链表的基础概念

一、在学习链表时我们需要了解几个基础概念：

1.结点：当我们在使用动态分配方法为一个结构分配内存空间时，每次分配一块空间可用来存放一个结构体对象的数据，这块空间我们可以称之为结点。
2.指针域：指针可以用于节点之间的联系，在结点结构体中定义一个结构体成员项来存放下一结点的首地址（指针），这个成员称为 指针域。使用动态分配时，结点之间可以不连续，但结点内是连续的。
3.链表：我们可以在第一个结点的指针域内存入第二个结点的首地址，在第二个结点的指针域内存如第三个结点的首地址，这样串联下去直到最后一个结点。最后一个结点因为没有后续结点，其指针域可以赋值为0。像我们这样连接的方式，称为链表。

二、链表的基本操作：

1.建立链表
2.链表的查找和输出
3.插入一个结点
4.删除一个结点

三、创建一个简单的链表

如下代码:

#include <iostream>

#define NULL_VALUE 0
#define TYPE_FUNC struct student
#define LEN sizeof (struct student)

using namespace std;

struct student
{
    int num;
    int age;
    struct student *next;
};

TYPE_FUNC *creat(int n)
{
    struct student *head = nullptr ,*banner = nullptr,*bottom;
    int i;
    for (i = 0; i < n ; i++)
    {
        //bottom = (TYPE_FUNC *)malloc(LEN);
        bottom = new TYPE_FUNC[LEN]();
        cout << "Please enter num and age : " << endl;
        cin >> bottom->num;
        cin.get();
        cin >> bottom->age;

        i == 0?banner = head = bottom:banner->next = bottom;
        bottom->next = NULL_VALUE;
        banner = bottom;
    }
    return head;
}

int main(int argc, const char * argv[])
{
    cout << "请输入结点个数 ：" << endl;
    int num;
    cin >> num;
    creat(num);
    return 0;
}

说明

creat函数用于建立一个有n个节点的链表，它是一个指针函数返回值为一个指向student结构体的指针。在该函数内部，定义了三个student结构体的指针变量。head为头指针，banner为指向两个相邻结点的前一个结点的指针变量，bottom为后一结点的指针变量

四、链表的输出

如下代码：

void Print(struct student *head)
{
    struct student *pStudent;
    pStudent = head;
    if (head != NULL)
    {
        cout << "Head is : " << head << endl;
        do
        {
            cout << pStudent << endl << pStudent->age << endl << pStudent->num << "         " << endl << "         " << endl;
            pStudent = pStudent->next;
        } while (pStudent != NULL);
    }
}

输出结果：

请输入节点个数 ：
3
Please enter num and age : 
12
23
Please enter num and age : 
34
45
Please enter num and age : 
56
67
Head is : 0x10020a290
0x10020a290
23
12         
         
0x100400000
45
34         
         
0x100300160
67
56         
         
Program ended with exit code: 0
五、删除结点
#pragma mark -- 删除结点
TYPE_FUNC *deleList(TYPE_FUNC *head,int num)
{
    TYPE_FUNC *pStudent1;//保存当前需要检查的结点的地址
    TYPE_FUNC *pStudent2 = nullptr;//保存当前检查过的结点的地址

    if (head == NULL)//是空链表
    {
        cout << "List is NULL " << endl;
        return head;
    }

    pStudent1 = head;//定位要删除的结点

    /*
     *pStudent1指向的结点不是所要查找的且pStudent1不是最后一个节点，那就继续查找
     */
    while (pStudent1->num != num && pStudent1->next != NULL)
    {
        pStudent2 = pStudent1;//保存当前结点的地址
        pStudent1 = pStudent1->next;//查找下一个结点
    }

    /**找到了需要的结点**/
    if (pStudent1->num == num)
    {
        if (pStudent1 == head)//如果要删除的是第一个结点
        {
            /*
             *头指针指向第一个结点的指针域，第一个结点就不存在链表中了
             **/
            head = pStudent1->next;
        } else
        {
            /*
             *如果是其他结点，则让原来指向它的结点指向它的下一个结点，这样就完成删除
             **/
            pStudent2->next = pStudent1->next;
        }

        delete pStudent1;
        pStudent1 = NULL;
        cout << "Delete Success!" << endl;

    }else//没有查找到需要的结点
    {
        cout << "The list not been found !" << endl;
    }
    return head;
}
六、插入结点
#pragma mark 插入结点
TYPE_FUNC *insertList(TYPE_FUNC *head,int num,TYPE_FUNC *node)
{
    //pStudent1用来保存当前需要检查的结点的地址（指针）
    TYPE_FUNC *pStudent1;

    //如果链表为空，就让插入的结点作为第一个结点
    if (head == NULL)
    {
        head = node;
        node->next = NULL;
        return head;
    }

    pStudent1 = head;
    while (pStudent1->num != num && pStudent1->next != NULL)
    {
        pStudent1 = pStudent1->next;
    }

    if (pStudent1->num == num)
    {
        /*
         *node的下一结点就是原pStudent1的next
         *插入后，原pStudent1的下一结点就是要插入的node
         */
        node->next = pStudent1->next;
        pStudent1->next = node;
        cout << "Insert Success !" << endl;
    }
    else
    {
        cout << "List Not Found !" << endl;
    }

    return head;
}

