杭电_数据结构课程设计报告模板(内附C代码)

1、.专业整理 .数据结构课程设计报告学院专业 ：软件工程班级：学号：学生姓名 ：指导老师 ：彭伟民日期：2016.01.01. 学习帮手 .专业整理 .目录1猴子吃桃子问题 .41.1需求分析 .41.2程序设计思想 .41.3程序源代码 .41.4程序运行结果 .82进制数转化问题 .92.1需求分析 .92.2程序设计思想 .92.3程序源代码 .102.4程序运行结果 .133长整数运算 .133.1需求分析 .133.2程序设计思想 .133.3程序源代码 .143.4程序运行结果 .224学生成绩管理系统 .224.1需求分析 .224.2程序设计思想 .234.3程序源代码 .24.

2、 学习帮手 .专业整理 .4.4程序运行结果.365哈夫曼编码应用 .385.1需求分析 .385.2程序设计思想.395.3程序源代码 .395.4程序运行结果.426学校超市选址问题 .446.1需求分析 .446.2程序设计思想.446.3程序源代码 .446.4程序运行结果.517学生成绩管理系统 .527.1需求分析 .527.2程序设计思想.527.3程序源代码 .527.4程序运行结果.638排序综合 .658.1需求分析 .658.2程序设计思想.668.3程序源代码 .678.4程序运行结果.829课程设计总结 .84. 学习帮手 .专业整理 .1 猴子吃桃子问题1.1 需求

3、分析有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第 10 天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子 。1.2 程序设计思想已知第十天只余下1 个桃子，第一天开始每天都吃当前桃子一半再多一个，那么就只需要从第十天开始倒推即可，用链表、数组、递推、常规方法都可以采用这种思路实现计算第一天桃子数量。1.3 程序源代码#include<iostream>using namespace std;/ 有一群猴子摘了一堆桃子 ，他们每天都吃当前桃子的一半且再多吃一个 ，到了第 10 天就只余下一个桃子 。用多种方法实现求出原来这群猴子共摘了多少个

4、桃子 。/ 链表方法实现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);. 学习帮

5、手 .专业整理 .int main()int peach=0;void shuZu();int digui(int i,int j);int changgui();shuZu();peach=digui(1,1);cout<<" 递归方法实现结果 ："<<peach<<endl;/ 以下为链表实现int i=10,data;Stack s;InitStack(s);PushStack(s,1);/ 先将第 10 天的桃子数 1 入栈while(i->1)data=PopStack(s);/ 出栈一个元素保存在data 中PushSt

6、ack(s,2*(data+1);/ 再将 2*(data+1) 入栈. 学习帮手 .专业整理 ./ 最后栈中剩余的那个元素就是第 1 天摘的桃子数cout<<" 链表方法实现结果 ："<<PopStack(s)<<endl;cout<<" 常规方法实现结果 ："<<changgui()<<endl;return 0;void shuZu()/ 数组方式实现int peach10;peach9=1;for(int i=8;i>=0;i-)peachi=(peachi+1+1)*

7、2;cout<<" 数组方法实现结果 ："<<peach0<<endl;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

8、 peach;1.4 程序运行结果. 学习帮手 .专业整理 .2 进制数转化问题2.1 需求分析任意给定一个 M 进制的数 x ，请实现如下要求1) 求出此数 x 的 10 进制值 （用 MD 表示）2) 实现对 x 向任意的一个非 M 进制的数的转换 。3) 至少用两种或两种以上的方法实现上述要求 （用栈解决 ，用数组解决，其它方法解决 ）2.2 程序设计思想假如 N 为输入的数 ，n 为要转换为的进制 ，若要将十进制 231 转换为 8 进制数，过程如下 ;NN/nN%n2312872834303则输出为 347 ，可以看出 ，首先得到的应该是7，然后才是 4，最. 学习帮手 .专业整理

9、.后是 3，但是要逆序显示 ，自然就类似压栈出栈的数据结构了。所以，只需要初始化栈后 ，将 N%n 不断的压入栈底 ，需要注意的是如果要转换为 16 进制，则需要对大于 9 的数字作字符处理 。2.3 程序源代码#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>void TransIntoDec(double M, int X)void TransIntoAny(int X);char *p = NULL;int len = 0;int i;int s

10、um = 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;in

11、t 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");scan

