完整word版 数据结构实验报告201111291

1、数据结构实验报告(1)班号序号姓名成绩一、实验目的1. 复习if语句、循环语句、数组及子函数；2. 了解算法的评价标准，并将该准则应用于算法的设计中;3. 初步掌握时间复杂度的分析方法。二、实验内容1.输入10个数据，存于一维数组a10中，并求和。mai n() int i, sum=0, a11;11printf (n input 10 number:n);for (i=1;iv=10;i+)scan f(%d,&ai);prin tf(n);for (i=1;i=10;i+)sum=sum+ai;j1!111 prin tf(sum=%dn,sum);11111getch();i111i1

2、1i1i1111(1) 若输入10000个数据，上述程序应该如何修改，将修改后的程序写在右上方;(2) 思考修改后的程序在时间和空间上的开销是多少？2.阅读并运行下列程序mai n()(1)该程序的功能是什么？ int i, j, a21;for (i=1;i=20;i+)1i -11ai=2*i-1;(2)该程序的输出结果是：i=1;j=1;while (i=20)J aj=ai; j=j+1; i=i+2;!( 3)该程序的时间复杂度是：1for (i=1;i=10;i+)prin tf(%5dn,ai);1ij getch();J 1111 I13阅读并运行下列程序。void selec

3、tsort (int s , i nt n)mai n()/*选择排序*/*主函数*/int i,j,k;int a21, n=20,i,j;for(i=1;i=n-1;i+)/*从键盘输入20个整数*/ k=i ；for(i=1;i=n ;i+)for(j=i+1;j=n ;j+)scanf( %d”,&ai);if(aj ak)/*输出20个整数*/k=j;for(i=1;i=n ;i+)/*k:记下目前找到的最小值的所在的位置prin tf(%d, ai);既：保持ak为最小*/prin tf(n);if(k!=i)selectsort(a, n); /*排序 */a0=ai ； ai=

4、ak ； ak=a0 ；/*输排序后的20个整数*/* 交换 ai和 ak*/for(i=1;i=n ;i+)prin tf(%4d, ai);prin tf(n);getch();（1 ）该程序的输出结果是：（3）该程序的时间复杂度是：4.阅读并运行程序4-1和4-2,分析为何程序4-2较程序4-1高效?1mai n()mai n()/* 4-1 求 s=1!+2!+ +20! */* 4-2 求 s=1!+2!+ +20! */long s=0, t;long s=0, t=1;int i,j;int i,i;for (i=1;i=20;i+)for (i=1;i=20;i+)t=1;fo

5、r (i=1;i=i;i+)t=t*i;t=t*j;s=s+t;s=s+t;prin tf(1!+2!+ +20!=%ldnlLprin tf(1!+2!+ +20!=%ldn,s);getchOgetch();（2）该程序的时间复杂度是：（1）该程序的时间复杂度是：11111.I15.程序设计从键盘输入3个整数a,b,c,按从小到大的顺序将它们输出。（程序写在反面）#数据结构实验报告(2)班号序号姓名成绩一、实验目的1. 掌握线性表逻辑结构；2. 掌握线性表的顺序存储结构(一维数组表示)3. 算法设计，并用 C语言实现。二、实验内容1. 读下列算法#defi ne MAXSIZE 100 m

6、ai n()int a100=0,1,3,5,7,9,11,13,15,17,19, n=10,i=5, x=20,j;for(j=1;j=i;j-) aj+1=aj;/* 从 an-ai, ai=x;/*在线性表的第n+;/*表长加1 */for (j=1;j=n;j+)printf ( “ %5d” ,aj);getchO;/*输出线性表中的n个整数*/元素后移*/i处插入X*/*输出插入x后的线性表*/a的第i处的后面插入新元素改写插入算法，在线性表算法分析，元素的移动次数与哪些因素有关?X。(3) 思考题：当当n个元素按无序排列时，在哪里插入新元素X最好，将插入算法重写一遍。n个元素按

7、有序(例如递增次序)排列时，在哪里插入新元素e最好呢，重写插入算法。2 .请写一程序完成顺序表的逆置。参考算法：voidalg2(i nt a,i nt n)int i,xfor (i=1;i=n/2;i+) x=ai; ai=an-i+1;an-i+1=x; /* 从 an-i+1 与 a,互换 */(1 )用C语言编程实现；(2)分析该程序的时间复杂度。33.将顺序表（ai, a2, ak, ak+i, an）改变成（ak+i,（ 1 ）运行程序，测试数据：n=20, k=8 。（2）分析时间度T（n）,用0（大欧）表示。an , a1, a2,ak )。参考程序：main()int ai

