隊列的鏈?zhǔn)酱鎯Υa實現(xiàn)
//帶頭節(jié)點 Q.front->next才指向第一個元素
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InintQueue(LinkQueue &Q)
{
Q.front = Q.rear = (QNode*)malloc(sizeof(QNode))
Q.front->next = NULL;
}
bool EmptyQueue(LinkQueue &Q)
{
return (Q.front == Q.rear);
}
Status EnQueue(LinkQueue &Q, ElemType x)
{
QNode *p = (QNode*)malloc(sizeof(QNode));
p->data = x;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue &Q, &e)
{
if(Q.front == Q.rear)
return False;
QNode *p= Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p)
{
Q.rear = Q.front;
}
free(p);
return OK;
}
ElemType GetHead(LinkQueue Q)
{
if(Q.front->next == NULL)
return NULL;
return Q.front->next->data;
}
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//不帶頭節(jié)點 頭指針是直接指向第一個隊頭元素
void InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = NULL;
}
bool EmptyQueue(LinkQueue &Q)
{
return (Q.front == NULL);
}
Status EnQueue(LinkQueue &Q, ElemType x)
{
QNode *p = (QNode*)malloc(sizeof(QNode));
p->data = x;
p->next = NULL;
if(Q.front == NULL)
{
Q.front = p;
Q.rear = p;
}
Q.rear->next = p;
Q.rear = p;
}
Status DeQueue(LinkQueue &Q, &e)
{
if(Q.front == NULL)
return False;
p = Q.front;
Q.front = p->next;
if(p == Q.rear)
{
Q.rear = Q.front;
}
free(p);
return OK;
}
ElemType GetHead(LinkQueue Q)
{
if(Q.front != NULL)
return Q.front->data;
return NULL;
}
隊列的具體應(yīng)用
- 計算八進制
void conversion(int N)
{
Stack S;
InitStatck(S);
while(N>0)
{
push(S, N % 8);
N /= 8;
}
while(!EmptyStack(S))
{
cout << Pop(S) << endl;
}
}
- 括號匹配
bool matching(char a[], int len)
{
Stack S;
InitStack(S);
for(int i = 0; i < len; i++)
{
if(a[i] == '(' || a[i] == '[' || a[i] == '{')
push(S, a[i]);
else
{
if(EmptyStack(S))
return false
e = GetTop(S);
if(e == '(' && a[i] == ')' || e == '[' && a[i] == ']'|| e == '{' && a[i] == '}')
{
Pop(S);
}
else
return false;
}
}
if(!EmptyStack(S))
return false;
return true;
}
4.表達式計算
規(guī)則:
1.遇到操作數(shù)直接加入操作數(shù)棧中
2.遇到運算符:運算符棧頂元素 和 當(dāng)前運算符 進行優(yōu)先級比較
1.運算符棧頂元素 >= 當(dāng)前運算符 彈出運算符棧 操作數(shù)棧彈出最上層的兩個棧頂元素進行改彈出運算符的運算并將結(jié)果放回操作數(shù)棧中,依次繼續(xù)和棧頂元素進行比較,比出來<就停止
2.運算符棧頂元素 < 當(dāng)前運算符 棧頂元素繼續(xù)呆在運算符棧
都要將當(dāng)前運算符入棧
3.遇到括號界定符:
1. 遍歷到“(”入棧
2. 遍歷到“)”,彈出運算符,并彈出最上層的兩個棧頂元素進行運算并將結(jié)果放回操作數(shù)棧中,直到彈出“)”
//NUM 操作數(shù)棧 OPR運算符棧
char EvaluateExpression()
{
Push(OPR,'#')
cin >> ch;
while(ch != '#' && GetTop(OPR) != '#')\
{
if(!operators(ch))
{
push(NUM, ch);
cin >> ch;
}
else
switch(precede(GetTop(OPR), ch))
{
case '<':
//運算符棧頂元素 < 當(dāng)前運算符
push(OPR, ch)
cin >> ch;
break;
case '>':
//這里優(yōu)先級包含左優(yōu)先,但當(dāng)棧頂元素是(時,不彈出。
//規(guī)定左括號運算級別最高,右括號運算級別最低,則括號內(nèi)的運算符基本運算完成后還剩下其他運算符時,一和右括號比較,優(yōu)先級肯定高 也會彈出棧進行運算
//運算符棧頂元素 >= 當(dāng)前運算符,彈出運算,!!繼續(xù)將當(dāng)前元素和棧頂元素比較!
Pop(OPR, op);
Pop(NUM, a);
Pop(NUM, b);
push(NUM, operate(a,op,b))
case '=':
//只有一種情況 左括號遇到右括號時 彈出
Pop(OPR,op);
cin >> ch;
}
}
}
- 和舞伴一起跳舞(實際應(yīng)用,只用基本函數(shù)并聲明一下)
void DancePartner(Person dance[], int num)
{
InitQueue(Mdancers);
InitQueue(Fdancers);
for(int i = 0; i < num; i++)
{
if(person[i].sex = 'M')
EnQueue(Mdancers, person[i]);
else
EnQueue(Fdancers, person[i]);
}
while(!EmptyQueue(Fdancers) && !EmptyQueue(Mdancers))
{
DeQueue(Mdancers, man);
DeQueue(Fdancers, woman);
cout << "歡迎" << man.name << "男士和" << woman.name << "女士一起跳舞" << endl;
}
if(!EmptyQueue(Fdancers))
{
woman = GetTop(Fdancers);
cout << "下一場第一個跳舞的女士是" << woman.name << endl;
}
if(!EmptyQueue(Mdancers))
{
man = GetTop(Mdancers);
cout << "下一場第一個跳舞的女士是" << man.name << endl;
}
}
浙公網(wǎng)安備 33010602011771號