备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

C/C++中对链表操作的理解&&实例分析

2017-07-10 782
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 链表概述　　 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。

链表概述
　　 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。
        链表的各类操作包括：学习单向链表的创建、删除、  插入（无序、有序）、输出、  排序（选择、插入、冒泡）、反序等等。

       单向链表的图示：
       ---->[NULL]
      head

      图1：空链表

       ---->[p1]---->[p2]...---->[pn]---->[NULL]
      head   p1->next  p2->next   pn->next

      图2：有N个节点的链表

      创建n个节点的链表的函数为：

 

 1 #include "stdlib.h"
 2 #include "stdio.h"
 3 
 4 #define NULL 0
 5 #define LEN sizeof(struct student)
 6 
 7 struct student
 8 {
 9     int num;              //学号 
10     float score;          //分数，其他信息可以继续在下面增加字段
11     struct student *next;        //指向下一节点的指针
12 };
13 
14 int n;    //节点总数 
15 /*
16 ==========================
17 功能：创建n个节点的链表
18 返回：指向链表表头的指针
19 ==========================
20 */
21 struct student *Create()
22 {
23     struct student *head;        //头节点
24     struct student *p1 = NULL;    //p1保存创建的新节点的地址
25     struct student *p2 = NULL;    //p2保存原链表最后一个节点的地址
26 
27     n = 0;            //创建前链表的节点总数为0：空链表
28     p1 = (struct student *) malloc (LEN);    //开辟一个新节点
29     p2 = p1;            //如果节点开辟成功，则p2先把它的指针保存下来以备后用
30 
31     if(p1==NULL)        //节点开辟不成功
32     {
33         printf ("\nCann't create it, try it again in a moment!\n");
34         return NULL;
35     }
36     else                //节点开辟成功
37     {
38         head = NULL;        //开始head指向NULL
39         printf ("Please input %d node -- num,score: ", n + 1);
40         scanf ("%d %f", &(p1->num), &(p1->score));    //录入数据
41     }
42     while(p1->num != 0)        //只要学号不为0，就继续录入下一个节点
43     {
44         n += 1;            //节点总数增加1个
45         if(n == 1)        //如果节点总数是1，则head指向刚创建的节点p1
46         {
47             head = p1;
48             p2->next = NULL;  //此时的p2就是p1,也就是p1->next指向NULL。
49         }
50         else
51         {
52             p2->next = p1;    //指向上次下面刚刚开辟的新节点
53         }
54 
55         p2 = p1;            //把p1的地址给p2保留，然后p1产生新的节点
56 
57         p1 = (struct student *) malloc (LEN);
58         printf ("Please input %d node -- num,score: ", n + 1);
59         scanf ("%d %f", &(p1->num), &(p1->score));
60     }
61     p2->next = NULL;        //此句就是根据单向链表的最后一个节点要指向NULL
62 
63     free(p1);            //p1->num为0的时候跳出了while循环，并且释放p1
64     p1 = NULL;            //特别不要忘记把释放的变量清空置为NULL,否则就变成"野指针"，即地址不确定的指针
65     return head;        //返回创建链表的头指针 
66 }

 

输出链表中节点的函数为：

 1 /*
 2 ===========================
 3  功能：输出节点
 4  返回： void
 5 ===========================
 6 */
 7 void Print(struct student *head)
 8 {
 9     struct student *p;
10     printf ("\nNow , These %d records are:\n", n);
11     p = head;
12     if(head != NULL)        //只要不是空链表，就输出链表中所有节点
13     {
14         printf("head is %o\n", head);     //输出头指针指向的地址
15         do
16         {
17             /*
18             输出相应的值：当前节点地址、各字段值、当前节点的下一节点地址。
19             这样输出便于读者形象看到一个单向链表在计算机中的存储结构，和我们
20             设计的图示是一模一样的。
21             */
22             printf ("%o   %d   %5.1f   %o\n", p, p->num, p->score, p->next);
23             p = p->next;        //移到下一个节点
24         }
25         while (p != NULL);
26     }
27 }/*
28 ===========================
29  功能：输出节点
30  返回： void
31 ===========================
32 */
33 void Print(struct student *head)
34 {
35     struct student *p;
36     printf ("\nNow , These %d records are:\n", n);
37     p = head;
38     if(head != NULL)        //只要不是空链表，就输出链表中所有节点
39     {
40         printf("head is %o\n", head);     //输出头指针指向的地址
41         do
42         {
43             /*
44             输出相应的值：当前节点地址、各字段值、当前节点的下一节点地址。
45             这样输出便于读者形象看到一个单向链表在计算机中的存储结构，和我们
46             设计的图示是一模一样的。
47             */
48             printf ("%o   %d   %5.1f   %o\n", p, p->num, p->score, p->next);
49             p = p->next;        //移到下一个节点
50         }
51         while (p != NULL);
52     }
53 }

