---

• 💓 博客主頁：江池俊的博客
• ? 收錄專欄：數(shù)據(jù)結(jié)構(gòu)探索
• 👉專欄推薦：?C語言初階之路 ?C語言進(jìn)階之路
• 💻代碼倉庫：江池俊的代碼倉庫
• 🔥編譯環(huán)境：Visual Studio 2022
• 🎉歡迎大家點贊👍評論📝收藏?

---

---

🚀線性表

【維基百科】 線性表（英語：Linear List）是由n（n≥0）個數(shù)據(jù)元素（結(jié)點）a[0]，a[1]，a[2]…，a[n-1]組成的有限序列。

其中：

• 數(shù)據(jù)元素的個數(shù)n定義為表的長度 = “l(fā)ist”.length() （“l(fā)ist”.length() = 0（表里沒有一個元素）時稱為空表）
• 將非空的線性表（n>=1）記作：（a[0]，a[1]，a[2]，…，a[n-1]）
• 數(shù)據(jù)元素a[i]（0≤i≤n-1）只是個抽象符號，其具體含義在不同情況下可以不同

一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)元素稱為記錄，含有大量記錄的線性表又稱為文件。這種結(jié)構(gòu)具有下列特點：存在一個唯一的沒有前驅(qū)的（頭）數(shù)據(jù)元素；存在一個唯一的沒有后繼的（尾）數(shù)據(jù)元素；此外，每一個數(shù)據(jù)元素均有一個直接前驅(qū)和一個直接后繼數(shù)據(jù)元素。

線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列、字符串…

線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。

---

🚀順序表

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

【維基百科】 順序表是在計算機內(nèi)存中以數(shù)組的形式保存的線性表，是指用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系。

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

🎈. 靜態(tài)順序表：使用定長數(shù)組存儲元素。

🎈. 動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。

---

🚀接口實現(xiàn)

靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了，空間開多了浪費，開少了不夠用。

所以現(xiàn)實中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間大小，所以下面我們實現(xiàn)動態(tài)順序表。

這里的接口其實就是 接口函數(shù) ，這些 接口函數(shù) 提供了順序表的各種基本操作，允許我們對順序表進(jìn)行 增、刪、查、改 等操作。

📌有哪些接口呢

// 基本 增刪查改 接口 --- 命名風(fēng)格是跟著STL走的，方便后續(xù)學(xué)習(xí)STL
// 順序表初始化
void SeqListInit(SL* psl);
// 檢查空間，如果滿了，進(jìn)行增容 --> 擴容
void SLCheckCapacity(SL* psl);
// 順序表尾插
void SeqListPushBack(SL* psl, SLDataType x);
// 順序表頭插
void SeqListPushFront(SL* psl, SLDataType x);
// 順序表尾刪
void SeqListPopBack(SL* psl);
// 順序表頭刪
void SeqListPopFront(SL* psl);
// 順序表查找
int SeqListFind(SL* psl, SLDataType x);
//順序表的修改
void SeqListModify(SL* psl,int pos, SLDataType x);
// 順序表在pos位置插入x（可以實現(xiàn)頭插和尾插）
void SeqListInsert(SL* psl, int pos, SLDataType x);
// 順序表刪除pos位置的值（可以實現(xiàn)頭刪和尾刪）
void SeqListErase(SL* psl, int pos);
// 順序表打印
void SeqListPrint(SL* psl);
// 順序表銷毀
void SeqListDestroy(SL* psl);

接下來我將帶著大家一 一實現(xiàn)這些接口。

📌準(zhǔn)備工作

在寫順序表前，我們需要創(chuàng)建工程，這里為了讓大家養(yǎng)成模塊化的好習(xí)慣，我們盡量將代碼分成三個文件來寫。這里我打開的編譯器是 vs 2022，在資源管理器的 頭文件 中創(chuàng)建 SeqList.h 文件，此文件作用主要是為了存儲各種頭文件和接口函數(shù)的聲明以及順序表結(jié)構(gòu)體的創(chuàng)建；在源文件中創(chuàng)建 SeqList.c 文件用來實現(xiàn)接口函數(shù)，Test.c 文件用來測試順序表的各個接口。具體如下圖所示：

注意：

