《太原理工大学数据结构实验报告》由会员分享，可在线阅读，更多相关《太原理工大学数据结构实验报告（18页珍藏版）》请在金锄头文库上搜索。
1、71-5-1I窈T.UYUAN UNIVERSITY OF TECHNOLOGY数据结构实验报告课程名称：数据结构实验项目：线性表、树、图、查找、内排序实验地点：k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* k1* *yw *yw *yw *yw *yw *yw *yw *yw *yw *yw *yw *yw *yw *yw *yw *yw *yw *yw *yw专业班级：物联网* 学号： *学生姓名：指导教师：2014 年*月*日实验一 线性表目的与要求本次实习的主要目的是为了使学生熟练
2、掌握线性表的基本操作在 顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力 要求仔细阅读并理解下列例题，上机调试并编译执行通过，并观察其 结果，然后独立完成后面的实验内容，写出完整的实验报告。编写程 序过程中注意养成良好的编程风格与习惯，要求程序结构清晰，程序 缩进，适当注释。实验仪器使用的计算机联想：硬件配置 cpu-i3 等、软件环境 win7实验内容问题描述：1.设顺序表A中的数据元素递增有序，试写一程序，将x插入 到顺序表的适当位置上，使该表仍然有序。输入：插入见的顺序表，插入的数，插入后的顺序表输出：插入前的顺序表，插入的数，插入后的顺序表存储结构：顺序表存储数据 算法基本
3、思想：这里采用了顺序表来存储数据，主要就是考虑插 入的位置是不是在最后一个，如果不是在最后一个，那么就要移动数据了，算法很简单就不在这里的数据都看成是整型的实验代码#include#includevoid 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
4、;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+)pr
5、intf(%4d,Li);printf(n); system(pause); return 0;实验结果 T112Z ADebugll 12 2 2. exepha iii gijOLri de shun xu biao wc i :25811141726wing shn pu yao cJia ru de e片eng sim： Pp haru?ha udes hun xuhiaowe i ：257811141720青按任意谨继渎实验心得与体会本次实验是数据结构的第一个实验，虽然已经学过 C 语言，也 用过vc+6.0,但是实验中还是不可避免的遇到许多问题，不过经过 自己上网了解和同学与老师的
6、帮助，问题都得到了解决，其中在运行 代码后出现了“预编译头文件找不到”的错误，多次运行都出现这种 错误，于是上网查询后，才知道是头文件错误，加上“#include” 之后程序顺利运行。通过本实验我对线性表有了更深的的认识，弄懂 了一些上课时没能理解的知识点，对我以后的学习有很大的帮助。实验二 树目的与要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现， 了解树在计算机科学及其它工程技术中的应用。实验仪器使用的计算机联想：硬件配置 cpu-i3 等、软件环境 win7实验内容问题描述：1编写递归算法，计算二叉树中叶子结点的数目。输入：按先序序列输入二叉树ABD.EHCF.I.G.输出：二
7、叉树叶子节点数目为 4存储结构：采用二叉链表存储算法基本思想：求二叉树中叶子结点个数，即求二叉树的所有 结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍 历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若 是则将计数器累加。实验代码：#include #include int 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=(N
8、ODE *)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
9、printf(遍历后的结果:n ); run(T);printf(n总共有叶子节点数d, count );printf(n);运行结果/-请输入一个树：fiBD.-EH.CF.I.G-.RBD.EH-.CF.I -.G.恒历后的结果：DHEBIFGCA肚共有叶子节点数4.Piess any k巳y to co nt inueMM卜IJ实验心得与体会本次实验是关于树的相关练习，树这一节在本书中算是一个重点 内容，不过它并不是一个难点，相比其他单元的内容来说已经算是简 单的了，所以本次实验相比前几次实验容易同时也顺利多了。源代码 一次就运行成功。通过本次实验我对树有了更深的了解，对我以后的 学习有
10、很大的帮助。实验三 图目的与要求熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学 及其他工程技术中的应用。实验仪器使用的计算机联想：硬件配置 cpu-i3 等、软件环境 win7实验内容问题描述： 1试基于图的深度优先搜索策略编写一程序，判别以邻接表方 式存储的有向图中是否存在有顶点Vi到Vj顶点的路径(iHj)。输入：图的顶点个数N,以及以VI、V2、V3、V4为弧尾的所有 的弧，并以-1 结束。还有你要判断是否连通的两个顶点。输出：若 A 到 B 无路径,则输出“不是连通的”,否则输出 A 到 B 路径上各顶点。存储结构：图采用邻接矩阵的方式存储。算法的基本思想：采用深度优先搜索的
11、方法,从顶点 A 开始, 依次访问与 A 邻接的顶点 V ,V ,.,V , 访问遍之后,若没有访 A1 A2 AK问B,则继续访问与V邻接的顶点V ,V，.，V，再访问与A1 A11 A12 A1MVA2邻接顶点.，如此下去，直至找到B最先到达B点的路径，一定是边数最少的路径。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来。程序代码：#include #include #include int n;typedef struct arcNodeint position; struct arcNode *next;ArcNode, *ArcNode_;type
12、def struct vNodeint mark; /在程序中用来标识是否被访问过ArcNode * firs存储连接到该结点的第一个弧信息的地址 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(
13、%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 = (Ar