单向链表的删除图示：
       ---->[NULL]
       head

       图3：空链表

      从图3可知，空链表显然不能删除

      ---->[1]---->[2]...---->[n]---->[NULL]（原链表）
      head   1->next  2->next   n->next

      ---->[2]...---->[n]---->[NULL]（删除后链表）
      head   2->next   n->next

      图4：有N个节点的链表，删除第一个节点
      结合原链表和删除后的链表，就很容易写出相应的代码。操作方法如下：
      1、你要明白head就是第1个节点，head->next就是第2个节点；
       2、删除后head指向第2个节点，就是让head=head->next,OK这样就行了。
       ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）
       head   1->next  2->next  3->next   n->next

       ---->[1]---->[3]...---->[n]---->[NULL]（删除后链表）
      head   1->next  3->next   n->next

      图5：有N个节点的链表，删除中间一个（这里图示删除第2个）
      结合原链表和删除后的链表，就很容易写出相应的代码。操作方法如下：
      1、你要明白head就是第1个节点，1->next就是第2个节点，2->next就是第3个节点；
      2、删除后2，1指向第3个节点，就是让1->next=2->next。

      删除指定学号的节点的函数为：

 

 1 /*
 2 ==========================
 3  功能：删除指定节点
 4   (此例中是删除指定学号的节点)
 5  返回：指向链表表头的指针
 6 ==========================
 7 */
 8 struct student *Del (struct student *head, int num)
 9 {
10     struct student *p1;        //p1保存当前需要检查的节点的地址
11     struct student *p2;        //p2保存当前检查过的节点的地址
12     if (head == NULL)        //是空链表（结合图3理解）
13     {
14         printf ("\nList is null!\n");
15         return head;
16     }
17 
18     //定位要删除的节点
19     p1 = head;
20     while (p1->num != num && p1->next != NULL)    //p1指向的节点不是所要查找的，并且它不是最后一个节点，就继续往下找
21     {
22         p2 = p1;            //保存当前节点的地址
23         p1 = p1->next;        //后移一个节点
24     }
25 
26     if(p1->num==num)        //找到了。（结合图4、5理解）
27     {
28         if (p1 == head)        //如果要删除的节点是第一个节点
29         {
30             head = p1->next;    //头指针指向第一个节点的后一个节点，也就是第二个节点。这样第一个节点就不在链表中，即删除
31         }
32         else            //如果是其它节点，则让原来指向当前节点的指针，指向它的下一个节点，完成删除
33         {
34             p2->next = p1->next;
35         }
36 
37         free (p1);        //释放当前节点
38         p1 = NULL;
39         printf ("\ndelete %ld success!\n", num);
40         n -= 1;            //节点总数减1个
41     }
42     else                //没有找到
43     {
44         printf ("\n%ld not been found!\n", num);
45     }
46 
47     return head;
48 }

 

单向链表的插入图示：
       ---->[NULL]（原链表）
      head

      ---->[1]---->[NULL]（插入后的链表）
      head   1->next

      图7 空链表插入一个节点
      结合原链表和插入后的链表，就很容易写出相应的代码。操作方法如下：
     1、你要明白空链表head指向NULL就是head=NULL；
     2、插入后head指向第1个节点，就是让head=1,1->next=NULL,OK这样就行了。

     ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）
     head   1->next  2->next  3->next   n->next

     ---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL]（插入后的链表）
     head   1->next  2->next  x->next  3->next   n->next

     图8：有N个节点的链表，插入一个节点（这里图示插入第2个后面）
     结合原链表和插入后的链表，就很容易写出相应的代码。操作方法如下：
    1、你要明白原1->next就是节点2，2->next就是节点3；
    2、插入后x指向第3个节点,2指向x，就是让x->next=2->next,1->next=x。

    插入指定节点的后面的函数为：

 1 /*
 2 ==========================
 3  功能：插入指定节点的后面
 4   (此例中是指定学号的节点)
 5  返回：指向链表表头的指针
 6 ==========================
 7 */
 8 struct student *Insert (struct student *head, int num, struct student *node)
 9 {
10     struct student *p1;        //p1保存当前需要检查的节点的地址
11     if (head == NULL)        //（结合图示7理解）
12     {
13         head = node;
14         node->next = NULL;
15         n += 1;
16         return head;
17     }
18 
19     p1 = head;
20     while(p1->num != num && p1->next != NULL)     //p1指向的节点不是所要查找的，并且它不是最后一个节点，继续往下找
21     {
22         p1 = p1->next;        //后移一个节点
23     }
24 
25     if (p1->num==num)        //找到了（结合图示8理解）
26     {
27         node->next = p1->next;    //显然node的下一节点是原p1的next
28         p1->next = node;        //插入后，原p1的下一节点就是要插入的node
29         n += 1;            //节点总数增加1个
30     }
31     else
32     {
33         printf ("\n%ld not been found!\n", num);
34     }
35     return head;
36 }

单向链表的反序图示：
       ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原链表）
       head   1->next  2->next  3->next   n->next

      [NULL]<----[1]<----[2]<----[3]<----...[n]<----（反序后的链表）
                1->next  2->next  3->next   n->next  head

          图9：有N个节点的链表反序
          结合原链表和插入后的链表，就很容易写出相应的代码。操作方法如下：
          1、我们需要一个读原链表的指针p2,存反序链表的p1=NULL（刚好最后一个节点的next为NULL）,还有一个临时存储变量p；
          2、p2在原链表中读出一个节点，我们就把它放到p1中，p就是用来处理节点放置顺序的问题；
          3、比如，现在我们取得一个2,为了我们继续往下取节点，我们必须保存它的next值，由原链表可知p=2->next;
          4、然后由反序后的链表可知，反序后2->next要指向1，则2->next=1;
          5、好了，现在已经反序一个节点，接着处理下一个节点就需要保存此时的信息：
          p1变成刚刚加入的2，即p1=2;p2要变成它的下一节点，就是上面我们保存的p,即p2=p。

          反序链表的函数为：

 1 /*
 2 ==========================
 3  功能：反序节点
 4   (链表的头变成链表的尾，链表的尾变成头)
 5  返回：指向链表表头的指针
 6 ==========================
 7 */
 8 
 9 struct student *Reverse (struct student *head)
