数据结构课程设计实验报告栈和队列的用

1、数学与计算机学院实 验 报 告（ 2009 /2010 学年 第 2 学期）课程名称数据结构实验名称实验1 栈和队列的用实验时间2010年4月26日指导单位软件工程系指导教师学生姓名班级学号学院（系）数学与计算机专 业软件工程实验名称栈和队列的应用指导教师实验类型验证实验学时3实验时间16：00-17：40一、 实验目的和要求1） 栈的顺序存储结构和链式存储结构；2） 掌握栈的先进后出的原则；3） 掌握栈的基本运算；加深理解顺序栈和链栈的意义，理解用栈的插入和删除操作算法。4） 掌握队列的顺序存储结构和链式存储结构；5） 掌握队列的先进先出的原则；6） 掌握队列的基本运算；加深理解顺序循环队列

2、和链队列的意义，理解用顺序循环队列和链队列的入队和出队等基本操作算法。实验要求：（1）理解栈初始化、判断栈是否空、入栈、出栈等算法；（2）理解队列入队、出队等算法。二、实验环境(实验设备) 硬件: 微型计算机p4 软件: windows xp+microsoft visual c+6.0三、实验原理及内容实验题目:1.请使用链栈实现通用数制转换程序：将任意一个十进制数转换成p进制的数。（p分别取2，8，16）2. 假定一个单向循环链表来表示队列（即循环链队），该队列只设一个队尾指针rear，不设队首指针，试编写下列各种运算的算法：1） 向循环链队插入一个元素值为x的结点；2） 从循环链队中删除

3、一个结点；3） 输出队列中所有元素；实验前准备：(1)请实现链栈的基本操作：初始化、进栈、出栈、输出。并要求上机验证通过。(2)创建只有一个尾指针的单向循环队列的的结构体定义和初始化操作。实验时完成1-2两题实验后：考虑如果将2小题链队中的结点的数据类型改一个学生的通讯簿：姓名，手机号码、邮箱、qq号。如何实现该题的相应算法 ,并要求上机验证通过。实验解答：1) 链栈中的结点是如何定义的？写出结构体描述。typedef struct dnode struct dnode *next;/指针域int data; /数据域dnode; /置于sqstack前，因为后面的用到了dnode 2）写出链