8、00=0,i,3,5,7,9,ii,i3,i5,i7,i9,2i,23,25,27,29,3i,33,35,37,39,n=20,k=8, i, j,x ; for(j=i;jn) printf( 参数错);else for(i=i;i=k;i+) x=ai; for(j=2;j=n;j+)aj -=aj;an=x;for(j=1;j=n;j+)printf (%3d ”,aj);/* 以(ak+i,getch();an , a1, a2,ak ）的顺序输出 */1)分析该程序的时间复杂度 。 重写该程序，要求在线性时间内完成。4.已知线性表存于a100中的前n个分量中，写一程序删除表中所有值

9、为0的元素（将非 0 元素移到前面来） ，各元素间的相对位置不变。存储结构定义及赋初值：int ai00=-32768,2,4,5,6,7,8,0,9,8,0,0,0,7,8,0,0,3,2,0,0,0,0,4,5,6,7,0,5,6,7;参考算法：alg4(int a, int n) int i,k=0 for(i=i;i=n;i+) if(ai=0) k+;else ai-k=ai; /*n=n-k;1)2)将为 0 元素删除 */用 C 语言编程实现； 输出删除表中所有值为 分析时间复杂性（用大0 的元素之后的线性表；O表示），并回答该算法是高效的吗?程序及运行结果写在反面）3)5数据结

10、构实验报告(3)班号序号姓名成绩一、实验目的1了解线性表的非顺序存储结构(链表)2. 基于链表进行算法设计。二、实验内容1阅读下列程序#defi ne n 8i#defi ne NULL 0struct node|1卜-1 int data;|i1!1istruct node *n ext;111111 ;i1i1!1i!11- - - - - - - - -1!111mai n()struct node *head, * p, *rear;int i,x;1L_-.head= (struct no de*)malloc(sizeof(struct no de);rear=head;for (

11、i=1;idata=x;rear- n ext=p;rear= p;1rear-n ext=NULL;for( p=head-n ext; p!=NULL; p=p-n ext)1printf ( =%d ”, p-data);|1getch();1 ! - -1运行结杲：1(1) 在右边加上适当的注释。(2) 从键盘输入10个整数1, 3，5，7, 9，10，8，6, 4，2,将运行结果填入上表中。#数据结构实验报告(4)班号序号姓名成绩2 .算法设计（1）建立一个长度为n的单链表，数据域存放节点序号（递增），然后反转该单链表。提示：首先建立一个空链表一结点；插入到新链表（an，,a1（逆置

12、后链表的初值）；取出原链表（a1,.,an） 中的 序）的表头处；重复上面的两步，直到原链表空止。带头结点的单链表的头指针 指向第1个元素结点将h用作新链表作头指针参考算法：void reverse (node *h) /h:node *s, * p=h-n ext; /ph- next=NULL; /while (p !=NULL) s=p; p=p-next; / (1)将s结点从原链中删除s-next=h-next; h-next=s; / (2)将 s 插入新链首部（2）已知线性表中的元素按值递增排列，并以单链表作存储结构，删除表中所有值大于min且小于max的元素（若表中存在这样的元

