【資料結構】手寫順序表【純C語言版】

摘要：本章主要講述線性表，以及用C語言代碼實作動态的順序表

<hr/>

@TOC

正文開始

<hr>

1. 什麼是線性表

1.1 概念

線性表(Linear list)是n個具有相同特性的資料元素的有限序列。線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、連結清單、棧、隊列、字元串...

線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在實體結構上并不一定是連續的，線性表在實體上存儲時，通常以數組和鍊式結構的形式存儲

1.2 線性表的特點

我們知道，由n（n≥0）個資料特性相同的元素構成的有限序列稱為線性表，是以線性表中元素的個數n（n≥0）就是線性表的長度，n=0 是稱為空表

對于非空線性表或線性結構，有以下幾個特點：

存在唯一的一個被稱作“第一個”的資料元素；
存在唯一的一個被稱作“最後一個”的資料元素；
除第一個資料元素外，結構中的每個資料元素均隻有一個前驅；
除最後一個元素之外，結構中的每個資料元素均隻有一個後繼。

3. 什麼是順序表

3.1 概念

順序表（Sequentila List）是用一段實體位址連續的存儲單元依次存儲資料元素的線性結構，一般情況下采用數組存儲。

順序表的特點：邏輯上相鄰的資料元素，在實體上也是相鄰的；順序表是一種随機存取的存儲結構

随機存取：可以通過下标直接操作資料元素，與存儲位置無關

順序存取：與随機存取相反，不能通過下标操作資料元素，與存儲位置有關

順序存取就是如果我們要操作第N個元素時，必須把該元素之前的所有元素通路一遍；而随機存取就是直接操作就行了。

3.2 順序表的分類

1.靜态順序表：使用定長數組存儲。

2.動态順序表：使用動态開辟的數組存儲，容量不受限制,支援資料插入,删除,修改等一系列操作。（接下來着重介紹）

4. 動态順序表的代碼實作

4.1 定義順序表及其資料元素類型

// 定義順序表中的資料元素的類型
typedef int SLDataType;

// 定義順序表
typedef struct SeqList
{
    SLDataType* datas; // 資料序列
    size_t size; // 順序表的有效資料個數
    size_t capacity; // 屬性表的最大存儲空間,即最多可以儲存多少個資料
} SeqList;

使用 typedef 定義順序表及其資料元素的類型是為了代碼的可擴充性，大家想一想，如果有一天我們的資料元素不用 int 了，而是使用double或結構體，那麼此時我們隻需要修改這裡就可以了，這樣是不是就避免很多麻煩了呢？

思考：為什麼資料序列要使用指針類型？

大家注意，我們這裡實作的是動态順序表，要使用順序表為動态，我們就需要動态開辟記憶體，使用指針是為了讓其容量不受限；如果我們将資料序列修改為 SLDataType data[50]，那麼這樣就是一個靜态的順序表了，因為它的長度已經被限定了

4.2 順序表的初始化

【算法步驟】：

為順序表 SeqList 動态配置設定一個預定義大小的數組空間，是資料序列datas 指向這段空間的基位址
将表的目前長度設為0，存儲空間設為預定義大小

【算法描述】

#define DEFAULT_SIZE 4
// 初始化順序表
void SeqListInit(SeqList* ps)
{
    assert(ps);
    // 預設開辟4個SLDataType大小的空間
    ps->data = (SLDataType*)malloc(sizeof(SLDataType) * DEFAULT_SIZE);
    if (ps->datas == NULL)
    {
        perror("申請記憶體失敗");
        exit(-1);
    }
    ps->size = 0;
    ps->capacity = DEFAULT_SIZE;
}

這裡我們為順序表的容量設定了一個常量DEFAULT_SIZE，其常量值為4

【使用】

int main()
{
    SeqList plist;
    SeqListInit(&plist);
}

思考：為什麼要傳遞指針？

因為我們這裡需要改變線性表 plist 中的内容，是以需要傳址；如果傳值的話ps隻是 plist 的一份臨時拷貝，在 SeqListInit 函數内對 ps 的修改并不會對 plist 有任何影響。當然也可以将 SeqListInit 改造為下面這個：
#define DEFAULT_SIZE 4
SeqList SeqListInit()
{
// 預設開辟4個SLDataType大小的空間
SLDataType* ps = (SLDataType*)malloc(sizeof(SLDataType) * DEFAULT_SIZE);
if (ps == NULL)
{
perror("申請記憶體失敗");
exit(-1);
}
SeqList list = { 0 };
list.datas = ps;
list.size = 0;
list.capacity = DEFAULT_SIZE;
return list;
}           

int main()
{
    SeqList plist = SeqListInit();

}

這是方式是使用傳回值完成順序表的初始化，當然是利用指針還是傳回值都是可以的。

4.3 順序表的增容

【算法步驟】

當順序表滿了的時候進行增容，每次增加原有容量的2倍
判斷順序表是否滿了：如果有效資料長度等于最大容量則表面表滿

// 檢查增容
void SeqListCheckCapacity(SeqList* ps)
{
    assert(ps);
    if ((ps->size) >= (ps->capacity))
    {
        // 兩倍增容
        ps->capacity *= 2;
        ps->datas = (SLDataType*)realloc(ps->datas, ps->capacity * sizeof(SLDataType));
        if (ps->datas == NULL)
        {
            perror("增容失敗");
            exit(-1);
        }
    }
}

4.4 順序表尾插法

檢查是否需要增容
在下标為size位置處插入資料
有效資料個數加1

