软件技术基础栈-队列-二叉树的应用(共13页)

1、精选优质文档-倾情为你奉上软件技术基础相关实验实验名称： 栈的应用 一、实验目的：掌握顺序栈和链式栈的定义和运算，了解它们的应用。二、实验要求：1、掌握顺序栈的定义、特点及常见算法。2、掌握链式栈的定义、特点及常见算法。3、参照给定的栈的程序样例，验证给出的栈的常见算法。4、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1、顺序栈的操作和测试。要求：设计一个主函数实现对顺序栈进行操作测试。测试方法为：依次把数据元素1,3,5，7,9入栈，并显示入栈结果；接着依次出栈其中的数据元素并在屏幕上显示。2、链式栈的操作

2、。设计一个主函数实现对链式栈进行操作测试。测试方法为：依次把数据元素3,6,9，12,15入栈，并显示入栈结果；接着依次出栈其中的数据元素并在屏幕上显示。3、栈的应用。利用顺序栈求解表达式（a+b）*(c-d)的值。四、程序要求：1、顺序栈的长度自行确定。2、重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。3、写出完整的程序并能调试通过。五、实验结果：入栈一个元素：删除一个元素：取栈顶元素：退出六、实验中遇到的问题及解决方法： 栈的操作有了前面的基础，相对而言能够编写出来，遇到的问题还是地址操作相关的，通过不断的练习对于指针对于地址传递应该说有了比较好的理解。附：源程序（自行编写或修

3、改的程序。若为修改程序请注明修改部分的功能，若为书上实例则可不附。）#include "stdio.h"#include"stdlib.h"#include"string.h"#define MAXNUM 20#define ElemType int /*定义顺序栈的存储结构*/typedef struct ElemType stackMAXNUM; int top;SqStack;/*初始化顺序栈*/void InitStack(SqStack *p)if(!p) printf("内存分配失败!");p->

4、top=-1;/*入栈*/void Push(SqStack *p,ElemType x) if(p->top<MAXNUM-1) p->top=p->top+1; p->stackp->top=x; else printf("Overflow! n");/*出栈*/ElemType Pop(SqStack *p) ElemType x; if(p->top>=0) x=p->stackp->top; printf("以前的栈顶数据元素%d已经被删除! n",p->stackp->t

5、op); p->top=p->top-1; return x; else printf("Underflow! n"); return(0); /*获取栈顶元素*/ElemType GetTop(SqStack *p)ElemType x;if(p->top>=0)x=p->stackp->top;printf("n栈顶元素为：%dn",x);return x;elseprintf("Underflow! n");return 0;/*遍历顺序栈*/void OutStack(SqStack *p)

