WHCSRL 技术网

数据结构实验5 链队列的基本操作_Far

姓名:Far_Rainbow
学号: 202505000X
专业: 软件工程
年级:2020级

实验名称:实验5 链队列的基本操作

实验内容

(1)实验目的
通过该实验,使学生理解链队列的构造特点并灵活应用,掌握链队基本操作的编程实现,认识栈是在一端进行插入,在另一端进行删除集中操作的线性结构,掌握队列的“先入先出”操作特点,知道判断队列空和满的条件,进一步熟悉C++中指针操作。

(2)实验内容
用链式存储结构,实现教材定义的队列的基本操作。

(3)参考界面
菜单中包括以下功能:

  1. 初始化队列
  2. 销毁队列
  3. 清空队列
  4. 队列判空
  5. 求队列长度
  6. 获取队头元素
  7. 插入一个 元素
  8. 删除一个元素
  9. 输出所有元素

要求:自定义的函数中不允许出现提示语和输出语句。

(4)验收/测试用例
通过菜单调用各个操作,测试点:

  • 没有初始化前进行其他操作,程序是否能控制住;
  • 初始化一个队列;
  • 判队列空,屏幕显示队列为空;
  • 3个数入队, 3、5、7;
  • 队列长度,屏幕输出3;
  • 取队头元素,再判队列是否空,然后再判队列长度,(让学生知道取队头元素不改变队列中的内容,队头指针不发生改变);
  • 出队,再判队列长度和显示队列中剩余的元素;(多次出队,队列为空之后再执行出队操作,是否提示队列为空);
  • 入队一个元素2,再出队,再判断队列是否为空,(主要测试出队操作中特殊情况下的那两行代码是否写了);
  • 销毁队列,再做其他操作,判断程序是否能控制。

实验类型:验证性

实验的重难点:入栈和出栈、进制转换(十六进制)

实验环境:TDM-GCC 4.9.2 64-bit

实验步骤及完成任务情况
一、设计思想

  1. 采用模板实现泛型编程,可创建任意数据类型的队列;
  2. 以双链表为原型实现链队列,双链表的header哨兵和trailer哨兵作为队列的队首指针front和队尾指针rear;
  3. 入队始终是将元素插入到队尾哨兵前,出队始终是删除队首哨兵后的元素,以保证队列被限制为只能从队尾入队,从队首出队;

二、主要源代码

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

template <typename T> struct Qnode {
	T data;
	Qnode<T>* pred;
	Qnode<T>* succ;
};

template <typename T> class Queue {
private:
	int _length;
	Qnode<T>* front;
	Qnode<T>* rear;
		
public:
	void init();
	void destroy();
	void clear();
	Queue() : front(NULL), rear(NULL) { }
	~Queue() {destroy(); }
	bool isempty() const {return _length > 0 ? 0 : 1; }
	int getlength() const {return _length; }
	bool exist() const {return front != NULL ? 1 : 0;}
	T& getfront() const {return front->succ->data; }
	T& getrear() const {return rear->pred->data; }
	void enqueue(T const& e);
	T dequeue();
	void traverse();
};

template <typename T> void Queue<T>::init()
{
	front = new Qnode<T>;
	rear = new Qnode<T>;
	front->succ = rear;
	front->pred = NULL;
	rear->pred = front;
	rear->succ = NULL;
	_length = 0;
}

template <typename T> void Queue<T>::destroy()
{
	Qnode<T>* p = front, *q;
	while(p){
		q = p->succ;
		delete p;
		p = q;
	}
	front = NULL;
	rear = NULL;
	_length = 0;
}

template <typename T> void Queue<T>::clear()
{
	Qnode<T>* p = front->succ, *q;
	while(p != rear){
		q = p->succ;
		delete p;
		p = q;
	}
	front->succ = rear;
	rear->pred = front;
	_length = 0;
}

template <typename T> void Queue<T>::enqueue(T const& e)
{
	Qnode<T>* p = new Qnode<T>;
	p->data = e;
	p->pred = rear->pred;
	p->succ = rear;
	rear->pred->succ = p;
	rear->pred = p;
	++ _length;
}

template <typename T> T Queue<T>::dequeue()
{
	Qnode<T>* p = front->succ;
	front->succ = p->succ;
	p->succ->pred = front;
	T e = p->data;
	delete p;
	-- _length;
	return e; 
}

template <typename T> void Queue<T>::traverse()
{
	Qnode<T>* p = front->succ;
	while(p != rear) {
		cout<<p->data<<' ';
		p = p->succ; 
	}
}

int main()
{
	cout<<"
   链队列的基本操作

";
	cout<<"1---初始化队列
";
	cout<<"2---销毁队列
";
	cout<<"3---清空队列
";
	cout<<"4---队列判空
";
	cout<<"5---求队列长度
";
	cout<<"6---获取队头元素
";
	cout<<"7---插入一个元素
";
	cout<<"8---删除一个元素
";
	cout<<"9---输出所有元素
";
	cout<<"
	退出,输入一个负数!

";
	Queue<int> q;
	int e;
	while(true){
		int myOption;
		cout<<"
请输入操作序号:";
		cin>>myOption;
		switch(myOption){
			case 1:{
				if(q.exist()){
					cout<<"初始化失败,队列已存在
";
					break;
				}
				q.init();
				cout<<"初始化成功!
";
				break;
			}
			case 2:{
				if (!q.exist()){
					cout<<"销毁失败,队列不存在
";
					break; 
				}
				q.destroy();
				cout<<"销毁成功!
";
				break;
			} 
			case 3:{
				if (!q.exist()){
					cout<<"清空失败,队列不存在
";
					break; 
				}
				if (q.isempty()) ; 
				else	q.clear();
				cout<<"清空成功!
"; 
				break;
			}
			case 4:{
				if (!q.exist()){
					cout<<"判空失败,队列不存在
";
					break; 
				}
				if (q.isempty())	cout<<"队列为空!
";
				else	cout<<"队列非空!
"; 
				break;
			}
			case 5:{
				if (!q.exist()){
					cout<<"请先创建队列!
";
					break; 
				}
				cout<<"队列的长度是"<<q.getlength()<<endl; 
				break;
			}
			case 6:{
				if (!q.exist()){
					cout<<"获取失败,队列不存在
";
					break; 
				}
				if (q.isempty()){
					cout<<"队列为空,无队首元素!
";
					break;
				}
				cout<<"队首元素是"<<q.getfront()<<endl; 
				break;
			}
			case 7:{
				if (!q.exist()){
					cout<<"插入失败,队列不存在!
";
					break; 
				}
				cout<<"请输入待插入元素e
"<<"  e为:"; 
				cin>>e;
				q.enqueue(e);
				break;
			}
			case 8:{
				if (!q.exist()){
					cout<<"删除失败,队列不存在!
";
					break; 
				}
				if (q.isempty()){
					cout<<"队列为空,删除失败!
";
					break;
				}
				else {
					e = q.dequeue();
					cout<<"被删除的元素是:"<<e<<endl;
				} 
				break;
			}
			case 9:{
				if (!q.exist()){
					cout<<"遍历并输出失败,队列不存在!
";
					break; 
				}
				if (q.isempty()){
					cout<<"队列为空!
";
					break;
				}
				cout<<"队列的所有元素是:";
				q.traverse();
				cout<<endl;
				break;
			}
		}
		if(myOption > 9 || myOption == 0)	cout<<"
请输入小于9的正整数

";
		if(myOption < 0){
			cout<<"
退出程序!
";
			break;
		}
	}
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226

实验结果
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

推荐阅读