数据结构入门----链队列的基本操作

一. 实验要求 用链式存储结构，实现队列的基本操作。 二. 实验目的 通过该实验，理解链队列的构造特点并灵活应用，掌握链队基本操作的编程实现，认识栈是在一端进行插入，在另一端进行删除集中操作的线性结构，掌握队列的“先入先出”操作特点，知道判断队列空和满的条件，进一步熟悉C语言中指针操作。 三. 设计思想 1.定义队列的链式存储结构，节点信息data、next，队列指针队头front、队尾rear，并且打出字幕的函数。 2.初始化队列，先申请队列Q的存储空间，构造一个空队列Q，一开始让Q.rear=Q.front，Q.rear->next=NULL。如果Q申请空间失败，则输出 初始化队列失败，否则，令Q.front->next=NULL。 3.销毁队列，利用while循环释放整个链式队列while(Q.front) {Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}。 4.清空队列，循环释放链队列的存储空间，while(Q.front!=Q.rear){q=Q.front; Q.front=Q.front->next;free(q);}。 5.判断队列是否为空，利用if语句判断：if(Q.front==Q.rear)，如果是则队列为空，否则队列不为空。 6.返回队列中元素个数，令指针p指向队列Q的队头元素，利用while循环遍历队列，定义变量n初始值为0，计数n每执行一次while循环则加一，循环结束后，n即为队列中的元素个数。 7.返回队列队头元素，先判断队列是否为空：if(Q.front==Q.rear){cout<<"队列为空！"<<endl;}。如果队列不为空，则返回Q.front->data即为队头元素。 8.插入新的队尾元素，令Q.rear->data=e，先申请节点p的存储空间，令p->next=NULL，然后令Q.rear->next=p，Q.rear=p，令p指向的节点成为新的Q.rear，即插入成功。 9.删除队头元素，先判断队列是否为空：if(Q.front==Q.rear){cout<<"队列为空！"<<endl;}。如果队列不为空，令新生成的指针p指向队头元素，用e =p->data返回队头元素的值，然后让队头指针Q.front指向队头元素后面一个元素，然后free指针p所指向的存储空间，即删除成功。 10.初始化并创建队列，先初始化队列Q，从键盘输入要创建队列的个数n，然后利用for循环循环输入队列元素e：把输入的队列元素e赋给Q.rear的data域值，新生成一个节点p，令p->next=NULL，让Q.rear的next域指向p，最后让Q.rear指向p。 11.输出队列元素，先判断队列是否为空：if(Q.front==Q.rear){cout<<"队列为空！"<<endl;}。如果队列不为空，令新生成的指针p指向队头元素，利用while循环遍历队列Q中的元素：while(p!=Q.rear){cout<<p->data<<endl;p=p->next;}。 四. 主要源代码

