2022年C语言链表排序讲课稿.pdf

《2022年C语言链表排序讲课稿.pdf》由会员分享，可在线阅读，更多相关《2022年C语言链表排序讲课稿.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C 语 言 链 表 排 序精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 14 页 - - - - - - - - - - = 功能：选择排序(由小到大 ) 返回：指向链表表头的指针= */ /* 选择排序的基本思想就是反复从还未排好序的那些节点中，选出键值（就是用它排序的字段，我们取学号num 为键值）最小的节点，依次重新组合成一个链表。我认为写链表这类程序，关键是理解：head 存储的是第一个节点的地址，head-next存储的是第二个节点的地址；任意一个节点p 的地址，只能通过它前一个节

2、点的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、- - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 14 页 - - - - - - - - - - 3、继续在原链表中找下一个最小的，找到后把它放入有序链表的尾指针的next,然后它变成其尾指针；*/ struct student *SelectSort(struct student *head) struct student *first; /*排列后有序链的表头指针*/ struct student *tail; /*排列后有序链的表尾指针*/ struct student *p_min; /*保留键值更小的节点的前驱节点的指针*/ stru

4、ct student *min; /*存储最小节点 */ struct student *p; /*当前比较的节点*/ first = NULL; while (head != NULL) /*在链表中找键值最小的节点。*/ /*注意：这里for 语句就是体现选择排序思想的地方*/ for (p=head,min=head; p-next!=NULL; p=p-next) /*循环遍历链表中的节点，找出此时最小的节点。 */ if (p-next-num num) /*找到一个比当前min 小的节点。 */ p_min = p; /*保存找到节点的前驱节点：显然p-next 的前驱节点是p。*

5、/ min = p-next; /*保存键值更小的节点。*/ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 14 页 - - - - - - - - - - /*上面 for 语句结束后，就要做两件事；一是把它放入有序链表中；二是根据相应的条件判断，安排它离开原来的链表。*/ /*第一件事 */ if (first = NULL) /*如果有序链表目前还是一个空链表*/ first = min; /*第一次找到键值最小的节点。*/ tail = min; /* 注意：尾指针让它指向最后的一个

6、节点。*/ else /* 有序链表中已经有节点*/ tail-next = min; /*把刚找到的最小节点放到最后，即让尾指针的next 指向它。 */ tail = min; /* 尾指针也要指向它。*/ /*第二件事 */ if (min = head) /*如果找到的最小节点就是第一个节点*/ head = head-next; /*显然让 head 指向原 head-next, 即第二个节点，就OK*/ else /* 如果不是第一个节点*/ p_min-next = min-next; /*前次最小节点的next 指向当前min 的 next, 这样就让min 离开了原链表。 *

7、/ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 14 页 - - - - - - - - - - if (first != NULL) /*循环结束得到有序链表first*/ tail-next = NULL; /*单向链表的最后一个节点的next 应该指向 NULL*/ head = first; return head; /* = 功能：直接插入排序(由小到大 ) 返回：指向链表表头的指针= */ /* 直接插入排序的基本思想就是假设链表的前面n-1 个节点是已经按键值（就是用它排序的

8、字段，我们取学号num 为键值）排好序的，对于节点n 在这个序列中找插入位置，使得n 插入后新序列仍然有序。按照这种思想，依次对链表从头到尾执行一遍，就可以使无序链表变为有序链表。单向链表的直接插入排序图示：-1-3-2.-n-NULL（原链表）head 1-next 3-next 2-next n-next -1-NULL（从原链表中取第1 个节点作为只有一个节点的有序链表）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 14 页 - - - - - - - - - - head 图 11

9、-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 罢了。这一点请读者务必搞清楚，要不然就可能认为它和上面的选择排序法一样了。*/ stru

10、ct student *InsertSort(struct student *head) struct student *first; /*为原链表剩下用于直接插入排序的节点头指针*/ struct student *t; /*临时指针变量：插入节点*/ struct student *p; /*临时指针变量 */ struct student *q; /*临时指针变量 */ first = head-next; /*原链表剩下用于直接插入排序的节点链表：可根据图12 来理解。 */ head-next = NULL; /*只含有一个节点的链表的有序链表：可根据图11 来理解。 */ whil

