前言

本文主要介紹順序表的定義和常見(jiàn)靜態(tài)順序表的用法。

一、線性表定義

線性表（line list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn)的線性表有：順序表、鏈表、棧、隊(duì)列、字符串。
線性表在邏輯上是線性結(jié)構(gòu)，也就是說(shuō)是連續(xù)的一條直線。但在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)

二、順序表實(shí)現(xiàn)

1概念及結(jié)構(gòu)

順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。

順序表一般可表示為：

1.靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)。
2.動(dòng)態(tài)順序表：使用動(dòng)態(tài)開(kāi)辟的數(shù)組存儲(chǔ)。

我們以簡(jiǎn)單的靜態(tài)順序表進(jìn)行引例（與動(dòng)態(tài)順序表接口函數(shù)思想是一樣的）
代碼如下（示例）：

#define N 10//這里定義宏是為了方便將來(lái)如果需要更改空間的大小，而代碼中用到的10過(guò)于多要更改多次，宏定義直接改N大小即可
typedef int SQDataType;//這里順序表10個(gè)空間都是int型，如果將來(lái)要改變類(lèi)型，可以在這里把int改為所需類(lèi)型
struct SeqList//單個(gè)數(shù)據(jù)直接定義變量，多個(gè)數(shù)據(jù)定義結(jié)構(gòu)體
{
	SQDataType a[N];//順序表有10個(gè)空間可進(jìn)行存儲(chǔ)
	int size;//順序表存了幾個(gè)數(shù)據(jù)（有10個(gè)空間不一定就存10個(gè)數(shù)據(jù)）
};

ps:順序表的一些要求：
1.連續(xù)的物理空間存儲(chǔ)-用的是數(shù)組
2.數(shù)據(jù)必須是從頭開(kāi)始，依次存儲(chǔ)

2靜態(tài)順序表

2.1實(shí)現(xiàn)順序表接口，第一步要對(duì)順序表進(jìn)行初始化

代碼如下（示例）：

#include<stdio.h>
#include<string.h>//memset函數(shù)頭文件
//增刪查改等接口函數(shù)
void SeqListInit(struct SeqList *ps)
{
	memset(ps->a, 0, sizeof(SQDataType)*N);//memset是一個(gè)初始化函數(shù)
	//sl.a表示按字節(jié)初始化
	//0表示初始化為0
	//sizeof(SQDataType)表示數(shù)組內(nèi)每個(gè)元素大小(之前定義了SQDataType=int)，N表示數(shù)組內(nèi)共有N個(gè)元素，兩者相乘是數(shù)組大小
	ps->size = 0;
}
void TestSeqList1()
{
	struct SeqList sl;//sl是實(shí)參，上面的ps是形參,為了實(shí)參和形參可以相互影響，這里用的是傳址調(diào)用
	SeqListInit(&sl);
}
int main()
{
	TestSeqList1();
	return 0;
}
//ps:如果這里你覺(jué)得寫(xiě)struct SeqList sl煩，你可以這樣改進(jìn)代碼（這里和2.1代碼對(duì)應(yīng)）
//typedef struct SeqList//單個(gè)數(shù)據(jù)直接定義變量，多個(gè)數(shù)據(jù)定義結(jié)構(gòu)體
//{
//	SQDataType a[N];//順序表有10個(gè)空間可進(jìn)行存儲(chǔ)
//	int size;//順序表存了幾個(gè)數(shù)據(jù)（有10個(gè)空間不一定就存10個(gè)數(shù)據(jù)）
//}SL;
//這樣結(jié)構(gòu)體類(lèi)型就可以直接寫(xiě)成SL

2.2對(duì)順序表的增刪查改的接口函數(shù)（以尾插為例）

void SeqListPushBack(struct SeqList *ps, SQDataType x)//尾插
{
	if (ps->size >= N)
	{
		printf("SeqList is full");//防止你尾插太多已經(jīng)大于了順序表最大容量
		return;
	}
	ps->a[ps->size] = x;
	ps->size++;//存儲(chǔ)的數(shù)據(jù)多了一個(gè)，size加1個(gè)
}

