鱼C论坛

 找回密码
 立即注册
查看: 2064|回复: 0

[学习笔记] 非循环链队列

[复制链接]
发表于 2018-4-21 22:09:34 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
《数据结构C++描述》 清华大学出版社    任燕编著
小弟还是改遍了程序,使之可以运行,同时还是重载了输出运算符,
便于输出,共勉
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstdbool>
  4. #include <assert.h>
  5. using namespace std;

  6. template <typename elemtype>
  7. class LinkQueue{
  8. public:
  9.         class LinkNode{
  10.         public:
  11.                 elemtype data;
  12.                 LinkNode *next;
  13.         };
  14.         typedef LinkNode* NodePointer;

  15.         //非循环链队列置空
  16.         void clear();

  17.         //出队列(删除头节点)
  18.         bool deQueue(elemtype &e);

  19.         //进队列
  20.         void enQueue(elemtype e);

  21.         //读取头节点的数据域
  22.         bool getFront(elemtype &e);

  23.         //判断是否为空
  24.         bool isEmpty();

  25.         //求结点个数
  26.         int getLength();

  27.         //重载赋值运算符
  28.         LinkQueue operator=(LinkQueue right);

  29.         //构造函数
  30.         LinkQueue();

  31.         //析构函数
  32.         virtual ~LinkQueue();

  33.         //拷贝初始化构造函数
  34.         LinkQueue(LinkQueue &other);

  35.         //重载输出函数
  36.         template <typename out_put>
  37.         friend ostream& operator<<(ostream& out, LinkQueue<out_put> &other);

  38. protected:
  39.         NodePointer front;//对头指针
  40.         NodePointer rear;//队尾指针
  41. };

  42. template <typename elemtype>
  43. void LinkQueue<elemtype>::clear(){
  44.         NodePointer q;
  45.         NodePointer p = front;
  46.         while (p){
  47.                 q = p;
  48.                 p = p->next;
  49.                 delete p;
  50.         }
  51.         front = rear = NULL;
  52. }

  53. //出队列
  54. template <typename elemtype>
  55. bool LinkQueue<elemtype>::deQueue(elemtype &e){
  56.         if (!front){
  57.                 return false;
  58.         }
  59.         NodePointer s = front;
  60.         e = s->data;
  61.         front = front->next;
  62.         delete s;

  63.         if (!front){
  64.                 rear = NULL;//如果该队列未空,那么尾指针也要设置为空
  65.         }

  66.         return true;
  67. }


  68. //进队列
  69. template <typename elemtype>
  70. void LinkQueue<elemtype>::enQueue(elemtype e){
  71.         NodePointer s;
  72.         s = new LinkNode;
  73.         assert(s != 0);
  74.         s->data = e;
  75.         s->next = NULL;
  76.         if (!front){
  77.                 front = rear = s;
  78.         }
  79.         else{
  80.                 rear->next = s;
  81.                 rear = s;
  82.         }
  83. }

  84. template <typename elemtype>
  85. bool LinkQueue<elemtype>::getFront(elemtype &e){
  86.         if (!front){
  87.                 return false;
  88.         }
  89.         e = front->data;
  90.         return true;
  91. }

  92. template <typename elemtype>
  93. bool LinkQueue<elemtype>::isEmpty(){
  94.         return !front ? true : false;
  95. }

  96. template <typename elemtype>
  97. int LinkQueue<elemtype>::getLength(){
  98.         int length = 0;
  99.         NodePointer p = front;

  100.         while (p){
  101.                 length++;
  102.                 p = p->next;
  103.         }
  104.         return length;
  105. }

  106. //重载赋值运算符
  107. template <typename elemtype>
  108. LinkQueue<elemtype> LinkQueue<elemtype>::operator=(LinkQueue<elemtype> right){
  109.         NodePointer s;
  110.         NodePointer rp = right.front;

  111.         if (this != &right){
  112.                 clear();
  113.                 while (rp){
  114.                         s = new LinkNode;
  115.                         assert(s != 0);
  116.                         s->data = rp->data;
  117.                         s->next = NULL;

  118.                         if (!front){
  119.                                 front = rear = s;
  120.                         }
  121.                         else{
  122.                                 rear->next = s;
  123.                                 rear = s;
  124.                         }
  125.                         rp = rp->next;
  126.                 }
  127.         }
  128.         return *this;//返回对象
  129. }

  130. template <typename elemtype>
  131. LinkQueue<elemtype>::LinkQueue(){
  132.         front = rear = NULL;
  133. }

  134. template <typename elemtype>
  135. LinkQueue<elemtype>::~LinkQueue(){
  136.         clear();
  137.         cout << "链队列清除完毕" << endl;
  138. }

  139. template <typename elemtype>
  140. LinkQueue<elemtype>::LinkQueue(LinkQueue<elemtype> &other){
  141.         NodePointer s;
  142.         NodePointer op = other.front;

  143.         rear = front = NULL;//当前队列置空,准备接受other的初始化
  144.         while (op){
  145.                 s = new LinkNode;
  146.                 assert(s != 0);

  147.                 s->data = op->data;
  148.                 s->next = NULL;

  149.                 if (!front){
  150.                         front = rear = s;
  151.                 }
  152.                 else{
  153.                         rear->next = s;
  154.                         rear = s;
  155.                 }
  156.                 op = op->next;
  157.         }
  158. }


  159. //重载输出函数
  160. template <typename out_put>
  161. ostream& operator<<(ostream& out, LinkQueue<out_put> &other){
  162.         while (other.front){
  163.                 out << other.front->data << "\t";
  164.                 other.front = other.front->next;
  165.         }
  166.         return out;
  167. }


  168. int main(void){
  169.         LinkQueue<int> s1;
  170.         for (int i = 1; i <= 10; i++){
  171.                 s1.enQueue(i);
  172.         }

  173.         cout << "链队列为:" << endl;
  174.         cout << s1 << endl;
  175.         return 0;
  176. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 19:20

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表