一、順序表的概念和結(jié)構(gòu)

1、順序表的概念：

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

---

?2、順序表的結(jié)構(gòu)：

（1）靜態(tài)順序表：使用定長數(shù)組存儲元素

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

// 順序表的靜態(tài)存儲
#define N 10
typedef int SLDataType;typedef struct SeqList
{SLDataType array[N];// 定長數(shù)組size_t size;// 有效數(shù)據(jù)個數(shù)
}SeqList;

---

?（2）動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲元素

優(yōu)點：動態(tài)順序表可以根據(jù)需要動態(tài)的分配空間大小。

// 順序表的動態(tài)存儲
typedef int SLDataType; //類型重命名，后續(xù)要存儲其它類型時方便更改typedef struct SeqList
{SLDataType* a;// 指向動態(tài)開辟的數(shù)組size_t size;// 有效數(shù)據(jù)個數(shù)（當(dāng)前順序表中已存放的數(shù)據(jù)個數(shù)）size_t capacity;// 容量大小（順序表總共能夠存放的數(shù)據(jù)個數(shù)）
}SeqList;

注：size_t 數(shù)據(jù)類型表示 C 中任何對象所能達到的最大長度，它是無符號整數(shù)。?

---

?二、動態(tài)順序表的接口實現(xiàn)

1、創(chuàng)建文件

1. test.c（主函數(shù)、測試順序表各個接口功能）
2. SeqList.c（動態(tài)順序表接口函數(shù)的實現(xiàn)）
3. SeqList.h（動態(tài)順序表的類型定義、接口函數(shù)聲明、引用的頭文件）

??

---

?2、SeqList.h 頭文件代碼

// SeqList.h
#pragma once // 防止頭文件被二次引用#include<stdio.h>
#include<assert.h> // assert
#include<stdlib.h> // realloctypedef int SLDataType; // 后續(xù)要存儲其它類型時方便直接更改// 順序表的動態(tài)存儲
typedef struct SeqList
{SLDataType* a; // 指向動態(tài)開辟的數(shù)組size_t size ; // 有效數(shù)據(jù)個數(shù)size_t capicity ; // 容量空間的大小
}SeqList;// 基本增刪查改接口
// 順序表初始化
void SeqListInit(SeqList* psl);
// 順序表銷毀
void SeqListDestory(SeqList* psl);
// 檢查空間，如果滿了，進行增容
void CheckCapacity(SeqList* psl);
// 順序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 順序表尾刪
void SeqListPopBack(SeqList* psl);
// 順序表頭插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 順序表頭刪
void SeqListPopFront(SeqList* psl);
// 順序表打印
void SeqListPrint(SeqList* psl);
// 順序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 順序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 順序表刪除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 查看順序表中的有效數(shù)據(jù)個數(shù)?
size_t SeqListSize(const SeqList* psl);
// 修改指定下標(biāo)位置的數(shù)據(jù)
void SeqListAt(SeqList* psl, size_t pos, SLDataType x);

---

?三、在?SeqList.c 中實現(xiàn)各個接口函數(shù)

1、初始化順序表

// 初始化順序表
void SeqListInit(SeqList* psl)
{assert(psl); // 斷言 -- 防止傳進來的指針為空psl->a = NULL; // 初始化順序表為空psl->size = 0; // 初始數(shù)據(jù)個數(shù)為0psl->capacity = 0; // 初始空間容量為0
}

---

2、順序表銷毀

// 銷毀順序表
void SeqListDestroy(SeqList* psl)
{assert(psl); // 斷言 -- 防止傳進來的指針為空free(psl->a); // 釋放動態(tài)開辟的空間psl->a = NULL; // 置空psl->size = 0; // 數(shù)據(jù)個數(shù)置為0psl->capacity = 0; // 空間容量大小置為0
}

---

3、檢查空間，如果滿了，進行增容?

// 檢查順序表容量是否滿了，好進行增容
void CheckCapity(SeqList* psl)
{if (psl->size == psl->capacity) // 檢查容量，滿了則增容{// 原來容量為0，擴容為4；不為0，擴容為原來的2倍size_t newcapacity = psl->capacity == 0 ? 4 : 2 * (psl->capacity);psl->a = (SeqList*)realloc(psl->a, sizeof(SLDateType) * newcapacity); // 擴容psl->capacity = newcapacity; // 更新容量}
}