12、f("%d %d", &m, &x);p = (char*)malloc(32);itoa(x, p, 10);length = strlen(p);for(i = 0; i < length; i+)if(*(p + i) - '0' > m)break;if(i = length)TransIntoDec(m, x);. 学习帮手 .专业整理 .elseprintf("Input errorn");return;2.4 程序运行结果3 长整数运算3.1 需求分析设计一个程序实现两个任意长的整数求和运算。提示

13、：可利用双项循环链表实现长整数的存储，每个结点含一个整型变量。3.2 程序设计思想定义双链表的节点结构 ，每个节点存储一个4 位的数，比如1,0031,0056 存入链表后就是1,31,56 三个节，输出的时候再补0 输出，由此完成长整数加法或减法运算。. 学习帮手 .专业整理 .3.3 程序源代码#include <stdio.h>#include <stdlib.h>#include <string.h>/ 以下是双链表的节点结构 ，每个节点存储一个 4 位的数，比如1,0031,0056 存入链表后就是1,31,56 三个节，输出的时候再补0 输出！t

14、ypedef struct nodeint 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=',

15、9;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(" 请输入运算

16、符号 :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-&

17、gt;prev=q;q->next->n=0;p->prev=q->next;q=q->next;q->n+=(conv(num2+i+1)+f);if(q->n<10000)f=0;elsef=1;q->n-=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;elsewhile(q->next!=p)q

18、=q->next;q->n+=1;if(q->n<10000)f=0;break;elseq->n=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,"

19、,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;elsef=1;q

20、->n+=10000;if(f)if(q->next=p)q->n-=10000;. 学习帮手 .专业整理 .elsewhile(q->next!=p)q=q->next;q->n-=1;if(q->n>=0)f=0;break;elseq->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,&

21、quot;,q->n);return 0;3.4 程序运行结果4 学生成绩管理系统4.1 需求分析现有学生成绩信息文件1（ 1.txt ），内容如下 （数据可以自拟 ）姓名学号语文数学英语张明明01677882李成友02789188张辉灿03688256. 学习帮手 .专业整理 .王露04564577陈东明05673847.学生成绩信息文件2（2.txt ）,内容如下 :姓名学号语文数学英语陈果31576882李华明32889068张明东33484256李明国34504587陈道亮35475877.试编写一管理系统 ，要求如下 ：1) 实现对两个文件数据进行合并 ，生成新文件 3.txt

22、2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt3) 对合并后的文件 3.txt 中的数据按总分降序排序 (至少采用两种排序方法实现 )4) 输入一个学生姓名后 ,能查找到此学生的信息并输出结果 (至少采用两种查找方法实现 )5) 要求使用结构体 ，链或数组等实现上述要求 。4.2 程序设计思想建立学生信息保存在文本文档中，具体对学生信息进行插入删除查询操作时，将保存在文本文档中的学生信息提取出来保存在自己定义的. 学习帮手 .专业整理 .数据结构中 ，然后再对该数据结构进行操作，所有操作完成后或者在相应的命令后再将学生信息保存到文本文档中。数据类型主要是char 、int 、

23、float 等数据类型 ，内容包括学号 、姓名等数据 。4.3 程序源代码#include<iostream>#include<stdlib.h>#include<string>using namespace std;char top50; /成绩文件顶部的标题用top 保存typedef struct student /单个学生成绩的记录char name10; /姓名int number; /学号int chinese; /语文int math; /数学int english; /英语struct student *next;student,*grade

24、list;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

25、(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)/ 关闭文件pri

26、ntf(" 文件关闭失败 ");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() /合并文

27、件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(" 合并成绩文档失败 ，

28、原因：建立文档出错 ");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.txtp1=p1->next;while(p2->next!=NULL) fprintf(fp,"%6s %2

29、d %d %d %dn",p2->name,p2->number,p2->chinese,p2->math,p2->english); /输入 2.txtp2=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

30、.txt","w+")=NULL) /新建文件 4.txtprintf(" 抽取补考学生成绩记录建立新文件失败");exit(0);gradelist file3=fileread(address3);student *p=file3;fprintf(fp,"%s",top); /先输入标题while(p->next!=NULL) if(p->chinese)<60|(p->math)<60|(p->english)<60) / 补考条件fprintf(fp,"%6s %2d %d %d %dn",p->name,p->number,p->chinese,p->math,