现在的位置: 首页 > 综合 > 正文

队列之顺序队列

2013年08月02日 ⁄ 综合 ⁄ 共 5109字 ⁄ 字号 小 中 大 ⁄ 评论关闭

    数据结构草草学过，不过没有认真运用过。 虽然知道一些最为基本的抽象类型及一些常用操作，不过叫我把这些基本的算法写出来我也是写不出来的。因为常说数据结构+算法是一个程序员最基本的素质，所以这次认真加以复习。在复习的同时我尽量将自己学习的其他的一些基本知识比如C++中的面向对象思想也引入进来，同时也会将在复习中碰到其他的一些问题提出来，能解决的便解决，不能解决的可以试着解决。
    To be a programmer .

----------------------------------------------------------------------------------------------------------------

     队列是另外一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素。允许插入的一端叫做队尾，允许删除的一端称为对头。
    队列只是一种抽象的数据类型，在计算机内有两种实现方式：顺序队列和链队列。通常用数组来表示顺序队列，本文档直接考虑循环队列的基本运算。

    文章的组织结构分为三部分：开头是简单的介绍，之后是数据结构基本运算的代码，最后是在复习中遇到的一些问题。
    我晕倒！ 原来还自以为是的认为自己在代码实现的时候运用了类模版和自定义异常层次还有点新意，起码与《数据结构 c语言描述》多了一些面向对象的东西。没想到的是，今天突然翻了下《数据结构 c++语言描述》，里面早就是这样的例子，太土了！

    以下代码实现了一些线性表最基本的运算，有关代码的两点总结：
    1） 学会使用默认形式参数；
    2） 学会在返回的时候并不仅仅是返回常用的数据类型， 试试this。
    实现代码分三个部分：queueexception.h定义针对队列的异常类，queue.h定义了模版类，main.cpp进行简单的测试。

----------------------------------------------------------------------------------------------------------------

Code:
  1. // queueexception.h   
  2.   
  3. #include <iostream>   
  4.   
  5. class QueueExcep   
  6. {   
  7. public:   
  8.     QueueExcep()   
  9.     {   
  10.     }   
  11.     ~QueueExcep()   
  12.     {   
  13.     }   
  14.     virtual void print()   
  15.     {   
  16.         std::cout <<" An Exception has occured !/n";   
  17.     }   
  18. };   
  19.   
  20. class QueueOverflow : public QueueExcep   
  21. {   
  22. public:   
  23.     QueueOverflow(){}   
  24.     ~QueueOverflow(){}   
  25.     void print()   
  26.     {   
  27.         std::cout <<" Overflow ! No  Enough Memory. /n";   
  28.     }   
  29. };   
  30.   
  31. class QueueOutofBound : public QueueExcep   
  32. {   
  33. public:   
  34.     QueueOutofBound(){}   
  35.     ~QueueOutofBound(){}   
  36.     void print()   
  37.     {   
  38.         std::cout <<" Out Of Bound ! /n";   
  39.     }   
  40. };  
