数据结构综合性实验

华南农业大学信息学院

综合性、设计性实验

起止日期:2011秋

学院软件学院专业班级软件工程R6 学号201131000923 姓名吴鑫潮实

验

题

目

实现平衡二叉排序树的各种算法

自我评价

项目算法设计独立完成情况算法熟练程度测试

通过

成功失败独立帮助掌握了解不懂

插入新结点成功独立掌握通过前序、中序、后序遍历二叉树

（递归）

成功独立掌握通过

前序、中序、后序遍历的非递归

算法

成功独立掌握通过层次遍历二叉树成功独立掌握通过在二叉树中查找给定关键字成功独立掌握通过交换各结点的左右子树成功独立掌握通过求二叉树的深度成功独立掌握通过叶子结点数成功独立掌握通过删除某结点成功帮忙了解通过

●A---------完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合

书写规范，实验报告叙述清晰完整，有详尽的分析和总结。

●B---------完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述清

晰完整。

●C---------完成实验要求的大部分功能，实验报告良好。

●D---------未按时完成实验，或者抄袭。

成

绩

教师签名：杨秋妹

一、分析题目要求

陈述说明程序设计的任务，强调的是程序要做什么并明确规定：

1）各个函数命名，包含的参数，返回值类型

①int InitQueue(SqQueue &Q) 建立队列函数，int；

②int EnQueue(SqQueue &Q,BSTree e)队列插入元素函数，参数e，int；

③int DeQueue(SqQueue &Q, BSTree &e)队列删除元素函数，参数e，int；

④int EmptyQueue(SqQueue Q)判断队列是否为空函数，int；

⑤int InitStack(SqStack &S)建立栈函数，int；

⑥int Push(SqStack &S,BSTree e) 栈元素插入函数，参数e，int；

⑦int Pop(SqStack &S,BSTree &e)栈元素删除函数，参数e，int；

⑧int StackEmpty(SqStack S) 判断栈是否为空函数，int；

⑨int StackLength(SqStack S) 栈长度函数，int；

⑩void R_Rotate(BSTree &p)树的右旋处理函数，void；

11void L_Rotate(BSTree &p)树的左旋处理函数，void；

12void LeftBalance(BSTree &T)树的左平衡处理函数，void；

13void RightBalance(BSTree &T)树的右平衡处理函数，void；

14int InsertAVL(BSTree &T,ElemType e,int &taller)平衡树的节点插入函数，e，taller，int；

15int InsertAVLD(BSTree &T)要输入的元素函数，int；

16int InitDSTable(BSTree &DT)构建动态查找表函数，int；

17int Visit(ElemType e)输出函数，void；

18Int PreOrderTraverse(BSTree &T,int (*Visit)(ElemType ch))递归先序遍历函数，ch，int；

19Int InOrderTraverse(BSTree &T,int (*Visit)(ElemType ch))递归中序遍历函数，ch，int；

20Int PostOrderTraverse(BSTree &T,int (*Visit)(ElemType ch))递归后序遍历函数，ch，int；

21int PreOrderTraverse1(BSTree &T,int (*Visit)(ElemType ch))非递归先序遍历函数，ch，int；

22int InOrderTraverse1(BSTree &T,int (*Visit)(ElemType ch))非递归中序遍历函数，ch，int；

23int PostOrderTraverse1(BSTree &T,int (*Visit)(ElemType ch))飞递归后序遍历函数，ch，int；

24int cengciOrderTraverse(BSTree &T)层次遍历函数，int；

25int exchange(BSTree T)左右子树交换函数，int；

26int Depth (BSTree T )二叉树的深度函数，int；

27int mathBiTree(BSTree T)二叉树的节点函数，int；

28int Search(BSTree T,ElemType ch)二叉树的查找函数，ch，int；

29int DeleteAVL(BSTree &T, int key, bool &shorter)二叉树的节点删除函数，key，shorter；

30int main()主函数，int；

2）输入的形式和输入值的范围

输入的形式都死整型int；输入的范围是非负数；

3）输出的形式

输出格式都是文字加数据，便于使用者操作；

4）程序所能达到的功能

利用switch处理，实现以下各个功能：

（1）插入新结点

（2）前序、中序、后序遍历二叉树（递归）

（3）前序、中序、后序遍历的非递归算法

