博客

代码实现

今天敲的是静态链表。静态链表相当于是用一个数组来实现线性表的链式存储结构，在静态链表中操作的是数组。静态链表区别于单链表的一大特点是，静态链表有部分的空间是由我们自己进行安排，所以这部分的代码自我感觉理解起来可能会更困难，所以会多一些文字说明，尽可能把其中的内存分配原理说清楚。

结构体定义

在这里我们定义了两个结构体，第一个结构体用于用户对空间进行分配：data表示用户存储的数据，next用于指明各个元素的直接后继元素所在数组中的位置下标；

第二个结构体用于系统对空间进行分配：nodes表示用户进行分配之后的一片片小空间，used用于标记空间是否被使用。我们可以借助下图了解：

#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(StaticLinkedList));
	
	tempPtr->nodes =(NodePtr)malloc(sizeof(StaticLinkedNode));
	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;
} 

在创建中，我们先是在内存中为tempPtr申请了一块内存空间，接着，我们又在tempPtr中为nodes和used申请了一块空间，其中，为used申请的空间是我们所决定的，在这里是5。

具体的我们可以看下图：



从图我们可以清晰的看出来，tempPtr的内存空间是由系统分配给我们的，而我们可以自主安排这一块内存空间。在创建中，我们让第一个节点始终保持被使用的状态，将其标记为1。

输出

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;
	
	p=0;
	for(i=0;i<paraPosition;i++)
	{
		p=paraListPtr->nodes [p].next;
		if(p==-1)
		{
			printf("The position %d is beyond the scope of the list.\r\n",paraPosition);
			return;
		}
	}
	
	for(i=1;i<DEFAULT_SIZE;i++)
	{
		if(paraListPtr->used [i]==0)
		{
			
			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;
	
	printf("Linking.\r\n");
	paraListPtr->nodes [q].next=paraListPtr->nodes [p].next;
	paraListPtr->nodes [p].next=q;
} 

在静态链表中，我们的插入会显得比较复杂。

首先，我们设置一个p变量，将p的值等于我们想要删除元素的上一个节点处的位置下标；

紧接着，我们需要找到整个静态链表中未被使用的空间，也就是标记为0的地方，我们将其标记为1，然后使变量q等于此处的位置下标；

然后让nodes中下标为q的数据域等于我们想要插入的值；

接下来，让nodes[q]中的next变为nodes[p]中的next，也就是-1，再使nodes[p]的next变为q，也就是第q个节点，至此，插入完成。

删除

先看图解，再说伪算法：



静态链表的删除：

1.首先找到我们需要删除元素的上一个节点，记录下此节点的位置下标p；

2.让q等于我们想要删除的元素的位置下标；

3.让p所指向的元素的位置下标直接等于q所指向的元素的位置下标，也就是p的下下个元素；

4.将以q为位置下标的空间标记为0，下次再使用这片空间时数据直接被覆盖。

//删除
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;
	
	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);
}

运行结果

小小的总结

静态链表确实在理解上会更加晦涩，但却能很好的帮助我们去了解内存的分配方式。通过代码可以看出，使用静态链表存储数据，数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间”一对一”的逻辑关系通过一个整形变量（我们所定义的next）维持（和链表类似）。

我认为静态链表和单链表最主要的区别依然是在于二者的内存分配方式，静态链表给了用户自己分配一片内存空间的权利，而单链表则全由系统进行分配。

并且静态链表在插入和删除操作时，只需要修改next，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要大量移动元素的缺点。不过静态链表仍然没有解决连续存储分配(数组)带来的表长难以确定的问题