#include "iostream" using namespace std; typedef struct QNode { int data; struct QNode *next; }*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; static LinkQueue Q; typedef char ElemType; int checkStatus=0; void selectFunc(int _select); void InitQueue(LinkQueue &Q); void DestroyQueue(LinkQueue &Q); void ClearQueue(LinkQueue &Q); void QueueEmpty(LinkQueue &Q); void QueueLen(LinkQueue &Q); void GetHead(LinkQueue &Q); void EnQueue(LinkQueue &Q); void DeQueue(LinkQueue &Q); void CreatQueue(LinkQueue &Q); void PrintQueue(LinkQueue &Q); void main() { cout<<"**********************************************************"<<endl; cout<<"***************** 1. 初始化队列 *****************"<<endl; cout<<"***************** 2. 销毁队列 *****************"<<endl; cout<<"***************** 3. 清空队列 *****************"<<endl; cout<<"***************** 4. 判断队列是否为空 *****************"<<endl; cout<<"***************** 5. 返回队列中元素个数 *****************"<<endl; cout<<"***************** 6. 返回队列队头元素 *****************"<<endl; cout<<"***************** 7. 插入新的队尾元素 *****************"<<endl; cout<<"***************** 8. 删除队头元素 *****************"<<endl; cout<<"***************** 9. 输出队列元素 *****************"<<endl; cout<<"***************** 10.初始化并创建队列 *****************"<<endl; cout<<"***************** 11.退出 *****************"<<endl; cout<<"**********************************************************"<<endl; int _select; while(1) { cout<<"请输入功能前面的数字代号："; cin>>_select; if(!cin || _select==0 || _select>11) { cout<<"您输入的选项有误，请重新输入！"<<endl; cout<<endl; cin.clear(); cin.sync(); continue; } else { if(_select<0) { exit(1); } else { selectFunc(_select); } } cout<<endl; } system("pause"); } void selectFunc(int _select) { switch(_select) { case 1: { InitQueue(Q); checkStatus=1; break; } case 2: { if(checkStatus==1) { DestroyQueue(Q); } else { checkStatus=0; cout<<"尚未初始化队列，请先初始化!"<<endl; } break; } case 3: { if(checkStatus==1) { ClearQueue(Q); } else { checkStatus=0; cout<<"尚未初始化，请先初始化!"<<endl; } break; } case 4: { if(checkStatus==1) { QueueEmpty(Q); } else { checkStatus=0; cout<<"尚未初始化队列，请先初始化!"<<endl; } break; } case 5: { if(checkStatus==1) { QueueLen(Q); } else { checkStatus=0; cout<<"尚未初始化队列，请先初始化!"<<endl; } break; } case 6: { if(checkStatus==1) { GetHead(Q); } else { checkStatus=0; cout<<"尚未初始化队列，请先初始化!"<<endl; } break; } case 7: { if(checkStatus==1) { EnQueue(Q); } else { checkStatus=0; cout<<"尚未初始化队列，请先初始化!"<<endl; } break; } case 8: { if(checkStatus==1) { DeQueue(Q); } else { checkStatus=0; cout<<"尚未初始化队列，请先初始化!"<<endl; } break; } case 9: { if(checkStatus==1) { PrintQueue(Q); } else { checkStatus=0; cout<<"尚未初始化队列，请先初始化!"<<endl; } break; } case 10: { CreatQueue(Q); checkStatus=1; break; } case 11: { ClearQueue(Q); DestroyQueue(Q); exit(1); break; } default: { cout<<"输入不合法，请重新输入！"<<endl; break; } } } void InitQueue(LinkQueue &Q) { Q.front=(QueuePtr)malloc(sizeof(QNode)); Q.rear=Q.front; Q.rear->next=NULL; if(!Q.front) { cout<<"初始化队列失败！"<<endl; } else { Q.front->next=NULL; cout<<"初始化队列成功！"<<endl; } } void DestroyQueue(LinkQueue &Q) { while(Q.front) { Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } cout<<"销毁队列成功！"<<endl; } void ClearQueue(LinkQueue &Q) { QueuePtr q; while(Q.front!=Q.rear) { q=Q.front; Q.front=Q.front->next; free(q); } cout<<"清空队列成功！"<<endl; } void QueueEmpty(LinkQueue &Q) { if(Q.front==Q.rear) { cout<<"队列为空！"<<endl; } else { cout<<"队列不为空！"<<endl; } } void QueueLen(LinkQueue &Q) { int n=0; QueuePtr p; p=Q.front; while(p->next!=NULL) { n++; p=p->next; } cout<<"队列中的元素个数为"<<n<<endl; } void GetHead(LinkQueue &Q) { int n; if(Q.front==Q.rear) { cout<<"队列为空！"<<endl; } else { n=Q.front->data; cout<<"队头元素为:"<<n<<endl; } } void EnQueue(LinkQueue &Q) { int e; cout<<"请输入要插入的队尾元素："; cin>>e; Q.rear->data=e; QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) { cout<<"插入失败！"<<endl; } p->next=NULL; Q.rear->next=p; Q.rear=p; cout<<"插入成功！"<<endl; } void DeQueue(LinkQueue &Q) { int e; if(Q.front==Q.rear) { cout<<"队列为空，无法删除！"<<endl; } else { QueuePtr p; p=Q.front; e=p->data; Q.front=Q.front->next; free(p); cout<<"删除成功！删除元素为："<<e<<endl; } } void CreatQueue(LinkQueue &Q) { InitQueue(Q); int n,e; cout<<"请输入要创建队列的个数："; cin>>n; cout<<"请输入队列元素："; for(int i=1;i<=n;i++) { cin>>e; Q.rear->data=e; QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); p->next=NULL; Q.rear->next=p; Q.rear=p; } cout<<"创建成功！"<<endl; } void PrintQueue(LinkQueue &Q) { if(Q.front==Q.rear) { cout<<"队列为空！"<<endl; } else { cout<<"队列元素为："<<endl; QueuePtr p; p=Q.front; while(p!=Q.rear) { cout<<p->data<<endl; p=p->next; } } }

五、参考界面