点击刷新
不同于动态链表，需要指针来建立节点之间的联系，而有些问题来说，节点的地址是比较小的整数（例如5位数的整数），这样就没必要建立动态链表，而使用方便得多的静态链表。
静态链表的实现原理是hash，通过建立一个结构体数组，并令数组的下标直接表示节点的地址，来达到直接访问数组中的元素就能访问节点的结果。
静态链表不需要头节点。
#include<stdio.h> #include<stdlib.h> struct Node { typename data;//数据域 int next;//指针域 }node[size]; //例子： node[11111].next = 22222; node[22222].next = 33333; node[33333].next = -1;//-1对应动态链表中的NULL; //由于可能要使用sort函数，在使用静态链表时尽量不要把结构体类型名和结构体变量名取成相同的名字,sort（首元素地址，尾元素地址的下一位置，比较函数）。
通用解题步骤：
1.定义静态链表：
struct Node { int address;//节点地址 typename data;//数据域 int next;//指针域 XXX;// 节点的某个性质，不同题目有不同的设置，例如可以设置为节点是否在链表上。 };
2.对静态链表进行初始化，对定义中的xxx初始化将其定义为一个正常情况下达不到的数字（小于所有能达到的数字）。例如对节点是否在在链表上这一性质来说，我们可以先将XXX定义为false或者0；
for (int i = 0; i < maxn; i++) { node[i].XXX = 0; }
3.根据题目中给出的一条链表首节点的地址，来遍历整条链表，同时对xxx进行标记，（同时用count可以对有效节点进行计数）。
int p = begin, count = 0; while (p != -1) { XXX = 1; count++; p = node[p]->next; }
4.通过sort函数对结构体数组进行排序，将有效节点都移到结构体数组的一端（如对xxx的性质进行从大到小排序等）。通过count的数值来访问它
5.一般题目会有额外的要求，cmp函数中一般都有第二级排序，在对两个节点都是有效节点的时候进行第二级排序。
例如：
bool cmp(Node a, Node b) { if (a.XXX == -1 || b.XXX == -1) { //至少一个节点为无效节点，就把他放到数组后面 return a.XXX > b.XXX; } else { //第二级排序 } }
6.此时有效节点就在数组的左端了，之后根据题目的要求进行接下来的操作。
练习例题：
© 著作权归作者所有
举报
发表评论
0/200
