理工大学数据结构实验报告Word文件下载.docx

1、stdio.h #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;=1; pj=pj-1; p0=n； int main（） int L10=2,5,8,11,14,17,20; int length=7; int

2、 i,x; printf（cha ru qian de shun xu biao wei ：n）; for（i=0;ilength;i+） printf（%4d,Li）; nqing shu ru yao cha ru de zheng shu： scanf（%d,&x）; Insert（L,length,x）;charu%dhoudeshunxubiaowei：,x）;=length; system（pause return 0;实验结果实验心得与体会本次实验是数据结构的第一个实验，虽然已经学过C语言，也用过vc+6.0，但是实验中还是不可避免的遇到许多问题，不过经过自己上网了解和同学与老师

3、的帮助，问题都得到了解决，其中在运行代码后出现了“预编译头文件找不到”的错误，多次运行都出现这种错误，于是上网查询后，才知道是头文件错误，加上“#includeint count = 0; struct node char info; struct node *llink,*rlink; ;typedef struct node NODE;NODE *creat（） char x;NODE *p;%c if（x!=.） p=（NODE *）malloc（sizeof（NODE）; p-info=x;llink=creat（）;rlink=creat（）; p=NULL; return p;vo

4、id run（NODE *t） if（t） run（t-llink）;rlink）;,t-info）; if（ （t-llink） = NULL） & （t-rlink） = NULL） count +;void main（） NODE *T;请输入一个树: T=creat（）; if（!T）这是一个空二叉树 else printf（遍历后的结果:n run（T）;n总共有叶子节点数%d, count ）;运行结果 本次实验是关于树的相关练习，树这一节在本书中算是一个重点内容，不过它并不是一个难点，相比其他单元的内容来说已经算是简单的了，所以本次实验相比前几次实验容易同时也顺利多了。源代码一次

5、就运行成功。通过本次实验我对树有了更深的了解，对我以后的学习有很大的帮助。实验三 图熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。1试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径（ij）。图的顶点个数N，以及以V1、V2、V3、V4为弧尾的所有的弧，并以-1结束。还有你要判断是否连通的两个顶点。若A到B无路径，则输出“不是连通的”,否则输出A到B路径上各顶点。图采用邻接矩阵的方式存储。算法的基本思想：采用深度优先搜索的方法，从顶点A开始，依次访问与A邻接的顶点VA1,VA2,.,VAK, 访问遍之后,若没

6、有访问B，则继续访问与VA1邻接的顶点VA11,VA12,.,VA1M，再访问与VA2邻接顶点.，如此下去，直至找到B，最先到达B点的路径，一定是边数最少的路径。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来。程序代码：#include int n;typedef struct arcNode int position; struct arcNode *next;ArcNode, *ArcNode_;typedef struct vNode int mark; /在程序中用来标识是否被访问过 ArcNode *first;/存储连接到该结点的第一个弧信息的地

7、址VNode, *VNode_;/函数声明部分VNode_ Structure（）;/构造一个图void DFS（VNode_ Chart, int t）; void Initialize（VNode_ Chart）;void End（VNode_ Chart）; int i=0; int count=0; int w, v; VNode_ Chart = Structure（）;/创建图请输入要查询的顶点w,vn%d,%d, &w, &v）; DFS（Chart, w-1）; if（Chartv-1.mark） 顶点V%d，与顶点V%d之间连通。, w, v）;顶点顶点V%d，与顶点V%d之

8、间不连通。nn End（Chart）;/构造一个图的过程VNode_ Structure（） VNode_ Chart; int i, j, k; ArcNode_ p, q;下面进行构造图的过程，请按照提示输入信息完成构造图的过程！n请输入要构造的图的顶点总数.nn）;/将用户输入的总的顶点数保存 /对输入数据进行判断 while（n1）录入的数据有误！请重新输入。 scanf（ Chart = （VNode_）malloc（n*sizeof（VNode）; Initialize（Chart）;/初始化申请出来的空间请按照下面的提示构造图。 iposition = k-1; （Chart+i

9、）-first = q; p = q; scanf（ while（k ! q = （ArcNode_）malloc（sizeof（ArcNode）; q- p-next = q; p = q; scanf（ p-next = NULL; else Charti.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）

10、;void Initialize（VNode_ Chart） int i; i mark = 0;void End（VNode_ Chart）i+） p = Charti.first; while（p!=NULL） q = p; p = p-next; free（q）; free（Chart）; 这次实验让我对图有了更加深厚的了解，实验中依然遇到了许多问题，实验代码明明写对了但是运行不能通过，在网上查询后调整了vc+6.0的相关设置，最后程序顺利运行。实验中，粗心大意的情况已然发生了，例如程序中的“ ”,经常写了前一半而忘写后一半。在以后的实验中我一定要细心认真，不能再出现这种情况。实验四 查

11、找通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。1. 试将折半查找的算法改写成递归算法。输入有序表要查找元素的位置数组存储将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如果xan/2，则我们只要在数组a的右半部继续搜索x。递归调用这个算法。#define MAXNUM 20typedef struct sSTable int aMAXNUM+1; int lenth;SSTable, *SSTable_;void Structure（SSTable_ ST）;int Binsearch（SSTable ST, int key,

12、 int low, int high）; int t; SSTable ST; Structure（&ST）;请输入要查找的数t）; if（Binsearch（ST, t, 1, ST.lenth）查找成功！void Structure（SSTable_ ST）以下为构造一个数组的过程，用0作为结束输入的标识。 n由于程序限定输入数组长度不能超过%d个并且数组元素从第1个开始。, MAXNUM）; ST-lenth = 0; while（t ! ST-aST-lenth+1 = t; + ST-lenth;int Binsearch（SSTable ST, int key, int low,

13、int high） int mid; 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;运行结果：实验心得与体会：本次实验是关于查找的，查找在数据结构中具有重要地位，内容繁多，而且不易理解，在实验中我就遇到了许多问题，例如规定数组的长度如何辨别已经输入完毕等，但是经过上网查阅相关文档最终解决了问题，达到

14、了实验的要求，并将源代码运行成功，由于实验室机器的问题，当实验进行一半时电脑突然死机然后重启，导致写到一半的程序全没了，这也告诉了我们要做好代码的备份，以防出现意外。实验五 内排序通过本次实验，掌握线性表的排序方法，并分析时间复杂度。1.对N个关键字取整数的记录进行整序，以使所有关键字为非负数的记录排在关键字为负数的记录之前，要求使用最少的附加空间，且算法的时间复杂度为O（N）。输入 ：一组数据。非负数排在负数之前。顺序存储。 由于问题仅要求非负数排在负数之前，所以提取非负数插在前面即可。#define MAX 100 int aMAX; int i, j, n;请输入记录的总个数。请输入各记录（仅输入关键字）n for（i=1;= n;ai）; a0 = a1; i=1; j=n; while（ij） while（ij&aj=0） +i; aj = ai; ai = a0;=n;, ai）; 本次实验是数据结构的最后一个实验，多次的实验已经让我积累了许多编程的经验与数据结构的思想，这对我以后的学习有很大的帮助，培养数据结构思想也正是我们这门课程的目的和要求，规范化的编程对于以后的工作更是有巨大的用处。总结前几次实验的失败和教训本次实验较为顺利，通过编程是我对内部排序有了更深的理解和认识。