10 {
11     struct student *p;        //临时存储
12     struct student *p1;        //存储返回结果
13     struct student *p2;        //源结果节点一个一个取
14 
15     p1 = NULL;            //开始颠倒时，已颠倒的部分为空
16     p2 = head;            //p2指向链表的头节点
17     while(p2 != NULL)
18     {
19         p = p2->next;
20         p2->next = p1;
21         p1 = p2;
22         p2 = p;
23     }
24     head = p1;
25     return head;
26 }

  对链表进行选择排序的基本思想就是反复从还未排好序的那些节点中，选出键值（就是用它排序的字段，我们取学号num为键值）最小的节点，依次重新组合成一个链表。

         我认为写链表这类程序，关键是理解：head存储的是第一个节点的地址，head->next存储的是第二个节点的地址；任意一个节点p的地址，只能通过它前一个节点的next来求得。

        单向链表的选择排序图示：
         ---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原链表）
         head   1->next  3->next  2->next   n->next

         ---->[NULL]（空链表）
        first
        tail

         ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后链表）
         first   1->next  2->next  3->next   tail->next

         图10：有N个节点的链表选择排序

        1、先在原链表中找最小的，找到一个后就把它放到另一个空的链表中；
        2、空链表中安放第一个进来的节点，产生一个有序链表,并且让它在原链表中分离出来（此时要注意原链表中出来的是第一个节点还是中间其它节点）；
        3、继续在原链表中找下一个最小的，找到后把它放入有序链表的尾指针的next,然后它变成其尾指针；

        对链表进行选择排序的函数为：

 1 /*
 2 ==========================
 3  功能：选择排序(由小到大)
 4  返回：指向链表表头的指针
 5 ==========================
 6 */
 7 struct student *SelectSort (struct student *head)
 8 {
 9     struct student *first;       //排列后有序链的表头指针
10     struct student *tail;      //排列后有序链的表尾指针
11     struct student *p_min;       //保留键值更小的节点的前驱节点的指针
12     struct student *min;       //存储最小节点
13     struct student *p;           //当前比较的节点
14 
15     first = NULL;
16     while(head != NULL)          //在链表中找键值最小的节点
17     {
18         //注意：这里for语句就是体现选择排序思想的地方
19         for (p = head, min = head; p->next != NULL; p = p->next)    //循环遍历链表中的节点，找出此时最小的节点
20         {
21             if (p->next->num < min->num)     //找到一个比当前min小的节点
22             {
23                 p_min = p;          //保存找到节点的前驱节点：显然p->next的前驱节点是p
24                 min = p->next;      //保存键值更小的节点
25             }
26         }
27 
28         //上面for语句结束后，就要做两件事；一是把它放入有序链表中；二是根据相应的条件判断，安排它离开原来的链表
29 
30         //第一件事
31         if (first == NULL)       //如果有序链表目前还是一个空链表
32         {
33             first = min;        //第一次找到键值最小的节点
34             tail = min;           //注意：尾指针让它指向最后的一个节点
35         }
36         else              //有序链表中已经有节点
37         {
38             tail->next = min;       //把刚找到的最小节点放到最后，即让尾指针的next指向它
39             tail = min;              //尾指针也要指向它
40         }
41 
42         //第二件事
43         if (min == head)            //如果找到的最小节点就是第一个节点
44         {
45             head = head->next;       //显然让head指向原head->next,即第二个节点，就OK
46         }
47         else            //如果不是第一个节点
48         {
49             p_min->next = min->next;    //前次最小节点的next指向当前min的next,这样就让min离开了原链表
50         }
51     }
52 
53     if (first != NULL)        //循环结束得到有序链表first
54     {
55         tail->next = NULL;    //单向链表的最后一个节点的next应该指向NULL
56     }
57     head = first;
58     return head;
59 }

