資料結構之動態順序表（含游戲選單）

上一篇文章我們談了資料結構的靜態順序表，以及實作了靜態順序表，具體可以看我的上一篇文章->>>資料結構之靜態順序表.

我們可以知道,靜態順序表的缺點是: 因為使用的是定長陣列,所以空間給少了不夠用,給多了,就會造成空間的浪費.

由此,我們引入一個新的順序表----動態順序表.

目錄

一.什么是動態順序表

什么是邏輯結構和物理結構

二.動態順序表的優缺點

三.創建專案

四.介面實作

1.定義順序表

2.結構體初始化

3.列印資料

4.順序表增容

5.頭插資料

6.尾插資料

7.頭刪資料

8.尾刪資料

9.查找資料、

10.某一位置插入資料

11.洗掉某一位置

12.修改某一位置資料

13.順序表的元素個數

14.銷毀順序表

精華總結：

附:原碼鏈接

一.什么是動態順序表?

動態順序表：使用動態開辟的陣列存盤，使用指標指向動態開辟的陣列，可以進行擴容，可以隊陣列內容進行增刪查改等操作，

這里順便提一下什么是邏輯結構和物理結構

• 邏輯結構: 人為想象出來的,實際并不存在.
• 物理結構: 實際存在,可以被觀察到

二.動態順序表的優缺點

優點：空間連續，支持隨機訪問，

缺點：1.中間或前面部分的插入時間復雜度是O(N)，

2.增容的代價比較大

三.創建專案

四.介面實作

1.定義順序表

為了后續我們想更改資料型別時方便，我們一般對型別進行typedef操作，

typedef int SeqlistType;

//創建結構體
typedef struct Seqlist
{
	SeqlistType* arr;	//指向動態開辟的陣列
	SeqlistType size;	//有效個數
	SeqlistType capacity;//容量
}SL;

2.結構體初始化

傳值：因為形參是實參的一份臨時拷貝，對形參的改變并不會改變實參，所以我們應該把結構體變數的地址傳過去，用結構體指標接收！為了防止傳過來的是空指標，我們可以用assert進行斷言！

