本文共 3825 字，大约阅读时间需要 12 分钟。

昨天写的单链表，我们称为动态链表，它在计算机内没有固定的储存位置，又或者说，他的储存范围是整个内存空间。 而今天我们介绍一个新的线性表结构——**静态链表** 那么我们来看一下什么是静态链表：我们通常会说静态链表是顺序表和动态链表的结合，这是为什么呢？这是因为，静态链表和顺序表一样限制了有限的空间，而在这个空间内，用链表的方式来排序。 在静态链表中，和动态链表一样分为两个区域，但称呼却不相同：数据域和游标。这个游标就像是类似于指针一样指向下一个结点，但他却是一个int型的变量，他真正所指向的也不过是下一个数组的下标。【我们姑且可以吧静态链表看作是一个巨大的数组】 接下来我们来说一下静态链表的优点吧： 它将顺序表和动态链表相结合，所以即继承了顺序表的数组存储，便于遍历操作，又可以像动态链表中插入一样，只需要轻微改动就可以完美插入，避免了顺序表中的大量移动，而对于空间限制问题，在静态链表中，为了提高空间重复利用，我们可以将不用的结点放入备用链表中，具体的图片我这没有，大家可以找一下，会很方便理解的。简单的说一下就是在申请的巨大的空间内，我们从数组1的位置开始数据链表构建，数据链表由下标0作为结尾，也就是最后指向数组0的时候就结束了，而为了方便对于空间的管理，我们从数组0开始，将没有用的结点串成一条备用链表。 介绍的差不多了，那么照例将代码贴上：

#include
   
    #define maxSize 7typedef struct{   	int data; //数据域 	int cur; //游标 }component;/*创建备用链表*/void reserveArr(component *array){   	int i;	for( i = 0; i < maxSize; i++){   		array[i].cur = i+1; //将每个数组分量连接到一起 	}	array[maxSize-1].cur = 0; //链表的最后一个节点的游标值赋值0 } /*提取分配空间*//*主要目的就是将备用链表中的一个值提取出来，放在数据链表中【数据链表从数组1的位置开始，而备用链表从0开始，】因为当数据链表指到0的时候停止，而为了方便，我们一般都会将紧接着备用链表的那个结点拿出来*/ int mallocArr(component *array){   	int i = array[0].cur;	if(array[0].cur){    //返回游标，并且array[0]的游标不为0的时候将下一个节点的游标付给array[0] 		array[0].cur = array[i].cur;	}	return i;} /*初始化静态链表*/int initArr(component *array){   	reserveArr(array);	int body = mallocArr(array); //从备用链表中取出一个作为头结点 	int tempBody = body; //声明一个变量作为游标，并且让他指向链表的最后的一个结点 	int i;	for(i = 1; i < 5; i++){   		int j = mallocArr(array); //继续从备用链表中取出空间 		array[tempBody].cur = j; //将新取出的空间连接在链表最后一个结点之后 		array[j].data = 'a'+i-1; //给新申请的数据域进行初始化 		tempBody = j;//将指针向后移一位 	}	array[tempBody].cur = 0; //将新链表最后结点的游标设置为0 	return body;} /*静态链表中的查找数据*/int selectElem(component *array, int body, char elem){   	int tempBody = body; //记录游标位置 	while(array[tempBody].cur != 0){    //当游标为0时，链表结束 		if(array[tempBody].data == elem){   			return tempBody; //返回数组位置 		}		tempBody = array[tempBody].cur;  	}	return -1; //没有找到该元素 } /*更改数据*/ void amendElem(component *array, int body, char oldElem, char newElem){   	int add = selectElem(array, body, oldElem); //找到需要替换的数据域的位置 	if(add == -1){   		printf("无更改元素");		return;  //没有找到旧值，跳出该调用函数 	} 	array[add].data = newElem; //将新的值替换旧的值 } /*插入结点*/void insertArr(component *array, int body, int add, char a){    //add是位置，a是插入的值 	int tempBody = body; //tempBody用来遍历链表 	int i;	for( i = 1; i < add; i++){    //找到需要插入的上一个结点的位置 		tempBody = array[tempBody].cur;	}	int insert = mallocArr(array); //申请空间 	array[insert].cur = array[tempBody].cur; //将要插入的游标，等于上一个结点的游标，用来确定后一个结点位置 	array[insert].data = a; //将需要插入的值赋予该结点 	array[tempBody].cur = insert; //将上一个结点的游标指向插入的结点 } /*静态链表的删除操作*/ void deletArr(component *array, int body, char a){   	int tempBody = body;	/*该循环查找我们所需要的结点，如果没有则跳出该调用函数*/	while(array[tempBody].data != a){   		tempBody = array[tempBody].cur;		if(tempBody == 0){   			printf("链表中没有该数据");			return;		}	}	//找到该结点 	int del = tempBody;	tempBody = body;	//找到该结点的上一个结点，将其游标改成删除结点的游标 	while(array[tempBody].cur != del){   		tempBody = array[tempBody].cur;	}	array[tempBody].cur = array[del].cur;		freeArr(array, del);} /*将删除的数据返回备用链表中，以备重新利用*/void freeArr(component *array, int k){   	array[k].cur = array[0].cur;	array[0].cur = k;} void displayArr(component *array, int body){   	int tempBody = body;	while(array[tempBody].cur){   		printf("%c,%d\n", array[tempBody].data,array[tempBody].cur);		tempBody = array[tempBody].cur;	}	printf("%c,%d\n", array[tempBody].data,array[tempBody].cur);}int main(){   	component array[maxSize];	int body = initArr(array);	printf("静态链表为：\n");	displayArr(array, body);		printf("在地3的位置上插入结点'e'：\n");	insertArr(array, body, 3, 'e');	displayArr(array, body);		printf("删除数据域为'a'的结点：\n");	deletArr(array, body, 'a');	displayArr(array, body);		printf("查找数据域为'e'的结点的位置：\n");	int selectAdd = selectElem(array, body, 'e');	printf("%d\n", selectAdd);		printf("将结点'e'改为'h'：\n");	amendElem(array, body, 'e', 'h');	displayArr(array, body);		return 0;}