本章會(huì)介紹的知識(shí)點(diǎn)如下圖：

?

?1： 順序表的概念：順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)的線性結(jié)構(gòu)，通常我們使用數(shù)組來(lái)表示，對(duì)數(shù)組進(jìn)行增刪查改。

? ? ? ? ? ? ? ? ?順序表的結(jié)構(gòu)：邏輯結(jié)構(gòu)與物理結(jié)構(gòu)都是內(nèi)存中一塊連續(xù)開辟的空間，都是11對(duì)應(yīng)的線性結(jié)構(gòu)。

2： 順序表的兩種定義方式：靜態(tài)的順序表與動(dòng)態(tài)的順序表，一般情況下我們很少會(huì)用靜態(tài)的順序表，因?yàn)殪o態(tài)的順序表會(huì)將空間固定，導(dǎo)致如果我們使用順序表的時(shí)候可能會(huì)浪費(fèi)很多的空間，也可能在我們?cè)鋈莸臅r(shí)候會(huì)出現(xiàn)空間不夠的情況，這種情況下如果我們還是在繼續(xù)使用的話那么數(shù)組將會(huì)越界這種情況是error的。

兩種定義順序表的方式代碼如下

? ? ? ? 靜態(tài)的順序表????????

typedef int SqListDataType;//這里是給我們的順序表元素的類型起個(gè)名字
//							 假設(shè)元素是其他類型我們就可以修改這里
//靜態(tài)的
struct SqList1
{
	SqListDataType arr1[1000];//開辟了一個(gè)整形的數(shù)組
	int size;//用來(lái)記錄順序表當(dāng)前使用了多少的空間
};

動(dòng)態(tài)的順序表：

????????

struct SqList2
{
	SqListDataType* arr2;
	int size;
	int Capacity;//用來(lái)記錄當(dāng)前數(shù)組開辟了多少個(gè)空間
};

在這兩種結(jié)構(gòu)中通常我們是會(huì)選擇動(dòng)態(tài)的順序表來(lái)管理數(shù)據(jù)的。

3：順序表的接口實(shí)現(xiàn)：

我們最終選擇這個(gè)定義的順序表?

????????1：這個(gè)接口的定義是應(yīng)為當(dāng)我們?cè)谠黾釉氐臅r(shí)候我們所存儲(chǔ)的元素會(huì)變多，總有一種情況下我們空間會(huì)慢，所以這時(shí)候我們就需要擴(kuò)容，使用了realloc這個(gè)函數(shù)擴(kuò)容有兩種情況，一種是原地?cái)U(kuò)，一種是換個(gè)空間擴(kuò)。不管怎么樣我們都定義一個(gè)空間，用來(lái)存儲(chǔ)新開辟的地址，讓后在給ps

//檢查容量的代碼
void check_capacity(SqList* ps)
{
	assert(ps);
	//空間不夠，擴(kuò)容,一次擴(kuò)兩倍
	if (ps->Capacity == ps->size)
	{

		SqListDataType* tmp=(SqListDataType*)realloc(ps->arr, (ps->Capacity)* 2*sizeof(SqListDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		else
		{
			printf("擴(kuò)容成功\n");
			ps->arr = tmp;
			ps->Capacity *= 2;
		}
	}
	
}

2：頭插思路：先檢查空間是否足夠，在從后往前移動(dòng)元素，將第一個(gè)位置給空出來(lái)，最后在添加元素即可。

void PushFrontSqList(SqList* ps, SqListDataType x)
{
	//先檢查空間夠不夠,空間不夠擴(kuò)容
	check_capacity(ps);//先判斷空間是否滿了
	//先移動(dòng)元素
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}

上述代碼的意思如下圖：

????????

?3：尾插思路：這個(gè)挺簡(jiǎn)單的，我們只要在size位置插入即可，size在++即可，這里要注意的就是我們插入要以數(shù)組的下標(biāo)。

代碼：

void PushBackSqList(SqList* ps, SqListDataType x)
{
	assert(ps);
	check_capacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
	//SqListInsert(ps, ps->size, x);
}

?4：頭刪思路：我們首先得判斷順序表是否有元素，如果有的話才能進(jìn)行刪除，我們只需要遍歷數(shù)組從前往后將后一個(gè)元素移動(dòng)到前一個(gè)就行，這里需要注意的就是我們移動(dòng)時(shí)位置的不同可能導(dǎo)致代碼的不一樣，而我的代碼是從第一個(gè)開始所以我最后的位置因該是size-2處，然后size--就可以了。

代碼：

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

5：尾刪思路：這個(gè)挺簡(jiǎn)單的，首先還是得判斷順序表是否存在元素，如果有將size--就行了。

代碼：

void PopBackSqList(SqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}

6：順序表得查找思路：遍歷數(shù)組就行了，如果存在則返回下標(biāo)，如果不存在我們返回-1.

代碼：

int FindSqList(SqList* ps, SqListDataType x)
{
    assert(ps);//防止ps沒(méi)有意義
	//思路：遍歷順序表找
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	//未找到
	printf("未找到\n");
	return -1;
}

7：順序表插入思路：在pos位置處插入一個(gè)元素，pos為下標(biāo)，首先先我們得判斷pos是否存在，如果存在我們先從前往后將元素向后移動(dòng)，然后在pos位置處插入即可。

代碼：

void SqListInsert(SqList* ps, int pos, SqListDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	check_capacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}

圖：

?8：順序表的刪除思路：先判斷，pos是否在順序表中，我們只要從前完后移動(dòng)pos后面的元素即可，然后我們?cè)诎裺ize--；

代碼：

void SqListErase(SqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = pos;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

9：順序表的修改思路：先判斷，pos是否在順序表中，然后在根據(jù)數(shù)組隨機(jī)訪問(wèn)的特點(diǎn)修改即可。

代碼：

void ModifySqlist(SqList* ps, int pos, SqListDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->arr[pos] = x;

}

10：打?。罕闅v數(shù)組即可

代碼：

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

11：銷毀順序表這一步也不能省略，防止內(nèi)存泄漏。

代碼：

//銷毀
void DestorySqList(SqList* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->Capacity = ps->size = 0;
}

以上就是順序表的大致結(jié)構(gòu)了。

通過(guò)上面我們可以發(fā)現(xiàn)：順序表適合尾插，尾刪，修改，這是因?yàn)轫樞虮黼S機(jī)訪問(wèn)的特點(diǎn)造成的。

? ? ? ? 本章完，感謝大家的觀看。

????????文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-665510.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之——（手撕）順序表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！