13、素）。测试数据：min=3,max=9带头结点的单链表的头指针参考算法：void del( node *h, int min, int max) / h:node *q=h, * p=h- next; /初值while (p !=NULL & p-datan ext; / p指向其值min的结点，q是p的前趋while (p !=NULL & p-datan ext; delete u ; /删除所有的其值min并且n ext=p;3.链表的综合应用（选做）利用单链表写一个学生成绩系统.（具有查询成绩，修改成绩，删除成绩，添加成绩，全班平均的功能），数据举例如下：学号学生姓名语文成绩英语成绩数

14、学成绩6Ala n85909815Dan ie76708017Helen95989620Bill65608023P eter796586一、实验目的1了解栈和队列的特点；2 掌握栈与队列的存储结构;3 .应用实训。二、实验内容91 数制转换(1 )问题描述将十进制数N和其他d进制。(2 )转换方法除d取余，例如将(1348)10 (3 )参考算法void conversion。 /* 将10进制数转换为In itStack(&s); /* scanf( “ %d , &n);while( n!=0)转换为(2504)8进制数*/构造空栈s */ pu sh(s, n %8);n /= 8; /

15、* n%88 ,方法：除8取余。进栈(4052进栈)*/while( !stacke mp ty(s) e= pop(s); printf( “%d , e); (4 )参考程序mai n() /* 将10进制数转换为8进制数*/int i,n;int top=0,s100;/*prin tf(i nput n=);sca nf(%d, &n); /*输入一个整数 */prin tf(n(%d)10=(, n);while( n!=0) sto p=n%8; top+; /* n%8 n=n/8;while( top 0) /*当栈不空时，出栈，并输出*/top-; /*出栈 */prin t

16、f(%d, sto p);prin tf()8n);getch();/*出栈(逆向输出)*/设置一个空栈*/入栈*/(5)完成10进制到2进制和16进制的转换，用C程序实现。(程序和运行结果写在反面)2借助队列完成基数排序。1）问题描述将一组整数，排列成按从小到大的次序。借助队列，实现基数排序。2）基数排序策略对于待排序数据不足 2 位的高位补 0，然后按位进行排序。 首先个位有序（2-1 ）分配操作 : 考察个位 , 放入相应队列中 （2-2 ）收集操作 : 按队列 0-9 收集 然后在个位有序的基础上，十位有序。方法同上。存储结构#define n 20int an+1;/* a1-an

17、用于存储 n 个整数 */int q10n /* 定义 10个队列 q0q9 */int f10,r10; /* 是 10 个队列的队首指针和队尾指针 */参考算法void distribute1( ) /* 分配算法 个位排序 */int i,j;for ( i=0;i=9; i+) fi=0; ri=0; for ( i=1; i=n;i+) j=ai%10; /* 分解个位数 qjrj=ai; rj+; /* ai/* 队列初始化 */*/的个位数是j , ai进入队列j */void distribute2( ) /* 分配算法 十位排序 */int i,j;for ( i=0;i=9

18、; i+) fi=0; ri=0; for ( i=1; i=n;i+) j=ai /10; /* 分解十位数qjrj=ai; rj+; /* ai/* 队列初始化 */*/的十位数是j , ai进入队列j */void collect ( ) /* 收集算法 , 按队列 q 0 q9 收集 */ int i,j,k=1;for (i=0;i=9;i+)for (j=0;j=ri; j+) ak=qij;k+;13void main（ ）*/ /* 给定 n 个 0-99 之内的整数，借助队列实现基数排序 void main（ ）int i,j;for(i=1; i=n; i+) printf

19、 (%5d,ai);printf(n);distribute1();collect( );for(i=1; i=n; i+) printf (%5d,ai);printf(n);distribute2();collect( );for(i=1; i=n; i+)printf (%5d,ai);printf(n);getch();(5)用 C 语言实现基数排序。 (程序写在反面)6）思考：基数排序的时间复杂性是多少？(6-1)用大 O 表示。(6-2)与你熟悉的排序方法 （如选择排序和冒泡排序） 比较，基数排序方法是否快一些？(6-3)有没有增加空间开销？空间复杂性是多少？用大 O 表示。(6-

20、4)与其他排序算法（如选择排序和冒泡排序）比较其实质性的不同是什么？6-5）基数排序最适合与什么情形？（6-6）进一步思考，能否以链表为存储结构，实现该算法？若使用链式队列，该程序 的空间复杂性又是多少呢？7）运行结果：数据结构实验报告（5）班号序号姓名成绩一、实验目的1了解串的特点和存储结构；2. 基于行结构，实现串的运算。二、实验内容1 给定字符串s，求s中的第i个字符开始的长度为 m的子串t。（1 ）存储结构un sig ned char t256 (2)参考算法void substr /* 求从串int j 1;,s256;/* t0: t 串长度,s0: s(un sig ned c

21、har t256, un sig ned char s256s中的第i个字符开始长度为m的子串t */*判断i和m的合法性*/串长度*/,int i,int m)#if(i=s0|m s0-i+1) printf(参数错！”)；else t0=m;向子串t复制字符*/for(j=1;j=m;j+)tj=sj+i-1; /*C语言，编写程序，输入你的身份证号，输出生日。（程序写在反面）(4)程序测试2 串的模式匹配。 （1 ）问题描述给定一个文本（主串），查找某一特定的单词 （子串），该操作称为串的模式匹配。设S为主串，T为模式串，如果S中有模式为T的子串，则返回该子串在 S中的位 置，若S中有

22、多个模式为T的子串时，则返回的是模式串 T在S中第一次出现的位置， 这种情况称匹配成功；否则，称为匹配失败。（2）算法思想设有两个串S （目标串）和T （模式串），其中:S=s1s2s3snT=t1t2t3tm （ K mc n,通常有 m n）模式匹配算法的基本思想是用T中字符依次与 S中字符比较。当在某一趟匹配中出i-m （本趟匹配的现t1 = si-m+1 , t2 = si-m+2，tm = si，那么匹配成功，返回序号 开始位置）。串长度 */ 串长度 */3）存储结构 unsigned char s256;/*s0: s char t128; /* t0： t4)算法设计int i

23、ndex(char s, char t) /* 在串 s 中找模式串int i=1,j=1;while (i=s0 & jt0) return i-t0;else return 0;t 首次出现的位置，若不存在返回0。*/*继续匹配下一个字符 */主串和子串依次匹配下一个字符主串、子串指针回溯重新开始下一次匹配/* 主串从下一个位置开始匹配子串从头开始匹配 */*/*/*/* 返回匹配的第一个字符的下标 */* 模式匹配不成功 */17( 5)编写一个 C 程序实现。(程序写在反面)2 个子串，其中一个子串在主串中，另（ 6）程序测试要求，从键盘输入一段文字，输入 一个子串不在主串中。运行结果

24、为：（7）写一程序完成子串替换操作，将串s中的子串t全部替换成串V。（程序写在反面）一、实验目的1. 了解huffman树的特点；2. 熟悉静态二叉链存储结构;3. 二叉树的应用实训。二、实验内容1. 问题描述huffman 编码。问题描述：对任意输入的一段字符，为每个字符编制其相应的2. 分析(1) 统计输入的一段英文中出现了多少个字符，和每个字符出现了多少次(权值)。(2) 根据n个权值构造huffman树， 并进行huffman编码。3. huffman 树的构造方法(1) 给定w1,w2,.,wn,构成F=T1,T2,.,Tn,每个树只有一个根结点；(2) 选择两个根结点最小的二叉树，

25、作为左子树和右子树，构成一新的二叉树； 直至一棵树止。4.存储结构int w2* n; /* wi:int l2* n; /* li:int r2* n; /* ri:int p 2* n; /* pi:第 第 第 第iiiiint hcn+1 n; /* hc10-hc n0:个结点的权值*/个结点的左孩子的地址 个结点的右孩子的地址 个结点的父结点的地址 存放*/*/*/n个叶子的编码长度*/5.参考算法/* 构造 huffman 树 */void set_huffma n_tree()/*初值：将n个权值视为n个二叉树，每个结点的左孩子、右孩子、父结点均为0 */for(i=1;i=n

26、;i+)li=ri=0;for(i=1;i=m;i+)P i=0；w0=32767;for (i=n+1;i=m;i+)/* 在w1-wi-1 中选择pj=0 且wj最小的结点，其序号为 sl*/ sl=0;for (j=1;j=i-1;j+)if (wjwsl & pj=0)最小值为wsl*/sl=j;/*p sl=i;li=sl;/*在 w1-wi-1中选择 pj=0 且 wj 最小的结点，其序号为 sr*/sr=0;最小值为 wsr*/for (j=1;j=i-1;j+) if (wjwsr&pj=0) sr=j; /* psr=i; ri=sr;wi=wsl+wsr;/* 构造 huf

27、fman 编码 */void set_huffman_code()*/ /* 叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码for(i=1;i=n;i+)k=0; /k:c=i;f=pi; /* f: cwhile(f!=0) k+;if(lf=c) hcik=0; /* celse hcik=1;c=f;f=pf; /* hci0=k; /* 记 huffman 编码的长度的父结点 */* c沿着叶子结点将第 i 个字符的/* 输出 huffmanvoid set_huffman_code() for (i=1;i=n;i+) printf(%d=1;j-) printf(%d,hcij)

28、;printf(n); getch();编码 */-,wi);1，逆向输出6. 写一个 C 程序，完成*/是f的左孩子，编码为0 */ 是 f 的右 孩子 , 编码为 1 */根的方向，继续进行哈夫曼编码huffman 编码的码长 k 存于 hci0huffman 编码 */huffman 编码。( c 程序写在反面)*/中*/运行结果写在反面)7. 测试数据及运行结果 char *s=abaaddcdaabacdcadc ;数据结构实验报告（7）班号序号姓名成绩一、实验目的1了解图的存储结构;2. 掌握图的有关算法;3. 图的应用实训。二、实验内容1. 问题描述在一个高速公路网上，一辆汽车从

