C語言實作靜态連結清單

定義靜态連結清單的結構體

#define MAX_SIZE 30
#define ElemType char
//定義靜态連結清單的節點，由資料和遊标組成
typedef struct StaticNode {
	ElemType data;
	int cur;
}Node;

//這個結構包含了30個Node類型的節點，如圖所示
typedef Node StaticList[MAX_SIZE];
           

初始化

cur遊标指向下一個數組元素的index（利用下标模拟指針）

//引用，給main函數調用的mylist起别名，指向同一塊記憶體空間
void InitList(StaticList  &space) {
	for (int i = 0; i < MAX_SIZE - 1; i++) {
		space[i].cur = i + 1;
	}
	space[MAX_SIZE - 1].cur = 0;
	space[0].cur = -1;
}
           

插入（頭插）

head表示真實有資料的位置起始

pool表示剩餘空間的位置起始

先插入A

如果再插入B（頭插）-1表示已經是最後一個元素了

void Insert(StaticList &space, ElemType x) {
	int i = Malloc(space);
	if (i == 0) {
		printf("申請節點失敗\n");
		return;
	}

	space[i].data = x;
	if (space[0].cur == -1) {//如果插入的是第一個節點
		space[i].cur = -1;//新插入的元素cur為-1
		space[0].cur = i;//頭結點指向第一個節點在space數組中的位置
	}
	else {
	//因為是頭插，新插入的元素直接被頭結點指向，space[0].cur是原來被頭指針指向的元素，現在放在新插入元素後
		space[i].cur = space[0].cur;
		space[0].cur = i;
	}
}

void showlist(StaticList &space) {
	int i = space[0].cur;
	while (i != -1) {
		printf("%c-->", space[i].data);
		i = space[i].cur;
	}
	printf("NULL\n");
}
//配置設定一個新節點空間
int  Malloc(StaticList &space) {
	int i = space[1].cur;//space[1]的下标為2，space[2]的下标為3，
	if (space[1].cur != 0) {
		space[1].cur = space[i].cur;//space[2]的下标為3指派給space[1]的下标，即space[1]，cur=3
		//space[1]用于指向下一個可插入的節點的位置，在這裡是space[3]
	}
	return i;//傳回2，從space[2]的地方開始插入
}
//測試
void main() {

	StaticList mylist;
	InitList(mylist);

	for (int i = 0; i < 3; i++) {
		Insert(mylist, 'A'+i);
	}
	showlist(mylist);
}
           

一開始記憶體中

插入一個資料後

插入兩條資料後（因為是頭插，新元素放在頭結點後面）

插入資料完畢

删除（頭删）

void Delete(StaticList &space) {
	//1.找到現在頭結點指向的元素（即要删除的元素）
	int i = space[0].cur;
	//2.把要删除元素的cur指派給頭結點，換種說法是讓指針指向删除元素的cur所指向的下一個元素
	space[0].cur = space[i].cur;
	//3.讓沒有存放資料的節點（按照初始化的順序）連續起來  即原來4->cur指向5，現在變成原來這樣
	space[i].cur = space[1].cur;
	//4.以前沒有存放資料的位置是5，現在是4（即要删除節點的位置），space[1].cur永遠指向下一個能存放結點的位置。
	space[1].cur = i;

}
           

2.

3.

4.