摘要
本文介绍了C语言如何用结构体来实现单链表,以及单链表的基础操作。简洁起见,比较简单的操作都放在最后的完整代码里(说明在注释里),不再赘述。
有序插入
图解:
- target的值为2
- 先找到合适的节点,此时prev=1,current=3
- 再改变next的值,将节点2指向3,节点1指向2。
Node *orderInsert(Node *head, Node *target){ Node *current = head; Node *prev = NULL; target->next = NULL; // 清空target的值,防止闭环、混入杂链等情况 // head为空值的情况 if (head == NULL) return target; while (current != NULL) { // 比较要插入的单位,若比当前节点大则继续寻找,直到找到比目标大的节点 if (target->data <= current->data) { target->next = current; // target应放在头部的情况 if (prev == NULL) head = target; else prev->next = target; return head; } prev = current; current = current->next; } prev->next = target; target->next = NULL; return head;}
逆转
请注意,完成这个操作必须用至少3个临时变量,因为改变节点方向需要"瞻前",进入下一个状态要"顾后"。
这里的next在循环的最开始赋值是取巧的,如果你把这行放在 current = next
的后面,current为NULL时执行 next = current->next
的会出错,需要另外增加一条if判断current是否为NULL。
Node *reverse(Node *head){ Node *prev = NULL; Node *current = head; Node *next = NULL; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } return prev;}
冒泡排序
这里不再赘述冒泡排序的原理,只专注于冒泡排序交换的过程。
提醒一点:在交换时不要通过交换data来交换,这么做虽然能运行、代码看上去也更简洁,但从算法上来讲开销较大,抹除了链表本身的优势,在data较大的情况下尤为显著。
这一部分比较复杂,希望下面的文字和三张图可以讲清楚我的思路。
链表的交换涉及到了4个节点和用来操作他们的两个指针P和C,我们看看一个循环要做什么,显然将2和3交换了。那P和C呢,你会发现P标记到了原来顺序的第三个节点(即2),而C标记的还是3!
下面一张图是实现:
prev = prev->next = current->next;
这行代码既完成了next1的赋值,又完成了P对第三个节点的标记。current->next = prev->next;
完成了next2的赋值。prev->next = current;
完成了next3的赋值。
至此3个next的赋值,和P对第三个点的标记的操作就完成了。
下图是对特殊情况(第一次循环)的补充,只有第一个操作有差别,就是把Header更新到第二个节点和P的标记。
Node *boubleSort(Node *head){ Node *prev = NULL; Node *current = head; Node *next = current->next; int flag = 1; // 检测当前轮数是否发生交换,若未发生说明排序成功。 while (flag) { flag = 0; while (current->next != NULL) { if (current->data > current->next->data) { flag = 1; if (prev == NULL) prev = head = current->next; else prev = prev->next = current->next; current->next = prev->next; prev->next = current; } else{ prev = current; current = current->next; } } prev = NULL; current = head; } return head;}
插入排序
插入排序很好理解,和打扑克牌时的理牌过程相同,取一个节点插入合适的位置即可。插入排序非常契合链表的特点,插入对于链表来说开销非常小。
这个算法需要前面的有序插入,如果有序插入已经实现了,那插入排序将非常简单。
Node *insertSort(Node *head){ Node *current = head; Node *next = current->next; head = NULL; int value; while (current != NULL) { next = current->next; // print(head); head = orderInsert(head, current); current = next; } return head;}
图解:
完整代码
#include #include // 定义节点typedef struct Node{ int data; struct Node *next;} Node; // 创建链表Node *create(){ Node *head = NULL, *tail; int value; head = tail = NULL; // 表示scanf正确接受了一个变量,因此输入非数字时,scanf会停止读取。 while (scanf("%d", &value) == 1) { if (tail == NULL) head = tail = (Node *)malloc(sizeof(Node)); else tail = tail->next = (Node *)malloc(sizeof(Node)); tail->data = value; tail->next = NULL; } return head;} // 输出链表void print(Node *head){ Node *current = head; while (current != NULL) { printf("%d", current->data); current = current->next; if (current == NULL) printf("\n"); else printf(" -> "); }} // 释放void release(Node *head){ Node *current = head; Node *next = NULL; while (current != NULL) { next = current->next; free(current); current = next; }} // 尾插void append(Node *head, int value){ Node *tail = head; while (tail->next != NULL) tail = tail->next; tail->next = (Node *)malloc(sizeof(Node)); tail->next->data = value; tail->next->next = NULL;} // 定位插入void insert(Node *head, int value, int pos){ Node *current = head; Node *prev = NULL; while (pos-- && current != NULL) { prev = current; current = current->next; } prev->next = (Node *)malloc(sizeof(Node)); prev->next->data = value; prev->next->next = current;} // 删除void delete(Node *head, int pos){ Node *prev = NULL; Node *current = head; while (current->next != NULL && pos--) { prev = current; current = current->next; } prev->next = current->next; free(current);} Node *reverse(Node *head){ Node *prev = NULL; Node *current = head; Node *next = NULL; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } return prev;} Node *boubleSort(Node *head){ Node *prev = NULL; Node *current = head; Node *next = current->next; int flag = 1; while (flag) { flag = 0; while (next != NULL) { if (current->data > next->data) { flag = 1; if (prev == NULL) head = next; else prev->next = next; current->next = next->next; next->next = current; } prev = current; current = next; next = current->next; } prev = NULL; current = head; next = current->next; } return head;} Node *orderInsert(Node *head, Node *target){ Node *current = head; Node *prev = NULL; target->next = NULL; if (head == NULL) return target; while (current != NULL) { if (target->data <= current->data) { target->next = current; if (prev == NULL) head = target; else prev->next = target; return head; } prev = current; current = current->next; } prev->next = target; target->next = NULL; return head;} Node *insertSort(Node *head){ Node *current = head; Node *next = current->next; head = NULL; int value; while (current != NULL) { next = current->next; // print(head); head = orderInsert(head, current); current = next; } return head;} int main(){ Node *head = create(); printf("Original List: "); print(head); append(head, 2); printf("List after appending: "); print(head); insert(head, 7, 7); printf("List after inserting: "); print(head); delete (head, 2); printf("List after deleting: "); print(head); head = reverse(head); printf("Reversed List: "); print(head); head = insertSort(head); printf("Insert sorted List: "); print(head); head = boubleSort(head); printf("Bouble sorted List: "); print(head); release(head); return 0;}
回显:
112 34 214 211 232 32 # Original List: 112 -> 34 -> 214 -> 211 -> 232 -> 32 List after appending: 112 -> 34 -> 214 -> 211 -> 232 -> 32 -> 2 List after inserting: 112 -> 34 -> 214 -> 211 -> 232 -> 32 -> 7 -> 2 List after deleting: 112 -> 34 -> 211 -> 232 -> 32 -> 7 -> 2 Reversed List: 2 -> 7 -> 32 -> 232 -> 211 -> 34 -> 112 Insert sorted List: 2 -> 7 -> 32 -> 34 -> 112 -> 211 -> 232 Bouble sorted List: 2 -> 7 -> 32 -> 34 -> 112 -> 211 -> 232
Comments NOTHING