数据结构与算法
课程设计报告
课程设计题目：图的算法实现专业班级：信息与计算科学1001班姓名：学号：
设计室号：理学院机房
设计时间： 2011-12-26 批阅时间：指导教师：成绩：
图的算法实现
目录
一．设计内容
二．功能设计流程
三．详细设计
四．调试
五．总结
六．参考文献
七．附录源代码
一、设计内容：
1.实验内容
图的算法实现
（1）将图的信息建立文件；
（2）从文件读入图的信息，建立邻接矩阵和邻接表；
（3）实现Prim、Kruskal、Dijkstra序算法。
2.实现的任务：从文件中读入图的信息，建立图的邻接矩阵和邻接表，实现Prim、Kruskal、Dijkstra
3.本系统涉及的知识点
Prim、Kruskal、Dijkstra、邻接矩阵和邻接表存储。
4.功能要求
1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。
2．对系统进行功能模块分析、画出总流程图和各模块流程图。
3．用户接口要求使用方便、简洁明了、美观大方、格式统一。
4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。
5．所有程序需调试通过。
二、功能设计流程：
图的算法
实现
邻接矩阵邻接表
Prim算法Kruskal算法Dijkstra算法
开始
辅助数组初始
输出生成树的边并计算其权值
新顶点并入U 集后重新选择最小边：遍历点，若g.edges[k][j]!=0 && g.edges[k][j] closedge[j].adjvex=g.n[k];closedge[j 假 真 ｊ＝１ ｊ＜ g.n 假 真 当ｊ！＝ｋ时，有下面赋值：closedge[j].adjvex=u; closedge[j].lowcost=g .edges[k][j];j++。 closedge[k].lowcost=0; k=LocateVex(u); ｉ＝２ k=minimu m (closedge); 输出生成树的边，并且遍历顶点数组g.n[]使closedge[k].adjvex==g.n[a]。通过s=s+g.edges[a][k]计算最小生成树的长度。i++。 closedge[k].lowcost=0; 结束 用prim算法的程序流程图 2、程序无向图相关算法的基本功能 本部分程序可以对图的相关信息：顶点、边以及顶点与边的指向关系建立无向图的邻接矩阵和邻接表。 三.详细设计 3.1 1．文件保存函数模块（void getin_1()） void getin_1()// 文件保存函数 { int a,b,k,w,z;FILE *fp; if((fp=fopen("record_1.txt","w"))==NULL) /*打开文件，并判断打开是否正常*/ { printf("不能打开文件\n"); /*没打开*/ exit(0); } printf("请输入顶点数:\n"); scanf("%d",&g.n); fprintf(fp,"%d\n",g.n); printf("请输入边数:\n"); scanf("%d",&g.e); fprintf(fp,"%d\n",g.e);//初始化矩阵各元素值//读入边 printf("请输入顶点信息:\n");//顶点的信息会出现在矩阵边界上。 fflush(stdin);//清空缓冲 for (z=0;z { scanf("%c",&g.vexs[z]); fprintf(fp,"%c\n",g.vexs[z]);} for(a=0;a for(b=0;b g.edges[a][b]=0; printf("\n"); printf("请输入应的弧头a和弧尾b及弧上的权值w(皆为整数，,从0开始，格式为:a,b,w):\n"); for(k=0;k { scanf("%d %d %d",&a,&b,&w); fprintf(fp,"%d %d %d\n",a,b,w); g.edges[a][b]=w; g.edges[b][a]=w; } fclose(fp); } 建立一个名为record_1.txt的文件保存数据，保存的数据包括顶点的个数、边的条数、顶点与边之间的关系 2.文件载入模块（int getout_1()）。 void getout_1()//文件载入函数 { int i,a,b,w; FILE *fp; if((fp=fopen("record_1.txt","ab+"))==NULL) { printf("不能打开文件\n"); exit(0); } fscanf(fp,"%d\n",&g.n); fscanf(fp,"%d\n",&g.e); for(i=0;i { fscanf(fp,"%c\n",&g.vexs[i]); } for (i=0;i { fscanf(fp,"%d %d %d\n",&a,&b,&w); g.edges[a][b]=w; g.edges[b][a]=w; } } 根据文件中保存的数据，从指定文件中按格式输入数据，并根据输入图的相关信息建立对应的无向图邻接矩阵。 3．邻接矩阵输出函数（void outmatrix();） void outmatrix()//邻接矩阵输出函数 { int i,m,z; printf("所建立表的邻接矩阵为:\n"); printf("\t"); for(i=0;i printf("%c\t",g.vexs[i]); for(m=0;m { printf("\n%c\t",g.vexs[m]); for(z=0;z printf("%d\t",g.edges[m][z]); } } 将根据相关信息建立的邻接矩阵打印出显示在屏幕上。 4．Prim算法函数（void MiniSpanTree_PRIM(char u))） void MiniSpanTree_PRIM(char u) { int i,j,k; minside closedge[9999]; k=LocateVex(u); for(j=0;j { if(j!=k) { closedge[j].adjvex=u; closedge[j].lowcost=g.edges[k][j];}} closedge[k].lowcost=0; //初始,U={u} printf("\n用prim算法生成的最小生成树为：\n"); for(i=1;i { k=minimum(closedge); // 求出T的下一个结点：第K顶点 printf("(%c-%c)\n",closedge[k].adjvex,g.vexs[k]); 输出生成树的边 closedge[k].lowcost=0; // 第K顶点并入U集 for(j=0;j if(g.edges[k][j]!=0 && g.edges[k][j] { closedge[j].adjvex=g.vexs[k]; closedge[j].lowcost=g.edges[k][j]; } } } 根据输入图的相关信息建立邻接矩阵运用Prim算法得出最小生成树并将所得最小生成树的结果打印出显示在屏幕上。 5．迪杰斯特拉算法函数（void Dijkstra(int v)） void Dijkstra(int v) { int dist[N],path[N]; int s[N]; int mindis,i,j,u; for(i=0;i { for(j=0;j { if(g.edges[i][j]==0) g.edges[i][j]=9999; } } for(i=0;i { dist[i]=g.edges[v][i]; s[i]=0; if(g.edges[v][i]<9999) path[i]=v; else path[i]=-1; } s[v]=1; path[v]=0; for(i=0;i { mindis=9999; for(j=0;j { if(s[j]==0&&dist[j] { u=j; mindis=dist[j]; } } s[u]=1; for(j=0;j { if(s[j]==0) { if(g.edges[u][j]<9999&&dist[u]+g.edges[u][j] { dist[j]=dist[u]+g.edges[u][j]; path[j]=u; } } } } Dispath(dist,path,s,g.n,v); } 根据输入图的相关信息建立邻接矩阵运用Dijkstra算法得出最短路径并将所得最短路径的结果打印出显示在屏幕上。 6.克鲁斯卡尔（void Kruskal(edgetype edges[],int n) ） void Kruskal(edgetype edges[],int n) { int front[100]; int i,vf1,vf2; printf("用Kruskal算法生成的最小生成树为：\n"); for(i=0;i front[i]=0; for(i=0;i { vf1=Search(front,edges[i].w1); vf2=Search(front,edges[i].w2); if(vf1!=vf2) { front[vf2]=vf1; printf("(%c-%c)\n",edges[i].w1,edges[i].w2); } } } 3.2 数据结构的定义 typedef struct { char vexs[N]; int edges[N][N]; int n,e; //顶点数和边数 }MGraph; //定义图的节点结构体 MGraph g; / typedef struct { char adjvex; int lowcost; }minside; typedef int elemtype; typedef struct { elemtype w1; //边的一个顶点 elemtype w2; //边的另一个顶点 int Cost; //一条边的一个权值}edgetype //定义顶点及边的结构体 四调试 4.1菜单界面 4.2数据保存成功界面 4.3 prim算法现实最小生成树界面 4.4 Dijkstra显示最短路径界面 4.5用Kruskal生成最小生成树界面 五总结 通过这次的综合训练让我对所学的知识加深了印象，要想学好c语言要重在实践，要通过不断的上机操作才能更好地学习它尤其是对算法有更深的认识。对整个程序的设计，算法是非常重要的，设计程序的整体框架，就是利用算法进行设计，在短短的几天里，我们去图书馆或在网上查找了很多资料，学了一些以前没有接触过的函数，以此来完善程序的功能。然而很多函数虽然用的语法没错，但是不能运用自如，为自己所用。最后逐步完善各个函数的功能模块，同时算法也有了一定的认识。这些都为以后的学习和实践，提高自身能力有很大的帮助，本次课设也锻炼我们的实践能力和提高了处理问题的能力，获益匪浅 六参考文献 刘玉龙．《数据结构与算法》.电子工业出版社. 严蔚敏. 《数据结构》（C语言版）. 清华大学出版社 严蔚敏等《数据结构题集》（C语言版）. 清华大学出版社 徐孝凯. 数据结构实用教程（C/C++描述）. 北京:清华大学出版社. 陈慧南. 数据结构（使用C++语言描述）. 南京:东南大学出版社. 殷人昆, 陶永雷, 谢若阳等. 数据结构（用面向对象方法与C++描述）. 北京:清华大学出版社. 七. 附录源代码 #include #include #define N 9999 typedef int elemtype; typedef struct { elemtype w1; elemtype w2; int Cost; }edgetype; typedef struct { char vexs[N]; int edges[N][N]; int n,e; //顶点数和边数 }MGraph;MGraph g; typedef struct { char adjvex; int lowcost; }minside; // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(char u) { int i; for(i = 0; i < g.n; ++i) if( u==g.vexs[i]) return i; else return -1; } // 求closedge.lowcost的最小正值 int minimum(minside SZ[]) { int i=0,j,k,min; while(SZ[i].lowcost==0) i++; min=SZ[i].lowcost; //第一个不为0的值 k=i; for(j=i+1;j if(SZ[j].lowcost>0) if(min>SZ[j].lowcost) { min=SZ[j].lowcost; k=j; } return k; } //用prim算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边 void MiniSpanTree_PRIM(char u) { int i,j,k; minside closedge[9999]; k=LocateVex(u); for(j=0;j { if(j!=k) { closedge[j].adjvex=u; closedge[j].lowcost=g.edges[k][j];}} closedge[k].lowcost=0; //初始,U={u} printf("\n用prim算法生成的最小生成树为：\n"); for(i=1;i { k=minimum(closedge); // 求出T的下一个结点：第K顶点 printf("(%c-%c)\n",closedge[k].adjvex,g.vexs[k]); // 输出生成树的边 closedge[k].lowcost=0; // 第K顶点并入U集 for(j=0;j if(g.edges[k][j]!=0 && g.edges[k][j] { closedge[j].adjvex=g.vexs[k]; closedge[j].lowcost=g.edges[k][j]; } } } void outmatrix()//邻接矩阵输出函数 { int i,m,z; printf("所建立表的邻接矩阵为:\n"); printf("\t"); for(i=0;i printf("%c\t",g.vexs[i]); for(m=0;m { printf("\n%c\t",g.vexs[m]); for(z=0;z printf("%d\t",g.edges[m][z]); } } void getin_1()// 文件保存函数 { int a,b,k,w,z;FILE *fp; if((fp=fopen("record_1.txt","w"))==NULL) /*打开文件，并判断打开是否正常*/ { printf("不能打开文件\n"); /*没打开*/ exit(0); } printf("请输入顶点数:\n"); scanf("%d",&g.n); fprintf(fp,"%d\n",g.n); printf("请输入边数:\n"); scanf("%d",&g.e); fprintf(fp,"%d\n",g.e);//初始化矩阵各元素值//读入边 printf("请输入顶点信息:\n");//顶点的信息会出现在矩阵边界上。 fflush(stdin);//清空缓冲 for (z=0;z { scanf("%c",&g.vexs[z]); fprintf(fp,"%c\n",g.vexs[z]);} for(a=0;a for(b=0;b g.edges[a][b]=0; printf("\n"); printf("请输入应的弧头a和弧尾b及弧上的权值w(皆为整数，,从0开始，格式为:a,b,w):\n"); for(k=0;k { scanf("%d %d %d",&a,&b,&w); fprintf(fp,"%d %d %d\n",a,b,w); g.edges[a][b]=w; g.edges[b][a]=w; } fclose(fp); } void getout_1()//文件载入函数 { int i,a,b,w; FILE *fp; if((fp=fopen("record_1.txt","ab+"))==NULL) { printf("不能打开文件\n"); exit(0); } fscanf(fp,"%d\n",&g.n); fscanf(fp,"%d\n",&g.e); for(i=0;i { fscanf(fp,"%c\n",&g.vexs[i]); } for (i=0;i { fscanf(fp,"%d %d %d\n",&a,&b,&w); g.edges[a][b]=w; g.edges[b][a]=w; } } //用迪杰斯特拉算法求最短路径 void Ppath(int path[],int i,int v) { int k; k=path[i]; if(k==v) return; Ppath(path,k,v); printf("%d,",k); } void Dispath(int dist[],int path[],int s[],int n,int v) { int i; for(i=0;i { if(i==v) continue; if(s[i]==1) { printf("从%d到%d的最短路径长度为：%d\t路径为：",v,i,dist[i]); printf("%d,",v); Ppath(path,i,v); printf("%d\n",i); } else printf("从%d到%d不存在路径\n",v,i); } } void Dijkstra(int v) { int dist[N],path[N]; int s[N]; int mindis,i,j,u; for(i=0;i { for(j=0;j { if(g.edges[i][j]==0) g.edges[i][j]=9999; } } for(i=0;i { dist[i]=g.edges[v][i]; s[i]=0; if(g.edges[v][i]<9999) path[i]=v; else path[i]=-1; } s[v]=1; path[v]=0; for(i=0;i { mindis=9999; for(j=0;j { if(s[j]==0&&dist[j] { u=j; mindis=dist[j]; } } s[u]=1; for(j=0;j { if(s[j]==0) { if(g.edges[u][j]<9999&&dist[u]+g.edges[u][j] { dist[j]=dist[u]+g.edges[u][j]; path[j]=u; } } } } Dispath(dist,path,s,g.n,v); } int flag_1; void Undigraph() { while(1) { system("cls"); if(flag_1==0) { printf("\n\t\t提示：若无文件请先输入数据建立无向图的邻接矩阵！\n"); system("pause"); } } } int Search(int front[],int v) { int t; t=v; while(front[t]>0) t=front[t]; return t; } void Kruskal(edgetype edges[],int n) { int front[100]; int i,vf1,vf2; printf("用Kruskal算法生成的最小生成树为：\n"); for(i=0;i front[i]=0; for(i=0;i { vf1=Search(front,edges[i].w1); vf2=Search(front,edges[i].w2); if(vf1!=vf2) { front[vf2]=vf1; printf("(%c-%c)\n",edges[i].w1,edges[i].w2); } } } void main() { int a,i; printf("\t\t*************图的实现算法*****************\n"); printf("\t\t****************************************\n\n"); printf("\t\t\t1:建立图的邻接矩阵\n\n"); printf("\t\t\t2:用prim算法生成的最小生成树为：\n\n"); printf("\t\t\t3:用Dijkstra生成的最短路径\n\n"); printf("\t\t\t4:用Kruskal算法生成的最小生成树为：\n\n"); printf("\t\t\t5:返回\n\n"); printf("\t\t****************************************\n"); printf("\t\t****************************************\n"); printf("\n\t\t输入一个有效的数字,选择你要做的操作:\n"); system("color A"); scanf("%d",&a); switch(a) { case 1: system("cls"); printf("输入数据建立无向图的邻接矩阵"); getin_1(); printf("数据保存成功！\n"); /*flag_1=1; Undigraph();*/ main(); break; HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日 一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。 第10章内部排序习题练习答案 1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。 (1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序 (5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序 上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。 答： (1)直接插入排序:(方括号表示无序区) 初始态: 265[301 751 129 937 863 742 694 076 438] 第一趟：265 301[751 129 937 863 742 694 076 438] 第二趟：265 301 751[129 937 863 742 694 076 438] 第三趟：129 265 301 751[937 863 742 694 076 438] 第四趟：129 265 301 751 937[863 742 694 076 438] 第五趟：129 265 301 751 863 937[742 694 076 438] 第六趟：129 265 301 742 751 863 937[694 076 438] 第七趟：129 265 301 694 742 751 863 937[076 438] 第八趟：076 129 265 301 694 742 751 863 937[438] 第九趟：076 129 265 301 438 694 742 751 863 937 (2)希尔排序(增量为5，3，1) 初始态: 265 301 751 129 937 863 742 694 076 438 第一趟：265 301 694 076 438 863 742 751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 (3)冒泡排序(方括号为无序区) 初始态[265 301 751 129 937 863 742 694 076 438] 第一趟：076 [265 301 751 129 937 863 742 694 438] 第二趟：076 129 [265 301 751 438 937 863 742 694] 第三趟：076 129 265 [301 438 694 751 937 863 742] 第四趟：076 129 265 301 [438 694 742 751 937 863] 第五趟：076 129 265 301 438 [694 742 751 863 937] 第六趟：076 129 265 301 438 694 742 751 863 937 (4)快速排序：（方括号表示无序区，层表示对应的递归树的层数） 成绩评定表 课程设计任务书 算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上，恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。 关键词：分治法，回溯法，棋盘覆盖，数字拆分 1分治法解决期盼覆问题1 1.1问题描述1 1.2问题分析1 1.3算法设计1 1.4算法实现2 1.5结果分析4 1.6算法分析5 2回溯法解决数字拆分问题7 2.1问题描述7 2.2问题分析7 2.3算法设计8 2.4算法实现8 2.5结果分析10 参考文献10 1分治法解决期盼覆问题 1.1问题描述 在一个2k×2k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中出现的位置有4k中情形，因而有4k中不同的棋盘，图（a）所示是k=2时16种棋盘中的一个。棋盘覆盖问题要求用图（b）所示的4中不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且热河亮哥L型骨牌不得重复覆盖 1.2问题分析 用分治策略，可以设计解决棋盘问题的一个简介算法。 当k>0时，可以将2^k*2^k棋盘分割为4个2^k-1*2^k-1子棋盘。由棋盘覆盖问题得知，特殊方格必位于4个较小的子棋盘中，其余3个子棋盘中无特殊方格。为了将3个无特殊方格的子棋盘转化为特殊棋盘可以将一个L型骨牌覆盖这3个较小棋盘的会合处，所以，这3个子棋盘上被L型覆盖的方格就成为给棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘简化为1*1棋盘为止。 。 1.3算法设计 将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是： 左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格 右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格 左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格 吉林财经大学课程设计报告 课程名称：算法课程设计 设计题目：插棒游戏 所在院系：管理科学与信息工程学院计算机科学与技术 指导教师： 职称：副教授 提交时间： 2017年4月 目录 一、题目描述与设计要求 (1) 1 题目描述与设计要求 (1) 二、问题分析 (1) 1 解空间 (1) 2 解空间结构 (2) 3 剪枝 (2) 4 回溯法的基本思想 (2) 5 回溯法的适用条件 (3) 6 回溯法的空间树 (4) 7 回溯法的基本步骤 (4) 三、算法设计 (5) 1 伪代码 (5) 四、复杂性分析 (6) 1 时间复杂度 (6) 2 空间复杂度该 (6) 五、样本测试、分析与总结 (6) 1 样本测试 (6) 2 分析 (7) 2.1、数据类型 (7) 2.2 主要函数思路 (7) 2.3 回溯 (8) 3 总结 (8) 参考文献 (9) 附录 (10) 一、题目描述与设计要求 1 题目描述与设计要求 这个类似谜题的游戏在等边三角形的板上布置了 15 个孔。在初始时候，如下图所示，除了一个孔，所有孔都插上了插棒。一个插棒可以跳过它的直接邻居，移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法，求解该谜题的下列版本： a.已知空孔的位置，求出消去 13 个插棒的最短步骤，对剩下的插棒的最终位置不限。 b.已知空孔的位置，求出消去 13 个插棒的最短步骤，剩下的插棒最终要落在最初的空孔上。 图1 二、问题分析 1 解空间 由于棋盘的对称性，棋盘在变化的过程中会形成多个同构的状态。 例如初始状态时，空孔只有一个，共有15种基本状态。如图2 所示，任意状态与空孔位置在其它的与该空孔颜色相同的点处的状态是同构的，它们可以通过沿中位线翻转和旋转60o 互相转换。也就是说，空孔所在位置的颜色相同的个状态是同构的。如空孔位置在顶点处的三个状态，他们仅通过旋转60o的操作即可互相转换。 数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| 合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第2 学期 课程数据结构与算法 课程设计名称Dijkstra算法的实现 学生姓名张睿辰 学号0804012044 专业班级08计科(2)班 指导教师王昆仑张贯虹 2010 年6月 Dijkstra算法的实现 一、问题分析与任务定义 1、课程设计题目： 1.1题目：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径 的Dijkstra算法 1.2 要求：设计合理的数据结构存储图，简单有效的实现Dijkstra算法。 1.3具体任务：建立图的存储模块，建立图的输出模块，在建图后从单源点开始求最短 路径，并显示出来！ 2、原始数据的输入格式： 2.1建图模块：2.1.1数字 2.2.2数字+空格+数字+空格+数字+回车 2.3显示模块：回车 3、实现功能： 3.1 建立有向图 3.2 显示存储的有向图 3.3 显示从顶点到其他各顶点的最短路径 4、测试用例： 4.1正确数据：a）顶点：3；边值信息：0 1 6；0 2 4；1 2 5；2 0 6；0 0 0； b）顶点：0；边值信息：0 0 0； 输出结果：a) v0到v1的最短路径是6，v0到v2的最短路径是4 b) 没有最短路径 4.2错误数据：a) 顶点：a b）顶点：2；边值信息：0 3 6；0 4 4；13 5；0 0 0； c）顶点：3；边值信息：0 1 a； 输出结果：边值错误，请从新输入 5、问题分析： 实现本程序要解决以下几个问题： 5.1如何存储一个有向图。 5.2如何在界面中输出该有向图。 5.3如何定义起始源点。 5.4如何选择出最短路径。 5.5找到的最短路径如何输出。 二、数据结构的选择和概要设计 1、数据结构的选择： 在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图;另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度数的 常见内部排序算法比较 排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析. 详细设计 1、起泡排序 算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key 成绩评定表 学生姓名吴旭东班级学号1309010236 专业信息与计算 科学课程设计题目 分治法解决棋盘覆 盖问题；回溯法解 决数字拆分问题 评 语 组长签字： 成绩 日期20 年月日 课程设计任务书 学院理学院专业信息与计算科学 学生姓名吴旭东班级学号1309010236 课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题实践教学要求与任务: 要求： 1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。 2．培养学生自学参考书籍，查阅手册、和文献资料的能力。 3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4．了解与课程有关的知识，能正确解释和分析实验结果。 任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1.运用分治算法求解排序问题。 2. 运用回溯算法求解N后问题。 工作计划与进度安排: 第12周：查阅资料。掌握算法设计思想，进行算法设计。 第13周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年月日专业负责人： 201 年月日 学院教学副院长： 201 年月日 算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法 （Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上， 恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。 关键词：分治法，回溯法，棋盘覆盖，数字拆分 算法设计与分析课程设计 实验指导书 上海第二工业大学 计算机与信息学院软件工程系 一、运动员比赛日程表 设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表： ●每个选手必须与其它n-1个选手各赛一次 ●每个选手一天只能赛一次 ●循环赛一共进行n-1天 1、运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机 通过。 输入：运动员人数n（假定n恰好为2的i次方） 输出：比赛日程表A[1..n,1..n] 1. for i←1 to n //设置运动员编号 2. A[i,1]←i 3. end for 4. Calendar(0,n) //位移为0，运动员人数为n。 过程Calendar(v, k) //v表示位移（v=起始行-1），k表示运动员人数。 1. if k=2 then //运动员人数为2个 2. A[v+2,2]←A[v+1,1] //处理右下角 3. A[v+1,2]←A[v+2,1]//处理右上角 4. else 5. Calendar(v,k/2) //假设已制定了v+1至v+k/2运动员循环赛日程表 6. Calendar(v+k/2,k/2) //假设已制定了v+k/2+1至v+k运动员循环赛日程表 7. comment：将2个k/2人组的解，组合成1个k人组的解。 8. for i←1 to k/2 9. for j←1 to k/2 10. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角 11. end for 12. end for 13. for i←k/2+1 to k 14. for j←1 to k/2 15. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角 16. end for 17. end for 18. end if 2、编制该问题的非递归算法，上机通过。 将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。 内部排序算法的实现与 比较 Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT 实验四：内部排序算法的实现与比较 一、问题描述 1．实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 2．基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。 （2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。 （3)对结果作出简要分析。 3．测试数据：随机函数产生。 二、需求分析 1．程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。 2．输入的形式及输入值范围：随机函数产生的N（N=30000）个随机整数。 3．输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。 4．测试数据要求：随机函数产生的N（N=30000）个随机整数。 三、概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能，应以一维数组表示集合数据类型。 int s[N]; int compare[6]={0},move[6]={0},D[N]={0},RS[N]={0}; 基本操作： 数组赋值： for(i=1;i 我国基本比例尺地形图分幅与编号的计算方法 韩丽蓉 (青海大学水电系,青海西宁 810016) 摘要:通过实例探讨了我国基本比例尺地形图分幅与编号的计算方法,此方法可以帮助使用者快速地由某点的经纬度值计算出高斯投影带带号和某比例尺地形图的图幅编号,在测绘工作中具有一定的实用性。 关键词:分幅;编号;六度带;中央子午线经度 中图分类号:K 99 文献标识码:B 文章编号:1006-8996(2006)06-0079-04 1 高斯分带投影 1.1 基本概念 在地理坐标中,经度是以经过英国格林威治天文台的子午面作为起算点(零度),自西向东逆时针至180°为东经,自东向西顺时针从0°至180°为西经,东、西经180°经线是重合的。地图投影是把不可展的 地球椭球体面上的经纬网,按照一定的数学法则转绘到平面上[1,2]。我国的8种国家基本比例尺地形图 (1:1000000～1:5000)中,除了1:1000000万地形图采用国际通用的正轴等角割圆锥投影外,其余7种国家基本比例尺地形图统一采用高斯投影。 高斯投影中限制长度变形的最有效方法是按一定经差将地球椭球面划分成若干投影带,通常投影分为六度带和三度带。分带时既要控制长度变形使其不大于测图误差,又要使带数不致过多以减少换带计算工作。我国1:500000～1:25000的比例尺地形图多采用六度带高斯投影,1:10000～1:5000的地形图采用三度带高斯投影。我国基本比例尺地形图的分幅与编号需要用到某地所在的1:1000000 地形图(经差6° )的中央子午线经度,故需计算该六度带的带号及中央子午线经度。1.2 投影带带号和中央子午线经度的计算方法 1.2.1 六度带 从格林威治零度经线起,每隔经差6°分为一个投影带,自西向东逆时针分带,全球依次编号为1,2, 3,……60,每带中间的子午线称为中央子午线[1,2]。 东半球从经度0°逆时针回算到东、西经180°,投影带号为1～30。假如知道东半球某地区的平均大地经度L 东,则其投影带带号M 东和中央子午线经度L 6东的计算公式为: M 东=[L 东Π6](取整数商)+1(有余数时);L 6东=(6M 东-3)° (东经)西半球投影带从东、西经180°逆时针回算到0°,投影带号为31～60,假如知道西半球某地区的平均大地经度L 西,则其投影带带号M 西和中央子午线经度L 6西的计算公式为: M 西=[(360°-L 西)Π6](取整数商)+1(有余数时)=[(180°-L 西)Π6](取整数商)+1(有余数时)+30;L 6西={360°-(6M 西-3)°}(西经) 1.2.2 三度带 自东经115°子午线起,每隔经差3°自西向东分带,依次编号为1,2,3,……120[1,2] 。 东半球有60个投影带,编号为1～60,假如知道东半球某地区的平均大地经度L 东,其投影带带号N 东和中央子午线经度L 3东的计算公式为: 收稿日期:2006-07-10 作者简介:韩丽蓉(1967—),女,撒拉族,青海循化人,副教授,硕士。第24卷 第6期2006年12月 青海大学学报(自然科学版)Journal of Qinghai University (Nature Science ) Vol 124No 16Dec 12006 实验四：内部排序算法的实现与比较 一、问题描述 1．实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。2．基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。 （2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。 （3)对结果作出简要分析。 3．测试数据：随机函数产生。 二、需求分析 1．程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。 2．输入的形式及输入值范围：随机函数产生的N（N=30000）个随机整数。 3．输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。 4．测试数据要求：随机函数产生的N（N=30000）个随机整数。 三、概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能，应以一维数组表示集合数据类型。 int s[N]; int compare[6]={0},move[6]={0},D[N]={0},RS[N]={0}; 基本操作： 数组赋值： for(i=1;i 电力系统分析课程设计-电力系统短路故障的计算机算法程序设计 ————————————————————————————————作者：————————————————————————————————日期： 电力系统分析课程设计 电力系统短路故障的计算机算法程序设计 姓名____刘佳琪___ 学号_2014409436__ 班级__20144094___ 指导教师___鲁明芳____ 目录 1 目的与原理 (1) 1.2 关于电力系统短路故障的计算机算法程序设计目的 (1) 1.2 设计原理 (1) 1.2.1计算机计算原理 (1) 1.2.2电力系统短路计算计算机算法 (2) 2 计算机编程环境及编程语言的选择 (2) 2.1 优势特点 (2) 2.1.1编程环境 (3) 2.1.2简单易用 (3) 2.1.3强处理能力 (3) 2.1.4图形处理 (3) 2.1.5模块集和工具箱 (4) 2.1.6程序接口 (4) 2.1.7应用软件开发 (4) 3 对称故障的计算机算法 (5) 3.1 用阻抗矩阵计算三相短路电流 (7) 3.2 用节点导纳矩阵计算三相短路电流 (9) 4 附录程序清单 (14) 4.1 形成节点导纳矩阵 (14) 4.2 形成节点阻抗矩阵 (15) 4.2 对称故障的计算 (17) 1 目的与原理 1.1 关于电力系统短路故障的计算机算法程序设计目的 电力系统正常运行的破坏多半是由于短路故障引起的，发生短路时，系统从一种状态剧变成另一种状态，并伴随复杂的暂态现象。所谓短路故障，是指一切不正常的相与相之间或相与地发生通路的情况。 本文根据电力系统三相对称短路的特点，建立了合理的三相短路的数学模型，在此基础上，形成电力系统短路电流实用计算方法；节点阻抗矩阵的支路追加法。编制了对任意一个电力系统在任意点发生短路故障时三相短路电流及其分布的通用计算程序，该办法适用于各种复杂结构的电力系统。从一个侧面展示了计算机应用于电力系统的广阔前景。 根据所给的电力系统，编制短路电流计算程序，通过计算机进行调试，最后完成一个切实可行的电力系统计算应用程序。通过自己设计电力系统计算程序使同学对电力系统分析有进一步理解，同时加强计算机实际应用能力的训练。 电力系统的短路故障是严重的，而又是发生几率最多的故障，一般说来，最严重的短路是三相短路。当发生短路时，其短路电流可达数万安以至十几万安，它们所产生的热效应和电动力效应将使电气设备遭受严重破环。为此，当发生短路时，继电保护装置必须迅速切除故障线路，以避免故障部分继续遭受危害，并使非故障部分从不正常运行情况下解脱出来，这要求电气设备必须有足够的机械强度和热稳定度，开关电气设备必须具备足够的开断能力，即必须经得起可能最大短路的侵扰而不致损坏。因此，电力系统短路电流计算是电力系统运行分析，设计计算的重要环节，许多电业设计单位和个人倾注极大精力从事这一工作的研究。由于电力系统结构复杂，随着生产发展，技术进步系统日趋扩大和复杂化，短路电流计算工作量也随之增大，采用计算机辅助计算势在并行。 1.2 设计原理 1.2.1 计算机计算原理 应用计算机进行电力系统计算，首先要掌握电力系统相应计算的数学模型；其次是运用合理的计算方法；第三则是选择合适的计算机语言编制计算程序。 建立电力系统计算的相关数学模型，就是建立用于描述电力系统相应计算的有关参数间的相互关系的数学方程式。该数学模型的建立往往要突出问题的主要方，即考虑影 课题：内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| （3.1） （II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| XXXX大学 算法设计与分析课程设计报告 院（系）： 年级： 姓名： 专业：计算机科学与技术 研究方向：互联网与网络技术 指导教师： X X X X 大学 目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (8) 题目2 切割木材 (10) 2.1题目描述 (10) 2.2算法文字描述 (10) 2.3算法程序流程 (11) 2.4算法的程序实现代码 (15) 题目3 设计题 (17) 3.1题目描述 (17) 3.2 输入要求 (17) 3.3输出要求 (17) 3.4样例输入 (17) 3.5样例输出 (17) 3.6测试样例输入 (17) 3.7测试样例输出 (18) 3.8算法实现的文字描述 (18) 3.9算法程序流程 (19) 3.10算法的程序实现代码 (20) 算法分析与设计课程总结 (23) 参考文献 (24) 题目1 电梯调度 1.1 题目描述 一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为4 5 10（有三位乘客，他们分别想去4楼、5楼和10楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4*9+2*10=56秒，则最后一位乘客到达办公室的时间为56秒，相应的停靠计划为4 5 10均停靠。对于此测试用例电梯停靠计划方案：4 10，这样到第4楼的乘客所需时间为3*4=12秒，到第5楼的乘客所需时间为3*4+20=32秒，到第10楼的乘客所需时间为9*4+10=46秒，即最后到达目的楼层的顾客所需时间为46秒。 输入要求： 输入的第1行为整数n f1 f2 … fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1 f2 … fn表示需要停靠的楼层（n<=30，2<=f1 八大排序算法 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 基本思想: 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。 直接插入排序示例： 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 算法的实现： [cpp]view plaincopyprint? 1.void print(int a[], int n ,int i){ 2. cout< 目录 1、问题描述： (2) 1.1题目内容: (2) 1.2基本要求: (2) 1.3测试数据: (2) 2、需求分析： (2) 2.1程序的基本功能: (2) 2.2输入值、输出值以及输入输出形式: (2) 2.3各个模块的功能要求： (2) 3、概要设计： (3) 3.1所需的ADT，每个程序中使用的存储结构设计说明 (3) 3.2主程序流程以及模块调用关系 (3) 3.3每个模块的算法设计说明（流程图） (4) 3.3.1气泡排序： (4) 3.3.2直插排序 (5) 3.3.3选择排序 (6) 3.3.4希尔排序 (7) 3.3.5快速排序 (8) 4、详细设计： (9) 4.1函数调用关系图 (9) 5、各个算法实现的源程序： (9) 5.1、冒泡排序及其主要算法 (9) 5.2、直接插入排序及其主要算法 (10) 5.3、选择排序及其主要算法 (10) 5.4、希尔排序及其主要算法 (11) 6、调试分析： (12) 7、使用说明： (13) 8、测试结果： (14) 9、主要参考文献 (14) 1、问题描述： 1.1题目内容: 内部排序算法实现与性能分析 1.2基本要求: （1）数据结构定义 （2）利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、希尔等排序方法进行排序，并统计每一种排序上机所花费的时间,对各种排序算法做分析比较. 1.3测试数据: 由函数随机产生的数据，由于是随机产生的，所以在此不一一写出。 2、需求分析： 2.1程序的基本功能: 输入30000个随机整数，对这些数进行多种方法进行排序，并对这些排序做比较，在屏幕上输出每种排序方法所比较的次数，交换的次数，和时间复杂度。 2.2输入值、输出值以及输入输出形式: 由于程序中所需的数据都是有函数随机生成的整形数，不需要用户自己输入，用户只需要对演示程序中的一些提示做一些必要的选择以便于程序的执行。 程序输出的是对六种排序做的一些比较，即输出六种排序各排序过程中所比较的数据的个数，交换的数据的次数，和排序完成所用的时间。六种排序依次在计算机终端上显示，便于用户观察。 2.3各个模块的功能要求： 一、随机函数：产生随机数 二、选择排序函数：对随机数进行选择排序 三、起泡排序函数：对随机数进行气泡排序 四、直接插入函数：对随机数进行直接插入排序 五、希尔排序函数：对随机数进行希尔排序 六、快速排序函数：对随机数进行快速排序 七、主函数 宝鸡文理学院 课程设计 题目：基于MATLAB的电炉温度控制算法比较及仿真研究 系别：电子电气工程系 班级：2010级电气3班 姓名：陈亚杰 学号：201095014094 指导教师：梁绒香 2013年5月 目录 一、研究对象分析说明 (2) 二、PID算法的设计及分析 (4) 1、算法简介 (4) 2、数学模型的建立 (5) 3、simulink仿真连接图 (8) 4、Matlab仿真曲线图…………………………………………………………,8 三、施密斯（Smith）预估控制算法的分析与设计 (11) 1、施密斯预估控制原理 (11) 2、具有纯滞后补偿的数字控制 (12) 3、施密斯预估器设计 (13) 4、采用simulink系统仿真 (15) 5、使用Matlab仿真被控对象 (15) 四、达林（Dahlin）控制算法的分析与设计 (17) 1、算法简介 (17) 2、算法具体设计 (17) 3.simulink仿真连接图 (19) 4、使用Matlab仿真被控对象 (19) 5、振铃现象 (20) 五、大林算法、PID算法、Smith预估控制算法三种算法比较 (22) 六、设计小节与心得体会 (23) 七、参考文献 (24) 一、研究对象分析说明 该设计电炉温度控制对象的控制模型为s e s s W 22011 )(-+= ，是一阶惯性加滞后模型，被控对象的纯滞后时间τ使系统的稳定性降低，动态性能变坏，如容易引起超调和持续的振荡。对象的纯滞后特性给控制器的设计带来困难。一般的，当对象的滞后时间τ与对象的惯性时间常数T m 之比超过0.5时，采用常规的控制算法很难获得良好的控制性能。因此，具有纯滞后特性对象属于比较难以控制的一类对象，对其控制需要采用特殊的处理方法。此外，系统要求： 1. 炉温变化范围：0—200℃，要求实现80℃温度的恒温控制； 2.炉温变化参数要求： S t ≤80S ；超调量p σ≤10℅；静态误差 v e ≤2℃。 现对该系统控制算法进行设计。算法设计与分析课程设计(完整版)
中南大学数据结构与算法第10章内部排序课后作业答案
计算机算法设计及分析课程设计报告
算法课程设计资料
数据结构课程设计(内部排序算法比较_C语言)
Dijkstra算法的实现-数据结构与算法课程设计报告
几种常见内部排序算法比较
计算机算法设计与分析课程设计.
算法设计与分析课程设计-实验指导书
内部排序算法的实现与比较
新旧图幅编号
内部排序算法的实现与比较
电力系统分析课程设计-电力系统短路故障的计算机算法程序设计
数据结构课程设计(内部排序算法比较 C语言)
算法分析资料报告与设计-课程设计资料报告材料
八大排序算法
内部排序算法实现与性能分析课程设计.
计算机课程设计.
相关主题
文本预览