数据结构MOOC|队列

电玩女神 2022-05-25 12:52 187阅读 0赞

课程内容来自： [http://www.icourse163.org/learn/ZJU-93001?tid=1002654021\#/learn/content?type=detail&id=1003620979][http_www.icourse163.org_learn_ZJU-93001_tid_1002654021_learn_content_type_detail_id_1003620979]

## 【队列】 ##

队列：受限的线性表，一端插入（front），一端删除（rear），即FIFO。

操作集：长度MaxSize的队列Q，队列元素item是ElementType类型。

涉及操作：

1.Queue CreatQueue(int MaxSize)：生成长度为MaxSize的空队列；

2.int IsFullQ(Queue Q, int MaxSize)：判断队列Q是否已满；

3.void AddQ(Queue Q, ElementType item)：将数据元素item插入队列Q中；

4.int IsEmptyQ(Queue Q)：判断队列是否为空；

5.ElementType Delete(Queue Q)：将队头数据元素从队列中删除并返回。

## 【队列的顺序存储实现】 ##

//一个一维数组和两个变量rear front
    #define MaxSize
    struct QNode{
        ElementType Data[MaxSize]; 
        int rear;
        int front;
    };

插入元素时rear+1,删除元素时front+1

front==rear时队列为空

### 循环队列 ###

为了避免无法区分队列满和队列空的情况，在循环队列里能够存储元素的最大个数通常是MaxSize-1。

这种情况下，队列空front==rear;队列满front==rear+1。

通过(rear+1)%Maxsize的方式，来决定插入元素的位置。

![20180516102742329][]

入队操作：

void AddQ(Queue PtrQ, ElementType item){
        if((PtrQ->rear+1)% MaxSize == PtrQ->front){
            cout<<"队列满"<<endl;
            return;
        }
        PtrQ->rear = (PtrlQ->rear+1)% MaxSize;
        PtrQ->Data[PtrQ->rear] = item;
    }

出队操作：

ElementType DeleteQ(Queue PtrQ){
        if(PtrQ->front == PtrQ->rear){
            cout<<"队列空"<<endl;
            return ERROR;
        }else{
            PtrQ->front = (PtrQ->front+1)% MaxSize;
            return PtrQ->Data[PtrQ->front];
        }
    }

## 【队列的链式存储实现】 ##

front做删除操作，rear做插入操作。

链表头既可以做插入操作也可以做删除操作，链表尾只能做插入操作(如果做删除操作，则找不到前面的指针）。

故链式存储实现队列时，front只能放在链表头部。

struct Node{
        ElementType Data; 
        struct Node *Next;
    };
    struct QNode{             /*链队列结构*/
        struct Node *rear;
        struct Node *front;
    };
    typedef struct QNode *Queue;
    Queue PtrQ;

不带头结点的链式队列出队操作：

ElementType DeleteQ(Queue PtrQ){
        struct Node *FrontCell;
        ElementType FrontElem;
    
        if(PtrQ->front == NULL){
            cout<<"队列空"<<endl;
            return ERROR;
        }
        FrontCell = PtrQ->front;
        if(PtrQ->front == PtrQ->rear)        /*若队列只有一个元素*/
            PtrQ->front = PtrQ->rear = NULL; /*删除后队列置为空*/
        else
            PtrQ->front = PtrQ->front->Next;
        FrontElem = FrontCell->Data;
        free(FrontCell);         /*释放删除结点空间*/            
        return FrontElem;
    }

## 【应用：多项式加法运算】 ##

采用不带头结点的**单向链表**，按照**指数递减**的顺序排列各项。

struct PolyNode{
        int coef;     //系数
        int expon;    //指数
        struct PolyNode *link; //指向下一个节点的指针
    };
    typedef struct PolyNode *Polynomial;
    Polynomial P1,P2;

算法思路：

![20180516171748516][]

![20180516171758748][]

![20180516171806720][]

PolyNode PolyAdd(PolyNomial P1, PolyNomial P1){
        Polynomial front,rear,tmp;
        int sum;
        rear = (Polymial)malloc(sizeof(struct) PolyNode);
        front = rear; //空的临时结点作为结果多项式链表头
        while(P1 && P2){
            switch(Compare(P1->expon,P2->expon)){
                case 1:
                    Attach(P1->coef,P1->expon,&rear);
                    P1 = P1->link;
                    break;
                case -1:
                    Attach(P2->coef,P2->expon,&rear);
                    P2 = P2->link;
                    break;
                case 0:
                    sum = P1->coef + P2->coef;
                    if(sum) Attach(sum,P1->expon,&rear);
                    P1 = P1->link;
                    P2 = P2->link;
                    break;
            }
        }
        for(;P1;P1 = P1->link) Attach(P1->coef,P1->expon,&rear);
        for(;P2;P2 = P2->link) Attach(P2->coef,P2->expon,&rear);
        rear->link = NULL;
        temp = front;
        front = front->link;
        free(tmp);
        return front;
    }

void Attach(int c, int e, Polynomial *pRear){
        Polynomial P;
        P = (Polynomial)malloc(sizeof(struct PolyNode));
        P->coef = c;
        P->expon = e;
        P->link = NULL;
        (*pRear)->link = P;
        *pRear = P;
    }

[http_www.icourse163.org_learn_ZJU-93001_tid_1002654021_learn_content_type_detail_id_1003620979]: http://www.icourse163.org/learn/ZJU-93001?tid=1002654021#/learn/content?type=detail&id=1003620979
[20180516102742329]: /images/20220525/3a8d184fd11b469991639582dd78a296.png
[20180516171748516]: /images/20220525/3f9a7fb63e96401ba92ad2eb071fe9aa.png
[20180516171758748]: /images/20220525/b0fdc67b2e46432f9ed23c2514f61ee0.png
[20180516171806720]: /images/20220525/2c0f4ac3b60449e9852e05386947e1cc.png