29、任一入口进入到任一出口。实现高速公路收费程序。2. 分析2-1上述问题是计算每对顶点间（即入口和出口之间）的最短路径问题，可以用邻接矩 阵为存储结构，采用floyd算法解决。2-2各种不同的车辆收费标准不同，其收费可以用线性表 cm来表示，即第i类车的收费标准是每公里ci元。2-3收费：所求的路径长度*车型费。3. 存储结构*/#define n 7/* n ：高速公路网上入口（出口）数#define m 5 /* m : m 种车型 */#define e 10 /* e :边数 */#define max 9999*/int gnn;/*图的邻接矩阵，gij:两个相邻入口之间的路径长度in

30、t cm+1=0,10,15,20,30,50; /* 第i类车的收费标准是每公里ci元*/4. 算法设计4-1建立图的邻接矩阵void set_gra ph() int i,j,k,h;for(i=0;i=n-1;i+)for (j=0;j=n-1;j+)gij=MAX;for(i=0;i=n-1;i+)gii=0;for(k=1;k=e;k+) printf(n请输入第d条边(入口到出口)的长度，格式入口编号，出口编号，里程数,k);scan f(%d,%d,%d,&i，&j,&h);while(i n-1|j n-1|h=0) printf(n输入错误，编号超出范围或里程数为负，请重新输

31、入！ n);sca nf(%d,%d,%d, &i,&j, &h);gij=gji=h;195-2 floyd 算法void short_ path()*/ /* floyd算法，计算每对顶点间的最短路径int i,j,k;for ( k=0; k=n-1 ;k+)for ( i=0 ;i=n-1 ;i+) for(j=0;j=n-1; j+)if (gik+gkjk,则在左子表中继续进行二分查找；若 rmid.k，则执行在右子表中继续进行二 分查找。(2)存储结构#define N 1000int a N ; /* N 是线性表的容量*/int n; /*n是线性表的长度*/3)参考算法in

