算法與資料結構之靜态連結清單

靜态連結清單

結構體的一個成員存放資料，另一個成員(“遊标”)存放下一個數的位置(下标)，這稱為靜态連結清單。輸對外連結表不是按數組的下标順序輸出的，而是由一個指定的位置開始根據遊标依次輸出的。

将所有空閑結點連結形成一個備用連結清單，數組下标為 0 的單元為備用連結清單的頭結點(這時，連結清單的頭結點就不能再是數組下标

為 0 的單元了，需要另外定義)。靜态數組實際有 2 個連結清單，一個連結清單上連結的是線性表的結點，另一個連結清單(備用連結清單)上連結的是所有沒被使用的結點。靜态數組的每一個元素都連結在這 2 個連結清單中的一個上。當線性表需要新結點時，把備用連結清單中的首元結點(由[0].cur 訓示)從備用連結清單中删除，作為新結點，插入線性表。當删除線性表中的結點時，被删除的結點插入備用連結清單中，成為備用連結清單的首元結點。之是以從備用連結清單删除結點或向備用連結清單插入結點都在表頭進行，是因為這樣效率最高。

靜态連結清單的定義

#include<stdio.h>
#include<malloc.h>

//一個數組隻生成一個靜态連結清單

#define	MAX_SIZE 100	//連結清單的最大長度
#define Destroy Clear	//Destroy()和Clear()的操作是一樣的

//線性表的靜态單連結清單存儲結構
typedef struct
{
	int data;	//存放資料
	int cur;	//遊标，相當于指針，記錄下一結點位置
}component,List[MAX_SIZE];
           

在這裡List是結構體數組類型。

List L；
//等價于
struct component L[MAX_SIZE];
           

比如

typedef int arr[5];

arr a;就定義了一個有5個int型變量的數組a。
           

基本操作

#include<stdio.h>
#include<malloc.h>

//一個數組隻生成一個靜态連結清單

#define	MAX_SIZE 100	//連結清單的最大長度
#define Destroy Clear	//Destroy()和Clear()的操作是一樣的

//線性表的靜态單連結清單存儲結構
typedef struct
{
	int data;
	int cur;
}component,List[MAX_SIZE];

//基本操作
void Init(List L);	//構造一個空的連結清單
void Clear(List L);	//将L置為空表
bool Empty(List	L);	//判斷L是否為空表
int Length(List L);	//傳回連結清單長度
bool Get(List L,int i,int e);	//用e傳回L中第i個資料元素
int Locate(List L,int e);	//傳回第一個值為e的元素的位序
bool Priorm(List L,int cur_e,int *pre_e);//用pre_e傳回cur_e元素的前驅
bool Next(List L,int cur_e,int *next_e);//用next_e傳回cur_e元素的後繼
bool Insert(List L,int i,int e);//在第i個元素之前插入資料元素e
bool Delete(List L,int i,int *e);//删除第i個資料元素用e儲存
int Malloc(List space);	//若備用連結清單非空，則傳回配置設定的結點下标
void Free(List space,int k);//将下标為k的空閑結點回收到備用連結清單(成為備用連結清單的第一個結點)
void Traverse(List L);	//周遊

