一、數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)和組織數(shù)據(jù)的方式。常用的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組（Array）、棧（Stack）、隊(duì)列（Queue）、鏈表（Linked List）、樹（Tree）、圖（Graph）、堆（Heap）等；而數(shù)據(jù)結(jié)構(gòu)又可以通過邏輯結(jié)構(gòu)與物理結(jié)構(gòu)進(jìn)行分類，邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，也就是數(shù)據(jù)元素之間的邏輯排列方式。常見的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)等。物理結(jié)構(gòu)是指數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)方式，常見的物理結(jié)構(gòu)包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

二、順序表簡(jiǎn)介

線性表是一種數(shù)據(jù)結(jié)構(gòu)，線性表是具有相同特性的數(shù)據(jù)結(jié)構(gòu)的集合。而它的物理結(jié)構(gòu)上不一定連續(xù)，但是在邏輯結(jié)構(gòu)上抽象為線性結(jié)構(gòu)，一定是連續(xù)的。常見線性表有順序表、鏈表、棧、隊(duì)列、字符串等。今天我們將介紹順序表

順序表是線性表的一種，他在邏輯結(jié)構(gòu)和物理結(jié)構(gòu)上都連續(xù)，且為線性。順序表的本質(zhì)是數(shù)組。

三、順序表的分類

順序表可以分為靜態(tài)順序表和動(dòng)態(tài)順序表。靜態(tài)順序表是創(chuàng)建結(jié)構(gòu)體時(shí)就開辟了固定的一塊空間，而動(dòng)態(tài)順序表則是在使用時(shí)再主動(dòng)申請(qǐng)空間。很明顯，靜態(tài)順序表的缺陷是我們?cè)谝婚_始就將它所需要的空間固定下來了，如果它的空間過小，我們?cè)诖鎯?chǔ)數(shù)據(jù)時(shí)就會(huì)遺漏泄露數(shù)據(jù)，如果它的空間過大，則會(huì)浪費(fèi)空間。而動(dòng)態(tài)順序表可以按需索取空間，動(dòng)態(tài)順序表可以動(dòng)態(tài)地進(jìn)行增容或者刪減。

下面我們來看一下代碼表示。

1、靜態(tài)順序表

typedef int Datatype//我們將int 重新命名，這樣可以方便我們更換數(shù)據(jù)類型

typedef struct SeqList
{
    int arr[10];//假設(shè)在內(nèi)存靜態(tài)區(qū)開辟固定的10個(gè)整形字節(jié)大小的空間
    int size;//順序表中數(shù)據(jù)個(gè)數(shù)
    int capacity;//順序表的容量，取決于arr[]的大小
}SL;

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

typedef int Datatype//我們將int 重新命名，這樣可以方便我們更換數(shù)據(jù)類型

typedef struct SeqList
{
    int* arr;//定義一個(gè)指針，用于之后申請(qǐng)和更改空間
    int size;//順序表中數(shù)據(jù)個(gè)數(shù)
    int capacity;//順序表的容量
}SL;

四、順序表的基本操作

我們主要介紹動(dòng)態(tài)順序表的基本操作，靜態(tài)順序表的操作可以參考靜態(tài)數(shù)組的做法。

1.動(dòng)態(tài)順序表的初始化

由于動(dòng)態(tài)順序表內(nèi)涵指針，所以我們需要對(duì)其中的指針初始化，當(dāng)我們不知道具體需要申請(qǐng)多大空間時(shí)可以賦NULL，也可以用malloc申請(qǐng)空間。

//對(duì)動(dòng)態(tài)順序表進(jìn)行初始化
void SLInit(SL* ps)//傳參為結(jié)構(gòu)體的地址
{
    ps->arr=NULL;//可以賦NULL進(jìn)行初始化，也可以申請(qǐng)空間 ps->arr=(int *)malloc(10*sizeof(int))
    int ps->size=ps->capacity=0;
}

2.動(dòng)態(tài)順序表的銷毀

因?yàn)閯?dòng)態(tài)順序表是在堆區(qū)申請(qǐng)了空間，我們需要手動(dòng)釋放掉這塊空間。

void SLDestory(SL *ps)
{
    if(ps->arr)//判斷ps是否為空指針
    {
        free(ps->arr);//用free函數(shù)對(duì)申請(qǐng)的空間進(jìn)行釋放
    }
    ps->arr=NULL;//賦空指針，防止錯(cuò)誤錯(cuò)誤訪問其它空間
    ps->size=ps->capacity=0;
}

3.尾插與頭插操作以及擴(kuò)容操作

有的時(shí)候我們需要在順序表的末端或者頭部或者其他位置插入一些數(shù)據(jù)，這個(gè)時(shí)候我們就需要頭插與尾插操作等，今天我們先介紹這兩種操作。

1.尾插

尾插，顧名思義，就是在順序表的末端插入新的數(shù)據(jù)，這個(gè)操作看似比較簡(jiǎn)單，但是我們需要考慮到很多問題，比如，是否有足夠空間讓我們插入數(shù)據(jù)？如果空間不夠我們應(yīng)該如何擴(kuò)容？擴(kuò)與尾插后的數(shù)據(jù)個(gè)數(shù)以及空間大小？這些都是我們需要考慮到的問題。