• 為了能夠在順序表中方便地存儲各種類型的數(shù)據(jù)，我們可以使用 typedef 將要存儲的數(shù)據(jù)類型重命名為 SLDataType ，這樣在定義順序表的數(shù)據(jù)類型時只需要使用 SLDataType 就行了，修改數(shù)據(jù)類型時只需要修改 typedef 后面跟著的這個數(shù)據(jù)類型，這樣就大大方便了對不同類型數(shù)據(jù)的存儲。
• 類似的，為了方便結(jié)構(gòu)體的定義和使用，我們也可以使用 typedef 將結(jié)構(gòu)體定義一個簡單的別名為 SL。

#pragma once#include<stdio.h>
#include<stdlib.h> // NULL、size_t
#include<assert.h>// 靜態(tài)的順序表:使用定長數(shù)組存儲元素。
// 特點：如果滿了就不讓插入
// 缺點：N給小了不夠用，給多了浪費，這個很難確定
//#define N 100
//typedef int SLDataType; // 給int取別名
//struct SeqList // 創(chuàng)建順序表
//{
//	SLDataType a[N]; // 定長數(shù)組
//	int size; // 存儲的有效數(shù)據(jù)的個數(shù)
//};// 動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。
//typedef double SLDatatype;
typedef int SLDataType; //重定義類型名稱，方便順序表對不同類型的數(shù)據(jù)的存儲和操作
typedef struct SeqList // 創(chuàng)建順序表
{SLDataType* a; //指向動態(tài)開辟的數(shù)組int size;       // 存儲的有效數(shù)據(jù)的個數(shù)int capacity;   // 容量空間大小
}SL; //將結(jié)構(gòu)體類型取別名為 SL

📌初始化

這里我們實現(xiàn)動態(tài)順序表，所以剛開始時我們可以假設(shè)給定順序表的大小為 4（即能存放4個元素），不夠就擴容，順序表中剛開始是沒有元素的。

//順序表初始化
void SeqListInit(SL* psl)
{//防止psl為空指針（即防止傳錯結(jié)構(gòu)體地址）assert(psl);psl->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);//判斷能否成功開辟空間if (psl->a == NULL){perror("malloc fail");//將系統(tǒng)錯誤信息輸出到屏幕return;}psl->capacity = 4;psl->size = 0;
}

📌擴容

在后續(xù)對順序表進(jìn)行操作過程中我們會插入數(shù)據(jù)，如果順序表空間不夠，我們就需要使用 realloc 函數(shù)進(jìn)行擴容。
這里newcapacity表示擴容后能存放的元素個數(shù)（即空間的容量），tmp表示的是擴容后的空間的地址，如果順序表的空間為空，就給定能存放4個元素的空間；如果空間不夠，就在原來空間的基礎(chǔ)上，增加 1 倍的空間（這樣也依然無法避免空間的部分浪費，所以就有了鏈表，后續(xù)文章我會為大家?guī)?#xff09;。