4、栈的入栈算法void push(sqstack &s,dnode *p,int e) p=(dnode *)malloc(sizeof(dnode);/定义结点，分配空间 p-data=e;/链栈不存在空间不足 /链栈是用指针取数据，这是顺序栈的操作.指向下一个元素是通过-next p-next=s.top;s.top=p;/p始终指向最后结点 3）写出链栈的出栈算法？void pop(sqstack &s) while(s.top!=s.base) /非空栈 if(s.top-data=10)/大于10进行字母转换 printf(%c,(char)(s.top-data+55);else p

5、rintf(%d,s.top-data); s.top=s.top-next;printf(n); 4）写出利用链栈进行通用数制转换算法？在该算法中你是如何考虑进位制中数码转换和保存的？void dtop(sqstack &s) s.base=s.top=(dnode *)malloc(sizeof(dnode); s.base-next=0; int n,i; printf(请输入十进制数:); scanf(%d,&n); int x; printf(请输入要转化成的进制:); scanf(%d,&x); while(n) dnode *p=0;p=(dnode*)malloc(sizeof

6、(dnode); /指向结点的指针push(s,p,n%x); /将余数进栈n=n/x; /将商做为新的被除数pop(s);答：在算法中，考虑到十进制数转换成十六进制数，在模余数大于10时要将其转换成大写字母，又由大写字母与数字间的转换关系来进行判断输出。4） 在数据转换中，你使用的测试数据有哪些？测试了哪几种进位制？结果是什么？答：测试数据有28，测试二进制：11100 测试数据有33，测试八进制：41 测试数据有95，测试十六进制：5f6对于只设一个队尾指针的循环链队，你是如何初始的？写出代码。dnode *initqueue(queue *q)dnode *head;/头指针head=(

7、dnode *)malloc(len);/分配空间if(head)head-data=0; /头指针初始化head-next=head; /循环q-rear=head;return (head); /返回头指针elseexit (0);7）对于只设一个队尾指针的循环链队，其结点的结构是怎样定义的？写出c语言代码。typedef struct dnodeint data;struct dnode *next;dnode; 9）写出向循环链队插入一个元素值为x的结点算法的代码。时间复杂是多少？void inseart(queue *q,dnode *head,int x)dnode *p,*q;q

8、=(dnode *)malloc(len);printf(插入数据:);scanf(%d,&q-data);p=head-next;int k=0;while(p!=head)k+;if(k=x-1)q-next=p-next;p-next=q;printf(插入成功!n);break;p=p-next;if(p=head)printf(插入失败!n);时间复杂度：10）写出从循环链队中删除一个结点算法，时间复杂度是多少？void delet(queue *q,dnode *head)dnode *p;if(q-rear=head & n=0)printf(队空!n);elsep=head-n

9、ext; printf(删除的元素是:);printf(%d,p-data);printf(n);head-next=head-next-next; free(p); printf(删除成功!n);时间复杂度：11）写出输出队列中所有元素算法。void input(queue *q,dnode *head)dnode *p,*q;p=(dnode *)malloc(len);printf(请输入数据 :);scanf(%d,&p-data);q-rear-next=p;p-next=head;n+;q-rear=p;/p始终作为最后一个结点 12）对于只设一个队尾指针rear的循环链队，如何获

10、取队首结点？入队和出队操作的核心语句是什么？定义一个头指针head入队核心语句： q-rear-next=p;p-next=head;q-rear=p;出队核心语句： if(q-rear=head & n=0)/判断是否队空printf(队列空，没有可输出元素!n);exit (0);p=head-next;while(p!=head)/输出队列元素printf(%d ,p-data);p=p-next;13）如果将循环链队的结点值类型改为学生的通讯簿，你认为入队和出队算法需要修改吗？请说明理由。同时给出学生通讯簿的定义。我认为不需要改变结点值类型，因为改变后只是结点存放数据增加了一部分数据类

11、型，而与队列的其他操作没有关系，只需要将入队时的输入数据增加即可。typedef struct dnodechar *name;char *telephone;char *email;unsigned long qq;struct inode *next;dnode;四、实验小结（包括问题和解决方法、心得体会、意见与建议等）1在链栈进行数据的插入和删除的过程中，你认为与线性表的插入和删除有区别吗？栈是如何进行数据的插入和删除的？有区别，线性表直接就可以进行插入删除操作，栈的大小是一定的，不能改变，在进行操作的时首先要判断栈满，而链栈则不需要这样。对于栈，数据的插入是通过创建一个新节点，然后对它

12、的数据域赋值，将next指针值指向上一次栈的元素，然后修改栈顶元素的指针，使rear始终指向栈顶元素。出栈的时候先将栈顶元素的指针值减一，然后输出数据，修改栈顶元素的指针，释放上一次的栈顶元素。接着进行下一次的出栈出栈。2利用栈进行通用数制转换的算法设计中，你认为应该注意些什么？可以将该算法转换成递归实现吗？如行，请写出通用数制转换的递归算法。在设计数值转换的算法中应该注意的是十进制与其他进制数之间的转换关系，尤其是与十六进制的相互转换，那里的转换关系相对要复杂一点。但是最终要确保转换设置的正确性。void zhuanghuan(stack *head,int x,int y)while(x)

13、pushstack(head,x%y);x=x/y;zhuanghuan(head,x,y);3在循环链队中，你准备的测试数据是：（给出你测试时使用的数据）请输入数据 :1请输入数据 :2请输入数据 :3请输入数据 :4请输入数据 :5请输入数据 :6请输入数据 :7请输入数据 :8队列!1 2 3 4 5 6 7 8 4你是如何测试该次实验中栈操作和队列操作的相关算法的？指出测试了哪些方面？我是通过在主函数中顺序调用相关函数来测试相关算法的。1测试栈的入栈和出栈操作以及初始化等相关算法。2测试了队列的初始化、入队、出队、查找、删除等相关算法。3测试了运用栈来对数值进行进制（2、8、16）转换

14、算法操作 5.通过本次实验，你有些什么收获？有什么不足？通过本次试验我让对栈的顺序存储结构和链式存储结构加深了理解，掌握了栈的先进后出的原理及其基本运算操作；理解了顺序栈和链栈的不同，掌握了栈的插入和删除操作算法；明白了队列的顺序存储结构和链式存储结构及队列都是先进先出的原则；掌握了队列的基本算法；加深了对顺序循环队列和链队列的理解，掌握了用顺序循环队列和链队列的入队和出队等基本操作算法。不足的是：没有在链队中实现队列元素的插入，最终都没有找到该函数未实现插入的原因.五、指导教师评语成 绩批阅人日 期数制转换源代码：#include#include #include #include/定义结构

15、体typedef struct dnode struct dnode *next;/指针域int data; /数据域dnode; /置于sqstack前，因为后面的用到了dnodetypedef struct dnode *top; dnode *base;sqstack;/进栈void push(sqstack &s,dnode *p,int e) p=(dnode *)malloc(sizeof(dnode);/定义结点，分配空间 p-data=e; /链栈不存在空间不足 /链栈是用指针取数据，这是顺序栈的操作.指向下一个元素是通过-next p-next=s.top;s.top=p;/

16、p始终指向最后结点 /出栈void pop(sqstack &s) while(s.top!=s.base) /非空栈 if(s.top-data=10)/大于10进行字母转换 printf(%c,(char)(s.top-data+55);else printf(%d,s.top-data); s.top=s.top-next;printf(n);/进制数转化 void dtop(sqstack &s) s.base=s.top=(dnode *)malloc(sizeof(dnode); s.base-next=0; int n,i; printf(请输入十进制数:); scanf(%d,

17、&n); int x; printf(请输入要转化成的进制:); scanf(%d,&x); while(n) dnode *p=0;p=(dnode*)malloc(sizeof(dnode); /指向结点的指针push(s,p,n%x); /将余数进栈n=n/x; /将商做为新的被除数pop(s);void main() sqstack s;dtop(s);循环链队源代码：#include #include #include #define null 0#define len sizeof(struct dnode)typedef struct dnode /定义数据结构体int data

18、;struct dnode *next;dnode; typedef struct qptrdnode *rear;queue;int n=0;/初始化dnode *initqueue(queue *q)dnode *head;/定义头指针head=(dnode *)malloc(len);/分配空间if(head)head-data=0; head-next=head; /循环q-rear=head;return (head); elseexit (0);int emputy(queue *q,dnode *head)/判断队空if(q-rear=head & n=0)return (1);

19、elsereturn (0);void input(queue *q,dnode *head)dnode *p,*q;p=(dnode *)malloc(len);printf(请输入数据 :);scanf(%d,&p-data);q-rear-next=p;p-next=head;n+;q-rear=p;/p始终作为最后一个结点void delet(queue *q,dnode *head)dnode *p;if(q-rear=head & n=0)printf(队空!n);elsep=head-next; printf(删除的元素是:);printf(%d,p-data);printf(n);head-next=head-next-next; free(p); printf(删除成功!n);/插入元素 void inseart(queue *q,dnode *head,int x)dnode *p,*q;q=(dnode *)malloc(len);print