实验三 栈队列串的操作.docx
实验三 栈队列串的操作实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的： 参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。 二、实验要求： 1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 1. 堆栈类测试和应用问题。要求： (1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。 (2)定义数据元素的数据类型为如下形式的结构体： 设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。 2. 队列类测试和应用问题。要求： 设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把 1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。 3设计串采用顺序存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结 有大于、等于和小于三种情况。 *4. 设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。 *5. 设计串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回。并要求设计主函数进行测试。 一个测试例子为：S”I am a student”，T=”student”，V=”teacher “。 四、实验源码 1.1 #include<iostream> using namespace std; const int StackSize=10; class SeqStack public: SeqStack( ) top=-1; SeqStack( ) void Push( int x ) if (top= StackSize-1) throw "溢出" top+; datatop=x; int Pop( ) if (top=-1) throw "溢出" int x=datatop-; return x; int dataStackSize; int top; ; int main SeqStack a; for(int i= 1 ; i <= 5; i+) a.Push(i); for( i = 0 ;i < 5; i+) int k = 0; k = a.Pop; cout<< k << endl; 1.2 #include<iostream> #include<string> using namespace std; const int StackSize=10; typedef struct int notask; char name10;DataType; class SeqStack public: SeqStack( ) top = -1; SeqStack( ) void Push( DataType x ) if (top= StackSize-1) throw "溢出" top+; datatop = x; DataType Pop( ) if (top=-1) throw "溢出" DataType x=datatop-; return x; DataType dataStackSize; int top; ; int main SeqStack a; DataType b5; for(int i = 1 ; i <= 5; i+) cin>> bi.name; bi.notask = i; for( i = 1 ; i <= 5; i+) a.Push(bi); for( i = 1 ;i <= 5; i+) DataType k ; k = a.Pop; cout<< k.name <<" "<<k.notask << endl; 2. #include<iostream> #include<string> using namespace std; #define T int const int QueueSize=100; class CirQueue public: T dataQueueSize; int front, rear; CirQueue( ) front=rear=0; CirQueue( ) void EnQueue(T x) if (rear+1) % QueueSize =front) throw "上溢" rear=(rear+1) % QueueSize; datarear=x; T GetQueue( ) if (rear=front) throw "下溢" int i=(front+1) % QueueSize; return datai; T DeQueue( ) if (rear=front) throw "下溢" front=(front+1) % QueueSize; return datafront; ; int main CirQueue a; for(int i = 1 ; i <= 5; i+) a.EnQueue(i); for( i = 1 ;i <= 5; i+) int k ; k = a.DeQueue;cout<< k<< endl; 3. #include<iostream> #include<string> using namespace std; #define T char const int QueueSize=100; class CirQueue public: T dataQueueSize; int front, rear; CirQueue( ) front=rear=0; CirQueue( ) void EnQueue(T x) if (rear+1) % QueueSize =front) throw "溢出" rear=(rear+1) % QueueSize; datarear=x; T GetQueue( ) if (rear=front) throw "溢出" int i=(front+1) % QueueSize; return datai; T DeQueue( ) if (rear=front) throw "溢出" front=(front+1) % QueueSize; return datafront; ; int main CirQueue a,b; char x100 = 0,y100 = 0 ; cin >> x >> y; for(int i = 0 ; i < strlen(x); i+) a.EnQueue(xi); for( i = 0 ; i < strlen(y); i+) b.EnQueue(yi); int lenx = strlen(x),leny = strlen(y); if( lenx < leny ) puts("max is y"); return 0; if(lenx > leny ) puts("max is x"); return 0; for( i = 0 ;i < lenx; i+) char xx,yy; xx = a.DeQueue; yy = b.DeQueue; if(xx != yy) if(xx > yy) puts("max is x"); return 0; else puts("max is y"); return 0; puts("x is equel to y"); 五、实验结果 1.1 1.2 2 3 六、心得体会 在这次实验中，我学到很多东西，加强了我的动手能力，并且培养了我的独立思考能力，我们坚持理论联系实际的思想，以实践证实理论，从实践中加深对理论知识的理解和掌握。通过这次实验，我们对数据结构有了更深刻的了解，增强了程序的编写的能力，巩固了专业知识，对程序的模块化观念也又模糊逐渐变的清晰了。在程序的运行与调试过程中出现了很多错误，通过不断的调试虽然修正了一些错误，但是还是有一些错误不知道如何去改，最终参考了老师的参考代码才弄懂。这次的实验，我们对数据结构中栈有了更深刻的理解。