（4）层次遍历二叉树

（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0)

（6）交换各结点的左右子树

（7）求二叉树的深度

（8）叶子结点数

（9）删除某结点

二、解题思路

对于要实现的各个操作，分别说明其应如何求解，用伪码形式描述其求解过程，求解过程中用到的数据结构。

（1）插入新结点调用int InsertAVL(BSTree &T,ElemType e,int &taller)函数，在通过

void R_Rotate(BSTree &p)树的右旋处理函数；

void L_Rotate(BSTree &p)树的左旋处理函数；

void LeftBalance(BSTree &T)树的左平衡处理函数；

void RightBalance(BSTree &T)树的右平衡处理函数；找出要插入的位

子，将元素插入到二叉树中。

（2）前序、中序、后序遍历二叉树（递归）

先序：T

if(PostOrderTraverse(T->lchild, Visit))

if(PostOrderTraverse(T->rchild, Visit))

if(Visit(T->data))

中序：T

if(InOrderTraverse(T->lchild,Visit))

if(Visit(T->data))

if(InOrderTraverse(T->rchild,Vis it))

后序：T

if(PostOrderTraverse(T->lchild, Visit))

if(PostOrderTraverse(T->rchild, Visit))

if(Visit(T->data))

（3）前序、中序、后序遍历的非递归算法

先序：SqStack S;

BSTree p=T;

InitStack(S);

Vis it(p->data );

Push(S,p->rchild );

p=p->lchild;

依次将根节点打印，右子树进栈，左子树乡下传；

传完后在将栈元素一次取出来

Pop(S,p);在进行上诉操作直到栈为空。

中序：Push(S,p);

p=p->lchild;

根节点进栈，左子树下传；

Pop(S,p);

if(!Visit(p->data ))

return ERROR;

p=p->rchild;

元素退栈，打印节点，节点右传；循环上面操作直到栈空。

后序：SqStack S1,S2;

Pop(S1,p);

Push(S2,p);

if(p->lchild)

Push(S1,p->lchild);

if(p->rchild)

Push(S1,p->rchild);

利用栈的先入后出将树的节点存入S1，并按要求的顺序存到

S2中；

Pop(S2,p);

printf("%d ",p->data);

取出栈S2中的元素，打印。

（4）层次遍历二叉树

SqQueue Q;

BSTree p=T;

DeQueue(Q,p);

if(p->lchild )

{

Visit(p->lchild->data);

EnQueue(Q,p->lchild );

}

if(p->rchild )

{

Visit(p->rchild ->data);

EnQueue(Q,p->rchild );

}利用队列将树顺序存储，顺序打印。

（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0)

if(ch>T->data)

Search(T->rchild,ch);

else if(chdata)

Search(T->lchild,ch);

else if(T->data==ch)

（6）交换各结点的左右子树

p=T->lchild;

T->lchild=T->rchild ;

T->rchild=p;

if(T->lchild)

exchange(T->lchild );

if(T->rchild)

exchange(T->rchild);

（7）求二叉树的深度

depthLeft = Depth( T->lchild );

depthRight= Depth( T->rchild );

depthval = 1 + (depthLeft > depthRight ?depthLeft : depthRight);

（8）叶子结点数

a=0;

else if(T->lchild==NULL&&T->rchild ==NULL)

a=a+1;

else

a=mathBiTree(T->lchild )+mathBiTree(T->rchild );

（9）删除某结点

先找出要删除的节点位子；

判断处理，重新平衡二叉树。

三、调试分析

1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析

对平衡二叉树的删除的算法设计程序存在很大问题。删除节点后需要

对新的排序树平衡化，改变节点的信息，使之形成一棵新的平衡二叉

树；主函数中的实参和子函数中的实参相等，造成调用该子函数时，

虽然没有错误，但其功能不能正确的实现。改变该变量后程序成功实

现各种功能；一些逻辑逻辑运算符书写不正确，造成实现的功能不正

确或程序死循环。

2）使用的测试数据（要求多组）

3）算法的效率分析和改进设想

由于二叉树的存储结构采用的是链式存储，每个二叉树的结点至少包

括三个域：数据域和左、右指针域。各种操作的算法时间复杂度基本

比较合理。大多数操作时间复杂度都为O(n)，n为平衡二叉树中结点

的个数。

对插入算法InsertAVL时间复杂度的分析如下：设在插入关键字e之

前，平衡二叉树中已有n个关键字，在插入时，要找到插入e的合适

位置，需要n次对函数InsertAVL的递归调用，所以时间复杂度为

O(n)；每次InsertAVL算法结束后，都有对二叉树的左处理或右处理，

时间复杂度为O(n)；所以整个插入算法的时间复杂度为O(n)。

对删除算法DeleteA VL时间复杂度的分析和插入算法的分析类似，其

时间复杂度也为O(n)。

4）经验和体会

通过本次实验，我深深的明白了过去打过的代码的重要性，想本次的

实验中计算树的深度，交换左右子树，节点数，遍历等功能都是之前

自己就经验实现过的，如果之前的代码有保留的话就可以直接引用

了；此外加深了我对平衡二叉树的理解，及对于二叉树的节点删除的

理解，不仅仅是删除节点，更重要的是删除后如何确保树的平衡；最

重要的是加强了我对代码的调试能力。

四、附录

带注释的源程序。

注意：1.只交电子版

2.每个同学的资料存放在以学号姓名为文件夹名的目录下，有学习委员收齐后统一交

给任课教师。

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）

数据结构习题(456章)

第四章串 一．选择题 1．若串S='software',其子串的数目是（） A．8 B．37 C．36 D．9 2．设有两个串p和q,求q在p中首次出现的位置的运算称作（） A．连接B．模式匹配C．求串长D．求子串 3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（） A．A BCDEF B．BCDEFG C．BCDPQRST D． BCDEFEF 4．下面的说法中，只有（）是正确的 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 5．两个字符串相等的条件是（） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 二．填空题 1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。 第五章数组和广义表 一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（） A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

中央电大数据结构形成性考核册实验报告

中央电大本科数据结构形成性考核册实验报告 实验名称：实验一线性表 线性表的链式存储结构 【问题描述】 某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序： （1）显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。 （2）在链表中删除一个最高分和一个最低分的结点。 （3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。 【基本要求】 （1）建立一个评委打分的单向链表； （2）显示删除相关结点后的链表信息。 （3）显示要求的结果。 【实验步骤】 （1）运行PC中的Microsoft Visual C++ 6.0程序， （2）点击“文件”→“新建”→对话窗口中“文件”→“c++ Source File”→在“文件名”中输入“X1.cpp” →在“位置”中选择储存路径为“桌面”→“确定”， （3）输入程序代码， 程序代码如下: #include #include #include #include #include #define NULL 0 #define PWRS 5 //定义评委人数 struct pw //定义评委信息 { char name[6]; float score; int age; }; typedef struct pw PW; struct node //定义链表结点 {struct pw data; struct node * next; }; typedef struct node NODE; NODE *create(int m); //创建单链表 int calc(NODE *h); //计算、数据处理

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构实验8实验报告

暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.37 6.38 6.39 指导教师孙世良 实验项目编号实验8 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午～月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 掌握遍历二叉树的各种操作及其实现方式。 理解二叉树线索化的实质是建立结点与其在相应序列中的前去或后继之间的直接联系，熟练掌握二叉树的线索化的过程以及在中序线索化树上找给定结点的前驱和后继的方法。 (二)实验内容和要求 6.37试利用栈的基本操作写出先序遍历的非递归形式的算法。 6.38同题6.37条件，写出后序遍历的非递归算法（提示：为分辨后序遍 历时两次进栈的不同返回点需在指针进栈时同时将一个标志进栈）。 6.39假设在二叉链表的结点中增设两个域：双亲域以指示其双亲结点； 标志域以区分在遍历过程中到达该结点时应继续向左或向右或访问该节点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。(三)主要仪器设备 实验环境：Microsoft Visual Studio 2012 (四)源程序

6.37： #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define TRUE 1 #define FALSE 0 typedef struct bitnode{ char data; struct bitnode *lchild,*rchild; }bitnode,*bitree; void create(bitree &T){ char t; t=getchar(); if(t==' ') T=NULL; else{ if( !( T=(bitnode*)malloc(sizeof(bitnode)) ) ) exit(0); T->data=t; create(T->lchild); create(T->rchild); } } typedef struct{ bitree *base; bitree *top; int stacksize; }sqstack; void initstack(sqstack &S){ S.base=(bitree*)malloc(STACK_INIT_SIZE *sizeof(bitree)); if(!S.base) exit(0); S.top=S.base; S.stacksize=STACK_INIT_SIZE; } void Push(sqstack &s,bitree e){ if(s.top - s.base >= s.stacksize){ s.base =

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

