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

数据结构课程设计实验报告-栈和队列的用 数学与计算机学院 , 2009 /2010 学年 第 2 学期, 课程名称 数据结构 实验名称 实验1 栈和队列的用 2010 4 26 实验时间 年 月 日 指导单位 软件 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 系 指导教师 学生姓名 班级学号 数学与计算机 软件工程 学院(系) 专 业 实验报告 实验名称 栈和队列的应用 指导教师 实验类型 验证 实验学时 3 实验时间 16:00-17:40 一、 实验目的和要求 1) 栈的顺序存储结构和链式存储结构; 2) 掌握栈的先进后出的原则; 3) 掌握栈的基本运算;加深理解顺序栈和链栈的意义，理解用栈的插入和删除操作算法。 4) 掌握队列的顺序存储结构和链式存储结构; 5) 掌握队列的先进先出的原则; 6) 掌握队列的基本运算;加深理解顺序循环队列和链队列的意义，理解用顺序循环队列和链队列 的入队和出队等基本操作算法。 实验要求:(1)理解栈初始化、判断栈是否空、入栈、出栈等算法;(2)理解队列入队、出队等算法。 二、实验环境(实验设备) 硬件: 微型计算机P4 软件: Windows XP+Microsoft Visual C++6.0 三、实验原理及内容 实验 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目: 1.请使用链栈实现通用数制转换程序:将任意一个十进制数转换成p进制的数。(p分别取2，8，16) 2. 假定一个单向循环链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 来表示队列(即循环链队)，该队列只设一个队尾指针rear，不设队首指针，试编写下列各种运算的算法: 1) 向循环链队插入一个元素值为x的结点; 2) 从循环链队中删除一个结点; 3) 输出队列中所有元素; 2 实验报告 实验前准备: (1)请实现链栈的基本操作:初始化、进栈、出栈、输出。并要求上机验证通过。 (2)创建只有一个尾指针的单向循环队列的的结构体定义和初始化操作。 实验时完成1-2两题 实验后:考虑如果将2小题链队中的结点的数据类型改一个学生的通讯簿:姓名，手机号码、邮箱、QQ号。如何实现该题的相应算法 ,并要求上机验证通过。 实验解答: 1) 链栈中的结点是如何定义的,写出结构体描述。 typedef struct dnode { struct dnode *next;//指针域 int data; //数据域 }Dnode; //置于Sqstack前，因为后面的用到了Dnode 2)写出链栈的入栈算法 void push(Sqstack &S,Dnode *p,int e) { p=(Dnode *)malloc(sizeof(Dnode));//定义结点，分配空间 p->data=e; 3 实验报告 ///链栈不存在空间不足 //链栈是用指针取数据，这是顺序栈的操作.指向下一个元素是通过->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 printf("%d",S.top->data); S.top=S.top->next; } printf("\n"); } 4 实验报告 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(Dnode)); //指向结点的指针 push(S,p,n%x); //将余数进栈 n=n/x; //将商做为新的被除数 } pop(S); } 答:在算法中，考虑到十进制数转换成十六进制数，在模余数大于10时要将其转换成 大写字母，又由大写字母与数字间的转换关系来进行判断输出。 5 实验报告 4)在数据转换中，你使用的测试数据有哪些,测试了哪几种进位制,结果是什么, 答:测试数据有28，测试二进制:11100 测试数据有33，测试八进制:41 测试数据有95，测试十六进制:5F 6 实验报告 6对于只设一个队尾指针的循环链队，你是如何初始的,写出代码。 DNode *InitQueue(Queue *Q) { DNode *Head;//头指针 Head=(DNode *)malloc(LEN);//分配空间 if(Head) { Head->data=0; //头指针初始化 Head->next=Head; //循环 Q->rear=Head; return (Head); //返回头指针 } else exit (0); } 7)对于只设一个队尾指针的循环链队，其结点的结构是怎样定义的,写出C语言代 码。 typedef struct Dnode { int data; struct Dnode *next; }DNode; 7 实验报告 9)写出向循环链队插入一个元素值为x的结点算法的代码。时间复杂是多少, void Inseart(Queue *Q,DNode *Head,int x) { DNode *p,*q; q=(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"); } 时间复杂度: 8 实验报告 10)写出从循环链队中删除一个结点算法，时间复杂度是多少, void delet(Queue *Q,DNode *Head) { DNode *p; if(Q->rear==Head && n==0) printf("队空!\n"); else { p=Head->next; 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始终作为最后一个结点 } 9 实验报告 12)对于只设一个队尾指针rear的循环链队，如何获取队首结点,入队和出队操作的核心语句 是什么, 定义一个头指针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)如果将循环链队的结点值类型改为学生的通讯簿，你认为入队和出队算法需要修改吗,请说 明理由。同时给出学生通讯簿的定义。 我认为不需要改变结点值类型，因为改变后只是结点存放数据增加了一部分数据类型，而与队 列的其他操作没有关系，只需要将入队时的输入数据增加即可。 typedef struct Dnode { char *name; char *telephone; char *email; unsigned long qq; struct Inode *next; }Dnode; 10 实验报告 四、实验小结,包括问题和解决 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 、 心得体会 决胜全面小康心得体会学党史心得下载党史学习心得下载军训心得免费下载党史学习心得下载 、意见与建议等, 1(在链栈进行数据的插入和删除的过程中，你认为与线性表的插入和删除有区别吗,栈是如何进行数据的插入和删除的, 有区别，线性表直接就可以进行插入删除操作，栈的大小是一定的，不能改变，在进行操作的时首先要判断栈满，而链栈则不需要这样。对于栈，数据的插入是通过创建一个新节点，然后对它的数据域赋值，将next指针值指向上一次栈的元素，然后修改栈顶元素的指针，使rear始终指向栈顶元素。出栈的时候先将栈顶元素的指针值减一，然后输出数据，修改栈顶元素的指针，释放上一次的栈顶元素。接着进行下一次的出栈出栈。 2(利用栈进行通用数制转换的算法设计中，你认为应该注意些什么,可以将该算法转换成递归实现吗,如行，请写出通用数制转换的递归算法。 在设计数值转换的算法中应该注意的是十进制与其他进制数之间的转换关系，尤其是与十六进制的相互转换，那里的转换关系相对要复杂一点。但是最终要确保转换设置的正确性。 void zhuanghuan(Stack *Head,int x,int y) { while(x) { PushStack(Head,x%y); x=x/y; zhuanghuan(Head,x,y); } 3(在循环链队中，你准备的测试数据是:(给出你测试时使用的数据) 请输入数据 :1 请输入数据 :2 请输入数据 :3 11 实验报告 请输入数据 :4 请输入数据 :5 请输入数据 :6 请输入数据 :7 请输入数据 :8 队列! 1 2 3 4 5 6 7 8 4(你是如何测试该次实验中栈操作和队列操作的相关算法的,指出测试了哪些方面, 我是通过在主函数中顺序调用相关函数来测试相关算法的。1测试栈的入栈和出栈操作以及初始化等相关算法。2测试了队列的初始化、入队、出队、查找、删除等相关算法。3测试了运用栈来对数值进行进制(2、8、16)转换算法操作 5.通过本次实验，你有些什么收获,有什么不足, 通过本次试验我让对栈的顺序存储结构和链式存储结构加深了理解，掌握了栈的先进后出的原理及其基本运算操作;理解了顺序栈和链栈的不同，掌握了栈的插入和删除操作算法;明白了队列的顺序存储结构和链式存储结构及队列都是先进先出的原则;掌握了队列的基本算法;加深了对顺序循环队列和链队列的理解，掌握了用顺序循环队列和链队列的入队和出队等基本操作算法。 不足的是:没有在链队中实现队列元素的插入，最终都没有找到该函数未实现插入的原因. 五、指导教师评语 12 实验报告 成 绩 批阅人 日 期 数制转换源代码: #include #include #include #include //定义结构体 typedef struct dnode { struct dnode *next;//指针域 int data; //数据域 }Dnode; //置于Sqstack前，因为后面的用到了Dnode typedef 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;//p始终指向最后结点 13 实验报告 } //出栈 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",&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); } 14 实验报告 循环链队源代码: #include #include #include #define NULL 0 #define LEN sizeof(struct Dnode) typedef struct Dnode //定义数据结构体 { int data; struct Dnode *next; }DNode; typedef struct qptr { DNode *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); } else exit (0); } int Emputy(Queue *Q,DNode *Head)//判断队空 { if(Q->rear==Head && n==0) return (1); else return (0); } void input(Queue *Q,DNode *Head) 15 实验报告 { 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"); else { p=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); printf("插入数据:"); scanf("%d",&q->data); p=Head->next; int k=0; while(p!=Head) { k++; if(k==x-1) 16 实验报告 { q->next=p->next; p->next=q; printf("插入成功!\n"); break; } p=p->next; } if(p==Head) printf("插入失败!\n"); } //输出队列元素 void print(Queue *Q,DNode *Head) { DNode *p; if(Q->rear==Head && n==0)//判断是否队空 { printf("队列空，没有可输出元素!\n"); exit (0); } p=Head->next; while(p!=Head)//输出队列元素 { printf("%d ",p->data); p=p->next; } printf("\n"); } void main() { int i; Queue *Q; DNode *Head;//建立头指针 Q=(Queue *)malloc(sizeof(struct qptr)); Head=InitQueue(Q); if(Emputy(Q,Head)) printf("the queue is emputy!\n"); else printf("the queue isn't emputy!\n"); for(i=0;i<8;i++) 17 实验报告 input(Q,Head); printf("队列!\n"); print(Q,Head); delet(Q,Head); printf("删除后的队列!\n"); print(Q,Head); Inseart(Q,Head,9); print(Q,Head); } 18