对链表进行直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值（就是用它排序的字段，我们取学号num为键值）排好序的，对于节点n在这个序列中找插入位置，使得n插入后新序列仍然有序。按照这种思想，依次对链表从头到尾执行一遍，就可以使无序链表变为有序链表。

         单向链表的直接插入排序图示：
         ---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原链表）
        head   1->next  3->next  2->next   n->next

         ---->[1]---->[NULL]（从原链表中取第1个节点作为只有一个节点的有序链表）
        head
        图11

        ---->[3]---->[2]...---->[n]---->[NULL]（原链表剩下用于直接插入排序的节点）
        first   3->next  2->next   n->next
        图12

        ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后链表）
        head   1->next  2->next  3->next   n->next

        图13：有N个节点的链表直接插入排序

       1、先在原链表中以第一个节点为一个有序链表，其余节点为待定节点。
       2、从图12链表中取节点，到图11链表中定位插入。
       3、上面图示虽说画了两条链表，其实只有一条链表。在排序中，实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。
       这一点请读者务必搞清楚，要不然就可能认为它和上面的选择排序法一样了。

       对链表进行直接插入排序的函数为：

 1 /*
 2 ==========================
 3  功能：直接插入排序(由小到大)
 4  返回：指向链表表头的指针
 5 ==========================
 6 */
 7 struct student *InsertSort (struct student *head)
 8 {
 9     struct student *first;      //为原链表剩下用于直接插入排序的节点头指针
10     struct student *t;          //临时指针变量：插入节点
11     struct student *p,*q;     //临时指针变量
12 
13     first = head->next;        //原链表剩下用于直接插入排序的节点链表：可根据图12来理解
14     head->next = NULL;        //只含有一个节点的链表的有序链表：可根据图11来理解
15 
16     while(first != NULL)        //遍历剩下无序的链表
17     {
18         //注意：这里for语句就是体现直接插入排序思想的地方
19         for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next);    //无序节点在有序链表中找插入的位置
20 
21         //退出for循环，就是找到了插入的位置，应该将t节点插入到p节点之后，q节点之前
22         //注意：按道理来说，这句话可以放到下面注释了的那个位置也应该对的，但是就是不能。原因：你若理解了上面的第3条，就知道了
23         //下面的插入就是将t节点即是first节点插入到p节点之后，已经改变了first节点，所以first节点应该在被修改之前往后移动，不能放到下面注释的位置上去
24         first = first->next;    //无序链表中的节点离开，以便它插入到有序链表中
25 
26         if (q == head)        //插在第一个节点之前
27         {
28             head = t;
29         }
30         else            //p是q的前驱
31         {
32             p->next = t;
33         }
34         t->next = q;        //完成插入动作
35         //first = first->next; 
36     }
37     return head;
38 }

   对链表进行冒泡排序的基本思想就是对当前还未排好序的范围内的全部节点，自上而下对相邻的两个节点依次进行比较和调整，让键值（就是用它排 序的字段，我们取学号num为键值）较大的节点往下沉，键值较小的往上冒。即：每当两相邻的节点比较后发现它们的排序与排序要求相反时，就将它们互换。

        单向链表的冒泡排序图示：
        ---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原链表）
       head   1->next  3->next  2->next   n->next

       ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后链表）
       head   1->next  2->next  3->next   n->next

       图14：有N个节点的链表冒泡排序

      任意两个相邻节点p、q位置互换图示:
      假设p1->next指向p，那么显然p1->next->next就指向q,
      p1->next->next->next就指向q的后继节点，我们用p2保存
      p1->next->next指针。即：p2=p1->next->next，则有：
       [  ]---->[p]---------->[q]---->[  ]（排序前）
       p1->next  p1->next->next  p2->next
       图15

       [  ]---->[q]---------->[p]---->[  ]（排序后）

       图16

      1、排序后q节点指向p节点，在调整指向之前，我们要保存原p的指向节点地址，即：p2=p1->next->next；
      2、顺着这一步一步往下推,排序后图16中p1->next->next要指的是p2->next,所以p1->next->next=p2->next;
      3、在图15中p2->next原是q发出来的指向，排序后图16中q的指向要变为指向p的，而原来p1->next是指向p的，所以p2->next=p1->next;
      4、在图15中p1->next原是指向p的，排序后图16中p1->next要指向q,原来p1->next->next（即p2)是指向q的，所以p1->next=p2;
      5、至此，我们完成了相邻两节点的顺序交换。
      6、下面的程序描述改进了一点就是记录了每次最后一次节点下沉的位置，这样我们不必每次都从头到尾的扫描，只需要扫描到记录点为止。 因为后面的都已经是排好序的了。

       对链表进行冒泡排序的函数为：

 1 /*
 2 ==========================
 3  功能：冒泡排序(由小到大)
 4  返回：指向链表表头的指针
 5 ==========================
 6 */
 7 struct student *BubbleSort (struct student *head)
 8 {
 9     struct student *endpt;      //控制循环比较
10     struct student *p;          //临时指针变量
11     struct student *p1,*p2;
12 
13     p1 = (struct student *) malloc (LEN);
14     p1->next = head;           //注意理解：我们增加一个节点，放在第一个节点的前面，主要是为了便于比较。因为第一个节点没有前驱，我们不能交换地址
15     head = p1;                   //让head指向p1节点，排序完成后，我们再把p1节点释放掉
16 
17     for (endpt = NULL; endpt != head; endpt = p)    //结合第6点理解
18     {
19         for (p = p1 = head; p1->next->next != endpt; p1 = p1->next)
20         {
21             if (p1->next->num > p1->next->next->num)    //如果前面的节点键值比后面节点的键值大，则交换
22             {
23                 p2 = p1->next->next;      //结合第1点理解
24                 p1->next->next = p2->next;      //结合第2点理解
25                 p2->next = p1->next;     //结合第3点理解
26                 p1->next = p2;      //结合第4点理解
27                 p = p1->next->next;    //结合第6点理解
28             }
29         }
30     }
31 
32     p1 = head;                //把p1的信息去掉
33     head = head->next;        //让head指向排序后的第一个节点
34     free (p1);            //释放p1
35     p1 = NULL;            //p1置为NULL，保证不产生“野指针”，即地址不确定的指针变量
36 
37     return head;
38 }

有序链表插入节点示意图：

        ---->[NULL]（空有序链表）
        head

       图18：空有序链表（空有序链表好解决，直接让head指向它就是了。）

       以下讨论不为空的有序链表。
        ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（有序链表）
        head   1->next  2->next  3->next   n->next

       图18：有N个节点的有序链表

       插入node节点的位置有两种情况：一是第一个节点前，二是其它节点前或后。

       ---->[node]---->[1]---->[2]---->[3]...---->[n]---->[NULL]
       head  node->next  1->next  2->next  3->next   n->next

       图19：node节点插在第一个节点前

       ---->[1]---->[2]---->[3]...---->[node]...---->[n]---->[NULL]
      head   1->next  2->next  3->next    node->next  n->next

       插入有序链表的函数为：

 

 1 /*
 2 ==========================
 3  功能：插入有序链表的某个节点的后面(从小到大)
 4  返回：指向链表表头的指针
 5 ==========================
 6 */
 7 
 8 struct student *SortInsert (struct student *head, struct student *node)
 9 {
10     struct student *p;        //p保存当前需要检查的节点的地址
11     struct student *t;        //临时指针变量
12 
13     if (head == NULL)        //处理空的有序链表
14     {
15         head = node;
16         node->next = NULL;
17         n += 1;            //插入完毕，节点总数加
18         return head;
19     }
20 
21     p = head;              //有序链表不为空
22     while(p->num < node->num && p != NULL)       //p指向的节点的学号比插入节点的学号小，并且它不等于NULL
23     {
24         t = p;              //保存当前节点的前驱，以便后面判断后处理
25         p = p->next;        //后移一个节点
26     }
27 
28     if (p == head)        //刚好插入第一个节点之前
29     {
30         node->next = p;
31         head = node;
32     }
33     else                 //插入其它节点之后
34     {
35         t->next = node;        //把node节点加进去
36         node->next = p;
37     }
38     n += 1;            //插入完毕，节点总数加1
39 
40     return head;
41 }

 