為什么不采取插一個數(shù)據(jù)，增容一個空間的方式呢？

因為這樣做很麻煩，代價也很大。一般情況下，為了避免頻繁的增容，當(dāng)空間滿了之后，我們不會選擇一個一個的去增，而是一次增容 2 倍，當(dāng)然也不會一次增容太大，比如 3 倍 4 倍，這樣空間可能會造成浪費，所以 2 倍是一個折中的選擇。

---

?注：realloc 在開辟動態(tài)內(nèi)存空間時，如果傳給它的是一個空指針，那么他就會開辟一個新的內(nèi)存空間，用法類似malloc。

---

4、順序表尾插

// 順序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x) // O(1)
{// 不需要斷言 空指針也符合條件// 第一種寫法：/* CheckCapacity(psl); // 檢查順序表容量是否已滿psl->a[psl->size] = x; // 尾插數(shù)據(jù)psl->size++; // 有效數(shù)據(jù)個數(shù)+1 */// 第二種寫法：SeqListInsert(psl, psl->size, x);
}

---

5、順序表尾刪

// 順序表尾刪
void SeqListPopBack(SeqList* psl) // O(1)
{assert(psl); // 斷言// 第一種寫法：/* assert(psl->size > 0); // 尾刪 -- 順序表不能為空//psl->a[psl->size - 1] = 0; // 不知道SLDataType是什么類型的數(shù)據(jù)，不能冒然的直接賦值為0psl->size--; // 有效數(shù)據(jù)個數(shù)-1 */// 第二種寫法：SeqListErase(psl, psl->size - 1);
}

關(guān)于在程序中檢查錯誤的方式：

（1）溫柔檢查法： 如果出現(xiàn)錯誤，程序就不再繼續(xù)執(zhí)行。因為一般情況下，程序運行成功就返回0，則運行失敗就返回-1。
（2）暴力檢查法（推薦）：如果發(fā)生錯誤，程序會報警告，可以直接知道出錯位置。

// 溫柔處理方式if (psl->size > 0){psl->a[ps->size - 1] = 0;psl->size--;}// 暴力處理方式assert(psl->size > 0);psl->size--;

---

注：不知道 SLDataType 是什么類型的數(shù)據(jù)，不能冒然的將順序表最后一個數(shù)據(jù)賦值為 0，我們只需將有效數(shù)據(jù)個數(shù) size 減 1 即可達到尾刪的目的。?

---

6、順序表頭插

// 順序表頭插
void SeqListPushFront(SeqList* psl, SLDateType x) // O(n)
{// 頭插不需要斷言 空指針也符合條件/* CheckCapacity(psl); // 檢查順序表容量是否已滿for (int i = psl->size - 1; i >= 0; i--) // 順序表中[0,size-1]的元素依次向后挪動一位{psl->a[i + 1] = psl->a[i];}psl->a[0] = x; // 頭插數(shù)據(jù)psl->size++; // 有效數(shù)據(jù)個數(shù)+1 */SeqListInsert(psl, 0, x);
}

---

7、順序表頭刪

// 順序表頭刪
void SeqListPopFront(SeqList* psl) // O(n)
{assert(psl); // 斷言// 方法一：/* assert(psl->size > 0);  //順序表不能為空for (int i = 1; i < psl->size; i++) // 順序表中[1,size-1]的元素依次向前挪動一位{psl->a[i - 1] = psl->a[i];}psl->size--; // 有效數(shù)據(jù)個數(shù)-1 */// 方法二：SeqListErase(psl, 0);
}

---

8、順序表打印

// 打印順序表
void SeqListPrint(SeqList* ps)
{assert(ps); // 斷言if (psl->size == 0) // 順序表為空{(diào)printf("順序表為空\n");return;}// 順序表不為空for (size_t i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}

---

?9、順序表查找指定值

// 順序表查找
int SeqListFind(SeqList* psl, SLDateType x)
{assert(psl); // 斷言for (int i = 0; i < psl->size; i++){if (psl->a[i] == x){return i; //查找到，返回該值在數(shù)組中的下標(biāo)}}return -1; // 沒查找到
}

---

?10、順序表在pos位置插入x

// 順序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{assert(psl); // 斷言assert(pos >= 0 && pos <= (psl->size)); // 檢查pos下標(biāo)的合法性CheckCapity(psl);// 第一種寫法：/* size_t end = psl->size;while (end > pos){psl->a[end] = psl->a[end - 1];end--;} *///第二種寫法：size_t i = 0;for (i = psl->size; i > pos; i--)  // 將pos位置后面的數(shù)據(jù)依次向后挪動一位{psl->a[i] = psl->a[i - 1];}psl->a[pos] = x; // 插入數(shù)據(jù)psl->size++; // 有效數(shù)據(jù)個數(shù)+1
}

