《栈和队列的基本操作实验报告.pdf》由会员分享，可在线阅读，更多相关《栈和队列的基本操作实验报告.pdf（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、.数据结构 实 验 报 告 一 软件 132 201300514211.徐蜀.实验二 栈和队列的基本操作及其应用 一、实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈和队列的特点，即后进先出和先进先出的原则。3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。二、实验内容 1回文判断 三、实验要求 1、按照数据结构实验任务书，提前做好实验预习与准备工作。2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。3、严格按照数据结构实验报告模板和规范，及时完成实验报告。四、实验步骤（说明：依据实验内容
2、分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（函数）的伪码算法、函数实现、程序编码、调试与分析。附流程图与主要代码）、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、栈的初始长度与需要再增加的长度#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef char SElemType;/定义 SElemType 为 char 型 .2、栈的顺序存储表示 typedef struct SElemType*base;SElemType*top;int stacksize
3、;SqStack;3、队列的链式表示方法 typedef struct QNode SElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;4、初始化栈./*函数功能：对栈进行初始化 参数：栈（SqStack&S）成功返回 1，否则返回 0 */int InitStack(SqStack&S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);/申请内存 if(!S.base)/
4、判断有无申请到空间 return ERROR;/没有申请到内存，返回 0 S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;5、入栈操作/*函数功能：将元素入栈 参数：栈（SqStack&S）,插入元素 e 插入成功返回 1，否则返回 0 */int Push(SqStack&S,SElemType e)if(S.top-S.base=S.stacksize)/判断栈顶与栈底的差是否大于栈的/容量.S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SEl
5、emType);/栈满了，重新申请内存 if(!S.base)/判断是否申请成功 return ERROR;/不成功返回 0 S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;6、出栈操作/*函数功能：将栈中的元素弹出 参数：栈(SqStack&S),记录元素 e */int Pop(SqStack&S,SElemType&e)if(S.top=S.base)/判断栈是否为空 return ERROR;e=*(-S.top);return OK;.7、初始化队列 /*函数功能：初始化队列 参数：队列
6、（LinkQueue&Q）成功返回 1，否则返回 0 */int InitQueue(LinkQueue&Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);/申请结点的内存 if(!Q.front)/判断有无申请到空间 return ERROR;/没有返回 0 Q.front-next=NULL;return OK;8.在队列队尾插入元素/*函数功能：在队列队尾插入元素 参数：队列（LinkQueue&Q），插入元素 e 成功返回 1，否则返回 0 */int EnQueue(LinkQueue&Q,QElemType e).p=(QueuePtr
7、)malloc(sizeof(QNode);/申请新的结点 if(!p)return ERROR;p-data=e;p-next=NULL;Q.rear-next=P;Q.rear=p;return OK;9.删除队头元素/*函数功能：删除对头元素 参数：队列（LinkQueue&Q），记录值 e 成功返回 1，否则返回 0 */int DeQueue(LinkQueue&Q,QElemType&e)if(Q.front=Q.rear)/判断队列是否为空 return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p).
8、Q.rear=Q.front;free(p);return OK;10、主函数 int main()SqStack S;/声明一个栈 LinkQueue Q;/声明一个队列 char m,k,c;int n=0,i,j,t=0,z=0;while(!t)cout 请输入你要判断回文的字符串，输入结束：;InitQueue(Q);InitStack(S);while(c=getchar()!=)/对字符的判断 不断输入字符 EnQueue(Q,c);Push(S,c);n+;.for(j=1;jn)/如果 j n 则说明全部相等 cout 这个字符串不是回文字符串 endl;else cout
9、这个字符串是回文字符串 endl;return 0;说明：通过调用序列号不同的函数进行各种操作。函数根据每次输入的数进行判断不在 110 内的函数将结束，否则将继续进行。程序调试及运行结果分析(应包含多组测试数据).五、实验总结 通过这次试验，我知道自己还有很多不足，还会犯一些细节上的错误，但是也因此对栈和队列的操作有了很好的认识 附录 1、程序流程图 开始 执行主函数 main.N Y N Y N Y 2、程序清单#include 声明一个栈S和队列Q！t(c=getchar()!=入栈入队列 j=1;j=n;j+出栈出队列，并判断值是否想等 判断是否是回文数，并输出判断语句 结束.#inc
10、lude using namespace std;/栈的表示和实现#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1 typedef char SElemType;typedef struct SElemType*base;SElemType*top;int stacksize;SqStack;/队列的表示和实现 typedef struct QNode SElemType data;.struct QNode*next;QNode,*QueuePtr;typedef struct Qu
11、euePtr front;QueuePtr rear;LinkQueue;/关于栈的函数 int InitStack(SqStack&S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;int Push(SqStack&S,SElemType e).if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base,(S
12、.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;int Pop(SqStack&S,SElemType&e)if(S.top=S.base)return ERROR;e=*(-S.top);return OK;./关于队列的函数 int InitQueue(LinkQueue&Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QN
13、ode);if(!Q.front)return ERROR;Q.front-next=NULL;return OK;int EnQueue(LinkQueue&Q,SElemType e)QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p)return ERROR;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;.int DeQueue(LinkQueue&Q,SElemType&e)if(Q.front=Q.rear)return ERROR;QueuePtr p=Q.front-next
14、;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;/主函数 int main()SqStack S;LinkQueue Q;char m,k,c;int n=0,i,j,t=0,z=0;while(!t).cout 请输入你要判断回文的字符串：endl;InitQueue(Q);InitStack(S);while(c=getchar()!=)/对字符的判断 不断输入字符 EnQueue(Q,c);Push(S,c);n+;for(j=1;jn)cout 这个字符串是回文字符串 endl;else cout 这个字符串不是回文字符串 endl;.return 0;