综上所述，链表的各类操作函数的完整代码如下：

 

  1 #include "stdlib.h"
  2 #include "stdio.h"
  3 
  4 #define NULL 0
  5 #define LEN sizeof(struct student)
  6 
  7 struct student
  8 {
  9     int num;              //学号 
 10     float score;          //分数，其他信息可以继续在下面增加字段
 11     struct student *next;        //指向下一节点的指针
 12 };
 13 
 14 int n;    //节点总数 
 15 /*
 16 ==========================
 17 功能：创建n个节点的链表
 18 返回：指向链表表头的指针
 19 ==========================
 20 */
 21 struct student *Create()
 22 {
 23     struct student *head;        //头节点
 24     struct student *p1 = NULL;    //p1保存创建的新节点的地址
 25     struct student *p2 = NULL;    //p2保存原链表最后一个节点的地址
 26 
 27     n = 0;            //创建前链表的节点总数为0：空链表
 28     p1 = (struct student *) malloc (LEN);    //开辟一个新节点
 29     p2 = p1;            //如果节点开辟成功，则p2先把它的指针保存下来以备后用
 30 
 31     if(p1==NULL)        //节点开辟不成功
 32     {
 33         printf ("\nCann't create it, try it again in a moment!\n");
 34         return NULL;
 35     }
 36     else                //节点开辟成功
 37     {
 38         head = NULL;        //开始head指向NULL
 39         printf ("Please input %d node -- num,score: ", n + 1);
 40         scanf ("%d %f", &(p1->num), &(p1->score));    //录入数据
 41     }
 42     while(p1->num != 0)        //只要学号不为0，就继续录入下一个节点
 43     {
 44         n += 1;            //节点总数增加1个
 45         if(n == 1)        //如果节点总数是1，则head指向刚创建的节点p1
 46         {
 47             head = p1;
 48             p2->next = NULL;  //此时的p2就是p1,也就是p1->next指向NULL。
 49         }
 50         else
 51         {
 52             p2->next = p1;    //指向上次下面刚刚开辟的新节点
 53         }
 54 
 55         p2 = p1;            //把p1的地址给p2保留，然后p1产生新的节点
 56 
 57         p1 = (struct student *) malloc (LEN);
 58         printf ("Please input %d node -- num,score: ", n + 1);
 59         scanf ("%d %f", &(p1->num), &(p1->score));
 60     }
 61     p2->next = NULL;        //此句就是根据单向链表的最后一个节点要指向NULL
 62 
 63     free(p1);            //p1->num为0的时候跳出了while循环，并且释放p1
 64     p1 = NULL;            //特别不要忘记把释放的变量清空置为NULL,否则就变成"野指针"，即地址不确定的指针
 65     return head;        //返回创建链表的头指针 
 66 }
 67 
 68 
 69 /*
 70 ===========================
 71  功能：输出节点
 72  返回： void
 73 ===========================
 74 */
 75 void Print(struct student *head)
 76 {
 77     struct student *p;
 78     printf ("\nNow , These %d records are:\n", n);
 79     p = head;
 80     if(head != NULL)        //只要不是空链表，就输出链表中所有节点
 81     {
 82         printf("head is %o\n", head);     //输出头指针指向的地址
 83         do
 84         {
 85             /*
 86             输出相应的值：当前节点地址、各字段值、当前节点的下一节点地址。
 87             这样输出便于读者形象看到一个单向链表在计算机中的存储结构，和我们
 88             设计的图示是一模一样的。
 89             */
 90             printf ("%o   %d   %5.1f   %o\n", p, p->num, p->score, p->next);
 91             p = p->next;        //移到下一个节点
 92         }
 93         while (p != NULL);
 94     }
 95 }
 96 
 97 /*
 98 ==========================
 99  功能：删除指定节点
100   (此例中是删除指定学号的节点)
101  返回：指向链表表头的指针
102 ==========================
103 */
104 struct student *Del (struct student *head, int num)
105 {
106     struct student *p1;        //p1保存当前需要检查的节点的地址
107     struct student *p2;        //p2保存当前检查过的节点的地址
108     if (head == NULL)        //是空链表（结合图3理解）
109     {
110         printf ("\nList is null!\n");
111         return head;
112     }
113 
114     //定位要删除的节点
115     p1 = head;
116     while (p1->num != num && p1->next != NULL)    //p1指向的节点不是所要查找的，并且它不是最后一个节点，就继续往下找
117     {
118         p2 = p1;            //保存当前节点的地址
119         p1 = p1->next;        //后移一个节点
120     }
121 
122     if(p1->num==num)        //找到了。（结合图4、5理解）
123     {
124         if (p1 == head)        //如果要删除的节点是第一个节点
125         {
126             head = p1->next;    //头指针指向第一个节点的后一个节点，也就是第二个节点。这样第一个节点就不在链表中，即删除
127         }
128         else            //如果是其它节点，则让原来指向当前节点的指针，指向它的下一个节点，完成删除
129         {
130             p2->next = p1->next;
131         }
132 
133         free (p1);        //释放当前节点
134         p1 = NULL;
135         printf ("\ndelete %ld success!\n", num);
136         n -= 1;            //节点总数减1个
137     }
138     else                //没有找到
139     {
140         printf ("\n%ld not been found!\n", num);
141     }
142 
143     return head;
144 }
145 
146 //销毁链表
147 void DestroyList(struct student *head)
148 {
149     struct student *p;
150     if(head==NULL)
151         return 0;
152     while(head)
153     {
154         p=head->next;
155         free(head);
156         head=p;
157     }
158     return 1;
159 }
160 
161 /*
162 ==========================
163  功能：插入指定节点的后面
164   (此例中是指定学号的节点)
165  返回：指向链表表头的指针
166 ==========================
167 */
168 struct student *Insert (struct student *head, int num, struct student *node)
169 {
170     struct student *p1;        //p1保存当前需要检查的节点的地址
171     if (head == NULL)        //（结合图示7理解）
172     {
173         head = node;
174         node->next = NULL;
175         n += 1;
176         return head;
177     }
178 
179     p1 = head;
180     while(p1->num != num && p1->next != NULL)     //p1指向的节点不是所要查找的，并且它不是最后一个节点，继续往下找
181     {
182         p1 = p1->next;        //后移一个节点
183     }
184 
185     if (p1->num==num)        //找到了（结合图示8理解）
186     {
187         node->next = p1->next;    //显然node的下一节点是原p1的next
188         p1->next = node;        //插入后，原p1的下一节点就是要插入的node
189         n += 1;            //节点总数增加1个
190     }
191     else
192     {
193         printf ("\n%ld not been found!\n", num);
194     }
195     return head;
196 }
197 
198 /*
199 ==========================
200  功能：反序节点
201   (链表的头变成链表的尾，链表的尾变成头)
202  返回：指向链表表头的指针
203 ==========================
204 */
205 
206 struct student *Reverse (struct student *head)
207 {
208     struct student *p;        //临时存储
209     struct student *p1;        //存储返回结果
210     struct student *p2;        //源结果节点一个一个取
211 
212     p1 = NULL;            //开始颠倒时，已颠倒的部分为空
213     p2 = head;            //p2指向链表的头节点
214     while(p2 != NULL)
215     {
216         p = p2->next;
217         p2->next = p1;
218         p1 = p2;
219         p2 = p;
220     }
221     head = p1;
222     return head;
223 }
224 /*
225 ==========================
226  功能：选择排序(由小到大)
227  返回：指向链表表头的指针
228 ==========================
229 */
230 struct student *SelectSort (struct student *head)
231 {
232     struct student *first;       //排列后有序链的表头指针
233     struct student *tail;      //排列后有序链的表尾指针
234     struct student *p_min;       //保留键值更小的节点的前驱节点的指针
235     struct student *min;       //存储最小节点
236     struct student *p;           //当前比较的节点
237 
238     first = NULL;
239     while(head != NULL)          //在链表中找键值最小的节点
240     {
241         //注意：这里for语句就是体现选择排序思想的地方
242         for (p = head, min = head; p->next != NULL; p = p->next)    //循环遍历链表中的节点，找出此时最小的节点
243         {
244             if (p->next->num < min->num)     //找到一个比当前min小的节点
245             {
246                 p_min = p;          //保存找到节点的前驱节点：显然p->next的前驱节点是p
247                 min = p->next;      //保存键值更小的节点
248             }
249         }
250 
251         //上面for语句结束后，就要做两件事；一是把它放入有序链表中；二是根据相应的条件判断，安排它离开原来的链表
252 
253         //第一件事
254         if (first == NULL)       //如果有序链表目前还是一个空链表
255         {
256             first = min;        //第一次找到键值最小的节点
257             tail = min;           //注意：尾指针让它指向最后的一个节点
258         }
259         else              //有序链表中已经有节点
260         {
261             tail->next = min;       //把刚找到的最小节点放到最后，即让尾指针的next指向它
262             tail = min;              //尾指针也要指向它
263         }
264 
265         //第二件事
266         if (min == head)            //如果找到的最小节点就是第一个节点
267         {
268             head = head->next;       //显然让head指向原head->next,即第二个节点，就OK
269         }
270         else            //如果不是第一个节点
271         {
272             p_min->next = min->next;    //前次最小节点的next指向当前min的next,这样就让min离开了原链表
273         }
274     }
275 
276     if (first != NULL)        //循环结束得到有序链表first
277     {
278         tail->next = NULL;    //单向链表的最后一个节点的next应该指向NULL
279     }
280     head = first;
281     return head;
282 }
283 
284 
285 /*
286 ==========================
287  功能：直接插入排序(由小到大)
288  返回：指向链表表头的指针
289 ==========================
290 */
291 struct student *InsertSort (struct student *head)
292 {
293     struct student *first;      //为原链表剩下用于直接插入排序的节点头指针
294     struct student *t;          //临时指针变量：插入节点
295     struct student *p,*q;     //临时指针变量
296 
297     first = head->next;        //原链表剩下用于直接插入排序的节点链表：可根据图12来理解
298     head->next = NULL;        //只含有一个节点的链表的有序链表：可根据图11来理解
299 
300     while(first != NULL)        //遍历剩下无序的链表
301     {
302         //注意：这里for语句就是体现直接插入排序思想的地方
303         for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next);    //无序节点在有序链表中找插入的位置
304 
305         //退出for循环，就是找到了插入的位置，应该将t节点插入到p节点之后，q节点之前
306         //注意：按道理来说，这句话可以放到下面注释了的那个位置也应该对的，但是就是不能。原因：你若理解了上面的第3条，就知道了
307         //下面的插入就是将t节点即是first节点插入到p节点之后，已经改变了first节点，所以first节点应该在被修改之前往后移动，不能放到下面注释的位置上去
308         first = first->next;    //无序链表中的节点离开，以便它插入到有序链表中
309 
310         if (q == head)        //插在第一个节点之前
311         {
312             head = t;
313         }
314         else            //p是q的前驱
315         {
316             p->next = t;
317         }
318         t->next = q;        //完成插入动作
319         //first = first->next; 
320     }
321     return head;
322 }
323 
324 /*
325 ==========================
326  功能：冒泡排序(由小到大)
327  返回：指向链表表头的指针
328 ==========================
329 */
330 struct student *BubbleSort (struct student *head)
331 {
332     struct student *endpt;      //控制循环比较
333     struct student *p;          //临时指针变量
334     struct student *p1,*p2;
335 
336     p1 = (struct student *) malloc (LEN);
337     p1->next = head;           //注意理解：我们增加一个节点，放在第一个节点的前面，主要是为了便于比较。因为第一个节点没有前驱，我们不能交换地址
338     head = p1;                   //让head指向p1节点，排序完成后，我们再把p1节点释放掉
339 
340     for (endpt = NULL; endpt != head; endpt = p)    //结合第6点理解
341     {
342         for (p = p1 = head; p1->next->next != endpt; p1 = p1->next)
343         {
344             if (p1->next->num > p1->next->next->num)    //如果前面的节点键值比后面节点的键值大，则交换
345             {
346                 p2 = p1->next->next;      //结合第1点理解
347                 p1->next->next = p2->next;      //结合第2点理解
348                 p2->next = p1->next;     //结合第3点理解
349                 p1->next = p2;      //结合第4点理解
350                 p = p1->next->next;    //结合第6点理解
351             }
352         }
353     }
354 
355     p1 = head;                //把p1的信息去掉
356     head = head->next;        //让head指向排序后的第一个节点
357     free (p1);            //释放p1
358     p1 = NULL;            //p1置为NULL，保证不产生“野指针”，即地址不确定的指针变量
359 
360     return head;
361 }
362 
363 /*
364 ==========================
365  功能：插入有序链表的某个节点的后面(从小到大)
366  返回：指向链表表头的指针
367 ==========================
368 */
369 
370 struct student *SortInsert (struct student *head, struct student *node)
371 {
372     struct student *p;        //p保存当前需要检查的节点的地址
373     struct student *t;        //临时指针变量
374 
375     if (head == NULL)        //处理空的有序链表
376     {
377         head = node;
378         node->next = NULL;
379         n += 1;            //插入完毕，节点总数加
380         return head;
381     }
382 
383     p = head;              //有序链表不为空
384     while(p->num < node->num && p != NULL)       //p指向的节点的学号比插入节点的学号小，并且它不等于NULL
385     {
386         t = p;              //保存当前节点的前驱，以便后面判断后处理
387         p = p->next;        //后移一个节点
388     }
389 
390     if (p == head)        //刚好插入第一个节点之前
391     {
392         node->next = p;
393         head = node;
394     }
395     else                 //插入其它节点之后
396     {
397         t->next = node;        //把node节点加进去
398         node->next = p;
399     }
400     n += 1;            //插入完毕，节点总数加1
401 
402     return head;
403 }
404 
405 /*
406 以上函数的测试程序：
407 提示：根据测试函数的不同注释相应的程序段，这也是一种测试方法。
408 */
409 int main(void)
410 {
411     struct student *head;
412     struct student *stu;
413     int thenumber;
414 
415     // 测试Create()、Print() 
416     head = Create();
417     Print(head);
418 
419     //测试Del()
420     printf("\nWhich one delete: ");
421     scanf("%d",&thenumber);
422     head = Del(head,thenumber);
423     Print(head);
424 
425     //测试Insert()
426     stu = (struct student *)malloc(LEN);
427     printf("\nPlease input insert node -- num,score: ");
428     scanf("%d %f",&stu->num,&stu->score);
429     printf("\nInsert behind num: ");
430     scanf("%d",&thenumber);
431     head = Insert(head,thenumber,stu);
432     Print(head);
433 
434     //测试Reverse()
435     printf("\nReverse the LinkList: \n");
436     head = Reverse(head);
437     Print(head);
438 
439     //测试SelectSort()
440     printf("\nSelectSort the LinkList: \n");
441     head = SelectSort(head);
442     Print(head);
443 
444     //测试InsertSort()
445     printf("\nInsertSort the LinkList: \n");
446     head = InsertSort(head);
447     Print(head);
448 
449     //测试BubbleSort()
450     printf("\nBubbleSort the LinkList: \n");
451     head = BubbleSort(head);
452     Print(head);
453 
454     printf("\nSortInsert the LinkList: \n");
455     //测试SortInsert():上面创建链表，输入节点时请注意学号num从小到大的顺序
456     stu = (struct student *)malloc(LEN);
457     printf("\nPlease input insert node -- num,score: ");
458     scanf("%d %f",&stu->num,&stu->score);
459     head = SortInsert(head,stu);
460     Print(head);
461 
462     //销毁链表
463     DestroyList(head);
464 
465     printf ("\n");
466     system ("pause");
467 }

 