// 順序表的尾插
void SeqListPushBack(SeqList* ps, SLDataType* data)
{
    assert(ps);

    // 1.檢查擴容
    SeqListCheckCapacity(ps);
    // 2.插入資料
    ps->datas[ps->size] = *data;
    // 3.有效資料個數加1
    (ps->size) ++;
}

4.5 順序表尾删法

判斷是否是空表，空表則中斷
有效資料個數減1即可

// 順序表的尾删
void SeqListPopBack(SeqList* ps) 
{
    assert(ps);
    // 空表時中斷
    assert(ps->size > 0);
    // 有效資料減1
    (ps->size)--;
}

4.6 列印順序表

void SeqListPrint(SeqList* ps)
{
    assert(ps);

    for (int i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->datas[i]);
    }
    putchar('\n');
}

int main()
{
    SeqList sl = SeqListInit();
    SLDataType a[] = { 0,1,2,3,4,5,6,7,8,9 };
    // 尾插
    SeqListPushBack(&sl, &a[1]);
    SeqListPushBack(&sl, &a[2]);
    // 列印
    SeqListPrint(&sl);              // 1 2 
}

4.7 順序表頭插法

所有元素整體後移
在頭插入資料

// 順序表的頭插
void SeqListPushFront(SeqList* ps, SLDataType* data)
{
    // 順序表的頭插
void SeqListPushFront(SeqList* ps, SLDataType* data)
{
    assert(ps);
    // 1.檢查增容
    SeqListCheckCapacity(ps);
    // 2.整體元素後移一個位置
    for (int i = ps->size - 1; i >= 0; i--)
    {
        // 後移
        ps->datas[i + 1] = ps->datas[i];
    }
    // 3.插入資料
    ps->datas[0] = *data;
    // 4.有效資料個數加1
    (ps->size) ++;
}}

4.8 順序表頭删法

判斷是否為空表，如果是函數執行結束
整體元素前移一個機關

// 順序表的頭删
void SeqListPopFront(SeqList* ps)
{
    assert(ps);
    if (ps->size == 0)
    {
        printf("順序表元素為空,删除失敗!");
        return;
    }
    // 1.整體元素前移一個位置 要移動的元素-->[1,size]
    for (int i = 0; i < ps->size - 1; i++)
    {
        ps->datas[i] = ps->datas[i + 1];
    }
    // 有效資料個數減1
    (ps->size)--;
}

4.9 順序表的插入

判斷插入位置pos是否合法（pos值的合法範圍時0≤pos＜size），若不合法則程式中斷。
判斷順序表是否需要增容。
将第pos個至第size-1個元素依次向後移動一個位置，空出第pos個位置。
将要插入的新元素data放入第pos處。
順序表有效資料個數加1。

// 任意位置插入
void SeqListInsert(SeqList* ps, int pos, SLDataType* data)
{
    assert(ps);
    size_t size = ps->size;
    // pos需要在[0,size]範圍中
    assert( (pos <= size) && (pos >= 0) );

    // 檢查增容
    SeqListCheckCapacity(ps);

    // [pos,size-1]處的元素後移一個位置
    for (int i = size - 1; i >= pos; i--)
    {
        ps->datas[i + 1] = ps->datas[i];
    }
    // 插入元素
    ps->datas[pos] = *data;
    // 有效資料個數加1
    (ps->size) ++;
}

4.10 順序表的删除

判斷插入位置pos是否合法（pos值的合法範圍時0≤pos≤size），若不合法則程式中斷。
将第pos個至第size-1個元素依次向前移動一個位置。
順序表有效資料個數減1

// 任意位置删除
void SeqListErase(SeqList* ps, int pos)
{
    assert(ps);
    size_t size = ps->size;
    assert((pos <= size) && (pos >= 0));

    // 檢查增容
    SeqListCheckCapacity(ps);
    // [pos+1,size-1] 的元素整體前移一個位置
    for (int i = pos; i < size -1; i++)
    {
        ps->datas[i] = ps->datas[i + 1];
    }
    (ps->size) --;
}

4.11 順序表的銷毀

将資料序列釋放掉
将資料序列置為NULL
将資料有效個數和最大容量置為0

void SeqListDestory(SeqList* ps)
{
    assert(ps);
    // 釋放資源
    free(ps->datas);
    ps->datas = NULL;
    ps->size = ps->capacity = 0;
}

4.12 思考

大家思考一下，為什麼我在對順序進行增容、插入等這些操作時，傳遞的資料采用傳址的方式，而不是傳值的方式呢？歡迎各位在評論區留言。

5. 源碼連結

點選跳轉

【檔案說明】	檔案名	說明
SeqList.h	類型定義和函數聲明
SeqList.c	具體函數的實作
test.c	測試代碼

後記

我水準有限，錯誤難免，還望各位加以指正。

【資料結構】手寫順序表【純C語言版】

1. 什麼是線性表

1.1 概念

1.2 線性表的特點

3. 什麼是順序表

3.1 概念

3.2 順序表的分類

4. 動态順序表的代碼實作

4.1 定義順序表及其資料元素類型

4.2 順序表的初始化

4.3 順序表的增容

4.4 順序表尾插法

4.5 順序表尾删法

4.6 列印順序表

4.7 順序表頭插法

4.8 順序表頭删法

4.9 順序表的插入

4.10 順序表的删除

4.11 順序表的銷毀

4.12 思考

5. 源碼連結

後記

繼續閱讀

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

CRC32和CRC8校驗代碼，C語言版

241 Different Ways to Add Parentheses（C代碼版）

[轉]ISUP信令的IAM消息詳細内容

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

結構體：typedef與struct的差別

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希