C数组实现静态链表及常用操作（模拟无指针编程语言数组实现链表）
16lz
2021-03-15
说明：
数据元素为结构体（复合数据类型）：
存放游标和实际数据 数据的第1个元素和末尾元素存放元数据 ** 第1个元素：** 游标：存放（指向）备用下标，供下次使用,初始化为1 数据：链表tail标识，（尾节点下标） **末尾元素：** 游标：存放链表第1个有效节点下标, head标识，初始化为1（根据len特殊处理） 数据：链表当前有效节点个数（长度len）#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <unistd.h>#define MAXSIZE 10typedef struct Node{ int data; int cur;} NODE, LINKLIST[MAXSIZE];void init(LINKLIST);bool is_full(LINKLIST);bool is_empty(LINKLIST);// 遍历所有有效元素void traverse(LINKLIST);// 遍历所有元素，便于学习void traverse_all(LINKLIST);// 追加节点（入栈）bool append(LINKLIST, int);// 获取指定位置上一个节点的下标,注意先检查再调用int get_pre(LINKLIST, int);// 删除指定节点，只返回成功失败，不返回删除成功的元素值bool delete(LINKLIST, int);// 允许前后插入bool insert(LINKLIST, int, int);/* * 清空链表, 如没特殊要求, 也可用init函数代替 * 这里调用delete函数，并从链表尾向前删除节点（只清空不改变head指向）*/ bool clear(LINKLIST);// 获取指定节点, 假设数据范围为正整数，错误我们返回-1int get(LINKLIST, int);// 获取并删除尾节点（出栈）, 假设数据范围取正整数，错误我们返回-1int pop(LINKLIST);int pop(LINKLIST L){ if (is_empty(L)) { printf("pop error! linklist is empty.\n"); return -1; } int len = L[MAXSIZE-1].data; int val = get(L, len); delete(L, len); printf("pop success! val: %d\n", val); return val;}int get(LINKLIST L, int pos){ int len = L[MAXSIZE-1].data; if (pos < 1 || pos > len) { printf("get error! pos(%d) out of range.\n", pos); return -1; } if (pos == 1) { int head = L[MAXSIZE-1].cur; int val = L[head].data; printf("get success! val:%d\n", val); return val; } int pre = get_pre(L, pos); int pos_index = L[pre].cur; int val = L[pos_index].data; printf("get success! val:%d\n", val); return val;}bool clear(LINKLIST L){ if (is_empty(L)) { printf("链表为空，无需clear操作.\n"); return true; } int len = L[MAXSIZE-1].data; for (int i=len; i > 0; i--) { if (! delete(L, i)) return false; } return true;}bool insert(LINKLIST L, int pos, int e){ int len = L[MAXSIZE-1].data; int head = L[MAXSIZE-1].cur; int tail = L[0].data; int now_index = L[0].cur; int next_index = L[now_index].cur; if (is_full(L)) { printf("插入失败，链表已满!\n"); return false; } if (pos < 1 || pos > len + 1) { printf("插入失败，无效的插入位置: %d\n", pos); return false; } int pre = get_pre(L, pos); printf("尝试插入位置 %d 值 %d", pos, e); // 插入空链表的第1个节点(条件成立时一定是pos=1) if (is_empty(L)) { printf(", (节点类型: 空链表第1个节点)"); NODE New = {e, 0}; L[now_index] = New; L[0].cur = next_index; L[0].data = now_index; ++L[MAXSIZE-1].data; L[MAXSIZE-1].cur = now_index; } // 插入新头节点 else if (pos == 1) { printf(", (节点类型: 新头节点)"); NODE New = {e, head}; L[now_index] = New; // head 指向新头节点 L[MAXSIZE-1].cur = now_index; // 备用节点指向 L[0].cur = next_index; ++L[MAXSIZE-1].data; } // 插入新尾节点 else if (pos == len + 1){ printf(", (节点类型: 新尾节点)"); NODE New = {e, 0}; L[now_index] = New; // 上一个节点（前尾节点）由原来的0指向新的tail节点 L[pre].cur = now_index; L[0].cur = next_index; // 更新tail标识 L[0].data = now_index; ++L[MAXSIZE-1].data; } //插入中间节点 else { printf(", (节点类型: 中间节点)"); int this_next = L[pre].cur; // 连接后继节点 NODE New = {e, this_next}; L[now_index] = New; // 连接前躯节点 L[pre].cur = now_index; L[0].cur = next_index; ++L[MAXSIZE-1].data; } putchar('\n'); return true;}bool delete(LINKLIST L, int pos){ /*删除任意节点共用操作： * len减1 * 回收空间 *删除不同类型节点需要做的额外操作: * pos == 1 的情况：头节点非尾节点，或头节点同时为尾节点 * 无需再查找删除位置的前躯节点下标 * 更新链表head, tail标识 * pos > 1的情况：尾节点, 或中间节点 * 删除尾节点：pos == len * 查找前躯节点下标 * 前躯节点的游标改为0 * 更新链表tail标识为前躯节点 * 删除中间节点： * 查找前躯节点下标 * 连接前躯节点及后继节点 * */ printf("尝试删除位置: %d, ", pos); if (is_empty(L)) { printf("删除失败, 链表为空!\n"); return false; } int head = L[MAXSIZE-1].cur; int tail = L[0].data; if (pos < 1 || pos > MAXSIZE-2) { printf("删除失败, 位置超出范围\n"); return false; } else if (pos == 1) { int new_head = L[head].cur; // 被删除节点数据置0 L[head].data = 0; // 判断头节点是否同时为尾节点 if (new_head == 0) { printf("(节点类型：头节点 + 尾节点)"); // tail指向0(head不变，下次追加元素从这个开始追加) L[0].data = 0; } else { printf("(节点类型：头节点)"); L[MAXSIZE-1].cur = new_head; } // 回收空间 L[head].cur = L[0].cur; L[0].cur = head; } else { int pre = get_pre(L, pos); // 删除的位置等于长度则为尾节点 if (pos == L[MAXSIZE-1].data) { // 被删除节点数据置0 L[tail].data = 0; printf("(节点类型：尾节点)"); // 更新tail指向 L[0].data = pre; // 上一个节点变为尾节点，更新游标 L[pre].cur = 0; // 回收空间 L[tail].cur = L[0].cur; L[0].cur = tail; } else { printf("(节点类型：中间节点)"); // 连接前躯和后继 int now_index = L[pre].cur; L[pre].cur = L[now_index].cur; // 被删除节点数据置0 L[now_index].data = 0; // 回收空间 L[now_index].cur = L[0].cur; L[0].cur = now_index; } } --L[MAXSIZE-1].data; printf(", 删除成功！\n"); return true;}// 函数不做复杂检查，无法找到时返回-1int get_pre(LINKLIST L, int pos){ if (pos == 1) return 0; int p = L[MAXSIZE-1].cur; int i = 1; while (L[p].cur && i < pos-1) { p = L[p].cur; ++i; } return p;}bool append(LINKLIST L, int e){ printf("追加元素:%d\n", e); if (is_full(L)) { printf("追加失败，链表已满!\n"); return false; } NODE New = {e, 0}; //追加的尾元素固定指向0 int tail_index = L[0].data; //获取链表尾元素的下标 int now_index = L[0].cur; //本次追加元素使用的下标 int next_index = L[now_index].cur; //保存备用下标的下一个下标作为新备用下标 L[now_index] = New; ++L[MAXSIZE-1].data; //len(当前有效元素)加1 L[0].data = now_index; //更新链表tail标识 L[0].cur = next_index; //更新链表备用下标 // 非init后首次插入，需要tail元素连接新元素操作 if (tail_index != 0) L[tail_index].cur = now_index; return true;}bool is_empty(LINKLIST L){ if (L[MAXSIZE-1].data == 0) return true; return false;}bool is_full(LINKLIST L){ if (L[MAXSIZE-1].data == MAXSIZE-2) return true; return false;}void traverse(LINKLIST L){ if (is_empty(L)) { printf("链表为空!\n"); return; } printf("链表元素:"); // 保存链表的头元素下标(并不总是1) int head = L[MAXSIZE-1].cur; // 当head == 0 代表有效节点遍历结束 while (head != 0) { printf("%d ", L[head].data); head = L[head].cur; } putchar('\n');}void traverse_all(LINKLIST L){ printf("--------------current linklist state-----------------\n"); printf("%10s", "Cursor: "); for (int i=0; i<MAXSIZE;i++) { printf("%4d ", L[i].cur); } putchar('\n'); printf("%10s", "Data: "); for (int i=0; i<MAXSIZE;i++) { printf("%4d ", L[i].data); } putchar('\n'); printf("%10s", "index: "); for (int i=0; i<MAXSIZE;i++) { printf("%4d ", i); } putchar('\n');}void init(LINKLIST L){ for (int i=0; i<MAXSIZE-1; i++) { L[i].cur = i + 1; L[i].data = 0; } /* * 数组的尾元素的游标初始化指向第1个有数据的元素下标 * 虽然此时1并不是是有效元素，但是append追加元素不用再加判断为空修改head变量了 */ L[MAXSIZE-1].cur = 1; //head L[MAXSIZE-1].data = 0; //len}int main(void){ LINKLIST L; init(L); // test append traverse(L); traverse_all(L); append(L, 11); traverse_all(L); append(L, 12); traverse_all(L); append(L, 13); append(L, 14); append(L, 15); append(L, 16); append(L, 17); append(L, 18); traverse_all(L); append(L, 19); traverse_all(L); traverse(L); // test delete delete(L, 9); delete(L, 0); delete(L, 1); traverse_all(L); delete(L, 7); traverse_all(L); delete(L, 4); traverse_all(L); delete(L, 2); traverse_all(L); delete(L, 2); traverse_all(L); delete(L, 3); traverse_all(L); delete(L, 1); traverse_all(L); delete(L, 1); traverse_all(L); delete(L, 1); traverse(L); // test append append(L, 21); traverse_all(L); append(L, 22); traverse_all(L); append(L, 23); append(L, 24); append(L, 25); append(L, 26); append(L, 27); append(L, 28); traverse_all(L); append(L, 29); traverse_all(L); traverse(L); // test clear clear(L); traverse_all(L); traverse(L); clear(L); // test insert insert(L, 0, 100); insert(L, 2, 101); insert(L, 1, 32); traverse_all(L); traverse(L); insert(L, 1, 31); traverse_all(L); traverse(L); insert(L, 3, 33); traverse_all(L); traverse(L); insert(L, 4, 34); traverse_all(L); traverse(L); insert(L, 5, 35); traverse_all(L); traverse(L); insert(L, 5, 355); traverse_all(L); traverse(L); insert(L, 4, 344); traverse_all(L); traverse(L); insert(L, 3, 333); traverse_all(L); traverse(L); insert(L, 2, 322); traverse_all(L); traverse(L); // test pop get(L, 9); get(L, 0); get(L, 8); get(L, 1); // test pop pop(L); traverse_all(L); traverse(L); pop(L); traverse_all(L); traverse(L); pop(L); traverse_all(L); traverse(L); pop(L); traverse_all(L); traverse(L); pop(L); pop(L); traverse_all(L); traverse(L); pop(L); pop(L); pop(L); traverse_all(L); traverse(L); return 0;}output
链表为空!--------------current linklist state----------------- Cursor: 1 2 3 4 5 6 7 8 9 1 Data: 0 0 0 0 0 0 0 0 0 0 index: 0 1 2 3 4 5 6 7 8 9 追加元素:11--------------current linklist state----------------- Cursor: 2 0 3 4 5 6 7 8 9 1 Data: 1 11 0 0 0 0 0 0 0 1 index: 0 1 2 3 4 5 6 7 8 9 追加元素:12--------------current linklist state----------------- Cursor: 3 2 0 4 5 6 7 8 9 1 Data: 2 11 12 0 0 0 0 0 0 2 index: 0 1 2 3 4 5 6 7 8 9 追加元素:13追加元素:14追加元素:15追加元素:16追加元素:17追加元素:18--------------current linklist state----------------- Cursor: 9 2 3 4 5 6 7 8 0 1 Data: 8 11 12 13 14 15 16 17 18 8 index: 0 1 2 3 4 5 6 7 8 9 追加元素:19追加失败，链表已满!--------------current linklist state----------------- Cursor: 9 2 3 4 5 6 7 8 0 1 Data: 8 11 12 13 14 15 16 17 18 8 index: 0 1 2 3 4 5 6 7 8 9 链表元素:11 12 13 14 15 16 17 18 尝试删除位置: 9, 删除失败, 位置超出范围尝试删除位置: 0, 删除失败, 位置超出范围尝试删除位置: 1, (节点类型：头节点), 删除成功！--------------current linklist state----------------- Cursor: 1 9 3 4 5 6 7 8 0 2 Data: 8 0 12 13 14 15 16 17 18 7 index: 0 1 2 3 4 5 6 7 8 9 尝试删除位置: 7, (节点类型：尾节点), 删除成功！--------------current linklist state----------------- Cursor: 8 9 3 4 5 6 7 0 1 2 Data: 7 0 12 13 14 15 16 17 0 6 index: 0 1 2 3 4 5 6 7 8 9 尝试删除位置: 4, (节点类型：中间节点), 删除成功！--------------current linklist state----------------- Cursor: 5 9 3 4 6 8 7 0 1 2 Data: 7 0 12 13 14 0 16 17 0 5 index: 0 1 2 3 4 5 6 7 8 9 尝试删除位置: 2, (节点类型：中间节点), 删除成功！--------------current linklist state----------------- Cursor: 3 9 4 5 6 8 7 0 1 2 Data: 7 0 12 0 14 0 16 17 0 4 index: 0 1 2 3 4 5 6 7 8 9 尝试删除位置: 2, (节点类型：中间节点), 删除成功！--------------current linklist state----------------- Cursor: 4 9 6 5 3 8 7 0 1 2 Data: 7 0 12 0 0 0 16 17 0 3 index: 0 1 2 3 4 5 6 7 8 9 尝试删除位置: 3, (节点类型：尾节点), 删除成功！--------------current linklist state----------------- Cursor: 7 9 6 5 3 8 0 4 1 2 Data: 6 0 12 0 0 0 16 0 0 2 index: 0 1 2 3 4 5 6 7 8 9 尝试删除位置: 1, (节点类型：头节点), 删除成功！--------------current linklist state----------------- Cursor: 2 9 7 5 3 8 0 4 1 6 Data: 6 0 0 0 0 0 16 0 0 1 index: 0 1 2 3 4 5 6 7 8 9 尝试删除位置: 1, (节点类型：头节点 + 尾节点), 删除成功！--------------current linklist state----------------- Cursor: 6 9 7 5 3 8 2 4 1 6 Data: 0 0 0 0 0 0 0 0 0 0 index: 0 1 2 3 4 5 6 7 8 9 尝试删除位置: 1, 删除失败, 链表为空!链表为空!追加元素:21--------------current linklist state----------------- Cursor: 2 9 7 5 3 8 0 4 1 6 Data: 6 0 0 0 0 0 21 0 0 1 index: 0 1 2 3 4 5 6 7 8 9 追加元素:22--------------current linklist state----------------- Cursor: 7 9 0 5 3 8 2 4 1 6 Data: 2 0 22 0 0 0 21 0 0 2 index: 0 1 2 3 4 5 6 7 8 9 追加元素:23追加元素:24追加元素:25追加元素:26追加元素:27追加元素:28--------------current linklist state----------------- Cursor: 9 0 7 5 3 8 2 4 1 6 Data: 1 28 22 25 24 26 21 23 27 8 index: 0 1 2 3 4 5 6 7 8 9 追加元素:29追加失败，链表已满!--------------current linklist state----------------- Cursor: 9 0 7 5 3 8 2 4 1 6 Data: 1 28 22 25 24 26 21 23 27 8 index: 0 1 2 3 4 5 6 7 8 9 链表元素:21 22 23 24 25 26 27 28 尝试删除位置: 8, (节点类型：尾节点), 删除成功！尝试删除位置: 7, (节点类型：尾节点), 删除成功！尝试删除位置: 6, (节点类型：尾节点), 删除成功！尝试删除位置: 5, (节点类型：尾节点), 删除成功！尝试删除位置: 4, (节点类型：尾节点), 删除成功！尝试删除位置: 3, (节点类型：尾节点), 删除成功！尝试删除位置: 2, (节点类型：尾节点), 删除成功！尝试删除位置: 1, (节点类型：头节点 + 尾节点), 删除成功！--------------current linklist state----------------- Cursor: 6 9 7 5 3 8 2 4 1 6 Data: 0 0 0 0 0 0 0 0 0 0 index: 0 1 2 3 4 5 6 7 8 9 链表为空!链表为空，无需clear操作.插入失败，无效的插入位置: 0插入失败，无效的插入位置: 2尝试插入位置 1 值 32, (节点类型: 空链表第1个节点)--------------current linklist state----------------- Cursor: 2 9 7 5 3 8 0 4 1 6 Data: 6 0 0 0 0 0 32 0 0 1 index: 0 1 2 3 4 5 6 7 8 9 链表元素:32 尝试插入位置 1 值 31, (节点类型: 新头节点)--------------current linklist state----------------- Cursor: 7 9 6 5 3 8 0 4 1 2 Data: 6 0 31 0 0 0 32 0 0 2 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 尝试插入位置 3 值 33, (节点类型: 新尾节点)--------------current linklist state----------------- Cursor: 4 9 6 5 3 8 7 0 1 2 Data: 7 0 31 0 0 0 32 33 0 3 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 33 尝试插入位置 4 值 34, (节点类型: 新尾节点)--------------current linklist state----------------- Cursor: 3 9 6 5 0 8 7 4 1 2 Data: 4 0 31 0 34 0 32 33 0 4 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 33 34 尝试插入位置 5 值 35, (节点类型: 新尾节点)--------------current linklist state----------------- Cursor: 5 9 6 0 3 8 7 4 1 2 Data: 3 0 31 35 34 0 32 33 0 5 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 33 34 35 尝试插入位置 5 值 355, (节点类型: 中间节点)--------------current linklist state----------------- Cursor: 8 9 6 0 5 3 7 4 1 2 Data: 3 0 31 35 34 355 32 33 0 6 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 33 34 355 35 尝试插入位置 4 值 344, (节点类型: 中间节点)--------------current linklist state----------------- Cursor: 1 9 6 0 5 3 7 8 4 2 Data: 3 0 31 35 34 355 32 33 344 7 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 33 344 34 355 35 尝试插入位置 3 值 333, (节点类型: 中间节点)--------------current linklist state----------------- Cursor: 9 7 6 0 5 3 1 8 4 2 Data: 3 333 31 35 34 355 32 33 344 8 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 333 33 344 34 355 35 插入失败，链表已满!--------------current linklist state----------------- Cursor: 9 7 6 0 5 3 1 8 4 2 Data: 3 333 31 35 34 355 32 33 344 8 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 333 33 344 34 355 35 get error! pos(9) out of range.get error! pos(0) out of range.get success! val:35get success! val:31get success! val:35尝试删除位置: 8, (节点类型：尾节点), 删除成功！pop success! val: 35--------------current linklist state----------------- Cursor: 3 7 6 9 5 0 1 8 4 2 Data: 5 333 31 0 34 355 32 33 344 7 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 333 33 344 34 355 get success! val:355尝试删除位置: 7, (节点类型：尾节点), 删除成功！pop success! val: 355--------------current linklist state----------------- Cursor: 5 7 6 9 0 3 1 8 4 2 Data: 4 333 31 0 34 0 32 33 344 6 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 333 33 344 34 get success! val:34尝试删除位置: 6, (节点类型：尾节点), 删除成功！pop success! val: 34--------------current linklist state----------------- Cursor: 4 7 6 9 5 3 1 8 0 2 Data: 8 333 31 0 0 0 32 33 344 5 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 333 33 344 get success! val:344尝试删除位置: 5, (节点类型：尾节点), 删除成功！pop success! val: 344--------------current linklist state----------------- Cursor: 8 7 6 9 5 3 1 0 4 2 Data: 7 333 31 0 0 0 32 33 0 4 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 333 33 get success! val:33尝试删除位置: 4, (节点类型：尾节点), 删除成功！pop success! val: 33get success! val:333尝试删除位置: 3, (节点类型：尾节点), 删除成功！pop success! val: 333--------------current linklist state----------------- Cursor: 1 7 6 9 5 3 0 8 4 2 Data: 6 0 31 0 0 0 32 0 0 2 index: 0 1 2 3 4 5 6 7 8 9 链表元素:31 32 get success! val:32尝试删除位置: 2, (节点类型：尾节点), 删除成功！pop success! val: 32get success! val:31尝试删除位置: 1, (节点类型：头节点 + 尾节点), 删除成功！pop success! val: 31pop error! linklist is empty.--------------current linklist state----------------- Cursor: 2 7 6 9 5 3 1 8 4 2 Data: 0 0 0 0 0 0 0 0 0 0 index: 0 1 2 3 4 5 6 7 8 9 链表为空!好知识，才能预见未来
赞赏
0人进行了赞赏支持
更多相关文章
- Think PHP框架清除运行时缓存（php文件目录递归删除）
- 在Ubuntu系统上使用kubeadm部署v1.20版的Kubernetes集群
- 用户行为分析模型实践（一）—— 路径分析模型
- 大数据成神之路-Java高级特性增强(ConcurrentSkipListMap)
- web前端技术分享之：Canvas框架之Konva.js --元素节点的事件
- 面试官再问你优先级队列，请把这篇文章丢给他
- 删除链表中重复的节点
- 2021-03-14：手写代码：单链表冒泡排序。
- 文件夹管理： mv cp rm touch mkdir LS 创建文件夹 移动 删除