數(shù)據(jù)結(jié)構(gòu)教程第九課循環(huán)鏈表與雙向鏈表

本課主題： 循環(huán)鏈表與雙向鏈表
    教學(xué)目的： 掌握循環(huán)鏈表的概念，掌握雙向鏈表的的表示與實現(xiàn)
    教學(xué)重點： 雙向鏈表的表示與實現(xiàn)
    教學(xué)難點： 雙向鏈表的存儲表示
    授課內(nèi)容：
    一、復(fù)習(xí)線性鏈表的存儲結(jié)構(gòu)
    二、循環(huán)鏈表的存儲結(jié)構(gòu)
    循環(huán)鏈表是加一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的特點是表中后一個結(jié)點的指針域指向頭結(jié)點。
    循環(huán)鏈表的操作和線性鏈表基本一致，差別僅在于算法中的循環(huán)條件不是p或p->next是否為空，而是它們是否等于頭指針。
    三、雙向鏈表的存儲結(jié)構(gòu)
    提問：單向鏈表的缺點是什么？
    提示：如何尋找結(jié)點的直接前趨。
    雙向鏈表可以克服單鏈表的單向性的缺點。
    在雙向鏈表的結(jié)點中有兩個指針域，其一指向直接后繼，另一指向直接前趨。
    1、線性表的雙向鏈表存儲結(jié)構(gòu)
    typedef struct DulNode{
    struct DulNode *prior;
    ElemType data;
    struct DulNode *next;
    }DulNode,*DuLinkList;
    對指向雙向鏈表任一結(jié)點的指針d，有下面的關(guān)系：
    d->next->priou=d->priou->next=d
    即：當(dāng)前結(jié)點后繼的前趨是自身，當(dāng)前結(jié)點前趨的后繼也是自身。
    2、雙向鏈表的刪除操作
    Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
    if(!(p=GetElemP_DuL(L,i)))
    return ERROR;
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->pror;
    free(p);
    return OK;
    }//ListDelete_DuL
    3、雙向鏈表的插入操作
    Status ListInsert_DuL(DuLinkList &L,int i,ElemType &e){
    if(!(p=GetElemP_DuL(L,i)))
    return ERROR;
    if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
    s->data=e;
    s->prior=p->prior;
    p->prior->next=s;
    s->next=p;
    p->prior=s;
    return OK;
    }//ListInsert_DuL 四、一個完整的帶頭結(jié)點的線性邊表類型定義：
    typedef struct LNode{
    ElemType data;
    struct LNode *next;
    }*Link,*Position;
    typedef struct{
    Link head,tail;
    int len;
    }LinkList;
    Status MakeNode(Link &p,ElemType e);
    //分配由p指向的值為e的結(jié)點，并返回OK；若分配失敗，則返回ERROR
    void FreeNode(Link &p);
    //釋放p所指結(jié)點
    Status InitLinst(LinkList &L);
    //構(gòu)造一個空的線性鏈表L
    Status DestroyLinst(LinkList &L);
    //銷毀線性鏈表L，L不再存在
    Status ClearList(LinkList &L);
    //將線性鏈表L重置為空表，并釋放原鏈表的結(jié)點空間
    Status InsFirst(Link h,Link s);
    //已知h指向線性鏈表的頭結(jié)點，將s所指結(jié)點插入在第一個結(jié)點之前
    Status DelFirst(Link h,Link &q);
    //已知h指向線性鏈表的頭結(jié)點，刪除鏈表中的第一個結(jié)點并以q返回
    Status Append(LinkList &L,Link s);
    //將指針s所指(彼此以指針相鏈)的一串結(jié)點鏈接在線性鏈表L的后一個結(jié)點
    //之后，并改變鏈表L的尾指針指向新的尾結(jié)點
    Status Remove(LinkList &L,Link &q);
    //刪除線性鏈表L中的尾結(jié)點并以q返回，改變鏈表L的尾指針指向新的尾結(jié)點
    Status InsBefore(LinkList &L,Link &p,Link s);
    //已知p指向線性鏈表L中的一個結(jié)點，將s所指結(jié)點插入在p所指結(jié)點之前，
    //并修改指針p指向新插入的結(jié)點
    Status InsAfter(LinkList &L,Link &p,Link s);
    //已知p指向線性鏈表L中的一個結(jié)點，將s所指結(jié)點插入在p所指結(jié)點之后，
    //并修改指針p指向新插入的結(jié)點
    Status SetCurElem(Link &p,ElemType e);
    //已知p指向線性鏈表中的一個結(jié)點，用e更新p所指結(jié)點中數(shù)據(jù)元素的值
    ElemType GetCurElem(Link p);
    //已知p指向線性鏈表中的一個結(jié)點，返回p所指結(jié)點中數(shù)據(jù)元素的值
    Status ListEmpty(LinkList L);
    //若線性鏈表L為空表，則返回TRUE,否則返回FALSE
    int ListLength(LinkList L);
    //返回線性鏈表L中的元素個數(shù)
    Position GetHead(LinkList L);
    //返回線性鏈表L中頭結(jié)點的位置
    Position GetLast(LinkList L);
    //返回線性鏈表L中后一個結(jié)點的位置
    Position PriorPos(LinkList L,Link p);
    //已知p指向線性鏈表L中的一個結(jié)點，返回p所指結(jié)點的直接前趨的值
    //若無前趨，返回NULL
    Position NextPos(LinkList L,Link p);
    //已知p指向線性鏈表L中的一個結(jié)點，返回p所指結(jié)點的直接后繼的值
    //若無后繼，返回NULL
    Status LocatePos(LinkList L,int i,Link &p);
    //返回p指示線性鏈表L中第i個結(jié)點的位置并返回OK,i值不合法時返回ERROR
    Position LocateElem(LinkList L,ElemType e,
    Status(*compare)(ElemType,ElemType));
    //返回線性鏈表L中第1個與e滿足函數(shù)compare()判定關(guān)系的元素的位置，
    //若下存在這樣的元素，則返回NULL
    Status ListTraverse(LinkList L,Status(*visit)());
    //依次對L的每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。
    五、總結(jié)本課內(nèi)容
    循環(huán)鏈表的存儲結(jié)構(gòu)
    雙向鏈表的存儲結(jié)構(gòu)