int main(int argc, const char * argv[])
{
    cout << "请输入节点个数 ：" << endl;
    int number;
    cin >> number;

    TYPE_FUNC *head = creat(number);

    cout << "请输入需要插入的结点信息" << endl;

    TYPE_FUNC *node = new TYPE_FUNC[LEN]();
    cin >> node->num;


    cin.get();
    cin >> node->age;

    cout << "请输入需要插入的位置信息" << endl;
    int number2;
    cin >> number2;
    cin.get();
    insertList(head, number2, node);

    delete [] node;

    return 0;
}

输出结果：

请输入节点个数 ：
2
Please enter num and age : 
12
23
Please enter num and age : 
34
45
请输入需要插入的结点信息
78
90
请输入需要插入的位置信息
34
Insert Success !
Program ended with exit code: 0
七、链表的遍历
#pragma mark ---遍历链表
void traverseList(TYPE_FUNC *head)
{
    TYPE_FUNC *pStudent1;//记录将要遍历的结点
    if (head == NULL) {
        cout << "List is temp !" << endl;
    }

    pStudent1 =head;//从头开始

    while (pStudent1 != NULL) {
        cout << "*************************" << endl;
        cout << pStudent1->age << endl << pStudent1->num << endl;
        cout << "*************************" << endl;
        pStudent1 = pStudent1->next;
    }
    cout << "Traverse Success !" << endl;
}

控制台输出显示：

请输入节点个数 ：
3
Please enter num and age : 
12
23
Please enter num and age : 
34
45
Please enter num and age : 
56
67
*************************
12
23
*************************
*************************
34
45
*************************
*************************
56
67
*************************
Traverse Success !
Program ended with exit code: 0
八、链表的销毁
#pragma mark --销毁链表
void destroyList(TYPE_FUNC *head)
{

    TYPE_FUNC *sthdent;
    if (head == NULL) {
        cout << "List is NULL" << endl;
        return;
    }
    while (head) {
        sthdent = head->next;
        delete [] head;
        head = sthdent;
        cout << "Leading..." << endl;
    }
    cout << "Destroy Success !" << endl;
    return;
}

    destroyList(head);
    cin.get();
    cin.get();
    traverseList(head);

控制台输出显示：

请输入节点个数 ：
3
Please enter num and age : 
12
23
Please enter num and age : 
34
45
Please enter num and age : 
56
67
Destroy Success !

*************************
0
0
*************************
Traverse Success !
Program ended with exit code: 0
九、链表的清空
#pragma mark --清空链表
void clearList(TYPE_FUNC *head)
{
    TYPE_FUNC *student1,*student2;
    if (head == NULL) {
        cout << "List is NULL !" << endl;
        return;
    }

    student1 = head->next;
    while (head) {
        student2 = student1->next;
        delete [] student1;
        student1 = student2;
    }
    head->next = NULL;
    cout << "Clear Success !" << endl;
    return;
}
十、链表的逆置（普通方法）
TYPE_FUNC *reverseList(TYPE_FUNC *head)
{

    if (head == NULL || head->next == NULL) {
        cout << "List is NULL !" << endl;
        return head;
    }

    TYPE_FUNC *student2 = NULL;
    TYPE_FUNC *student1 = head;
    while (student1) {
        TYPE_FUNC *student3 = student1;
        student1 = student1->next;
        student3->next = student2;
        student2 = student3;
    }
    return student2;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 数据结构 第4讲 单链表
    本文来自本人著作《趣学数据结构》 链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么...
    rainchxy阅读 9,175评论 6赞 20
  • 数据结构第4-2讲双向链表
    链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么怎么表示逻辑上的相邻关系呢？ 可以...
    rainchxy阅读 6,296评论 0赞 6
  • 线性表复习和进阶学习
    大学的时候不好好学习，老师在讲台上讲课，自己在以为老师看不到的座位看小说，现在用到了老师讲的知识，只能自己看书查资...
    和珏猫阅读 5,314评论 1赞 3
  • ios -链表的简单认识
    作为一个资深的新手程序员😂,链表这些既基础又深奥的东西是日常工作中并不常见,但是却非常重要,所以就总结一下链表的简...
    Clark_new阅读 9,753评论 4赞 12
  • 诗画故乡 | 故乡的老藤椅
    ◎ 故乡的老藤椅 （文 \ 林嘉梓） 我不止一次地梦到你——故乡的老藤椅你是在我的梦中，亲昵地唤着我的乳名摇啊摇！...
    林嘉梓阅读 5,111评论 26赞 76