【揭秘C語言中的鏈表與隊列】高效數據結構實戰指南

引言

在打算機科學中，數據構造是構造跟存儲數據的方法，它直接影響着算法的機能跟順序的效力。鏈表跟行列是兩種罕見且重要的數據構造，它們在C言語中有着廣泛的利用。本文將深刻探究鏈表跟行列在C言語中的實現，並分析它們的上風跟實用處景。

鏈表

1. 鏈表概述

鏈表是一種線性數據構造，由一系列節點構成，每個節點包含數據跟指向下一個節點的指針。鏈表的重要長處是拔出跟刪除操縱機動，不須要挪動其他元素。

2. 單鏈表實現

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void appendNode(Node* head, int data) {
    Node* newNode = createNode(data);
    if (!head) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = newNode;
}

void printList(Node* head) {
    Node* temp = head;
    while (temp) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

3. 雙鏈表實現

雙鏈表是單鏈表的擴大年夜，每個節點包含兩個指針，一個指向前一個節點，一個指向下一個節點。

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

void insertBefore(Node* prevNode, int data) {
    Node* newNode = createNode(data);
    newNode->next = prevNode;
    newNode->prev = prevNode->prev;
    if (prevNode->prev) {
        prevNode->prev->next = newNode;
    }
    prevNode->prev = newNode;
}

行列

1. 行列概述

行列是一種進步先出（FIFO）的數據構造，容許在一端拔出元素（隊尾）跟在另一端刪除元素（隊頭）。

2. 行列實現

#include <stdio.h>
#include <stdlib.h>

typedef struct Queue {
    Node* head;
    Node* tail;
} Queue;

void QueueInit(Queue* q) {
    q->head = NULL;
    q->tail = NULL;
}

void QueuePush(Queue* q, int data) {
    Node* newNode = createNode(data);
    if (!q->tail) {
        q->head = q->tail = newNode;
        return;
    }
    q->tail->next = newNode;
    newNode->prev = q->tail;
    q->tail = newNode;
}

int QueuePop(Queue* q) {
    if (!q->head) {
        printf("Queue is empty\n");
        return -1;
    }
    int data = q->head->data;
    Node* temp = q->head;
    q->head = q->head->next;
    if (q->head) {
        q->head->prev = NULL;
    } else {
        q->tail = NULL;
    }
    free(temp);
    return data;
}

總結

鏈表跟行列是C言語中常用的數據構造，它們在處理靜態數據時表示出色。經由過程本文的介紹，讀者應當可能懂得鏈表跟行列的基本不雅點跟實現方法，並可能在現實項目中利用它們。