博客

静态链表不同于单链表的有：静态链表所分配的存储数据的空间是相邻的，这个空间就像是数组空间，不同的是每个小空间内不止存有有数据，而且还有数字，这里的数字就作为访问数组内下一个小空间的脚标，起到了类似指针的作用；静态链表不仅包括了数组的空间，还分配了一个数组大小和存储数据的数组大小相同的空间，用于0和1标记存储数据的空间是否已经被使用。同时静态链表的空间在使用过程中大小不变。而单链表每个空间不一定相邻，采用的是指针连接，且空间可变

具体理解请结合图示，代码一起理解：

图示：

存储数据的结构体

typedef struct StaticLinkedNode{
	char data;//数据
	int next;//脚标
}*NodePtr;

指向两片空间的指针的结构体

typedef struct StaticlinkedList{
	NodePtr nodes;//指向存储空间区域
	int *used;//指向判断 储空间区域是否被使用的区域
}*ListPtr; 

静态链表的初始化 

ListPtr initLinkedList(){
	ListPtr tempPtr = (ListPtr)malloc(sizeof(struct StaticlinkedList));
	
	tempPtr->nodes  = (NodePtr)malloc(sizeof(struct StaticLinkedNode)*DEFAULT_SIZE);//用于储存数据 ,得到空间 
	tempPtr->used = (int*)malloc(sizeof(int)*DEFAULT_SIZE);//用于标记空间是否被占用 
	
	tempPtr->nodes[0].data = '\0';
	tempPtr->nodes[0].next = -1;
	
	tempPtr->used[0] = 1;
	for(int i = 1;i < DEFAULT_SIZE;i++){
		tempPtr->used[i] = 0;
	}
	
	return tempPtr; 
}//静态链表的初始化 

打印链表 

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 = 0,q,i;
	
	for(i = 0;i < paraPosition;i++){
		if(paraListPtr->nodes[p].next == -1){
			printf("超出链表此时的长度，不存在第%d位置\r\n",paraPosition);
			return; 
		}
		p = paraListPtr->nodes[p].next;
	}//判断该位置是否存在 
	
	for(i = 0;i < DEFAULT_SIZE;i++){
		if(paraListPtr->used[i] == 0){
			printf("Space at %d allocated.\r\n", i);
			q = i;
			paraListPtr->nodes[q].data = paraChar;
			paraListPtr->used[i] = 1;
			break;
		}
	}//追踪数据储存的空间的区域 

	if(i == DEFAULT_SIZE){
		printf("没有空间可存储\r\n");
		return; 
	}//判断该静态链表还是否存在多余的空间 
	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("没有该元素可以删除\r\n");
		return;
	}
		q = paraListPtr->nodes[p].next;
		paraListPtr->nodes[p].next =  paraListPtr->nodes[paraListPtr->nodes[p].next].next;//删除元素 

		paraListPtr->used[q] = 0;//释放空间，将空间标记为未使用状态
} //删除元素函数 

完整代码 

#include <stdio.h>
#include <malloc.h>
#define DEFAULT_SIZE 5

typedef struct StaticLinkedNode{
	char data;
	int next;
}*NodePtr;

typedef struct StaticlinkedList{
	NodePtr nodes;
	int *used;
}*ListPtr; 

ListPtr initLinkedList(){
	ListPtr tempPtr = (ListPtr)malloc(sizeof(struct StaticlinkedList));
	
	tempPtr->nodes  = (NodePtr)malloc(sizeof(struct StaticLinkedNode)*DEFAULT_SIZE);//用于储存数据 ,得到空间 
	tempPtr->used = (int*)malloc(sizeof(int)*DEFAULT_SIZE);//用于标记空间是否被占用 
	
	tempPtr->nodes[0].data = '\0';
	tempPtr->nodes[0].next = -1;
	
	tempPtr->used[0] = 1;
	for(int i = 1;i < DEFAULT_SIZE;i++){
		tempPtr->used[i] = 0;
	}
	
	return tempPtr; 
}//静态链表的初始化 

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 = 0,q,i;
	
	for(i = 0;i < paraPosition;i++){
		if(paraListPtr->nodes[p].next == -1){
			printf("超出链表此时的长度，不存在第%d位置\r\n",paraPosition);
			return; 
		}
		p = paraListPtr->nodes[p].next;
	}//判断该位置是否存在 
	
	for(i = 0;i < DEFAULT_SIZE;i++){
		if(paraListPtr->used[i] == 0){
			printf("Space at %d allocated.\r\n", i);
			q = i;
			paraListPtr->nodes[q].data = paraChar;
			paraListPtr->used[i] = 1;
			break;
		}
	}//追踪数据储存的空间的区域 

	if(i == DEFAULT_SIZE){
		printf("没有空间可存储\r\n");
		return; 
	}//判断该静态链表还是否存在多余的空间 
	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("没有该元素可以删除\r\n");
		return;
	}
		q = paraListPtr->nodes[p].next;
		paraListPtr->nodes[p].next =  paraListPtr->nodes[paraListPtr->nodes[p].next].next;//删除元素 
		paraListPtr->used[q] = 0;//释放空间 	
} //删除元素函数 

void appendInsertDeleteTest(){
	ListPtr tempList = initLinkedList();
	printList(tempList);

	insertElement(tempList, 'H', 0);
	insertElement(tempList, 'e', 1);
	insertElement(tempList, 'l', 2);
	insertElement(tempList, 'l', 3);
	insertElement(tempList, 'o', 4);
	printList(tempList);//测试插入函数 

	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();
}

测试结果