数据结构实验报告
课程名称： 数据结构
实验项目： 线性表、树、图、查找、内排序
实验地点： ***********************
专业班级： 物联网**** 学号： *********
学生姓名：
指导教师： 周杰伦
20##年*月*日
实验一 线性表
目的与要求
本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机调试并编译执行通过，并观察其结果，然后独立完成后面的实验内容，写出完整的实验报告。编写程序过程中注意养成良好的编程风格与习惯，要求程序结构清晰，程序缩进，适当注释。
实验仪器
使用的计算机联想：硬件配置cpu-i3等、软件环境win7
实验内容
问题描述：
1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。
输入：插入见的顺序表，插入的数，插入后的顺序表
输出：插入前的顺序表，插入的数，插入后的顺序表
存储结构：顺序表存储数据
算法基本思想：这里采用了顺序表来存储数据，主要就是考虑插入的位置是不是在最后一个，如果不是在最后一个，那么就要移动数据了，算法很简单就不在这里的数据都看成是整型的
实验代码
#include<stdio.h>
#include<stdlib.h>
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]={2,5,8,11,14,17,20};
int length=7;
int i,x;
printf("cha ru qian de shun xu biao wei ：\n");
for(i=0;i<length;i++){
printf("%4d",L[i]); }
printf("\nqing shu ru yao cha ru de zheng shu：\n");
scanf("%d",&x);
Insert(L,length,x);
printf("charu%dhoudeshunxubiaowei：\n",x);
for(i=0;i<=length;i++){
printf("%4d",L[i]);
}
printf("\n"); system("pause");
return 0;
}
实验结果
实验心得与体会
本次实验是数据结构的第一个实验，虽然已经学过C语言，也用过vc++6.0，但是实验中还是不可避免的遇到许多问题，不过经过自己上网了解和同学与老师的帮助，问题都得到了解决，其中在运行代码后出现了“预编译头文件找不到”的错误，多次运行都出现这种错误，于是上网查询后，才知道是头文件错误，加上“#include<stdio.h>”之后程序顺利运行。通过本实验我对线性表有了更深的的认识，弄懂了一些上课时没能理解的知识点，对我以后的学习有很大的帮助。
实验二 树
目的与要求
熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。
实验仪器
使用的计算机联想：硬件配置cpu-i3等、软件环境win7
实验内容
问题描述：
1．编写递归算法，计算二叉树中叶子结点的数目。
输入：按先序序列输入二叉树ABD..EH…CF.I..G..
输出：二叉树叶子节点数目为4
存储结构：采用二叉链表存储
算法基本思想：求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。
实验代码：
#include<stdio.h>
#include<malloc.h>
int count = 0;
struct node{
char info;
struct node *llink,*rlink;
};
typedef struct node NODE;
NODE *creat(){
char x;NODE *p;
scanf("%c",&x);
printf("%c",x);
if(x!='.'){
p=(NODE *)malloc(sizeof(NODE));
p->info=x;
p->llink=creat();
p->rlink=creat();
}
else{
p=NULL;
return p;
}
void run(NODE *t){
if(t){
run(t->llink);
run(t->rlink);
printf("%c",t->info);
if( ((t->llink) == NULL) && ((t->rlink) == NULL))
count ++;
}
}
void main()
{
NODE *T;
printf("请输入一个树:\n");
T=creat();
printf("\n");
if(!T)
printf("这是一个空二叉树");
else
{ printf("遍历后的结果:\n ");
run(T);
}
printf("\n总共有叶子节点数%d", count );
printf("\n");
}
运行结果
实验心得与体会
本次实验是关于树的相关练习，树这一节在本书中算是一个重点内容，不过它并不是一个难点，相比其他单元的内容来说已经算是简单的了，所以本次实验相比前几次实验容易同时也顺利多了。源代码一次就运行成功。通过本次实验我对树有了更深的了解，对我以后的学习有很大的帮助。
实验三 图
目的与要求
熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。
实验仪器
使用的计算机联想：硬件配置cpu-i3等、软件环境win7
实验内容
问题描述：
1．试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径(i≠j)。
输入：图的顶点个数N，以及以V1、V2、V3、V4为弧尾的所有的弧，并以-1结束。还有你要判断是否连通的两个顶点。
输出：若A到B无路径，则输出“不是连通的”,否则输出A到B路径上各顶点。
存储结构：图采用邻接矩阵的方式存储。
算法的基本思想：采用深度优先搜索的方法，从顶点A开始，依次访问与A邻接的顶点VA1,VA2,...,VAK, 访问遍之后,若没有访问B，则继续访问与VA1邻接的顶点VA11,VA12,...,VA1M，再访问与VA2邻接顶点...，如此下去，直至找到B，最先到达B点的路径，一定是边数最少的路径。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来。
程序代码：
#include <stdio.h>
#include <malloc.h>
#include <Windows.h>
int n;
typedef struct arcNode
{
int position;
struct arcNode *next;
}ArcNode, *ArcNode_;
typedef struct vNode
{
int mark; //在程序中用来标识是否被访问过
ArcNode *first;//存储连接到该结点的第一个弧信息的地址
}VNode, *VNode_;
//函数声明部分
VNode_ Structure();//构造一个图
void DFS(VNode_ Chart, int t);
void Initialize(VNode_ Chart);
void End(VNode_ Chart);
void main()
{
int i=0;
int count=0;
int w, v;
VNode_ Chart = Structure();//创建图
printf("请输入要查询的顶点w,v\n");
scanf("%d,%d", &w, &v);
DFS(Chart, w-1);
if(Chart[v-1].mark)
{
printf("顶点V%d，与顶点V%d之间连通。", w, v);
}
else
{
printf("顶点顶点V%d，与顶点V%d之间不连通。", w, v);
}
printf("\n\n");
End(Chart);
}
//构造一个图的过程
VNode_ Structure()
{
VNode_ Chart;
int i, j, k;
ArcNode_ p, q;
printf("下面进行构造图的过程，请按照提示输入信息完成构造图的过程！\n");
printf("\n请输入要构造的图的顶点总数.\n");
scanf("%d", &n);//将用户输入的总的顶点数保存
//对输入数据进行判断
while(n<1)
{
printf("录入的数据有误！请重新输入。\n");
scanf("%d", &n);
}
Chart = (VNode_)malloc(n*sizeof(VNode));
Initialize(Chart);//初始化申请出来的空间
printf("请按照下面的提示构造图。\n\n");
for(i=0; i<n; ++i)
{
printf("请输入指向'V%d'顶点的所有顶点，结束请输入 0 \n", i+1);
scanf("%d", &k);
if(k != 0)
{
q = (ArcNode_)malloc(sizeof(ArcNode));
q->position = k-1;
(Chart+i)->first = q;
p = q;
scanf("%d", &k);
while(k != 0)
{
q = (ArcNode_)malloc(sizeof(ArcNode));
q->position = k-1;
p->next = q;
p = q;
scanf("%d", &k);
}
p->next = NULL;
}
else
{
Chart[i].first = NULL;
}
}
return Chart;
}
void DFS(VNode_ Chart, int t)
{
ArcNode_ q;
if(Chart[t].mark == 0)
{
Chart[t].mark = 1;
for(q=Chart[t].first; q != NULL; q=q->next)
{
DFS(Chart, q->position);
}
}
}
void Initialize(VNode_ Chart)
{
int i;
for(i=0; i < n; i++)
{
(Chart+i)->mark = 0;
}
}
void End(VNode_ Chart)
{
int i;
ArcNode_ p, q;
for(i=0;i<n;i++)
{
p = Chart[i].first;
while(p!=NULL)
{
q = p;
p = p->next;
free(q);
}
}
free(Chart);
}
运行结果
实验心得与体会
这次实验让我对图有了更加深厚的了解，实验中依然遇到了许多问题，实验代码明明写对了但是运行不能通过，在网上查询后调整了vc++6.0的相关设置，最后程序顺利运行。实验中，粗心大意的情况已然发生了，例如程序中的“{ }”,经常写了前一半而忘写后一半。在以后的实验中我一定要细心认真，不能再出现这种情况。
实验四 查找
目的与要求
通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。
实验仪器
使用的计算机联想：硬件配置cpu-i3等、软件环境win7
实验内容
问题描述：
1. 试将折半查找的算法改写成递归算法。
输入：输入有序表
输出：要查找元素的位置
存储结构：数组存储
算法的基本思想：将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。递归调用这个算法。
程序代码：
#define MAXNUM 20
#include <stdio.h>
#include <Windows.h>
typedef struct sSTable
{
int a[MAXNUM+1];
int lenth;
}SSTable, *SSTable_;
void Structure(SSTable_ ST);
int Binsearch(SSTable ST, int key, int low, int high);
void main()
{
int t;
SSTable ST;
Structure(&ST);
printf("请输入要查找的数");
scanf("%d", &t);
if(Binsearch(ST, t, 1, ST.lenth))
printf("查找成功！！\n\n");
system("pause");
}
void Structure(SSTable_ ST)
{
printf("以下为构造一个数组的过程，用0作为结束输入的标识。\
\n由于程序限定输入数组长度不能超过%d个并且数组元素从第1个开始。\n", MAXNUM);
int t;
ST->lenth = 0;
scanf("%d", &t);
while(t != 0)
{
ST->a[ST->lenth+1] = t;
++ ST->lenth;
scanf("%d", &t);
}
}
int Binsearch(SSTable ST, int key, int low, int high)
{
int mid;
int i=0;
mid = (low+high)/2;
if(low <= high)
{
if(key == ST.a[mid]) return mid;
else if(key < ST.a[mid]) i = Binsearch(ST, key, low, mid-1);
else i = Binsearch(ST, key, mid+1, high);
}
return i;
}
运行结果：
实验心得与体会：
本次实验是关于查找的，查找在数据结构中具有重要地位，内容繁多，而且不易理解，在实验中我就遇到了许多问题，例如规定数组的长度如何辨别已经输入完毕等，但是经过上网查阅相关文档最终解决了问题，达到了实验的要求，并将源代码运行成功，由于实验室机器的问题，当实验进行一半时电脑突然死机然后重启，导致写到一半的程序全没了，这也告诉了我们要做好代码的备份，以防出现意外。
实验五 内排序
目的与要求
通过本次实验，掌握线性表的排序方法，并分析时间复杂度。
实验仪器
使用的计算机联想：硬件配置cpu-i3等、软件环境win7
实验内容
问题描述：
1.对N个关键字取整数的记录进行整序，以使所有关键字为非负数的记录排在关键字为负数的记录之前，要求使用最少的附加空间，且算法的时间复杂度为O(N)。
输入 ：一组数据。
输出：非负数排在负数之前。
存储结构：顺序存储。
算法的基本思想：
由于问题仅要求非负数排在负数之前，所以提取非负数插在前面即可。
程序代码：
#include <stdio.h>
#define MAX 100
void main()
{
int a[MAX];
int i, j, n;
printf("请输入记录的总个数。\n");
scanf("%d", &n);
printf("请输入各记录（仅输入关键字）\n");
for(i=1; i <= n; i++)
{
scanf("%d", &a[i]);
}
a[0] = a[1];
i=1; j=n;
while(i<j)
{
while(i<j&&a[j]<=0) --j;
a[i] = a[j];
while(i<j&&a[i]>=0) ++i;
a[j] = a[i];
}
a[i] = a[0];
for(i=1; i<=n; i++)
{
printf("%4d", a[i]);
}
printf("\n");
}
运行结果：
实验心得与体会
本次实验是数据结构的最后一个实验，多次的实验已经让我积累了许多编程的经验与数据结构的思想，这对我以后的学习有很大的帮助，培养数据结构思想也正是我们这门课程的目的和要求，规范化的编程对于以后的工作更是有巨大的用处。总结前几次实验的失败和教训本次实验较为顺利，通过编程是我对内部排序有了更深的理解和认识。