0.引言

????????在本章之后，就要求大家對(duì)于指針、結(jié)構(gòu)體、動(dòng)態(tài)開辟等相關(guān)的知識(shí)要熟練的掌握，如果有小伙伴對(duì)上面相關(guān)的知識(shí)還不是很清晰，要先弄明白再過來接著學(xué)習(xí)哦！

????????那進(jìn)入正題，在講解順序表之前，我們先來介紹線性表這個(gè)數(shù)據(jù)結(jié)構(gòu)。

0.1 線性表

????????線性表是 n個(gè)具有相同特性的數(shù)據(jù)元素組成的有限的序列。
????????并且在邏輯上是一對(duì)一的，一個(gè)接著一個(gè)的。比如我們之前學(xué)過的數(shù)組，字符串等。

????????相同特性：同一種數(shù)據(jù)類型
????????有限：數(shù)據(jù)元素的個(gè)數(shù)是有限的

????????常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串等。

????????我們?cè)谥v解數(shù)據(jù)結(jié)構(gòu)的時(shí)候通常要先看它的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

0.2 線性表的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

0.2.1 邏輯結(jié)構(gòu)

????????線性表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，線性結(jié)構(gòu)?是一條連續(xù)的直線，也就是說 線性表在邏輯上是連續(xù)的，比如我們?cè)贑語言學(xué)過的的數(shù)組（順序表），指針（可以構(gòu)成鏈表）。

????????上圖分別為順序表跟鏈表，他們?cè)谶壿嫿Y(jié)構(gòu)上都是一個(gè)接著一個(gè)，連續(xù)的。但是在物理結(jié)構(gòu)他們還依舊連續(xù)嗎？讓我們帶著疑問往下走。

0.2.2 線性表的物理結(jié)構(gòu)

????????明確告訴大家，線性表在物理結(jié)構(gòu)上不一定連續(xù)，因?yàn)槲覀兛梢詷?gòu)成線性表的結(jié)構(gòu)有數(shù)組和指針，指針又被稱作鏈?zhǔn)浇Y(jié)構(gòu)。

那什么時(shí)候是連續(xù)的？

當(dāng)線性表是由數(shù)組構(gòu)成時(shí)：物理結(jié)構(gòu)連續(xù)

? ? ? ? 線性表的物理結(jié)構(gòu)一定連續(xù)，因?yàn)閿?shù)組是一個(gè)一個(gè)挨著的空間，地址上是緊挨著的，所以是連續(xù)的。

如圖：

什么時(shí)候又不是連續(xù)的呢？???????

當(dāng)線性表為鏈?zhǔn)浇Y(jié)構(gòu)時(shí)：物理結(jié)構(gòu)不連續(xù)

? ? ? ? ?首先鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上一定是連續(xù)的，因?yàn)槲覀兛梢酝ㄟ^指針就找到該指針對(duì)應(yīng)的地址。
????????但指針的地址不一定是連續(xù)的，我們可以這存一個(gè)，那存一個(gè)，通過指針給他們鏈接起來。

如圖：

????????當(dāng)了解了線性表的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)之后，就讓我們一起學(xué)習(xí)第一種數(shù)據(jù)結(jié)構(gòu)---順序表吧！

1. 順序表

1.1概念

????????順序表是 用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，通常采用數(shù)組的形式存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
????????這是什么意思呢？首先順序表是物理地址連續(xù)的，那物理地址連續(xù)，就應(yīng)該是用數(shù)組的形式來存儲(chǔ)，之后根據(jù)數(shù)組的性質(zhì)進(jìn)行數(shù)據(jù)的增加，刪除，查找和更改。

????????我們知道順序表是由什么構(gòu)成之后，讓我們看看順序表都分為哪幾種吧！

1.2 順序表的分類

? ? ? ? 我們順序表只分為靜態(tài)順序表和動(dòng)態(tài)順序表兩種，下面我們會(huì)給大家展示這兩種順序表。

1.2.1 靜態(tài)順序表

????????靜態(tài)順序表指的是利用定長(zhǎng)數(shù)組來存儲(chǔ)元素

//順序表的靜態(tài)存儲(chǔ)
#define N 7 //順序表一次開辟的空間個(gè)數(shù)
typedef int SLDataType; //將數(shù)據(jù)類型重命名，以便我們未來換用其他的數(shù)據(jù)類型
typedef struct SeqList
{
    SLDataType arr[N]; //定長(zhǎng)數(shù)組
    size_t size; //有效的數(shù)據(jù)個(gè)數(shù)，size_t指的是無符號(hào)整型
}Seqlist;

