數(shù)據(jù)結(jié)構(gòu)教程第十三課隊列

教學(xué)目的： 掌握隊列的類型定義,掌握鏈隊列的表示與實現(xiàn)方法
    教學(xué)重點： 鏈隊列的表示與實現(xiàn)
    教學(xué)難點： 鏈隊列的表示與實現(xiàn)
    授課內(nèi)容：
    一、隊列的定義:
    隊列是一種先進先出的線性表。它只允許在表的一端進行插入，而在另一端刪除元素。象日常生活中的排隊，早入隊的早離開。
    在隊列中，允許插入的的一端叫隊尾，允許刪除的一端則稱為隊頭。
    抽象數(shù)據(jù)類型隊列:
    ADT Queue{
    數(shù)據(jù)對象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
    數(shù)據(jù)關(guān)系: R1={ | ai-1,ai(- D,i=2,...,n}
    基本操作：
    InitQueue(&Q) 構(gòu)造一個空隊列Q
    Destroyqueue(&Q) 隊列Q存在則銷毀Q
    ClearQueue(&Q) 隊列Q存在則將Q清為空隊列
    QueueEmpty(Q) 隊列Q存在,若Q為空隊列則返回TRUE,否則返回FALSE
    QueueLenght(Q) 隊列Q存在,返回Q的元素個數(shù),即隊列的長度
    GetHead(Q,&e) Q為非空隊列,用e返回Q的隊頭元素
    EnQueue(&Q,e) 隊列Q存在,插入元素e為Q的隊尾元素
    DeQueue(&Q,&e) Q為非空隊列,刪除Q的隊頭元素,并用e返回其值
    QueueTraverse(Q,vivsit()) Q存在且非空,從隊頭到隊尾,依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗
    }ADT Queue 二、鏈隊列－隊列的鏈式表示和實現(xiàn)
    用鏈表表示的隊列簡稱為鏈隊列。一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針。 鏈隊列表示和實現(xiàn)：
    //存儲表示
    typedef struct QNode{
    QElemType data;
    struct QNode *next;
    }QNode,*QueuePtr;
    typedef struct{
    QueuePtr front;
    QueuePtr rear;
    }LinkQueue;
    //操作說明
    Status InitQueue(LinkQueue &Q)
    //構(gòu)造一個空隊列Q
    Status Destroyqueue(LinkQueue &Q)
    //隊列Q存在則銷毀Q
    Status ClearQueue(LinkQueue &Q)
    //隊列Q存在則將Q清為空隊列
    Status QueueEmpty(LinkQueue Q)
    // 隊列Q存在,若Q為空隊列則返回TRUE,否則返回FALSE
    Status QueueLenght(LinkQueue Q)
    // 隊列Q存在,返回Q的元素個數(shù),即隊列的長度
    Status GetHead(LinkQueue Q,QElemType &e)
    //Q為非空隊列,用e返回Q的隊頭元素
    Status EnQueue(LinkQueue &Q,QElemType e)
    //隊列Q存在,插入元素e為Q的隊尾元素
    Status DeQueue(LinkQueue &Q,QElemType &e)
    //Q為非空隊列,刪除Q的隊頭元素,并用e返回其值
    Status QueueTraverse(LinkQueue Q,QElemType vivsit())
    //Q存在且非空,從隊頭到隊尾,依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗
    //操作的實現(xiàn)
    Status InitQueue(LinkQueue &Q) {
    //構(gòu)造一個空隊列Q
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)exit(OVERFLOW);
    Q.front->next=NULL;
    return OK;}
    Status Destroyqueue(LinkQueue &Q) {
    //隊列Q存在則銷毀Q
    while(Q.front){
    Q.rear=Q.front->next;
    free(Q.front);
    Q.front=Q.rear;
    } return OK;}
    Status EnQueue(LinkQueue &Q,QElemType e) {
    //隊列Q存在,插入元素e為Q的隊尾元素
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data=e;p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;}
    Status DeQueue(LinkQueue &Q,QElemType &e) {
    //Q為非空隊列,刪除Q的隊頭元素,并用e返回其值
    if(Q.front==Q.rear)return ERROR;
    p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)Q.rear=Q.front;
    free(p);
    return OK;}
    三、總結(jié)
    鏈隊列的存儲表示
    鏈隊列的操作及實現(xiàn)