隊(duì)列(Queue): 具有一定約束的線性表湘今。
- 插入和刪除操作：只能在一端插入，在另一端刪除剪菱。
- 數(shù)據(jù)插入：入隊(duì)列
- 數(shù)據(jù)刪除：出隊(duì)列
- 先進(jìn)先出：FIFO
1. 隊(duì)列的順序存儲(chǔ)實(shí)現(xiàn)
-
隊(duì)列的順序存儲(chǔ)通常使用一個(gè)數(shù)組和一個(gè)標(biāo)識(shí)隊(duì)頭front和隊(duì)尾rear的變量實(shí)現(xiàn)摩瞎。
struct QNode{
ElementType data[MAXSIZE];
int front;
int rear;
};
typedef struct QNode* Queue;
- 當(dāng)rear到達(dá)數(shù)組最大索引的時(shí)候，但是出棧了一些元素時(shí)孝常，數(shù)組不能充分被使用愉豺。 因此引入了循環(huán)隊(duì)列。
循環(huán)隊(duì)列：
- 我們僅憑front == rear是不能判別隊(duì)列是否已滿的茫因。我們可以用size或tag來(lái)區(qū)分蚪拦。
- 其次我們可以少用一個(gè)元素空間，約定隊(duì)頭front在隊(duì)尾rear的下一個(gè)位置，作為隊(duì)列滿的狀態(tài)標(biāo)志驰贷。
1. 入隊(duì)列
void EnQueue(Queue ptrQ,ElementType item)
{
if((ptrQ->rear + 1) % MAXSIZE == ptrQ->front)
{
printf("隊(duì)列已滿")盛嘿；
return;
}
ptrQ->rear = (ptrQ->rear + 1) % MAXSIZE;
ptrQ->data[ptrQ->rear] = item;
}
2. 出隊(duì)列
ElementType DeQueue(Queue ptrQ)
{
if(ptrQ->front == ptrQ->rear)
{
printf("隊(duì)列空");
return NULL;
}
ptrQ->front = (ptrQ->front + 1) % MAXSIZE;
return ptrQ->data[ptrQ->front];
}
2. 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)
-
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)也可以用單鏈表實(shí)現(xiàn)。插入和刪除可以在鏈表的兩頭進(jìn)行括袒。隊(duì)列的front和rear分別在鏈表頭和鏈表尾次兆。
struct Node{
ElementType data;
struct Node *next;
};
struct QNode{
struct Node *front;
struct Node *rear;
};
typedef struct QNode* Queue;
出隊(duì)列
ElementType DeQueue(Queue ptrQ)
{
struct Node *frontCell;
ElementType item;
if(ptrQ->front == NULL){
printf("隊(duì)列空");
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. 多項(xiàng)式加法運(yùn)算
struct PolyNode{
int coef; //系數(shù)
int expon; //指數(shù)
struct PolyNode *link; //指向下一個(gè)節(jié)點(diǎn)的指針
}
typedef struct PolyNode* Polynomial;
Polynomial p1, p2;
算法思路:兩個(gè)指針P1和P2分別指向這兩個(gè)多項(xiàng)式第一個(gè)結(jié)點(diǎn)，不斷循環(huán):
- P1->expon==P2->expon:系數(shù)相加锹锰，若結(jié)果不為0芥炭，則作為結(jié)果多項(xiàng)式對(duì)應(yīng)項(xiàng)的系數(shù)。同時(shí)恃慧，P1和P2都分別指向下一項(xiàng);
- P1->expon>P2->expon:將P1的當(dāng)前項(xiàng)存入結(jié)果多項(xiàng)式园蝠，并使P1指向下一項(xiàng);
- P1->expon<P2->expon:將P2的當(dāng)前項(xiàng)存入結(jié)果多項(xiàng)式，并使P2指向下一項(xiàng);
當(dāng)某一多項(xiàng)式處理完時(shí)痢士，將另一個(gè)多項(xiàng)式的所有結(jié)點(diǎn)依次復(fù)制到結(jié)果多項(xiàng)式中去彪薛。
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;
}
多項(xiàng)式乘法
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;
}
