最近在写一个学生管理系统，还没有写完就已经遇到了很多困难，也学到了很多，本文谨记录本人对链表排序的一些理解。

冒泡排序与直接排序

  • 就冒泡排序与直接排序而言，链表与数相似，先比较两个变量的大小，再交换两个变量的内容。
  • 交换的仅是变量所存的内容，链表(数组)的每个节点(元素)的位置关系不变。

交换number1和number2后：

改变的只是变量a和b的内容（number），a和b的位置关系没有改变。

  • 比大小与数组完全一致，只需取出节点内的number进行比较，难点在于交换number。
  • 如果一个节点中只储存一个number，可以直接将number取出进行交换。
#include#include#define N 5typedef struct node{int number;struct node* next;}NODE;int main(){int i;NODE* head = (NODE*)malloc(sizeof(NODE));head->next = NULL;NODE* last = head;//尾插法创建含有5个节点的链表for (i = 0; i number);last->next = p;last = p;p->next = NULL;}//直接排序法从大到小进行排序for (NODE* p = head->next; p->next; p = p->next)for (NODE* q = p->next; q; q = q->next)if (q->number > p->number){int t = p->number;p->number = q->number;q->number = t;}//输出链表for (NODE* p = head->next; p != 0; p = p->next)printf("%d\n", p->number);}
  • 当一个节点内有很多内容时，如学生信息管理系统，一个节点包含姓名、成绩、学号等多个内容，如果把节点内的全部内容取出，然后交换，将十分麻烦。

为什么我们不直接通过结构体的赋值来进行节点的交换？因为结构体赋值会把节点的next也进行交换，会打乱节点相对位置，破坏掉整条链表。所以我们在结构体赋值之前，提前记录下所交换节点的next，既他们的位置关系，交换结束后，将他们的位置关系还原。

#include#include#define N 5typedef struct node{int number;struct node* next;}NODE;int main(){int i;NODE* head = (NODE*)malloc(sizeof(NODE));head->next = NULL;NODE* last = head;//尾插法创建含有5个节点的链表for (i = 0; i number);last->next = p;last = p;p->next = NULL;}//直接排序法从大到小进行排序for (NODE* p = head->next; p->next; p = p->next)for (NODE* q = p->next; q; q = q->next)if (q->number > p->number){//提前记录p和q的nextNODE* p_next = p->next;NODE* q_next = q->next;//整体交换p和qNODE t = *p;*p = *q;*q = t;//将p和q的位置关系还原p->next = p_next;q->next = q_next;}//输出链表for (NODE* p = head->next; p != 0; p = p->next)printf("%d\n", p->number);}

插入排序

  • 链表和数组的插入排序差异较大，本质在于两者插入新节点(元素)的方式不同，数组需要整体后移，而链表只需改变节点的next。
  • 数组仍不改变每个元素间的相对位置关系，只改变元素所包含的内容，而链表是整体搬家，改变的是节点间的位置关系。

重新排序后：

不要在意我按照什么规则进行的排序，主要突出一个乱，重点在于理解他们的位置关系发生了变化。

  • 插入排序的思路主要是，将链表分为两条，一条主链表等待被插入，一条从链表逐个插入到主链表中。
  • 具体操作需要对两条链表都进行遍历，如果从链表中的某个节点没有找到位置可以插入，需要补在主链表的末尾。
  • 所以我们需要两次嵌套的for循环进行遍历，需要一个flag记录节点是否成功插入。
#include#include#define N 5typedef struct node{int number;struct node* next;}NODE;int main(){int i;NODE* head = (NODE*)malloc(sizeof(NODE));head->next = NULL;NODE* last = head;//尾插法创建含有5个节点的链表for (i = 1; i number);last->next = p;last = p;p->next = NULL;}//插入排序法从大到小进行排序//将原链表拆分成两个链表NODE* p = head->next;NODE* q = p->next;p->next = NULL;int flag = 0;//将链表q逐一插入链表p中for (NODE* r = q->next; q; q = r){//flag为0说明q的节点还未插入链表p中flag = 0;//记录q的下一个节点r = q->next;for (NODE* last = head; p; last = p, p = p->next)if (q->number > p->number){//找到插入位置flag变为1flag = 1;q->next = p;last->next = q;break;}//我这里的起点有两个，p和last//for循环可以帮我们复原last//我们还需手动将p的位置复原p = head->next;//flag为0即该节点应补在链表p的末尾if (flag == 0){NODE* last = head;//找到链表p的最后一个节点while (last->next)last = last->next;last->next = q;q->next = NULL;}}//输出链表for (NODE* p = head->next; p != 0; p = p->next)printf("%d\n", p->number);}

这个插入排序的代码不管是可读性还是执行效率都有可优化的空间，仅作为学习记录，随着本人的后续学习，可能会有完善。