????????我們?cè)谑褂渺o態(tài)順序表的時(shí)候，只能每次開辟N個(gè)大小的空間，這也就要求我們?cè)谑褂弥熬鸵牒媚阋娣哦嗌賯€(gè)數(shù)據(jù)，非常不靈活，沒有辦法做到你想插入幾個(gè)數(shù)據(jù)的時(shí)候就插入幾個(gè)數(shù)據(jù)，所以我們大多時(shí)候不使用靜態(tài)順序表，而是改用動(dòng)態(tài)順序表作為我們?nèi)粘?yīng)用。

這也是我們常說的要適應(yīng)大環(huán)境的需要，而不是一味不變。

1.2.2 動(dòng)態(tài)順序表

????????動(dòng)態(tài)順序表：使用動(dòng)態(tài)開辟的數(shù)組存儲(chǔ)。在這里需要大家對(duì)動(dòng)態(tài)開辟內(nèi)存知識(shí)有一定的掌握。

1. 動(dòng)態(tài)順序表的定義

我們首先要明確自己需要什么

1.動(dòng)態(tài)開辟的數(shù)組

2.有效的數(shù)據(jù)個(gè)數(shù)（你存入的數(shù)據(jù)個(gè)數(shù)）

3.數(shù)組的容量（開辟的空間大小）

????????這三個(gè)數(shù)據(jù)是綁定一起的吧！因?yàn)槟阌袛?shù)組，你才可以存入元素，你存入元素，你的有效的數(shù)據(jù)個(gè)數(shù)才會(huì)增加，而在你存入元素之前，你必須開辟空間，給數(shù)組一定的容量。

????????所以我們?cè)谶@里用了結(jié)構(gòu)體包含三者，目的就是能讓他們?nèi)齻€(gè)綁定，便于大家完成代碼。

????????未來大家如果要?jiǎng)?chuàng)造更多的關(guān)系數(shù)據(jù)（具有關(guān)系的數(shù)據(jù)），強(qiáng)烈推薦使用結(jié)構(gòu)體來給它們打包。

typedef int SLDataType; //數(shù)據(jù)類型的重命名，方便更改數(shù)據(jù)類型
typedef struct SeqList
{
    SLDataType *a; //指向動(dòng)態(tài)開辟的數(shù)組
    int size;     //有效的數(shù)據(jù)個(gè)數(shù)
    int capacity; //動(dòng)態(tài)開辟的數(shù)組的容量
}SL;

2.初始化

????????在初始化這里，我們要給數(shù)組開辟一定的空間，方便在插入數(shù)據(jù)的時(shí)候進(jìn)行操作，但是在這里，我們只是開辟空間，并沒有給數(shù)組插入元素，所以我們的有效元素個(gè)數(shù)size就是0，容量就是你開辟的空間個(gè)數(shù)。

????????我們一般開辟空間第一次給4個(gè)數(shù)據(jù)類型的空間。但是這個(gè)沒有定性要求（固定的要求）你想開辟幾個(gè)就開辟幾個(gè)。

void SLInit(SL*ps) //初始化
{
    ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);
    if(ps->a == NULL)
    {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    ps ->size = 0;
    ps ->capacity = 4;
}

3.退出程序時(shí)的銷毀

注意????????????

????????這個(gè)函數(shù)有講頭了，我們要記住一點(diǎn)，凡是通過動(dòng)態(tài)開辟的空間，一定要進(jìn)行銷毀釋放，因?yàn)橛蒻alloc，realloc等開辟的空間是在堆上開辟的，無法自動(dòng)釋放掉。我們沒有這個(gè)函數(shù)，那么就會(huì)造成內(nèi)存的泄漏。

????????那么如何釋放呢？

????????free函數(shù)來釋放開辟的空間，誰被開辟free誰，之后要將free的對(duì)象置為空就OK啦！不要忘了你釋放空間之后，有效的數(shù)據(jù)元素是0了哈，容量也是0.

void SLDestroy(SL*ps) //退出時(shí)銷毀
{
    free(ps->a);
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;
}

4.擴(kuò)容

????????這個(gè)函數(shù)是解決當(dāng)你第一次開辟的空間不夠的問題，就要用到這個(gè)函數(shù)來進(jìn)行擴(kuò)容，擴(kuò)容一般是擴(kuò)原來空間的二倍這么大。

????????那擴(kuò)容的條件是什么呢？

????????就是當(dāng)我們插入的 ?有效元素的個(gè)數(shù)size?= 容量capacity ?的時(shí)候，完成擴(kuò)容之后一定要判斷你擴(kuò)容是否成功了，如果 tmp??NULL，那就說明開辟空間失敗，用perror函數(shù)告訴你哪里失敗了，之后用exit函數(shù)退出程序，exit函數(shù)是直接強(qiáng)制退出，不回到主函數(shù)，跟return不一樣。當(dāng)開辟成功了，就讓a指向這段空間就OK，再更新一下capacity；

