数据结构课程设计报告模板(内附C代码).doc

精品文档数据结构课程设计报告 学院专业： 软件工程 班 级： 学 号： 学生姓名： 指导老师： 彭伟民 日 期： 2016.01.01 目录1猴子吃桃子问题31.1需求分析31.2程序设计思想31.3程序源代码31.4程序运行结果52进制数转化问题52.1需求分析52.2程序设计思想62.3程序源代码62.4程序运行结果73长整数运算83.1需求分析83.2程序设计思想83.3程序源代码83.4程序运行结果124学生成绩管理系统134.1需求分析134.2程序设计思想134.3程序源代码144.4程序运行结果205哈夫曼编码应用225.1需求分析225.2程序设计思想225.3程序源代码235.4程序运行结果246学校超市选址问题266.1需求分析266.2程序设计思想266.3程序源代码266.4程序运行结果307学生成绩管理系统307.1需求分析307.2程序设计思想307.3程序源代码307.4程序运行结果368排序综合378.1需求分析378.2程序设计思想388.3程序源代码388.4程序运行结果469课程设计总结471 猴子吃桃子问题1.1 需求分析有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。1.2 程序设计思想已知第十天只余下1个桃子，第一天开始每天都吃当前桃子一半再多一个，那么就只需要从第十天开始倒推即可，用链表、数组、递推、常规方法都可以采用这种思路实现计算第一天桃子数量。1.3 程序源代码#includeusing namespace std;/有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。/链表方法实现typedef structint *base;int *top;Stack;void InitStack(Stack &s)s.base=(int *)malloc(sizeof(int);if(s.base) s.top=s.base;elseprintf(空间分配错误！n);exit(0);/入栈void PushStack(Stack &s,int data) *s.top+=data;/出栈int PopStack(Stack &s) return *(-s.top);int main()int peach=0;void shuZu();int digui(int i,int j);int changgui();shuZu();peach=digui(1,1);cout递归方法实现结果：peach1)data=PopStack(s);/出栈一个元素保存在data中PushStack(s,2*(data+1);/再将2*(data+1)入栈/最后栈中剩余的那个元素就是第1天摘的桃子数cout链表方法实现结果：PopStack(s)endl;cout常规方法实现结果：changgui()=0;i-)peachi=(peachi+1+1)*2;cout数组方法实现结果：peach0endl;int digui(int i,int j)/递归方法实现static int peach=i;static int day=j;if (day=10)return peach;else peach=(digui(peach,+day)+1)*2;return peach;int changgui()int peach = 1;for (int i = 1; i 10; i+)peach = (peach+1)*2;return peach;1.4 程序运行结果2 进制数转化问题2.1 需求分析任意给定一个M进制的数x ，请实现如下要求1) 求出此数x的10进制值（用MD表示）2) 实现对x向任意的一个非M进制的数的转换。3) 至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）2.2 程序设计思想假如N为输入的数，n为要转换为的进制，若要将十进制231转换为8进制数，过程如下;N N/n N%n231 28 728 3 43 0 3则输出为347，可以看出，首先得到的应该是7，然后才是4，最后是3，但是要逆序显示，自然就类似压栈出栈的数据结构了。所以，只需要初始化栈后，将N%n不断的压入栈底，需要注意的是如果要转换为16进制，则需要对大于9的数字作字符处理。2.3 程序源代码#include #include #include #include void TransIntoDec(double M, int X) void TransIntoAny(int X); char *p = NULL; int len = 0; int i; int sum = 0; int by = 1; printf(十进制数为: ); p = (char*)malloc(32); itoa(X, p, 10); len = strlen(p); for(i = 0; i len; i+) by *= pow(M,len-i-1); by *= (*(p + i) - 0); sum += by; by = 1; printf(%dn, sum); TransIntoAny(sum);void TransIntoAny(int X) int r; int temp32; int i = 0; printf(请输入转化进制：n); scanf(%d, &r); while(X) tempi+ = X % r; X /= r; printf(经转化为: ); while(i) printf(%d, temp-i); printf(n);void main() int m; int x; int i; int length; char* p = NULL; printf(请输入数字及确定其进制：n); scanf(%d %d, &m, &x); p = (char*)malloc(32); itoa(x, p, 10); length = strlen(p); for(i = 0; i m) break; if(i = length) TransIntoDec(m, x); else printf(Input errorn); return; 2.4 程序运行结果 3 长整数运算3.1 需求分析设计一个程序实现两个任意长的整数求和运算。提示：可利用双项循环链表实现长整数的存储，每个结点含一个整型变量。3.2 程序设计思想定义双链表的节点结构，每个节点存储一个4位的数，比如1,0031,0056存入链表后就是1,31,56三个节，输出的时候再补0输出，由此完成长整数加法或减法运算。3.3 程序源代码#include #include #include /以下是双链表的节点结构，每个节点存储一个4位的数，比如1,0031,0056存入链表后就是1,31,56三个节，输出的时候再补0输出！typedef struct node int n; struct node *next; struct node *prev; node;node *p;char num11024,num21024;int conv(char *a) int n=0,i; for(i=0;ai;+i) n*=10; n+=(ai-0); return n;int main() char c2; int i,f; node *q; p=(node*)malloc(sizeof(node); p-next=p-prev=0; q=p; num10=num20=,; printf(请输入第一个数字:n); scanf(%s,num1+1); for(i=strlen(num1);i=0;-i) if(num1i=,) num1i=0; q-next=(node*)malloc(sizeof(node); q-next-prev=q; q-next-next=0; q=q-next; q-n=conv(num1+i+1); q-next=p; p-prev=q; printf(请输入运算符号:n); scanf(%s,c); *c=*c=+?0:1; printf(请输入第二个数字:n); scanf(%s,num2+1); q=p;f=0; if(!*c) /+ for(i=strlen(num2);i=0;-i) if(num2i=,) num2i=0; if(q-next=p) q-next=(node*)malloc(sizeof(node); q-next-next=p; q-next-prev=q; q-next-n=0; p-prev=q-next; q=q-next; q-n+=(conv(num2+i+1)+f); if(q-nn-=10000; if(f) if(q-next=p) q-next=(node*)malloc(sizeof(node); q-next-next=p; q-next-prev=q; q-next-n=1; else while(q-next!=p) q=q-next; q-n+=1; if(q-nn=0; f=1; if(f) q-next=(node*)malloc(sizeof(node); q-next-next=p; q-next-prev=q; q-next-n=1; printf(%d,p-prev-n); for(q=p-prev-prev;q!=p;q=q-prev) printf(%04d,q-n); else /- for(i=strlen(num2);i=0;-i) if(num2i=,) num2i=0; if(q-next=p) q-next=(node*)malloc(sizeof(node); q-next-next=p; q-next-prev=q; q-next-n=0; p-prev=q-next; q=q-next; q-n-=(conv(num2+i+1)+f); if(q-n=0) f=0; else f=1; q-n+=10000; if(f) if(q-next=p) q-n-=10000; else while(q-next!=p) q=q-next; q-n-=1; if(q-n=0) f=0; break; else q-n+=10000; f=1; if(f) q-n-=10000; printf(%d,p-prev-n); for(q=p-prev-prev;q!=p;q=q-prev) printf(%04d,q-n); return 0;3.4 程序运行结果4 学生成绩管理系统4.1 需求分析现有学生成绩信息文件1（1.txt），内容如下（数据可以自拟）姓名 学号 语文 数学 英语 张明明 01 67 78 82李成友 02 78 91 88张辉灿 03 68 82 56王露 04 56 45 77陈东明 05 67 38 47. . . . 学生成绩信息文件2（2.txt）,内容如下:姓名 学号 语文 数学 英语 陈果 31 57 68 82李华明 32 88 90 68张明东 33 48 42 56李明国 34 50 45 87陈道亮 35 47 58 77. . . . 试编写一管理系统，要求如下：1) 实现对两个文件数据进行合并，生成新文件3.txt2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt3) 对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现)4) 输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现)5) 要求使用结构体，链或数组等实现上述要求。4.2 程序设计思想建立学生信息保存在文本文档中，具体对学生信息进行插入删除查询操作时，将保存在文本文档中的学生信息提取出来保存在自己定义的数据结构中，然后再对该数据结构进行操作，所有操作完成后或者在相应的命令后再将学生信息保存到文本文档中。数据类型主要是char、int、float等数据类型，内容包括学号、姓名等数据。4.3 程序源代码#include#include#includeusing namespace std;char top50; /成绩文件顶部的标题用top保存typedef struct student /单个学生成绩的记录 char name10; /姓名 int number; /学号 int chinese; /语文 int math; /数学 int english; /英语 struct student *next;student,*gradelist;gradelist fileread(char *adress) /读取成绩文件 FILE * fp; if(fp=fopen(adress,r)=NULL) /打开文件 printf(文件打开出错); exit(0); gradelist file=(student *)malloc(sizeof(student); /申请空间 file-next=NULL; student * p=file; /操作指针 int n=0; /循环标记，具体作用是在第一次循环时方便处理标题 while(!feof(fp) if(n=0) fgets(top,50,fp); /处理标题，并且文件指针移到第二行 if(n=1) /申请空间 p-next=(student *)malloc(sizeof(student); p=p-next; p-next=NULL; fscanf(fp,%s%d%d%d%d,p-name,&p-number,&p-chinese,&p-math,&p-english); /将文件的数据输入到链表中 n=1; if(fclose(fp)/关闭文件 printf(文件关闭失败); exit(0); return file;void FilePrint(gradelist file)/将成绩文件打印到屏幕上 student *p=file; printf(%sn,top); /打印标题 while(p-next!=NULL) printf(%6s %2d %d %d %dn,p-name,p-number,p-chinese,p-math,p-english); /循环打印 p=p-next; void merger() /合并文件 char * address1=F:/1.txt,*address2=F:/2.txt,*address3=F:/3.txt; gradelist file1=fileread(address1),file2=fileread(address2); FILE *fp; if(fp=fopen(F:3.txt,w+)=NULL) /先新建一个3.txt，然后将1.txt和2.txt的内容输入到里面 printf(合并成绩文档失败，原因：建立文档出错); exit(0); student *p1=file1,*p2=file2; fprintf(fp,%s,top); /先输入标题 while(p1-next!=NULL) fprintf(fp,%6s %2d %d %d %dn,p1-name,p1-number,p1-chinese,p1-math,p1-english); /输入1.txt p1=p1-next; while(p2-next!=NULL) fprintf(fp,%6s %2d %d %d %dn,p2-name,p2-number,p2-chinese,p2-math,p2-english); /输入2.txt p2=p2-next; if(fclose(fp) printf(文件关闭失败); exit(0); void extract() /抽取补考的成绩记录 char * address4=F:/4.txt,*address3=F:/3.txt; FILE *fp; if(fp=fopen(F:/4.txt,w+)=NULL) /新建文件4.txt printf(抽取补考学生成绩记录建立新文件失败); exit(0); gradelist file3=fileread(address3); student *p=file3; fprintf(fp,%s,top); /先输入标题 while(p-next!=NULL) if(p-chinese)math)english)name,p-number,p-chinese,p-math,p-english); p=p-next; if(fclose(fp) printf(文件关闭失败); exit(0); void sort(int i) char * address3=F:/3.txt; gradelist file3=fileread(address3); /先将3.txt读入链表 student *p=file3; if(remove(F:/3.txt) /由于排序后的内容也要保存到3.txt，故删除3.txt printf(删除文件出错); exit(0); int n=0; /学生个数 FILE *fp; if(fp=fopen(F:/3.txt,w+)=NULL) /新建一个空的3.txt printf(新建文件出错); exit(0); fprintf(fp,%s,top); /标题先输入 while(p-next!=NULL) n+; p=p-next; typedef struct int totalgrade; char name10; int number; int chinese; int math; int english;gradenote; /成绩记录typedef struct gradenote r100; /只初始化了100了空间，学生人数超过100就不能了，懒得动态分配了grade_list; /待排序成绩表grade_list L;p=file3;int t,k,j,k1,j1;for(t=1;tnext) /将链表的内容复制到结构数组里 strcpy(L.,p-name); L.rt.number=p-number; L.rt.chinese=p-chinese; L.rt.math=p-math; L.rt.english=p-english; L.rt.totalgrade=p-chinese+p-math+p-english;if(i=1) /直接插入排序 for(k=2;k=n;+k) if(L.rk.totalgradeL.rk-1.totalgrade) L.r0=L.rk; L.rk=L.rk-1; for(j=k-2;L.r0.totalgradeL.rj.totalgrade;-j) L.rj+1=L.rj; L.rj+1=L.r0; if(i=2) int m; for(k1=2;k1=n;+k1) L.r0=L.rk1; int low=1,high=k1-1; while(low=high) m=(low+high)/2; if(L.r0.totalgrade=high+1;-j1) L.rj1+1=L.rj1; L.rhigh+1=L.r0; int q; for(q=n;q=1;q-)/将排序好的内容输入到3.txt fprintf(fp,%6s %2d %d %d %dn,L.,L.rq.number,L.rq.chinese,L.rq.math,L.rq.english); if(fclose(fp) printf(文件关闭失败); exit(0); void search(char *name) /按姓名查找 gradelist file=fileread(F:/3.txt); student * p=file; while(p-next!=NULL) if(strcmp(name,p-name)=0) printf(%6s %2d %d %d %dn,p-name,p-number,p-chinese,p-math,p-english); return; p=p-next; printf(查无此人,请确定名字输入正确n); exit(0);void main(void) int chioce; gradelist file1=fileread(F:/1.txt),file2=fileread(F:/2.txt); printf(现有成绩记录文件1n); printf(*n); FilePrint(file1); printf(*n); printf(现有成绩记录文件2n); printf(*n); FilePrint(file2); printf(*n); printf(第一步，合并成绩记录文件n); merger(); printf(合并成功n); system(PAUSE); printf(现有合并后的成绩记录文件3n); printf(*n); gradelist file3=fileread(F:/3.txt); FilePrint(file3); printf(*n); printf(第二步，抽取补考成绩记录n); extract(); system(PAUSE); printf(现有补考成绩记录文件4n); printf(*n); gradelist file4=fileread(F:/4.txt); FilePrint(file4); printf(*n); printf(第三步，对文件3进行排序n); printf(请输入排序方式(1/2)n1:直接插入排序n2:折半插入排序n); scanf(%d,&chioce); if(chioce=1) sort(1); else if(chioce=2) sort(2); else printf(输入不合理,程序默认采用1方式n); sort(1); file3=fileread(F:/3.txt); printf(现有按总分降序的成绩记录3n); printf(*n); FilePrint(file3); printf(*n); printf(第四步，查找学生信息n); char name100; printf(请输入学生姓名n); scanf(%s,name); search(name); printf(按任意键结束程序n); getchar();4.4 程序运行结果5 哈夫曼编码应用5.1 需求分析 问题要求：找一篇英文文章，统计出每个字符出现的次数，然后以他们为权值，对每个字符进行编码，编码完成后对其编码进行译码。要求： a) 输入一篇英文文章，根据字符出现的次数给出哈夫曼编码方式。 b) 对英文文章进行编码； c) 对编码进行译码核对正确性d) 采用哈夫曼编码的思想，实现该文件的压缩和恢复功能，并提供压缩前后的占用空间之比。5.2 程序设计思想初始化:程序自动统计文章中的字符出现次数并赋予权值. 编制哈夫曼码:根据权值选出两个权值最小值最为叶节点，其权值之和为根节点，哈弗曼树从叶到根总体按照小到大原则生长，最终实现哈弗曼树.编码:输入字符,输出哈夫曼码. 译码:输入哈夫曼,输出字符代码. 退出:结束进程,退出程序.5.3 程序源代码#include #include 5_1.husing namespace std;int main()cout * endl;cout * * endl;cout * 哈夫曼编码译码器 * endl;cout * 1、打开一篇英文文章或输入一篇文章 * endl;cout * 2、根据字符出现的次数以他们为权值给出哈夫曼编码方式 * endl;cout * 3、对英文文章进行编码 * endl;cout * 4、对编码进行译码核对正确性 * endl;cout * * endl;cout * endlendl;system(pause);cout endl;Huffman huffman;huffman.ReadTextFromFile(F:/text.txt);cout 程序自动统计字符和权值 endl;huffman.CountCharsWeight();cout endl;cout 字符及对应权值： endl;huffman.PrintCharWeight();cout endl;system(pause);cout endl;huffman.MakeCharMap();cout 字符及对应编码： endl;huffman.PrintCharCode();cout endl;system(pause);cout endl;cout 对原文进行编码： endl;cout 原文： endl;huffman.PrintText();huffman.Encode();cout endl;cout 编码： endl;huffman.PrintCode();huffman.SaveCodeToFile(F: