北邮数据结构实验报告.doc

精品学习资料范文
北邮数据结构实验报告
篇一：北邮数据结构第三次实验-实验报告
数据结构实验报告
实验名称： 实验三——栈和队列
学生姓名：
班 级：
班内序号：
学 号：
日 期：
1. 实验要求
1.1 实验目的
通过选择下面两个题目之一进行实现，掌握如下内容：
?
?
?
1.2 实验内容
根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。 二叉树的基本功能：
1、二叉树的建立
2、前序遍历二叉树
3、中序遍历二叉树
4、后序遍历二叉树
5、按层序遍历二叉树
6、求二叉树的深度
7、求指定结点到根的路径
8、二叉树的销毁
9、其他：自定义操作
编写测试main()函数测试线性表的正确性 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力
2. 程序分析
2.1 二叉链表
2.2 二叉树的二叉链表存储示意图
2.3 关键算法分析
2.3.1算法1：void create(Binode T * R, T data[], int i);
[1] 算法功能：创建一个二叉树
[2] 算法基本思想：通过构造函数创建一个二叉树，构造函数通过调用函数
create()创建二叉树，关于函数create()的伪代码：
1.定义根指针，输入节点储存的data，若输入“#”，则该节点为空；
2.申请一个新节点，判断它的父结点是否不为空，如果不为空在判断其为左
或者右孩子，并把地址付给父结点，把data写入。
[3] 算法空间、时间复杂度：O（n）
[4] 代码逻辑（可用伪代码描述）：if(data[i-1]!=0){R = new Binode T R- data
= data[i-1];R- lch = R- rch = NULL;create(R- lch, data,
2*i);create(R- rch, data, 2*i+1);}
2.3.2算法2：void Destroy(Binode T *R);
[1] 算法功能：二叉树的销毁
[2] 算法基本思想：采用后序遍历的方法，释放节点。
[3] 算法空间、时间复杂度：
O(n)
[4] 代码逻辑（可用伪代码描述）：
if(R!=NULL){Destroy(R- lch);Destroy(R- rch);
delete R;}
2.3.3算法3：void preorder(Binode T *R);
[1] 算法功能：前序遍历二叉树
[2] 算法基本思想：设置递归边界条件：if root==null则停止递归；2打印起始
节点的值，并先后在左子数右子数上递归调用打印函数
[3] 算法空间、时间复杂度：O（n)
[4] 代码逻辑（可用伪代码描述）：
if(R!=NULL){cout R- data;preorder(R- lch);preorder(R- rch);}
2.3.4算法4：void Inorder(Binode T *R);
[1] 算法功能：中序遍历二叉树
[2] 算法基本思想： 1.设置递归边界条件：if root==null则停止递归，2.递归
遍历左子树3.打印根节点数据域内容4.递归遍历右子树
[3] 算法空间、时间复杂度：O（n)
[4] 代码逻辑（可用伪代码描述）：
if(R!=NULL){Inorder(R- lch);cout R- data;
Inorder(R- rch);}
2.3.5算法5：void Postorder(Binode T *R);
[1] 算法功能：后序遍历二叉树
[2] 算法基本思想：1.设置递归边界条件：if root==null则停止递归2.递归遍历
左子树3.递归遍历右子树4.访问根结点数据域
[3] 算法空间、时间复杂度：O（n)
[4] 代码逻辑（可用伪代码描述）：
if(R!=NULL){Postorder(R- lch);Postorder(R- rch);
cout R- data;}}
2.3.6算法6：void Levelorder(Binode T *R);
[1] 算法功能：层序遍历二叉树
[2] 算法基本思想：1.队列Q及所需指针的定义和初始化2.如果二叉树非空，将
根指针入队3.循环直到队列Q为空3.1 q=队列Q的队头元素出队3.2 访问
节点q的数据域cout q- data 3.3 若节点q存在左孩子，则将左孩
子指针入队 if (q- lchild != NULL) Q[rear++] = q- lchild; 3.4若
节点q存在右孩子，则将右孩子指针入队if (q- rchild != NULL)
[3] 算法空间、时间复杂度：O（n)
[4] 代码逻辑（可用伪代码描述）：Binode T *queue[10000];int f = 0, r = 0;if(R!=NULL) queue[++r] = R;while(f!=r){Binode T
*queue[++f];cout p- data;if(p- lch!=NULL)
queue[++r] = p- if(p- rch!=NULL)queue[++r] = p- }
2.3.7算法7：int Depth(Binode T *R, int d);
[1] 算法功能：计算二叉树深度
[2] 算法基本思想：1. 定义和初始化计数深度的参数2．如果根节点为空，return0
3．如果根节点为非空，递归调用自身的到叶子节点到根的路径长度，输出其中
较大的作为树的深度
[3] 算法空间、时间复杂度：O（n)
[4] 代码逻辑（可用伪代码描述）：if(R==NULL) return d;
if((R- lch==NULL) (R- rch==NULL))return d+1;else{int m =
Depth(R- lch, d+1);int n = Depth(R- rch, d+1);return n m?n:m;}
2.3.8算法8：void path(Binode T *root, char m);
[1] 算法功能：输出指定结点到根结点的路径
[2] 算法基本思想：代码：1.建立一个存储路径结点结构，定义和初始化结构体的数
组2.当root不为空或top为0时，进入循环3.当此时root所指的节点的数据
不为指定数据时，将root指向它的左孩子4.当此时root所指的节点的数据为
指定数据时，访问其数据域并输出
[3] 算法空间、时间复杂度：O(n)
[4] 代码逻辑（可用伪代码描述）：Binode T *stack[10000];Binode T int tag[10000];
int top = 0;s =
root;do{while(s!=NULL){top++;stack[top]=s;tag[top]=0;s=s- }
if(top 0){if(tag[top] == 1){if(stack[top]- data == m){cout 路径：
\t for(int
i=1;i =top;i++)cout stack[i]- data;break;}top--;}else{s=stack[top]
;if(top 0){s=s- tag[top]=1;}}}}while(s!=NULL || top!=0);}
3. 程序运行结果
篇二：北京邮电大学 计算机学院数据结构第一次实验报告
实验报告（1）
姓 名：学 号： 实验目的、实验原理和内容：
一、实验目的：熟悉实验环境，掌握线性表动态存储结构的基本特点。
二、实验原理：链表运算，完成有关单链表有关运算的程序。
三、实验内容及要求：
1、 有一个带头结点的单链表，写出在其值为x的结点之后插入m个结点的算法程序。
2、已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写—个删除表中所有值大于min且小于max的元素(若表中存在这样的元素)的算法程序。
要求：请同学把步骤、调试好的程序及存在的问题写在下面。
第一题实验程序代码：
#include stdio.h
#include stdlib.h
typedef struct Lnode{
int data;
struct Lnode *next;
}Lnode,*Linklist;//非头结点结构定义
typedef struct{
int len;
Linklist head;
}HeadNode;//头结点结构定义
Linklist creatlist(HeadNode *L);//创造含头结点的链表函数
Linklist get(Linklist R,int key);//在链表中寻找值为key的结点，并返回该结点
Linklist invert(HeadNode *L,Linklist S,int num); //在链表中的某个结点之后插入num个结点 void printlist(HeadNode *L,Linklist S);//打印链表中数据域的值
void deletelist(Linklist R);//释放链表
int main()
{
HeadNode *L;
Linklist S;
int key,num;
L=(HeadNode*)malloc(sizeof(HeadNode));
if(L==NULL)
return 0;
L- head=creatlist(L);//含头结点的链表的创建
printlist(L,L- head);
if(L- head==NULL)//判断链表中是否只有头结点
{
printf( The list has no data, can t be inverted!\n
return 0;
}
printf( Please input the data you want to research:\n
scanf( %d , key);//提示用户输入需要查找的数值
fflush(stdin);//清空缓冲区，防止读入用户多输入的数据
S=get(L- head,key);
if(!S)
return 0;
printf( Please input the number of the Lnode you want to invert:\n //提示用户输入需要插入的结点值
scanf( %d , num);
S=invert(L,S,num);
printlist(L,L- head);
deletelist(L- head);
free(L);//释放头结点
system( pause
return 0;
}
Linklist creatlist(HeadNode *L)//创造含头结点的链表函数
{
Linklist S=NULL,R=NULL,H=NULL;
int i;
printf( Please input the length of the list:\n
scanf( %d , L- len);
fflush(stdin);
if(L- len =0)
return 0;
printf( Please input the data:\n
for(i=0;i =L- len-1;i++)
{
S=(Linklist)malloc(sizeof(Lnode));
if(S!=NULL)
{
if(R==NULL)
{
R=S;
H=S;
}
scanf( %d , S- data);
R- next=S;
R=S;
}
}
fflush(stdin);
R- next=NULL;
L- head=H;
return L- head;
}
Linklist get(Linklist R,int key)//在链表中寻找值为key的结点，并返回该结点
{
Linklist S;
S=R;
while(S S- data!=key)
S=S- next;
if(!S)
{
printf( Can t find the data %d, the list can t be inverted!\n ,key);
return NULL;
}
else
{
printf( Find the data successful!\n
return S;
}
}
Linklist invert(HeadNode *L,Linklist S,int num)//在链表中的某个结点之后插入num个结点 {
Linklist R,K,H;
int i;
R=S;
H=S- next;
if(num 0)
{
printf( Please input the data of %d inverted Lnode:\n ,num);
L- len+=num;
}
else
printf( Invert failed!\n
for(i=0;i =num-1;i++)
{
K=(Linklist)malloc(sizeof(Lnode));
scanf( %d , K- data);
R- next=K;
R=K;
}
R- next=H;
return S;
}
void printlist(HeadNode *L,Linklist S)//打印链表中数据域的值
{
if (S==NULL)
printf( The list is empty.\n
else
{
printf( The list has %d Lnodes.\n ,L- len);
printf( The list is:\n
while(S!=NULL)
{
printf( %d--- ,S- data);
S=S- next;
}
printf( NULL\n
}
}
void deletelist(Linklist R)//释放链表
{
Linklist temp;
while(R!=NULL)
{
temp=R;
R=R- next;
free(temp);
}
}
第一题存在的问题:
1.注意头结点与非头结点结构定义的差别，链表的长度由用户输入，需要排除用户错误输入即L- len小于0时的情况，并注意判断链表
中是否只含有头结点；
2. 在进行链表的创建与结点的查找操作时，需要读入每个结点的数据值及num的值，这时候需要清空缓存区，防止读入用户输入的多余的数据。
第二题实验程序代码：
#include stdio.h
#include stdlib.h
typedef struct Lnode{
int data;
struct Lnode *next;
}Lnode,*Linklist;//非头结点结构定义
typedef struct{
int len;
Linklist head;
}HeadNode;//头结点结构定义
Linklist creatlist(HeadNode *L);//创造含头结点的链表函数
Linklist get(HeadNode *L,Linklist H,int num,int judge);//在链表中寻找数值小于num的结点并返回
Linklist delete(HeadNode *L,Linklist S,Linklist R,int min);//释放链表中两个节点之间的所有节点空间
int judgelist(Linklist S);//判断链表是否按升序排列
void printlist(HeadNode *L,Linklist S);//打印链表中数据域的值
void deletelist(Linklist S);//释放链表
int main()
{
HeadNode *L=NULL;
Linklist S,R;
int min,max;
L=(HeadNode*)malloc(sizeof(HeadNode));
if(L==NULL)
return 0;
L- head=creatlist(L);
printlist(L,L- head);
while((judgelist(L- head))==0)//判断链表是否按升序排列，若不是，则提示用户重新输入，直至符合要求
篇三：北邮数据结构实验报告排序
数据结构实验报告
实验名称： 实验四——排序 学生姓名： 班 级： 班内序号： 学 号：
日 期： 2014年12月19日
1．实验要求
实验目的
通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 实验内容
使用简单数组实现下面各种排序算法，并进行比较。 排序算法：1、插入排序2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性。
2. 程序分析
首先，题目要求测试不同的数据，所以可以手动输入待排序元素。其次，由于对一组数据要求用不同的排序算法来处理，所以需要一个复制函数把排序前的无序数组寄存出去，为下一次排序做准备。再次，由于每次排序后都需要把排序后的结果打印出来，代
码是一样的，根据相同的代码可以封装成一个函数的思想，所以还需增加一个打印函数。
2.1 存储结构
本程序采用简单数组来储存输入的待排序数组
2.2 关键算法分析
核心算法思想：
1. 利用教材讲述的基本算法思想，实现七种排序算法，统计其运行相关数据。
2. 将七种排序函数入口地址作为函数指针数组，实现快速调用和统计。使得程序代码可读 性增、结构更加优化。 关键算法思想描述和实现：
关键算法1： 实现七种算法的基本排序功能。
1、 插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。插入排序的思想是：每次从无序区取一元素将其添加到有序区中。 2、 希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，
待整个序列基本有序时，再对全体记录进行一次直接插入排序。
3、 冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。 4、 快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则
大于基准，然后对两部分重复上述过程，直至整个序列排序完成。
5、 选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中
的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。
2.3 其他
时间复杂度与空间复杂度
理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示：
3. 程序运行结果
程序运行框图：
实际测试和分析： 实际运行结果如下： 1． 正序排序
2．
倒序排序
3． 乱序排序
4. 总结
1、在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生器，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计、算法移动次数和比较次数的精确统计。如果设计不合理，将使得主调函数的调用代码冗长，可读性变差。因而采用了函数指针数组和统一的接口函数，采用二维数组存储移动次数和比较次数，调用精确的系统函数实现时间的统计。此外还添加了一些列优化，特别是函数封装的方法，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。
2、程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。由于优化中用到很多类的封装和访问控制方面的知识，而这部分知识恰好是大一一年学习的薄弱点。因而以后要多花力气学习C++编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。
3、改进：本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。在实现类的封装的时候为了共享数据采用了友元函数的方式，考虑能否使用其他方式使得类的封装更加完善。