二、順序表

1、 順序表基本概念

定義：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，這種存儲(chǔ)結(jié)構(gòu)的線性表稱(chēng)為順序表。

特征：邏輯上相鄰的數(shù)據(jù)元素，物理次序也是相鄰的。

優(yōu)缺點(diǎn)：

①隨機(jī)訪問(wèn)：只要確定好了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取（數(shù)據(jù)讀寫(xiě)所需的時(shí)間與存儲(chǔ)位置無(wú)關(guān)）。在O(1)的時(shí)間內(nèi)找到第 i 個(gè)元素。代碼上以數(shù)組 (序號(hào)讀取地址) 的方式實(shí)現(xiàn)。

②存儲(chǔ)密度高：每個(gè)節(jié)點(diǎn)只存儲(chǔ)數(shù)據(jù)元素。

③靜態(tài)拓展容量不方便，動(dòng)態(tài)拓展容量易造成空間浪費(fèi)。

④插入、刪除數(shù)據(jù)不方便，需要移動(dòng)大量數(shù)據(jù)。

2、靜態(tài)順序表結(jié)構(gòu)體定義

#define N 100
typedef int SeqDataType;
typedef struct Seqlist
{
	SeqDataType a[N];//定值數(shù)組
	int size;//表示數(shù)組中存儲(chǔ)了多少個(gè)數(shù)據(jù)
}SeqList;

靜態(tài)特點(diǎn)：如果滿(mǎn)了就不讓插入
缺點(diǎn):給多少空間不確定 給小了不夠用，給大了浪費(fèi)
一般不推薦，在現(xiàn)實(shí)中運(yùn)用少，但適合初學(xué)者練習(xí)順序表的建立

3、動(dòng)態(tài)順序表結(jié)構(gòu)體定義

typedef int SeqDataType;
typedef struct SeqList
{
	SeqDataType* a;//指向動(dòng)態(tài)開(kāi)辟的數(shù)組指針
	int size;      // 有效數(shù)據(jù)的個(gè)數(shù)
	int capacity;  // 容量
}SeqList; 

動(dòng)態(tài)特點(diǎn)：將靜態(tài)的定值數(shù)組改為了可以接收動(dòng)態(tài)開(kāi)辟內(nèi)存地址的指針，且增加了一個(gè)變量capacity表示容量。
我們這里使用動(dòng)態(tài)順序表結(jié)構(gòu)體來(lái)定義接口函數(shù)

三、順序表接口實(shí)現(xiàn)

1、頭文件的結(jié)構(gòu)體建立和接口函數(shù)聲明

typedef int SeqDataType;
typedef struct SeqList
{
	SeqDataType* a;
	int size;      
	int capacity;
}SeqList;
void SeqListInit(SeqList* pq);//初始化
void SeqListCheckCapacity(SeqList* ps);//檢查擴(kuò)容
void SeqListPushBack(SeqList* pq, SeqDataType x);//尾插
void SeqListPushFront(SeqList* pq, SeqDataType x);//頭插
void SeqListPopBack(SeqList* pq);//尾刪
void SeqListPopFront(SeqList* pq);//頭刪
int SeqListFind(SeqList* pq, SeqDataType x);//查找
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);//任意位置插入
void SeqListErase(SeqList* pq, int pos);//任意位置刪除
void SeqListModify(SeqList* pq, int pos, SeqDataType x);//修改
void SeqListPrint(SeqList* pq);//打印
void SeqListDestory(SeqList* pq);//銷(xiāo)毀

2、接口函數(shù)代碼實(shí)現(xiàn)

A、初始化接口函數(shù)

void SeqListInit(SeqList* pq)
{
	assert(pq);
	pq->a = NULL;
	pq->size = pq->capacity = 0;
}

初始化即將指針置空，長(zhǎng)度容量初始化為0。

B、檢查擴(kuò)容接口函數(shù)

void SeqCheckCapacity(SeqList* pq)
{
	// 滿(mǎn)了，需要增容
	if (pq->size == pq->capacity)
	{
		int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
		SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType)*newcapacity);
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

在這里作者用了一個(gè)三目操作符判定空間如果為空則增加4個(gè)整形空間，若滿(mǎn)則以2倍增容，這樣不容易造成空間浪費(fèi)，當(dāng)然，隨著數(shù)組長(zhǎng)度越來(lái)越大，你會(huì)發(fā)現(xiàn)浪費(fèi)依然存在且越來(lái)越大，實(shí)際上這也就是我們?cè)谇懊嫣岬降木€性表的缺點(diǎn)，這是不可避免的，在后面我們學(xué)到的鏈表就很好的彌補(bǔ)了這個(gè)缺陷。

C、尾部插入接口函數(shù)

void SeqListPushBack(SeqList* pq, SeqDataType x)
{
	assert(pq);

	SeqCheckCapacity(pq);

	pq->a[pq->size] = x;
	pq->size++;
}

尾插在順序表中是最好實(shí)現(xiàn)的，直接增加一位插入即可。

D、頭部插入接口函數(shù)

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
	assert(pq);
	SeqCheckCapacity(pq);

	int end = pq->size - 1;
	while (end >= 0)
	{
		pq->a[end + 1] = pq->a[end];
		--end;
	}

	pq->a[0] = x;
	pq->size++;
}

