前言：大家好😍，本文主要介紹了數據結構——順序表部分的內容
目錄
一、線性表的定義
二、線性表的基本操作
三.順序表
1.定義
2.?存儲結構
3.?特點
四 順序表操作
4.1初始化
4.2 插入
4.2.1頭插
4.2.2 尾插
4.2.3 按位置插
4.3 刪除
4.3.1 頭刪
4.3.2 尾刪
?4.3.3 按位置刪
4.3.4 按值刪
4.4 查找?
4.5 刪除值val出現的位置
4.6 其余操作
4.7 主函數測試
一、線性表的定義
線性表是具有相同數據類型的n個數據元素的有限序列，n為表長，當n=0時線性表時一個空表。用l命名線性表，表示為l=（a1，a2，? ，an）。
線性表除第一個元素之外，每個元素都有直接前驅，除最后一個元素之外每個元素都有直接后繼。
二、線性表的基本操作
Initlist（&L）：初始化表，構造一個空的線性表L，構造一個空的線性表，分配內存空間
Destroylist（&L）：銷毀。銷毀線性表并釋放線性表L所占用的內存空間
Insertlist（&L，i，e）：插入，在表L中第i個位置上插入指定元素e
Deletelist（&L，i，&e）：刪除，刪除表L中第i個位置上的元素，并用e返回刪除元素的值
LocateElem（L，e）：按值查找，在表L中查找具有給定關鍵字e值的元素
? ?GetElem（L，i）：按位查找，獲取表L中第i個位置的元素的值
Length（L)：求表長，返回線性表L的長度，即L中數據元素的個數
Printlist（L）：輸出，輸出線性表所有元素值
Empty（L）：判空，若L為空，返回true，否則返回false
對參數的修改結果需要引用&
三.順序表
1.定義
順序表是一種線性表的存儲實現方式。線性表是具有相同數據類型的元素構成的有限序列，順序表通過數組的形式將這些元素存儲在內存中，并通過下標索引來訪問和操作元素。
2.?存儲結構
順序表通常使用數組來實現，數組的每個位置存儲一個元素。例如，一個順序表可以表示為：
數組：[a0, a1, a2, ..., an-1]
其中，a0 是表頭元素，an-1 是表尾元素。
3.?特點
優點：
隨機訪問：可以通過下標索引快速訪問任意位置的元素，時間復雜度為 O(1)。
存儲密度高：由于沒有額外的指針存儲空間，順序表的存儲利用率較高。
操作簡單：基于數組的實現使得順序表的操作邏輯相對簡單。
缺點：
插入和刪除效率低：插入或刪除元素時，需要移動大量元素以保持順序表的連續性，時間復雜度為 O(n)。
存儲空間固定：順序表的存儲空間在初始化時需要預先分配，難以動態擴展。如果分配的空間不足，需要重新分配更大的空間并復制數據；如果分配過多，則會浪費空間。
內存碎片問題：頻繁的動態擴展和收縮可能導致內存碎片化。
四 順序表操作
點h文件中定義了一個順序表（SeqList）的結構體
#define INIT_SIZE 10 //初始化時malloc購買的格子數量
//可庫容的順序表的結構體設計
typedef int ELEM_TYPE;
typedef struct SeqList
{ELEM_TYPE* elem;//用來接收malloc返回的數組首地址int length;//存放有效值個數int listsize;//存放數組的總的格子數
}SeqList, * PSeqList;
作用：定義了一個宏
INIT_SIZE，表示順序表初始化時分配的內存大小（即初始容量）。值：
INIT_SIZE被設置為 10，表示初始化時會分配 10 個元素的空間。結構體名稱：
SeqList，表示順序表的結構體。指針類型別名：
PSeqList，表示指向SeqList的指針。
ELEM_TYPE*表示elem是一個指針，指向ELEM_TYPE類型的數據。ELEM_TYPE是一個類型別名
4.1初始化
void Init_SeqList(struct SeqList* psl)
{//0.安全處理 每一個函數都要寫的assert(nullptr != psl);if (nullptr == psl){exit(EXIT_FAILURE);}//1.對我們的 elem 用來去malloc 在堆區購買一塊連續的空間psl->elem = (ELEM_TYPE*)malloc(INIT_SIZE * sizeof(ELEM_TYPE));if (NULL == psl->elem){exit(EXIT_FAILURE);}//2.對我們的 length 初始化為0psl->length = 0;//3.對我們的 listsize 初始化為 INITSIZEpsl->listsize = INIT_SIZE;}
類型轉換：
malloc返回的是void*類型的指針，需要強制轉換為ELEM_TYPE*。安全檢查：如果
malloc分配失敗（返回NULL），程序會退出。
length：表示順序表中當前存儲的元素個數，初始值為 0。
listsize：表示順序表當前分配的總容量，初始值為INIT_SIZE。
psl->elem存儲了這塊內存的首地址。通過
psl->elem[i]可以訪問順序表中的第i個元素。存儲元素：
elem指向的內存空間被用來存儲順序表中的所有元素。例如，如果elem指向的內存空間大小為INIT_SIZE，則可以存儲INIT_SIZE個ELEM_TYPE類型的元素。
4.2 插入
4.2.1頭插
bool Insert_Seqlist_head(PSeqList psl, ELEM_TYPE val)
{//0.assert//0.5 判滿if (Is_Full(psl)){Increase(psl);}//此時，肯定有空閑格子//1.集體向后挪(尾巴先動)for (int i = psl->length - 1; i >= 0; i--){psl->elem[i + 1] = psl->elem[i];}//2.將val放入0號下標psl->elem[0] = val;//3.有效值個數+1psl->length++;return true;
}
邏輯：從順序表的尾部開始，逐個將元素向后移動一個位置。
psl->elem[i + 1] = psl->elem[i]：將第i個元素移動到第i + 1個位置。循環條件：從
psl->length - 1開始，直到i = 0，確保所有元素都向后移動。更新順序表的長度，反映新插入的元素。
函數返回
true，表示插入操作成功
psl->length表示順序表中當前存儲的有效元素的個數。例如：如果psl->length的值為 5，說明順序表中有 5 個有效元素。
psl->length - 1是對psl->length的值減去 1，如果psl->length為 5，那么最后一個有效元素的索引為5 - 1 = 4。常用于從順序表的最后一個有效元素開始，逐個向前遍歷所有元素
4.2.2 尾插
bool Insert_Seqlist_tail(PSeqList psl, ELEM_TYPE val)
{//0.assert//0.5 判滿if (Is_Full(psl)){Increase(psl);}//此時，肯定有空閑格子psl->elem[psl->length] = val;psl->length++;return true;
}4.2.3 按位置插
bool Insert_Seqlist_pos(PSeqList psl, ELEM_TYPE val, int pos)
{//默認pos==0 則認為是頭插//0.安全性處理 psl pos合法性判斷assert(nullptr != psl);assert(pos >= 0 && pos <= psl->length);//0.5 判滿if (Is_Full(psl)){Increase(psl);}//此時，肯定有空閑格子//1.將插入位置之后的元素，統一向后挪動，把插入位置給空出來for (int i = psl->length - 1; i >= pos; i--){psl->elem[i + 1] = psl->elem[i];}//2.插入psl->elem[pos] = val;//3.length++psl->length++;return true;
}通過
psl->elem[i]可以訪問順序表中的第i個元素。
4.3 刪除
4.3.1 頭刪
bool Del_Seqlist_head(SeqList* psl)
{//0.assert//0.5 判空if (Is_Empty(psl))return false;//1.除了第一個元素之外，統一向前挪動for (int i = 1; i <= psl->length - 1; i++){psl->elem[i - 1] = psl->elem[i];}//2.有效值個數-1psl->length--;return true;
}//1.除了第一個元素之外，統一向前挪動
?? ?for (int i = 1; i <= psl->length - 1; i++)
?? ?{
?? ??? ?psl->elem[i - 1] = psl->elem[i];
?? ?}?//1.集體向后挪(尾巴先動)
?? ?for (int i = psl->length - 1; i >= 0; i--)
?? ?{
?? ??? ?psl->elem[i + 1] = psl->elem[i];
?? ?}
4.3.2 尾刪
//尾刪
bool Del_Seqlist_tail(SeqList* psl)
{//0.assert//0.5 判空if (Is_Empty(psl))return false;psl->length--;return true;
}?4.3.3 按位置刪
bool Del_Seqlist_pos(SeqList* psl, int pos)
{//0.assert psl posassert(psl != NULL);assert(pos >= 0 && pos < psl->length);//0.5 判空isemptyif (Is_Empty(psl))return false;//1.將pos位置之后的有效值，統一向前覆蓋(頭先動)for (int i = pos + 1; i <= psl->length - 1; i++){psl->elem[i - 1] = psl->elem[i];}//2.有效值個數-1psl->length--;return true;
}4.3.4 按值刪
//按值刪(只刪除這個val值出現的第一次的位置)
bool Del_Seqlist_val(SeqList* psl, ELEM_TYPE val)
{//0.assert//0.5 isempty//1.通過調用查找函數，查找val值在順序表中的位置int index = Search_SeqList(psl, val);//2.若返回的位置下標為-1 返回假 若不等于-1，則此時怎么刪if (index == -1)return false;return Del_Seqlist_pos(psl, index);
}4.4 查找?
//4.查找數據是否已經存在(若存在，則只需要返回下標即可 找不到返回-1)
int Search_SeqList(PSeqList psl, ELEM_TYPE val)
{//0.assertfor (int i = 0; i < psl->length; i++){if (psl->elem[i] == val)return i;}return -1;
}4.5 刪除值val出現的位置
//刪除當前val值出現的所有位置(1)
bool Del_SeqList_All_Val1(struct SeqList* psl, ELEM_TYPE val)
{int count = 0;for (int i = 0; i < psl->length; i++){if (psl->elem[i] == val){count++;}}for (int i = 0; i < count; i++){int index = Search_SeqList(psl, val);Del_Seqlist_pos(psl, index);}return true;}?
//刪除當前val值出現的所有位置(2)
bool Del_SeqList_All_Val2(struct SeqList* psl, ELEM_TYPE val)
{int qianfangkongxiangezishu = 0;for (int i = 0; i < psl->length; i++){if (psl->elem[i] == val)qianfangkongxiangezishu++;elsepsl->elem[i - qianfangkongxiangezishu] = psl->elem[i];}psl->length = psl->length - qianfangkongxiangezishu;return true;
}4.6 其余操作
//5.判空
bool Is_Empty(PSeqList psl)
{return psl->length == 0;
}//6.判滿
bool Is_Full(PSeqList psl)
{return psl->length == psl->listsize;
}//7.擴容函數(1.5 2) 默認用2倍擴容
void Increase(PSeqList psl)
{ELEM_TYPE* tmp = (ELEM_TYPE*)realloc(psl->elem, psl->listsize * sizeof(ELEM_TYPE) * 2);if (tmp != nullptr){psl->elem = tmp;}}//8.清空 (不釋放已購買的內存)
void Clear(PSeqList psl)
{//malloc申請空間先不釋放，而是認為所有格子里都是無效值psl->length = 0;
}//9.銷毀 (需要釋放malloc購買的內存的)
void Destroy(PSeqList psl)
{free(psl->elem);psl->length = psl->listsize = 0;
}//打印
void Show(PSeqList psl)
{//assertfor (int i = 0; i < psl->length; i++){printf("%d ", psl->elem[i]);}printf("\n");}4.7 主函數測試
int main()
{struct SeqList sq;Init_SeqList(&sq);Insert_Seqlist_head(&sq, 100);Insert_Seqlist_head(&sq, 101);Insert_Seqlist_head(&sq, 102);Insert_Seqlist_tail(&sq, 200);Insert_Seqlist_tail(&sq, 201);Insert_Seqlist_tail(&sq, 202);Insert_Seqlist_tail(&sq, 2000);Insert_Seqlist_tail(&sq, 2010);Insert_Seqlist_tail(&sq, 2020);Insert_Seqlist_pos(&sq, 10000, 3);Show(&sq);Insert_Seqlist_head(&sq, 111);Insert_Seqlist_tail(&sq, 222);Show(&sq);//刪除Del_Seqlist_head(&sq);Del_Seqlist_tail(&sq);Show(&sq);Del_Seqlist_pos(&sq, 4);Show(&sq);Del_Seqlist_pos(&sq, 8);Show(&sq);Del_Seqlist_pos(&sq, 0);Show(&sq);Del_Seqlist_val(&sq, 201);Show(&sq);//Clear(&sq);//Show(&sq);//Destroy(&sq);//Show(&sq);//------------------------------------------------Insert_Seqlist_pos(&sq, 3, 2);Insert_Seqlist_pos(&sq, 3, 4);Insert_Seqlist_pos(&sq, 3, 6);Show(&sq);Del_SeqList_All_Val2(&sq, 3);Show(&sq);return 0;
}
