队列(Queue): 具有一定约束的线性表。

• 插入和删除操作：只能在一端插入，在另一端删除。
• 数据插入：入队列
• 数据删除：出队列
• 先进先出：FIFO

1. 队列的顺序存储实现

• 队列的顺序存储通常使用一个数组和一个标识队头front和队尾rear的变量实现。

  
  

struct QNode{
    ElementType data[MAXSIZE];
    int front;
    int rear;
};
typedef struct QNode* Queue;

• 当rear到达数组最大索引的时候，但是出栈了一些元素时，数组不能充分被使用。 因此引入了循环队列。

循环队列：

• 我们仅凭front == rear是不能判别队列是否已满的。我们可以用size或tag来区分。
• 其次我们可以少用一个元素空间，约定队头front在队尾rear的下一个位置，作为队列满的状态标志。

1. 入队列
void EnQueue(Queue ptrQ,ElementType item)
{
    if((ptrQ->rear + 1) % MAXSIZE == ptrQ->front)
    {
        printf("队列已满")；
        return;
    }
    ptrQ->rear = (ptrQ->rear + 1) % MAXSIZE;
    ptrQ->data[ptrQ->rear] = item;
}
2. 出队列
ElementType DeQueue(Queue ptrQ)
{
    if(ptrQ->front == ptrQ->rear)
    {
        printf("队列空");
        return NULL;
    }
    ptrQ->front = (ptrQ->front + 1) % MAXSIZE;
    return ptrQ->data[ptrQ->front];
}

2. 队列的链式存储实现

• 队列的链式存储也可以用单链表实现。插入和删除可以在链表的两头进行。队列的front和rear分别在链表头和链表尾。

  
  

struct Node{
    ElementType data;
    struct Node *next;
};

struct QNode{
    struct Node *front;
    struct Node *rear;
};
typedef struct QNode* Queue;

出队列
ElementType DeQueue(Queue ptrQ)
{
    struct Node *frontCell;
    ElementType item;
    if(ptrQ->front == NULL){
        printf("队列空");
        return NULL;
    }
    frontCell = ptrQ->front;
    item = frontCell->data;
    if(ptrQ->front == ptrQ->rear)
        ptrQ->front = ptrQ->rear = NULL;
    else
        ptrQ->front = frontCell -> next;
    free(frontCell);
    return item;
}

3. 多项式加法运算

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

算法思路:两个指针P1和P2分别指向这两个多项式第一个结点，不断循环:

• P1->expon==P2->expon:系数相加，若结果不为0，则作为结果多项式对应项的系数。同时，P1和P2都分别指向下一项;
• P1->expon>P2->expon:将P1的当前项存入结果多项式，并使P1指向下一项;
• P1->expon<P2->expon:将P2的当前项存入结果多项式，并使P2指向下一项;
  当某一多项式处理完时，将另一个多项式的所有结点依次复制到结果多项式中去。

Polynomial PolyAdd(Polynomial p1,Polynomial p2)
{
    Polynomial front,rear,temp;
    int sum;
    rear = (Polynomial)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->coef,&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(temp);
    
    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;
}

多项式乘法
Polynomial Mult(Polynomial p1, Polynomial p2)
{
    Polynomial t1 = p1;
    Polynomial t2 = p2;
    Polynomial p = (Polynomial)malloc(sizeof(struct PolyNode));
    Polynomial rear = p;
    Polynomial t;
    int c, e;
    while (t1) {
        rear = p;
        t2 = p2;
        while (t2) {
            c = t1->coef * t2->coef;
            e = t1->expon * t2->expon;
            while (rear->link && rear->link->expon > e) {
                rear = rear->link;
            }
            
            if(rear->link && rear->link->expon == e){
                if(rear->link->expon + e){
                    rear->link->expon += e;
                }else{
                    t = rear->link;
                    rear->link = t->link;
                    free(t);
                }
            }else{
                t = Polynomial)malloc(sizeof(struct PolyNode));
                t->expon = e;
                t->coef = c;
                t->link = rear->link;
                rear->link = t;
                rear = t;
            }
            t2 = t2->link;
        }
        t1 = t1->link;
    }
    
    t = p;
    p = p->link;
    free(t);
    return p;
}