文章目錄

線性結構
- 連結清單
- - 單向連結清單
  - 有序連結清單
  - 循環連結清單
- 堆棧
- - 數組實作
  - 實驗性的面向對象
  - 鍊式堆棧
- 隊列
- - 棧式隊列
  - 鍊式隊列

線性結構

所謂線性結構，用偏數學的觀點來看，其内部資料的關系構成一個有序集合，且這個有序集合中不存在自反性。

如果将這種數學表達執行個體化，可以表述為在這個集合中，所有的元素之間能夠與整數的連續子集建立一一對應的關系，這種情況下即可稱之為線性資料結構。

例如，數組是一種典型的線性結構，對于一個長度為 n n n的數組，其下标便和 [ 0 , n − 1 ] [0,n-1] [0,n−1]構成了一一映射。樹則顯然不是一種線性結構，就樹結構本身而言，對于父節點 S S S來說，其左節點 L L L和右節點 R R R并不能構成統一的偏序關系，除非在樹這個結構上添加一個類似最大堆的預先約定。

按照這種觀點，線性結構的順序關系至少有兩種方式可以實作，其一是數組實作，通過下标與整數的子集形成一一對應；其二則是連結清單實作，通過指向後一個節點的指針來規定節點間的偏序關系。就C語言的特性來說，其固有的數組必須聲明長度，然而指針卻十分寬松，也就是說對于一個新的資料結構，我們可以從數組和指針兩個思路出發。前者即為靜态數組，後者則為動态連結清單，二者結合在一起就是動态數組。

連結清單

單向連結清單

所謂連結清單就是每個節點除了值之外附帶一個連結的表，一般這個連接配接指向下一個節點，進而形成一個有序隊列。

C語言實作連結清單、堆棧和隊列線性結構

如圖所示，其中next指向下一個節點的指針，value為目前節點的值，最後一個節點的

next

值為

NULL

。在這個連結清單中，隻有第一個節點的指針是暴露給我們的入口，其他節點的指針和值都需要通過第一個節點來查找。

這樣的一個節點過指針實作為

//ADT.c
typedef struct NODE{
    struct NODE *next;
    int value;
}Node;

有了第一個節點，我們就可以找到第二個，依次類推，如果想找到第n個節點，也隻需循環n次即可

//列印第n個節點
void printNodeN(Node *preNode,int n){
    for (int i = 0; i < n+1; i++)
        preNode = preNode->next;
    printf("the %dth node is",n,preNode->value);   
}

不過目前我們隻有一個節點，如果希望建立一個新的連結清單，則需要在現有連結清單中添加一個元素。由于連結清單的最後一個節點不指向任何節點，是以我們可以将其設為

NULL

，這樣以來，隻需對現有連結清單進行循環，

next

為

NULL

時，将新節點接入即可。

void addNode(Node *preNode, int val){
    while (preNode->next != NULL)
        preNode = preNode->next;
    //建立新節點，開辟新的記憶體空間
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->value = val;
    newNode->next = preNode->next;  //此值為NULL
    preNode->next = newNode;
}

然後測試一下連結清單

//列印所有節點
void printNode(Node *preNode){
    int i = 0;
    while (preNode->next!=NULL){
        printf("the %dth node:%d\n",i,preNode->value);
        preNode = preNode->next;
        i++;
    }
    printf("the %dth node:%d\n",i,preNode->value);
}
int main(){
    Node *firstNode;
    firstNode->value=0;
    firstNode->next=NULL;
    
    for (int i = 1; i < 6; i++)
        addNode(firstNode,i);//添加節點
    printNode(firstNode);
    return 0;
}

測試

PS E:\Code\AlgC> gcc .\ADT.c
PS E:\Code\AlgC> .\a.exe    
the 0th node:0
the 1th node:1
the 2th node:2
the 3th node:3
the 4th node:4

有序連結清單

這裡的有序指的是連結清單的位置按照其

value

的大小進行排序，對于有序連結清單來說，新插入的節點未必會在原有連結清單的末尾，是以我們需要實作在原有連結清單中插入新值的功能。首先，我們可以改造一下此前的

addNode

函數。

void addNode(Node *preNode, int val, int n){
    int i = 0;
    while (preNode->next != NULL && ++i<n)//先比較，再循環
        preNode = preNode->next;
    
    //建立新節點，開辟新的記憶體空間
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->value = val;
    newNode->next = preNode->next;  //newNode指向preNode後一個元素
    preNode->next = newNode;        //preNode指向newNode
}

