链表概述
链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以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 }
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/11849.html