Code:
  1. // queue.h   
  2.   
  3. #include "queueexception.h"   
  4.   
  5. /*  
  6.  * class decleration  
  7.  */  
  8. template <class T>   
  9. class Queue   
  10. {   
  11. public:   
  12.     Queue(int maxQueueSize = 6)   
  13.     {   
  14.         maxSize = maxQueueSize + 1;   
  15.         queue = new T[maxSize];    
  16.         front = 0;   
  17.         rear = 0;   
  18.     }   
  19.     ~Queue()   
  20.     {   
  21.         delete []queue;   
  22.     }   
  23.     bool isEmpty();   
  24.     bool isFull();   
  25.     T first();   
  26.     T last();   
  27.     Queue<T>& insert(T item);   
  28.     Queue<T>& delet();   
  29. private:   
  30.     int maxSize;   
  31.     int front;   
  32.     int rear;   
  33.     T *queue;   
  34. };   
  35.   
  36. /*  
  37.  * previous state: the queue has been created.  
  38.  * input: no.  
  39.  * purpose: to check if the queue is empty.  
  40.  * output: bool value   
  41.  * next state: no  
  42.  */  
  43. template <class T>   
  44. bool Queue<T>::isEmpty()   
  45. {   
  46.     if (front == rear)   
  47.         return true;   
  48.     return false;   
  49. }   
  50.   
  51.   
  52. /*  
  53.  * previous state: the queue has been created.  
  54.  * input: no.  
  55.  * purpose: to check if the queue is full.  
  56.  * output: bool value   
  57.  * next state: no  
  58.  */  
  59. template <class T>   
  60. bool Queue<T>::isFull()   
  61. {   
  62.     if (front == (rear+1) % maxSize)   
  63.         return true;   
  64.     return false;   
  65. }   
  66.   
  67. /*  
  68.  * previous state: the queue is not empty.  
  69.  * input: no  
  70.  * purpose: return the first element of the queue.  
  71.  * output: the first elment of the queue.  
  72.  * previous state: no alteration.  
  73.  */  
  74. template <class T>   
  75. T Queue<T>::first()   
  76. {   
  77.     if (isEmpty())   
  78.         throw QueueOutofBound();   
  79.     return queue[front+1];   
  80. }   
  81.   
  82. /*  
  83.  * previous state: the queue is not empty.  
  84.  * input: no  
  85.  * purpose: return the last element of the queue.  
  86.  * output: the last elment of the queue.  
  87.  * previous state: no alteration.  
  88.  */  
  89. template<class T>   
  90. T Queue<T>::last()   
  91. {   
  92.     if (isEmpty())   
  93.         throw QueueOutofBound();   
  94.     return queue[rear];   
  95. }   
  96.   
  97. /*  
  98.  * previous state: the queue has been created.  
  99.  * input: one element .  
  100.  * purpose: to insert one element to the queue.   
  101.  * output:  a pointer to the queue   
  102.  * next state: the element has been inserted successfully or not.   
  103.  */  
  104. template <class T>   
  105. Queue<T>& Queue<T>::insert(T item)   
  106. {   
  107.     if (isFull())   
  108.         throw QueueOverflow();   
  109.     rear = (rear + 1) % maxSize;   
  110.     queue[rear] = item;   
  111.   
  112.     return *this;   
  113. }   
  114.   
  115. /*  
  116.  * previous state: the queue has been created.  
  117.  * input: no.   
  118.  * purpose: to delete one element from the queue.   
  119.  * output:  a pointer to the queue   
  120.  * next state: the element has been deleted successfully or not.   
  121.  */  
  122. template <class T>   
  123. Queue<T>& Queue<T>::delet()   
  124. {   
  125.     if (isEmpty())   
  126.         throw QueueOutofBound();   
  127.     front = (front + 1) % maxSize;   
  128.   
  129.     return *this;   
  130. }  
Code:
  1. // main.cpp   
  2.   
  3. #include "queue.h"   
  4.   
  5. int main()   
  6. {   
  7.     try  
  8.     {   
  9.         Queue<int> Q(6);   
  10.   
  11.         for (int i=0; i<6; i++)   
  12.             Q.insert(i);   
  13.   
  14.         std::cout <<"the first element of the queue is:/n";   
  15.         std::cout <<Q.first() <<std::endl;   
  16.         std::cout <<"the last element of the queue is:/n";   
  17.         std::cout <<Q.last() <<std::endl;   
  18.            
  19.         for (int i=0; i<22; i++)   
  20.             Q.delet();   
  21.     }   
  22.     catch (QueueOverflow &ex)   
  23.     {   
  24.         ex.print();   
  25.     }   
  26.     catch (QueueOutofBound &ex)   
  27.     {   
  28.         ex.print();   
  29.     }   
  30.     catch (QueueExcep &ex)   
  31.     {   
  32.         ex.print();   
  33.     }   
  34.     catch (...)   
  35.     {}   
  36.   
  37.     return 0;   
  38. }  

----------------------------------------------------------------------------------------------------------------

    在学习vim的同时，发现必须学会使用make工具。编译的文件虽然不多，但是也觉得每次把全部文件名都敲进去或者滚动命令找到之前的编译命令都是挺繁琐的，因而也来小试牛刀，学着写个简单的Makefile文件来帮帮忙。

Code:
  1. #   
  2. CC = g ++   
  3. queue ： main.cpp queue.h queueexception.h   
  4.     $(CC) $< -o $@   
  5.   
  6. .PHONY : clean   
  7. clean :    
  8.     $(RM) –r –f *.o  

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