Hello,米娜桑們，這里是君兮_，今天正式開始開新坑啦！在接下來的這一個月來我會逐步帶大家了解初階數(shù)據(jù)結(jié)構(gòu)的知識，如果是你主修的是計算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)的重要性不言而喻，哪怕在以后你工作面試時，它也是面試官們最喜歡考察的內(nèi)容之一，如果你想對這部分內(nèi)容有一個系統(tǒng)又深刻的認(rèn)識，那么不要錯過這個專欄的內(nèi)容哦?。∥視τ猛ㄋ滓锥脑拋韼Т蠹胰腴T的！
好了，廢話不多說，開始今天的學(xué)習(xí)吧！

前言

ps：順序表中難以理解的點應(yīng)該就是malloc以及realloc的使用了，這是有關(guān)C語言的動態(tài)內(nèi)存管理的知識，我們主要目的是介紹順序表的因此不做綴敘，如果你感興趣之后我也會更新有關(guān)博客并且把鏈接貼在這里噠！

一.線性表

我們知道，順序表是最基礎(chǔ)的線性表，那么什么是線性表呢？

1.線性表的概念

• 線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列、字符串…
• 線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲
  

二.順序表

2.1 概念及結(jié)構(gòu)

• 順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
• 注意：這里我們要知道的是，順序表存放的數(shù)據(jù)是連續(xù)的并且在內(nèi)存中是真正依次存放的,這一點是與鏈表最大的區(qū)別！

2.2 順序表的分類

• 順序表一般有兩種形式
• 1. 靜態(tài)順序表：使用定長數(shù)組存儲元素。

// 靜態(tài)順序表
#define N 1000
typedef int SLDataType;

struct SeqList
{
	SLDataType a[N];
	int size;
};

• 靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致N定大了，空間開多了浪費，開少了不夠用。所以現(xiàn)實中基本都是使用第二種順序表——動態(tài)順序表，根據(jù)需要動態(tài)的分配空間大小。
• 2.動態(tài)順序表

// 動態(tài)順序表
typedef int SLDataType;//重命名數(shù)據(jù)類型,方便以后直接修改

typedef struct SeqList
{
	SLDataType* a;//指向動態(tài)開辟的數(shù)組
	int size;        // 存儲有效數(shù)據(jù)個數(shù)
	int capacity;    // 容量空間大小
}SL;

• 顧名思義，動態(tài)順序表使用動態(tài)開辟的數(shù)組儲存，這樣更方便我們實時根據(jù)數(shù)據(jù)的多少調(diào)整數(shù)組的大小。。
• 以下是上面這段代碼要提醒的幾處要點：
• 1.我們在上面這段代碼中使用了兩個typedef，但是用處卻不相同
• • 第一處的typedef實際是為了方便我們的使用，因為我們也不知道我們的順序表是用來存儲什么類型的數(shù)據(jù)的，因此我們這里就定義一個SLDataType，下面的代碼中統(tǒng)一把數(shù)據(jù)類型用它來代替，這樣一來，我們以后想要改變存儲的數(shù)據(jù)類型，只需要改動這里即可，比如我們現(xiàn)在想要存儲double類型的數(shù)據(jù)

typedef double SLDataType;

• • 第二處的typedef是將這個結(jié)構(gòu)體重命名，方便我們接下來的使用，接下來的結(jié)構(gòu)體直接寫出‘SL’就行。

接下來我們來具體實現(xiàn)一下動態(tài)順序表的各種功能以及使用方法

2.3 動態(tài)順序表的實現(xiàn)

順序表的初始化

• 我們確定了順序表內(nèi)的基本內(nèi)容，我們得把順序表先初始化一下，不然連空間都還沒開辟咋使用呢？

//初始化順序表
void SLInit(SL* ps)
{
    ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);//申請四個字節(jié)的空間，如果不夠再進(jìn)行增容
    if (ps->a == NULL)
    {
        perror("malloc failed");
        exit (-1);
    }
    ps->size = 0;
    ps->capacity = 4;
}

• 我們通過malloc為我們的順序表申請了四個字節(jié)的空間，同時此時我們還未填入數(shù)據(jù)，因此size初始化為0，容量空間大小為4.
• 但是我們只是申請了空間，還不知道是否成功，因此我們又通過分辨動態(tài)數(shù)組是否為NULL并通過perror報錯來判斷我們開辟內(nèi)存的操作是否成功。

順序表的擴(kuò)容

• 我們初始化了一個順序表，但是我們并不知道我們申請的空間是否夠用，如果不夠用，我們就得擴(kuò)容一下。因此我們這里的邏輯應(yīng)該是先判斷容量是否夠用，夠用就不用做多余的操作，如果不夠用，就申請擴(kuò)容

