《數(shù)據(jù)結(jié)構(gòu)（C語言版）》鏈隊列的實現(xiàn)
清華大學(xué)計算機(jī)系列教材? ?累計發(fā)行超400萬冊
嚴(yán)蔚敏 吳偉民 編著
數(shù)據(jù)結(jié)構(gòu)（C語言版）
以下是本人對該紫皮書第三章棧和隊列中鏈隊列的代碼實現(xiàn)，即課本3.4.2節(jié)隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)，并處理了非法輸入字母等問題。
（貌似專欄把我縮進(jìn)吃了，懶得加了，另外建議用visual studio編譯）
代碼如下：
/*帶頭結(jié)點的隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXQSIZE 100
typedef int Status;
typedef int QElemType;
typedef struct QNode
{
QElemType data;
struct QNode* next;
}QNode, * QueuePtr;
typedef struct
{
QueuePtr front;//隊頭指針
QueuePtr rear;//隊尾指針
}LinkQueue;
Status InitQueue(LinkQueue& Q);//鏈隊列的初始化
Status DestoryQueue(LinkQueue& Q);//銷毀隊列
Status EnQueue(LinkQueue& Q, QElemType e);//入隊
Status DeQueue(LinkQueue& Q, QElemType& e);//出隊
Status GetHead(LinkQueue Q, QElemType& e);//獲取隊頭元素
void Menu()
{
printf("***************************\n");
printf("********0：退出系統(tǒng)********\n");
printf("********1：元素入隊********\n");
printf("********2：元素出隊********\n");
printf("********3：求隊頭值********\n");
printf("***************************\n");
}
int main()
{
int option;
int value;
LinkQueue MyQueue;
InitQueue(MyQueue);
Menu();
printf("請輸入你想使用的功能：");
while (scanf("%d", &option) != EOF)
{
while (getchar() != '\n');
switch (option)
{
case 1:
printf("請輸入你想入隊的元素：");
while (scanf("%d", &value) != 1)
{
while (getchar() != '\n');
printf("非法輸入，請重試\n");
}
if (EnQueue(MyQueue, value))
{
printf("入隊成功！\n");
}
else
{
printf("隊列的最大長度為%d,隊列已滿！\n", MAXQSIZE - 1);
}
break;
case 2:
if (DeQueue(MyQueue, value))
{
printf("元素%d出隊成功!\n", value);
}
else
{
printf("隊空，無元素可出隊\n");
}
break;
case 3:
if (GetHead(MyQueue, value))
{
printf("隊頭元素為%d\n", value);
}
else
{
printf("隊空，無隊頭元素\n");
}
break;
case 0:
printf("感謝使用！\n");
exit(0);
default:
printf("非法輸入，請重試\n");
}
Menu();
printf("請輸入你想使用的功能：");
}
return 0;
}
Status InitQueue(LinkQueue& Q)//鏈隊列的初始化
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front)
{
exit(OVERFLOW);
}
Q.front->next = NULL;
return OK;
}
Status DestoryQueue(LinkQueue& Q)//銷毀隊列
{
while (Q.front)
{
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}
Status EnQueue(LinkQueue& Q, QElemType e)//入隊
{
QNode* 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)//出隊
{
if (Q.front == Q.rear)
{
return ERROR;
}
QNode* p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)//注意這里要考慮到,當(dāng)隊列中最后一個元素被刪后，隊列尾指針也丟失了，因此需對隊尾指針重新復(fù)制(指向頭結(jié)點)
{
Q.rear = Q.front;
}
free(p);
return OK;
}
Status GetHead(LinkQueue Q, QElemType& e)//獲取隊頭元素
{
if (Q.front == Q.rear)
{
return ERROR;
}
e = Q.front->next->data;
}
