算法基础 (三):队列基础

先上一张图:(我这里的队列为一般队列,双向队列、循环队列等下一章讨论)

下面是实现源码:

 

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
 
  1. #include "stdafx.h"  
  2. #include<stdio.h>  
  3. #include<malloc.h>  
  4. #include<stdlib.h>  
  5.   
  6. #define TRUE  1   
  7. #define FALSE 0  
  8. #define OK    1  
  9. #define ERROR 0  
  10. #define INFEASIBLE -1  
  11. #define OVERFLOW   -2  
  12.   
  13. typedef int Status;                 //函数返回值  
  14.   
  15. typedef int QElemType;              //暂定元素类型为int,可以根据自己需要修改  
  16. typedef struct  QNode               //定义节点类型  
  17. {  
  18.     QElemType data;  
  19.     struct QNode *next;  
  20. }QNode, *QueuePtr;  
  21. typedef struct  
  22. {  
  23.     QueuePtr front;                 //定义队头指针  
  24.     QueuePtr rear;                  //定义队尾指针  
  25. }LinkQueue;  
  26. /*---------------------------以下是队列的基本操作的函数声明以及实现--------------------------------*/  
  27. Status InitQueue(LinkQueue &Q);     //构造一个空队列  
  28. Status DestroyQueue(LinkQueue &Q);  //销毁队列  
  29. Status InsertQueue(LinkQueue &Q,QElemType e);       //插入元素e为Q的队尾元素  
  30. Status DeQueue(LinkQueue &Q);           //在队列不为空的情况下,删除队头元素  
  31.   
  32. //入口测试函数  
  33.   
  34. int _tmain(int argc, _TCHAR* argv[])                  
  35. {      
  36.     LinkQueue Q;  
  37.     if(InitQueue(Q))  
  38.     {  
  39.         //初始化分配空间成功  
  40.         for(int i = 0;i<10; i++) //0~9自然数入队  
  41.         {  
  42.             InsertQueue(Q,i);  
  43.         }  
  44.         printf("\n元素入队完毕...测试...");  
  45.         for(int i = 0;i<10;i++)      //  
  46.         {  
  47.             printf("\n出队元素为:%d",DeQueue(Q));  
  48.         }  
  49.     }  
  50.     return 0;  
  51. }  
  52.   
  53. Status InitQueue(LinkQueue &Q)  
  54. {  
  55.     Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));  
  56.     if(!Q.front)exit(OVERFLOW);  
  57.     Q.front->next = NULL;  
  58.     return OK;  
  59. }  
  60. Status DestroyQueue(LinkQueue &Q)   //销毁队列  
  61. {  
  62.     while(Q.front)  
  63.     {  
  64.         Q.rear = Q.front->next;  
  65.         free(Q.front);  
  66.         Q.front = Q.rear;  
  67.     }  
  68.     return OK;  
  69. }  
  70. Status InsertQueue(LinkQueue &Q,QElemType e)        //插入元素e为Q的队尾元素  
  71. {  
  72.     QueuePtr p = (QueuePtr)malloc(sizeof(QNode));  
  73.     if(!p)exit(OVERFLOW);  
  74.     p->data = e;         //赋值  
  75.     p->next = NULL;            
  76.     Q.rear->next = p;        //连接  
  77.     Q.rear = p;             //新的队尾  
  78.     return OK;  
  79. }  
  80.   
  81. QElemType DeQueue(LinkQueue &Q )            //在队列不为空的情况下,删除队头元素  
  82. {  
  83.     QElemType e;  
  84.     if(Q.front == Q.rear)  
  85.         return ERROR;       //空队列,返回  
  86.     QueuePtr p = Q.front->next;  
  87.     e = p->data;  
  88.     Q.front->next = p->next;  
  89.     if(Q.rear == p)  
  90.         Q.rear = Q.front;   //删得都只剩一个了,队首队尾是同一个节点  
  91.     free(p);  
  92.     return e;  
  93. }  
Pour de plus amples informations sur les optimisations de compilation, consultez notre Avertissement concernant les optimisations.