文章标签：
存储
测试技术
C++
机器学习/深度学习
关键词：
C++链表
C++分析
C++实例分析
angel_kitty
目录
相关文章
北飞的山羊
|
21天前
|
C++
【链表】还不会用C++实现链表？一文教会你各种链表的实现
【链表】还不会用C++实现链表？一文教会你各种链表的实现
北飞的山羊
24 0
蒾酒
|
1月前
|
存储 Java 编译器
java和c++的主要区别、各自的优缺点分析、java跨平台的原理的深度解析
java和c++的主要区别、各自的优缺点分析、java跨平台的原理的深度解析
蒾酒
71 0
SarPro
|
2月前
|
存储 自然语言处理 算法
【编译原理】LR(1)分析法：C/C++实现
【编译原理】LR(1)分析法：C/C++实现
SarPro
61 0
泡沫o0
|
24天前
|
算法 安全 大数据
【C/C++ 随机函数行为】深入探索C++中的随机数：std::random_device与rand的行为分析（二）
【C/C++ 随机函数行为】深入探索C++中的随机数：std::random_device与rand的行为分析
泡沫o0
46 0
泡沫o0
|
23天前
|
算法 Java C++
【C/C++ 内存知识扩展】内存不足的可能性分析
【C/C++ 内存知识扩展】内存不足的可能性分析
泡沫o0
12 0
泡沫o0
|
23天前
|
存储 监控 Linux
Linux 使用getrusage系统调用获取cpu信息：一个C++实例分析
Linux 使用getrusage系统调用获取cpu信息：一个C++实例分析
泡沫o0
48 0
泡沫o0
|
23天前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
泡沫o0
36 0
泡沫o0
|
24天前
|
算法 安全 数据安全/隐私保护
【C/C++ 随机函数行为】深入探索C++中的随机数：std::random_device与rand的行为分析（一）
【C/C++ 随机函数行为】深入探索C++中的随机数：std::random_device与rand的行为分析
泡沫o0
45 0
泡沫o0
|
30天前
|
存储 缓存 算法
C++链表解析：从基础原理到高级应用，全面掌握链表的使用
C++链表解析：从基础原理到高级应用，全面掌握链表的使用
泡沫o0
49 0
ST小智
|
1月前
|
存储 编译器 C++
嵌入式中C++ 编程习惯与编程要点分析
嵌入式中C++ 编程习惯与编程要点分析
ST小智
18 1