//檢查空間，如果順序表滿了，就進(jìn)行增容操作
void SLCheckCapacity(SL* ps)
{
    assert(ps);//斷言防止傳入ps為空
    //判斷一下是否空間滿了，如果滿了就把容量增加到原來的2倍
    if (ps->size == ps->capacity)//有效數(shù)據(jù)是否占滿所有空間
    {
        SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));//利用realloc擴(kuò)容
        if (tmp == NULL)
        {
            perror("realloc failed");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity *= 2;
    }
}

• 我們這里通過realloc將空間擴(kuò)容到原來的2倍，當(dāng)我們通過perror判斷擴(kuò)容成功后將擴(kuò)容賦給我們的動態(tài)數(shù)組，由于擴(kuò)容到原來的兩倍，這里的容量空間大小也要變?yōu)樵瓉淼?倍。

順序表的銷毀

• 當(dāng)我們使用完順序表后，由于我們是用malloc開辟的內(nèi)存，因此必須把它給銷毀并且釋放掉

void SLDestroy(SL* ps)
{
    free(ps->a);//釋放malloc申請的空間并且將a指向NULL
    ps->a = NULL;
    ps->capacity = ps->size = 0;

}

• 在銷毀并釋放內(nèi)存的同時，我們也需要把size和capacity初始化一下。

順序表的打印

• 當(dāng)我們把數(shù)據(jù)插入或者刪除后，我們就需要打印一下順序表來看看我們的操作是否執(zhí)行成功

void SLPrint(SL* ps)
{
    int i =0;
    for (i = 0; i < ps->size; i++)
        printf("%d ", ps->a[i]);//把有效數(shù)據(jù)通過循環(huán)都打印一下
    printf("\n");
}

• 如果說之前的都是前菜，我們接下來進(jìn)入今天的正餐，也是順序表中最難理解的一部分，就是咱們所謂的增刪查改

順序表的尾插與尾刪

• 什么叫尾插和尾刪呢？
• **所謂尾插就是從順序表的末尾插入數(shù)據(jù)，而尾刪就是把最后一個數(shù)據(jù)給刪除**

//順序表尾插
void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);//先判斷以下順序表是否已滿，未滿才能插入數(shù)據(jù)
    ps->a[ps->size] = x;//把數(shù)組a中size位置的數(shù)據(jù)賦值為x，size位置即最后一位
    ps->size++;//插入數(shù)據(jù)成功，有效數(shù)據(jù)+1
}

• 其中，尾刪時，我們需要檢查是否越界，比如你就倆數(shù)據(jù)，你尾刪了10次，那么此時你的有效數(shù)據(jù)就成負(fù)的了，這時你是不是就越界了？
• 檢查是否越界有兩種方法我愿稱之為溫柔檢查法和暴力檢查法，這又是怎么個回事呢？

//順序表尾刪
void SLPopBack(SL* ps)
{

    assert(ps);
    溫柔的檢查
    //if (ps->size == 0)
    //    return;
    //暴力檢查
    assert(ps->size > 0);
    ps->a[ps->size - 1] = 0;//把最后一個數(shù)據(jù)抹掉
    ps->size--;//有效數(shù)據(jù)-1

}

• 啥叫溫柔檢查呢？
• 當(dāng)我們size已經(jīng)刪沒的時候（size == 0），說明有效數(shù)據(jù)都已經(jīng)刪完了，這時我們就直接return即可。此時程序既不會往下走導(dǎo)致越界，也不會報錯。
• 而暴力檢查法就如你的嚴(yán)父一樣
• 我們直接通過assert斷言，，如果它發(fā)現(xiàn)你越界了，就會直接掏出七匹狼（報錯），并且告誡你錯在哪里，如下所示
  
  。。。放錯了，如下所示：
  

順序表的頭插與頭刪

• 與尾插和尾刪類似，順序表的頭插與頭刪就是在開頭進(jìn)行插入與刪除數(shù)據(jù)操作

/順序表的頭插
void SLPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);//判斷容量是否已滿
    //挪動數(shù)據(jù)
    int End = ps->size - 1;
    while (End >= 0)
    {
        ps->a[End + 1] = ps->a[End];
        End--;
    }
    ps->a[0] = x;
    ps->size++;

}

• 在頭插的過程中，我們需要注意的是，在頭部插入一個數(shù)據(jù)，我們就需要把順序表中的數(shù)據(jù)都朝后挪動一位給頭部插入讓位。

//順序表的頭刪
void SLPopFront(SL* ps)
{
    assert(ps);
    int begin = 0;
    while (begin < ps->size-1)
    {
        ps->a[begin] = ps->a[begin + 1];
        begin++;
    }
    ps->size--;
}

• 在頭刪時，與頭插類似，我們需要把所有數(shù)據(jù)都往前挪動一位來彌補(bǔ)頭刪的空缺，最后再把有效數(shù)據(jù)減少一位即可。

