第一篇：《算法设计综合实验》教案
《算法设计综合实验》教案
统计与应用数学学院
2012年5月11日制
实验一 数据类型、运算符和表达式
实验目的：
1、掌握C语言数据类型，熟悉如何定义一个整型、字符型和实型的变量，以及对它们赋值的方法；
2、掌握不同的数据类型之间赋值的规律；
3、学会使用C的有关算术运算符，以及包含这些运算符的表达式，特别是自加和自减运算符的使用；
4、学会使用赋值运算符及复合赋值运算符；
5、进一步熟悉C程序的编辑、编译、连接和运行的过程。
实验环境：
Windows操作系统、Visual C++6.0
实验学时：2学时； 实验内容：
1、整型变量实型变量、字符型变量的定义与输出，赋整型常量值时的情形，以及给整型变量赋字符常量值时的情形；
2、各类数值型数据间的混合运算；
3、要将“China”译成密码，密码规律是：用原来的字母后面第4各字母代替原来的字母。例如，字母“A”后面第4个字母是“E”，用“E”代替“A”。因此，“China”应译成“Glmre”。请编一程序，用赋初值的方法使c1、c2、c3、c4、c5这5个变量的值分别为’C’、’h’、’i’、’n’、’a’，经过运算，使c1、c2、c3、c4、c5分别变为’G’、’l’、’m’、’r’、’e’，并输出。
实验二 顺序结构程序设计
实验目的：
1、掌握C语言中赋值语句的使用方法；
2、掌握各种类型数据的输入输出方法，能正确使用各种格式转换符；
3、学习调试程序。
实验环境： Windows操作系统、Visual C++6.0 实验学时：2学时； 实验内容：
1、掌握各种格式转换符的正确使用方法；
2、设圆半径r=1.5，圆柱高h=3，求圆周长、圆面积、圆球表面积、圆球体积、圆柱体积。用scanf输入数据，输出计算结果。输出时要有文字说明，取小数点后两位数字。
3、编程序：用getchar函数读入两个字符给c1、c2，然后分别用putchar函数和printf函数输出这两个字符。上机运行程序，比较用printf和putchar函数输出字符的特点。
实验三 选择结构程序设计
实验目的：
1、了解C语言表示逻辑量的方法（以0代表“假”，以非0代表“真”）。
2、学会正确使用逻辑运算符和逻辑表达式。
3、熟练掌握if语句和switch语句。
4、学习调试程序。
实验环境：
Windows操作系统、Visual C++6.0 实验学时：2学时； 实验内容：
1、有一函数
(x1)xy2x1(1x10)3x11(x10)
用scanf函数输入x的值，求y值（运行程序，输入x的值，检查输出的y值是否正确）。
2、给出一个百分制成绩，要求输出成绩等级A、B、C、D、E，90分以上为A，80～89分为B，70～79分为C，60～69分为D，60分以下为E。要求：（1）事先编好程序，要求用switch语句来实现，运行程序，并检查输出结果是否正确。（2）修改程序，当输入分数为负值，或大于100时，通知用户“输入数据错误”，程序结束。（3）修改程序，要求用if结构来实现，运行程序，并检查输出结果是否正确。
3、给一个不多于5位的正整数，要求求出它是几位数，打印出每一位数字，并按逆序打印出各位数字。
4、输入4个整数，要求按由小到大的顺序输出。
5、求方程axbxc0的解。2实验四 循环结构程序设计
实验目的：
1、熟练掌握用while语句，do-while语句；
2、掌握for语句实现循环的方法，掌握在程序设计中用循环的方法实现一些常用算法（如穷举、迭代、递推等）；
3、掌握break语句和continue语句的使用；
4、掌握循环结构程序中典型的算法；
5、进一步学习调试程序；
实验环境：
Windows操作系统、Visual C++6.0 实验学时：3学时； 实验内容：
1、编程计算1!+2!+3!+„„n!的值，其中，n值由键盘输入。
2、输入一行字符，分别统计出其中的大小写字母、空格、数字和其他字符的个数。
3、输入两个正整数m和n，求它们的最大公约数和最小公倍数；
4、猴子吃桃问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上再吃时，见只剩下一个桃子了。求第一天共摘了多少桃子。
5、求s=a+aa+aaa+„+aa„a之值，其中a是一个数字，n表示a的位数；
6、有一分数序列：2/1,3/2,5/3,8/5,13/8,21/13„„，求出这个数列的前20项之和。
实验五 数组
实验目的：
1、掌握一维数组和多维数组的定义、赋值和输入输出的方法；
2、掌握两种排序算法：冒泡法排序和选择法排序；
3、掌握字符数组和字符串的使用；
4、掌握字符串处理函数的应用；
实验环境：
Windows操作系统、Visual C++6.0 实验学时：5学时； 实验内容：
1、求两个2×3和3×2的矩阵之积，并把结果显示出来。2、10个人的成绩存放在score数组中，编写程序，将不及格的人数，最低分和最高分显示出来。
3、任意给定三个字符串，编写程序：用两种方法给出最大的一个。
4、编写程序，实现矩阵(5行6列)的转置(即行列互换)。
5、输出杨辉三角（要求输出10行）。
6、编程：将一个十进制整数转换成二进制数。
7、将两个字符串连接起来，用strcat函数和不用strcat函数两种情形；
实验六 函数
实验目的：
1、掌握定义函数的方法；
2、掌握函数实参与形参的对应关系，以及“值传递”的方式。
3、掌握函数的嵌套调用和递归调用的方法；
4、掌握全局变量和局部变量、动态变量、静态变量的概念和使用方法；
实验环境：
Windows操作系统、Visual C++6.0 实验学时：6学时； 实验内容：
1、编程序：通过一个函数判断字符串是否为回文?若是则函数返回1，主函数中输出yes，否则返回0，主函数中输出no。回文是指顺读和倒读都是一样的字符串。
ncm2、编程实现由主函数输入m，n并输出最终结果，按下述公式计算的值：
ncmm!nn!(mn)!，其中函数f的功能是计算阶乘，函数g的功能是求cm的值。要求三个函数分别存在三个不同的文件中。
3、编写一个函数fun，它的功能是：将字符串a中所有下标为奇数位置上的字母转换为大写(若该位置上不是字母，则不转换)。主函数只能用来输入输出字符串。
4、小软件。功能是：输入1，测试姓名的得分；输入2，测试两个名字的缘分；输入3，测试某一天的幸运度。要求：三个功能要用三个独立的函数编写，主函数只能用来输入输出结果。
5、写一个判别素数的函数，在主函数输入一个整数，输出是否素数的信息。本程序应当准备以下测试数据：17、34、2、1、0。分别运行并检查结果是否正确。
6、编程序：用递归法将一个整数n转换成字符串。例如，输入483，应输出”483”。n的位数不确定，可以是任意的整数。
7、编程序：求两个函数的最大公约数和最小公倍数，用一个函数求最大公约数。用另一个函数根据求出的最大公约数求最小公倍数。（要求：不用全局变量，分别用两个函数求最大公约数和最小公倍数。两个整数在主函数中输入，并传送给函数1，求出的最大公约数返回主函数，然后再与两个整数一起作为实参传递给函数2，以求出最小公倍数，返回到主函数输出最大公约数和最小公倍数。）
8、编程序：用全局变量的方法，分别用两个函数求最大公约数和最小公倍数，但其值不由函数带回。将最大公约数和最小公倍数设为全局变量，在主函数中输出它们的值。
实验七 指针
实验目的：
1、通过实验进一步掌握指针的概念，会定义和使用指针变量；
2、能正确使用数组的指针和指向数组的指针变量；
3、能正确使用字符串指针和只想字符串的指针变量；
4、了解指向指针的指针的概念及使用方法。
实验环境：
Windows操作系统、Visual C++6.0 实验学时：6学时； 实验内容：
1、编程序：用指针方法编写程序，输入3个整数，将它们按由小到大的顺序排列输出。然后将程序改为：输入3个字符串，按由小到大的顺序输出。
2、编程序：将一个3×3的矩阵转置，用一函数实现之。在主函数中用scanf函数输入以下矩阵元素：
1357911131519
将数组名作为函数实参，在执行函数的过程中实现矩阵转置，函数调用结束后在主函数中输出已转置的矩阵。
3、编程序：用一个函数实现两个字符串的比较，即自己写一个strcmp函数，函数的原型为：int strcmp(char *p1,char *p2);设p1指向字符串s1，p2指向字符串s2，要求s1＝s2时，函数返回值为0；如果s1≠s2，返回它们二者第一个不相同字符的ASCII码差值（如 “BOY”与 “BAD”，第二个字母不相同，“O”与“A”之差为79－65＝14）；如果s1>s2，则输出正值；如s1 4、编程序：用指向指针的指针的方法对n个整数排序并输出。要求将排序单独写成一个函数。n和各整数在主函数中输入。最后在主函数中输出。 实验八 综合训练 实验目的： 综合运用C语言知识，设计实用的一个小系统。实验环境： Windows操作系统、Visual C++6.0 实验学时：6学时； 实验内容： 请编写完成如下功能的程序： 在主函数main()中输出如下形式的菜单： Management System of Scores Input the data Out the data Sort the data Search one data Exit the System 然后，输出： Please input your choice: 接收键盘上输入的选择，分别完成输入数据、输出数据、排序数据、查找数据以及结束程序运行的功能。其中前4个功能分别编写函数 input(), output(), sort(), search()实现，第5个功能可以通过调用系统函数 exit(0)实现。 实验九 结构体与共用体 实验目的： 1、掌握结构体类型变量的定义和使用； 2、掌握结构体类型数组的概念和使用； 3、掌握链表的概念，初步学会对链表的操作； 4、掌握共用体的概念与使用。 实验环境： Windows操作系统、Visual C++6.0 实验学时：4学时； 实验内容： 1、编程序：有5个学生，每个学生的数据包括学号、姓名、3门课的成绩，从键盘输入5个学生的数据，要求输出3门课总平均成绩，以及最高分的学生的数据（包括学号、姓名、3门课的成绩、平均分数）。要求用一个Input函数输入5个学生数据：用一个average函数求总平均分；用max函数找出最高分学生数据；总平均分和最高分的学生的数据在主函数中输出。 2、编程序：13个人围成一圈，从第1个人开始顺序报号1、2、3。凡报到“3”者退出圈子，找出最后留在圈子中的人原来的序号。 3、编程序：建立一个链表，每个结点包括：学号、姓名、性别、年龄。输入一个年龄，如果链表中的结点所包含的年龄等于此年龄，则将此结点删去。 课型：新课 《算法与程序设计》（选修）人教版 教学目标： 1.进一步理解什么是；算法，知道算法的多样性 2.能够对设计的算法做简装的评价 3.学会利用自然语言、流程图和伪代码来描述算法 教学内容 1.了解什么是算法及其特征 2.学习三种描述算法语言 教学重点:通过例子设计算法 教学难点:三种描述算法语言的使用 课时数：1课时 正课讲解 一、算法是“灵魂” 1.算法存在于人们生活中，如：上街购物、顾客付款、营业员（主）找银等。 2.“韩信点兵问题”有不同的求解过程，就有不同的算法。 有N个人，除以3，5，7，分别余2，3，2，求N。 3.算法——解决问题的方法和步骤。 算法是尼克劳斯.沃斯（N.Writh）提出的，他指出：算法+数据结构=程序。 （即算法不能单独构成程序，它必须和数据结构合二为一） 4.算法的发现 时间：公元前3000年~公元前1500年 地点：巴比伦 巴比伦人求解“算法”的过程：先用解代数方法，再计算实际数目，最后写上一句短句“这就是一个过程”。 5.算法的特征 我们曾在必须修课中提过一点算法，如：冒泡排序法。 例：计算1+2+3+„„+100=？ 分析：这个算法有限制范围，可以在有限时间内完成，这是算法的第一个特征：有穷性。计算此算法可以用纸笔、算盘、运算器 和计算机来完成，且计算过程是多样的，但结果是唯一的。这就是算法的可行性、确定性。 计算方法： ⑴把这100个数按顺序相加。 ⑵用凑数法：1+99=100，2+98=100，3+97=100，„„，49+51，最后只剩下50和100。 ⑶令S=0，使1≤n≤100，先执行S=S+n ⑴，再执行n=n+1 ⑵ n=1，S=0时，S（0）=1 n=2，S=1时，S（0）=3 n=3，S=3时，S（0）=6 n=4，S=6时，S（0）=10 n=5，S=10时，S（0）=15 n=6，S=15时，S（0）=21„„ 算法的另外一个特征：输入、输出。 练习：水仙花数问题，如153=1^3+5^3+3^3，分析它应满足什么条件才能使用此方法？ 二、如何描述算法 1.用自然语言描述算法 ⑴自然语言——人们日常生活中使用的语言。 ⑵此种语言的特点：通俗语易懂，缺乏直观性和简洁，且易产生歧义。 使用此种语言的注意事项：描述要求尽可能精确，详尽。 例：用自然语言描述凯撒密码的原理 第1步：输入26个英文字母，它们分别对应1~26个数学。 第2步：令a=1，k=3，n=26。 第3步：使a的取值范围为1≤a≤26，F(a)=(a+k)mod n，转第5步。 第4步：a=a+1，转第3步。 第5步：输出F(a)相对应的数字。 第6步：把数学转化成相当的字母，输出字母。 第7步：累计字母出现顺序，转第4步。 练习：现有一串字母“PROGRAM”给它加密，请设计算法，用自然语言描述。 2.用流程图描述算法 ⑴特点：描述算法形象、直观，容易理解。 ⑵流程图符号 3.用伪代码描述算法 特点：描述的算法简、易懂，修改容易，容易转化为程序语言代码。 例：分析课本经9页算法描述 第一个条件：y mod 4=0 判断闰年的条件：⑴y不能被100整除；⑵y能被400整除且y能被400整除。 判断不是闰年的条件：⑴y mod 4=0 且y mod 100=0,但y不能被400整除；⑵y不能被4整除。 表示条件判断语句 表示循环处理语句： IF 条件 THEN 执行语句一 Do While 条件循环语句 ELSE执行语句二 Loop END IF 条件语句中可以包含多个子语句 实践：用表格比较自然语言、流程图和伪代码3种描述方法的优缺点。 实验八 概率算法（2学时） 一、实验目的与要求 熟悉快速排序算法； 通过本实验加深对概率算法的理解。 二、实验内容： 利用随机序列选取枢轴值，改进快速排序算法。 三、实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。实验提示 void QuickSort(int r[ ], int low, int high) { if(low i=Random(low, high); r[low]←→r[i]; k=Partition(r, low, high); QuickSort(r, low, k-1); QuickSort(r, k+1, high); } } 四、实验过程 优化选取枢轴 三数取中，即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。对于非常大的待排序的序列来说还是不足以保证能够选择出一个好的pivo tkey，因此还有个办法是所谓的九数取中，先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。 public class QuickSortRealize { public static void QuickSort(int[] arr){ QSort(arr,0,arr.length-1);} /* * 对顺序表子序列作快速排序 待排序序列的最小下标值low和最大下标值high */ public static void QSort(int[] arr,int low,int high){ int pivot;if(low QSort(arr, low, pivot-1);//对低子表递归排序 QSort(arr, pivot+1, high);//对高子表递归排序 } } /* * 选择一个关键字，想尽办法将它放到一个位置，使得它左边的值都比小，* 右边的值都比它大，我们称这个关键字叫枢轴。*/ public static int Partition(int[] arr,int low,int high){ if(arr == null || low<0 || high>=arr.length){ new Exception();} int pivotkey; ChoosePivotkey(arr,low,high);//选取枢轴值 pivotkey = arr[low]; while(low high--;} Swap(arr, low, high);while(low public static void Swap(int[] arr,int low,int high){ int temp = arr[low];arr[low] = arr[high];arr[high] = temp;} /* * 三数取中 选择枢轴 将枢轴值调至第一个位置 */ public static void ChoosePivotkey(int[] arr,int low,int high){ int mid = low +(int)(high-low)/2;if(arr[low]>arr[high]){ //保证左端较小 Swap(arr, low, high);} if(arr[mid]>arr[high]){ //保证中间较小 Swap(arr, mid, high);} if(arr[mid]>arr[low]){ //保证中间较小 Swap(arr, mid, low);} } public static void main(String[] args){ int[] arr = {50,10,90,30,70,40,80,60,20};QuickSort(arr);for(int array : arr){ System.out.print(array+“ ”);} System.out.println();} } 五、实验结果 六、心得体会 通过本次利用随机序列选取枢轴值，改进快速排序算法的实验，我熟悉快速排序算法，并加深对概率算法的理解。 《算法设计与分析》实验报告 实验3贪心算法 姓名 学号班级 实验日期实验地点 一、实验目的 1、掌握贪心算法的设计思想。 2、理解最小生成树的相关概念。 二、实验环境 1、硬件环境 CPU：酷睿i5 内存：4GB 硬盘：1T 2、软件环境 操作系统：Windows10 编程环境：jdk 编程语言：Java 三、实验内容：在Prim算法与Kruskal算法中任选一种求解最小生成树问题。 1、你选择的是：Prim算法 2、数据结构 （1）图的数据结构——图结构是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系，即结点之间的关系可以是任意的，图中任意元素之间都可能相关。 图形结构——多个对多个，如 （2）树的数据结构——树结构是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。树形结构——一个对多个，如 3、算法伪代码 Prim(G,E,W)输入：连通图G 输出：G的最小生成树T 1.S←{1};T=∅ 2.While V-S ≠∅ do 3.从V-S中选择j使得j到S中顶点的边e的权最小；T←T∪{e} 4.S←S∪{j} 3、算法分析 时间复杂度：O(n)空间复杂度：O(n^2) 4、关键代码（含注释） package Prim; import java.util.*;publicclass Main { staticintMAXCOST=Integer.MAX_VALUE; staticint Prim(intgraph[][], intn){ /* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */ intlowcost[]=newint[n+1]; /* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */ intmst[]=newint[n+1]; intmin, minid, sum = 0; /* 默认选择1号节点加入生成树，从2号节点开始初始化 */ for(inti = 2;i<= n;i++){ /* 标记1号节点加入生成树 */ mst[1] = 0; /* n个节点至少需要n-1条边构成最小生成树 */ for(inti = 2;i<= n;i++){ /* 找满足条件的最小权值边的节点minid */ for(intj = 2;j<= n;j++){ /* 输出生成树边的信息:起点，终点，权值 */ System.out.printf(“%c1, minid + 'A''A' + 1;intj = chy-'A' + 1;graph[i][j] = cost;graph[j][i] = cost;for(intj = 1;j<= n;j++){ } graph[i][j] = MAXCOST;} } System.out.println(”Total:"+cost);} } 5、实验结果（1）输入 （2）输出 最小生成树的权值为： 生成过程： (a) (b) (d) (e) (c) 四、实验总结（心得体会、需要注意的问题等） 这次实验，使我受益匪浅。这次实验我选择了Prim算法来求出树的最小生成树，在编写代码的过程中，我对Prim算法有了更深的了解，也使我对算法设计与分析更有兴趣，今后一定要更努力的学习这门课。 金陵科技学院实验报告 学 生 实 验 报 告 册 课程名称： 学生学号： 所属院部： （理工类） 算法与数据结构 专业班级： 13网络工程 1305106009 学生姓名： 陈韬 网络与通信工程学院 指导教师： 沈奇 14 ——20 15 学年 第 1 学期 金陵科技学院教务处制 金陵科技学院实验报告 实验报告书写要求 实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。 实验报告书写说明 实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 （1）细致观察，及时、准确、如实记录。（2）准确说明，层次清晰。 （3）尽量采用专用术语来说明事物。 （4）外文、符号、公式要准确，应使用统一规定的名词和符号。（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。 金陵科技学院实验报告 实验项目名称： 顺序表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。 （2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。（3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。 （4）删除顺序表中所有等于X的数据元素。 2、选做题 （5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。 程序清单： #include 金陵科技学院实验报告 } sequenlist;sequenlist L={{1,3,5,5,7,8,10,12,17},8};void print_list(){ int i;for(i=0;i<=L.last;i++)printf(“%4d”,L.data[i]);} void find_all_x(int x){ int found=0,i;for(i=0;i<=L.last;i++)if(L.data[i]==x){ printf(“%3d”,i+1);found=1;} if(found==0)printf(“-1n”);} void insert_x(int x){ int loc,i;for(i=0;i<=L.last;i++)if(x 金陵科技学院实验报告 loc=i;for(i=L.last;i>=loc;i--)L.data[i+1]=L.data[i];L.data[loc]=x;L.last++;} void delete_x(int x){ int i,j,found=0;for(i=0;i<=L.last;i++)if(x==L.data[i]){ found=1;for(j=i+1;j<=L.last;j++)L.data[j-1]=L.data[j];i--;L.last--;} if(found==0)printf(“x is not foundn”);else { printf(“x is deletedn”);printf(“the list after deletion is:n”);print_list(); 金陵科技学院实验报告 } } void main(){ int x,choice;while(1){ printf(“**********menu**********n”);printf(“ 1--printn”);printf(“ 2--searchn”);printf(“ 3--insertn”);printf(“ 4--deleten”);printf(“ 5--exitn”);printf(“please input your choice:”);scanf(“%d”,&choice); switch(choice){case 1: printf(“the original list is:n”);print_list();break;case 2: printf(“pls input x you want to search:n”); 金陵科技学院实验报告 scanf(“%d”,&x);find_all_x(x);break;case 3: printf(“pls input x you want to insert:n”);scanf(“%d”,&x);insert_x(x);printf(“the list after insertion is:n”);print_list();break;case 4: printf(“pls input x you want to delete:n”);scanf(“%d”,&x);delete_x(x);printf(“the list after deletion is:n”);print_list();break;case 5: exit(0);} } } 金陵科技学院实验报告 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 单链表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验2 单链表 一、实验目的和要求 1、实验目的 掌握单链表的定位、插入、删除等操作。 2、实验要求 （1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。 （2）链表不能实现直接定位，一定注意指针的保存，防止丢失。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2）在递增有序的单链表中插入一个新结点x，保持单链表的有序性。 解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。 （3）编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。 2、选做题 已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。程序清单： 金陵科技学院实验报告 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 堆栈和队列 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验3 堆栈和队列 一、实验目的和要求 （1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。 （3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）判断一个算术表达式中开括号和闭括号是否配对。（2）测试“汉诺塔”问题。 （3）假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。 2、选做题 在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 串 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验4 串 一、实验目的和要求 掌握串的存储及应用。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。 （2）编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。 解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。（3）设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。 2、选做题 假设以链结构表示串，编写算法实现将串S插入到串T中某个字符之后，若串T中不存在这个字符，则将串S联接在串T的末尾。 提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 二叉树 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验5 二叉树 一、实验目的和要求 （1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。 （2）在第一题基础上，求二叉树中叶结点的个数。（3）在第一题基础上，求二叉树中结点总数。（4）在第一题基础上，求二叉树的深度。 2、选做题 已知一棵完全二叉树存于顺序表sa中，sa.elem[1…sa.last]存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。 解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 图 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验6 图 一、实验目的和要求 （1）熟练掌握图的基本概念、构造及其存储结构。 （2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）构造一个无向图（用邻接矩阵表示存储结构）。 （2）对上面所构造的无向图，进行深度优先遍历和广度优先遍历，输出遍历序列。 2、选做题 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。简单路径是指其顶点序列中不含有重复顶点的路径。提示：两个顶点及k值均作为参数给出。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 排序 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验7 排序 一、实验目的和要求 （1）熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的基本概念。 （2）掌握以上各种排序的算法。区分以上不同排序的优、缺点。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 用随机数产生100000个待排序数据元素的关键字值。测试下列各排序函数的机器实际执行时间（至少测试两个）：直接插入排序、希尔排序（增量为4，2，1）、冒泡排序、快速排序、直接选择排序、堆排序。 2、选做题 假设含n个记录的序列中，其所有关键字为值介于v和w之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v…w]，令number[i]统计关键字为整数i的纪录个数，然后按number重排序列以达到有序。试编写算法实现上述排序方法，并讨论此种方法的优缺点。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 查找 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验8 查找 一、实验目的和要求 （1）掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。（2）掌握哈希表设计。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）在一个递增有序的线性表中利用二分查找法查找数据元素X。 2、选做题 （2）构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。 提示：构造哈希表只是完成查找的第一步，大家应该掌握在哈希表上进行查找的过程，可以试着编程序实现。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会）第二篇：算法描述与设计教案
第三篇：实验八 概率算法
第四篇：实验3 贪心算法（定稿）
第五篇：算法与数据结构实验
点击咨询 