11、e (first != NULL) /*遍历剩下无序的链表*/ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 14 页 - - - - - - - - - - /*注意：这里for 语句就是体现直接插入排序思想的地方*/ for (t=first, q=head; (q!=NULL) & (q-num num); p=q, q=q-next); /*无序节点在有序链表中找插入的位置*/ /*退出 for 循环，就是找到了插入的位置*/ /*注意：按道理来说，这句话可以放到下面注释了的那个位置

12、也应该对的，但是就是不能。原因：你若理解了上面的第3 条，就知道了。*/ first = first-next; /*无序链表中的节点离开，以便它插入到有序链表中。*/ if (q = head) /*插在第一个节点之前*/ head = t; else /*p 是 q 的前驱 */ p-next = t; t-next = q; /* 完成插入动作 */ /*first = first-next;*/ return head; /* 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 14 页

13、- - - - - - - - - - = 功能：冒泡排序(由小到大 ) 返回：指向链表表头的指针= */ /* 直接插入排序的基本思想就是对当前还未排好序的范围内的全部节点，自上而下对相邻的两个节点依次进行比较和调整，让键值（就是用它排序的字段，我们取学号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-nex

14、t 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 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 14 页 - - - - - - - - -

15、 - 图 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,原

16、来 p1-next-next （即 p2)是指向 q 的，所以p1-next=p2; 5、至此，我们完成了相邻两节点的顺序交换。6、下面的程序描述改进了一点就是记录了每次最后一次节点下沉的位置，这样我们不必每次都从头到尾的扫描，只需要扫描到记录点为止。因为后面的都已经是排好序的了。*/ struct student *BubbleSort(struct student *head) struct student *endpt; /*控制循环比较 */ struct student *p; /*临时指针变量 */ struct student *p1; struct student *p2; p

17、1 = (struct student *)malloc(LEN); p1-next = head; /*注意理解：我们增加一个节点，放在第一个节点的前面，主要是为了便于比较。因为第一个节点没有前驱，我们不能交换地址。*/ head = p1; /* 让 head 指向 p1 节点，排序完成后，我们再把p1 节点释放掉 */ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 14 页 - - - - - - - - - - for (endpt=NULL; endpt!=head; endpt=

18、p) /*结合第 6 点理解 */ for (p=p1=head; p1-next-next!=endpt; p1=p1-next) if (p1-next-num p1-next-next-num) /*如果前面的节点键值比后面节点的键值大，则交换 */ p2 = p1-next-next; /*结合第 1 点理解 */ p1-next-next = p2-next; /*结合第 2 点理解 */ p2-next = p1-next; /*结合第 3 点理解 */ p1-next = p2; /*结合第 4 点理解 */ p = p1-next-next; /*结合第 6 点理解 */ p1

19、 = head; /* 把 p1 的信息去掉 */ head = head-next; /*让 head 指向排序后的第一个节点*/ free(p1); /* 释放 p1*/ p1 = NULL; /*p1置为 NULL ，保证不产生 “ 野指针 ” ，即地址不确定的指针变量*/ return head; /* = 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 14 页 - - - - - - - - - - 功能：插入有序链表的某个节点的后面(从小到大 ) 返回：指向链表表头的指针= *

20、/ /* 有序链表插入节点示意图：-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

21、 1-next 2-next 3-next node-next n-next 图 20：node 节点插在其它节点后*/ struct student *SortInsert(struct student *head, struct student *node) struct student *p; /*p保存当前需要检查的节点的地址*/ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 14 页 - - - - - - - - - - struct student *t; /*临时指针变量

22、*/ if (head = NULL) /*处理空的有序链表*/ head = node; node-next = NULL; n += 1; /* 插入完毕，节点总数加1*/ return head; p = head; /* 有序链表不为空*/ while (p-num num & p != NULL) /*p指向的节点的学号比插入节点的学号小，并且它不等于NULL*/ t = p; /* 保存当前节点的前驱，以便后面判断后处理*/ p = p-next; /* 后移一个节点 */ if (p = head) /*刚好插入第一个节点之前*/ node-next = p; head = no

23、de; else /* 插入其它节点之后*/ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 14 页 - - - - - - - - - - t-next = node; /*把 node 节点加进去 */ node-next = p; n += 1; /* 插入完毕，节点总数加1*/ return head; /* 测试代码如下：*/ /*测试 SelectSort(): 请编译时去掉注释块*/ /* head = SelectSort(head); Print(head); */ /*

24、测试 InsertSort(): 请编译时去掉注释块*/ /* head = InsertSort(head); Print(head); */ /*测试 BubbleSort(): 请编译时去掉注释块*/ /* head = BubbleSort(head); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 14 页 - - - - - - - - - - Print(head); */ /*测试 SortInsert(): 上面创建链表，输入节点时请注意学号num 从小到大的顺序。请编译

25、时去掉注释块 */ /* stu = (struct student *)malloc(LEN); printf(nPlease input insert node - num,score: ); scanf(%ld,%f,&stu-num,&stu-score); head = SortInsert(head,stu); free(stu); stu = NULL; Print(head); */ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 14 页 - - - - - - - - - -