存放游标和实际数据
数据的第1个元素和末尾元素存放元数据
**第1个元素**
游标：存放（指向）备用下标，供下次使用,初始化为1
数据：链表tail标识，（尾节点下标）
**末尾元素：**
游标：存放链表第1个有效节点下标, head标识，初始化为1（根据len特殊处理）
数据：链表当前有效节点个数（长度len）#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#define MAXSIZE 10
typedef 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);
// 获取指定节点, 假设数据范围为正整数，错误我们返回-1
int get(LINKLIST, int);
// 获取并删除尾节点（出栈）, 假设数据范围取正整数，错误我们返回-1
int 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;
}
// 函数不做复杂检查，无法找到时返回-1
int 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:35
get success! val:31
get 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: 33
get 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: 32
get success! val:31
尝试删除位置: 1, (节点类型：头节点 + 尾节点), 删除成功！
pop success! val: 31
pop 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
链表为空!
C数组实现静态链表及常用操作（模拟无指针编程语言数组实现链表）
原文：https://blog.51cto.com/sndapk/2660754