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

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