图书管理系统 c++ 数据结构实验报告

图书管理系统 c++ 数据结构实验报告学生姓名: 学院: 软件学院 专业: 信息管理与信息系统 题目: 图书管理系统 成绩 指导教师 2011年1月6日 1(设计目的(小标题黑体五号字) 《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑 关系，讨论其 在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的 效率进行简单的分 析和讨论。进行数据结构课程设计要达到以下目的: , 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力; , 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; , 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2(设计内容和要求 1)每种书的登记内容包括书号、书名、著作者、现存量和库存量; 2)对书号建立索引表(线性表)以提高查找效率; 3)系统主要功能如下:

*采编入库:新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加; *借阅:如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量; *归还:注销对借阅者的登记，改变该书的现存量。 3(本设计所采用的数据结构 定义图书链表和图书索引结构 struct Book { char BookID[10];/*图书编号*/ char BookName[512];/*书名*/ char Writer[512];/*作者*/ int CurrentNumber;/*现存量*/ Book *pNext;/*下一个图书信息*/ }; struct Index { char BookID[10];/*图书编号*/ Index *pNext;/*下一个索引指针*/ }; 1 /*借阅信息结构*/ struct Borrow {

数据结构实验报告(四)

《数据结构》实验报告 班级： 学号： 姓名：

实验四二叉树的基本操作实验环境：Visual C++ 实验目的： 1、掌握二叉树的二叉链式存储结构； 2、掌握二叉树的建立，遍历等操作。 实验内容： 通过完全前序序列创建一棵二叉树，完成如下功能： 1)输出二叉树的前序遍历序列； 2)输出二叉树的中序遍历序列； 3)输出二叉树的后序遍历序列； 4)统计二叉树的结点总数； 5)统计二叉树中叶子结点的个数； 实验提示： //二叉树的二叉链式存储表示 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

一、程序源代码 #include #include #define MAXSIZE 30 typedef char ElemType; typedef struct TNode *BiTree; struct TNode { char data; BiTree lchild; BiTree rchild; }; int IsEmpty_BiTree(BiTree *T) { if(*T == NULL) return 1; else return 0;

} void Create_BiTree(BiTree *T){ char ch; ch = getchar(); //当输入的是"#"时，认为该子树为空 if(ch == '#') *T = NULL; //创建树结点 else{ *T = (BiTree)malloc(sizeof(struct TNode)); (*T)->data = ch; //生成树结点 //生成左子树 Create_BiTree(&(*T)->lchild); //生成右子树 Create_BiTree(&(*T)->rchild); } } void TraverseBiTree(BiTree T) { //先序遍历 if(T == NULL) return;

数据结构图的遍历实验报告

实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include

typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;ivexnum;i++) if(strcmp(v,G->vexs[i].name)==0) { c=i; break;} return c;} MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入{ int i,j,k,w; char v1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum);

数据结构实验报告册

实验一线性表的操作 实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的： 参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。 二、实验要求： 1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 1．设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：建立一个线性表，首先依次输人数据元素1，2，3，…，10，然后删除数据元素6，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过10个。 第一题源代码： #include using namespace std; template //定义模板类SeqList class SeqList { private: int length,x,j,data[10]; public: public: SeqList( ) //无参构造函数 { length=0; } SeqList(T a[ ], int n) //有参构造函数 { for(int i=0;i

} T Get(int i) //按位查找，取线性表的第i个元素 { } int Locate(T x ) //按值查找，求线性表中值为x的元素序号{ } void Insert(int i, T x) //在线性表中第i个位置插入值为x的元素{ } T Delete(int i) //删除线性表的第i个元素 { if(length==0) throw"下溢"; if(i<1||i>length) throw"位置异常"; x=data[i-1]; for(j=i;j theseqlist(a,n); cout<<"删除前元素："; for(int i=0;i

数据结构实验报告模板

2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数： 主函数； 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构实验二叉树

实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7);

正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：

数据结构实验报告图实验

邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph（DataType a[], int n, int e）; ~MGraph（）{ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: " cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

数据结构实验报告.

实验目的 （1）学会用先序创建一棵二叉树。 （2）学会采用递归算法对二叉树进行先序、中序、后序遍历。 （3）学会打印输出二叉树的遍历结果。 实验内容 【问题描述】建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 【基本要求】 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 【测试数据】 ABCффDEфGффFффф(其中ф表示空格字符) 则输出结果为先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 【选作内容】 采用非递归算法实现二叉树遍历。 实验步骤 （一）需求分析 1、在这个过程中，接受遍历的二叉树是从键盘接受输入（先序），以二叉链表作为存储结构，建立的二叉树。因此，首先要创建一棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的元素设定为大写字母ABCDEFG，输出的先序，中序，后序遍历分别为ABCDEGF,CBEGDFA,CGBFDBA。二叉树可以表示为：

接受的输入数据在进行递归的先序，中序，后序遍历后，分别将结果打印出来。 2、在程序运行的过程中可以看到，以计算机提示用户执行的方式进行下去，即在计算机终端上提示“输入二叉树的先序序列”后，由用户在键盘上输入ABC##DE#G##F###，之后相应的选择遍历及遍历结果显示出来。 3、程序执行的命令包括：首先是二叉树的先序序列被创建输入，其次是对输入进去的先序序列有次序的进行先序，中序，后序遍历。最后是打印出二叉树的遍历结果。 4、测试数据 （1）在键盘上输入的先序序列ABC##DE#G##F### （2）先序遍历结果ABCDEGF

数据结构实验报告

数据结构实验报告 第 6 次实验 学号：20141060106 姓名：叶佳伟 一、实验目的 1、复习图的逻辑结构、存储结构及基本操作； 2、掌握邻接矩阵、邻接表及图的创建、遍历； 3、了解图的应用。 二、实验内容 1、（必做题）假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作： （ 1）构造图（包括有向图、有向网、无向图、无向网）； （ 2）根据深度优先遍历图； （ 3）根据广度优先遍历图。 三、算法描述 （采用自然语言描述） 四、详细设计 （画出程序流程图） 五、程序代码 （给出必要注释） #include #include #include #include #include #define INFINITY 255678 /*赋初值用*/ #define MAX_VERTEX_NUM 20 /* 最大顶点个数*/ enum {DG, DN, UDG, UDN}; typedef struct ArcCell {

int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/ }AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM][5];/*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum, arcnum;/*图的当前顶点数和弧数*/ int kind; }MGraph; void CreateDG(MGraph *G); void CreateDN(MGraph *G); void CreateUDG(MGraph *G); void CreateUDN(MGraph *G); int LocateVex(MGraph *G, char v[]); void print(MGraph *G); int main(void) { MGraph *G; G = (MGraph *)malloc(sizeof(MGraph)); printf("请选者0-有向图,1-有向网,2-无向图,3-无向网: "); scanf("%d", &G->kind); switch(G->kind) { case DG : CreateDG(G); print(G); break; case DN : CreateDN(G); print(G); break; case UDG : CreateUDG(G); print(G); break; case UDN : CreateUDN(G);

数据结构实验三实验报告

三题目：哈夫曼编/译码器 班级：姓名：学号：完成日期：15.11.14 一、题目要求 描述：写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0. 输入：输入表示字符集大小为n（n <= 100）的正整数，以及n个字符和n个权值（正整数，值越大表示该字符出现的概率越大）； 输入串长小于或等于100的目标报文。 输出：经过编码后的二进制码，占一行； 以及对应解码后的报文，占一行； 最后输出一个回车符。 输入样例： 5 a b c d e 12 40 15 8 25 bbbaddeccbbb 输出样例： 00011111110111010110110000 bbbaddeccbbb 提示：利用编码前缀性质。 二、概要设计 1.设计需要的数据结构：树型结构 2.需要的抽象数据类型： ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3,…,Dm(m>0)，对于任意j≠k(≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi?Di有?H; (3) 对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1，H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi}) 是一棵符合本定义的树，称为根root的子树。 基本操作： InitTree(&T); 操作结果：构造空树T。

数据结构实验报告无向图

《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v)

以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main()

数据结构实验报告 - 答案汇总

数据结构(C语言版) 实验报告

专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序 的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存