《数据结构》内部排序12种算法上机实验报告
成都信息工程学院计算机系
课
程
实
验
报
告
（说明：实验报告必须包含下面的每项内容，根据实验情况认真填写，封面必须打印或复印（A4纸），书写上机实验报告内容的纸张也用A4纸，最后从侧面装订）
一【上机实验目的】
目的：从键盘输入一组数，通过内部排序的12种算法对这组数字进行排序。熟练掌握刚
刚学过的内部排序的算法，并对这12种排序算法的时间复杂度进行比较，根据不同的情况，选择合适的算法
二【实验环境】
PC机每人1台
三【上机实验内容】
实现内部排序的12种排序算法的全排序。
四【上机调试程序流程图】（注：可打印）
（用传统流程图的形式表示）
五【上机调试中出现的错误信息、错误原因及解决办法】
（记录下你调试程序中出现的错误信息的英文提示，分析出错原因及可能的解决办法）
六【上机调试后的源程序及还存在的问题】（注：源程序可打印）
（同时记录下你对你编写此程序的其它具体想法，）
主要的程序：
/********************************直接插入排序***************************/ void InsertSort(SqList &L)
{//直接插入排序
int i,j;
for(i=2;i<=L.length;++i)
{
if(L.r[i].key<=L.r[i-1].key)
{
L.r[0]=L.r[i];
L.r[i]=L.r[i-1];
for(j=i-2;(L.r[0].key L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; } } } /*********************************折半插入排序************************/ void BinsertSort(SqList &L) {//折半插入排序 int i,j,low,high,m; for(i=2;i<=L.length;i++) { L.r[0]=L.r[i]; low=1; high=i-1; while(low<=high) { m=(low+high)/2; if(L.r[0].key high=m-1; else low=m+1; } for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; } } /**********************************2-路插入排序***********************/ void P2_InsertSort(SqList &L) {//2—路插入排序 int i,j,first,final; RedType *d; d=(RedType*)malloc(L.length*sizeof(RedType)); //生成L.length个记录的临时空间d[0]=L.r[1]; first=final=0; // first、final分别指示d中排好序的记录的第1个和最后1个记录的位置for(i=2;i<=L.length;++i) { //依次将L的第2个～最后1个记录插入d中 if(L.r[i].key { // 待插记录小于d中最小值，插到d[first]之前(不需移动d数组的元素) first=(first-1+L.length)%L.length; // 设d为循环向量 d[first]=L.r[i]; } else if(L.r[i].key>d[final].key) { //待插记录大于d中最大值，插到d[final]之后(不需移动d数组的元素) final=final+1; d[final]=L.r[i]; } else { //待插记录大于d中最小值，小于d中最大值，插到d的中间(需要移动d数组的元素) j=final++; // 移动d的尾部元素以便按序插入记录 while(L.r[i].key { d[(j+1)%L.length]=d[j]; j=(j-1+L.length)%L.length; } d[j+1]=L.r[i]; } } for(i=1;i<=L.length;i++) // 把d赋给L.r L.r[i]=d[(i+first-1)%L.length]; //线性关系 } /***************************************希尔排序***************************/ void ShellInsert(SqList &L,int dk) { // printf("OK"); int i,j; for(i=dk+1;i<=L.length;i++) if(L.r[i].key { L.r[0]=L.r[i]; for(j=i-dk;j>0&&(L.r[0].key L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0]; } } void ShellSort(SqList &L,int dlta[],int t) { // printf("OK"); int k; for(k=0;k ShellInsert(L,dlta[k]); // display(L); } /***********************************表插入排序***********************/ void TableInsert(SLinkListType &SL,RedType D[]){ //由数组D建立的n个元素的表插入排序的静态链表SL int i,p,q; SL.r[0].rc.key=INT_MAX; //表头结点记录的关键字取得最大整数（非降序表的表尾） SL.r[0].next=0; //next域为0表示表尾（现为空表，初始化） for(i=0;i SL.r[i+1].rc=D[i]; //将数组D的值赋给静态链表SL q=0; p=SL.r[0].next; while(SL.r[p].rc.key<=SL.r[i+1].rc.key){ //静态链表后移 q=p; p=SL.r[p].next; } SL.r[i+1].next=p; SL.r[q].next=i+1; //将当前记录插入到静态链表 } SL.length=MAXSIZE; } void Arrange(SLinkListType &SL) { //根据静态链表SL中各结点的指针值调整记录位置，使得SL中记录按关键字非递减有序排列 int i,p,q; SLNode t; p=SL.r[0].next; //p指示第一个记录的当前位置 printf("%d ",SL.length); for(i=1;i { //SL.r[i...i-1]中记录已按关键字有序排列，第i个记录在SL中的当前记录不应小于i while(p p=SL.r[p].next; //找到第i个记录，并用p指示其在SL中当前位置 q=SL.r[p].next; //q指示当前未调整的表尾 if(p!=i){ t=SL.r[p]; //交换记录，使第i个记录到位 SL.r[p]=SL.r[i]; SL.r[i]=t; SL.r[i].next=p; //指向被移走的记录，使得以后可由while循环找回} p=q; //p指示未调整的表尾，为找到第i+1个记录作准备// print(SL); // printf("\n"); } } /*************************************冒泡排序***********************/ void bubble_sort(SqList &L) {//冒泡排序 int i; int k; RedType tem; for(i=L.length-1,k=1;i>=1&&k;--i) { k=0; for(int j=1;j<=i;++j) { if(L.r[j].key>L.r[j+1].key) { tem=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=tem; k=1; } } } } /************************************快速排序**************************/ int Partition(SqList &L,int low,int high) {//快速排序递归函数的实现 int pivotkey; L.r[0]=L.r[low]; pivotkey=L.r[low].key; while(low { while(low --high; L.r[low]=L.r[high]; while(low L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low; } /********************************简单选择排序***********************/ int SelectMinKey(SqList &L,int i) { int j,k=i; for(j=i+1;j { if(L.r[k].key>L.r[j].key) k=j; } return k; } void Select_Sort(SqList &L) { int i,j; RedType tem; for(i=1;i { j=SelectMinKey(L,i); if(i!=j) { tem=L.r[i]; L.r[i]=L.r[j]; L.r[j]=tem; } } } /**************************************堆排序*************************/ void HeapAdjust(HeadType &L,int s,int m) {//对生成的堆进行排序，生成大顶堆 RedType rc; rc=L.r[s]; int j; for(j=2*s;j<=m;j*=2) { if(j if(rc.key>=L.r[j].key) break; L.r[s]=L.r[j]; s=j; } L.r[s]=rc; } void HeadSort(HeadType &L) {//对一组无序的数字进行排序生成堆 int i; RedType temp; for(i=L.length/2;i>0;--i) HeapAdjust(L,i,L.length); for(i=L.length;i>1;--i) { temp=L.r[1]; L.r[1]=L.r[i]; L.r[i]=temp; HeapAdjust(L,1,i-1); } } /**************************************归并排序***************************/ void Merge(RedType SR[],RedType TR[],int s,int m,int t) {//printf("+_+_+_+_+_+_"); int i,j,k; // RcdType *tem; for(j=m+1,k=s,i=s;i<=m&&j<=t;k++) { if(SR[i].key TR[k]=SR[i++]; else TR[k]=SR[j++]; } while(i<=m) { // for(l=0;l TR[k++]=SR[i++]; } while(j<=t) { // for(l=0;l TR[k++]=SR[j++]; } } void MSort(RedType SR[],RedType TR1[],int s,int t) { int m; RedType TR2[MAXSIZE+1]; if(s==t) TR1[s]=SR[s]; else { m=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t); } } void MergeSort(SqList &L) { MSort(L.r,L.r,1,L.length); } /************************************基数排序*************************/ oid InitList(SLList &L,RedType D[],int n) // 初始化静态链表L(把数组D中的数据存于L 中) { char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY]; int i,j,max=D[0].key; // max为关键字的最大值 for(i=1;i if(max max=D[i].key; L.keynum=int(ceil(log10(max))); L.recnum=n; for(i=1;i<=n;i++) { L.r[i].otheritems=D[i-1].otherinfo; itoa(D[i-1].key,c,10); // 将10进制整型转化为字符型，存入c for(j=strlen(c);j { strcpy(c1,"0"); strcat(c1,c); strcpy(c,c1); } for(j=0;j } void Distribute(SLCell r[],int i,ArrType f,ArrType e) // 算法10.15 { // 静态键表L的r域中记录已按(keys[0]，…，keys[i-1])有序。本算法按 // 第i个关键字keys[i]建立RADIX个子表，使同一子表中记录的keys[i]相同。 // f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录 int j,p; for(j=0;j for(p=r[0].next;p;p=r[p].next) { j=r[p].keys[i]-'0'; // 将记录中第i个关键字映射到[0..RADIX-1] if(!f[j]) f[j]=p; else r[e[j]].next=p; e[j]=p; // 将p所指的结点插入第j个子表中 } } void Collect(SLCell r[],ArrType f,ArrType e) // 算法10.16 // 本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成 // 一个链表，e[0..RADIX-1]为各子表的尾指针。 { int j,t; for(j=0;!f[j];j=++j); // 找第一个非空子表 r[0].next=f[j]; t=e[j]; // r[0].next指向第一个非空子表中第一个结点 while(j { for(j=++j;j if(f[j]) // 链接两个非空子表 { r[t].next=f[j]; t=e[j]; } } r[t].next=0; // t指向最后一个非空子表中的最后一个结点 } void printl(SLList L)// 按链表输出静态链表 { int i=L.r[0].next,j; while(i) { for(j=L.keynum-1;j>=0;j--) printf("%c",L.r[i].keys[j]); printf(" "); i=L.r[i].next; } void RadixSort(SLList &L) // 算法10.17 // L是采用静态链表表示的顺序表。对L作基数排序，使得L成为按关键字// 自小到大的有序静态链表，L.r[0]为头结点。 { int i; ArrType f,e; for(i=0;i L.r[L.recnum].next=0; // 将L改造为静态链表 for(i=0;i Collect(L.r,f,e); // 第i趟收集 printf("第%d趟收集后:\n",i+1); printl(L); printf("\n"); } } void print(SLList L)// 按数组序号输出静态链表 { int i,j; printf("keynum=%d recnum=%d\n",L.keynum,L.recnum); for(i=1;i<=L.recnum;i++) { printf("keys="); for(j=L.keynum-1;j>=0;j--) printf("%c",L.r[i].keys[j]); printf(" otheritems=%d next=%d\n",L.r[i].otheritems,L.r[i].next); } } void Sort(SLList L,int adr[]) // 改此句(类型) // 求得adr[1..L.length]，adr[i]为静态链表L的第i个最小记录的序号 { int i=1,p=L.r[0].next; while(p) { adr[i++]=p; p=L.r[p].next; } } void Rearrange(SLList &L,int adr[]) // 改此句(类型) // adr给出静态链表L的有序次序，即L.r[adr[i]]是第i小的记录。 // 本算法按adr重排L.r，使其有序。算法10.18(L的类型有变) { int i,j,k; for(i=1;i if(adr[i]!=i) { j=i; L.r[0]=L.r[i]; // 暂存记录L.r[i] while(adr[j]!=i)// 调整L.r[adr[j]]的记录到位直到adr[j]=i为止 { k=adr[j]; L.r[j]=L.r[k]; adr[j]=j; j=k; // 记录按序到位 } L.r[j]=L.r[0]; adr[j]=j; } } 运行效果图： 七【上机实验中的其他它问题及心得】 （在上机实验中遇到的你不能解决的其它问题，简单描述一下你此次上机的收获及感想）心得： 排序时计算机程序设计中的一种重要的操作，因为我们无论做什么样的程序都会涉及到排序算法，在第十章的内部排序算法中，基本上都是一些经典的排序算法，这是我选择这个题目的主要原因，因为通过这个综合设计，我可以了解不同的排序算法，根据不同的情况，选择更好的算法。 在本章中共有12种算法：插入排序5种，选择排序3种，快速排序2种，归并排序和基数排序。在没有接触本章之前，我们只是接触了简单的冒泡排序和选择排序，这些只是对数n不是很大的情况，当n值很大时，我们果继续使用这些简单的算法，时间复杂度会很大的。因此，在本章中介绍的这些算法，适合我们遇到的任何情况，不能够说那种算法是好的，不同的算法都有好坏，我们可以根据不同的情况，从这些算法中选择合适的算法。 每一种排序都有最好的情况和最坏的情况。1.从平均时间性能而言，快速排序是最好的，因为其所用的时间是最少的。但是，如果想到最坏的情况，当然就要考虑到堆排序和归并排序。堆排序对n值较大时是比较有效的，因为堆排序主要的耗时是在建初始堆和调整建新堆时进行的反复的“筛选”。当n值很大时，归并排序所需时间较堆排序省，但是归并排序所需要的辅助空间较多。入过在输入一行数字是，这些数字是基本有序的，为了节省时间和空间，可以选择冒泡排序和简单选择排序。从方法的稳定性来说：基数排序时稳定的内部排序算法，所有时间复杂度为O(n^2)的简单排序法也是稳定的，但是，快速排序、堆排序和希尔排序等时间较好的排序方法都是不稳定的。一般来说，排序过程中的“比较“是在“相邻两个关键字”间进行的排序方法是稳定的。 因此，在所有的算法当中，没有哪一种算法是绝对最优的。有的适用于n较大时，有的 适合n的有序情况，有的……，所以，在使用时需要根据不同的情况适当选用，甚至可将多种方法结合起来使用。 其它问题：在这个综合设计中，我的设计思路是：先点——面。就是先编好每一种算法， 当每一种算法都能够运行的时候，然后再将所有的程序结合到一起，组合成我的综合设计。但是问题就出现了，我在编写每一个算法的时候，结构体定义的不一样，结果，当我将所有的算法都结合到一起时，会出现很多的错误，不能够运行，花费我大量的时间寻找错误。到目前为止，基数排序一直没有加到里面去，因为前面的算法基本上都是在顺序存储结构上是现代的，但是基数排序使用的是静态链表，结构体定义的不一样，而且，初始化也不一样。现在我只有将基数排序单独运行。 《计算方法》实验报告 姓名： 班级： 学号： 实验日期: 2011年10月26日 一、实验题目： 数值积分 二、实验目的： 1．熟悉matlab 编写及运行数值计算程序的方法。 2．进一步理解数值积分的基础理论。 3．进一步掌握应用不同的数值积分方法求解给定的积分并给出数据结果及误差分析。 三、实验内容： 1．分别用复合梯形求积公式及复合辛普森求积公式计算积分xdx x ln 10 ? , 要求计算精度达到410-,给出计算结果并比较两种方法的计算节点数. 2．用龙贝格求积方法计算积分dx x x ?+3 021,使误差不超过510-. 3．用3=n 的高斯-勒让德公式计算积分?3 1 sin x e x ,给出计算结果. 4．用辛普森公式(取2==M N ) 计算二重积分.5 .00 5 .00 dydx e x y ? ? - 四、实验结果： 1.（1）复合梯形法: 将区间[a,b]划分为n 等份，分点n k n a b h kh a x k ,2,1,0,,=-=+=在每个区间[1,+k k x x ](k=0,1,2,···n-1)上采用梯形公式，则得 )()]()([2)()(1 11 1 f R x f x f h dx x f dx x f I n n k k k b a n k x x k k ++===∑?∑? -=+-=+ 故)]()(2)([21 1 b f x f a f h T n k k n ++=∑-=称为复合梯形公式 计算步长和划分的区间 Eps=1E-4 h1=sqrt(Eps/abs(-(1-0)/12*1/(2+1))) h1 =0.0600 N1=ceil(1/h1) N1 =17 用复合梯形需要计算17个结点。 复合梯形： function T=trap(f,a,b,n) h=(b-a)/n; 《计算方法》上机实验报告 班级：XXXXXX 小组成员：XXXXXXX XXXXXXX XXXXXXX XXXXXXX 任课教师：XXX 二〇一八年五月二十五日 前言 通过进行多次的上机实验，我们结合课本上的内容以及老师对我们的指导，能够较为熟练地掌握Newton 迭代法、Jacobi 迭代法、Gauss-Seidel 迭代法、Newton 插值法、Lagrange 插值法和Gauss 求积公式等六种算法的原理和使用方法，并参考课本例题进行了MATLAB 程序的编写。 以下为本次上机实验报告，按照实验内容共分为六部分。 实验一： 一、实验名称及题目： Newton 迭代法 例2.7(P38):应用Newton 迭代法求 在 附近的数值解 ，并使其满足 . 二、解题思路： 设'x 是0)(=x f 的根,选取0x 作为'x 初始近似值,过点())(,00x f x 做曲线)(x f y =的切线L ,L 的方程为))((')(000x x x f x f y -+=,求出L 与x 轴交点的横坐标) (') (0001x f x f x x - =,称1x 为'x 的一次近似值,过点))(,(11x f x 做曲线)(x f y =的切线,求该切线与x 轴的横坐标) (') (1112x f x f x x - =称2x 为'x 的二次近似值,重复以上过程,得'x 的近似值序列{}n x ,把 ) (') (1n n n n x f x f x x - =+称为'x 的1+n 次近似值，这种求解方法就是牛顿迭代法。 三、Matlab 程序代码： function newton_iteration(x0,tol) syms z %定义自变量 format long %定义精度 f=z*z*z-z-1; f1=diff(f);%求导 y=subs(f,z,x0); y1=subs(f1,z,x0);%向函数中代值 x1=x0-y/y1; k=1; while abs(x1-x0)>=tol x0=x1; y=subs(f,z,x0); y1=subs(f1,z,x0); x1=x0-y/y1;k=k+1; end x=double(x1) K 四、运行结果： 实验二： 数据结构与算法设计 实验报告 （2016 — 2017 学年第1 学期） 实验名称： 年级： 专业： 班级： 学号： 姓名： 指导教师： 成都信息工程大学通信工程学院 一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 （1）从键盘读入一组无序数据，按输入顺序先创建一个线性表。 （2）用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。 三、实验步骤 1、创建工程（附带截图说明） 2、根据算法编写程序（参见第六部分源代码） 3、编译 4、调试 四、实验结果图 图1-直接输入排序 图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比，本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法，但冒泡 排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。 六、源代码 要求：粘贴个人代码，以便检查。 #include 算法设计与分析基础 实验报告 应用数学学院 二零一六年六月 实验一插入排序算法 一、实验性质设计 二、实验学时14学时 三、实验目的 1、掌握插入排序的方法和原理。 2、掌握java语言实现该算法的一般流程。 四、实验内容 1、数组的输入。 2、输入、输出的异常处理。 3、插入排序的算法流程。 4、运行结果的输出。 五、实验报告 Ⅰ、算法原理 从左到右扫描有序的子数组，直到遇到一个大于（或小于）等于A[n-1]的元素，然后就把A[n-1]插在该元素的前面（或后面）。 插入排序基于递归思想。 Ⅱ、书中源代码 算法InsertionSort（A[0..n-1]） //用插入排序对给定数组A[0..n-1]排序 //输入：n个可排序元素构成的一个数组A[0..n-1] //输出：非降序排列的数组A[0..n-1] for i ←1 to n-1 do v ← A[i] j ← i-1 while j ≥0and A[j] > v do A[j+1] ← A[j] j ← j-1 A[j+1] ← v Ⅲ、Java算法代码： import java.util.*; public class Charu { public static void main(String[] args) { int n = 5; int a[] = new int[n]; int s = a.length; int i = 0, j = 0, v = 0; System.out.println("请输入若干个数字："); Scanner sc = new Scanner(System.in); try { while (i < s) { a[i] = sc.nextInt(); i++; } for (i = 1; i 本科实验报告 课程名称：计算机数值方法 实验项目：方程求根、线性方程组的直接解 法、线性方程组的迭代解法、代数插值和最 小二乘拟合多项式 实验地点：行勉楼 专业班级： ******** 学号： ********* 学生姓名： ******** 指导教师：李誌，崔冬华 2016年 4 月 8 日 y = x*x*x + 4 * x*x - 10; return y; } float Calculate(float a,float b) { c = (a + b) / 2; n++; if (GetY(c) == 0 || ((b - a) / 2) < 0.000005) { cout << c <<"为方程的解"<< endl; return 0; } if (GetY(a)*GetY(c) < 0) { return Calculate(a,c); } if (GetY(c)*GetY(b)< 0) { return Calculate(c,b); } } }; int main() { cout << "方程组为：f(x)=x^3+4x^2-10=0" << endl; float a, b; Text text; text.Getab(); a = text.a; b = text.b; text.Calculate(a, b); return 0; } 2.割线法： // 方程求根（割线法）.cpp : 定义控制台应用程序的入口点。// #include "stdafx.h" #include"iostream" 心得体会 使用不同的方法，可以不同程度的求得方程的解，通过二分法计算的程序实现更加了解二分法的特点，二分法过程简单，程序容易实现，但该方法收敛比较慢一般用于求根的初始近似值，不同的方法速度不同。面对一个复杂的问题，要学会简化处理步骤，分步骤一点一点的循序处理，只有这样，才能高效的解决一个复杂问题。 《数据结构》实验报告排序实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 1. 插入排序：直接插入排序的基本操作是，将一个记录到已排好序的有序表中，从而得到一个新的，记录增一得有序表。 一般情况下，第i 趟直接插入排序的操作为：在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后，变成含有i 个记录的有序子序列r[1..i ]；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r [0]处设置哨兵。在自i-1 起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1 趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第2 个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 （通常可选第一个记录L.r[s]）作为枢轴（或支点）（PiVOt ）,然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线，将序列{L.r[s] ，… ，L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序，或一次划分。 一趟快速排序的具体做法是：附设两个指针lOw 和high ，他们的初值分别为lOw 和high ，设枢轴记录的关键字为PiVOtkey ，则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换，然后从lOw 所指位置起向后搜索，找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换，重复这两不直至low=high 为止。 具体实现上述算法是，每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上， 简单计算器 姓名: 周吉祥 实验目的：模仿日常生活中所用的计算器，自行设计一个简单的计算器程序，实现简单的计算功能。 实验内容： (1)体系设计： 程序是一个简单的计算器，能正确输入数据，能实现加、减、乘、除等算术运算，运算结果能正确显示，可以清楚数据等。 (2)设计思路： 1)先在Visual C++ 6.0中建立一个MFC工程文件，名为 calculator. 2)在对话框中添加适当的编辑框、按钮、静态文件、复选框和单 选框 3)设计按钮，并修改其相应的ID与Caption. 4)选择和设置各控件的单击鼠标事件。 5)为编辑框添加double类型的关联变量m_edit1. 6)在calculatorDlg.h中添加math.h头文件，然后添加public成 员。 7)打开calculatorDlg.cpp文件，在构造函数中，进行成员初始 化和完善各控件的响应函数代码。 (3)程序清单： ●添加的public成员： double tempvalue; //存储中间变量 double result; //存储显示结果的值 int sort; //判断后面是何种运算：1.加法2.减法3. 乘法 4.除法 int append; //判断后面是否添加数字 ●成员初始化： CCalculatorDlg::CCalculatorDlg(CWnd* pParent /*=NULL*/) : CDialog(CCalculatorDlg::IDD, pParent) { //{{AFX_DATA_INIT(CCalculatorDlg) m_edit1 = 0.0; //}}AFX_DATA_INIT // Note that LoadIcon does not require a subsequent DestroyIcon in Win32 m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME); tempvalue=0; result=0; sort=0; append=0; } 实验报告名称 班级：学号：姓名：成绩： 1实验目的 1）通过对二分法与牛顿迭代法作编程练习与上级运算，进一步体会二分法与牛顿迭代法的不同特点。 2）编写割线迭代法的程序，求非线性迭代法的解，并与牛顿迭代法。 2 实验内容 用牛顿法和割线法求下列方程的根 x^2-e^x=0; x*e^x-1=0; lgx+x-2=0; 3实验步骤 1)根据二分法和牛顿迭代法，割线法的算法编写相应的求根函数； 2)将题中所给参数带入二分法函数，确定大致区间； 3)用牛顿迭代法和割线法分别对方程进行求解； 3 程序设计 牛顿迭代法x0=1.0; N=100; k=0; eps=5e-6; delta=1e-6; while(1) x1=x0-fc1(x0)/fc2(x0); k=k+1; if k>N disp('Newmethod failed') break end if(abs(x1-x0) 2010级数据结构实验报告 实验名称：排序 姓名：袁彬 班级： 2009211120 班内序号： 09 学号： 09210552 日期： 2010 年12 月19 日 1．实验要求 试验目的： 通过选择试验内容中的两个题目之一，学习、实现、对比各种排序的算法，掌握各种排序算法的优缺点，以及各种算法使用的情况。 试验内容： 题目一： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②希尔排序 ③冒泡排序； ④快速排序； ⑤简单选择排序； ⑥堆排序 ⑦归并排序 ⑧基数排序 ⑨其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 题目二： 使用链表实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②冒泡排序； ③快速排序； ④简单选择排序； ⑤其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙（选作） ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构 程序中每一个算法均是用一个类来表示的，类中有自己的构造函数、排序函数。 程序的储存结构采用数组。数组的第一个位置不存储数据。数据从第二个位置开始。数组中的相对位置为数组的下标。 2.2 关键算法分析 ㈠、关键算法： 1、插入排序函数：Insert s ort(int n) ①、从2开始做循环，依次和前面的数进行比较：for(int i=2;i<=n;i++) ②、如果后面的比前面的小，则进行前移：if(number[i] 《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的，记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort，它的参数是一个数组A[1..n]，包含了n 个待排序的数。用伪代码表示直接插入排序算法如下： InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是，通过一趟排序将待排序序列分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序序列为数组A[1..n]，首先选取第一个数A[0]，作为枢轴（pivot），然后按照下述原则重新排列其余数：将所有比A[0]大的数都排在它的位置之前，将所有比A[0] 小的数都排在它的位置之后，由此以A[0]最后所在的位置i 作为分界线，将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序，对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey，则首先从high 所指位置起向前搜索，找到第一个小于pivotkey 的数，并将其移到低端，然后从low 所指位置起向后搜索，找到第一个大于pivotkey 的数，并将其移到高端，重复这两步直至low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下： Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low 计算方法实验报告格式 小组名称: 组长姓名(班号)： 小组成员姓名(班号): 按贡献排序情况: 指导教师评语: 小组所得分数: 一个完整的实验，应包括数据准备、理论基础、实验内容及方法，最终对实验结果进行分析，以达到对理论知识的感性认识，进一步加深对相关算法的理解，数值实验以实验报告形式完成，实验报告格式如下： 一、实验名称 实验者可根据报告形式需要适当写出． 二、实验目的及要求 首先要求做实验者明确，为什么要做某个实验，实验目的是什么，做完该实验应达到什么结果，在实验过程中的注意事项，实验方法对结果的影响也可以以实验目的的形式列出． 三、算法描述（实验原理与基础理论） 数值实验本身就是为了加深对基础理论及方法的理解而设置的，所以要求将实验涉及到的理论基础，算法原理详尽列出． 四、实验内容 实验内容主要包括实验的实施方案、步骤、实验数据准备、实验的算法以及可能用到的仪器设备． 五、程序流程图 画出程序实现过程的流程图，以便更好的对程序执行的过程有清楚的认识，在程序调试过程中更容易发现问题． 六、实验结果 实验结果应包括实验的原始数据、中间结果及实验的最终结果，复杂的结果可以用表格 形式列出，较为简单的结果可以与实验结果分析合并出现． 七、实验结果分析 实验结果分析包括对对算法的理解与分析、改进与建议． 数值实验报告范例 为了更好地做好数值实验并写出规范的数值实验报告，下面给出一简单范例供读者参考． 数值实验报告 小组名称: 小组成员(班号): 按贡献排序情况: 指导教师评语: 小组所得分数: 一、实验名称 误差传播与算法稳定性． 二、实验目的 1．理解数值计算稳定性的概念． 2．了解数值计算方法的必要性． 3．体会数值计算的收敛性与收敛速度． 三、实验内容 计算dx x x I n n ? += 1 10 ，1,2,,10n = ． 四、算法描述 由 dx x x I n n ? += 1 10 ，知 dx x x I n n ?+=--101110，则 数值分析上机实验报告 《数值分析》上机实验报告 1.用Newton 法求方程 X 7-X 4+14=0 在（0.1，1.9）中的近似根（初始近似值取为区间端点，迭代6次或误差小于0.00001）。 1.1 理论依据： 设函数在有限区间[a ，b]上二阶导数存在，且满足条件 {}α?上的惟一解在区间平方收敛于方程所生的迭代序列 迭代过程由则对任意初始近似值达到的一个中使是其中上不变号 在区间],[0)(3,2,1,0,) (') ()(],,[x |))(),((|,|,)(||)(|.4;0)(.3],[)(.20 )()(.110......b a x f x k x f x f x x x Newton b a b f a f mir b a c x f a b c f x f b a x f b f x f k k k k k k ==- ==∈≤-≠>+ 令 )9.1()9.1(0)8(4233642)(0)16(71127)(0)9.1(,0)1.0(,1428)(3 2 2 5 333647>?''<-=-=''<-=-='<>+-=f f x x x x x f x x x x x f f f x x x f 故以1.9为起点 ?? ?? ? ='- =+9.1)()(01x x f x f x x k k k k 如此一次一次的迭代，逼近x 的真实根。当前后两个的差<=ε时，就认为求出了近似的根。本程序用Newton 法求代数方程(最高次数不大于10)在（a,b ）区间的根。 1.2 C语言程序原代码： #include 【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释： for(j=2*i+1; j<=m; j=j*2+1) { if(j temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为："< 计算方法实验报告 班级： 学号： 姓名： 成绩： 1 舍入误差及稳定性 一、实验目的 （1）通过上机编程，复习巩固以前所学程序设计语言及上机操作指令； （2）通过上机计算，了解舍入误差所引起的数值不稳定性 二、实验内容 1、用两种不同的顺序计算10000 21n n -=∑，分析其误差的变化 2、已知连分数() 1 01223//(.../)n n a f b b a b a a b =+ +++，利用下面的算法计算f ： 1 1 ,i n n i i i a d b d b d ++==+ (1,2,...,0 i n n =-- 0f d = 写一程序，读入011,,,...,,,...,,n n n b b b a a 计算并打印f 3、给出一个有效的算法和一个无效的算法计算积分 1 041 n n x y dx x =+? (0,1,...,1 n = 4、设2 2 11N N j S j == -∑ ，已知其精确值为1311221N N ?? -- ?+?? （1）编制按从大到小的顺序计算N S 的程序 （2）编制按从小到大的顺序计算N S 的程序 （3）按两种顺序分别计算10001000030000,,,S S S 并指出有效位数 三、实验步骤、程序设计、实验结果及分析 1、用两种不同的顺序计算10000 2 1n n -=∑，分析其误差的变化 （1）实验步骤： 分别从1~10000和从10000~1两种顺序进行计算，应包含的头文件有stdio.h 和math.h （2）程序设计： a.顺序计算 #include 一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度，需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 （1）源程序如下所示： //文件名:exp10-1.cpp #include 《排序问题求解》实验报告 一、算法得基本思想 1、直接插入排序算法思想 直接插入排序得基本思想就是将一个记录插入到已排好序得序列中,从而得到一个新得, 记录数增 1 得有序序列。 直接插入排序算法得伪代码称为InsertｉonＳorｔ，它得参数就是一个数组A[1、、n］,包含了n 个待排序得数。用伪代码表示直接插入排序算法如下: IｎsｅrtｉonＳｏｒt (Ａ) for i←2 tｏn ｄo ｋeｙ←Ａ[i］／/key 表示待插入数 //Ｉnsｅrt A［i] ｉnto ｔhｅsｏrteｄｓequence A［1、、i-１］ j←i-1 wｈｉｌe j＞0 ａnｄＡ[j]＞key do A[j＋１］←A［j］ j←j-1 Ａ[j+1］←keｙ 2、快速排序算法思想 快速排序算法得基本思想就是，通过一趟排序将待排序序列分割成独立得两部分，其中一 部分记录得关键字均比另一部分记录得关键字小,则可对这两部分记录继续进行排序,以达 到整个序列有序。 假设待排序序列为数组A[１、、n]，首先选取第一个数Ａ[0],作为枢轴(ｐｉvｏt)，然后按照下述原则重新排列其余数:将所有比Ａ[0]大得数都排在它得位置之前,将所有比 A[０]小得数都排在它得位置之后,由此以A[0]最后所在得位置i 作为分界线,将数组 A[1、、n]分成两个子数组Ａ［1、、i－1］与Ａ[ｉ+1、、n］。这个过程称作一趟快速排序。通过递归调用快速排序,对子数组A[1、、ｉ-1]与A[i＋1、、n]排序。 一趟快速排序算法得伪代码称为Paｒtｉtion，它得参数就是一个数组A[１、、n］与两个指针ｌoｗ、high,设枢轴为ｐｉvotｋeｙ，则首先从higｈ所指位置起向前搜索,找到第一个小于ｐivｏtｋey得数,并将其移到低端,然后从low 所指位置起向后搜索,找到第一个大于pivotkey 得数,并将其移到高端，重复这两步直至low=ｈigh。最后,将枢轴移到正确得位置上。用伪代码表示一趟快速排序算法如下: Partiｔｉｏn ( Ａ，low，higｈ) A[０］←A[low] ／／用数组得第一个记录做枢轴记录 priｖotkey←Ａ[low] //枢轴记录关键字 wｈile lｏw<ｈigh //从表得两端交替地向中间扫描 whｉle low 南京信息工程大学实验（实习）报告 一、实验目的: 用最小二乘法将给定的十个点拟合成三次多项式。 二、实验步骤： 用matlab编制以函数为基的多项式最小二乘拟合程序，并用于对下列数据作三次多项式最小二乘拟合(取权函数wi=1) x -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 y -2.30 -1 -0.14 -0.25 0.61 1.03 1.75 2.75 4.42 6.94 给定直线方程为：y=1/4*x3+1/2*x2+x+1 三、实验结论： 最小二乘法：通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。最小二乘法还可用于曲线拟合。 一般地。当测量数据的散布图无明显的规律时，习惯上取n次代数多项式。 程序运行结果为： a = 0.9731 1.1023 0.4862 0.2238 即拟合的三次方程为：y=0.9731+1.1023x+0.4862*x2+0.2238*x3 -2.5 -2-1.5-1-0.5 00.51 1.52 2.5 -4-20246 81012 x 轴 y 轴 拟合图 离散点 y=a(1)+a(2)*x+a(3)*x.2+a(4)*x.3 结论： 一般情况下，拟合函数使得所有的残差为零是不可能的。由图形可以看出最小二乘解决了残差的正负相互抵消的问题，使得拟合函数更加密合实验数据。 优点：曲线拟合是使拟合函数和一系列的离散点与观测值的偏差平方和达到最小。 缺点：由于计算方法简单，若要保证数据的精确度，需要大量的数据代入计算。 实验报告3 实验名称：数据结构与软件设计实习 题目：内部排序算法比较 专业：生物信息学班级：01 姓名：学号：实验日期：2010.07.24 一、实验目的： 比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序； 二、实验要求： 待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数； 对结果做简单的分析，包括各组数据得出结果的解释； 设计程序用顺序存储。 三、实验内容 对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。 将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。 四、实验编程结果或过程： 1. 数据定义 typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length; }SqList; 2. 函数如下，代码详见文件“排序比较.cpp”int Create_Sq(SqList &L) void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序 void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法 void QuickSort(SqList &L) void ShellInsert(SqList &L,int dk)//希尔排序 void ShellSort(SqList &L,int dlta[ ]) 3. 运行测试结果，运行结果无误，如下图语速个数为20《计算方法》课内实验报告
计算方法上机实验报告
排序操作实验报告
插入排序算法实验报告
太原理工大学数值计算方法实验报告
《数据结构》实验报告——排序.docx
c 计算器实验报告
计算方法第二章方程求根上机报告
排序问题实验报告
算法排序问题实验报告
计算方法实验报告格式
数值分析上机实验报告
各种排序实验报告
计算方法上机实习题大作业(实验报告).
数据结构内排序实验报告
算法排序问题实验报告
计算方法实验报告 拟合
内部排序比较 (实验报告+源程序)C++