6、int i;printf("n");if(p->top<0)printf("这是一个空栈!");printf("n");for(i=p->top;i>=0;i-) printf("第%d个数据元素是：%6dn",i,p->stacki);/*主函数*/void main()SqStack *q;int cord;ElemType a; printf("第一次使用必须初始化! n"); do printf("n-主菜单- "); printf(&q

7、uot;n 1 初始化顺序栈 "); printf("n 2 插入一个元素 "); printf("n 3 删除栈顶元素 "); printf("n 4 取栈顶元素 "); printf("n 5 置空顺序栈 "); printf("n 6 结束程序运行 "); printf("n- "); printf("n请输入指令"); scanf("%d",&cord); printf("n"); swit

8、ch(cord) case 1: q=(SqStack*)malloc(sizeof(SqStack); InitStack(q); OutStack(q); break; case 2: printf("请输入要插入的数据元素：a="); scanf("%d",&a); Push(q,a); OutStack(q); break; case 3: Pop(q); OutStack(q); break; case 4: GetTop(q); OutStack(q); break; case 5: printf("n顺序栈被置空! n&q

9、uot;); OutStack(q); break; case 6: exit(0); while(cord<=6);实验名称： 队列的应用 一、实验目的：掌握循环队列和链队列的定义及其基本运算，了解并熟悉队列的应用。二、实验要求：1、掌握循环队列和链队列的特点及常见算法。2、参照给定的循环队列和链队列的程序样例，验证给出的队列的常见算法。3、能对队列进行简单的应用。4、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1、循环队列的基本操作。要求：设计一个主函数对循环队列进行测试。主要功能有：入队操作、出队

10、操作、取对头元素。2、链队列的基本操作。要求：设计一个主函数对链队列进行测试。主要功能有：链队列的初始化、求队列的长度、入队列操作、出队列操作、取对头元素。3、对队列进行简单的应用。四、程序要求：1、能用数字化菜单的方式选择队列的各项操作。2、循环队列中选择入队或出队时能一次入队或出队多个数据。3、程序具有一定的防误操作性，能处理常见的突发事件。4、写出完整的程序并能调试通过。五、实验结果：1、创建队列进行入队操作2、出对操作，根据先进先出原理，一次出队3、取出队头元素4、判断队列是不是空队列5将队列置空六、实验心得体会：通过本次实验，让我了解了队列的一些操作，掌握了队列编程的技巧。学会了循环

11、队列的算法。队列的操作在计算机领域应用较为广泛，通过队列的学习也让我了解到了一些队列相关的应用，让我对于计算机操作系统的任务控制也有了一定的了解。先进先出的模式在生活中也十分常见，有了队列可以解决很多的实际难题，队列的知识需要我们掌握。附：源程序（自行编写或修改的程序。若为修改程序请注明修改部分的功能，若为书上实例则可不附。）#include<stdio.h>#include<stdlib.h>typedef int boolean;#define true 1#define false 0typedef struct queueint element10;int re

12、ar;int front;*Squeue,Queue;void Enqueue(Squeue q);/入队操作void Dequeue(Squeue q);/出队操作void Getfront(Squeue q);/取对头元素boolean IsEmpty(Squeue q);/判断是否为空void EnEmpty(Squeue q);/使队列置空void main()int input;Squeue q;q=(Squeue)malloc(sizeof(Queue);q->front=0;q->rear=-1;printf("=循环队列=n");printf(&

13、quot; 1. 入队操作n");printf(" 2. 出队操作n");printf(" 3. 取对头元素n");printf(" 4. 判断队列是否为空n");printf(" 5. 置空队列n");printf("=n");doprintf("请输入您的操作：");scanf("%d",&input);switch(input)case 1:Enqueue(q); break;case 2:Dequeue(q); break;cas

14、e 3:Getfront(q); break;case 4:if(IsEmpty(q)printf("不存在该队列n");elseprintf("存在该队列n"); break;case 5:EnEmpty(q); break;while(input<=5);void Enqueue(Squeue q)int num,i=0,record=0;printf("请输入您想入队的元素个数(一次队列存在不超过10个数据)：");scanf("%d",&num);for(i;i<num;i+)print

15、f("请输入第%d个元素：",i+1);if(+q->rear<=9)if(q->rear=q->front&&record=1)printf("数据溢出n");system("pause");exit(1);else if(q->rear=q->front)record+;scanf("%d",&q->elementq->rear);else q->rear-=10;scanf("%d",&q->ele

16、mentq->rear);if(q->rear=q->front)printf("数据溢出n");system("pause");exit(1);void Dequeue(Squeue q)if(IsEmpty(q)printf("不存在队列n");elseif(q->front<=9)printf("%dn",q->elementq->front+);elseq->front=0;printf("%dn",q->elementq->f

17、ront+);void Getfront(Squeue q)if(IsEmpty(q)printf("不存在该队列n");elseprintf("%dn",q->elementq->front);boolean IsEmpty(Squeue q)if(q->rear=-1|q->front-1=q->rear)return true;else return false;void EnEmpty(Squeue q)q->front=0;q->rear=-1;实验名称： 二叉树的生成与遍历 一、实验目的：1、熟悉二叉

18、树节点的定义和二叉树的定义；2、熟悉二叉树链式结构的生成方式；3、掌握二叉树遍历算法的实现。二、实验要求：1、掌握二叉树的常见算法：二叉树的生成、判断树是否为空、插入或删除节点、插入或删除子树、二叉树遍历等。2、参照给定的二叉树的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。3、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1编程实现二叉树的生成及遍历算法，要求：（1）编写创建二叉链表形式存储的二叉树程序并输出。 （2）编写递归实现二叉树的先序、中序、后序遍历算法。 （3）编写主函数测试以上二叉树

19、的创建和遍历函数。 2. 假设二叉树采用链式存储结构进行存储，编写程序实现二叉树的所有叶子结点的统计并输出统计个数。四、实验结果：创建、先序遍历、中序遍历、后序遍历、查找。5、 实验中遇到的问题及解决方法： 实验过程中，对于二叉树的应用落实到代码上遇到了很多困难，对我而言最困难的就是创建二叉排序树。如何将自己输入的数据按二叉排序树的方式排序对我而言是一个难点，再参阅了资料之后我才写出。六、实验心得体会：通过本次实验让我对二叉树的应用有了一定的了解，通过编写代码中遇到的各种困难也让我对于数据结构的理解有所加深，同时也在一定程度上提高了我的编程能力。这次编程参考借鉴了资料，借助别人的代码才成功修改

20、完成，以后的学习中我要更加扎实，努力将知识点掌握牢固。附：源程序（自行编写或修改的程序。若为修改程序请注明修改部分的功能，若为书上实例则可不附。）#include<stdio.h>#include<stdlib.h>typedef struct Nodeint data;struct Node *lchild;struct Node *rchild;NODE,*BSTree;BSTree search(BSTree pTree,int key)if(!pTree | pTree->data = key)return pTree;else if(key < p

21、Tree->data)return search(pTree->lchild,key);elsereturn search(pTree->rchild,key);/查找元素bool search_BSTree(BSTree pTree,int key,BSTree parent,BSTree &p)if(!pTree) p = parent;return false;else if(key = pTree->data)p = pTree;return true;else if(key < pTree->data)return search_BSTre

22、e(pTree->lchild,key,pTree,p); elsereturn search_BSTree(pTree->rchild,key,pTree,p); bool insert(BSTree &pTree,int key)BSTree p;if(!search_BSTree(pTree,key,NULL,p)BSTree pNew = (BSTree)malloc(sizeof(NODE);pNew->data = key;pNew->lchild = pNew->rchild = NULL;if(!p) pTree = pNew;else i

23、f(key < p->data)p->lchild = pNew; elsep->rchild = pNew;return true;elsereturn false;/创建二叉树BSTree create_BSTree(int *arr,int len)BSTree pTree = NULL;int i;for(i=0;i<len;i+)insert(pTree,arri);return pTree;void fdlr(BSTree pTree) /先序遍历if(pTree)printf("%d ",pTree->data);fdlr(pTree->lchild);fdlr(pTree->rchild);void cdlr(BSTree pTree) /中序遍历if(pTree)if(pTree->lchild)cdlr(pTree->lchild);printf("%d ",pTree->data);if(pTree-&