静态链表的学习笔记

写在前面———

承接上一回，本次我学习的是一种在生活工作中罕见的链表数据类型——静态链表。这种链表看似比较不实用，但是对于我们理解好链表的本质有很大的帮助。首先为了与之前的学习衔接，先做一个链表的“报菜名”

单链表
 轻松的到达下一个节点,艰难的回到前一个结点；轻松的单向遍历，困难(基本不可能）双向遍历

双链表
 1.操作稍复杂

  2.占用内存空间更大一些.

  3.轻松从头遍历到尾, 轻松从尾遍历到头
————————————-引入一个新的概念————————-

静态链表

1.用数组来表示链表,用数组元素的下标来模拟链表的指针

2.静态储存分配(利用数组来定义的链表，因而叫做静态链表)

e.g 这个概念看起来比较唬人，但本质上其实很好理解,如果把内存看作一个巨大的数组, 那么递归定义的链表和静态链表就相差无几了。这么说感觉还是很抽象呀，那举个例子吧，首先我们都已经知道(我默认的，哈哈哈)，使用静态链表存储数据，需要预先申请足够大的一整块内存空间，也就是说，静态链表存储数据元素的个数从其创建的那一刻就已经确定，后期无法更改。比如，如果创建静态链表时只申请存储 10 个数据元素的空间，那么在使用静态链表时，数据的存储个数就不能超过 10 个，否则程序就会发生错误。

3.静态链表是在固定大小的存储空间内随机存储各个数据元素，需要使用另一条链表（姑且称为”备用表”吧）来记录空间存储空间的位置，以便后期分配给新添加元素使用。意味着使用静态链表存储数据时，你需要通过操控两条链表，一条是存储数据，另一条是记录空闲空间的位置。

感觉废话有点多了呀，那就上代码吧！

(复刻闵版）

#include #include #define DEFAULT_SIZE 5typedef struct StaticLinkedNode{char data;int next;} *NodePtr;//构建静态链表数据类型 typedef struct StaticLinkedList{NodePtr nodes;int* used;} *ListPtr;//将表初始化 ListPtr initLinkedList(){// The pointer to the whole list space.ListPtr tempPtr = (ListPtr)malloc(sizeof(StaticLinkedList));// Allocate total space.tempPtr->nodes = (NodePtr)malloc(sizeof(struct StaticLinkedNode) * DEFAULT_SIZE);tempPtr->used = (int*)malloc(sizeof(int) * DEFAULT_SIZE);// The first node is the header.tempPtr->nodes[0].data = '\0';tempPtr->nodes[0].next = -1;// Only the first node is used.tempPtr->used[0] = 1;for (int i = 1; i used[i] = 0;}return tempPtr;}//printf函数的定义 void printList(ListPtr paraListPtr){int p = 0;while (p != -1) {printf("%c", paraListPtr->nodes[p].data);p = paraListPtr->nodes[p].next;}printf("\r\n");}//插入函数的实现 void insertElement(ListPtr paraListPtr, char paraChar, int paraPosition){int p, q, i;// Step 1. Search to the position.p = 0;for (i = 0; i nodes[p].next;if (p == -1) {printf("The position %d is beyond the scope of the list.\r\n", paraPosition);return;}} // Step 2. Construct a new node.for (i = 1; i used[i] == 0){// This is identical to malloc.printf("Space at %d allocated.\r\n", i);paraListPtr->used[i] = 1;q = i;break;}}if (i == DEFAULT_SIZE){printf("No space.\r\n");return;}paraListPtr->nodes[q].data = paraChar;// Step 3. Now link.printf("linking\r\n");paraListPtr->nodes[q].next = paraListPtr->nodes[p].next;paraListPtr->nodes[p].next = q;}//删除函数的定义 void deleteElement(ListPtr paraListPtr, char paraChar){int p, q;p = 0;while ((paraListPtr->nodes[p].next != -1) && (paraListPtr->nodes[paraListPtr->nodes[p].next].data != paraChar)){p = paraListPtr->nodes[p].next;}if (paraListPtr->nodes[p].next == -1) {printf("Cannot delete %c\r\n", paraChar);return;}q = paraListPtr->nodes[p].next;paraListPtr->nodes[p].next = paraListPtr->nodes[paraListPtr->nodes[p].next].next;// This statement is identical to free(q)paraListPtr->used[q] = 0;}//测试样例 void appendInsertDeleteTest(){// Step 1. Initialize an empty list.ListPtr tempList = initLinkedList();printList(tempList);// Step 2. Add some characters.insertElement(tempList, 'H', 0);insertElement(tempList, 'e', 1);insertElement(tempList, 'l', 2);insertElement(tempList, 'l', 3);insertElement(tempList, 'o', 4);printList(tempList);// Step 3. Delete some characters (the first occurrence).printf("Deleting 'e'.\r\n");deleteElement(tempList, 'e');printf("Deleting 'a'.\r\n");deleteElement(tempList, 'a');printf("Deleting 'o'.\r\n");deleteElement(tempList, 'o');printList(tempList);insertElement(tempList, 'x', 1);printList(tempList);}//这步就不多说了，懂得都懂 int main(){appendInsertDeleteTest();return 0;}

几点说明、感想：

1.还是老问题了，估计我的dev指定有点大病，主函数调用非要int 型才能调用，所以就小小的改了

2.写了一遍后深刻理解了静态链表为啥在日常工作中是“稀有物种”了，原理真的非常晦涩，报错是经常性的，如果关系稍微搞晕了，一行报几个错是非常正常的(手动苦涩).以后能不用静态链表就尽量不用吧！(笑哭)

3.这里搬运一些闵老的感悟，很难不认同！

1nodes 存储节点, used 存储空间使用情况, 0 表示空闲, 1 表示被占用.
2next 是一个整数, 表示相对地址. 在操作系统中, 应该是绝对地址.
3这里用 -1 表示 NULL.
4 nodes[0] 永远存储头节点.
5 并没考虑多个链表共享同一片空间的情况, 但这是真实操作系统需要面对的.
6 paraListPtr->nodes[paraListPtr->nodes[p].next].data 这种代码有一点点复杂, 懂了就好办. 这个代码的调拭也就 10 分钟.

——————————————华丽的分界线——————-————

1.这个图呢，就是小小的分析了静态链表。可以看到，和前几篇的单，双链表的图示不同，它的图很大、很长。其实不难理解，因为它的优点也是它的缺点(提前申请了一大片内存空间),所以它的图注定了会很大，很死板。缺点一目了然，那就不再多说了哈！

2.建立一个静态链表

其实也和建立其他表差不多，没啥好说的，唯一新奇巧妙的可能就是指针居然是Int类型的。怎么说呢，我对于这个操作爱恨交加。爱是用数组游标代替确实非常巧妙！恨是在于，这个非常炫酷的操作，带来了后续的麻烦,尤其是对我这种对地址、内存理不太清楚的小白。

3.试着理清一些基本操作

1.初始化静态链表：把 a[0] 的 next 设为 -1
2.如何判断结点是否为空：可让 next 为某个特殊值
3.插入位序为 i 的结点：
①找到一个空的结点，存入数据元素
②从头结点出发找到位序为 i-1 的结点
③修改新结点的 next
④修改 i-1 号结点的 next
4.删除某个结点：
①从头结点出发找到前驱结点
②修改前驱结点的游标
③被删除结点 next 设为 -2

静态链表：用数组的方式实现的链表
（1）优点：增、删 操作不需要大量移动元素
（2）缺点：不能随机存取，只能从头结点开始依次往后查找。(为啥呢，显然跟前文提到的内存上的致命缺陷有关系噻）
（3）适用场景：①不支持指针的低级语言(别杠，注意我说的是低级语言，不是java或者python哈!)②数据元素数量固定不变的场景（比如FAT分配表）