前言：
本章節將對順序表的概念進行介紹，著重講解動態順序表，對常用的介面函式進行一個個講解，并進行決議，順序表講解部分將從零實作順序表介面函式，遇到問題我會進行一步步地除錯說明，通過對本章的學習不僅能學會順序表，還能實戰練習下除錯的技能，除錯不僅僅是幫助我們分析程式找到錯誤的，也可以讓我們去觀察和理解程式，除錯才是硬技能！寫一點點測一點點，不要寫完了再來測，這樣我們就可以很輕松的找出問題，
🔗 C語言教學專欄：《維生素C語言》
🔗 除錯的學習：第八章 - 實用除錯技巧
一、線性表的概念
【百度百科】線性表是最基本、最簡單、也是最常用的一種資料結構，線性表（linear list）是資料結構的一種，一個線性表是n個具有相同特性的資料元素的有限序列，
線性表中資料元素之間的關系是一對一的關系，即除了第一個和最后一個資料元素之外，其它資料元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部，比如，回圈鏈表邏輯層次上也是一種線性表（存盤層次上屬于鏈式存盤，但是把最后一個資料元素的尾指標指向了首位結點），
📚 概念：線性表（Linear list）是n個具有相同特性的資料元素的有限序列，線性表是一種在實際中廣泛使用的資料結構，常見的線性表有：順序表、鏈表、堆疊、佇列、字串等……
線性表在邏輯上是線性結構，呈現出一條線性，他們在邏輯上是挨著挨著的，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，
二、順序表
0x00 順序表的概念
【百度百科】順序表是在計算機記憶體中以陣列的形式保存的線性表，線性表的順序存盤是指用一組地址連續的存盤單元依次存盤線性表中的各個元素、使得線性表中在邏輯結構上相鄰的資料元素存盤在相鄰的物理存盤單元中，即通過資料元素物理存盤的相鄰關系來反映資料元素之間邏輯上的相鄰關系，采用順序存盤結構的線性表通常稱為順序表，順序表是將表中的結點依次存放在計算機記憶體中一組地址連續的存盤單元中，
📚 概念：順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，順序表一般可以分為靜態順序表和動態順序表：
靜態順序表：使用定長陣列存盤元素
動態順序表：使用動態開辟的陣列存盤
? 順序表的本質是什么？
🔑 順序表的本質就是陣列，但是在陣列的基礎上它還要求陣列是從頭開始存，并且是連續存盤的，不能跳躍間隔，換言之，順序表既然叫順序表，那么資料一定必須是挨著挨著存的，
0x01 靜態順序表
💬 使用定長陣列存盤元素：
#define N 8
typedef int SLDataType
typedef struct SeqList {
SLDataType array[N]; //定長陣列
size_t size; //有效資料的個數
} SeqList;
📚 靜態順序表的特點：如果滿了就不讓插入，
💭 靜態順序表的缺點：是給多少合適呢？這個往往難以斟酌，N給小了不夠用，N給大了又浪費空間，
0x02 動態順序表
💬 使用動態開辟的陣列存盤元素：
typedef int SLDataType
typedef struct SeqList {
SLDataType* array; //指向動態開辟的陣列
size_t size; //有效資料的個數
size_t capacity; //容量空間的大小
} SeqList;
三、介面實作
0x00 Q&A
? 為什么使用動態順序表？
🔑 靜態順序表只適用于確定知道需要存多少資料的場景，如果靜態順序表的定長陣列導致N定大了，就會造成空間浪費，如果N定小了又不夠用，所以現實中基本都是使用動態順序表，可以根據需要動態地分配空間大小，
? 什么是介面函式？
🔑 介面函式是在資料進行操作時進行呼叫的函式，通過呼叫資料結構的介面幫助你完成一系列操作，
0x00 基本增刪查改介面
/* 介面函式 */
void SeqListInit(SL* psl); //初始化
void SeqListDestory(SL* psl); //銷毀
void SeqListCheckCapacity(SL* psl); //檢查是否需要增容
void SeqListPushBack(SL* psl, SLDataType x); //尾插
void SeqListPrint(SL* psl); //列印
void SeqListPushFront(SL* psl, SLDataType x); //頭插
void SeqListPopBack(SL* psl); //尾刪
void SeqListPopFront(SL* psl); //頭刪
int SeqListFind(SL* psl, SLDataType x); //查找
int SeqListInsert(SL* psl, int pos, SLDataType x); //指定位置插入
int SeqListEarse(SL* psl, int pos); //指定位置洗掉0x01順序表初始化（SeqListInit）
📜 為了養成模塊化好習慣，我們盡量把代碼分開來寫，首先打開 VS2017，在解決方案資源管理器中的 "頭檔案" 檔案夾中創建 SeqList.h 用來存放頭檔案，在 "源檔案" 檔案夾中創建 SeqList.c 用來實作函式，Test.c 用來測驗我們的順序表：
💬 SeqList.h：
#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef int SLDataType;
/* 動態順序表 */
typedef struct SeqList {
SLDataType* array;
int size; //有效資料個數
int capacity; //陣列實際能存資料的空間容量是多大
}SL;
/* 介面函式 */
void SeqListInit(SL* psl);🔑 解讀：
為了避免同一個頭檔案被包含多次我們可以使用 #pragma once（在C語言系列預處理章節提到過，為了加深印象我在這里不得不再重申一下），
為了方便后續修改資料型別，我們可以使用 typedef 定義一個新的資料型別，這里我們把它取名為 SLDataType（順序表資料型別），
我們為了讓定義的結構體使用時更方便，我們同樣可以使用 typedef 將其定義為 SL（此時 SL = struct SeqList，后續在使用時可以更加方便），
最后宣告我們要實作的介面函式——順序表初始化函式并取名為 SeqListInit ，引數部分為 SL* psl（這里的 SL 就是之前被 typedef 定義的結構體 struct SeqList ），考慮到形參是只是實參的臨時拷貝的問題，為了能夠傷其內部，這里我們會使用址傳遞，所以，為了能夠接收 "這個" 地址，我們使用指標 psl 來接收，
💬 SeqList.c：
#include "SeqList.h"
/* 初始化 */
void SeqListInit(SL* psl) {
psl->array = NULL;
psl->size = psl->capacity = 0;
}🔑 解讀：
首先引入我們自己創建的頭檔案 #include "SeqList.h" ，我們就可以開始動手實作順序表初始化函式了，
首先通過 psl 指向 array，將陣列為空，因為是初始化，所以將有效資料個數和陣列時即能存資料的空間容量一并置為0，
💬 Test.c：
#include "SeqList.h"
void TestSeqList1() {
SL sl;
SeqListInit(&sl);
}
int main() {
TestSeqList1();
return 0;
}🔑 解讀：測驗代碼部分，我們不在 main 函式內直接測驗而是通過函式來測驗，這樣的好處是可以方便我們選擇性的測驗一部分的代碼，
為了測驗，TestSeqList1 函式中首先創建一個結構體，這里取名為 sl ，隨后將 sl 址傳遞傳入 SeqListInit 函式中進行測驗，
我們運行代碼發現代碼可以成功運行，我們下面進入除錯來看一下 SeqListInit 函式是否起作用了，
🐞 除錯代碼：
至此，SeqListInit 函式就寫好了，
0x02 尾插（SeqListPushBack）
📚 說明：所謂的尾插，就是在后面進行插入，
💡 出現三種情況：
① 第一種情況是順序表壓根就沒有空間，
② 第二種情況就是我們創建的 capacity 空間滿了，
③ 第三種情況是空間足夠，直接插入資料即可，
💬 SeqList.h：
...
void SeqListPushBack(SL* psl, SLDataType x); //尾插🔑 解讀：SLDataType x 是要添加到順序表的元素，
💬 SeqList.c：
...
/* 尾插 */
void SeqListPushBack(SL* psl, SLDataType x) {
// 首先判斷有沒有空間，如果沒有空間或者空間不足，那么我們就擴容
if (psl->size == psl->capacity) {
// 如果容量是0（第一次）就賦4，如果不是0，就把容量翻一倍
int new_capacity = psl->capacity == 0 ? 4 : psl->capacity*2;
// 這里使用realloc，因為如果原空間為空，就等于malloc，調整為 new_capacity個SLDataType大小的空間
SLDataType* tmp_array = (SLDataType*)realloc(psl->array, new_capacity * sizeof(SLDataType));
// 檢測是否realloc成功
if (tmp_array == NULL) {
printf("realloc fail {擴容失敗}\n");
exit(-1);
}
// 更新它們的大小
psl->array = tmp_array;
psl->capacity = new_capacity;
}
//插入
psl->array[psl->size] = x;
psl->size++;
}🔑 解讀：
根據我們剛才分析的三種情況，首先我們需要判斷是空間是否足夠，判斷思路如下：如果 size == capacity（有效資料個數等于實際能存的最大空間容量），我們進行擴容操作，
如果空間不足，我們就創建一個變數 new_capacity 用來存放 "新容量" ，int new_capacity = psl->capacity 首先把 capacity 的值賦值給這個 "新容量" ，因為考慮到第一次使用 capacity 大小為0，翻倍會出問題（0乘以任何數都是0），這里巧妙地使用三目運算子：int new_capacity = psl->capacity == 0 ? 4 : psl->capacity*2 ， 如果 capacity 為 0 （第一次使用大小是0），就把4賦值給它；如果不為0，就把 capacity 的值翻一倍（x2），
? 這里為什么要x2（翻一倍）？
💡 隨便你，你想一次擴容多少就擴容多少，乘2只是一個比較折中的擴容容量方案，
此時，new_capacity 中就存放了擴容的新容量（如果第一次使用為容量為4，容量擴容后為capacity的二倍），
確定好新的容量后，我們可以對陣列動刀子了，為了防止翻車，我們先創建一個臨時陣列來擴容，這里要進行動態記憶體開辟，我們選擇使用 realloc 而不是 malloc 函式，因為 realloc 可以調整并且如果是第一次用自帶 malloc 的效果：
（摘自MSDN）
下面我們來看是如何擴容的：
🔗 如果還是比較懵，建議詳細復習： 《維生素C語言》第十三章 - 動態記憶體管理
這里我們還加了一段判斷，如果你動態記憶體管理學的比較好這里就不難理解：
如果沒有問題，就可以進行賦值操作了，將 new_capacity 交給 psl->capacity，將 tmp_array 交給 psl->array ：
擴容成功后就可以插入了，插入相對來說就很很簡單了，
🔺 當然，如果一開始空間足夠就不需要擴容，就可以直接跳到這里：
💬 Test.c：
#include "SeqList.h"
void TestSeqList1() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
}
int main() {
TestSeqList1();
return 0;
}🔑 解讀：我們來測驗下 SeqListPushBack 尾插功能是否實作成功了，我們之前定義的 SLDataType 是 int 型，所以我們傳入數字進行測驗，
🐞 除錯：
至此，SeqListPushBack 函式就寫好了，
0x03 順序表列印（SeqListPrint）
📚 順序表列印就是列印順序表內資料，我們可以利用回圈解決，
💬 SeqList.h：
···
void SeqListPrint(SL* psl); //列印🔑 解讀：因為是單純的列印，所以只需要把順序表傳過去就行，
💬 SeqList.c：
/* 列印 */
void SeqListPrint(SL* psl) {
int i = 0;
for (i = 0; i < psl->size; i++) {
printf("%d ", psl->array[i]);
}
printf("\n");
}🔑 解讀：遍歷整個順序表，利用 for 回圈就可以輕松解決，把他們都列印出來就可以了，
💬 Test.c：
void TestSeqList1() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl);
}🚩 運行結果如下：
0x04 銷毀（SeqListDestroy）
📚 因為是動態開辟的，所以如果空間不用我們就需要銷毀掉，如果不銷毀會存在記憶體泄漏的風險，所以與之對應的我們寫一個銷毀的介面函式，
💬 SeqList.h：
...
void SeqListDestory(SL* psl); //銷毀💬 SeqList.c：
/* 銷毀 */
void SeqListDestory(SL* psl) {
//首先把空間還給作業系統
free(psl->array);
psl->array = NULL; //置空防止空指標
psl->capacity = psl->size = 0; //空間置0
}🔑 解讀：首先使用 free 函式把動態開辟的記憶體空間釋放掉，因為 free 之后那塊開辟的記憶體空間已經不在了，為了防止野指標，我們還需要手動把它置為空指標，最后再把 capacity 和 size 全部設為0，做到空著手來，空著手去，銷毀部分就實作好了，
💬 Test.c：
void TestSeqList1() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl);
SeqListDestory(&sl);
}0x05 尾刪（SeqListPopBack）
📚 如果我們想把第一個資料洗掉，最簡單的思路是把要尾刪的地方置為 0，然后再把 size-- 即可實作，這就是尾刪：
💬 SeqList.h：
void SeqListPopBack(SL* psl); //尾刪💬 SeqList.c：
/* 尾刪 */
void SeqListPopBack(SL* psl) {
psl->array[psl->size - 1] = 0; //因為是下標，所以size-1才能對的上
psl->size--; //實際有效個數-1
}🔑 解讀：首先 psl->array[psl -> size - 1] 這里 -1 ，是因為下標的原因，減1才可以對的上，這里把末尾的元素設為了0，此時再 size-- 讓實際有效個數減1，
💬 Test.c：我們來洗掉兩個資料測驗一下
void TestSeqList1() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}🚩 運行結果：
🤔 不知道你有沒有發現，其實我們只需要 psl -> size-- 就可以了…… 找到尾部的目標然后把他置為0其實沒有意義，因為 size 一減，貨一拉，就什么痕跡都沒有了，是 size 標識了我們存入了多少個有效資料，比如有5個資料，size-- 后就只有前4個資料有意義了，所以，尾刪我們只需要 size-- ，就可以達到目的：
/* 尾刪 */
void SeqListPopBack(SL* psl) {
// psl->array[psl->size - 1] = 0;
psl->size--; //實際有效個數-1
}
? 尾刪就這么簡單？
當然不是，我們還需要考慮一些情況的發生，如果我們一直刪，刪到沒有資料可以刪了，是不是會出現問題呢？我們試著刪完5個資料后繼續刪，然后再插入輸入列印看看：
void TestSeqList1() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPrint(&sl); //列印
SeqListPushBack(&sl, 10);
SeqListPushBack(&sl, 20);
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}🚩 運行結果如下：
（吐槽：這時候一列印，就爆炸了，以為寫的很完美的尾插，一直以為它是不會翻車的，就，就，爆炸了，碎成了片片，我同情它甚至超過了同情我自己，）
🐞 不慌，我們來除錯看看！
💡 解決方案：添加 SeqListPopBack 限制條件
方式一：如果沒有資料了，使呼叫 SeqListPopBack 沒效果（儒雅隨和的方式）
💬 SeqList.c：
/* 尾刪 */
void SeqListPopBack(SL* psl) {
if (psl->size > 0) {
// psl->array[psl->size - 1] = 0;
psl->size--; //實際有效個數-1
}
}
方式二：使用斷言，直接不允許你做類似這樣的動作，你在呼叫這個介面之前你必須確定它是有資料的，如果沒有資料就不能調了，調了就給你報錯，
💬 SeqList.h：使用斷言需引入 assert.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
···💬 SeqList.c：
/* 尾刪 */
void SeqListPopBack(SL* psl) {
//if (psl->size > 0) {
// // psl->array[psl->size - 1] = 0;
// psl->size--; //實際有效個數-1
//}
assert(psl->size > 0);
psl->size--;
}
🔺 至于選擇儒雅隨和的方式還是暴力解決的方式，就看你自己喜好了，
0x06 頭插（SeqListPushFront）和檢查是否需要增容（SeqListCheckCapacity）
📚 順序表要求資料是連續存盤的，且必須是從頭開始存盤，所以，對于順序表而言如果要實作頭插，就需要把資料往后挪動，不能從前往后挪，如果從前往后挪就挪就會把后面的資料覆寫掉，
💬 SeqList.h：
void SeqListPushFront(SL* psl, SLDataType x); //頭插
💬 SeqList.c：
/* 頭插 */
void SeqListPushFront(SL* psl, SLDataType x) {
// 挪動資料
int end = psl->size - 1; // 因為指向的是資料的下標，所以要 -1
while (end >= 0) {
psl->array[end + 1] = psl->array[end];
end--; //讓end指向下一個要移的資料
}
// 此時第一個位置已經被騰出來了，可以插入了
psl->array[0] = x;
psl->size++;
}
🔑 解讀：首先創建一個 end 變數用來指向要移動的資料，因為指向的是資料的下標，所以是 size 要減 1 ，隨后進入 while 回圈，如果 end >= 0 說明還沒有移動完，就會進入回圈，回圈體內利用下標，進行向后移動操作，移動結束后再 end-- ，進行下一個資料的向后移動，挪動資料成功后，就可以插入了，此時順序表第一個位置就被騰出來了，就可以在下標0位置插入欲插入的資料 x 了，最后記得 size++ ，
💬 Test.c：測驗頭插
我們之前用的 TestSeqList1 測驗函式里東西太多了很亂，現在我們再創建一個 TestSeqList2 函式來繼續測驗，現在就能體現出不在 main 函式內直接測驗而是通過函式來測驗的好處了，我們可以選擇性地測驗一部分代碼，互相之間不干擾，
void TestSeqList2() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPushFront(&sl, -1);
SeqListPushFront(&sl, -2);
SeqListPushFront(&sl, -3);
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}
int main() {
// TestSeqList1();
TestSeqList2();
return 0;
}🚩 運行結果如下：（先插入了12345，又在12345前面頭插了 -1、-2、-3）
? 我們是不是少了點啥？
💡 我們還需要檢查是否需要擴容，和尾插一樣，
📚 我們之前在完成 SeqListPushBack 尾插的時候就已經寫好了，我們不妨把它抽取出來寫成一個函式，方便以后多次呼叫：
💬 SeqList.c：檢查是否需要增容函式
/* 檢查是否需要擴容 */
void SeqListCheckCapacity(SL* psl) {
// 首先判斷有沒有空間，如果沒有空間或者空間不足，那么我們就擴容
if (psl->size == psl->capacity) {
// 如果容量是0（第一次）就賦4，如果不是0，就把容量翻一倍
int new_capacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
// 這里使用realloc，因為如果原空間為空，就等于malloc，調整為 new_capacity個SLDataType大小的空間
SLDataType* tmp_array = (SLDataType*)realloc(psl->array, new_capacity * sizeof(SLDataType));
// 檢測是否realloc成功
if (tmp_array == NULL) {
printf("realloc fail {擴容失敗}\n");
exit(-1);
}
// 更新它們的大小
psl->array = tmp_array;
psl->capacity = new_capacity;
}
}🔑 解讀：我們把之前寫在 SeqListPushBack 中的檢查增容的代碼直接復制粘貼過來就可以了，這樣一來，我們需要檢查是否需要增容時直接呼叫 SeqListCheckCapacity 函式就可以了！
💬 SeqList.c：更新下尾插函式
/* 尾插 */
void SeqListPushBack(SL* psl, SLDataType x) {
//檢查增容
SeqListCheckCapacity(psl);
//插入
psl->array[psl->size] = x;
psl->size++;
}💬 SeqList.c：更新下頭插函式
/* 頭插 */
void SeqListPushFront(SL* psl, SLDataType x) {
//檢查增容
SeqListCheckCapacity(psl);
// 挪動資料
int end = psl->size - 1; // 因為指向的是資料的下標，所以要 -1
while (end >= 0) {
psl->array[end + 1] = psl->array[end];
end--; //讓end指向下一個要移的資料
}
// 此時第一個位置已經被騰出來了，可以插入了
psl->array[0] = x;
psl->size++;
}
📌 如果不擴容，繼續往下添加會造成的后果：【不感興趣可跳過】
💬 Test.c：把尾插函式內的 SeqListCheckCapacity(psl); 注釋掉
void TestSeqList2() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPushFront(&sl, -1);
SeqListPushFront(&sl, -2);
SeqListPushFront(&sl, -3);
SeqListPushFront(&sl, -4); //繼續添加
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}
0x07 頭刪（SeqListPopFront）
📚 如果我們想把第一個資料洗掉，用尾刪的方法直接把 size-- 顯然是沒有用的了，因為順序表資料是從頭開始存且有順序的， size-- 無效的也只是最后一個資料，所以要想實作頭刪，我們不得不把資料先往前挪動，然后再 --size ，
💬 SeqList.h：
···
void SeqListPopFront(SL* psl); //頭刪💬 SeqList.c：
/* 頭刪 */
void SeqListPopFront(SL* psl) {
assert(psl->size > 0);
//挪動資料
int begin = 1;
while (begin < psl->size) {
psl->array[begin - 1] = psl->array[begin];
begin++;
}
//int begin = 0;
//while (begin < psl->size - 1) {
// psl->array[begin] = psl->array[begin + 1];
// begin++;
//}
psl->size--; //實際有效個數-1
}🔑 解讀：首先斷言順序表有資料，這個前面講過了這里就不再贅述了，然后開始挪動資料，創建一個 begin 變數并賦個 1，然后進入回圈，只要 size 大于 begin 就會進入回圈，每次進入回圈后將下標 begin -1 上的資料賦給下標 begin 上的資料，這樣就達到了右向左移動的目的，最后 begin++ 移動下一個（如果滿足條件的話），移動完畢后，第一個資料就被第二個資料覆寫掉了，而第二個資料被第三個資料覆寫掉了……最后多出來的一塊我們再用 size-- 解決掉，實際容量減1 ，此時，就實作了頭刪，
💬 Test.c：測驗代碼
void TestSeqList2() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPushFront(&sl, -1);
SeqListPushFront(&sl, -2);
SeqListPushFront(&sl, -3);
SeqListPushFront(&sl, -4);
SeqListPrint(&sl); //列印
SeqListPopFront(&sl);
SeqListPopFront(&sl);
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}🚩 運行結果如下：
0x08 查找位置（SeqListFind）
📚 查找順序表中某值的位置，如果找到了就回傳該值的下標，沒有找到我們就回傳 -1 ，
💬 SeqList.h：
···
int SeqListFind(SL* psl, SLDataType x); //查找💬 SeqList.c：查找
/* 查找 */
int SeqListFind(SL* psl, SLDataType x) {
int i = 0;
for (i = 0; i < psl->size; i++) {
if (psl->array[i] == x) {
return i;
}
}
// 沒找到
return -1;
}🔑 解讀：首先遍歷整個順序表，如果 psl->array[i] == x 就回傳 i 接，沒找到就回傳 -1，這里我們用的方法就是簡單粗暴的 O(N) Find 暴力求解，當然你還可以試著用二分查找做，排序一下，寫一個二分查找的介面，
💬 Test.c：
void TestSeqList3() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
int ret = SeqListFind(&sl, 3);
if (ret != -1)
printf("找到了，下標為%d\n", ret);
else
printf("沒找到！\n");
SeqListDestory(&sl); //銷毀
}
int main() {
// TestSeqList1();
// TestSeqList2();
TestSeqList3();
return 0;
}🚩 運行結果如下
0x09 在指定的下標位置插入（SeqListInsert）
📚 順序表要求資料從第一個開始放并且資料是連續存盤的，所以我們就要注意下指定指定的下標位置 pos 的位置了！有些位置并不可以，所以我們需要進行一些檢查，
💬 SeqList.h：
int SeqListInsert(SL* psl, int pos, SLDataType x); //指定位置插入💬 SeqList.c：
/* 指定位置插入 */
int SeqListInsert(SL* psl, int pos, SLDataType x) {
//if (pos > psl->size || pos < 0) {
// printf("pos invalid {pos非法}\n");
// return;
//}
assert(pos >= 0 && pos <= psl->size);
//檢查增容
SeqListCheckCapacity(psl);
int end = psl->size - 1;
while (end >= pos) {
psl->array[end + 1] = psl->array[end];
end--;
}
//插入
psl->array[pos] = x;
psl->size++;
}🔑 解讀：首先添加 pos 位置的限定條件，可以根據自己的喜好選擇是儒雅隨和的處理方式，還是暴力處理方式，這里我的選擇是簡單粗暴地使用斷言解決，限定 pos >= 0 并且 pos <= psl->size 從而保證 pos 合法，然后，因為是插入所以免不了要檢查增容，直接呼叫之前寫好的檢查增容的函式即可，檢查完后就可以開始移動了，和頭插差不多，我們創建一個變數 end 記錄最后一個的下標（psl->size-1），并通過它來指向要移動的資料，最后進入 while 回圈，以 end >= pos 作為條件，移動完后，x 的位置就騰出來了，再把 x 插入進去，最后再 size++，就完成了，
💬 Test.c：
void TestSeqList3() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListInsert(&sl, 2, 30);
SeqListPrint(&sl); //列印
int pos = SeqListFind(&sl, 4);
if (pos != -1) {
SeqListInsert(&sl, pos, 40);
}
SeqListPrint(&sl); //列印
SeqListInsert(&sl, 0, -10);
SeqListPrint(&sl); //列印
SeqListInsert(&sl, 8, 80);
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}
int main() {
// TestSeqList1();
// TestSeqList2();
TestSeqList3();
return 0;
}
🔑 解讀：這里為了防止有問題，我們不妨多測測驗，
🚩 運行結果如下：
? 頭插函式和尾插函式的修改：
我們都把功能這么強的 SeqListInsert 寫出來了，我們之前寫的頭插和尾插介面函式是不是可以直接復用下 SeqListInsert ？
💬 SeqList.c：尾插復用 SeqListInsert
/* 尾插 */
void SeqListPushBack(SL* psl, SLDataType x) {
SeqListInsert(psl, psl->size, x);
}💬 SeqList.c：頭插復用 SeqListInsert
/* 頭插 */
void SeqListPushFront(SL* psl, SLDataType x) {
SeqListInsert(psl, 0, x);
}💬 Test.c：測驗下有沒有問題，先尾插12345，再頭插12345
void TestSeqList4() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPushFront(&sl, 1);
SeqListPushFront(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
SeqListPushFront(&sl, 5);
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}
int main() {
// TestSeqList1();
// TestSeqList2();
// TestSeqList3();
TestSeqList4();
return 0;
}🚩 運行結果如下：
🔺 我們把 Insert 寫好了，就可以直接復用到前面的寫的尾插和頭插了，其實只要寫好 SeqListInsert 任意位置插入，頭尾就都能控制了，
0x10 洗掉指定位置的資料（SeqListErase）
📚 洗掉指定位置的資料，我們仍然要限制 pos 的位置，限制條件部分和 SeqListInsert 不同的是，因為 psl->size 這個位置沒有效資料，所以洗掉的位置不能是 psl->size！
💬 SeqList.h：
···
int SeqListEarse(SL* psl, int pos); //指定位置洗掉💬 SeqList.c：
/* 指定位置洗掉 */
int SeqListEarse(SL* psl, int pos) {
assert(pos >= 0 && pos < psl->size);
int begin = pos + 1;
while (begin < psl->size) {
psl->array[begin - 1] = psl->array[begin];
begin++;
}
psl->size--;
}
💬 Test.c：測驗下代碼
void TestSeqList4() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPushFront(&sl, 1);
SeqListPushFront(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
SeqListPushFront(&sl, 5);
SeqListPrint(&sl); //列印
SeqListEarse(&sl, 2);
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}
int main() {
// TestSeqList1();
// TestSeqList2();
// TestSeqList3();
TestSeqList4();
return 0;
}🚩 運行結果如下：
? 對應的，和上面一樣，頭刪尾刪都可以復用 SeqListEarse 了
💬 SeqList.c：頭刪復用 SeqListEarse
/* 頭刪 */
void SeqListPopFront(SL* psl) {
SeqListEarse(psl, 0);
}💬 SeqList.c：尾刪復用 SeqListEarse
/* 尾刪 */
void SeqListPopBack(SL* psl) {
/*
//if (psl->size > 0) {
// psl->array[psl->size - 1] = 0;
// psl->size--; //實際有效個數-1
//}
assert(psl->size > 0);
psl->size--;
*/
SeqListEarse(psl, psl->size - 1);
}💬 Test.c：測驗下代碼
void TestSeqList4() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPushFront(&sl, 1);
SeqListPushFront(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
SeqListPushFront(&sl, 5);
SeqListPrint(&sl); //列印
SeqListEarse(&sl, 2);
SeqListPrint(&sl); //列印
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopFront(&sl);
SeqListPopFront(&sl);
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}
int main() {
// TestSeqList1();
// TestSeqList2();
// TestSeqList3();
TestSeqList4();
return 0;
}
🚩 運行結果如下：
四、完整代碼
💬 SeqList.h：頭檔案以及函式申明
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
/* 動態順序表 */
typedef struct SeqList {
SLDataType* array;
int size; //有效資料個數
int capacity; //陣列實際能存資料的空間容量是多大
}SL;
/* 介面函式 */
void SeqListInit(SL* psl); //初始化
void SeqListDestory(SL* psl); //銷毀
void SeqListCheckCapacity(SL* psl); //檢查是否需要增容
void SeqListPushBack(SL* psl, SLDataType x); //尾插
void SeqListPrint(SL* psl); //列印
void SeqListPushFront(SL* psl, SLDataType x); //頭插
void SeqListPopBack(SL* psl); //尾刪
void SeqListPopFront(SL* psl); //頭刪
int SeqListFind(SL* psl, SLDataType x); //查找
int SeqListInsert(SL* psl, int pos, SLDataType x); //指定位置插入
int SeqListEarse(SL* psl, int pos); //指定位置洗掉💬 SeqList.c：介面實作
#include "SeqList.h"
/* 初始化 */
void SeqListInit(SL* psl) {
psl->array = NULL;
psl->size = psl->capacity = 0;
}
/* 銷毀 */
void SeqListDestory(SL* psl) {
//首先把空間還給作業系統
free(psl->array);
psl->array = NULL; //置空防止空指標
psl->capacity = psl->size = 0; //空間置0
}
/* 列印 */
void SeqListPrint(SL* psl) {
int i = 0;
for (i = 0; i < psl->size; i++) {
printf("%d ", psl->array[i]);
}
printf("\n");
}
/* 檢查是否需要擴容 */
void SeqListCheckCapacity(SL* psl) {
if (psl->size == psl->capacity) {
// 如果容量是0（第一次）就賦4，如果不是0，就把容量翻一倍
int new_capacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
// 這里使用realloc，因為如果原空間為空，就等于malloc，調整為 new_capacity個SLDataType大小的空間
SLDataType* tmp_array = (SLDataType*)realloc(psl->array, new_capacity * sizeof(SLDataType));
// 檢測是否realloc成功
if (tmp_array == NULL) {
printf("realloc fail {擴容失敗}\n");
exit(-1);
}
// 更新它們的大小
psl->array = tmp_array;
psl->capacity = new_capacity;
}
}
/* 尾插 */
void SeqListPushBack(SL* psl, SLDataType x) {
/*
//檢查增容
SeqListCheckCapacity(psl);
//插入
psl->array[psl->size] = x;
psl->size++;
*/
SeqListInsert(psl, psl->size, x);
}
/* 尾刪 */
void SeqListPopBack(SL* psl) {
/*
//if (psl->size > 0) {
// psl->array[psl->size - 1] = 0;
// psl->size--; //實際有效個數-1
//}
assert(psl->size > 0);
psl->size--;
*/
SeqListEarse(psl, psl->size - 1);
}
/* 頭插 */
void SeqListPushFront(SL* psl, SLDataType x) {
/*
//檢查增容
SeqListCheckCapacity(psl);
// 挪動資料
int end = psl->size - 1; // 因為指向的是資料的下標，所以要 -1
while (end >= 0) {
psl->array[end + 1] = psl->array[end];
end--; //讓end指向下一個要移的資料
}
// 此時第一個位置已經被騰出來了，可以插入了
psl->array[0] = x;
psl->size++;
*/
SeqListInsert(psl, 0, x);
}
/* 頭刪 */
void SeqListPopFront(SL* psl) {
assert(psl->size > 0);
/*
// 挪動資料
int begin = 1;
while (begin < psl->size) {
psl->array[begin - 1] = psl->array[begin];
begin++;
}
psl->size--; //實際有效個數-1
*/
SeqListEarse(psl, 0);
}
/* 查找 */
int SeqListFind(SL* psl, SLDataType x) {
int i = 0;
for (i = 0; i < psl->size; i++) {
if (psl->array[i] == x) {
return i;
}
}
// 沒找到
return -1;
}
/* 指定位置插入 */
int SeqListInsert(SL* psl, int pos, SLDataType x) {
//if (pos > psl->size || pos < 0) {
// printf("pos invalid {pos非法}\n");
// return;
//}
assert(pos >= 0 && pos <= psl->size);
//檢查增容
SeqListCheckCapacity(psl);
int end = psl->size - 1;
while (end >= pos) {
psl->array[end + 1] = psl->array[end];
end--;
}
//插入
psl->array[pos] = x;
psl->size++;
}
/* 指定位置洗掉 */
int SeqListEarse(SL* psl, int pos) {
assert(pos >= 0 && pos < psl->size);
int begin = pos + 1;
while (begin < psl->size) {
psl->array[begin - 1] = psl->array[begin];
begin++;
}
psl->size--;
}
💬 Test.c：測驗用例
#include "SeqList.h"
void TestSeqList1() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPrint(&sl); //列印
SeqListPushBack(&sl, 10);
SeqListPushBack(&sl, 20);
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}
void TestSeqList2() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPushFront(&sl, -1);
SeqListPushFront(&sl, -2);
SeqListPushFront(&sl, -3);
SeqListPushFront(&sl, -4);
SeqListPrint(&sl); //列印
SeqListPopFront(&sl);
SeqListPopFront(&sl);
SeqListPrint(&sl); //列印
SeqListDestory(&sl); //銷毀
}
void TestSeqList3() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
int ret = SeqListFind(&sl, 3);
if (ret != -1)
printf("找到了，下標為%d\n", ret);
//else
printf("沒找到！\n");
SeqListInsert(&sl, 2, 30);
SeqListPrint(&sl); //列印
int pos = SeqListFind(&sl, 4);
if (pos != -1) {
SeqListInsert(&sl, pos, 40);
}
SeqListPrint(&sl); //列印
SeqListInsert(&sl, 0, -10);
SeqListPrint(&sl); //列印
SeqListInsert(&sl, 8, 80);
SeqListPrint(&sl); //列印
SeqListDestory(&sl);
}
void TestSeqList4() {
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl); //列印
SeqListPushFront(&sl, 1);
SeqListPushFront(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
SeqListPushFront(&sl, 5);
SeqListPrint(&sl); //列印
SeqListEarse(&sl, 2);
SeqListPrint(&sl); //列印
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopFront(&sl);
SeqListPopFront(&sl);
SeqListPrint(&sl); //列印
SeqListDestory(&sl);
}
int main() {
// TestSeqList1();
// TestSeqList2();
// TestSeqList3();
// TestSeqList4();
return 0;
}參考資料
Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .
百度百科[EB/OL]. []. https://baike.baidu.com/.
位元科技. 資料結構v5[EB/OL]. 2021[21]. .
📌 作者：王亦優
📃 更新： 2021.10.16
? 勘誤： 無
📜 宣告： 由于作者水平有限，本文有錯誤和不準確之處在所難免，本人也很想知道這些錯誤，懇望讀者批評指正！
本章完，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/319727.html
標籤：其他
上一篇：【C語言學習記錄】初識C語言
下一篇：爭當后“浪”