C/C++ 雙向鏈表實現與排序操作詳解

雙向鏈表基礎結構

雙向鏈表是鏈表的一種變體，每個節點包含指向前驅和後繼節點的指針，使得雙向遍歷成為可能。以下是典型的節點定義：

struct list {
    int data;
    struct list *next;
    struct list *pre;
};
typedef struct list node;
typedef node *link;

核心操作函數

節點插入 (push)

在表尾插入新節點，維護前驅後繼關係：

link push(int item) {
    link newnode = malloc(sizeof(node));
    newnode->data = item;
    if (head == NULL) {
        head = newnode;
        head->next = NULL;
        head->pre = NULL;
        rear = head;
    } else {
        rear->next = newnode;
        newnode->pre = rear;
        newnode->next = NULL;
        rear = newnode;
    }
    return head;
}

遍歷顯示 (display)

從頭節點順序輸出所有數據：

void display(link l) {
    link p = l;
    while (p != NULL) {
        printf("%d->", p->data);
        p = p->next;
    }
}

棧式操作 (pop, tops)

雖然是雙向鏈表，但代碼中也實現了棧的基本操作，以尾節點為棧頂：

int tops() {
    if (empty()) return NULL;
    else return rear->data;
}

void pop() {
    if (empty()) printf("stack is empty!\n");
    else rear = rear->pre;
}

主程序測試

主函數演示了輸入 4 個整數建立鏈表，顯示後執行一次彈出操作：

void main() {
    int n, i;
    printf("input your first data!\n");
    scanf("%d", &n);
    front = push(n);
    for (i = 0; i < 3; i++) {
        printf("input:\n");
        scanf("%d", &n);
        push(n);
    }
    ptr = front;
    display(ptr);
    printf("\n Please enter any key to pop");
    getch();
    pop();
    ptr = front;
    display(ptr);
    getch();
}

總結

此代碼展示了雙向鏈表的基本構建、尾插法插入、順序遍歷以及簡單的棧式尾部刪除。實際應用中可根據需要擴展排序、查找、任意位置插入刪除等功能。