void SLCheckCapacity(SL*ps)  //擴(kuò)容函數(shù)
{
    if(ps->size == ps->capacity)
    {
        SLDataType *tmp = (SLDataType*)realloc(ps->a,((sizeof(SLDataType)) * ((ps->capacity) * 2)));
        if(tmp == NULL)
        {
            perror("realloc");
            exit(EXIT_FAILURE);
        }
        ps -> a = tmp;
        ps->capacity *= 2;
    }
}

6.尾插尾刪

????????順序表的尾插：

? ? ? ? 在尾插的時(shí)候，我們要判斷是否插滿了，就需要用到我們的擴(kuò)容函數(shù)來判斷一下，沒滿就直接插入，滿了則擴(kuò)容。

如圖：這就是沒有插滿的情況，我們目前已經(jīng)插入了5個(gè)元素，ps->size=5，我們?cè)俨迦胍粋€(gè)元素的時(shí)候就可以在下標(biāo)為size這里插入了，之后再size++就可以了

如圖：是插滿的情況，我們就要先擴(kuò)容

如圖：擴(kuò)容之后，這個(gè)時(shí)候我們就可以插入啦！

? ? ? ? 順序表的尾刪：

? ? ? ? 尾刪就好寫多了，我們只需要將size減1即可，因?yàn)閟ize代表有效的元素個(gè)數(shù)，將元素個(gè)數(shù)減一，就相當(dāng)于刪除了。

尾插
void SLPushBack(SL*ps,int i) 
{
    SLCheckCapacity(ps);
    ps->a[ps->size] = i;
    ps->size++;
}

尾刪
void SLPopBack(SL*ps) 
{
    assert(ps->size > 0);
    ps->size--;
}

5.頭插頭刪

?順序表的頭插：

? ? ? ? 對(duì)于頭插就要麻煩很多了，我們需要將數(shù)據(jù)一個(gè)個(gè)覆蓋給下一個(gè)。再將我們的第一個(gè)元素值變成要插入的元素值，這里也要判斷是否需要擴(kuò)容哦！

? ? ? ??

????????順序表的頭刪：

????????同理頭刪也是需要覆蓋數(shù)據(jù)的，要把第二個(gè)數(shù)據(jù)給第一個(gè)，第三個(gè)給第二個(gè)等等以此類推

頭插
void SLPushFront(SL*ps,int i)
{
    SLCheckCapacity(ps);
    int end = ps->size;
    for(;end - 1 >= 0 ; end--)
    {
        ps->a[end] = ps->a[end - 1];
    }
    ps->a[0] = i;
    ps->size++;
}
 ///頭刪
void SLPopFront(SL*ps)
{
    assert(ps->size > 0);
    int i = 0;
    for(i = 0 ; i + 1 < ps->size ; i++)
    {
        ps->a[i] = ps->a[i+1];
    }
    ps->size--;
}

7.順序表的查找

? ? ? ? 查找某一值x是否存在順序表里，存在返回?cái)?shù)組下標(biāo)，不存在返回-1.

int SeqListFind(SL*ps,SLDataType x) //查找
{
    int i = 0;
    for(i = 0 ; i < ps->size ; i++)
    {
        if(ps->a[i] == x)
        {
            return i;
        }
    }
    return -1;
}

8.在下標(biāo)為pos的位置的插入

下面的大家自行畫圖理解哦，相信經(jīng)過前面的講解，大家有一定的收獲啦！

void SeqListInsert(SL* ps, int pos, SLDataType x)// 順序表在pos位置插入x
{
    if(ps->size == ps->capacity)
    {
        SLCheckCapacity(ps);
    }
    int i = SeqListFind(ps,pos);
    int j = ps->size;
    for(;j > i ; j--)
    {
        ps->a[j] = ps->a[j-1];
    }
    ps->a[i] = x;
    ps->size++;
}

9.刪除下標(biāo)為pos位置的值

void SeqListErase(SL* ps, int pos)// 順序表刪除pos位置的值
{
    assert(ps->size > 0);
    int i = SeqListFind(ps,pos);
    for(i;i < ps->size - 1; i++ )
    {
        ps->a[i] = ps->a[i+1];
    }
    ps->size--;
}

9.打印

打印就是遍歷一邊數(shù)組就OK啦！

void SLPrint(SL*ps) //打印
{
    int i = 0;
    for(i = 0 ; i < ps->size ;i++)
    {
        printf("%d ",ps->a[i]);
    }
    printf("\n");
}

以上就是順序表的相關(guān)接口實(shí)現(xiàn)啦！謝謝大家過來與博主一起學(xué)習(xí)，如果覺得博主寫的還可以，對(duì)各位有幫助，別忘了點(diǎn)贊和收藏，方便以后再次查看呀！文章來源地址http://www.zghlxwxcb.cn/news/detail-713154.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之手撕順序表（講解?源代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！