热门文章

最新文章

  • 1
    【C++ 17 新特性 文件管理】探索C++ Filesystem库：文件和目录操作的全面指南（一）
  • 2
    【C++ 函数调用操作符】探究C++中的函数调用操作符 基础到高级应用
  • 3
    C++ 智能指针与 JSON 处理：高级编程技巧与常见问题解析
  • 4
    【C++ 泛型编程 高级篇】使用SFINAE和if constexpr灵活处理类型进行条件编译
  • 5
    C++文件格式深度解析：从底层结构到关键特性
  • 6
    【C++ 泛型编程 进阶篇】深入探究C++模板参数推导：从基础到高级
  • 7
    【C++ 17 新特性 文件管理】探索C++ Filesystem库：文件和目录操作的全面指南（二）
  • 8
    【C++ TypeName用法 】掌握C++中的TypeName：模板编程的瑞士军刀
  • 9
    从Proto到C++：探索Protocol Buffers的强大转换机制
  • 10
    【C++ 泛型编程 高级篇】C++模板元编程：使用模板特化 灵活提取嵌套类型与多容器兼容性
  • 1
    【C++成长记】C++入门 | 类和对象（下） |Static成员、 友元
    14
  • 2
    【C++成长记】C++入门 | 类和对象（中） |拷贝构造函数、赋值运算符重载、const成员函数、 取地址及const取地址操作符重载
    13
  • 3
    畅游网络：构建C++网络爬虫的指南
    19
  • 4
    C++从遗忘到入门（上）
    19
  • 5
    【实战项目】网络编程：在Linux环境下基于opencv和socket的人脸识别系统--C++实现
    20
  • 6
    C++和Java中的随机函数你玩明白了吗？内附LeetCode470.rand7()爆改rand10()巨详细题解，带你打败LeetCode%99选手
    12
  • 7
    【C++对于C语言的扩充】C++与C语言的联系，命名空间、C++中的输入输出以及缺省参数
    22
  • 8
    【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
    24
  • 9
    Dev-C++详细安装教程及中文设置（附带安装包链接）
    25
  • 10
    C++ const修饰符
    16

    • 相关课程

    更多
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    阿里云oss简介和使用流程
    为什么选择阿里云什么是云计算全球基础设施技术领先稳定可靠安全合规分析师报告
    产品和定价全部产品免费试用产品动态产品定价价格计算器云上成本管理
    解决方案技术解决方案
    文档与社区文档开发者社区天池大赛培训与认证
    权益中心免费试用高校计划企业扶持计划推荐返现计划
    支持与服务基础服务企业增值服务迁云服务官网公告健康看板信任中心
    关注阿里云
    关注阿里云公众号或下载阿里云APP，关注云资讯，随时随地运维管控云服务
    阿里云APP阿里云微信
    联系我们：4008013260
    法律声明Cookies政策廉正举报安全举报联系我们加入我们
    阿里巴巴集团淘宝网天猫全球速卖通阿里巴巴国际交易市场1688阿里妈妈飞猪阿里云计算AliOS万网高德UC友盟优酷钉钉支付宝达摩院淘宝海外阿里云盘饿了么
    © 2009-2024 Aliyun.com 版权所有 增值电信业务经营许可证： 浙B2-20080101 域名注册服务机构许可： 浙D3-20210002 京D3-20220015
    浙公网安备 33010602009975号浙B2-20080101-4