---

注：原先下面這種寫法，當(dāng)順序表為空 size = 0 時，會導(dǎo)致 i = -1，執(zhí)行 i >= pos 時，i 被算術(shù)轉(zhuǎn)換成無符號數(shù)，而無符號數(shù)的 -1 是一個值很大的正數(shù)，遠遠大于 pos，滿足條件進入循環(huán)，會造成越界訪問。?

int i = 0;
for (i = psl->size - 1; i >= pos; i--)psl->a[i + 1] = psl->a[i];

注：轉(zhuǎn)換并不會改變 i 本身的值，而是在執(zhí)行 i >= pos 時，生成一個臨時值與 pos 進行比較。如果在順序表頭部（pos = 0）插入數(shù)據(jù)，i 最終也會減成 -1，被算術(shù)轉(zhuǎn)換后變成一個很大的數(shù)。

---

總結(jié)：避免負(fù)數(shù)給到無符號數(shù)，或者避免有符號數(shù)變成負(fù)數(shù)后，被算術(shù)轉(zhuǎn)換或整型提升后，變成一個很大的數(shù)。按照第二種寫法就可以避免 i 變成負(fù)數(shù)（-1）了。

---

?實現(xiàn)了此接口，順序表頭插和尾插相當(dāng)于在下標(biāo)為 0 和 psl -> size-1 位置處插入數(shù)據(jù)。

---

---

11、順序表刪除pos位置的值

// 順序表刪除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{assert(psl); // 斷言assert(psl->size > 0); // 順序表不能為空assert(pos >= 0 && pos < psl->size); // 檢查pos下標(biāo)的合法性// 第一種寫法：/* size_t start = pos;while (start < psl->size-1){psl->a[start] = psl->a[start + 1];start++;} *///第二種寫法：size_t i = 0;for (i = pos + 1; i < psl->size; i++)  // 將pos位置后面的數(shù)據(jù)依次向前挪動一位{psl->a[i - 1] = psl->a[i];}psl->size--; // 有效數(shù)據(jù)個數(shù)-1
}

實現(xiàn)了此接口，順序表頭刪和尾刪相當(dāng)于刪除下標(biāo)為 0 和 psl -> size-1?位置處的數(shù)據(jù)。

---

---

12、查看順序表中的有效數(shù)據(jù)個數(shù)?

// 查看順序表中的有效數(shù)據(jù)個數(shù)
size_t SeqListSize(const SeqList* psl)
{assert(psl); // 斷言return psl->size;
}

為什么不選擇在主函數(shù)里面直接通過定義的結(jié)構(gòu)體變量直接訪問，還要弄一個相關(guān)函數(shù)呢？

在數(shù)據(jù)結(jié)構(gòu)中，如果要訪問或者修改數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)，不要直接訪問，而是應(yīng)該去調(diào)用它的函數(shù)來訪問和修改，這樣會更加規(guī)范和安全，也更方便檢查出是否出現(xiàn)了越界等錯誤情況。

---

數(shù)組越界是不一定報錯的，系統(tǒng)對越界的檢查是設(shè)崗檢查。

• 越界讀（讀了不屬于自己的數(shù)據(jù)），一般是檢查不出來的，往往并不會造成內(nèi)存奔潰。

• 越界寫（緩沖區(qū)溢出）如果是修改到標(biāo)志位才會被檢查出來，會造成數(shù)據(jù)破壞，嚴(yán)重會造成內(nèi)存奔潰。

（系統(tǒng)在數(shù)組末尾后設(shè)的有標(biāo)志位，越界寫時，恰好修改到標(biāo)志位了，就會被檢查出來）

---

13、修改指定下標(biāo)位置的數(shù)據(jù)