void SeqlistInit(SL* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

3.列印資料

我們只需要遍歷順序表就能完成列印

void SeqlistPrint(SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

4.順序表增容

我們插入資料時，應該要先檢查順序表的容量是否滿了（ps->size == ps->capacity）

因為一開始我們時沒有給容量的（capacity = 0），所以我們可以先給4個空間，后續不夠空間了再兩倍的擴容！

//檢查容量
void SeqlistCheckCapacity(SL* ps)
{
	assert(ps);
	//當size == capacity時要擴容了
	int newcapacity = 0;
	if (ps->size == ps->capacity)
	{
		newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
		//如果一開始容量為0，就給4個空間
		//不為0就擴為原來的2倍
		//擴容還要重新開辟空間->realloc
		SeqlistType* tmp = 
			(SeqlistType*)realloc(ps->arr, sizeof(SeqlistType) * newcapacity);
		//注意：要判斷是否開辟成功
		if (tmp == NULL)
		{
			printf("擴容失敗\n");
			//exit(-1);
			return;
		}
		else
		{
			ps->arr = tmp;
			ps->capacity = newcapacity;
		}
	}
}

5.頭插資料

頭插資料：1.要先檢查順序表容量，不夠則擴容

2.頭插即為把資料放到第一個位置，那我們把陣列原來的資料向后移動即可！要注意從最右邊的開始移動(i = ps->size-1)，否則前面的資料會把后面的資料覆寫！

3.插入資料后，標記有效數字的size+1；

//頭插
void SeqlistPushFront(SL* ps, SeqlistType x)
{
	assert(ps);
	//注意先檢查容量！！！！
	SeqlistCheckCapacity(ps);
	int i = 0;
	for (i = ps->size-1; i >=0; i--)
	{
		ps->arr[i+1] = ps->arr[i];
	}
	ps->arr[0] = x;
	ps->size++;
}

6.尾插資料

尾插資料：1.尾插資料也要先檢查容量

2.在陣列的位置上插入資料即：ps->size位置

3.插入資料，szie++；

//尾插
void SeqlistPushBack(SL* ps, SeqlistType x)
{
	assert(ps);
	//注意先檢查容量！！！！
	SeqlistCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

7.頭刪資料

頭刪資料：1.把后面的資料往前面覆寫，要注意從左邊開始(i=0)，否則會造成資料丟失！

2.洗掉了資料，size--

void SeqlistPopFront(SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i+1];
	}
	ps->size--;
}

8.尾刪資料

只需讓有效數字-1即可，資料雖然還在陣列里，但是我們以及訪問不到了！

void SeqlistPopBack(SL* ps)
{
	assert(ps);
	ps->size--;
}

9.查找資料、

1查找元素是否在順序表內,如果元素在陣列中的下標.

2.如果不在,回傳-1 （-1為無效坐標）

3.回傳型別為int 若回傳型別寫成我們之前typedef的型別要注意typedef的型別是什么！

int SeqlistFind(SL* ps, SeqlistType x)
{
	assert(ps);
	//遍歷查找
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;	//-1為無效坐標
}

10.某一位置插入資料

函式介面實作內容：給一個下標，在該下標前位置插入資料.

1.要保證位置在陣列有效范圍內（ps->size-1范圍內）

2.把要插入位置的資料及后面的資料向后移動，注意要從最后的資料開始移動（i=ps->size-1），否則會造成前面的資料覆寫后面的資料，

3.最后把資料插入該位置，size++

//插入
void SeqlistInsert (SL* ps, SeqlistType pos, SeqlistType x)
{
	assert(ps);
	//要保證在有效區域內插入
	assert(pos < ps->size);
	//把pos位置及其后面的資料后移  
	// 要從最后面開始移動
	//要保證容量
	SeqlistCheckCapacity(ps);
	for (int i = ps->size-1; i >=pos;i--)
	{
		ps->arr[i+1] = ps->arr[i];
	}
	ps->arr[pos] = x;
	ps->size++;
}

11.洗掉某一位置

函式介面實作內容：給一個下標，洗掉該位置，

1.要保證要洗掉的位置的陣列在資料范圍內（（ps->size-1范圍內））

2.把該位置后面的資料向前移動，把要洗掉位置的資料覆寫即可，

3.洗掉掉元素->size--

//洗掉
void SeqlistErase(SL* ps, SeqlistType pos)
{
	assert(ps);
    assert(pos<ps->size);
	//把pos后面的東西前移動
	for (int i = pos + 1; i < ps->size; i++)
	{
		ps->arr[i-1] = ps->arr[i];
	}
	ps->size--;
}

12.修改某一位置資料

函式介面實作內容：給一個下標，修改該下標對應的值

要保證該下標在陣列的資料范圍內(ps->size-1范圍)

//更改資料
void SeqlistModify(SL* ps, SeqlistType pos, SeqlistType x)
{
	//要保證在有效資料范圍內更改
	assert(pos < ps->size);
	ps->arr[pos] = x;
}

13.順序表的元素個數

size標識的就是順序表的有效數字個數

//統計順序表元素數量
int  SeqListSize(SL* ps)
{
	assert(ps);
	return ps->size;
}

14.銷毀順序表

釋放掉動態開辟的陣列即可，free和指標置空要同時使用！不然就可能造成野指標！

//銷毀空間
void SeqlistDestory(SL* ps)
{
	//free和NULL要配合使用
	free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

精華總結：

1. 有些童鞋理解不了size和陣列下標的關系！下面請看圖

size是有效數字的個數，即陣列有多少個元素，陣列的下標是從0開始的，所以ps->arr[ps->size]是陣列最后一個元素后面的位置，陣列最后一個元素下標為ps->arr[ps->size-1]

其他注意事項：

！搞清楚傳值還是傳址問題！

傳值：形參是實參的一份臨時拷貝，對形參的改變并不會改變實參

1.插入資料時要檢查容量！

2.在某個下標，修改/刪/插入資料，要保證該下標在陣列下標的范圍內(ps->size-1)

3.插入/洗掉資料后，size也要記得++ /-- ！

4.頭插頭刪以及在某個下標位置前插入，要搞清楚從哪邊元素開始移動！

當我們將全部介面實作時，我們就可以設計成一個游戲選單了！

效果展示：

具體游戲代碼以及本文章中的所有代碼都在附錄！

如果感覺本篇文章對你有所幫助，請給筆者一個小小的點贊，評論和關注吧！你們的支持就是我的動力！

附:原碼鏈接

動態順序表代碼