LIAOCHENG UNIVERSITY |
【20 16 ～20 17 学年第 1 学期】
| 【一、基本信息】 | |||||
| 【实验课程】 | 数据结构 | ||||
| 【设课形式】 | □ 非☑ | 【课程学分】 | 4 | ||
| 【实验项目】 | 栈和队列 | ||||
| 【项目类型】 | 基础□ 综合☑ 设计□ 研究创新□ 其它[ ] | 【项目学时】 | 4 | ||
| 【学生姓名】 | 沈凯 | 【学 号】 | 2015205377 | ||
| 【系别专业】 | 软件开发 | ||||
| 【实验班组】 | 15级 11班 组 台 | ||||
| 【同组学生】 | |||||
| 【实验室名】 | 综合实验楼 | ||||
| 【实验日期】 | 2016. | 【报告日期】 | 2016. | ||
| 【二、实验教师对报告的最终评价及处理意见】 | |||||
实验成绩： （涂改无效） 指导教师签名： 张振领 2016年 月 日 | |||||
| 注：要将实验项目、实验课程的成绩评定及课程考核办法明确告知学生，并报实验管理中心备案 | |||||
| 【三、实验预习】 | ||
| 实验目的和要求： 1、熟练掌握二叉树的结构，以及这种数据结构的特点； 2、会定义二叉树的链式存储结构； 3、能实现二叉树的建立、遍历等功能，需要完成先序遍历、中序遍历和后序遍历递归算法以及中序非递归算法。 | ||
| 实验内容和原理或涉及的知识点： 自己编写程序实现二叉树的各种基本操作，如二叉树的建立，遍历等。 | ||
| 实验条件： 具有C语言集成开发环境的计算机 | ||
| 实验设计方案： 设计的算法有： 1、递归建立二叉树； 2、先序递归遍历二叉树； 3、中序递归遍历二叉树； 4、后序递归遍历二叉树。 5、中序非递归遍历二叉树 | ||
| 实验预习成绩（涂改无效） | 合格□ | 不合格□ |
| 【四、实验过程、数据和实验结果记录】 |
| 实验方法、步骤、操作过程的记录描述或程序代码。实验过程中输入/输出数据、程序运行结果的记录。（可加附页） 1、根据实验预习阶段的实验设计方案，编写伪C代码如下。 typedef struct BiTNode { TelemType data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; status CreateBiTree(BiTree &T){ //按先序次序输入二叉树中结点的值,空格表示空树 //生成二叉树的二叉链表存储结构，T为根结点指针 scanf("%c",&ch); if (ch==' ') T=NULL; else{ if (!(T=(BiTNode *) malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=ch; //建立根结点 CreateBiTree( T->lchild); //建立左子树 CreateBiTree(T->rchild); //建立右子树 } return OK; } //CreateBiTree status PrintElement(TelemType e) { printf("%c",e); //输出元素值 return OK; } status PreorderTraverse(BiTree T, status(*visit)(TelemType e)) { //先序遍历根结点指针为T的二叉树 if (T) { if (visit(T->data)) if (PreorderTraverse(T->lchild,visit)) if (PreorderTraverse(T->rchild,visit)) return OK; return ERROR; }else return OK; //if (T) }//PreorderTraverse Status InorderTraverse1(BiTree T, Status(*visit)(TElemType e)) { //先序遍历根结点指针为T的二叉树 if (T) { if (InorderTraverse1(T->lchild,visit)) if (visit(T->data)) if (InorderTraverse1(T->rchild,visit)) return OK; return ERROR; }else return OK; //if (T) }//InorderTraverse status PostorderTraverse(BiTree T, status(*visit)(TelemType e)) { //后序遍历根结点指针为T的二叉树 if (T) { if (PostorderTraverse(T->lchild,visit)) if (PostorderTraverse(T->rchild,visit)) if (visit(T->data)) return OK; return ERROR; }else return OK; //if (T) }//PostorderTraverse Status InorderTraverse2(BiTree T, Status (*visit)(TElemType e)) { SqStack S; InitStack(S); BiTree p=T; while( p || !StackEmpty(S) ){ // 找到最左下的结点 if (p) { Push(S,p); p=p->lchild; } // 根指针进栈，遍历左子树 else { //根指针退栈，访问根结点，遍历右子树 Pop(S,p); if (!visit(p->data) ) return ERROR; p=p->rchild; } //else } // while return OK; }// InOrderTraverse |
#include #include #include #define LIST_INIT_SIZE 10 #define LISTINCREMENT 100 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define TRUE 1 #define FALSE 0 #define true 1 #define false 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define OPSETSIZE 7 #define MAXQSIZE 100 #define NULL 0 typedef char TelemType; typedef int Status; typedef struct BiTNode { TelemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; Status CreateBiTree(BiTree *T); Status PrintElement(TelemType e); Status visit(TelemType e); Status PreorderTraverse(BiTree T, Status *visit(TelemType e)); Status InorderTraverse(BiTree T, Status *visit(TelemType e)); Status PostorderTraverse(BiTree T, Status *visit(TelemType e)); int main() { BiTree T; printf("Please input characters to create a tree:\\n"); CreateBiTree(&T); printf("PreorderTraverse:"); PreorderTraverse(T, visit); printf("\\nInorderTraverse:"); InorderTraverse(T, visit); printf("\\nPostorderTraverse:"); PostorderTraverse(T, visit); return 0; } Status CreateBiTree(BiTree *T) { char ch; ch = getchar(); if (ch == ' ') *T = NULL; else { if (!(*T = (BiTNode *) malloc(sizeof (BiTNode)))) exit(OVERFLOW); (*T)->data = ch; CreateBiTree(&((*T)->lchild)); CreateBiTree(&((*T)->rchild)); } return OK; } Status PrintElement(TelemType e) { printf("%c", e); return OK; } Status visit(TelemType e) { printf("%c ", e); return OK; } Status PreorderTraverse(BiTree T, Status *visit(TelemType e)) { if (T) { if (visit(T->data)) if (PreorderTraverse(T->lchild, visit)) if (PreorderTraverse(T->rchild, visit)) return OK; return ERROR; } return OK; } Status InorderTraverse(BiTree T, Status *visit(TelemType e) ) { if (T) { if (InorderTraverse(T->lchild, visit)) if (visit(T->data)) if (InorderTraverse(T->rchild, visit)) return OK; return ERROR; } return OK; } Status PostorderTraverse(BiTree T, Status *visit(TelemType e)) { if (T) { if (PostorderTraverse(T->lchild, visit)) if (PostorderTraverse(T->rchild, visit)) if (visit(T->data)) return OK; return ERROR; } return OK; int main() { BiTree T; printf("Please input characters to create a tree:\\n"); CreateBiTree(&T); printf("PreorderTraverse:"); PreorderTraverse(T, visit); printf("\\nInorderTraverse:"); InorderTraverse(T, visit); printf("\\nPostorderTraverse:"); PostorderTraverse(T, visit); return 0; } 实验数据和实验结果记录 2、分析如果将数转换为二进制， conversion函数的修改； 3、分析如果没有初始化栈的操作时程序的运行结果； 3、写出自己的心得体会。
3、编译、链接、运行程序。} 程序的一个运行实例如下。 记录成绩（涂改无效） 合格□ 不合格□ 【五、实验结果分析】 1、分析数制转换时后进先出的特点；
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
