藍橋杯C/C++國賽衝刺打卡3/30 詳情 - 鏈表,Stack,初始化,HarmonyOS,後端開發 mob64ca14144dde 博客

一、鏈表

1.線性鏈表：
鏈表是一組存儲線性表的數據元素存儲單元;
由若干個節點組成，結點包括兩個域:
其中存儲數據元素信息的稱為數據域;存儲直接後繼存儲位置有域稱為指針域。

2.鏈表的基本操作：
（1）鏈表存儲結構

typedef int ElemType;
typedef struct node
{
    ElemType data;  //數據域
    struct node *next;  //指針域
} Node;

（2）單鏈表-初始化

Node* initList()
{
    Node *head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    return head;
}
int main ()
{
    Node *list = initList();
    return 1;
}

（3）單鏈表-頭插法

int insertHead (Node* L, ElemType e)
{
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->next = L->next;
    L->next = p;
}
int main ()
{
    Node *list = initList();

    insertHead(list, 10);
    insertHead(list, 20);
}

（4）單鏈表-遍歷

void listNode (Node* L)
{
    Node *p = L->next;
    while (p != NULL)
    {
        printf ("%dn", p->data) ;
        p = p->next;
    }
    printf("\n");
}

（5）單鏈表-獲取鏈表長度

int listLength (Node *L)
{
    Node *p = L;
    int len = 0;
    while (p != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}

（6）單鏈表-尾插法

Node* get_tail (Node *L)
{
    Node *p = L;
    while (p->next != NULL)
    {
        p = p->next;
    }
    return p;
}

（7）單鏈表-在指定位置插入數據

int insertNode(Node *L, int pos, ElemType e)
{
    Node *p = L;
    int i = 0;
    while(i < pos-1)
    {
        p = p->next;
        i++;
        if (p == NULL)
        return 0;
    }
    Node *q = (Node*)malloc(sizeof(Node));
    q->data = e;
    q->next = p->next;
    p->next = q;
    return 1;
}

（8）單鏈表-刪除節點

int deleteNode(Node *L, int pos)
{
    Node *p = L;
    int i = 0;
    while(i < pos-1)
    {
        p = p->next;
        i++;
        if (p == NULL)
        {
            return 0;
        }
    }
    if(p->next == NULL)
    {
        printf("要刪除的位置錯誤\n");
        return 0;
    }
    Node *q = p->next;
    p->next = q->next;
    free(q);
    return 1;
}

（9）單鏈表-釋放鏈表

void freeList (Node *L)
{
    Node *p = L->next;
    Node *q;
    while (p != NULL)
    {
        q = p->next;
        free (p) ;
        p = q;
    }
    L->next = NULL;
}

3.雙向鏈表：

鏈式存儲結構的節點中只有一個指示直接後繼的指針域,由此,從某個結點出發只能順指針向後尋查其他節點。若要尋查結點的直接前驅、則必須從表頭指針出發。換句話説,在單鏈表中,查找直接後繼的執行時間為O(1),而查找直接前驅的執行時間為O(n)。為克服單鏈表這種單向性的缺點,可利用雙向鏈表。在雙向鏈表的節點中有兩個指針域,一個指向直接後繼,另一個指向直接前驅。

雙向鏈表的結構

typedef int ElemType;

typedef struct node
{
    ElemType data;
    struct node *prev, *next; //prev為前驅結點，next為後繼結點
} Node;

二、棧

1.棧(stack)是限定僅在表尾進行插入或刪除操作的線性表。
因此對棧來説,表尾端有其特殊含義,稱為棧頂(top),相應地,表頭端稱為棧底(bottom)。不含元素的空表稱為空棧。
假設S=(a1,a2,…,an),則稱a1為棧底元素,an為棧頂元素。棧中元素按a1,a2,…,an的次序進棧,退棧的第一個元素應為棧頂元素。換句話説,棧的修改是按照後進先出的原則進行的。
因此,棧又稱為後進先出(Last In First Out,LIFO)的線性表。
棧是限制插入和刪除操作只能在一個位置進行的表,該位置是表的末端,叫作棧頂(top)。對棧的基本操作有進棧(push)和出棧(Pop),前者相當於插入,後者則是刪除最後插入的元素。

2.棧的基本操作：

（1）棧的鏈式結構實現：

typedef int ElemType;
typedef struct stack
{
    ElemType data;
    struct stack *next;
} Stack;

（2）棧的鏈式結構實現-初始化：

typedef int ElemType;
typedef struct stack
{
    ElemType data;
    struct stack *next;
} Stack;
Stack* initStack ()
{
    Stack *s = (Stack*)malloc(sizeof(Stack));
    s->data = 0;
    s->next = NULL;
    return s;
}

（3）棧的鏈式結構實現-判斷棧是否為空

int isEmpty (Stack *s)
{
    if (s->next == NULL)
    {
        printf("空的\n");
        return 1;
    }
    else
    {
        return 0;
    }
}

（4）棧的鏈式結構實現-進棧/壓棧

int push (Stack *s, ElemType e)
{
    Stack *p = (Stack*)malloc(sizeof(Stack));
    p->data = e;
    p->next = s->next;
    s->next = p;
    return 1;
}

（5）棧的鏈式結構實現-出棧

int pop(Stack *s, ElemType *e)
{
    if (s->next == NULL)
    {
        printf("空的\n");
        return 0;
    }
    *e = s->next->data;
    Stack *q = s->next;
    s->next = q->next;
    free (q) ;
    return 1;
}

（6）棧的鏈式結構實現-獲取棧頂元素

int getTop(Stack *s, ElemType *e)
{
    if (s->next == NULL)
    {
        printf("空的\n");
        return 0;
    }
    *e = s->next->data;
    return 1;
}

三、隊列

1.隊列(queue)是一種先進先出的線性表。
它只允許在表的一端進行插入,而在另一端刪除元素。在隊列中,允許插入的一端稱為隊尾,允許刪除的一端則稱為隊頭。假設隊列為q=(a1,a2,…,an),那麼,a1就是隊頭元素,an就是隊尾元素。
隊列中的元素是按照a1,a2,…,an的順序進入的,退出隊列也只能按照這個次序依次退出,也就是説,只有在a1,a2,…,an-1都離開隊列之後,an才能退出隊列。

2.隊列的基本操作：

（1）隊列的鏈式結構-初始化

Queue* initQueue ()
{
    Queue *q = (Queue*) malloc(sizeof (Queue));
    QueueNode *node = (QueueNode*)malloc(sizeof (QueueNode)) ;
    node->data = 0;
    node->next = NULL;
    q->front = node;
    q->rear = node;
    return q;
}

（2）隊列的鏈式結構

typedef struct QueueNode
{
    ElemType data;
    struct QueueNode *next;
} QueueNode;
typedef struct
{
    QueueNode *front;
    QueueNode *rear;
} Queue;

（3）隊列的鏈式結構-初始化

Queue* initQueue ()
{
    Queue *q = (Queue*)malloc(sizeof (Queue));
    QueueNode *node = (QueueNode*)malloc(sizeof (QueueNode));
    node->data = 0;
    node->next = NULL;
    q->front = node;
    q->rear = node;
    return q;
}

（4）隊列的鏈式結構-判斷隊列是否為空

int isEmpty (Queue *q)
{
    if (q->front == q->rear)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

（5）隊列的鏈式結構-入隊

void equeue (Queue *q, ElemType e)
{
    QueueNode *node = (QueueNode*) malloc(sizeof (QueueNode)) ;
    node->data = e;
    node->next = NULL;
    q->rear->next = node;
    q->rear = node;
}

（6）隊列的鏈式結構-出隊

int dequeue(Queue *q, ElemType *e)
{
    QueueNode *node = q->front->next;
    *e = node->data;
    q->front->next = node->next;
    if (q->rear == node)
    {
        q->rear = q->front;
    }
    free (node) ;
    return 1;
}

（7）隊列的鏈式結構-獲取隊頭元素

ElemType getFront (Queue *q)
{
    if (isEmpty (q))
    {
        printf("空的\n");
        return 0;
    }
    return q->front->next->data;
}

四、總結

1.基本操作的實現共性與差異
（1）共性
存儲基礎：鏈表、棧（鏈式）、隊列（鏈式）均基於節點 + 指針的鏈式存儲結構，通過動態內存分配（malloc）創建節點，藉助指針維護元素間的邏輯關係，最終都需通過free釋放內存以避免泄漏。

初始化邏輯：三者初始化均需創建頭節點（或頭指針），並將指針域置空（NULL），為後續操作建立初始的空結構。

遍歷 / 訪問邏輯：都需通過指針遍歷節點實現元素訪問，且訪問過程中需判斷指針是否為空以防止越界。
（2）差異

結構	核心操作位置	核心操作	時間複雜度（核心操作）	典型應用場景
單鏈表	任意位置	頭插、尾插、指定位置插入 / 刪除	插入 / 刪除 O (1)（已知位置）、遍歷 O (n)	動態數據存儲、不定長數據管理
雙向鏈表	任意位置	前驅 / 後繼節點的查找與操作	查找前驅 O (1)、其他同單鏈表	需頻繁查找前驅的場景（如鏈表排序）
棧（鏈式）	棧頂	壓棧、出棧	壓棧 / 出棧 O (1)	表達式求值、函數調用棧、回溯算法
隊列（鏈式）	隊尾（插入）、隊頭（刪除）	入隊、出隊	入隊 / 出隊 O (1)	任務排隊、消息隊列、廣度優先搜索

2.實現中的注意事項與易錯點
(1)內存管理：鏈式結構中每次創建節點都需通過malloc分配內存，操作完成後必須通過free釋放節點，否則會導致內存泄漏；同時需避免野指針。

(2)邊界條件判斷：

鏈表：插入 / 刪除時需判斷位置是否合法、遍歷到鏈表尾部時需判斷p->next是否為空；

棧：出棧和獲取棧頂元素時需先判斷棧是否為空；

隊列：出隊時需判斷隊列是否為空，且當最後一個節點出隊時需將隊尾指針重置為隊頭指針，避免野指針。

(3)指針操作順序：插入節點時需先維護後繼節點的指針關係，再修改前驅節點的指針，否則會導致鏈表斷裂。

本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。

mob64ca14144dde 博客

mob64ca14144dde 博客

博客 / 詳情