資料結構——靜态連結清單

昨天寫的單連結清單，我們稱為動态連結清單，它在計算機内沒有固定的儲存位置，又或者說，他的儲存範圍是整個記憶體空間。
 而今天我們介紹一個新的線性表結構——**靜态連結清單**
 那麼我們來看一下什麼是靜态連結清單：我們通常會說靜态連結清單是順序表和動态連結清單的結合，這是為什麼呢？這是因為，靜态連結清單和順序表一樣限制了有限的空間，而在這個空間内，用連結清單的方式來排序。
 在靜态連結清單中，和動态連結清單一樣分為兩個區域，但稱呼卻不相同：資料域和遊标。這個遊标就像是類似于指針一樣指向下一個結點，但他卻是一個int型的變量，他真正所指向的也不過是下一個數組的下标。【我們姑且可以吧靜态連結清單看作是一個巨大的數組】
 接下來我們來說一下靜态連結清單的優點吧：
 它将順序表和動态連結清單相結合，是以即繼承了順序表的數組存儲，便于周遊操作，又可以像動态連結清單中插入一樣，隻需要輕微改動就可以完美插入，避免了順序表中的大量移動，而對于空間限制問題，在靜态連結清單中，為了提高空間重複利用，我們可以将不用的結點放入備用連結清單中，具體的圖檔我這沒有，大家可以找一下，會很友善了解的。簡單的說一下就是在申請的巨大的空間内，我們從數組1的位置開始資料連結清單建構，資料連結清單由下标0作為結尾，也就是最後指向數組0的時候就結束了，而為了友善對于空間的管理，我們從數組0開始，将沒有用的結點串成一條備用連結清單。
 介紹的差不多了，那麼照例将代碼貼上：
           

#include<stdio.h>
#define maxSize 7

typedef 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;
}