32、t search_bin (int r ， int n， int k) /* 在长度为 n 的有序表中，查找int mid， i=1， j=n ;while ( i=j )mid=(i+j)/2 ;/*取中 */if ( k= rmid ) return (mid) ;else if ( k rmid ) j=mid-1; elsei=mid+1;k */*/*/*查找成功 */ 在左半部分继续查找 在右半部分继续查找*/*/return(0); 用 C 语言实现二分查找程序。测试数据：30int a1000=1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31

33、,33,35,37,39,41,43,45,47,49 ， 在这组数据中查找 15和3散列查找算法思想是 key 在 hash 表中的地址 =key ；1-1)构造 hash 表 计算： j=hash(key), j 若 htj 为空 , 则 htj 否则，解决冲突，直到若 htj为空止，htj=key;(1-2) hash表的查找 计算： j=hash(key)， j 是 key 在 hash 表中的地址htj 为空止 , 查找失败 htj=key 止，查找成功若 htj 为空 ， 则查找失败； 否则，解决冲突，直到或2)存储结构#define M 1000n 个大于 0 的正整数 */n/

34、M 约等于 3/4 */int ht M ; /* M 是hash表的容量，可以存储 int n; /* n是hash表中的元素个数，3)参考算法3-1)构造 hash 表算法void create_hashtable(int ht, int n) int j,i,key;for (i=0; i=M-1; i+) hti=-1; /* hash 表初始化 */for (i=1; i=n; i+)*/3-2)scanf(“%d”,&key); j=hash(key); /* 计算 hash 函数 */ if (htj=-1) htj=key;while ( htj!=-1) j=(j+1)%M;