乍一看代碼比較晦澀難懂，我們用圖來(lái)理解一下這個(gè)代碼：

（圖片來(lái)自比特就業(yè)課）

圖示順序表有7個(gè)空間，我們放了5個(gè)數(shù)據(jù)，現(xiàn)在要在尾部插入一個(gè)數(shù)據(jù)，該數(shù)據(jù)下標(biāo)是5，而ps->size=5（結(jié)構(gòu)體指針相關(guān)知識(shí)見(jiàn)筆者結(jié)構(gòu)體文章）所以a[5]也就是a[ps->size]恰好是尾部后一個(gè)元素，這里的5改成其他數(shù)也是同樣的道理。

ps->a[ps->size]=x，也就是對(duì)尾部后一個(gè)元素賦值。

ps->size++是表示順序表存儲(chǔ)的數(shù)據(jù)又多了一個(gè)（原本認(rèn)定順序表存儲(chǔ)5個(gè)數(shù)據(jù)，你現(xiàn)在添加了一個(gè)，認(rèn)定存儲(chǔ)幾個(gè)數(shù)據(jù)也要再加1個(gè)）
而你在尾插的過(guò)程中，可能插入數(shù)據(jù)多了，甚至多于數(shù)組最大容量，這肯定會(huì)有問(wèn)題，所以我們用了一個(gè)if進(jìn)行判斷一下。

到這里大家可能就會(huì)發(fā)現(xiàn)了，在使用靜態(tài)鏈表有兩個(gè)不方便的地方：
1.數(shù)組給的空間小了，可能不夠用
2.數(shù)組給的空間大了，可能浪費(fèi)空間

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

3.1動(dòng)態(tài)順序表初始化

代碼如下（示例）：

