資料結構之連結清單 一、概念 二、代碼 三、練習

（1）數組的線性序是由數組的下标決定的，連結清單中的順序是由各對象中的指針所決定的

（2）連結清單結點結構

node *prev;

node *next;

int key;

（3）連結清單結點

node *head;

node *nil;//哨兵

（4）對連結清單的操作

list-search(l, k)

list-insert(l, x)

list-delete(l, x)

（5）哨兵是個啞對象，可以簡化邊界條件

//連結清單結點結構  

struct node  

{  

    node *pre;  

    node *next;  

    int key;  

    //構造函數  

    node(int x):pre(null),next(null),key(x){}  

};  

//連結清單結構  

struct list  

    node *head;  

    list():head(null){}  

//列印  

void list_print(list *l)  

    node *p = l->head;  

    while(p)  

    {  

        cout<<p->key<<' ';  

        p = p->next;  

    }  

    cout<<endl;  

}  

//搜尋，找出l中第一個關鍵字為k的結點，沒有則傳回null  

node *list_search(list *l, int k)  

    node *x = l->head;  

    while(x != null && x->key!=k)  

        x = x->next;  

    return x;  

//插入  

void list_insert(list *l, node *x)  

    //插入到表的前端  

    x->next = l->head;  

    if(l->head != null)  

        l->head->pre = x;  

    l->head = x;  

    x->pre = null;  

//删除  

void list_delete(list *l, node* x)  

    if(x->pre != null)  

        x->pre->next = x->next;  

    else  

        l->head = x->next;  

    if(x->next != null)  

        x->next->pre = x->pre;  

    delete x;  

    node *nil;//哨兵  

    list()  

        nil = new node(0);  

        nil->next = nil;  

        nil->pre = nil;  

    node *p = l->nil->next;  

    while(p != l->nil)  

    node *x = l->nil->next;  

    while(x != l->nil && x->key!=k)  

    x->next = l->nil->next;  

    l->nil->next->pre = x;  

    l->nil->next = x;  

    x->pre = l->nil;  

    x->pre->next = x->next;  

    x->next->pre = x->pre;  

10.2-1  

能，能  

10.2-2  

//結點  

    node *pre;//為了友善實作出棧操作  

//鍊式棧  

    node *head;//棧的起始結點  

    node *top;//棧頂指針  

    list(){head = new node(0);top = head;}  

//列印棧中的元素  

void print(list *l)  

    node *p = l->head->next;  

//入棧  

void push(list *l, int x)  

    //構造一個新的結點  

    node *a = new node(x);  

    //鍊入到棧頂位置，修改指針  

    l->top->next = a;  

    a->pre = l->top;  

    l->top = a;  

//出棧  

int pop(list *l)  

    if(l->head == l->top)  

        cout<<"error:underflow"<<endl;  

        return -1;  

    //取出棧頂元素  

    int ret = l->top->key;  

    //修改指針  

    node *a = l->top;  

    l->top = a->pre;  

    l->top->next = null;  

    delete a;  

    return ret;  

10.2-3  

    node(int x):next(null),key(x){}  

//鍊式隊列  

    node *head;//頭指針  

    node *tail;//尾指針  

    list(){head = new node(0);tail = head;}  

//入隊列  

void enqueue(list *l, int x)  

    //鍊入尾部，修改指針  

    l->tail->next = a;  

    l->tail = a;  

//出隊列  

int dequeue(list *l)  

    if(l->head == l->tail)  

    //取出隊頭結點，修改指針  

    node *a = l->head->next;  

    int ret = a->key;  

    l->head->next = a->next;  

    if(a == l->tail)  

        l->tail = l->head;  

10.2-4  

把哨兵的值置為一個不可能與x相等的值  

10.2-5

10.2-6

使用帶尾指針的連結清單，令a的尾指針為tail，tail->next=b

10.2-7

//逆轉  

void reverse(list *l)  

    node *p = null, *q = l->head, *r;  

    //依次修改指針，讓q是p->next,令q->next=p  

    while(1)  

        r = q->next;  

        q->next = p;  

        if(r == null)  

        {  

            l->head = q;  

            break;  

        }  

        p = q;  

        q = r;