08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾,索引参见:http://blog.csdn.net/xiaowei_cqu/article/details/7747205
顺序队列各种基本运算算法的实现
顺序队列是较为普遍的一种队列实现方式,采用环状数组来存放队列元素,并用两个变量分别指向队列的前端(front)和尾端(rear),往队列中加进或取出元素时分别改变这两个变量的计数(count)。
队列中用环状数组存储数据(合理利用空间、减少操作),通过基本的append()将元素加入队列,serve()将元素移出队列,先进入的先移出,retieve得到最先加入队列的元素。此外在继承的Extended_queue()中我增加了empty()和serve_and_retrieve()的功能。
【实验说明】
我选择的题目:课本中Programming Projects 3.3 P1
问题描述:Write a function that will read one line of input from the terminal. The input is supposed to consist of two parts separated by a colon ':'. As its results, your function should produce a single character as follows:
N No colon on the line.
L The left part(before the colon) is longer than the right.
R The right part(after the colon) is longer than the left.
D The left and right parts have the same length but are different.
S The left and right are exactly the same.
Examples:
Use either a queue or an extended queue to keep track of the left part of the line while reading the right part.
1.分析队列要实现的基本功能以及继承的类要拓展的功能从而确定基本成员函数——append(),serve(),retireve(),拓展队列中:empty(),serve_and_retrieve(),确定队列中以环形数组存储数据从而确定成员函数——Queue_entry entry[],count(记录队列中数据数量)
2.编写队列的头文件及实现
3.分析题目中结束程序并输出几种字母的条件,简略画出功能实现的流程图,编写程序。(具体思路见源代码注释)
4.简单测试程序的几种情况,分析需要改进的地方
【相关代码】
queue.h
#ifndef QUEUE_H
#define QUEUE_H
const int maxqueue=10;
enum Error_code {success,overflow,underflow};
typedef char Queue_entry ;
class Queue{
public:
Queue();
bool empty() const;
Error_code append(const Queue_entry &item);
Error_code serve();
Error_code retrieve(Queue_entry &item)const;
protected:
int count;
int front,rear;
Queue_entry entry[maxqueue];
};
class Extended_queue:public Queue{
public:
bool full()const;
int size()const;
void clear();
Error_code serve_and_retrieve(Queue_entry &item);
};
#endif
queue.cpp
#include"queue.h"
Queue::Queue()
{
count=0;
rear=maxqueue-1;
front=0;
}
bool Queue::empty() const
{
return count==0;
}
Error_code Queue::append(const Queue_entry &item)
{
if(count>=maxqueue)return overflow;
count++;
rear=((rear+1)==maxqueue)?0:(rear+1);
entry[rear]=item;
return success;
}
Error_code Queue::serve()
{
if(count<=0)return underflow;
count--;
front=((front+1)==maxqueue)?0:(front+1);
return success;
}
Error_code Queue::retrieve(Queue_entry &item) const
{
if(count<=0)return underflow;
item=entry[front];
return success;
}
bool Extended_queue::full() const{
return count==maxqueue;
}
int Extended_queue::size()const{
return count;
}
void Extended_queue::clear(){
count=0;
rear=front;
}
Error_code Extended_queue::serve_and_retrieve(Queue_entry &item){
if(count==0)return underflow;
count--;
item=entry[front];
front=((front+1)==maxqueue)?0:(front+1);
return success;
}
【过程记录】
实验截图:
【结果分析】
1.实验中我以课本后面的练习题为例,实现并验证了顺序队列的更种功能。
2.队列与栈一样是在类中以数组存储数据,但由于队列先进先出的特点在实现存储形式上与栈有一定的不同。因为如果与栈一样对数据操作,队列会无限向后扩大,而前面取出过数据的地方将不会再被利用,十分浪费,也很容易溢出。所以我们采用循环数组来存储,这样合理利用了资源。但在类的实现要要极为时刻考虑周全rear和front的各种可能,要判断是不是循环到了前面,count在此时的功能也极为突出。
3.书中的程序看似简单,但实际判断各种输出情况的时候却极难考虑周全。我首先做出了简易的流程图,然后才写函数,具体分析及思路可见我源码的注释。另外本题还有另外一种实现思路:即将左右输入分别存放在两个队列中,边取去边比较,那样在逻辑上容易理解一些。但鉴于题目的要求,我还是用边从左边队列中取出边比较右边输入的方法。
4.我在实验中遇到的问题:
(1)自己一开始在循环判断用的是cin.get()=='\n'即遇到回车就停止输入,但却无法如料想中结束循环……最终采用cin>>a && waiting(用以标志‘:’的输入)来作为循环终止的条件,这样虽然可以运行,但用户必须输入Ctrl+‘Z’以结束输入。看来自己对输入流的理解与掌握还没有到位。
(2)另外在检验的时候,我发现输入‘:’之前是否输入回车情况是有区别的。如
输入“sam:sam”(无空格),结果为“R”
输入“sam : sam”(有空格),结构为“S”
显然后者是我希望得到的结果,我分析可能是前面情况‘:’被列入了right的判断,从而使结构右边比左边长。还没有想到如何改进。
分享到:
相关推荐
java语言实现的数据结构顺序队列,部分代码:public class OrderQueue { int rear=-1; int front=0; String[]queue; public OrderQueue(int initcap)throws Exception{ if(initcap){ throw new Exception(...
队列用于存储按顺序排列的数据,遵循 先进先出(FIFO,First-In-First-Out) 的原则,也是计算机常用的一种数据结构,别用于很多地方,比如提交给操作系统的一系列进程,打印池任务等。 同栈有点类似,队列的操作主要...
队列中用环状数组存储数据(合理利用空间、减少操作),通过基本的append()将元素加入队列,serve()将元素移出队列,先进入的先移出,retieve得到最先加入队列的元素。 参考博客:...
数据结构与算法-队列 极客笔记 ⼀、什么是队列? 1.先进者先出,这就是典型的"队列"结构。 2.⽀持两个操作:⼊队enqueue(),放⼀个数据到队尾;出队dequeue(),从队头取⼀个元素。 3.所以,和栈⼀样,队列也是⼀种...
顺序表、链表、栈、队列、树、Hashmap等数据结构;排序、二分法查找、树遍历等常见算法实现python语言实现 常见数据结构 顺序表 Python中的list和tuple两种类型采用了顺序表的实现技术 链表 单向链表 双向链表 单向...
这些数据结构能够有效地维护元素的优先级顺序,使得插入、删除和查找等操作都能够在对数时间复杂度内完成。特别是二叉堆,由于其具有堆属性(即任意节点都小于或等于其子节点,或大于或等于其子节点),因此非常适合...
任务描述栈和队列都提供 Push/Pop 两... 输出描述对每组测试数据输出一行, 输出该组数据对应的线性结构,若为栈则输出”Stack”,若为队列则输出“Queue”,若两者都是则输出“Both”,若两者都不是则输出“Error”。
在广度优先搜索遍历求解最短路径过程中,应该设置一个队列queue作为辅助数据结构;路径采用一个整数数组pred来表示。这二个数据结构的存储结构类型均为list类型,其说明定义如下:typedef int list[MAXVER]; 队列...
顺序数据结构数组栈Stack后进先出(LIFO)队列Queue先进先出(FIFO)链表LinkedList存储有序的元素集合元素本身指针(链接):指向下一个元素
目前写在了图,之后的内容会在github上持续更新,数据结构系列更新完之后,可能会更新算法的教程(参考屈婉玲版《算法设计与分析》)希望可以帮到各位!! InitList.cpp------顺序表 LinkList.cpp------链表 ...
优先队列(Priority Queue)是一种数据结构,它类似于常规的队列或栈,但每个元素都有与其关联的“优先级”。在优先队列中,元素的出队顺序是基于它们的优先级,而不是它们进入队列的顺序。通常,优先级最高的元素...
1. 经过以下栈运算后,x的值是( )。...3. 递调用时,处理参数及返回地址,要用一种称为 栈 的数据结构。 4. 设循环队列中数组的下标范围是1-n,其头尾指针分别为f和r,则其元素个数为_(r-f+n) mod n。
数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合。 常用的数据结构有: 数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表...
队列是另一种操作受限的线性表,是指只允许在表的一端进行插入操作的数据结构,具有“先进先出”的特点。 队列分为两种,一种为顺序队列,一种为链队列。在这里重点讲顺序循环队列 顺序队列 采用静态结构的顺序队列...
写出以下各词语对应的中文(英) sequential storge structure 顺序存储结构 Abstract Data Type (ADT) 抽象数据类型 二叉排序树 Binary sort tree queue 队列 storge structure 存储结构 time complexity 时间...
双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构。双端队列也拥有两端:队首(front)、队尾(rear),但与队列不同的是,插入操作在两端(队首和队尾)都可以进行,删除操作也一样...
系统了解请参照-数据结构 概念 存储方式 队列:(queue)是一种运算受限的线性表,它只允许在表的一端插入,一端删除。 线性表-顺序存储-队列-顺序队列 线性表-链式存储-队列-链式队列 特点:就行在排队一样,队头...
常用数据结构 数组 (Array) 在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集 合称为数组。在C语言中, 数组属于构造数据类型。一个数组可以分解为多...