《数据结构实验指导书(C++)- 栈、队列、串的操作.docx》由会员分享，可在线阅读，更多相关《数据结构实验指导书(C++)- 栈、队列、串的操作.docx（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验二 栈、队列、串的操作实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。二、实验要求：1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1. 堆栈类测试和应用问题。要求： (1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。 (2)定义数据元素的数
2、据类型为如下形式的结构体：typedef struct char taskname10;/任务名 int taskno;/任务号 DataType； 设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。2. 队列类测试和应用问题。要求： 设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。3设计串采用顺序存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。 *4. 设计算法利用栈类实现把十进制
3、整数转换为二至九进制之间的任一进制输出。 *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 顺序栈类的定义const int StackSize=10; /10只是示例性的数据，可以根据实际问题具体定义template /定义模板类SeqStackc
4、lass SeqStackpublic: SeqStack( ) top=-1; /构造函数，栈的初始化 SeqStack( ) /析构函数 void Push( T x ); /将元素x入栈 T Pop( ); /将栈顶元素弹出 T GetTop( ) if (top!=-1) return datatop; /取栈顶元素（并不删除） bool Empty( ) top=-1? return 1: return 0; /判断栈是否为空private: T dataStackSize; /存放栈元素的数组 int top; /栈顶指针，指示栈顶元素在数组中的下标;template void S
5、eqStack:Push(T x) if (top= StackSize-1) throw 上溢; top+; datatop=x; template T SeqStack: Pop( ) if (top=-1) throw 下溢; x=datatop-; return x; 2 链式栈类的定义template class LinkStackpublic: LinkStack( ) top=NULL; /构造函数，置空链栈 LinkStack( ); /析构函数，释放链栈中各结点的存储空间 void Push(T x); /将元素x入栈 T Pop( ); /将栈顶元素出栈 T GetTop(
6、 ) if (top!=NULL) return top-data; /取栈顶元素（并不删除） bool Empty( ) top=NULL? return 1: return 0; /判断链栈是否为空栈private: Node *top; /栈顶指针即链栈的头指针;template void LinkStack:Push(T x) s=new Node; s-data=x; /申请一个数据域为x的结点s s-next=top; top=s; /将结点s插在栈顶 template T LinkStack:Pop( ) if (top=NULL) throw 下溢; x=top-data; /
7、暂存栈顶元素 p=top; top=top-next; /将栈顶结点摘链 delete p; return x; template LinkStack:LinkStack( ) while (top) p=top-next; delete top; top=p; 3双栈类的定义const int StackSize=100; /100只是示例数据，需根据具体问题定义template class BothStack public: BothStack( ) top1= -1; top2=StackSize; /构造函数，将两个栈分别初始化 BothStack( ) /析构函数 void Push
8、(int i, T x); /将元素x压入栈i T Pop(int i); /对栈i执行出栈操作 T GetTop(int i); /取栈i的栈顶元素 bool Empty(int i); /判断栈i是否为空栈private: T dataStackSize; /存放两个栈的数组 int top1, top2; /两个栈的栈顶指针，分别指向各自的栈顶元素在数组中的下标;template void BothStack: Push(int i, T x )if (top1=top2-1) throw 上溢;if (i=1) data+top1=x;if (i=2) data-top2=x;temp
9、late T BothStack: Pop(int i)if (i=1) /将栈1的栈顶元素出栈if (top1= -1) throw 下溢; return datatop1-; if (i=2) /将栈2的栈顶元素出栈if (top2=StackSize) throw 下溢; return datatop2+; 4.循环队列类定义const int QueueSize=100; /定义存储队列元素的数组的最大长度template /定义模板类CirQueueclass CirQueuepublic: CirQueue( ) front=rear=0; /构造函数，置空队 CirQueue(
10、) /析构函数 void EnQueue(T x); /将元素x入队 T DeQueue( ); /将队头元素出队 T GetQueue( ); /取队头元素（并不删除） bool Empty( ) front=rear? return 1: return 0; /判断队列是否为空private: T dataQueueSize; /存放队列元素的数组 int front, rear; /队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置;template void CirQueue:EnQueue(T x) if (rear+1) % QueueSize =front) throw
11、 上溢; rear=(rear+1) % QueueSize; /队尾指针在循环意义下加1 datarear=x; /在队尾处插入元素 template T CirQueue:GetQueue( ) if (rear=front) throw 下溢; i=(front+1) % QueueSize; /注意不要给队头指针赋值 return datai; template T CirQueue:DeQueue( ) if (rear=front) throw 下溢; front=(front+1) % QueueSize; /队头指针在循环意义下加1 return datafront; /读取并
12、返回出队前的队头元素，注意队头指针5.链队列类定义template class LinkQueuepublic: LinkQueue( ); /构造函数，初始化一个空的链队列 LinkQueue( ); /析构函数，释放链队列中各结点的存储空间 void EnQueue(T x); /将元素x入队 T DeQueue( ); /将队头元素出队 T GetQueue( ) if (front!=rear) return front-next-data; /取链队列的队头元素 bool Empty( ) front=rear? return 1: return 0; /判断链队列是否为空priva
13、te: Node *front, *rear; /队头和队尾指针，分别指向头结点和终端结点;template T LinkQueue:DeQueue( )if (rear=front) throw 下溢;p=front-next; x=p-data; /暂存队头元素front-next=p-next; /将队头元素所在结点摘链if (p-next=NULL) rear=front; /判断出队前队列长度是否为1delete p; return x;template LinkQueue:LinkQueue( ) s=new Node; s-next=NULL; /创建一个头结点s front=rear=s; /将队头指针和队尾指针都指向头结点stemplate void LinkQueue:EnQueue(T x) s=new Node; s-data=x; /申请一个数据域为x的结点s s-next=NULL; rear-next=s; /将结点s插入到队尾 rear=s; 注意问题1重点理解栈、队列和串的算法思想，能够根据实际情况选择合适的存储结构。 2栈、队列的算法是后续实验的基础（树、图、查找、排序等）。