#include <stdlib.h>
#include <stdio.h>
#define STATUS_OK 0
#define STATUS_FAILED -1
// 定义基本数据结构
// 1 利用大数组定义静态链表，数组由头结点，尾结点，已用链表，备用链表四部分构成
// 2 数组头结点：存放链表第一个结点的索引值
// 3 数组尾结点：存放备用链表第一个结点的索引值
#define MAXSIZE 10
typedef char ElemType;
typedef struct node {
ElemType data;
int cur;
}LNode; // 定义结点名称
typedef LNode StaticLinkedList[MAXSIZE]; // 定义链表名称
// 常见操作:
// init - 核心
// insert - 核心
// delete - 核心
// find
// traverse
// length
// 初始化操作：本质是将一个大数组赋索引值，形成空的单链表的过程
// 赋值过程分为：
// a. 头结点：备用链表的头结点索引位置，赋值为0，尾结点:链表的第一个结点的索引，赋值为0
// b. 普通结点：指向数组下个元素的索引位置，索引值+1
void init(StaticLinkedList list) {
for (int i = 0; i < MAXSIZE - 1; i++) {
list[i].cur = i + 1; // 各个结点的指针指向下一数组序号
}
list[MAXSIZE - 1].cur = 0;
}
// 申请内存空间操作：
// 1 本质是将备用链表第一个结点取出，并更新备用链表第一个结点的指向
int malloc_node(StaticLinkedList list)
{
int p = list[0].cur; // 备用链表第一个结点的索引
printf("malloc_node-1-p索引值：%d
", p);
if (list[0].cur) { // 是否非0，初始化以后，除了数组最后一个结点，都是非零。排除数组尾结点
list[0].cur = list[p].cur; // 更新备用链表头结点索引
}
return p;
}
// 释放操作：
// 1 本质是将结点添加到备用链表的过程
void free_node(StaticLinkedList list, int k) // 结点释放后，放到备用链表的第一个结点位置。头插法
{
printf("free_node-1-p索引值：%d
", list[0].cur);
list[k].cur = list[0].cur; // 原第一结点的指向赋给k结点的指向
list[0].cur = k; // 更新第一结点指向为索引值k
printf("free_node-2-p索引值：%d
", list[0].cur);
}
// 插入操作：在初始化形成的空静态链表基础上进行插入
// 步骤：
// 1 从备用链表中拿出一个结点---->自定义malloc函数
// 2 将拿出的结点赋值后，链接到链表指定位置
int insert(StaticLinkedList list, int k, ElemType x)
{
if (k < 1 || k > length(list) + 1) return;
int p = MAXSIZE - 1;
int j = malloc_node(list);
if (j) { // 排除数组尾结点
list[j].data = x;
for (int i = 1; i < k; i++) { // for循环执行1次，p指向第1个元素的索引
p = list[p].cur;
}
list[j].cur = list[p].cur;
list[p].cur = j;
return STATUS_OK;
}
return STATUS_FAILED;
}
// 删除结点：
// 1 找到该结点前一结点k-1, 将k+1结点的索引赋给k-1的向量
// 2 释放k结点
void delete_node(StaticLinkedList list, int k)
{
if (k < 1 || k > length(list)) return;
int p = MAXSIZE - 1;
for (int i = 1; i < k; i++) {
p = list[p].cur;
} // for循环结束后，p为k-1结点的index值
int q = list[p].cur; // q 为第k个结点
list[p].cur = list[q].cur; // k+1 指向赋给 k-1
free_node(list, q);
}
// 遍历链表
// 1 从第一个结点【数组尾结点所指向的结点】开始，依次遍历每个结点的数值
void traverse(StaticLinkedList list)
{
int p = list[MAXSIZE - 1].cur; // 链表第一个结点的索引
while (p > 0)
{
printf("索引值：%d, 指针向量值:%d, 数据值:%c
", p, list[p].cur, list[p].data);
p = list[p].cur;
}
}
int length(StaticLinkedList list)
{
int j = 0;
int p = list[MAXSIZE - 1].cur; // 链表第一个结点的索引
while (p > 0)
{
p = list[p].cur;
j++;
}
return j;
}
void traverseArray(StaticLinkedList list) {
for (int i = 1; i < MAXSIZE; i++) {
printf("索引值：%d, 指针向量值:%d, 数据值: %c
", i, list[i].cur, list[i].data);
}
}
int main()
{
StaticLinkedList list;
int status;
init(list);
printf("Init finished, static link list length:%d
", length(list));
insert(list, 1, 'A');
insert(list, 2, 'B');
insert(list, 3, 'C');
insert(list, 4, 'D');
insert(list, 5, 'E');
insert(list, 6, 'F');
insert(list, 7, 'G');/*
insert(list, 8, 'H');
insert(list, 9, 'I');
insert(list, 10, 'K');
insert(list, 11, 'G');*/
traverseArray(list);
/*printf("=========================分割线=========================
");
insert(list, 4, 'N');
traverse(list);
traverseArray(list);*/
printf("=========================分割线=========================
");
delete_node(list, 2);
traverseArray(list);
printf("=========================分割线=========================
");
traverse(list);
}