void Init(List L)
{
	//構造一個空的連結清單L，表頭為L的最後一個單元L[MAX_SIZE-1],
	//其餘單元鍊成一個備用連結清單，表頭為L的第一個單元L[0],"0"表示空指針
	int i;
	L[MAX_SIZE-1].cur=0;	//L的最後一個單元為空連結清單的表頭
	for(i=0;i<MAX_SIZE-2;i++)	//将其餘單元連結成以L[0]為表頭的備用連結清單
		L[i].cur=i+1;
	L[MAX_SIZE-2].cur=0;
}
void Clear(List L)
{
	int i,j,k;
	i=L[MAX_SIZE-1].cur;	//連結清單第一個結點的位置
	L[MAX_SIZE-1].cur=0;	//連結清單空
	k=L[0].cur;				//備用連結清單第一個結點的位置
	L[0].cur=i;				//把連結清單的結點連到備用連結清單的表頭
	while(i!=0)
	{
		j=i;
		i=L[i].cur;			//指向下一個元素
	}
	L[j].cur=k;				//備用連結清單的第一個結點接到連結清單的尾部
}
bool Empty(List L)
{
	if(L[MAX_SIZE-1].cur==0)
		return true;
	else
		return false;
}
int Length(List L)
{
	int i=L[MAX_SIZE-1].cur;
	int count=0;	//臨時存放連結清單元素個數
	while(i!=0)
	{
		count++;
		i=L[i].cur;
	}
	return count;
}
bool Get(List L,int i,int *e)
{
/*	int k=L[MAX_SIZE-1].cur;
	int j=1;	
	while(j<i&&k!=0)
	{
		j++;
		k=L[k].cur;
	}
	if(j>i||k==0)
		return false;
	*e=L[k].data;
	return true;
*/
	int j,k=MAX_SIZE-1;//k指向表頭序号
	if(i<1||i>Length(L))
		return false;
	for(j=1;j<i;j++)
		k=L[k].cur;
	*e=L[k].data;	
}
int Locate(List L,int e)
{
	int i=L[MAX_SIZE-1].cur; // i訓示表中第一個結點
	while(i&&L[i].data!=e) // 在表中順鍊查找(e不能是字元串)
		i=L[i].cur;
	return i;
}
bool Priorm(List L,int cur_e,int *pre_e)
{
	int j,i=L[MAX_SIZE-1].cur;	//i訓示連結清單第一個位置
	do{
		j=i;
		i=L[i].cur;
	}while(i!=0&&cur_e!=L[i].data);
	if(i!=0)
	{
		*pre_e=L[j].data;
		return true;
	}
	return false;
}
bool Next(List L,int cur_e,int *next_e)
{
	int j,i=Locate(L,cur_e);
	if(i)
	{
		j=L[i].cur;	//cur_e後繼的位置
		if(j)		//cur_e有後繼
		{
			*next_e=L[j].data;
			return true;
		}
	}
	return false;
}
bool Insert(List L,int i,int e)
{
	int l,j,k=MAX_SIZE-1;	//k指向表頭
	if(i<1||i>Length(L)+1)
		return false;
	j=Malloc(L);	//申請新單元
	if(j)			//申請成功
	{
		L[j].data=e;	//指派給新單元
		for(l=1;l<i;l++) // 移動i-1個元素
			k=L[k].cur;
		L[j].cur=L[k].cur;
		L[k].cur=j;
		return true;
	}
	return false;
}
bool Delete(List L,int i,int *e)
{
	int j,k=MAX_SIZE-1; // k指向表頭
	if(i<1||i>Length(L))
		return false;
	for(j=1;j<i;j++) // 移動i-1個元素
		k=L[k].cur;
	j=L[k].cur;
	L[k].cur=L[j].cur;
	*e=L[j].data;
	Free(L,j);
	return true;
}
int Malloc(List space)
{ 
	// 若備用連結清單非空，則傳回配置設定的結點下标(備用連結清單的第一個結點)；否則傳回0
	int i=space[0].cur;
	if(i) // 備用連結清單非空
		space[0].cur=space[i].cur; // 備用連結清單的頭結點指向原備用連結清單的第二個結點
	return i; // 傳回新開辟結點的坐标
}
void Free(List space,int k)
{ 
	// 将下标為k的空閑結點回收到備用連結清單(成為備用連結清單的第一個結點)
	space[k].cur=space[0].cur; // 回收結點的＂遊标＂指向備用連結清單的第一個結點
	space[0].cur=k; // 備用連結清單的頭結點指向新回收的結點
}
void Traverse(List L)
{
	int i=L[MAX_SIZE-1].cur; // 指向第一個元素
	while(i) // 沒到靜态連結清單尾
	{
		printf("%d ",L[i].data);
		i=L[i].cur; // 指向下一個元素
	}
	printf("\n");
}
int main()
{
	List L;
	Init(L);
	Insert(L,1,1);
	Insert(L,2,2);
	Insert(L,3,3);
	Insert(L,4,4);
	Insert(L,5,5);
	printf("插入的元素為：");
	Traverse(L);
	return 0;
}