這個函數有一個十分顯著的問題，即當

為0時，會将

newNode

插入到1的位置。是以，我們最好在程式的結尾再加一個判斷，當傳入的序号為0時，交換第0個和第1個節點的值,即在函數開始加上一個判斷。

if (n==0){
        int temp = val;
        val = preNode->value;
        preNode->value = temp;
    }

若是在有序清單中插入值，則循環過程中的循環條件變為

while (preNode->next!=NULL && preNode->value<val)

，判斷條件變為

if(preNode->value>val)

。

void addLargerNode(Node *preNode, int val){
    if (preNode->value>val){
        int temp = val;
        val = preNode->value;
        preNode->value = temp;
    }
    
    while (preNode->next!=NULL && preNode->value<val)//先比較，再循環
        preNode = preNode->next;
    
    //建立新節點，開辟新的記憶體空間
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->value = val;
    newNode->next = preNode->next;  //newNode指向preNode後一個元素
    preNode->next = newNode;        //preNode指向newNode
}

循環連結清單

單連結清單隻能從頭部進行通路，如果不小心在其他位置進入，則隻能周遊此後的節點，而對此前的節點無能為力。若想解決這個問題，隻需在節點中加入一個指向前面的指針即可。然而，由于這會改變現有節點的結構，進而影響後面許多其他資料結構的實作，是以從略。

如果不希望增加節點所占用的記憶體，則可以使得連結清單的末尾節點指針指向初始節點。隻不過這樣一來，就無法用空指針來判斷循環終止條件，而是需要儲存起始節點，判斷目前節點的指針是否指向起始節點來進行循環終止判定。

是以，添加節點函數、列印節點函數和主函數改為

void addCircle(Node *preNode, int val){
    Node *firstNode = preNode;
    //當指針指向初始節點時，說明此節點為尾節點
    while (preNode->next != firstNode)
        preNode = preNode->next;
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->value = val;
    newNode->next = preNode->next;
    preNode->next = newNode;
}
//列印所有節點
void printNode(Node *preNode){
    Node* firstNode = preNode;
    int i = 0;
    while (preNode->next!=firstNode){
        printf("the %dth node:%d\n",i,preNode->value);
        preNode = preNode->next;
        i++;
    }
    printf("the %dth node:%d\n",i,preNode->value);
}
int main(){
    Node *firstNode;
    firstNode->value=0;
    firstNode->next=firstNode; //此時隻有一個指向自身的節點
    
    for (int i = 1; i < 5; i++)
        addCircle(firstNode,i);//添加節點
    printNode(firstNode);
    pop(firstNode);
    return 0;
}

測試結果為

PS E:\Code\AlgC> gcc .\ADT.c
PS E:\Code\AlgC> .\a.exe    
the 0th node:0
the 1th node:1
the 2th node:2
the 3th node:3
the 4th node:4

循環連結清單在使用的時候顯得更加靈活，例如，若将尾節點設為入口節點，那麼對于堆棧還有隊列的實作來說是大有幫助的。此時，如果希望增加節點，則隻需在入口節點後面增加即可。如果希望實作棧式彈出，則隻需删除最後一個節點；而若希望實作隊列式删除，則隻需将指針移動到首節點，然後删除即可。

堆棧

數組實作

棧與數組的差別在于，後者是靜态的，即有确定多個元素個數。棧和隊列則為動态數組，前者實作一種先入後出的政策，後者則是先入先出。下圖即棧的一種直覺描述。

C語言實作連結清單、堆棧和隊列線性結構

是以，除了數組的索引功能之外，棧還要求實作壓入和彈出的功能，以實作數組的動态變化。對此，我們隻需在數組之外，額外給出一個指針指向目前數組的末尾即可。

#include<stdio.h>
#define MAXSTACK 100

//無腦棧的實作
typedef struct Stack
{
    int data[MAXSTACK]; //棧最大長度
    int length;         //棧長度
}Stack;

void popStack(Stack *s){
    if(s->length==0)
        printf("overflow");     //棧已空
    else
        s->length--;
}

