1. 首页
  2. IT资讯

队列的链式存储结构

队列的顺序存储结构(参考前面文章:http://blog.itpub.net/29876893/viewspace-1847566/)比链式较为复杂些,顺序存储结构要构造循环队列;但是链式就不需要,存储元素的内存地址是随机的,用的时候再向os申请内存空间。链式存储结构中需要两个flag工作指针,过程相对较简单些。但是其中也有需要注意的细节。下面给出实现代码:

点击(此处)折叠或打开

  1. #include<iostream>
  2. using namespace std;
  3. typedef struct Queue{  //队列结点结构
  4.     char ch;
  5.     Queue *next;
  6. }*queue;
  7. typedef struct flaging {  //flag指针结构
  8.     queue front, rear;   
  9. }*flag;
  10. void initSqueue(queue);
  11. void initflag(flag);
  12. void createSqueue(queue, flag);
  13. void pushSqueue(queue, flag, char);
  14. void popSqueue(queue, flag);
  15. void throughSqueue(queue, flag);
  16. void initSqueue(queue first) {
  17.     first = new Queue;
  18. }
  19. void initflag(flag fg) {
  20.     fg = new flaging;
  21. }
  22. void createSqueue(queue q,flag fg){    
  23.     cout << “输入入队的元素:” << endl;
  24.     queue p,head;
  25.     head = q;
  26.     for (char ch; cin >> ch, ch != #;) {
  27.         p = new Queue;
  28.         head>next=p;
  29.         p>ch = ch;
  30.         head = p;
  31.         head>next = NULL;
  32.     }
  33.     fg>front=q>next;
  34.     fg>rear = head;
  35. }
  36. void pushSqueue(queue q,flag fg,char ch) { //入队
  37.     q = fg>rear;
  38.     q>next = new Queue;
  39.     q>next>ch = ch;
  40.     q>next>next = NULL;
  41.     fg>rear = q>next;
  42. }
  43. void popSqueue(queue q,flag fg){  //出队
  44.     
  45.     q = fg>front;
  46.         cout << q>ch;
  47.         fg>front = q>next;
  48.         delete q;
  49. }
  50. void throughSqueue(queue q, flag fg) {//遍历队列,打印在队列中的元素
  51.     q = fg>front;
  52.     do{
  53.         cout << q>ch << ” “;
  54.         q = q>next;
  55.     } while (q != NULL);
  56. }

  57. int main(){
  58.     Queue q;
  59.     flaging fg;
  60.     initSqueue(&q);
  61.     initflag(&fg);
  62.     createSqueue(&q, &fg);
  63.     pushSqueue(&q, &fg, F);
  64.     cout << “出队的元素是:”;
  65.     popSqueue(&q, &fg);
  66.     cout << endl;
  67.     cout << “出队的元素是:”;
  68.     popSqueue(&q, &fg);
  69.     cout << endl;
  70.     cout << “出队的元素是:”;
  71.     popSqueue(&q, &fg);
  72.     cout << endl;
  73.     cout << “在队列中的元素是:” << endl;
  74.     throughSqueue(&q, &fg);
  75.     cout << endl;
  76. }

运行结果:
队列的链式存储结构
该过程用下面图示简单的表示一下:

队列的链式存储结构
有朋友会问,为什么最后指向NULL结点,添加这一步似乎对程序的可读性没有带来多少好处,但是这一步关键之处,在throughSqueue(queue q, flag fg)中,遍历整个队列时,用来判断遍历整个队列时退出的条件,对于该函数作用十分重要,但是如果不实现该函数功能的话,那么没有必要再构造出NULL结点。队列的性质是从front指针处出队列,从rear指针处入队列,上面的示意图很清楚的看出这一性质,front,rear可以看成记忆指针,可以准确的告诉q指针该到什么位置工作,q指针可以看成是移动的。整个过程,画出图会很清晰,相信读者会有更精彩的功能实现。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29876893/viewspace-1850594/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:℅傍ㄖ免沦陷dε鬼,转转请注明出处:http://www.cxybcw.com/191809.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code