void SLPushBack(SL* ps,Datatype x)//地址傳遞，并且傳遞需要尾插的數(shù)據(jù)
{
    assert(ps);//我們需要對(duì)傳過來的結(jié)構(gòu)體地址判斷是否為空，為空則會(huì)造成空間無法訪問
              //我們可以用到assert斷言，也可以用if進(jìn)行判斷

    //下面我們需要對(duì)順序表的空間進(jìn)行判斷
    if(ps->size==ps->capacity)//如果實(shí)際數(shù)據(jù)個(gè)數(shù)等于我們所申請(qǐng)的空間，那么我們就需要進(jìn)行擴(kuò)容處理
    {
        int newCapacity = ps->arr == 0?4:2 * ps->capacity;
                //判斷arr空間大小，如果為0就假設(shè)給4個(gè)單位的空間，
               //不為0則給兩倍大小的空間（也可以給3倍，按照經(jīng)驗(yàn)給定，不浪費(fèi)也不缺乏）

        Datatype *tmp = (Datatype *)realloc(ps->arr ,newCapacity*sizeof(Datatype));
              //我們先用臨時(shí)指針進(jìn)行擴(kuò)容，因?yàn)閞ealloc有時(shí)申請(qǐng)空間會(huì)失敗。
        if(tmp==NULL)
        {
            perror("realloc fail");
            exit(1);//如果擴(kuò)容失敗，則退出程序
        }
        ps->arr =tmp;//如果成功了就賦給arr
    }
    ps->arr[ps->size++]=x;//此處完成了數(shù)據(jù)個(gè)數(shù)增加和尾插數(shù)據(jù)兩個(gè)操作
}

2.擴(kuò)容

其實(shí)擴(kuò)容是我們?cè)陧樞虮碇薪?jīng)常用到的步驟，我們可以將它寫成一個(gè)函數(shù)，方便我們使用以及簡(jiǎn)化代碼。

void SLCheckCapacity(SL * ps)
{
    assert(ps);
 if(ps->size==ps->capacity)//如果實(shí)際數(shù)據(jù)個(gè)數(shù)等于我們所申請(qǐng)的空間，那么我們就需要進(jìn)行擴(kuò)容處理
    {
        int newCapacity = ps->arr == 0?4:2 * ps->capacity;
                //判斷arr空間大小，如果為0就假設(shè)給4個(gè)單位的空間，
               //不為0則給兩倍大小的空間（也可以給3倍，按照經(jīng)驗(yàn)給定，不浪費(fèi)也不缺乏）

        Datatype *tmp = (Datatype *)realloc(ps->arr ,newCapacity*sizeof(Datatype));
              //我們先用臨時(shí)指針進(jìn)行擴(kuò)容，因?yàn)閞ealloc有時(shí)申請(qǐng)空間會(huì)失敗。
        if(tmp==NULL)
        {
            perror("realloc fail");
            exit(1);//如果擴(kuò)容失敗，則退出程序
        }
        ps->arr =tmp;//如果成功了就賦給arr
    }
}

3.頭插

頭插操作就是在順序表（數(shù)組）的首位插入一個(gè)數(shù)據(jù)，那么我們需要思考如何進(jìn)行操作。首先，為了確保數(shù)據(jù)的完整性，我們需要將arr[0]空出來，那么我們就需要將原順序表的數(shù)據(jù)整體往后挪動(dòng)一個(gè)單位。這里也要涉及空間大小判斷以及數(shù)據(jù)的增加。

void SLPushFront(SL *ps)
{
    assert(ps);
    SLCheckCapacity(ps);//將擴(kuò)容操作寫成一個(gè)函數(shù)會(huì)簡(jiǎn)化很多代碼
    //下面進(jìn)行整體后挪操作
    for(int i=ps->size;i>0;i--)
    {
        ps->arr[i]=ps->arr[i-1];
    }
    //頭插操作
    ps->arr[0] = x;
    ps->size++;//注意插入了數(shù)據(jù),size要增加
}

4.尾刪和頭刪操作

1.尾刪

尾刪操作也很好理解，就是刪除末尾的數(shù)據(jù)，同樣要注意一些細(xì)節(jié)，如順序表大小是否為0，數(shù)據(jù)個(gè)數(shù)要進(jìn)行刪減等

void SLPopBack(SL* ps)//尾刪
{
	assert(ps);//順序表為空不能執(zhí)行刪除,如果空則會(huì)訪問arr[-1]造成越界訪問
	assert(ps->size);//size不能為空
	--ps->size;//此處直接將size的大小減一，同時(shí)也刪除了數(shù)據(jù)
}

2.頭刪

和頭插反著理解，我們要先刪除第一個(gè)數(shù)據(jù)，再將順序表整體前移一個(gè)單位

void SLPopFront(SL* ps)//頭刪
{
	assert(ps);//順序表為空不能執(zhí)行刪除,如果空則會(huì)訪問arr[-1]造成越界訪問
	assert(ps->size);
	
	//數(shù)據(jù)整體往前挪動(dòng)一位
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}

5.打印順序表

我們有的時(shí)候需要一邊對(duì)順序表進(jìn)行操作，一邊要測(cè)試我們的代碼是否正確，除了進(jìn)行調(diào)試外，我們還可以將順序表打印出來直觀地觀察。

void SLPrint(SL ps)//打印，此處我們進(jìn)行值傳遞即可
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
}

以上就是動(dòng)態(tài)順序表的基本操作，感謝各位的瀏覽。希望這篇文章對(duì)你理解和使用順序表有幫助，如有不足或者錯(cuò)誤請(qǐng)指出。文章來源地址http://www.zghlxwxcb.cn/news/detail-853333.html

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