太原理工大学数据结构实验报告.doc

数据结构实验报告课程名称： 数据结构 实验项目： 线性表、树、图、查找、内排序 实验地点： * 专业班级： 物联网* 学号： * 学生姓名： 指导教师： 周杰伦 2014年*月*日实验一 线性表目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机调试并编译执行通过，并观察其结果，然后独立完成后面的实验内容，写出完整的实验报告。编写程序过程中注意养成良好的编程风格与习惯，要求程序结构清晰，程序缩进，适当注释。实验仪器使用的计算机联想：硬件配置cpu-i3等、软件环境win7实验内容问题描述：1设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。输入：插入见的顺序表，插入的数，插入后的顺序表输出：插入前的顺序表，插入的数，插入后的顺序表存储结构：顺序表存储数据算法基本思想：这里采用了顺序表来存储数据，主要就是考虑插入的位置是不是在最后一个，如果不是在最后一个，那么就要移动数据了，算法很简单就不在这里的数据都看成是整型的实验代码#include #include void Insert(int* p,int length,int n) int i,j; int flag=0; if(n=plength-1) plength=n; flag=1; else for(i=length-2;i=0;i-) if(n=pi) for(j=length;j=i+2;j-) pj=pj-1; pi+1=n; flag=1; break； if(flag=0) for(j=length;j=1;j-) pj=pj-1; p0=n； int main() int L10=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;ilength;i+) printf(%4d,Li); 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,Li); printf(n); system(pause); return 0; 实验结果实验心得与体会本次实验是数据结构的第一个实验，虽然已经学过C语言，也用过vc+6.0，但是实验中还是不可避免的遇到许多问题，不过经过自己上网了解和同学与老师的帮助，问题都得到了解决，其中在运行代码后出现了“预编译头文件找不到”的错误，多次运行都出现这种错误，于是上网查询后，才知道是头文件错误，加上“#include”之后程序顺利运行。通过本实验我对线性表有了更深的的认识，弄懂了一些上课时没能理解的知识点，对我以后的学习有很大的帮助。实验二 树目的与要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。实验仪器使用的计算机联想：硬件配置cpu-i3等、软件环境win7实验内容问题描述：1编写递归算法，计算二叉树中叶子结点的数目。输入：按先序序列输入二叉树ABD.EHCF.I.G.输出：二叉树叶子节点数目为4存储结构：采用二叉链表存储算法基本思想：求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。实验代码：#include#includeint count = 0; struct nodechar 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(); elsep=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顶点的路径(ij)。输入：图的顶点个数N，以及以V1、V2、V3、V4为弧尾的所有的弧，并以-1结束。还有你要判断是否连通的两个顶点。输出：若A到B无路径，则输出“不是连通的”,否则输出A到B路径上各顶点。存储结构：图采用邻接矩阵的方式存储。算法的基本思想：采用深度优先搜索的方法，从顶点A开始，依次访问与A邻接的顶点VA1,VA2,.,VAK, 访问遍之后,若没有访问B，则继续访问与VA1邻接的顶点VA11,VA12,.,VA1M，再访问与VA2邻接顶点.，如此下去，直至找到B，最先到达B点的路径，一定是边数最少的路径。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来。程序代码：#include #include #include int n;typedef struct arcNodeint position;struct arcNode *next; ArcNode, *ArcNode_;typedef struct vNodeint 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,vn);scanf(%d,%d, &w, &v);DFS(Chart, w-1);if(Chartv-1.mark)printf(顶点V%d，与顶点V%d之间连通。, w, v);elseprintf(顶点顶点V%d，与顶点V%d之间不连通。, w, v);printf(nn);End(Chart);/构造一个图的过程VNode_ Structure()VNode_ Chart;int i, j, k;ArcNode_ p, q;printf(下面进行构造图的过程，请按照提示输入信息完成构造图的过程！n);printf(n请输入要构造的图的顶点总数.n);scanf(%d, &n);/将用户输入的总的顶点数保存/对输入数据进行判断while(n1)printf(录入的数据有误！请重新输入。n);scanf(%d, &n);Chart = (VNode_)malloc(n*sizeof(VNode);Initialize(Chart);/初始化申请出来的空间printf(请按照下面的提示构造图。nn);for(i=0; iposition = 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;elseCharti.first = NULL;return Chart;void DFS(VNode_ Chart, int t)ArcNode_ q;if(Chartt.mark = 0)Chartt.mark = 1;for(q=Chartt.first; q != NULL; q=q-next)DFS(Chart, q-position);void Initialize(VNode_ Chart)int i;for(i=0; i mark = 0;void End(VNode_ Chart)int i;ArcNode_ p, q;for(i=0;inext;free(q);free(Chart);运行结果实验心得与体会 这次实验让我对图有了更加深厚的了解，实验中依然遇到了许多问题，实验代码明明写对了但是运行不能通过，在网上查询后调整了vc+6.0的相关设置，最后程序顺利运行。实验中，粗心大意的情况已然发生了，例如程序中的“ ”,经常写了前一半而忘写后一半。在以后的实验中我一定要细心认真，不能再出现这种情况。实验四 查找目的与要求通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。实验仪器使用的计算机联想：硬件配置cpu-i3等、软件环境win7实验内容问题描述：1. 试将折半查找的算法改写成递归算法。输入：输入有序表输出：要查找元素的位置存储结构：数组存储算法的基本思想：将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如果xan/2，则我们只要在数组a的右半部继续搜索x。递归调用这个算法。程序代码：#define MAXNUM 20#include #include typedef struct sSTableint aMAXNUM+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(查找成功！nn);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-aST-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.amid)return mid;else if(key ST.amid)i = Binsearch(ST, key, low, mid-1);else i = Binsearch(ST, key, mid+1, high);return i;运行结果：实验心得与体会：本次实验是关于查找的，查找在数据结构中具有重要地位，内容繁多，而且不易理解，在实验中我就遇到了许多问题，例如规定数组的长度如何辨别已经输入完毕等，但是经过上网查阅相关文档最终解决了问题，达到了实验的要求，并将源代码运行成功，由于实验室机器的问题，当实验进行一半时电脑突然死机然后重启，导致写到一半的程序全没了，这也告诉了我们要做好代码的备份，以防出现意外。实验五 内排序目的与要求通过本次实验，掌握线性表的排序方法，并分析时间复杂度。实验仪器使用的计算机联想：硬件配置cpu-i3等、软件