void pushStack(Stack *s,int data){
    if(s->length==MAXSTACK)
        printf("overflow");     //棧已滿
    else{
        s->data[s->length]=data;
        s->length++;
    }
}

//初始化棧，輸入為數組和數組長度
Stack initStack(int *arr, int n){
    Stack s;
    s.length = 0;
    for (int i = 0; i < n; i++)
        pushStack(&s,arr[i]);

    return s;
}

int main(){
    Stack s;
    int data[10] = {1,2,3,4,5,6,7,8,9,0};
    s = initStack(data,10);
        
    printf("%d\n",s.length);
    for (int i = 0; i < 10; i++){
        printf("s.data[%d]=%d\n",i,s.data[i]);
    }
    
    return 0;    
}

其輸出結果為

E:\Code\AlgC>gcc test.c
E:\Code\AlgC>a
10
s.data[0]=1
s.data[1]=2
...//雷同省略
s.data[9]=0

實驗性的面向對象

上述方式雖然能夠實作壓棧和彈出的操作，但對于熟悉面向對象程式設計的人來說顯然是難以忍受的，即我們并沒有為棧的方法進行良好的封裝。這種封裝在此前可能是無法想象的，好在gcc編譯器已經足夠現代，讓我們可以在結構體中實作類似于成員方法的功能。

//包含成員函數的棧實作
#include<stdio.h>

typedef struct stack{
    int datas[10];
    int length;
    int (*push)(int data);      //成員方法push的函數指針
    int (*pop)();               //成員方法pop的函數指針
}stack;

//push建立函數，輸出為push函數
int (*createPush(int *x, int *length))(int){
    int push(int y){
        x[*length]=y;
        *length=*length+1;
        return 1;
    }
    return *push;
}

//pop建立函數，輸出為pop函數
int (*createPop(int *x, int *length))(int){
    int pop(int y){
        *length=*length-1;
        return 1;
    }
    return *pop;
}

stack Stack(int *arr, int length){
    stack s;
    s.length = 0;
    s.push = createPush(s.datas,&(s.length));
    for (int i = 0; i < length; i++)
        s.push(arr[i]);
    return s;
}

int main(){
    stack s;
    s.length = 0;
    s.push = createPush(s.datas,&(s.length));

    int arr[5] = {1,2,3,4,5};
    for (int i = 0; i < 5; i++)
        s.push(arr[i]);
    
    printf("pushed successfully\n");
    for (int i = 0; i < s.length; i++)
        printf("a[%d]=%d\n",i,s.datas[i]);
    
    s.pop = createPop(s.datas,&(s.length));
    s.pop();
    s.pop();


    printf("poped successfully\n");
    for (int i = 0; i < s.length; i++)
        printf("a[%d]=%d\n",i,s.datas[i]);
    
}

測試

E:\Code\AlgC>a
pushed successfully
a[0]=1
a[1]=2
a[2]=3
a[3]=4
a[4]=5
poped successfully
a[0]=1
a[1]=2
a[2]=3

當然，類似于

int (*push)(int data);

這種寫法，看上去就十分危險，讓人不寒而栗。在結構體中定義指針，使用時稍有不慎就會報錯，在C語言中并不推薦這麼做。而且就性能來說，也額外增添了記憶體的開銷，是十分不劃算的。

鍊式堆棧

通過數組實作棧，最終得到的不過是個僞棧，因為我們還是可以對數組進行通路。相比之下，單向連結清單隻暴露給我們一個初始值，和棧隻暴露給我們頂部的值十分相似，差別隻是在于棧的暴露給我們的是最後壓入的值而已。

是以，棧節點的指針需要指向前一個節點，在此前，我們曾經寫過單向連結清單，其指針為

next

指向下一個節點，友善起見，我們仍用這個詞表示下面的節點。

typedef struct NODE{
    struct NODE *next;
    int value;
}Node;

相應的

push

，

pop

以及列印棧的函數為

//删除棧頂
void pop(Node *top){
    if (top->next!=NULL)
        top->next = top->next->next;
    else
        printf("empty stack");//此時棧已空
}

//傳入棧頂指針和新增值
void push(Node *top, int val){
    Node *new;
    new = (Node*)malloc(sizeof(Node));

    new->value = val;
    if (top->next==NULL)     //此時棧為空
        new->next = NULL;   //新增節點為棧底，故指向空處
    else
        new->next = top->next;  //新節點指向原來棧頂指向的節點
    top->next = new;        //棧頂指向新節點
}
//列印鍊式棧
void printStack(Node *top){
    int i = 0;
    while(top->next!=NULL){
        top = top->next;
        printf("%d\n",top->value);
    }
}

