数据结构由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“基于数据结构”。
实验：线性表的基本操作
【实验目的】
学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。
【实验内容】
1.顺序表的实践
1)建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立的基本操作。
2)在sqlist []={1，2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。
3)在sqlist []={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9，实现顺序表的删除的基本操作。2.单链表的实践
3.1)建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链表建立的基本操作。
2)将该单链表的所有元素显示出来。
3)在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插入的基本操作。
4)在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2）删除一个结点，实现单链表删除的基本操作。5)实现单链表的求表长操作。
【实验步骤】
1.打开VC++。
2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。
3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
【实验心得】
线性是我们学习数据结构中，碰到的第一个数据结构。学习线性表的重点掌握顺序表和单链表的各种算法和时间性能分析。线性表右两种存储方式即顺序存储结构和链式存储结构。通过学习我知道了对线性表进行建立、插入、删除，同时单链表也是进行建立、插入、删除。而对于顺序表的插入删除运算，其平均时间复杂度均为0（n）.通过这次的学习，掌握的太熟练，主要是课本上的知识点没有彻底的理解，回去我会多看书，理解重要的概念。总之，这次实验我找到了自己的不足之处，以后会努力的。
实验二：栈的表示与实现及栈的应用
【实验目的】
（1）掌握栈的顺序存储结构及其基本操作的实现。（2）掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。（3）掌握用递归算法来解决一些问题。【实验内容】
1.编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。
2.编写递归程序，实现N！的求解。3.编写递归程序，实现以下函数的求解。
n,n0,1Fib(n) Fib(n1)Fib(n2),n1
4.编写程序，实现Hanoi塔问题。【实验步骤】 1.打开VC++。
2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。
3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
【实验心得】
通过这次的学习我掌握了栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；总的来说，栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（botton）；栈又称为后进先出（Last In First Out）的线性表,简称LIFO结构，因为它的修改是按后进先出的原则进行的。
加上这个实验，我已经学了线性表（顺序表，单链表）和栈，知道它们都是线性表，而且对以后的学习有很大的作用，可以说这是学习以后知识的总要基础。
实验三：二叉树的建立及遍历
【实验目的】
（1）掌握利用先序序列建立二叉树的二叉链表的过程。（2）掌握二叉树的先序、中序和后序遍历算法。【实验内容】
1.编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc###de###，则建立如下图所示的二叉树。
并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开VC++。
2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。
3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
【实验心得】
这次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历，在这次实验中我按先序方式建立二叉树的，而遍历方式则相对要多一些，有递归的先序、中序、后序遍历，和非递归的先序、中序、后序遍历，此外还有层次遍历.二叉树高度和叶子个数的计算和遍历相差不大，只是加些判断条件，总体来说，本次试验不太好做，期间出现了很多逻辑错误，变量初始化的问题等，不过经过仔细排查最后都一一解决了。
实验四：查找与排序
【实验目的】
（1）掌握折半查找算法的实现。（2）掌握冒泡排序算法的实现。【实验内容】
1.编写折半查找程序，对以下数据查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.编写冒泡排序程序，对以下数据进行排序。49，38，65，97，76，13，27，49 【实验步骤】 1.打开VC++。
2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。
3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
（1）查找算法的代码如下所示： #include “stdio.h” #include “malloc.h” #define OVERFLOW-1 #define OK 1 #define MAXNUM 100 #define N 10 typedef int Elemtype;typedef int Status;typedef struct {
Elemtype *elem;
int length;}SSTable;Status InitList(SSTable &ST){ int i,n;
ST.elem =
(Elemtype*)
malloc(Elemtype));
if(!ST.elem)return(OVERFLOW);
printf(“输入元素个数和各元素的值:”);
scanf(“%dn”,&n);
for(i=1;i
(MAXNUM*sizeof
scanf(“%d”,&ST.elem[i]);}
ST.length = n;
return OK;} int Seq_Search(SSTable ST,Elemtype key){
int i;
ST.elem[0]=key;
for(i=ST.length;ST.elem[i]!=key;--i);
return i;} int BinarySearch(SSTable ST,Elemtype key){
int mid,low,high,i=1;
low=1;
high=ST.length;
while(low
{
mid=(low+high)/2;
if(ST.elem[mid]==key)
return mid;
else if(key
high=mid-1;
else
}
return 0;} void main(){ SSTable ST;InitList(ST);
Elemtype key;int n;printf(“ key= ”);
scanf(“%d”,&key);
printf(“nn”);
/*printf(“After SeqSearch:: ”);
n=Seq_Search(ST,key);
printf(“position is in %d nn”,n);*/
printf(“After Binary Search::”);
n=BinarySearch(ST,key);
low=mid+1;if(n)printf(“position is in %d nn”,n);else
} 实验结果如下所示：
（2）排序算法的代码如下所示： #include “stdio.h” #include “malloc.h” #define OVERFLOW-1 #define OK 1 #define MAXNUM 100 #define N 10 typedef int Elemtype;typedef int Status;typedef struct {
Elemtype *elem;
int length;}SSTable;Status InitList(SSTable &ST)printf(“not in nn”);{ int i,n;
ST.elem(Elemtype));
if(!ST.elem)return(OVERFLOW);
printf(“输入元素个数和各元素的值:”);
scanf(“%dn”,&n);
for(i=1;i
scanf(“%d”,&ST.elem[i]);}
ST.length = n;
return OK;} void Sort(SSTable ST){
int i,j,t;
for(i=1;i
for(j=i+1;j
if(ST.elem[i]>ST.elem[j]){ t=ST.elem[i];=
(Elemtype*)
malloc
(MAXNUM*sizeof
}
} ST.elem[i]=ST.elem[j];ST.elem[j]=t;void display(SSTable ST){ int i;
for(i=1;i
printf(“%d
”,ST.elem[i]);}
} void main(){
SSTable ST;InitList(ST);int n;printf(“before sort::n”);display(ST);Sort(ST);printf(“nafter sort::n”);display(ST);} 实验结果如下所示：
【实验心得】
通过这次实验,我明白了程序里的折半查找和冒泡查找.其实排序可以有很多种，但是其目的应该都是为了能够在海量的数据里迅速查找到你要的数据信息，折半查找是种比较快的方式，但前提是要是有 序的排序才可以。对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。算法中需要用到三个变量，low表示区域下界，high表示上界，中间位置mid=(low+high)/2.而冒泡查找则是从小到大的排序.
