一键复制
在日常的学习、工作、生活中，肯定对各类范文都很熟悉吧。写范文的时候需要注意什么呢？有哪些格式需要注意呢？下面是小编为大家收集的优秀范文，供大家参考借鉴，希望可以帮助到有需要的朋友。
数据结构课程设计快速排序 数据结构课程设计排序算法比较篇一
一、实验目的
1、熟练掌握二叉排序树查找算法及c语言描述。
2、熟练掌握折半查找算法及c语言描述。
3、熟练掌握简单选择排序算法及c语言描述。
4、熟练掌握简单插入排序算法及c语言描述。
5、熟练掌握冒泡（起泡）排序算法及c语言描述。
6、了解各种查找及排序算法的优缺点、实用性及应用。
7、将理论与实际相结合，切实提高自己的逻辑能力和动手能力。
二、设计内容
1.折半查找算法
折半查找算法的思路：
初始状态：假设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值，初始时，令low=0,high=n-1,mid=(low+high)/2 让key与mid指向的记录比较
若key==r[mid].key，查找成功,算法结束；若key
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即l.r[1].key>l.r[2].key），则将两个记录交换之，然后比较【第二个记录和第三个记录】的关键字。以此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称做第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。一般地，第i躺起泡排序是从l.r[1]到l.r[n-i+1]以此比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程需进行k(1<=k 首先以一个元素为基准，从一个方向开始扫描，比如从左至右扫描，以a[0]为基准，接下来从a[0]...a[9] 中找出最小的元素，将其与a[0]交换，然后将基准位置右 移一位，重复上面的动作，比如，以a[1]为基准，找出a[1]至a[9]中最小的，将其与a[1]交换，一直进行到基准位置移到数组最后一个元素时排序结束（此时基准左边所有元素均递增有序，而基准为最后一个元素，故完成排序）。4.直接插入排序算法 直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的，记录数增1的有序表。 一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r[1...i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1....i].在自i-1起往前搜索的过程中，可以同时后移记录。 整个排序过程为进行n-1躺插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止 三、程序源代码 1.二叉排序树的创建、遍历和查找删除算法 #include if(!t){ t=new lnode;t->data=key;t->lchild=t->rchild=null;} else } { } if(key } insert(t,num);c=getchar();if(c=='n')return;void in_order(tree t)//中序遍历 { if(t){ in_order(t->lchild);printf(“%d ”,t->data);} in_order(t->rchild);} void delete(tree &p){ tree q,s;if(!p->rchild){ q = p;p=p->lchild;free(q);} else if(!p->lchild){ } q = p;p=p->rchild;free(q); else { } q = p;s = p->lchild;while(s->rchild){ } q = s;s = s->rchild;p->data = s->data;if(q!=p)q->rchild = s->lchild;else q->lchild = s->lchild;free(s);} void delnode(tree &t,keytype key){ } if(!t){ printf(“n该结点不存在n”);return;} else { } if(key == t->data)delete(t);else if(key < t->data)delnode(t->lchild, key);else delnode(t->rchild,key);tree search(tree t,keytype key)//二叉排序树查找 { if(!t){ } printf(“该结点不存在”);return 0;else if(key == t->data)return t;else if(key < t->data) return(search(t->lchild, key));else return(search(t->rchild, key));} int main()//主函数 { tree t,p;t=null;keytype x; printf(“请输入二叉树各结点：n”); creattree(t); printf(“中序遍历为：n”);in_order(t);printf(“n请输入要查找和删除的结点：n”);scanf(“%d”,&x);p=search(t, x);if(p){ } delnode(t, x);printf(“中序遍历为：n”);in_order(t); } 2、冒泡排序和折半查找算法 #include int i,t,j;for(i=0;i<9;i++){ } for(j=0;j<9-i;j++){ } if(c[j]>c[j+1]){ } t=c[j];c[j]=c[j+1];c[j+1]=t; printf(“n您所输入的数字的升序排列是:nn”);for(i=0;i<10;i++){ printf(“%d”,c[i]);printf(“ ”);} return 1;} //折半查找 int binarysearch(int b[]){ } int t,mid;int i=0;int j=9;printf(“nn请输入您要查找的数字：”);scanf(“%d”, &t);while(i<=j){ mid=i+(j-i)/2; } return 1;if(t==b[mid]){ printf(“n您要查找的数字的排列位置是：%dn”,mid+1);break;} else if(t int main(int argc,char *argv[]){ int a[10];printf(“请您输入数据:nn”);for(int i=0;i<10;i++){ scanf(“%d”,&a[i]); } } bubblesort(a);binarysearch(a);return 0; 3、简单选择排序和简单插入排序算法 #include for(i=0;i { key=0; min=a[i]; } for(j=i;j if(a[j] if(key==1){a[p]=a[i]; a[i]=min;} for(k=0;k printf(“%d ”,a[k]);printf(“n”); return 1;} int insersort(int*a,int n){ int i,j,k;for(i=2;i<=n;i++){ a[0]=a[i];for(j=1;j { if(a[j]>a[i]){for(k=i;k>j;k--) a[k]=a[k-1]; a[k]=a[0]; } } break;} } for(j=1;j<=n;j++){ } printf(“%d ”,a[j]);printf(“n”);return 1;int main(){ int a[80],i,n,b;printf(“请输入关键字的个数：”);scanf(“%d”,&n);printf(“排序类型：n”);printf(“1.选择排序n”);printf(“2.插入排序n”);printf(“请选择：”);scanf(“%d”,&b);switch(b){ case 1: printf(“请输入关键字：n”);for(i=0;i selectionsort(a,n); return 1; break; case 2: printf(“请输入关键字：n”); for(i=1;i<=n;i++){ scanf(“%d”,&a[i]);} printf(“插入排序的流程以及结果：n”); insersort(a,n);return 1; } break;}while(a!=0); 四、实验运行结果 1.二叉排序树的创建、遍历和查找删除算法 2、冒泡排序和折半查找算法 3、简单选择排序和简单插入排序算法 七、心得体会 通过本次的数据结构课程设计报告，掌握了查找和排序的几种基本排序算法，了解了他们各自的特点和优缺点，完成了对于他们c语言的描述和实际应用，对他们有了一个更加具体、深刻的认识，同时也锻炼了我们的逻辑思维能力和动手实践能力，使我们受益匪浅，给我们今后的计算机专业课程学习带来很大的帮助。 数据结构课程设计 1.赫夫曼编码器 设计一个利用赫夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。要求： 1)将权值数据存放在数据文件(文件名为，位于执行程序的当前目录中) 2)初始化：键盘输入字符集大小26、26个字符和26个权值（统计一篇英文文章中26个字母），建立哈夫曼树； 3)编码：利用建好的哈夫曼树生成哈夫曼编码； 4)输出编码（首先实现屏幕输出，然后实现文件输出）； 5)界面优化设计。 代码如下： #include //结构体 { int weight; char ch;int parent,lchild,rchild;}htnode;typedef char * * hcode; void save(int n,htnode *ht) //把权值保存到文件 { file * fp; int i; if((fp=fopen(“”,“wb”))==null) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&ht[i].weight,sizeof(struct htnode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void create_h(int n,int m,htnode *ht) //建立赫夫曼树，进行编码 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n请输入权值和字符(用空格隔开): ”); scanf(“%d”,&w); scanf(“ %c”,&c);ht[k].ch=c; ht[k].weight=w; } else ht[k].weight=0; ht[k].parent=ht[k].lchild=ht[k].rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(ht[j].parent==0) { if(ht[j].weight { w2=w1;p2=p1; w1=ht[j].weight; p1=j; } else if(ht[j].weight { w2=ht[j].weight; p2=j; } } } ht[k].lchild=p1;ht[k].rchild=p2;ht[k].weight=ht[p1].weight+ht[p2].weight; ht[p1].parent=k;ht[p2].parent=k; } printf(“输入成功！”);} void coding_h(int n,htnode *ht) //对结点进行译码 { int k,sp,fp,p;char *cd;hcode hc; hc=(hcode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]=''; printf(“************************n”);printf(“char codingn”); for(k=1;k<=n;k++) { sp=n-1;p=k;fp=ht[k].parent; for(;fp!=0;p=fp,fp=ht[fp].parent) if(ht[fp].lchild==p) cd[--sp]='0'; else cd[--sp]='1'; hc[k]=(char *)malloc((n-sp)*sizeof(char)); strcpy(hc[k],&cd[sp]); printf(“%c %sn”,ht[k].ch,hc[k]); } printf(“************************n”);free(cd);} void read(int n,htnode *ht) //从文件中读出数据 { int i;file * fp;if((fp=fopen(“”,“rb”))==null){ printf(“cannot open filen”); exit(0);} for(i=0;i fread(&ht[i].weight,sizeof(struct htnode),1,fp);// printf(“%d n”,ht[i].weight); } coding_h(n,ht); fclose(fp);} void print_h(int m,htnode *ht) //输出赫夫曼造树过程 { int k;printf(“************************n”);printf(“num weight par lch rch n”);for(k=1;k<=m;k++){ printf(“%d ”,k); printf(“ %d”,ht[k].weight); printf(“ %d”,ht[k].parent); printf(“ %d”,ht[k].lchild); printf(“ %dn”,ht[k].rchild); } printf(“************************n”);} void decode(int m,htnode *ht) //对输入的电文进行译码 { int i,j=0;char a[10];char endflag='2';i=m;printf(“输入发送的编码，以‘2’结束:”);scanf(“%s”,&a);printf(“译码后的字符：”);while(a[j]!='2'){ if(a[j]=='0') i=ht[i].lchild; else i=ht[i].rchild; if(ht[i].lchild==0) //ht[i]是叶结点 { printf(“%c”,ht[i].ch); i=m; //回到根结点 } j++;} printf(“n”);if(ht[i].lchild!=0&&a[j]!='2') printf(“error”);} int main() //主函数 { int n,m,c;htnode ht[n];do { system(“color 2f”); //(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 赫夫曼编译码系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入权值、字母nttt2.把数据写入文件nttt3.输出赫夫曼编码表nttt”); printf(“6.从文件中读出数据nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);printf(“输入多少结点:”); scanf(“%d”,&n);m=2*n-1;create_h(n,m,ht);break; case 2:system(“cls”);save(n,ht);break; case 3:system(“cls”);print_h(m,ht);break; case 4:system(“cls”);coding_h(n,ht);break; case 5:system(“cls”);decode(m,ht);break; case 6:system(“cls”);read(n,ht);break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 2.学生成绩管理（链表实现）要求： 实现如下功能：增加、查找、删除、输出、退出。 代码如下： #include char number[20];char name[20];char chinese[20];char english[20];char math[20];}score;typedef struct node_score //定义成绩信息链表结点，包括数据域和指针域 { score data;struct node_score *next;}node_score,*p_node_score;p_node_score headscore;//定义链表的头指针为全局变量 void printscore(score s)//输出信息函数 { printf(“ %10s”,);printf(“ | %-6s”,);printf(“ | %-3s”,e);printf(“ | %-3s”,h); printf(“ | %-3sn”,);} void view()//输出函数 { p_node_score pnodescore; pnodescore=headscore;printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”);while(pnodescore!= null){ printscore(pnodescore->data);//输出学生信息和成绩信息 pnodescore=pnodescore->next;} } void add(){ p_node_score pnodescore;// 定义一个节点 pnodescore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间 printf(“请输入学号：”);scanf(“%s”,pnodescore->);printf(“请输入姓名：”);scanf(“%s”,pnodescore->);printf(“请输入语文成绩：”);scanf(“%s”,pnodescore->e);printf(“请输入英语成绩：”);scanf(“%s”,pnodescore->h);printf(“请输入高数成绩：”);scanf(“%s”,pnodescore->);if(headscore==null){ //如果头结点为空 headscore=pnodescore; pnodescore->next=null;} else { //如果头结点不为空 pnodescore->next=headscore; headscore=pnodescore;//将头结点新结点 } } void input(){ int n,i;printf(“输入几个学生的数据：”);scanf(“%d”,&n);for(i=0;i add();printf(“输入成功！”);} int delete(){ p_node_score pnodescore,p1;//p1为pnodescore的前驱 p1=headscore;if(p1==null){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char deletenumber[20]; printf(“请数入要删除的学生学号:”);scanf(“%s”,deletenumber);if(strcmp(p1->,deletenumber)==0) { //如果要删除的结点在第一个 headscore=p1->next; pnodescore=p1; printf(“学号为%s的学生信息已经删除！n”,deletenumber); return 0;} else { pnodescore=p1->next; while(pnodescore!=null) { if(strcmp(pnodescore->,deletenumber)==0) { p1->next=pnodescore->next; printf(“学号为%s的学生信息已经删除！n”,deletenumber); return 0; } else { //否则，结点向下一个，p1仍为pnodescore的前驱 p1=pnodescore; pnodescore=pnodescore->next; } } } printf(“没有此学号的学生！”);} int change(){ p_node_score pnodescore; pnodescore=headscore;if(pnodescore==null){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char editnumber[20];printf(“请输入你要修改的学生学号：”);scanf(“%s”,editnumber);while(pnodescore!=null){ if(strcmp(pnodescore->,editnumber)==0) { //用strcmp比较两字符串是否相等，相等则返回0 printf(“原来的学生成绩信息如下：n”);//输出原来的成绩信息 printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); printscore(pnodescore->data); printf(“语文新成绩:”); scanf(“%s”,pnodescore->e); printf(“英语新成绩:”); scanf(“%s”,pnodescore->h); printf(“高数新成绩:”); scanf(“%s”,pnodescore->); printf(“成绩已经修改！”); return 0; } pnodescore=pnodescore->next;//如果不相等，pnodescore则指向下一个结点 } printf(“没有此学号的学生！n”);//如果找到最后都没有，则输出没有此学号的学生 } int find(){ p_node_score pnodescore; pnodescore=headscore;if(pnodescore==null){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char findnumber[20];printf(“请输入你要查找的学生学号：”);scanf(“%s”,findnumber);while(pnodescore!=null){ if(strcmp(pnodescore->,findnumber)==0) { printf(“你要查找的学生成绩信息如下：n”); printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); printscore(pnodescore->data); return 0; } pnodescore=pnodescore->next;} printf(“没有此学号的学生！n”);} int main() //主函数 { int choice=0;headscore=null;int c;do { system(“color 2f”); //(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 学生成绩管理系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入成绩信息nttt2.输出成绩信息nttt3.添加成绩信息nttt”); printf(“4.修改成绩信息nttt5.删除成绩信息nttt6.查询成绩信息nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);input();break; case 2:system(“cls”);view();break; case 3:system(“cls”);add();break; case 4:system(“cls”);change();break; case 5:system(“cls”);delete();break; case 6:system(“cls”);find();break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 数 据 结 构 课程设计报告 题 目： 一元多项式计算 专 业： 信息管理与信息系统 班 级： 2012级普本班 学 号： 201201011367 姓 名： 左帅帅 指导老师： 郝慎学 时 间： 一、课程设计题目分析 本课程设计要求利用c语言或c++编写，本程序实现了一元多项式的加法、减法、乘法、除法运算等功能。 二、设计思路 本程序采用c语言来完成课程设计。 1、首先，利用顺序存储结构来构造两个存储多项式a(x)和 b(x)的结构。 2、然后把输入，加，减，乘，除运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块。 3、然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能，尽量减少程序运行时错误的出现。 4、最后编写main()主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。 三、设计算法分析 1、相关函数说明： (1)定义数据结构类型为线性表的链式存储结构类型变量 typedef struct polynomial{} (2)其他功能函数 插入函数void insert(polyn p,polyn h) 比较函数int compare(polyn a,polyn b) 建立一元多项式函数polyn create(polyn head,int m) 求解并建立多项式a+b，polyn add(polyn pa,polyn pb) 求解并建立多项式a-b，polyn subtract(polyn pa,polyn pb)2 求解并建立多项式a*b，polyn multiply(polyn pa,polyn pb) 求解并建立多项式a/b，void device(polyn pa,polyn pb) 输出函数输出多项式，void print(polyn p) 销毁多项式函数释放内存，void destroy(polyn p) 主函数，void main（） 2、主程序的流程基函数调用说明(1)typedef struct polynomial { float coef; int expn; struct polynomial *next;} *polyn,polynomial; 在这个结构体变量中coef表示每一项前的系数，expn表示每一项的指数，polyn为结点指针类型，属于抽象数据类型通常由用户自行定义，polynomial表示的是结构体中的数据对象名。 (2)当用户输入两个一元多项式的系数和指数后，建立链表，存储这两个多项式，主要说明如下： polyn createpolyn(polyn head,int m)建立一个头指针为head、项数为m的一元多项式 p=head=(polyn)malloc(sizeof(struct polynomial));为输入的多项式申请足够的存储空间 p=(polyn)malloc(sizeof(struct polynomial));建立新结点以接收数据 insert(p,head);调用insert函数插入结点 这就建立一元多项式的关键步骤 (3)由于多项式的系数和指数都是随即输入的，所以根据要求需要对多项式按指数进行降幂排序。在这个程序模块中，使用链表，根据对指数大小的比较，对各种情况进行处理，此处由于反复使用指针对各个结点进行定位，找到合适的位置再利用void insert(polyn p,polyn h)进行插入操作。(4)加、减、乘、除、的算法实现： 在该程序中，最关键的一步是实现四则运算和输出，由于加减算法原则是一样，减法可通过系数为负的加法实现；对于乘除算法的大致流程都是：首先建立多项式a*b，a/b，然后使用链表存储所求出的乘积，商和余数。这就实现了多项式计算模块的主要功能。 (5)另一个子函数是输出函数 printpolyn（）； 输出最终的结果，算法是将最后计算合并的链表逐个结点依次输出，便得到整链表，也就是最后的计算式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理。 四、程序新点 通过多次写程序，发现在程序在控制台运行时总是黑色的，本次写程序就想着改变一下，于是经过查资料利用system(“color e0”);可以函数解决，这里“e0，”e是控制台背景颜色，0是控制台输出字体颜色。 五、设计中遇到的问题及解决办法 首先是，由于此次课程设计里使用指针使用比较多，自己在指针多的时候易脑子混乱出错，对于此问题我是采取比较笨的办法在稿纸上写明白后开始进行 4 代码编写。 其次是，在写除法模块时比较复杂，自己通过查资料最后成功写出除法模块功能。 最后是，前期分析不足开始急于写代码，中途出现各种问题，算是给自己以后设计时的一个经验吧。 六、测试（程序截图） 1.数据输入及主菜单 2.加法和减法模块 3.乘法和除法模块 七、总结 通过本次应用c语言设计一元多项式基本计算程序，使我更加巩固了c语言程序设计的知识，以前对指针这一点使用是比较模糊，现在通过此次课程设计对指针理解的比较深刻了。而且对于数据结构的相关算法和函数的调用方面知识的加深。本次的课程设计，一方面提高了自己独立思考处理问题的能力；另一方面使自己再设计开发程序方面有了一定的小经验和想法，对自己以后学习其他语言程序设计奠定了一定的基础。 八、指导老师评语及成绩 附录：（课程设计代码） #include int expn; struct polynomial *next;} *polyn,polynomial; //polyn为结点指针类型 void insert(polyn p,polyn h){ if(p->coef==0)free(p); //系数为0的话释放结点 else { polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//将指数相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系数为0的话释放结点 { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指数为新时将结点插入 } 7 } //建立一个头指针为head、项数为m的一元多项式 polyn create(polyn head,int m){ int i; polyn p; p=head=(polyn)malloc(sizeof(struct polynomial)); head->next=null; for(i=0;i { p=(polyn)malloc(sizeof(struct polynomial));//建立新结点以接收数据 printf(“请输入第%d项的系数与指数:”,i+1); scanf(“%f %d”,&p->coef,&p->expn); insert(p,head); //调用insert函数插入结点 } return head;} //销毁多项式p void destroy(polyn p){ polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指针后移 q2=q2->next; } } //输出多项式p int print(polyn p){ polyn q=p->next; int flag=1;//项数计数器 if(!q)//若多项式为空，输出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项 9 if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况 { printf(“%g”,q->coef); if(q->expn==1)putchar('x'); else if(q->expn)printf(“x^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('x'); else printf(“x^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-x”); else printf(“-x^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(polyn a,polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn } else if(!a&&b)return-1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空 } //求解并建立多项式a+b，返回其头指针 polyn add(polyn pa,polyn pb){ polyn qa=pa->next; polyn qb=pb->next; polyn headc,hc,qc; hc=(polyn)malloc(sizeof(struct polynomial));//建立头结点 11 hc->next=null; headc=hc; while(qa||qb){ qc=(polyn)malloc(sizeof(struct polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//当相加系数为0时，释放该结点 } return headc;} //求解并建立多项式a-b，返回其头指针 polyn subtract(polyn pa,polyn pb){ polyn h=pb; polyn p=pb->next; polyn pd; while(p)//将pb的系数取反 { p->coef*=-1;p=p->next;} pd=add(pa,h); for(p=h->next;p;p=p->next) //恢复pb的系数 p->coef*=-1;13 return pd;} //求解并建立多项式a*b，返回其头指针 polyn multiply(polyn pa,polyn pb){ polyn hf,pf; polyn qa=pa->next; polyn qb=pb->next; hf=(polyn)malloc(sizeof(struct polynomial));//建立头结点 hf->next=null; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(polyn)malloc(sizeof(struct polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; insert(pf,hf);//调用insert函数以合并指数相同的项 } } return hf;} //求解并建立多项式a/b，返回其头指针 void device(polyn pa,polyn pb){ polyn hf,pf,temp1,temp2; polyn qa=pa->next; polyn qb=pb->next; hf=(polyn)malloc(sizeof(struct polynomial));//建立头结点,存储商 hf->next=null; pf=(polyn)malloc(sizeof(struct polynomial));//建立头结点，存储余数 pf->next=null; temp1=(polyn)malloc(sizeof(struct polynomial)); temp1->next=null; temp2=(polyn)malloc(sizeof(struct polynomial)); temp2->next=null; temp1=add(temp1,pa); while(qa!=null&&qa->expn>=qb->expn) { temp2->next=(polyn)malloc(sizeof(struct polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); insert(temp2->next,hf); pa=subtract(pa,multiply(pb,temp2));15 qa=pa->next; temp2->next=null; } pf=subtract(temp1,multiply(hf,pb)); pb=temp1; printf(“商是:”); print(hf); printf(“余数是:”); print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“color e0”);polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值null printf(“请输入a(x)的项数:”);scanf(“%d”,&m);printf(“n”);pa=create(pa,m);//建立多项式a printf(“n”);printf(“请输入b(x)的项数:”);16 scanf(“%d”,&n);printf(“n”);pb=create(pb,n);//建立多项式b printf(“n”);printf(“**********************************************n”);printf(“* 多项式操作菜单 printf(”**********************************************n“);printf(”tt 1.输出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.减法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”执行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多项式a(x):“);print(pa);*n”); printf(“多项式b(x):”);print(pb); break; case 2: pc=add(pa,pb); printf(“多项式a(x)+b(x):”);print(pc); destroy(pc);break; case 3: pd=subtract(pa,pb); printf(“多项式a(x)-b(x):”);print(pd); destroy(pd);break; case 4: pf=multiply(pa,pb); printf(“多项式a(x)*b(x):”); print(pf); destroy(pf); break; case 5: device(pa,pb);18 break; case 6: exit(0); break; } } destroy(pa); destroy(pb);} 综合课程设计1 ——《数据结构课程设计》教学大纲 一、课程的性质、教学目的和要求 《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能 二、设计要点 1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。 3、本次课程设计按照教学要求需要独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时地向指导教师汇报。 4、编程语言任选。 三、设计题目 1、集合的并、交和算差运 任务：编制一个能演示执行集合的并、交和差运算的程序。要求:(1)集合的元素限定为小写字母字符 [‘a’..’z’]。(2)演示程序以用户和计算机的对话方式执行。实现提示:以链表表示集合。 选作内容:(1)集合的元素判定和子集判定运算。 (2)求集合的补集。 (3)集合的混合运算表达式求值。 (4)集合的元素类型推广到其他类型，甚至任意类型。 2、停车场管理 任务：设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 要求：以栈模拟停车场，以队列模拟车场外的便道。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停车不收费）。栈以顺序存储结构实现，队列以链表结构实现。 3、哈夫曼码的编/译码系统 【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【基本要求】一个完整的系统应具有以下功能： （1）i:初始化（initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree中。 （2）e:编码（encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetran中的正文进行编码，然后将结果存入文件codefile中。（3）d:译码（decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。 （4）p:打印代码文件（print）。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codeprin中。 （5）t:打印哈夫曼树（tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。【测试数据】 （1）利用下面这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。 （2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“this program is my favorite”。 字符 空格 a b c d e f g h i j k l m 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 n o p q r s t u v w x y z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【实现提示】 （1）编码结果以文本方式存储在文件codefile中。 （2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“q”，表示退出运行quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“q”为止。 （3）在程序的一次执行过程中，第一次执行i，d或e命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行i命令，因为文件hfmtree可能早已建好。 4、校园导游咨询 任务：设计一个校园导游程序，为来访的客人提供各种信息查询服务。 要求： （1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2）为来访客人提供图中任意景点相关信息的查询。 （3）为来访客人提供景点的问路查询，即已知一个景点，查询到某景点之间的一条最短路径及长度。 5、散列表的设计与实现 任务：设计散列表实现电话号码查找系统。要求： （1）设每个记录有下列数据项：用户名、电话号码、地址； 2（2）从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表；（3）采用一定的方法解决冲突； （4）查找并显示给定电话号码的记录； 选作内容： （1）系统功能的完善； （2）设计不同的散列函数，比较冲突率； （3）在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。 6、文章编辑 功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共n行； 要求:（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。 存储结构使用线性表，分别用几个子函数实现相应的功能； 输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式： （1）分行输出用户输入的各行字符； （2）分4行输出“全部字母数”、“数字个数”、“空格个数”、“文章总字数”（3）输出删除某一字符串后的文章； 四、参考书目 《数据结构 c语言》 严蔚敏 清华大学出版社 《c语言程序设计》 谭浩强 清华大学出版社 《数据结构》 高教出版社 《数据结构习题》 李春保 清华大学出版社 《数据结构习题》 严蔚敏 清华大学出版社 《c语言与数据结构》 王立柱 清华大学出版社 《数据结构（c语言篇）习题与解析》李春葆 清华大学出版社 东华理工大学 东华理工大学 课程设计报告 课程设计题目： 综合排序的设计 学生姓名：何杨 班 级：1223202 专 业：信息与计算科学 指导教师：郭树蕻 2014年 12 月 13 日 东华理工大学 目录 摘要..............................................................2 一、题目的内容及要求-----------------4 二、需求分析------------------------------4 三、概要设计------------------------------5 四、四种排序源代码详细设计--------5 五、程序输出的结果-------------------10 六、运行结果及分析-------------------12 七、收获及体会-------------------------13 八、参考文献-----------------------------1 东华理工大学 摘 要 数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。 关键字：数据结构；算法比较；比较次数；时间复杂度 东华理工大学 一、题目的内容及要求 排序综合 利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。要求： (1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 (2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 (3)如果采用4种或4种以上的方法者，可适当加分。 二、需求分析 2.1 问题描述 此次的任务要求是输入20000个以上的随机整数，对这些数进行多种方法进行排序。（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。 约束：程序可由用户自行设定排序数的个数，但排序数具体值需要由计算机生成，然后用三种以上的排序方法对随机数组进行排序，每一种排序方法执行后需统计出数据移动次数以判断排序方法的对比随机数组的执行优劣性。另：用户自行算出每一种排序方法的时间复杂度与空间复杂度。 2.2 基本要求 2.2.1输入的形式和输入值的范围； 设定的随机数据的范围为20000以上，用户自定义随机数的个数n，随机数的数据类型均为整形。 2.2.2输出的形式； 程序是以一个完整的有序数组来进行输出。 2.2.3程序所达到的功能： 将一个无序数组进行排序随机生成20000以上个随机整数，对这些数进行多种方法进行排序。分别采用以下方法实现上述问题求解（可采用的方法有简单排序、希尔排序、冒泡排序、快速排序这四种排序方法）。 东华理工大学 三、概要设计 3.1可排序表的抽象数据类型定义： typedef int keytype;//关键字为整型 typedef int othertype;//关键字为整型 typedef struct { keytype key;//关键字为keytype型 othertype other_data;}recordtype;//定义一个recordtype型结构体，存放关键字 void quicksort(recordtype a[],int left,int right)//快速排序 void bubblesort(recordtype a[],int length)//冒泡排序 void shellsort(recordtype a[],int n)//希尔排序 void binsort(recordtype r[], int length)//折半插入排序 void main()//主函数运行入口 四、四种排序源代码详细设计： 4.1快速排序模块： void quicksort(recordtype a[],int left,int right){ recordtype t;int i,j,temp; if(left>right) return; temp=a[left].key; i=left; j=right; while(i!=j) { while(a[j].key>=temp && i j--; while(a[i].key<=temp && i 东华理工大学 i++; if(i { t=a[i]; a[i]=a[j]; a[j]=t; } } a[left] = a[i]; a[i].key = temp; quicksort(a,left,i-1);//继续处理左边的，这是一个递归的过程 quicksort(a,i+1,right);//继续处理右边的，这是一个递归的过程 } /* 快速排序算法 */ 4.2冒泡排序模块： //此处是一次冒泡排序过程，在主函数中会通过循环调用此冒泡函数过程 void bubblesort(recordtype a[],int length){ int i,temp; for(i=1;i { if(a[i].key>a[i+1].key) { temp = a[i].key; a[i].key=a[i+1].key; a[i+1].key=temp; } } }/* 冒泡排序算法 */ 4.3希尔排序模块： void shellsort(recordtype a[],int n){ int i, j, temp; int gap = 0; while(gap<=n)//根据待排序的个数生成合适的步长，gap是步长 { gap = gap * 3 + 1; 东华理工大学 } } while(gap > 0){ for(i = gap;i < n;i++){ j = igap; } a[j+gap+1].key = temp;} gap =(gap-1)/ 3;} 4.4希尔折半插入排序模块： /*折半插入排序法*/ void binsort(recordtype r[], int length)/*对记录数组r进行折半插入排序，length为数组的长度*/ { int i,j;recordtype x;int low,high,mid;for(i=2;i<=length;++i) { x= r[i]; low=1;high=i-1; while(low<=high) /* 确定插入位置*/ { mid=(low+high)/ 2; if(< r[mid].key) high=mid-1; else low=mid+1; } for(j=i-1;j>= low;--j) r[j+1]= r[j]; /* 记录依次向后移动 */ r[low]=x; /* 插入记录 */ } }/*binsort*/ 东华理工大学 4.5主函数模块： void main(){ int n,i,j,t; char b; bool q=false; recordtype a[40000]; while(1) { printf(“nn”);printf(“ ************** 综 合 排 序*****************************nn”); printf(“ *********************菜 单***************************nn”);printf(“ * ========= * n”); printf(“ * 1.读 取 待排序长度 * n”); printf(“ * 2.产生随机数并输出 * n”); printf(“ * 3.采用快速排序法排序 * n”); printf(“ * 4.采用冒泡排序法排序 * n”); printf(“ * 5.采用希尔排序法排序 * n”); printf(“ * 6.采用折半插入排序法排序 * n”); printf(“ * 7.输 出 * n”);printf(“ * 0.退 出 系 统 * n”);printf(“ *------------------------* n”); printf(“ ”); b = getch(); switch(b) { case '1': printf(“%cn”,b); printf(“请输入待排序记录的长度：”); scanf(“%d”,&n);break; 东华理工大学 case '2': printf(“%cn”,b); srand((unsigned)time(null)); printf(“下面随机生成%d个数字存储在数组中n”,n); for(i=1;i<=n;i++) { a[i].key = rand()%20000; printf(“%dt”,a[i].key); if(i%100==0) printf(“n”); } printf(“n”); break; case '3': printf(“%cn”,b); printf(“n -----------------快速排序结束------------------- nn”); quicksort(a,1,n); q=true;break; case '4': printf(“%cn”,b); for(i=0;i { bubblesort(a,n-i); } printf(“n -----------------冒泡排序结束------------------- nn”); q=true;break; case '5': printf(“%cn”,b); printf(“n -----------------希尔排序结束------------------- nn”); shellsort(a,n); q=true;break; case '6': printf(“%cn”,b); binsort(a,n); printf(“n -----------------折半插入排序结束-------------------nn”); q=true;break; case '7': printf(“%cn”,b); 东华理工大学 if(q) { printf(“n -----------------排序后输出------------------- n”); for(i=1;i<=n;i++) { printf(“%dt”,a[i].key); if(i%100==0) printf(“n”); } } else { printf(“n * ========= * n”); printf(“ * 您未对待排序数据排序 * n”); printf(“ * 请重新选择排序的序号 * n”); printf(“ *------------------------* n”); } break; case '0': printf(“%cn”,b); printf(“n 感谢使用综合排序程序n 按任意键退出......n”); return;break; default:printf(“nn”); } } } 五、程序输出的结果： 5.1输入和输出： (1)主函数运行的输出结果： 东华理工大学 (2)选择1，读取待排序长度（这里以20000为例）： (3)选择2，产生随机数并输出： (4)选择3，采用快速排序法排序： 东华理工大学 （选择4、5、6的其他排序法的输出雷同，此处就不再重复）(5)选择7，输出排序结果： 六、运行结果及分析 6.1各算法的比较方法 1.稳定性比较 折半插入排序、冒泡排序是稳定的希尔排序、快速排序是不稳定的 2.时间复杂性比较 折半插入排序、冒泡排序的时间复杂性为o(n2)其它非线形排序的时间复杂性为o(nlog2n)3.辅助空间的比较 东华理工大学 线形排序的辅助空间为o(n),其它排序的辅助空间为o(1);4.其它比较 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。 反而在这种情况下，快速排序反而慢了。 当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。 当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。 七、收获及体会 根据四种排序法的基础理论实际性模仿和编写算法程序，很是困难，算法是程序的灵魂，数据结构确是算法的基础，但是不断的实践也是一种进步的好途径。这次课程设计主要是对基础知识的灵活应用，这就让我进一步提高了对数结构知识的巩固。这次设计的完成，困难是少不了的，还有很多其它的难题让我都不知道所措，但是通过努力最终解决他们让我体会到成就感，更重要的是我的能力在实践中得到了提升和优化，特别是对常用的排序算法的应用，这对我以后从事软件应用程序开发是有很大的帮助的。这次课程设计的心得体会通过实习我的收获如下 1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。 2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。 3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。 4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。 2、写程序的过程中要考虑周到，严密。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。 5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。我通过课程设计建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验，树立团队协作精神。同时，充分弥补了课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助从全局角度把握 东华理工大学 课程体系，并且可以将理论与实际联系。在课程设计的过程中不仅仅是书本上的知识，这便促使我去查阅更多的课外资料来充实自己的内容，同时学会在面对困难时要耐心得分析它细心得解决它以及通过合作更完美得深入了解剖析它以便得到提高。细心、耐心、团结、求知，是我这次课程设计最大的收获。同时要感谢老师这几天的悉心教导。 八、参考文献 [1] 啊哈磊，《啊哈！算法》，人民邮电出版社，2014-6-1 [2] 刘艳飞，《c语言范例开发大全》清华大学出版社，2010 [3] 严蔚敏，吴伟民。数据结构。北京：清华大学出版社，2001数据结构课程设计快速排序 数据结构课程设计排序算法比较篇二
数据结构课程设计快速排序 数据结构课程设计排序算法比较篇三
数据结构课程设计快速排序 数据结构课程设计排序算法比较篇四
数据结构课程设计快速排序 数据结构课程设计排序算法比较篇五