測試一下，主函數為

int main(){
    Node *topNode;      //聲明棧頂
    topNode->next=NULL; //棧頂指向空處，此時為空棧

    //初始化節點
    for (int i = 1; i < 6; i++)
        push(topNode,i);
    printStack(topNode);

    pop(topNode);
    printf("popped\n");
    printStack(topNode);
    return 0;
}

輸出的值為

PS E:\Code\AlgC> gcc .\ADT.c
PS E:\Code\AlgC> .\a.exe    
5
4
3
2
1
popped
4
3
2
1

隊列

棧式隊列

隊列和堆棧的差別在于，後者是采取先入後出的操作原則，前者則是先入先出。就其結構來分析，即棧在删除元素時，隻能從棧頂開始删除，而隊列則從列首開始，是一種先入先出的模式。

C語言實作連結清單、堆棧和隊列線性結構

如果希望通過連結清單的形式實作隊列，則至少有兩個不同的思路，即前向清單和後向清單。前向清單将初始節點暴露給我們，我們在插入新的值時需要周遊所有節點，但是在删除時比較友善，隻需對初始節點執行類似

pop

的操作即可；後向連結清單則相當于堆棧，将棧頂暴露給我們，我們在插入新節點時隻需

push

即可，但是删除節點時需要周遊到隊首。

由于此前已經實作了連結清單和堆棧的代碼，是以下面将隻給對外連結式隊列有關的函數和主函數。

對于"棧"式隊列，我們隻需加入一個删除隊首的操作即可。

typedef struct NODE{
    struct NODE *next;
    int value;
}Node;
void push(Node *top, int val);
void printStack(Node *top);

//删除隊首
void delFirst(Node *top){
    while (top->next->next!=NULL)
        top = top->next;
    free(top->next->next);
    top->next = NULL;
}

int main(){
    Node *topNode;
    topNode->next=NULL;

    
    for (int i = 1; i < 5; i++)
        push(topNode,i);
    printStack(topNode);

    delFirst(topNode);
    printf("popped\n");
    printStack(topNode);
    return 0;
}

輸出結果為

PS E:\Code\AlgC> gcc .\ADT.c
PS E:\Code\AlgC> .\a.exe    
4
3
2
1
popped
4
3
2

即完成了從棧到隊列的更改。

鍊式隊列

對于"鍊"式隊列，其修改方式大同小異，隻需在單項清單實作函數中添加一個删除首節點的函數即可。甚至我們并不需要再寫一個新的函數，隻需把

pop

直接拿過來用即可。

當然，二者之間還有一個細小的差别，此前我們再定義堆棧的時候，預設棧頂節點的值為空，是以再建立

pop

函數的時候并沒有關注其

value

的變化。那麼在建立隊列删除操作時，需要補上這一條

//删除隊首
void pop(Node *top){
    if (top->next!=NULL){
        top->value = top->next->value;
        top->next = top->next->next;
    }
    else
        printf("empty stack");
}
int main(){
    Node *firstNode;
    firstNode->value=0;
    firstNode->next=NULL;
    
    for (int i = 1; i < 5; i++)
        addNode(firstNode,i);//添加節點
    printNode(firstNode);
    pop(firstNode);
    printf("popped\n");
    printNode(firstNode);
    return 0;
}

結果為

PS E:\Code\AlgC> gcc .\ADT.c
PS E:\Code\AlgC> .\a.exe    
the 0th node:0
the 1th node:1
the 2th node:2
the 3th node:3
the 4th node:4
popped
the 0th node:1
the 1th node:2
the 2th node:3
the 3th node:4

C語言實作連結清單、堆棧和隊列線性結構

文章目錄

線性結構

連結清單

單向連結清單

有序連結清單

循環連結清單

堆棧

數組實作

實驗性的面向對象

鍊式堆棧

隊列

棧式隊列

鍊式隊列

繼續閱讀

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

【資料結構】醫院選址

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

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

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

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

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

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

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

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

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

結構體：typedef與struct的差別

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

詳解STM32單片機的堆棧

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

hdu7108哈希