在順序表中任意位置的刪除與插入

//在順序表中pos位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);//檢查容量空間大小
    assert(pos >= 0 && pos <= ps->size);//判斷pos的合法化，避免插入到非法坐標(biāo)中
    int end = ps->size - 1;
    while (end >= pos)//把pos位置后的數(shù)據(jù)都朝后挪動一位，給插入的數(shù)據(jù)騰位置
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;//插入數(shù)據(jù)
    ps->size++;//有效數(shù)字+1

}

• 這里與頭插類似，只不過我們需要挪動的數(shù)據(jù)變成了pos位置后的數(shù)據(jù)，它們都需要朝后挪動一位

//在順序表中刪除pos位置的值
void SLErase(SL* ps, int pos)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    int begin = pos;
    while (begin < ps->size-1)
    {
        ps->a[begin] = ps->a[begin + 1];//pos后的數(shù)據(jù)都朝前挪動一位
        begin++;
    }
    ps->size--;//有效數(shù)據(jù)-1
}

• 與頭刪類似，pos后面的數(shù)據(jù)都要朝前挪動一位來填補(bǔ)刪除pos位置上數(shù)據(jù)的空缺

順序表中數(shù)據(jù)的查找與修改

• 順序表中數(shù)據(jù)的查找

//查找順序表中是否有某個數(shù)，如果有就返回該數(shù)的下標(biāo)

int SLFind(SL* ps, SLDataType x)
{
    assert(ps);

    for (int i = 0; i < ps->size; i++)
    {
        if (ps->a[i] == x)
        {
            return i;
        }
    }

    return -1;
}

• 通過遍歷數(shù)組的形式來查找是否存在某個數(shù)據(jù)，找到就返回該數(shù)據(jù)所在的位置，沒找到就返回-1。
• 順序表中的修改
• 要想修改，我們需要知道要修改哪個位置的數(shù)據(jù)以及我們要把該位置上的數(shù)據(jù)修改成多少

void SLModify(SL* ps, int pos, SLDataType x)
{
    assert(ps);

    assert(pos >= 0 && pos < ps->size);//判斷要修改數(shù)據(jù)的坐標(biāo)是否合法

    ps->a[pos] = x;//修改數(shù)據(jù)
}

2.4 測試一下我們的動態(tài)順序表

• 好了，我們順序表的基本功能都已經(jīng)通過代碼實現(xiàn)了，我們現(xiàn)在來挑選幾個重要的功能測試一下

int main()
{
    SL s1;
    SLInit(&s1);
    SLPushBack(&s1, 1);
    SLInsert(&s1, 1, 50);
    SLPushFront(&s1, 20);
    SLPrint(&s1);
  
    int ret=SLFind(&s1, 50);
    if(ret!=-1)
    printf("找到了，下標(biāo)是%d\n", ret);
    SLErase(&s1, 0);
    SLPopBack(&s1);
   
    SLPrint(&s1);
    SLModify(&s1, 0, 666);
    SLPrint(&s1);

    
    return 0;
}

• 仔細(xì)對比一下我們要實現(xiàn)的功能，發(fā)現(xiàn)雀氏沒有問題

2.5順序表的優(yōu)缺點

• 存在的問題：
• 1. 中間/頭部的插入刪除，時間復(fù)雜度為O(N)
• 2. 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。（尤其是異地擴(kuò)容）
• 3. 增容一般是呈2倍的增長，勢必會有一定的空間浪費。
  例如當(dāng)前容量為100，滿了以后增容到200，我們再繼續(xù)插入了5個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費了95個數(shù)據(jù)空間
• 優(yōu)點
• 1.尾刪和尾插足夠快
• 2.能通過下標(biāo)實現(xiàn)隨機(jī)訪問和修改（這點是非常重要的）

總結(jié)

• 今天的內(nèi)容到這里就結(jié)束了，我們帶大家具體的實現(xiàn)了順序表的編寫。由于篇幅原因，在順序表編寫中存在的易錯點以及各種細(xì)節(jié)的知識我們放到下一篇再講，同時也會講幾個相關(guān)的面試題目加深大家對這些易錯點的理解。
• ps：其實是熬夜寫博客有點太晚了，博主有點頂不住了,看在博主這么努力的份上真的不留下你的三連嗎？??！
• 好了，如果你有任何疑問歡迎在評論區(qū)或者私信我提出，大家下次再見啦！

新人博主創(chuàng)作不易，如果感覺文章內(nèi)容對你有所幫助的話不妨三連一下這個新人博主再走唄。你們的支持就是我更新的動力?。?！

文章來源地址http://www.zghlxwxcb.cn/news/detail-612560.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】帶你輕松拿捏順序表（內(nèi)附源碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！