順序表的創建與常見介面函式

一、什么是線性表？
二、如何創建一個順序表？
三、介面函式
- 容量審查函式：
- 初始化函式：
- 銷毀函式：
- 尾插函式:
- 尾刪函式：
- 頭插函式：
- 頭刪函式：
- 尋找函式:
- 指定下標插入：
- 洗掉指定下標元素：
- 小結

線性表是資料結構中最常見的一種資料存盤方式，線性表分為順序表與鏈表，本文將會從簡單的順序表開始，一點一點揭開C資料結構的神秘面紗，

一、什么是線性表？

線性表，顧名思義，其會呈現出一種線性進行存盤，這和我們所學過的陣列的概念很像，回顧一下陣列的基本知識：陣列的各個元素連續存放在記憶體中，并按照陣列型別為每一個變數分配對應大小的存盤空間，在線性表中也是如此，當記憶體中的資料是連續存盤時我們可以將其用陣列的角度理解，我們稱之為順序表，當資料以指標的形式連接起來時，此時我們稱其為鏈表，

二、如何創建一個順序表？

由上面的敘述，我們可以知道，一個順序表可以近似理解為一個陣列，但與陣列不同的是，順序表本質上是一個需要不斷的進行資料的存盤、洗掉動態空間，所以我們需要用多個介面函式來維護順序表，

由于順序表不僅僅是一個陣列，還需要我們不斷的探索其長度，所以我們并不能簡單的通過創建陣列的方式創建順序表，所以我們想到用一個結構體就能夠有效的將陣列與其大小緊密聯合起來：

#pragma once
#define N 1000
typedef int SLDataType;

//靜態資料表
typedef struct SeqList
{
    SLDataType a[N];
    int size;
}SL;

注意到，這里的N是我們預先進行定義的1000，若我們需要更多的資料存盤進順序表，那么我們需要不斷的修改#define N的值，這顯得有些麻煩，
所以稍微改進一下，我們就可以用一個指標將靜態順序表轉變為一個可以擴展空間的動態順序表，

typedef struct SeqList
{
    SLDataType *a;
    int size;//表示陣列實際存盤了多少個資料
    int capacity//資料實際能存盤資料的空間容量是多大
}SL;

注意到，在創建動態順序表時，我們又引入了一個capacity變數來探索當前順序表的“存盤資料的能力”而選擇是否進行擴容，capacity變數在后續的介面函式中起著至關重要的作用，請注意，這里的size是當前順序表實際存盤資料的多少，capacity是整個順序表的容量，比如說容量可以是8（capacity=8)，但當前順序表可以只存盤4個元素（size=4)

三、介面函式

一個動態的順序表需要用多個介面函式進行維護，以實作對資料元素的增刪查改操作，我們定義如下的介面函式型別：

void SeqListCheckCapacity(SL*ps)
//容量判斷函式
void SeqListInit(SL* ps);
//初始化函式
void SwqListDestory(SL*ps);
//銷毀函式
void SeqListPushBack(SL* ps,SLDataType x);
//尾插
void SeqListPopBack(SL* ps);
//尾刪
void SeqListPushFront(SL*ps,SLDataType x);
//頭插
void SeqListPopFront(SL*ps);
//頭刪
int SeqListFind(SL* ps,SLDataType x);
//找到了回傳x位置下標，沒有找到回傳-1
void SeqListInsert(SL*ps,int pos,SLDataType x);
//指定pos下標位置插入
void SeqListErase(SL*ps,int pos);
//洗掉pos位置的資料

容量審查函式：

但是在寫入或者讀出資料之前，我們需要先對線性表空間進行審查，以確定能否進行后續的操作，
函式創建的基本思想：當前存盤資料與容量相等時，說明順序表已經沒有多余空間進行增加操作，那么需要對其擴容，只有在第一次擴容時，容量為4，之后均用當前容量的二倍形式進行擴容，