在順序表中，頭插相對(duì)于尾插來(lái)說(shuō)就不是那么簡(jiǎn)單了，這里主要是讓順序表整體向后移動(dòng)，再在頭部插入數(shù)據(jù)。

E、尾部刪除接口函數(shù)

void SeqListPopBack(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);

	--pq->size;
}

尾刪直接進(jìn)行–size操作即可，沒(méi)必要對(duì)最后一個(gè)元素進(jìn)行置空，再進(jìn)行尾插時(shí)同樣會(huì)覆蓋

F、頭部刪除接口函數(shù)

void SeqListPopFront(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);//防止只剩一個(gè)元素，造成越界訪問(wèn)

	int begin = 0;
	while (begin < pq->size-1)
	{
		pq->a[begin] = pq->a[begin+1];
		++begin;
	}

	pq->size--;
}

頭刪的實(shí)現(xiàn)就是將除第一位之后的元素整體向前挪動(dòng)覆蓋。

在這里做一個(gè)小小的總結(jié)，我們會(huì)發(fā)現(xiàn)不論是頭插還是頭刪，無(wú)論在時(shí)間上，還是代碼量上都比尾插和尾刪浪費(fèi)更多，動(dòng)一位影響整體，在鏈表中，同樣也很好的彌補(bǔ)了這一點(diǎn)。

G、查找接口函數(shù)

int SeqListFind(SeqList* pq, SeqDataType x)
{
	assert(pq);

	for (int i = 0; i < pq->size; ++i)
	{
		if (pq->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

查找的實(shí)現(xiàn)即為遍歷順序表，比較查找是否有我們想要的元素
沒(méi)有：返回-1
有：返回該元素的下標(biāo)（如果有多個(gè)符合要查找的元素，則返回優(yōu)先找到的元素的下標(biāo)）

H、任意位置插入接口函數(shù)

void SeqListInsert(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos <= pq->size);//斷言是否在有效范圍內(nèi)

	SeqCheckCapacity(pq);

	int end = pq->size - 1;
	while (end >= pos)
	{
		pq->a[end + 1] = pq->a[end];
		--end;
	}

	pq->a[pos] = x;
	pq->size++;
}

任意位置插入代碼實(shí)現(xiàn)，即為將從順序表中要插入的位置開(kāi)始，往后原有的元素整體往后移動(dòng)一位，騰出空位來(lái)插入要插入的元素；此函數(shù)可以很好的替代前面的頭插和尾插。
頭插

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
	SeqListInsert(pq, 0, x);
}

尾插

void SeqListPushBack(SeqList* pq, SeqDataType x)
{
	SeqListInsert(pq, pq->size, x);
}

I、任意位置刪除接口函數(shù)

void SeqListErase(SeqList* pq, int pos)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	int begin = pos;
	while (begin <= pq->size-1)
	{
		pq->a[begin] = pq->a[begin+1];
		++begin;
	}

	pq->size--;
}

任意位置刪除代碼實(shí)現(xiàn)，和任意位置插入函數(shù)同理，即為將從順序表中要?jiǎng)h除的位置開(kāi)始，往后原有的元素整體向前移動(dòng)一位，直接覆蓋要?jiǎng)h除的元素；此函數(shù)可以很好的替代前面的頭刪和尾刪。
頭刪

void SeqListPopFront(SeqList* pq)
{
	SeqListErase(pq, 0);
}

尾刪

void SeqListPopBack(SeqList* pq)
{
	SeqListErase(pq, pq->size - 1);
}

J、修改接口函數(shù)

void SeqListModify(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);//斷言是否在有效范圍內(nèi)

	pq->a[pos] = x;
}

對(duì)某個(gè)元素的修改，可以對(duì)其所在下標(biāo)進(jìn)行訪問(wèn)再進(jìn)行覆蓋修改

K、打印順序表接口函數(shù)

void SeqListPrint(SeqList* pq)
{
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
		printf("%d ", pq->a[i]);
	}
	printf("\n");
}

遍歷順序表逐個(gè)打印即可，與打印數(shù)組類(lèi)似。

L、銷(xiāo)毀順序表接口函數(shù)

void SeqListDestory(SeqList* pq)
{
	assert(pq);

	free(pq->a);
	pq->a = NULL;
	pq->capacity = pq->size = 0;
}

與初始化類(lèi)似，但在這我們需要先f(wàn)ree空間（對(duì)應(yīng)relloc），再進(jìn)行初始化操作，即可銷(xiāo)毀順序表。

四、總結(jié)

總的來(lái)說(shuō)，結(jié)合頭刪尾刪的小總結(jié)，包括中間插入和刪除操作，我們不難看出，這些操作效率都很低，且在增容內(nèi)存分配上，存在空間浪費(fèi)，有一定缺陷，但在元素的訪問(wèn)上，可以做到隨機(jī)訪問(wèn)，通過(guò)下標(biāo)直接訪問(wèn)元素，這是順序表的優(yōu)點(diǎn)。

這就是數(shù)據(jù)結(jié)構(gòu)線性表之順序表的主要知識(shí)點(diǎn)，感謝你的閱讀，讓我有更新的動(dòng)力，下一期我們講鏈表中的單鏈表！??！

制作不易，如有不正之處，敬請(qǐng)指出，感謝來(lái)訪，一鍵三連，蟹蟹你呦?。?！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-411211.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門(mén)（C語(yǔ)言版）線性表中順序表介紹及接口實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！