数据结构(笔记）——单向循环链表

1.单向循环链表的定义单向链表每个节点只有一个指针域指向下一个节点。循环链表链表的最后一个节点指针不是 NULL而是指向头节点。所以 单向循环链表 就是链表中的最后一个节点的 next 指针指向头节点而不是空指针从而形成一个 环状结构。2.特点特点描述存储结构用指针将节点串联起来访问方式只能沿着next方向单向访问尾节点指针list-last-next指向头节点没有空指针结尾任意节点开始遍历都能回到起点节点插入删除不需要移动其他节点只改指针即可判空条件head NULL3.优缺点优点可以从任意一个节点开始遍历形成一个闭环结构。在循环处理中比较方便例如约瑟夫问题。插入、删除操作不需要整体移动元素。缺点只能单向遍历不能反向。查找效率低必须从头开始。代码实现比顺序表复杂。4.实现函数申请一个节点Node* _buynode(ElemType x) { Node* s (Node*)malloc(sizeof(Node)); assert(s ! NULL); s-data x; s-next NULL; return s; }目的申请一个新节点存放数据 x。步骤malloc 分配一块 Node 结构体大小的内存。assert(s ! NULL) 保证申请成功。把传入的数据 x 存到 data 域。next 指针先置空后续再连接。返回这个新节点指针。初始化void InitSCList(List* list) { Node* s (Node*)malloc(sizeof(Node)); assert(s ! NULL); list-first list-last s; list-last-next list-first; list-size 0; }目的初始化一个空的单向循环链表。步骤申请一个头结点 s。头和尾都指向这个结点说明链表里还没有有效数据。尾结点的 next 指向头结点形成 环。size0表示空表。尾插void push_back(List* list, ElemType x) { Node* s _buynode(x); list-last-next s; list-last s; list-last-next list-first; list-size; }目的尾插法在链表最后添加一个元素。步骤新建节点 s存放 x。旧尾节点 last-next s把新节点接在后面。更新尾指针 last s。尾节点 next 指向头节点保持循环。长度 size。头插void push_front(List* list, ElemType x) { Node* s _buynode(x); s-next list-first-next; list-first-next s; if (list-first list-last) { list-last s; } list-size; }目的头插法把新元素插到表头头结点之后。步骤新建节点 s。让 s-next 指向原来的第一个有效节点。让头结点指向 s完成插入。如果插入前链表是空的firstlast那么新节点也要成为尾节点。长度 size。显示元素void show_list(List* list) { Node* p list-first-next; while (p ! list-first) { printf(%d--, p-data); p p-next; } printf(Nul.\n); }目的遍历并打印链表数据。步骤从第一个有效节点开始first-next。一直循环直到回到头结点 first。每次输出一个节点数据。输出结束后打印 Nul.。尾删void pop_back(List* list) { if (list-size 0) return; Node* p list-first; while (p-next ! list-last) { p p-next; } free(list-last); list-last p; list-last-next list-first; list-size--; }目的删除最后一个节点。步骤如果空表直接返回。找到尾节点的前一个节点 p。释放原尾节点内存。更新 last p。last-next first 保持循环。长度 --。头删void pop_front(List* list) { if (list-size 0) return; Node* p list-first-next; list-first-next p-next; free(p); if (list-size 1) { list-last list-first; } list-size--; }目的删除第一个有效节点。步骤如果空表直接返回。取出第一个有效节点 p first-next。头结点绕过 p指向 p-next。释放 p。如果删除后变空表则 lastfirst。长度 --。插入值void insert_val(List* list, ElemType x) { Node* p list-first; while (p-next ! list-last p-next-data x) { p p-next; } if (p-next list-last p-next-data x) { push_back(list, x); } else { Node* s _buynode(x); s-next p-next; p-next s; list-size; } }目的按升序插入新元素 x。步骤从头结点开始找到第一个比 x 大的节点前驱 p。如果到尾节点还比 x 小 → 直接尾插。否则在 p 和 p-next 之间插入新节点。长度 。查找Node* find(List* list, ElemType key) { if (list-size 0) return NULL; Node* p list-first-next; while (p ! list-first p-data ! key) p p-next; if (p list-first) return NULL; return p; }目的查找值为 key 的节点。步骤空表直接返回 NULL。从第一个节点开始查找直到回到头结点或找到 key。如果回到头结点还没找到 → 返回 NULL。否则返回找到的节点。长度int length(List* list) { return list-size; }目的返回链表长度。步骤直接返回 size。删除值void delete_val(List* list, ElemType key) { if (list-size 0) return; Node* p find(list, key); if (p NULL) { printf(要删除的数据不存在.\n); return; } if (p list-last) { pop_back(list); } else { Node* q p-next; p-data q-data; p-next q-next; free(q); list-size--; } }目的删除值为 key 的节点。步骤如果空表 → 返回。调用 find 查找目标节点 p。如果没找到 → 提示不存在。如果要删的是尾节点 → 调用 pop_back。否则用 复制后继节点数据 的方法删除O(1)。把 q p-next 的数据拷贝到 p。删除 q 节点相当于“跳过了它”。size--。排序void sort(List* list) { if (list-size 0 || list-size 1) return; Node* s list-first-next; Node* q s-next; list-last-next NULL; list-last s; list-last-next list-first; while (q ! NULL) { s q; q q-next; Node* p list-first; while (p-next ! list-last p-next-data s-data) { p p-next; } if (p-next list-last p-next-data s-data) { s-next list-last-next; list-last-next s; list-last s; } else { s-next p-next; p-next s; } } }目的对链表进行升序排序插入排序。步骤特殊情况0 或 1 个节点不用排。先把第一个节点 s 当作有序链表后面节点逐个插入。遍历剩余节点 q把每个节点 s 插入到合适位置。插入方法找到第一个比 s-data 大的节点之前。如果都小于 → 插到尾部。逆序void resver(List* list) { if (list-size 0 || list-size 1) return; Node* p list-first-next; Node* q p-next; list-last-next NULL; list-last p; list-last-next list-first; while (q ! NULL) { p q; q q-next; p-next list-first-next; list-first-next p; } }目的反转链表头插法逆置。步骤空表/一个元素 → 不处理。p 指第一个节点q 指第二个节点。暂时断开循环last-nextNULL。把第一个节点设为新尾节点。从第二个节点开始把每个节点插到头结点后面头插法。直到所有节点反转完成。清除void clear(List* list) { Node* p list-first-next; while (p ! list-first) { list-first-next p-next; free(p); p list-first-next; } list-last list-first; list-last-next list-first; list-size 0; }目的清空链表但保留头结点。步骤从第一个有效节点开始依次删除节点。头结点指向下一个未删除节点。最后 lastfirstsize0。销毁void destroy(List* list) { clear(list); free(list-first); list-first list-last NULL; }目的销毁整个链表释放所有内存包括头结点。步骤调用 clear 清空所有有效节点。释放头结点。把指针 first 和 last 置空避免野指针。