// 修改指定下標(biāo)位置的數(shù)據(jù)
void SeqListAt(SeqList* psl, size_t pos, SLDataType x)
{assert(psl); // 斷言assert(psl->size > 0); // 順序表不能為空assert(pos >= 0 && pos < psl->size); // 檢查pos下標(biāo)的合法性psl->a[pos] = x; // 修改pos下標(biāo)處對應(yīng)的數(shù)據(jù)
}

---

?四、代碼整合

// SeqList.c
#include "SeqList.h"

// 初始化順序表
void SeqListInit(SeqList* psl)
{assert(psl); // 斷言 -- 防止傳進來的指針為空psl->a = NULL; // 初始化順序表為空psl->size = 0; // 初始數(shù)據(jù)個數(shù)為0psl->capacity = 0; // 初始空間容量為0
}// 銷毀順序表
void SeqListDestroy(SeqList* psl)
{assert(psl); // 斷言 -- 防止傳進來的指針為空free(psl->a); // 釋放動態(tài)開辟的空間psl->a = NULL; // 置空psl->size = 0; // 數(shù)據(jù)個數(shù)置為0psl->capacity = 0; // 空間容量大小置為0
}// 檢查順序表容量是否滿了，好進行增容
void CheckCapity(SeqList* psl)
{if (psl->size == psl->capacity) // 檢查容量，滿了則增容{// 原來容量為0，擴容為4；不為0，擴容為原來的2倍size_t newcapacity = psl->capacity == 0 ? 4 : 2 * (psl->capacity);psl->a = (SeqList*)realloc(psl->a, sizeof(SLDateType) * newcapacity); // 擴容psl->capacity = newcapacity; // 更新容量}
}// 順序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x) // O(1)
{SeqListInsert(psl, psl->size, x);
}// 順序表尾刪
void SeqListPopBack(SeqList* psl) // O(1)
{assert(psl); // 斷言SeqListErase(psl, psl->size - 1);
}// 順序表頭插
void SeqListPushFront(SeqList* psl, SLDateType x) // O(n)
{SeqListInsert(psl, 0, x);
}// 順序表頭刪
void SeqListPopFront(SeqList* psl) // O(n)
{assert(psl); // 斷言SeqListErase(psl, 0);
}// 打印順序表
void SeqListPrint(SeqList* ps)
{assert(ps); // 斷言if (psl->size == 0) // 順序表為空{(diào)printf("順序表為空\n");return;}// 順序表不為空for (size_t i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}// 順序表查找
int SeqListFind(SeqList* psl, SLDateType x)
{assert(psl); // 斷言for (int i = 0; i < psl->size; i++){if (psl->a[i] == x){return i; //查找到，返回該值在數(shù)組中的下標(biāo)}}return -1; // 沒查找到
}// 順序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{assert(psl); // 斷言assert(pos >= 0 && pos <= (psl->size)); // 檢查pos下標(biāo)的合法性CheckCapity(psl);size_t i = 0;for (i = psl->size; i > pos; i--)  // 將pos位置后面的數(shù)據(jù)依次向后挪動一位{psl->a[i] = psl->a[i - 1];}psl->a[pos] = x; // 插入數(shù)據(jù)psl->size++; // 有效數(shù)據(jù)個數(shù)+1
}// 順序表刪除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{assert(psl); // 斷言assert(psl->size > 0); // 順序表不能為空assert(pos >= 0 && pos < psl->size); // 檢查pos下標(biāo)的合法性size_t i = 0;for (i = pos + 1; i < psl->size; i++)  // 將pos位置后面的數(shù)據(jù)依次向前挪動一位{psl->a[i - 1] = psl->a[i];}psl->size--; // 有效數(shù)據(jù)個數(shù)-1
}// 查看順序表中的有效數(shù)據(jù)個數(shù)
size_t SeqListSize(const SeqList* psl)
{assert(psl); // 斷言return psl->size;
}// 修改指定下標(biāo)位置的數(shù)據(jù)
void SeqListAt(SeqList* psl, size_t pos, SLDataType x)
{assert(psl); // 斷言assert(psl->size > 0); // 順序表不能為空assert(pos >= 0 && pos < psl->size); // 檢查pos下標(biāo)的合法性psl->a[pos] = x; // 修改pos下標(biāo)處對應(yīng)的數(shù)據(jù)
}