// 擴容 ---> 檢查空間，如果滿了，進(jìn)行增容
void SLCheckCapacity(SL* psl)
{if (psl->size == psl->capacity){//如果沒有空間或者空間不足，就擴容int newcapacity = (psl->capacity == 0 ? 4 : psl->capacity * 2);SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1); //退出程序}psl->a = tmp;psl->capacity = newcapacity;}
}

📌順序表打印

打印比較簡單，這里我們只需要依次遍歷每一個節(jié)點就行。

//打印
void SeqListPrint(SL* psl)
{//防止psl為空指針（即防止傳錯結(jié)構(gòu)體地址）assert(psl);//遍歷for (int i = 0; i < psl->size; i++){printf("%d ", psl->a[i]);}printf("\n");
}

📌順序表銷毀

因為是動態(tài)開辟的，所以如果空間不用我們就需要銷毀掉。如果不銷毀會存在內(nèi)存泄漏的風(fēng)險，所以這里我們使用free函數(shù)釋放開辟的動態(tài)空間，并把有效數(shù)據(jù)個數(shù)和容量空間都置為0。

//銷毀
void SeqListDestroy(SL* psl)
{assert(psl);free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}

📌尾插

尾插就是在最后一個元素的后面插入一個元素（即在size下標(biāo)位置處插入數(shù)據(jù)），但要注意的是當(dāng)capacity空間滿了就需要擴容，因此我們要調(diào)用SLCheckCapacity函數(shù)。

//尾插
void SeqListPushBack(SL* psl, SLDataType x)
{assert(psl);//psl->a[psl->size] = x;//psl->size++;SLCheckCapacity(psl); // 檢查擴容psl->a[psl->size++] = x;//復(fù)用指定pos下標(biāo)位置插入數(shù)據(jù)的函數(shù)//SeqListInsert(psl, psl->size, x);
}

📌尾刪

尾刪其實就是將順序表最后一個數(shù)據(jù)刪去，要實現(xiàn)這一操作其實只需要將有效數(shù)據(jù)個數(shù)減一就可以了（即size--），但是在尾刪之前要先判斷順序表中是否有元素，如果沒有元素就沒有必要刪了。

//尾刪
void SeqListPopBack(SL* psl)
{assert(psl);//溫柔的處理方式//if (psl->size > 0)//{//	psl->size--;//}//else//{//	printf("沒有數(shù)據(jù)能夠再刪了！\n");//		exit(-1); //退出程序//}//暴力的處理方式assert(psl->size > 0);//確保順序表中有數(shù)據(jù)psl->size--;//復(fù)用pos下標(biāo)位置刪除數(shù)據(jù)的函數(shù)//SeqListErase(psl, psl->size - 1);
}

📌頭插

頭插操作其實就是在順序表下表為 0 的位置插入數(shù)據(jù)，然后 size++，但是在此之前要判斷順序表容量空間是否已滿，所以要先調(diào)用 SLCheakCapacity 函數(shù)。

//頭插
void SeqListPushFront(SL* psl, SLDataType x)
{assert(psl);SLCheckCapacity(psl);//挪動數(shù)據(jù)int end = psl->size -1;while (end >= 0){psl->a[end + 1] = psl->a[end];end--;}psl->a[0] = x;psl->size++;//復(fù)用指定pos下標(biāo)位置插入數(shù)據(jù)的函數(shù)//SeqListInsert(psl, 0, x);
}

📌頭刪

頭刪的實現(xiàn)其實只需要將順序表開頭后面的數(shù)據(jù)依次往前挪動，然后將 size-- 就可以了，這里要從前往后挪，如果從后往前挪數(shù)據(jù)會被覆蓋。注意：這里與尾刪類似，在頭刪之前要先判斷順序表中是否有元素，如果沒有元素就沒有必要刪了。

//頭刪
void SeqListPopFront(SL* psl)
{assert(psl);assert(psl->size > 0);//有數(shù)據(jù)才能刪，沒數(shù)據(jù)就會報錯int begin = 1;while (begin < psl -> size){psl->a[begin - 1] = psl->a[begin];begin++;}psl->size--;//復(fù)用pos效標(biāo)位置刪除數(shù)據(jù)的函數(shù)//SeqListErase(psl, 0);
}

📌指定pos下標(biāo)位置插入數(shù)據(jù)

我們只需要將順序表中pos位置到最后的數(shù)據(jù)依次往后挪動（從后往前挪），然后將pos下標(biāo)位置的數(shù)據(jù)改為要插入的數(shù)據(jù)，最后 size++ 即可。但是我們依然要判斷是否滿容,所以在插入數(shù)據(jù)前要調(diào)用 SLCheakCapacity 函數(shù)。同時我們也要判斷pos位置是否合理，防止越界訪問。

//指定pos下標(biāo)位置插入數(shù)據(jù)
void SeqListInsert(SL* psl, int pos, SLDataType x)
{assert(psl);//if (pos > psl->size || pos < 0)//{//	printf("pos的下標(biāo)位置越界");//	return;//}//暴力的方式處理（pos下標(biāo)不能越界）assert(pos >= 0 && pos <= psl->size);//如果沒有空間或者空間不足，就擴容SLCheckCapacity(psl);//挪動數(shù)據(jù)int end = psl->size - 1;while (end >= pos){psl->a[end + 1] = psl->a[end];end--;}psl->a[pos] = x;psl->size++;
}

📌刪除pos位置的數(shù)據(jù)

與頭刪類似，我們只需要將pos位置后的數(shù)據(jù)依次往前挪動將pos位置處的數(shù)據(jù)覆蓋，然后再 size-- 就可以了。但是要判斷pos位置是否合理，防止越界訪問。

//刪除pos位置的數(shù)據(jù)（結(jié)合SeqListFind函數(shù)可以刪除指定的數(shù)據(jù)）
void SeqListErase(SL* psl, int pos)
{assert(psl);assert(pos >= 0 && pos < psl->size);//pos位置需要有數(shù)據(jù)//挪動數(shù)據(jù)int begin = pos + 1;while (begin < psl->size){psl->a[begin - 1] = psl->a[begin];begin++;}psl->size--;
}

📌查找

這個比較簡單，我們只需要遍歷一遍順序表，查找相應(yīng)數(shù)據(jù)，若找到，就返回下標(biāo)，若沒找到，就返回-1。

//查找，找到了返回下標(biāo)，沒找到返回-1
int SeqListFind(SL* psl, SLDataType x)
{assert(psl);for (int i = 0; i < psl->size; i++){if (psl->a[i] == x){return i;}}return -1;
}

📌修改pos位置的數(shù)據(jù)

通過pos下標(biāo)直接修改

//修改pos位置的數(shù)據(jù)
void SeqListModify(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos >= 0 && pos < psl->size);psl->a[pos] = x;
}

