数据结构实验报告.docx

本科实验报告
课程名称: 数据结构B
实验项目:线性结构、树形结构、图结构、查找、排序
实验地点: 逸夫楼202
专业班级: XXXX 学号:
学生姓名: XXX
指导教师: XXX

2012年12月27日
实验项目:线性结构
一、实验目的和要求
本次实****的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现,提高分析和解决问题的能力。要求仔细阅读并理解下列例题,上机通过,并观察其结果,然后独立完成后面的实****题。
二、实验内容和原理
问题描述:设顺序表A中的数据元素递增有序,将x插入到顺序表的适当位置上,使该表仍然有序。
输入:任意一个整数
输出:数据元素地递增有序的顺序表
存储结构:采用链式存储结构
算法基本思想:移动指针,使插入的整数与初始表中的数据元素挨个比较,找到插入位置,将新结点插入到该位置之前。
三、主要仪器设备
惠普ProBook6460b操作系统 Windows 7 旗舰版 32位( DirectX 11 )
处理器 英特尔第二代酷睿 i5-2430M @ 双核
主板 惠普 161D (英特尔 HM65 芯片组)
内存 4 GB ( 三星 DDR3 1333MHz )
运行环境:Microsoft Visual Studio 2010
四、操作方法与实验步骤
#include<>
void Insert(int *p,int length,int n)
{
int i,j;
int flag=0;
if(n>=p[length-1])
{
p[length]=n;
flag=1;
}
else{
for(i=length-2;i>=0;i--){
if(n>=p[i]){
for(j=length;j>=i+2;j--){
p[j]=p[j-1];
}
p[i+1]=n;
flag=1;
break;
}
}
}
if(flag==0){
for(j=length;j>=1;j--){
p[j]=p[j-1];
}
p[0]=n;
}
}
int main(){
int L[10]={10,33,48,88,90};
int length=5;
int i,x;
printf("初始顺序表A:\n");
for(i=0;i<length;i++){
printf("%5d",L[i]);
}
printf("\n请输入要插入的整数:\n");
scanf("%d",&x);
Insert(L,length,x);
printf("插入%d后顺序表为:\n",x);
for(i=0;i<=length;i++){
printf("%5d",L[i]);
}
printf("\n");
}
五、实验数据记录和处理
六、实验结果与分析
优点:简单易懂;缺点:在比较的时候,要移动指针,很容易出现错误。
时间复杂度为O(n)。
七、讨论、心得
除此之外,还可以建立一个新的顺序表,将插入的元素与初始表中的元素逐个比较,然后把比较后的元素放入依次新表中。
实验项目:树形结构
一、实验目的和要求
熟悉树的各种表示方法和各种遍历方式,掌握有关算法的实现,了解树在计算机科学及其它工程技术中的应用。
二、实验内容和原理
问题描述:编写递归算法,计算二叉树中叶子结点的数目。
输入:输入新建树ABCD…EF..G....KL…或.
输出:若不为空,则输出为“二叉树中叶子结点的数目为5”。若为空,则为“这是一个空树”。
存储结构:二叉链表存储
算法分析:用递归方法建立和遍历二叉树。首先建立二叉树的根结点,然后建立其左右子树,直到空子树为止。采用递归方法,查找结点,是结点则返回1,然后递归将左子树的叶子加上右子树的叶子个数。
三、主要仪器设备
惠普ProBook6460b操作系统 Windows 7 旗舰版 32位( DirectX 11 )
处理器 英特尔第二代酷睿 i5-2430M @ 双核
主板 惠普 161D (英特尔 HM65 芯片组)
内存 4 GB ( 三星 DDR3 1333MH)
运行环境:Microsoft Visual Studio 2010
四、操作方法与实验步骤
#include<>
struct BiTree{
char data;
struct BiTree *lchild;
struct BiTree *rchild;
};
struct BiTree* CreatBiTree(){