void SeqListCheckCapacity(SL*ps)
{
    if(ps->size==ps->capacity)
    {
        int newcapacity=ps->capacity==0?4:ps->capacity*2;//三目運算子
        SLDataType *tmp=(SLDataType*)realloc(ps->a,newcapcity*sizeof(SLDataType));//realloc追加記憶體空間進行擴容
        if(tmp==NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a=tmp;
        ps->capacity=newcapaticy;
    }
}

初始化函式：

//初始化函式
void SeqListInit(SL* ps)
{
    ps->a=NULL;
    ps->size=ps->capacity=0;
}//這里要注意，要對結構體進行傳址操作，否則不能進行初始化
//結構體變數本質上是一個變數，不是一個函式，通過函式指標的學習我明白了函式的名字就是函式的地址，當使用回呼函式時可以&函式名 也可以不進行取地址操作，但對于一個變數來說，必須進行傳址操作才能改變其值

銷毀函式：

當使用完記憶體之后，需要對順序表申請的記憶體空間進行銷毀，以防止記憶體泄漏，

//銷毀函式
void SeqlistDestory(SL*ps)
{
    free( ps->a);
    ps->a=NULL;
    ps->sz=ps->capacity=0;
}

尾插函式:

對于一個動態的順序表來說，尾插一種重要的元素增加方式，但在尾插之前我們需要檢查當前順序表的容量是否已滿，元素插入的思想便是向陣列末尾進行插入資料，注意：size表示的是陣列長度，而對應的最后一個元素的角標應是size-1

void SeqListPushBack(SL* ps,SLDataType x)//尾插
{
    //首先要判斷當前空間夠不夠用
    //第一種情況：第一次插入之前，是空的陣列
    //第一種情況：當前空間不夠
    //第三種情況：當前空間足夠
    //通過呼叫容量檢查函式檢查空間是否足夠
    SeqListCheckCapacity(pc);
    ps->a[ps->size]=x;
    ps->size++;
}

尾刪函式：

尾刪函式的基本思想更為簡單，只需要對size維護空間進行縮小，即對size以外的內容不進行訪問就完成了洗掉操作，

void SeqListPopBack(SL* ps);//尾刪
{
    //最基本的思想就是將ps->a[ps->sz-1]的位置上的元素置零 //然后對ps->sz進行減一操作，
    //但是事實上僅對size進行——操作就行，但是當size為0的時候就不能進行洗掉了，//所以要對size為0的極限情況進行限制
    if(ps->size>0)
    {
        ps->size--;
    }
    //或者用assert 方法
    /*assert(ps->size>0);
    ps->size--;*/
}

頭插函式：

連續存盤的所有資料結構的所有的插入函式在插入元素之前，都需要對容量進行判定，以確定是否可以進行插入操作，頭插的基本思想與尾插類似，只不過需要對資料元素進行相鄰賦值，最后將第一塊空間騰出來以進行頭插，所有插入函式結束之后，不要忘記對size+1，

void SeqListPushFront(SL*ps,SLDataType x)//頭插
{
    SeqListCheckCapacity(ps);
    //基本思想就是從陣列的最后向后移動，依次移動一個單位
    //每移動一次 end指標減一 當end指標為0時，跳出回圈
    //此時陣列的第一個元素空了出來，我們可以對其進行賦值
    //當插入之后有效容量就會加一，size就要進行加一
    int end=ps->size-1;
    while(end)
    {
        ps->a[end+1]=ps->a[end];
        end--;
    }
    ps->a[0]=x;
    ps->size++;//頭插之后容量變大 size表示的是實際的有效資料的容量
}

頭刪函式：

在頭刪時，要將元素從后向前的覆寫，最終使得size-1，需要注意begin變數的起始位置，這里給出了begin從第二個元素開始的情況，若設定begin為0，那么相應的回圈終止條件也要發生改變，

void SeqListPopFront(SL*ps)//頭刪
{
    assert(ps->size>0);
    //挪動資料
    int begin=1;
    while(begin< ps->size)
    {
        ps->a[begin -1]=ps->a[begin];//向前賦值
        begin++;
    }
    ps->size--;
}

尋找函式:

使用for回圈對順序表元素進行遍歷尋找，當所需目標元素在順序表內時回傳其角標，反之回傳-1

int SeqListFind(SL* ps,SLDataType x)
{
    SeqListCheckCapacity(ps);
    int i=ps->size-1;
    for(i=ps->size-1;i>=0;i--)
    {
        if(x==ps->a[i])
        {
            printf("找到了，為第%d個元素",i);
            return i;
            break;
        }
        
    }
    return -1;
}

指定下標插入：

這里采用回圈的方式進行空間轉換，通過回圈將元素相鄰從左向右賦值，最終將所指定位置空出，將指定下標的元素插入

void SeqListInsert(*SL ps,int pos,SLDataType x)
{
    SeqListCheckCapacity(ps);
    assert(pos<ps->size || pos>=0);
    int end=ps->size-1;
    if(pos<ps->size)
    {
        int turn=ps->size-pos;//控制跳出回圈條件就是插入位置到末尾的距離
        while(turn)
        {
            ps->a[end+1]=ps->a[end];
            end--;//end做減法來不斷的向前移動進行前后位賦值
            turn--;
        }
        ps->a[pos]=x;
        ps->size++;
    }
    else if(pos==ps->size)
    {
        ps->a[end+1]=ps->a[end];
        ps->a[end]=x;
        ps->size++;
    }
    else 
    {
        printf("越界插入，錯誤");
        exit(-1);
    }
    
}

洗掉指定下標元素：

洗掉指定下標元素時，給出了第二種指定下標的寫法，即從指定下標pos的下一個位置開始進行回圈，將pos位置資料進行覆寫，最終size-1，完成指定下標的元素洗掉

void SeqListErase(SL*ps,int pos)
{
    assert(pos>=0||pos<ps->size);
    
    int begin=pos+1;
    while(begin<ps->size)
    {
        ps->a[begin-1]=ps->a[begin];
        begin++;
    }
    ps->size--;
}

小結

綜上，我們對順序表的結構就有了一個宏觀的認識，從邏輯上來說，順序表本質上是一種陣列的變型，即用各種介面函式對順序表整個動態的陣列進行動態維護，從代碼實作角度，我們用結構體定義了順序表的基本內容：用于空間申請的指標、當前存盤量size、與整體容量capacity，并定義了多種介面函式用于對順序表的增刪查改，需要注意的是，在結構體物體化時，結構體變數仍是一個變數，若需要對其進行值的修改操作，必須進行傳址操作，當完成順序表存盤功能后，需要對其進行銷毀，必須要對申請的記憶體空間進行釋放，以避免記憶體泄漏而產生的不可預知的錯誤，

希望本文能對你有所幫助??，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/333794.html

標籤：其他

上一篇：【C語言】??動態記憶體管理及相關函式

下一篇：資料結構學習筆記--堆疊

【C資料結構】什么是順序表？一文迅速搞懂！