typedef int SQDataType;
struct SeqList
{
	SQDataType*a;
	int size;//有效數(shù)據(jù)個(gè)數(shù)
	int capacity;//容量
};
//由于沒(méi)有數(shù)組a了，所以順序表初始化也要改一下
void SeqListInit(struct SeqList *ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

（圖片來(lái)自比特就業(yè)課）

3.2動(dòng)態(tài)順序表-尾插

代碼如下（示例）：

void SeqListPushBack(struct SeqList *ps, SQDataType x)
{	
	if (ps->size == ps->capacity)//原先空間滿(mǎn)了，無(wú)法進(jìn)行尾插了，需要進(jìn)行擴(kuò)容（擴(kuò)容一般擴(kuò)2倍）
	{
		int newcapacity = ps->capacity==0?4:ps->capacity*2;//這個(gè)4是可以換其他數(shù)的
		//這里是防止原來(lái)的容量是0，擴(kuò)容后的倍數(shù)仍然是0
		SQDataType*tmp = (SQDataType*)realloc(ps->a, newcapacity* sizeof(SQDataType));
		if (tmp == NULL)//防止擴(kuò)容失敗，也就是沒(méi)有剩余空間供它使用了
		{
			printf("realloc is fail\n");
			exit(-1);//退出運(yùn)行
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
	ps->a[ps->size] = x;
	ps->size++;//存儲(chǔ)的數(shù)據(jù)多了一個(gè)，size加1個(gè)
}

我們?cè)跀U(kuò)容時(shí)，是用一個(gè)擴(kuò)容一個(gè)嗎？這樣太浪費(fèi)時(shí)間，一般是擴(kuò)容所需要的空間的兩倍，realloc函數(shù)可對(duì)指針指向的空間進(jìn)行擴(kuò)大或縮小，感興趣的同學(xué)自行了解，這里不作深究。

3.3動(dòng)態(tài)順序表-頭插

了解過(guò)尾插，這里講頭插也很容易理解，就是在最前面插入一個(gè)內(nèi)容，如何操作呢？把已有的內(nèi)容全部向后移動(dòng)一位，然后最前面會(huì)空出一個(gè)空間，然后你放入內(nèi)容
代碼如下（示例）：

void SeqListPushFront(struct SeqList *ps, SQDataType x)
{
//原先空間滿(mǎn)了需要進(jìn)行擴(kuò)容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity==0?4:ps->capacity*2;
		//這里是防止原來(lái)的容量是0，擴(kuò)容后的倍數(shù)仍然是0
		SQDataType*tmp = (SQDataType*)realloc(ps->a, newcapacity* sizeof(SQDataType));
		if (tmp == NULL)//防止擴(kuò)容失敗，也就是沒(méi)有剩余空間供它使用了
		{
			printf("realloc is fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
	int end = ps->size - 1;//確定最后一個(gè)內(nèi)容下標(biāo)
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];//以此把原先的內(nèi)容往后挪一位
		--end;
	}
	ps->a[0] = x;//把需要插入的內(nèi)容放在最開(kāi)始的空間
	ps->size++;
}

這里需要注意的是，頭插和尾插都面臨一個(gè)空間已經(jīng)滿(mǎn)的情況，如果滿(mǎn)了都需要擴(kuò)容，這個(gè)不要忘記。如果你嫌麻煩每次都要寫(xiě)擴(kuò)容，你可以寫(xiě)一個(gè)擴(kuò)容函數(shù)，用的時(shí)候調(diào)用一下即可。

3.4動(dòng)態(tài)順序表-尾刪

代碼如下（示例）：

void SeqListPopBack(struct SeqList *ps)
{
	assert(ps->size > 0);
	//要進(jìn)行刪除，首先要有東西可刪
	//這里會(huì)進(jìn)行斷言，如果沒(méi)有東西刪會(huì)報(bào)錯(cuò)
	ps->size--;
}

這里為什么size- -即可完成尾部數(shù)據(jù)的刪除？解釋是這樣的，size- -后，電腦認(rèn)為的有效數(shù)據(jù)就少了一個(gè)，不管你那個(gè)數(shù)據(jù)還在不在，電腦已經(jīng)認(rèn)為它不再是一個(gè)所需的數(shù)據(jù)了，使用順序表時(shí)不會(huì)對(duì)無(wú)效數(shù)據(jù)進(jìn)行考慮。

3.5動(dòng)態(tài)順序表-頭刪

頭刪也就是把最前面的數(shù)據(jù)刪除，其他數(shù)據(jù)下標(biāo)依次減1即可
代碼如下（示例）：

void SeqListPopFront(struct SeqList *ps)
{
	assert(ps->size > 0);
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

3.6動(dòng)態(tài)順序表-任意位置插入數(shù)據(jù)

我們以下面這個(gè)順序表舉例

我們要在1和2中間插一個(gè)數(shù)據(jù)怎么辦？0和1不變，2和3分別向后移
但是考慮到其他的順序表，假設(shè)它原來(lái)的數(shù)據(jù)已經(jīng)占滿(mǎn)了所有空間，你再插是不是有可能空間不夠，還有一點(diǎn)，雖說(shuō)是任意位置插入數(shù)據(jù)，你能不能在順序表尾部插入？非法訪問(wèn)了屬于是。考慮上面幾點(diǎn)，我們有下面的代碼。

void SeqListInsert(struct SeqList *ps, int pos, SQDataType x)
//pos表示插入位置的下標(biāo)
{
	assert(pos < ps->size);//防止在尾部插入構(gòu)成非法訪問(wèn)
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

3.7動(dòng)態(tài)順序表-任意位置刪除數(shù)據(jù)

我們?nèi)砸韵旅娴膱D舉例，要將2刪除怎么辦？把3往前挪一位即可。

void SeqListErase(struct SeqList *ps, int pos)
{
	assert(pos < ps->size);
	int start =pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}

結(jié)束

ps:上述的所有刪除都是刪除數(shù)據(jù)，空間是不刪除的。

以上就是C語(yǔ)言編程簡(jiǎn)單卻重要的數(shù)據(jù)結(jié)構(gòu)順序表全面講解的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表的資料請(qǐng)關(guān)注服務(wù)器之家其它相關(guān)文章！

原文鏈接：https://blog.csdn.net/m0_57180439/article/details/120261201