数据结构实验报告(电商-经管)1-7.doc

数据结构实验报告（1） 班号 序号_ 姓名 成绩_一、实验目的1. 复习if语句、循环语句、数组及子函数；2. 了解算法的评价标准，并将该准则应用于算法的设计中；3初步掌握时间复杂度的分析方法。二、实验内容1输入10个数据，存于一维数组a10中，并求和。main() int i, sum=0, a11; printf (n input 10 number:n); for (i=1;i=10;i+)scanf(%d,&ai); printf(n); for (i=1;i=10;i+)sum=sum+ai; printf(sum=%dn,sum);getch(); (1) 若输入10000个数据，上述程序应该如何修改，将修改后的程序写在右上方；(2) 思考修改后的程序在时间和空间上的开销是多少？2. 阅读并运行下列程序main() （1）该程序的功能是什么？ int i, j, a21; for (i=1;i=20;i+)ai=2*i-1;（2）该程序的输出结果是： i=1;j=1; while (i=20) aj=ai; j=j+1; i=i+2;（3）该程序的时间复杂度是： for (i=1;i=10;i+) printf(%5dn,ai); getch();3阅读并运行下列程序。main( )void selectsort (int s , int n) /* 主函数 */ /* 选择排序*/ int a21,n=20,i,j;int i,j,k; /* 从键盘输入20个整数 */for(i=1;in;i+) for(i=1;i=n;i+) k=i；scanf(“%d”,&ai);for(j=i+1;j=n;j+)/* 输出20个整数 */if(aj ak ) for(i=1;i=n;i+) k=j; printf(%d, ai); /*k记下目前找到的最小值的所在的位置*/ printf(n);if(k!=i) selectsort(a,n); /*排序*/ a0=ai；ai=ak；ak=a0； /* 输排序后的20个整数 */*交换ai和ak*/ for(i=1;i=n;i+) printf(%4d, ai); printf(n);getch(); （1）该程序的输出结果是： （3）该程序的时间复杂度是：4. 阅读并运行程序4-1和4-2,分析为何程序4-2较程序4-1高效？main()main() /* 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,j; for (i=1;i=20;i+) for (i=1;i=20;i+) t=1; for (j=1;j=i;j+) t=t*i; t=t*j;s=s+t;s=s+t; printf(1!+2!+20!=%ldn,s); printf(1!+2!+20!=%ldn,s); getch(); getch(); (2) 该程序的时间复杂度是：(1) 该程序的时间复杂度是：5 程序设计从键盘输入3个整数a,b,c, 按从小到大的顺序将它们输出。（程序写在反面）数据结构实验报告（2） 班号 序号_ 姓名 成绩_一、实验目的1掌握线性表逻辑结构；2掌握线性表的顺序存储结构（一维数组表示）；3算法设计，并用C语言实现。二、实验内容1读下列算法 #define MAXSIZE 100 main() 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; /* 在线性表的第i处插入x*/n+; /* 表长加1 */for (j=1;j=n;j+)printf (“%5d”,aj); /* 输出插入x后的线性表 */getch(); （1）改写插入算法，在线性表a的第i处的后面插入新元素x。（2）算法分析，元素的移动次数与哪些因素有关？（3）当n个元素按无序排列时，在哪里插入新元素x最好，将插入算法重写一遍。思考题：当n个元素按有序（例如递增次序）排列时，在哪里插入新元素e最好呢，重写插入算法。2请写一程序完成顺序表的逆置。参考算法： void alg2(int a,int n) int i,x for (i=1;i=n/2;i+) x=ai; ai=an-i+1;an-i+1=x;/* 从an-i+1与ai, 互换 */（1）用C语言编程实现；（2）分析该程序的时间复杂度 。3. 将顺序表（a1, a2, ak, ak+1, an) 改变成 (ak+1, an , a1, a2, ak )。（1）运行程序，测试数据： n=20, k=8。（2）分析时间度T(n)，用O(大欧)表示。参考程序：main() int a100=0,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,n=20,k=8, i, j,x ; for(j=1;jn) printf(参数错); else for(i=1;i=k;i+) x=a1; for(j=2;j=n;j+) aj1=aj; an=x; for(j=1;j=n;j+)printf (%3d ,aj); /* 以(ak+1, an , a1, a2, ak )的顺序输出 */ getch();（1）分析该程序的时间复杂度 。（2）重写该程序，要求在线性时间内完成。4已知线性表存于a100中的前n个分量中，写一程序删除表中所有值为0的元素（将非0元素移到前面来），各元素间的相对位置不变。存储结构定义及赋初值： int a100=-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=1;i=n;i+) if(ai=0) k+; else ai-k=ai; /* 将为0元素删除 */ n=n-k; （1）用C语言编程实现；（2）输出删除表中所有值为0的元素之后的线性表；（3）分析时间复杂性（用大O表示），并回答该算法是高效的吗？（程序及运行结果写在反面）数据结构实验报告（3） 班号 序号_ 姓名 成绩_一、实验目的1了解线性表的非顺序存储结构（链表）；2基于链表进行算法设计。二、实验内容1阅读下列程序#define n 8#define NULL 0struct node int data; struct node *next; ;main( ) struct node *head, *p, *rear; int i,x; head= (struct node*)malloc(sizeof(struct node); rear=head; for (i=1;idata=x; rear-next=p; rear=p; rear-next=NULL; for( p=head-next; p!=NULL; p=p-next) printf (“=%d”, p-data); getch();运行结果：（1）在右边加上适当的注释。（2）从键盘输入10个整数1，3，5，7，9，10，8，6，4，2，将运行结果填入上表中。2算法设计（1）建立一个长度为n的单链表，数据域存放节点序号（递增），然后反转该单链表。提示: 首先建立一个空链表 ( 逆置后链表的初值)；取出原链表(a1,.,an)中的一结点；插入到新链表(an,.,a1序)的表头处;重复上面的两步, 直到原链表空止。 参考算法：void reverse (node *h) /h:带头结点的单链表的头指针 node *s, *p=h-next; /p指向第1个元素结点 h-next=NULL; / 将h用作新链表作头指针 while (p!=NULL) s=p; p=p-next; / (1) 将s结点从原链中删除 s-next=h-next; h-next=s; / (2) 将s插入新链首部 （2）已知线性表中的元素按值递增排列, 并以单链表作存储结构， 删除表中所有值大于min且小于max的元素(若表中存在这样的元素)。测试数据:min=3,max=9参考算法：void del(node *h, int min, int max) / h:带头结点的单链表的头指针 node *q=h, *p=h-next; /初值 while (p!=NULL & p-datanext; / p指向其值min的结点, q是p的前趋 while (p!=NULL & p-datanext; delete u ; / 删除所有的其值min并且next=p; 3链表的综合应用 （选做）利用单链表写一个学生成绩系统.(具有查询成绩,修改成绩,删除成绩,添加成绩,全班平均的功能)，数据举例如下:学号学生姓名语文成绩英语成绩数学成绩6Alan85909815Danie76708017Helen95989620Bill65608023Peter796586数据结构实验报告（4） 班号 序号_ 姓名 成绩_一、实验目的1了解栈和队列的特点；2掌握栈与队列的存储结构；3应用实训。 二、实验内容1数制转换（1）问题描述将十进制数N和其他 d 进制。（2）转换方法 除d取余，例如将（1348)10 转换为 (2504)8 ，方法：除8取余。 （3）参考算法void conversion() /* 将10进制数转换为8进制数 */ InitStack(&s); /* 构造空栈s */ scanf(“%d”, &n); while(n!=0) push(s, n%8);n /= 8; /* n%8进栈 (4052进栈)*/ while( !stackempty(s) ) e=pop(s); printf(“%d”, e); /* 出栈 （逆向输出）*/ （4）参考程序main() /* 将10进制数转换为8进制数 */ int i,n; int top=0,s100;/* 设置一个空栈 */ printf(input n= ); scanf(%d, &n); /* 输入一个整数 */ printf(n(%d)10=(, n); while(n!=0) stop=n%8; top+; /* n%8 入栈 */ n=n/8; while( top0) /* 当栈不空时,出栈，并输出 */top-; /* 出栈 */ printf(%d, stop); printf()8n); getch(); （5）完成10进制到2进制和16进制的转换，用C程序实现。（程序和运行结果写在反面）2借助队列完成基数排序。（1）问题描述 将一组整数，排列成按从小到大的次序。借助队列，实现基数排序。（2）基数排序策略对于待排序数据不足2位的高位补0，然后按位进行排序。首先个位有序（2-1）分配操作: 考察个位,放入相应队列中（2-2）收集操作: 按队列 0-9 收集然后在个位有序的基础上，十位有序。方法同上。（3）存储结构#define n 20int an+1; /* a1-an 用于存储n个整数*/int q10n /* 定义10个队列q0q9 */int f10,r10; /*是10个队列的队首指针和队尾指针*/（4）参考算法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; i+) fi=0; ri=0; /*队列初始化*/ for ( i=1; i=n;i+) j=ai /10; /* 分解十位数 */ qjrj=ai; rj+; /* ai的十位数是j ，ai进入队列j */ void collect ( ) /* 收集算法, 按队列q 0q9 收集*/ int i,j,k=1;for (i=0;i=9;i+) for (j=0;j=ri; j+) ak=qij; k+; void main( ) /* 给定n个0-99之内的整数，借助队列实现基数排序 */void main( ) int i,j; for(i=1; i=n; i+) printf (%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-4) 与其他排序算法（如选择排序和冒泡排序）比较其实质性的不同是什么？（6-5）基数排序最适合与什么情形？（6-6）进一步思考，能否以链表为存储结构，实现该算法？若使用链式队列，该程序的空间复杂性又是多少呢？（7）运行结果：数据结构实验报告（5） 班号 序号_ 姓名 成绩_一、实验目的1了解串的特点和存储结构；2. 基于行结构，实现串的运算。二、实验内容1给定字符串s，求s中的第i个字符开始的长度为m的子串t。（1）存储结构 unsigned char t256，s256;/* t0：t串长度, s0: s串长度*/(2) 参考算法 void substr（unsigned char t256, unsigned char s256，int i,int m ） /* 求从串s中的第i个字符开始长度为m的子串t */int j 1; /*判断i和m的合法性*/if(i=s0|m s0-i+1) printf(参数错!); else t0=m;for(j=1;j=m;j+) tj=sj+i-1; /*向子串t复制字符*/ （3）用C语言，编写程序，输入你的身份证号，输出生日。（程序写在反面）（4）程序测试2串的模式匹配。（1）问题描述给定一个文本（主串），查找某一特定的单词（子串），该操作称为串的模式匹配。设S为主串，T为模式串，如果S中有模式为T的子串，则返回该子串在S中的位置，若S中有多个模式为T的子串时，则返回的是模式串T在S中第一次出现的位置，这种情况称匹配成功；否则，称为匹配失败。（2）算法思想设有两个串S（目标串）和T（模式串），其中： S=s1s2s3sn T=t1t2t3tm（1mn，通常有mn） 模式匹配算法的基本思想是用T中字符依次与S中字符比较。当在某一趟匹配中出现t1si-m+1，t2si-m+2，tmsi，那么匹配成功，返回序号i-m（本趟匹配的开始位置）。（3）存储结构 unsigned char s256;/*s0: s串长度*/ char t128; /* t0：t串长度*/（4）算法设计int index(char s, char t) /* 在串s中找模式串t首次出现的位置，若不存在返回0。 */int i=1,j=1; while (i=s0 & jt0) return i-t0; /*返回匹配的第一个字符的下标*/ else return 0; /*模式匹配不成功*/ （5）编写一个C程序实现。（程序写在反面） （6）程序测试要求，从键盘输入一段文字，输入2个子串，其中一个子串在主串中，另一个子串不在主串中。 运行结果为：（7）写一程序完成子串替换操作，将串s中的子串t全部替换成串v。（程序写在反面）数据结构实验报告（6）班号 序号_ 姓名 成绩_一、实验目的1了解huffman树的特点；2. 熟悉静态二叉链存储结构；3二叉树的应用实训。二、实验内容1问题描述问题描述：对任意输入的一段字符，为每个字符编制其相应的huffman编码。 2. 分析（1）统计输入的一段英文中出现了多少个字符，和每个字符出现了多少次（权值）。（2）根据n个权值构造huffman树， 并进行huffman 编码。3. huffman树的构造方法 (1) 给定w1,w2,.,wn, 构成F=T1,T2,.,Tn, 每个树只有一个根结点;(2) 选择两个根结点最小的二叉树,作为左子树和右子树, 构成一新的二叉树;, 直至一棵树止。4. 存储结构 int w2*n; /* wi:第i个结点的权值*/int l2*n; /* li:第i个结点的左孩子的地址*/int r2*n; /* ri:第i个结点的右孩子的地址*/int p2*n; /* pi:第i个结点的父结点的地址*/int hcn+1n; /* hc10-hcn0:存放n个叶子的编码长度 */5. 参考算法/* 构造huffman 树*/void set_huffman_tree() /* 初值：将n个权值视为n个二叉树，每个结点的左孩子、右孩子、父结点均为0 */ for(i=1;i=n;i+) li=ri=0; for(i=1;i=m;i+) pi=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) sl=j; /* 最小值为wsl*/ psl=i; li=sl; /* 在w1-wi-1中选择pj=0且wj最小的结点，其序号为sr*/ sr=0; for (j=1;j=i-1;j+) if (wjwsr&pj=0) sr=j; /* 最小值为wsr*/ psr=i; ri=sr; wi=wsl+wsr; /* 构造huffman 编码*/void set_huffman_code() /*叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/ for(i=1;i=n;i+) k=0; /k: 记huffman编码的长度 */ c=i; f=pi; /* f: c的父结点 */ while(f!=0) k+; if(lf=c) hcik=0; /* c是f的左孩子,编码为0 */ else hcik=1; /* c是f的右 孩子,编码为1 */ c=f; f=pf; /* 沿着叶子结点根的方向，继续进行哈夫曼编码*/ hci0=k; /* 将第i个字符的huffman 编码的码长k存于hci0中*/ /* 输出huffman 编码*/void set_huffman_code() for (i=1;i=n;i+) printf(%d-,wi); /* 从hci01，逆向输出huffman编码*/ for(j=hci0;j=1;j-) printf(%d,hcij); printf(n); getch(); 6. 写一个C程序，完成huffman编码。（c程序写在反面）7. 测试数据及运行结果 （运行结果写在反面）char *s=abaaddcdaabacdcadc ;数据结构实验报告（7）班号 序号_ 姓名 成绩_一、实验目的1了解图的存储结构；2掌握图的有关算法；3图的应用实训。二、实验内容1问题描述在一个高速公路网上，一辆汽车从任一入口进入到任一出口。实现高速公路收费程序。2分析2-1 上述问题是计算每对顶点间（即入口和出口之间）的最短路径问题，可以用