🚀源碼

🌴SeqList.h 文件

#pragma once#include<stdio.h>
#include<stdlib.h>//NULL、size_t
#include<assert.h>// 靜態(tài)的順序表:使用定長數(shù)組存儲元素。
// 特點：如果滿了就不讓插入
// 缺點：N給小了不夠用，給多了浪費，這個很難確定
//#define N 10000
//typedef int SLDatatype; // 給int取別名
//struct SeqList // 創(chuàng)建順序表
//{
//	SLDatatype a[N]; // 定長數(shù)組
//	int size; // 存儲的有效數(shù)據(jù)的個數(shù)
//};
//靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了，空間開多了浪
//費，開少了不夠用。所以現(xiàn)實中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間大小，所以下面我們實
//現(xiàn)動態(tài)順序表。// 動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。
//typedef double SLDatatype;
typedef int SLDataType; //重定義類型名稱，方便順序表對不同類型的數(shù)據(jù)的存儲和操作
typedef struct SeqList
{SLDataType* a; //指向動態(tài)開辟的數(shù)組int size;       // 存儲的有效數(shù)據(jù)的個數(shù)int capacity;   // 容量空間大小
}SL;// 基本 增刪查改 接口 --- 命名風(fēng)格是跟著STL走的，方便后續(xù)學(xué)習(xí)STL
// 順序表初始化
void SeqListInit(SL* psl);// 檢查空間，如果滿了，進(jìn)行增容
void SLCheckCapacity(SL* psl);// 順序表尾插
void SeqListPushBack(SL* psl, SLDataType x);
// 順序表尾刪
void SeqListPopBack(SL* psl);
// 順序表頭插
void SeqListPushFront(SL* psl, SLDataType x);
// 順序表頭刪
void SeqListPopFront(SL* psl);
// 順序表查找
int SeqListFind(SL* psl, SLDataType x);
// 順序表在pos位置插入x（可以實現(xiàn)頭插和尾插）
void SeqListInsert(SL* psl, int pos, SLDataType x);
// 順序表刪除pos位置的值（可以實現(xiàn)頭刪和尾刪）
void SeqListErase(SL* psl, int pos);// 順序表打印
void SeqListPrint(SL* psl);
// 順序表銷毀
void SeqListDestroy(SL* psl);//順序表的修改
void SeqListModify(SL* psl, int pos, SLDataType x);

🌴SeqList.c 文件

