資料結構與算法之線性表（靜态連結清單）

靜态連結清單

靜态連結清單是用數組描述的連結清單，這種描述的方法叫遊标實作法

線性表的靜态連結清單存儲如圖：

如上圖：數組模拟的靜态連結清單有兩個元素，一個儲存資料和一個儲存遊标

這裡有幾個特殊的地方：

（1）靜态連結清單的頭和尾都不儲存資料

（2）第一個結點的遊标存放數組中第一個沒有資料的下标

（3）最後一個元素的遊标存放第一個有資料的下标，也就是數組的第二個元素，下标為1

（4）從第一個有資料的元素開始，遊标存放的是下一個元素的下标，依次類推，形成連結清單的形式

（5）最後一個有資料的遊标為0

靜态連結清單的資料結構：

/*
*靜态連結清單的定義
*/

#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 1000
typedef int ElemType;

typedef struct 
{
	ElemType data;//資料
	int cur;//遊标
}Componet,StaticList[MAXSIZE];
           

對靜态連結清單進行初始化相當于初始化數組

/*
*靜态連結清單的定義
*/

#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 1000
typedef int ElemType;

typedef struct 
{
	ElemType data;//資料
	int cur;//遊标
}Componet,StaticList[MAXSIZE];

//初始化靜态連結清單
Componet initList(StaticList space)
{
	int i;
	for ( i = 0; i < MAXSIZE; i++)
	{
		space[i].cur = i + 1;
	}
	space[MAXSIZE - 1].cur = 0;
	return OK;
}
           

靜态連結清單的定義生成總結：

--對數組的第一個和最後一個元素做特殊處理，他們的data存放資料

--通常把未使用的數組元素（無資料）稱為備用連結清單

--數組的第一個元素，即下标為0的元素的cur就存放備用連結清單的第一個結點的下标

--數組的最後一個元素，即下标為MAXSIZE-1的cur則存放第一個有數值的元素的下标，相當于單連結清單中的頭結點的作用

靜态連結清單的插入和删除操作

--在靜态連結清單中，我們操作的是數組，不存在像動态連結清單的結點申請和釋放的問題，是以我們需要自己實作這兩個函數，才能做到插入和删除操作

--解決的辦法是将所有未被使用過的和以及被删除的遊标鍊成一個備用連結清單

（1）靜态連結清單的插入操作

/*
*靜态連結清單的定義
*/

#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 1000
typedef int ElemType;
typedef int Stu;

typedef struct 
{
	ElemType data;//資料
	int cur;//遊标
}Componet,StaticList[MAXSIZE];

//初始化靜态連結清單
Stu initList(StaticList space)
{
	int i;
	for ( i = 0; i < MAXSIZE; i++)
	{
		space[i].cur = i + 1;
	}
	space[MAXSIZE - 1].cur = 0;
	return OK;
}

//擷取空閑元素（無資料的）下标
int malloc_i(StaticList space)
{
	int i = space[0].cur;//第一進制素的遊标存放的就是第一個空元素的下标
	if (space[0].cur)//如果space[0].cur不為0
	{
		space[0].cur = space[i].cur;//就接着把i位置的遊标再給第一個元素的遊标
	}
	return i;
}

//靜态連結清單的插入
Stu insertList(StaticList L,int i ,ElemType e)
{
	int k,j,m;
	k = MAXSIZE - 1;//最後一個元素的下标
	if (i<1 || i>StaticList(L) - 1)
	{
		return ERROR;
	}

	j = malloc_i(L);
	if (j)
	{
		L[j].data = e;
		for (m = 1; m <= i - 1; m++)
		{
			k = L[k].cur;//把最後一進制素的遊标
		}
	}
	L[j].cur = L[k].cur;
	L[k].cur = j;
	return OK;
}
           

（2）靜态連結清單的删除

//靜态連結清單的删除
Stu DeleteList(StaticList L, int i)
{
	int k, j;
	k = MAXSIZE - 1;//最後一個元素的下标
	if (i<1 || i>StaticList(L) - 1)
	{
		return ERROR;
	}
	for (j = 1; j <= i - 1; j++)
	{
		k = L[k].cur;//把最後一進制素的遊标
	}

	j = L[k].cur;
	L[k].cur = L[j].cur;

	Pree_i(L, j);//把删除的元素加入到未使用的連結清單中

	return OK;
}

//把删除的元素加入到未使用的連結清單中
void Pree_i(StaticList L, int i)
{
	L[i].cur = L[0].cur;
	L[0].cur = i;
}
           

（3）傳回靜态連結清單的元素個數

//傳回L中資料元素的個數
int ListLength(StaticList L)
{
	int j = 0;
	int i = L[MAXSIZE - 1].cur;

	while (i)
	{
		i = L[i].cur;
		j++;
	}
	return j;
}
           

靜态連結清單的優點和缺點：

優點

--在插入和删除操作，隻需要修改遊标，不需要移動元素，進而改進了在順序存儲結構中插入和删除操作需要移動大量元素的缺點

缺點

--沒有解決連續存儲配置設定（數組）帶來的表長難以确定的問題

--失去了順序存儲結構随機存取的特性