栈和队列的基本操作实验报告

1、数据结构实验报告一软件132201300514211徐蜀实验二 栈和队列的基本操作及其应用一、实验目的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;sqstack;3、队列的链

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 + stackincreme

5、nt) * sizeof(selemtype); /栈满了，重新申请内存 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

6、) ; return ok;7、初始化队列 /* 函数功能：初始化队列参数：队列（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 */

7、int enqueue(linkqueue &q, qelemtype e) p = (queueptr)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) /判断

8、队列是否为空 return error; p = q.front - next; e = p - data; q.front - next = p - next; if(q.rear = p) 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()!

9、=)/对字符的判断 不断输入字符enqueue (q,c);push (s,c);n+;for( j=1;jn) /如果j n则说明全部相等cout 这个字符串不是回文字符串 endl;elsecout 这个字符串是回文字符串 endl; return 0;说明：通过调用序列号不同的函数进行各种操作。函数根据每次输入的数进行判断不在110内的函数将结束，否则将继续进行。 程序调试及运行结果分析(应包含多组测试数据) 五、实验总结通过这次试验，我知道自己还有很多不足，还会犯一些细节上的错误，但是也因此对栈和队列的操作有了很好的认识附录 1开始、程序流程图执行主函数main 声明一个栈s和队列q！

10、t n (c=getchar()!= y n y入栈入队列j=1;j=n;j+ n出栈出队列，并判断值是否想等 y判断是否是回文数，并输出判断语句结束 2、程序清单#include#includeusing namespace std;/栈的表示和实现#define stack_init_size 100#define stackincrement 10#define error 0#define ok 1typedef char selemtype;typedef struct selemtype *base; selemtype *top; int stacksize;sqstack;/队

11、列的表示和实现typedef struct qnode selemtype data; struct qnode *next; qnode, *queueptr;typedef struct queueptr 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_ini

12、t_size; return ok;int push(sqstack &s, selemtype e) if(s.top - s.base = s.stacksize) s.base = (selemtype *)realloc(s.base, (s.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

13、 &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(qnode); if(!q.front) return error; q.front -next = null; return ok;int enqueue(linkqueue &q, selemtype e) queueptr p = (queueptr)malloc(sizeof(

14、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; 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;cha