前言

本文主要介紹順序表的定義和常見靜態順序表的用法。

一、線性表定義

線性表（line list）是n個具有相同特性的數據元素的有限序列。線性表是一種在實際中廣泛使用的數據結構，常見的線性表有：順序表、鏈表、棧、隊列、字符串。
線性表在邏輯上是線性結構，也就是說是連續的一條直線。但在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲

二、順序表實現

1概念及結構

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。

順序表一般可表示為：

1.靜態順序表：使用定長數組存儲。
2.動態順序表：使用動態開辟的數組存儲。

我們以簡單的靜態順序表進行引例（與動態順序表接口函數思想是一樣的）
代碼如下（示例）：

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

ps:順序表的一些要求：
1.連續的物理空間存儲-用的是數組
2.數據必須是從頭開始，依次存儲

2靜態順序表

2.1實現順序表接口，第一步要對順序表進行初始化

代碼如下（示例）：

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

2.2對順序表的增刪查改的接口函數（以尾插為例）

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

乍一看代碼比較晦澀難懂，我們用圖來理解一下這個代碼：

（圖片來自比特就業課）

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

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

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

到這里大家可能就會發現了，在使用靜態鏈表有兩個不方便的地方：
1.數組給的空間小了，可能不夠用
2.數組給的空間大了，可能浪費空間

3動態順序表

3.1動態順序表初始化

代碼如下（示例）：

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

（圖片來自比特就業課）

3.2動態順序表-尾插

代碼如下（示例）：

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

我們在擴容時，是用一個擴容一個嗎？這樣太浪費時間，一般是擴容所需要的空間的兩倍，realloc函數可對指針指向的空間進行擴大或縮小，感興趣的同學自行了解，這里不作深究。

3.3動態順序表-頭插

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

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

這里需要注意的是，頭插和尾插都面臨一個空間已經滿的情況，如果滿了都需要擴容，這個不要忘記。如果你嫌麻煩每次都要寫擴容，你可以寫一個擴容函數，用的時候調用一下即可。

3.4動態順序表-尾刪

代碼如下（示例）：

void SeqListPopBack(struct SeqList *ps)
{
	assert(ps->size > 0);
	//要進行刪除，首先要有東西可刪
	//這里會進行斷言，如果沒有東西刪會報錯
	ps->size--;
}

這里為什么size- -即可完成尾部數據的刪除？解釋是這樣的，size- -后，電腦認為的有效數據就少了一個，不管你那個數據還在不在，電腦已經認為它不再是一個所需的數據了，使用順序表時不會對無效數據進行考慮。

3.5動態順序表-頭刪

頭刪也就是把最前面的數據刪除，其他數據下標依次減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動態順序表-任意位置插入數據

我們以下面這個順序表舉例

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

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

3.7動態順序表-任意位置刪除數據

我們仍以下面的圖舉例，要將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--;
}

結束

ps:上述的所有刪除都是刪除數據，空間是不刪除的。

以上就是C語言編程簡單卻重要的數據結構順序表全面講解的詳細內容，更多關于C語言數據結構順序表的資料請關注服務器之家其它相關文章！

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