#include"SeqList.h"//void SeqListInit(SL* psl)
//{
//	psl->a = NULL;
//	psl->size = 0;
//	psl->capacity = 0;
//}//順序表初始化
void SeqListInit(SL* psl)
{//防止psl為空指針（即防止傳錯結(jié)構(gòu)體地址）assert(psl);psl->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);//判斷能否成功開辟空間if (psl->a == NULL){perror("malloc fail");//將系統(tǒng)錯誤信息輸出到屏幕return;}psl->capacity = 4;psl->size = 0;
}
//銷毀
void SeqListDestroy(SL* psl)
{assert(psl);free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}
//打印
void SeqListPrint(SL* psl)
{assert(psl);for (int i = 0; i < psl->size; i++){printf("%d ", psl->a[i]);}printf("\n");
}
// 檢查空間，如果滿了，進(jìn)行增容
void SLCheckCapacity(SL* psl)
{assert(psl);if (psl->size == psl->capacity){//如果沒有空間或者空間不足，就擴容int newcapacity = (psl->capacity == 0 ? 4 : psl->capacity * 2);SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);//退出程序}psl->a = tmp;psl->capacity = newcapacity;}
}
//尾插
void SeqListPushBack(SL* psl, SLDataType x)
{assert(psl);//psl->a[psl->size] = x;//psl->size++;SLCheckCapacity(psl);//檢查擴容psl->a[psl->size++] = x;//復(fù)用指定pos下標(biāo)位置插入數(shù)據(jù)的函數(shù)//SeqListInsert(psl, psl->size, x);
}
//尾刪
void SeqListPopBack(SL* psl)
{assert(psl);//溫柔的處理方式//if (psl->size > 0)//{//	psl->size--;//}//else//{//	printf("沒有數(shù)據(jù)能夠再刪了！\n");//		exit(-1);//}//暴力的處理方式assert(psl->size > 0);//確保順序表中有數(shù)據(jù)psl->size--;//復(fù)用pos下標(biāo)位置刪除數(shù)據(jù)的函數(shù)//SeqListErase(psl, psl->size - 1);
}
//頭插
void SeqListPushFront(SL* psl, SLDataType x)
{assert(psl);SLCheckCapacity(psl);//挪動數(shù)據(jù)int end = psl->size -1;while (end >= 0){psl->a[end + 1] = psl->a[end];end--;}psl->a[0] = x;psl->size++;//復(fù)用指定pos下標(biāo)位置插入數(shù)據(jù)的函數(shù)//SeqListInsert(psl, 0, x);
}
//頭刪
void SeqListPopFront(SL* psl)
{assert(psl);assert(psl->size > 0);//有數(shù)據(jù)才能刪，沒數(shù)據(jù)就會報錯int begin = 1;while (begin < psl -> size){psl->a[begin - 1] = psl->a[begin];begin++;}psl->size--;//復(fù)用pos效標(biāo)位置刪除數(shù)據(jù)的函數(shù)//SeqListErase(psl, 0);
}
//查找，找到了返回下標(biāo)，沒找到返回-1
int SeqListFind(SL* psl, SLDataType x)
{assert(psl);for (int i = 0; i < psl->size; i++){if (psl->a[i] == x){return i;}}return -1;
}
//指定pos下標(biāo)位置插入數(shù)據(jù)
void SeqListInsert(SL* psl, int pos, SLDataType x)
{assert(psl);//if (pos > psl->size || pos < 0)//{//	printf("pos的下標(biāo)位置越界");//	return;//}//暴力的方式處理（pos下標(biāo)不能越界）assert(pos >= 0 && pos <= psl->size);//如果沒有空間或者空間不足，就擴容SLCheckCapacity(psl);//挪動數(shù)據(jù)int end = psl->size - 1;while (end >= pos){psl->a[end + 1] = psl->a[end];end--;}psl->a[pos] = x;psl->size++;
}//刪除pos位置的數(shù)據(jù)（結(jié)合SeqListFind函數(shù)可以刪除指定的數(shù)據(jù)）
void SeqListErase(SL* psl, int pos)
{assert(psl);assert(pos >= 0 && pos < psl->size);//pos位置需要有數(shù)據(jù)//挪動數(shù)據(jù)int begin = pos + 1;while (begin < psl->size){psl->a[begin - 1] = psl->a[begin];begin++;}psl->size--;
}//修改pos位置的數(shù)據(jù)
void SeqListModify(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos >= 0 && pos < psl->size);psl->a[pos] = x;}

🌴Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"int main()
{SL s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPushBack(&s, 4);SeqListPushBack(&s, 5);SeqListPushBack(&s, 6);//尾插SeqListPopBack(&s);//尾刪SeqListPushFront(&s, 0);//頭插SeqListPopFront(&s);//頭刪SeqListInsert(&s, 2, 8);//指定pos下標(biāo)為2的位置插入數(shù)據(jù)8SeqListPrint(&s);//打印SeqListDestroy(&s);//銷毀return 0;
}

💨 今天的分享就到這里，如果覺得博主的文章還不錯的話， 請👍三連支持一下博主哦🤞