《数据结构》线性表的静态链表实现

数据结构中的线性表指的是在逻辑上连续呈现出线性的一组数据元素。它的实际实现方法根据存储结构的不同可以分为顺序实现、链式实现、静态链式实现。这里介绍不常见的静态链表实现。它的存储结构主要依赖于数组，也就是说不同于顺序实现和链式实现，它的链表长度的不可变化的。存储结构逻辑图如下：

规定了这个无名结构体也可以被叫做com型变量，100的这个变量组成的数据被称作SList变量。上图给出了一个实例，这个数组大小为5，假如数组名是l的话。数组第一个元素的数据与为空，游标域的值是逻辑上第一个元素的物理位置，这里是2，即l**[0].dataNULL,l[0].cur2**所以逻辑上第一个元素是l[2].data,也就是QIAN。而l[2].cur的值又是逻辑上下一个元素的物理地址，这里是1，即逻辑上第二个元素就是l[1].data,这里是ZHAO。熟悉链表的话应该可以看出来，这里数组的第一个元素就是充当了链表中的头结点的作用，数据域为空。而游标的作用和链表实现中的指针的作用是相当的，指向下逻辑上下一个元素的物理位置。这里给出一个静态链表的初始化函数的C语言实现。

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

typedef struct{
	int data;
	int cur;
}component,SLinkList[MAX];

int main(){
	void InitList(SLinkList);	
	
	SLinkList a;
	for(int i=0;i<MAX;i++){
		printf("%d\t",a[i].cur);
	}
	printf("\n\n\n\n");
	InitList(a);
	for(int i=0;i<MAX;i++){
		printf("%d\t",a[i].cur);
	}
}

void InitList(SLinkList sl){
	for(int i=0;i<MAX-1;i++){
		sl[i].cur=i+1;
	}
	sl[MAX-1].cur=0;
}

运行结果：
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16777216 0 0 0 0 0 32762 0 0 3673957 32762 0 0 0 0 0 0 0 0 0 7733349 6029413 0 0 7667820 6029365 7471205 6553665 6881390 6357106 6029426 7012467 6029424 1736730426 -1795268607 3044272 101 0 32762 0 32762 0 0 32762 0 0 0 0 0 0 0 0 32762 0 0 0 0 0 0 0 32762 0 0 0 0 0 32762 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 0

Process exited after 0.2331 seconds with return value 0
请按任意键继续. . .
这里做了一个小实验，证明链表a确实被初始化了。未初始化的时候，每个数组元素的cur值都是随机的，初始化中，把每个数组元素的游标值都设置为它物理上下一个。
明白了静态链表的结果之后，我们可以把线性表的三种实现方式做一个比较
1：顺序实现，线性表中的每个数据元素物理上的位置即为逻辑上的位置，这样，它支持动态管理大小。它的优点是由于物理位置和逻辑位置一一对应，多以可以随机存取，在访问和或者修改值的时候速度很快，但是一旦涉及插入或者删除的操作的时候就很浪费时间和空间了，因为要保持物理位置和逻辑位置一一对应的关系，插入一个元素的时候，它后面的元素都要向后面诺挪一位，在排序的时候同样面临这个问题，速度慢，消耗空间大。
2：链式实现，每一个元素都存在结点中，物理上完全随机存放，靠着指针将他们逻辑上关联起来，在访问元素或者修改元素的时候，都只能从头指针出发挨个找，所以会比顺序实现慢一点，但是其实也瞒不了多少。但是它的有点更加明显，在进行插入或者删除、排序等操作的时候，只需要改变几个元素的指针的值就可以了，完全不需要挪动元素，速度快消耗空间极少。
3：静态链式实现，线性表中的每个元素在物理上存在一个连续的地址空间中，但是物理位置又不一一对应逻辑位置，通过一个结果体数组，第一个数组元素的数据域是NULL，它的游标域是逻辑上第一个元素的物理位置。它的缺点很明显是线性表的大小固定，在访问和修改元素的时候也必须想链表一样从第一个数据元素开始，根据游标值挨个找。无法实现随机访问，在插入或者删除、排序的时候，也不需要挪动元素，花费的代价和链表是差不多。性能来看，静态链表于链表类似，这样就这给了不提供指针的高级程序设计语言提供了和链表性能接近的顺序表实现，当时大小固定到底还是个硬伤啊。