35、htj=key;/* j 既 key 在 hash 表中的地址/* 利用线性探测法解决冲突*/hash查找算法int search_ hash_(int ht, int key) int j;j=hash(key); /* 计算 hash 函数 */ if (htj=-1) return -1;/* 查找失败 */if (htj=key) return j;/* 查找成功 */while ( htj!=-1& htj!=key) j=(j+1)%M;if (htj=-1) return -1;if (htj=key) return j;/*/*/* 利用线性探测法解决冲突 查找失败 */ 查找

36、成功 */*/用 C 语言编写程序构造hash表，并实现 hash查找。测试数据：在地址空间 ht0-ht16 中以 14,1,68,27,55,23,11,10,19,20,79,84 探测法处理冲突，hash 函数： hash(key)= key % 17 。在hash表中查找 55和65建立散列表，并用线性6）运行结果6）思考：查找失败时，可以插入吗？如何修改查找算法？25数据结构实验报告(9)班号序号姓名成绩一、实验目的1了解各种排序算法；2实现冒泡排序、选择排序等排序算法；3学会在特定的场合选用最为合适的排序算法。二、实验内容1.冒泡排序(1)排序思想相邻的两个元素进行比较，将较小数

37、向前换较大的数向后换。(2 )存储结构#define N 1000int a N ; /* N 是线性表的容量*/int n; /*n是线性表的长度*/(3 )参考算法void bubble_sort( int a , i nt n) j=1;do swa p=0; /* swa p:for ( i=1;iri+1)交换标志，swap=0表示未交换*/*j=j+1;while (j=n & swap !=0) /* r0=ri; ri=rj; rj=r0;swa p=1;交换ri和ri+1, swp =1进行过交换*/排序n-1趟或排序至无交换为止*/用C语言实现冒泡排序，并显示每一趟的排序结

38、果。测试数据：431974751477101374(6)运行结果(排序结果)2.选择排序29(1)排序思想在待排序的数据中选择最小值。(2 )存储结构#define N 1000int a N ; /* N 是线性表的容量*/int n; /*n是线性表的长度*/(3)参考算法 void selectsort ( ) /*对记录序列 a1.an 进行简单选择排序 */int i,j,k;for ( i=1; i=n-1; i+ ) /* k=i;for (j=i+1;j=n;j+) if (ajak)k=j; /* if (i!=k)进行 n-1 趟 */保持 ak 最小 */ r0=ri;ri=rk; rk=r0; 待排序的数据中选择最小值，并存入 ri 处 */*（4） 大值。用 C 语言实现选择排序，在待排序的n 个数据中选择前 k 个最大值并输出前 k 个最测试数据随机产生 10000 个 100 之内的整数，输出前 10 个最大值。randomize() ，5-1 ）随机数的初始化使用的