2013级数据结构课程设计报告

1、计算机科学与技术学院课程设计成绩单课程名称：数据结构课程设计 指导教师： 袁嵩姓名涂智明性别男学号1班级软件1101综合成绩成绩等级程序运行情况（占总成绩20%）能正确运行 基本能正确运行 能运行但结果不完善（20分） （15分） （10分）程序功能的完善程度（占总成绩10%）完善 基本完善 不完善（10分） （8分） （5分）程序结构的合理性（占总成绩10%）合理 基本合理 不太合理（10分） （8分） （5分）对问题的答辩情况（占总成绩40%）概念正确有创新 能正确回答所有问题 基本能正确回答（40分） （35分） （30分）部分问题回答概念不清晰（20分）学生的工作态度与独立工作能力（占

2、总成绩10%）工作态度认真能独立完成任务 工作态度认真但独立性较差（10分） （8分）工作态度基本认真但缺乏独立性（5分）设计报告的规范性（占总成绩10%）符合规范 基本符合规范 规范性较差（10分） （8分） （5分）优秀：90分100分 良好：80分89分 中等：7079分 及格：6069分 不及格0分59分 武汉科技大学计算机科学与技术学院制表 计算机科学与技术学院 课 程 设 计 报 告课程名称： 数据结构 专 业： 软件工程 班 级： 11级 1 班 学 号： 1 姓 名： 涂智明 指导老师： 袁嵩 题目一 通讯录一、问题描述1） 通过键盘建立通讯录，每条记录至少包括2个数据项：姓名

3、、电话号码；2） 对通讯录进行插入、删除、修改和查找；3） 通过姓名查找，必须实现精确查找和模糊查找，例如输入“张”，则显示第一个姓张的朋友，然后可以选择“下一个”，鼓励思路创新，提供其他多种查找方式，例如拼音查找等；4） 也可以根据电话号码或部分电话号码进行精确查找和模糊查找；5） 自行定义数据结构，可以选择性的将顺序查找、折半查找、索引查找、树型查找、哈希表等灵活运用其中，完成多方式查找功能。二、解题思路将一个用户的信息定义为一个结构体，使用链表存储用户信息。每一个用户为一个节点。通讯录功能设置为新建通讯录，新增联系人，查找联系人，修改联系人，删除联系人，保存通讯录，打开已有通讯录。保存通

4、讯录将通讯录以文本文件存到本地硬盘，在启动程序后，可选择打开已保存的通讯录。三、算法描述四、程序设计typedef struct nodeint n;char name20;char tel20;char add20;char qq15;struct node * next;list;用于存储联系人信息void enterdata(list *p0);用于数据输入void show (list *head);显示已输入的信息void save (list *head,FILE *fp);保存文件void load (list *&head);载入已存储的文件void search (list

5、*head);搜索联系人void change (list *head);改变已有联系人信息void del (list *&head);删除已有联系人void create (list *&head);创建新通讯录void insert(list *&head);插入一个联系人信息程序源码：#include stdafx.h#include #include#include#include #include#define LEN sizeof(list)using namespace std;typedef struct nodeint n;char name20;char tel20;ch

6、ar add20;char qq15;struct node * next;list;void enterdata(list *p0);void show (list *head);void save (list *head,FILE *fp);void load (list *&head);void search (list *head);void change (list *head);void del (list *&head);void create (list *&head);void insert(list *&head);int main(int argc, char* argv

7、)list *head=NULL;FILE *fp=NULL;int m;/功能代号吗docouttttt通讯录endl;cout请选择您需要的功能：endl;cout#;cout#tt1.显示所有联系人信息tt2.新建通讯录tt #;cout#tt3.查找联系人ttt4.修改联系人tt #;cout#tt5.删除联系人ttt6.增加联系人tt #;cout#tt7.保存tttt8.打开ttt #;cout#tt9.清屏tttt0.退出ttt #;cout#endl;coutm;switch(m)case 1: show(head);break;case 2: create(head); br

8、eak;case 3: search(head);break;case 4: change(head);break;case 5: del(head);break;case 6: insert(head);break;case 7: save(head,fp);printf(=保存成功=n);break;case 8: load(head);break;case 9: system(cls);break;while(m!=0);return 0;/数据输入void enterdata(list *p0)printf(名字: );gets(p0-name); printf(城市: ); gets

9、(p0-add); printf(电话: ); gets(p0-tel); printf(QQ: ); gets(p0-qq); printf(n); /显示列表void show (list *head)list *p; /定义移动指针int i;char *menu=姓名,地址,电话, QQ;/,生日,备注p=head;printf(-n);for(i=0;i4;i+)printf(%-12s,menui);coutname);printf(%-12s,p-add);printf(%-12s,p-tel);printf(%-12s,p-qq);printf(n);p=p-next; els

10、ecout不好意思,列表为空n;coutname,p0-add,p0-tel,p0-qq);p0=p0-next;fclose(fp);/载入void load (list *&head)FILE *fp;char ch;/存储从文件中读取的字符char lujing100;list *p1,*p2;/,*p3;printf(输入打开通讯录得路径：n);printf(例如：c:新建文件夹通讯录.txtn请输入:);scanf(%s,lujing);fp=fopen(lujing,r);if(fp=NULL)printf(错误:打不开文件或文件不在n);exit(0);ch=fgetc(fp);

11、/判定通讯录是否为空if(ch=EOF)printf(=通讯录空=n);p2=p1=head;while(p1!=NULL)p2=p1;p1=p1-next;free(p2);head=NULL;while(!feof(fp) p1=(list *)malloc(LEN); p1-next=NULL; fscanf(fp,%s %s %s %s,p1-name,p1-add,p1-tel,p1-qq); if(head=NULL) head=p1; p2=head; else p2-next=p1; p2=p1; fclose(fp);show(head);printf(n通讯录打开成功n);

12、/查找void search (list *head)list *p1,*p2;char check_name20; int j=0,m;printf(请输入要查找的姓名n);scanf(%s,check_name); if(head=NULL)printf(n不好意思,列表为空n);p1=head;while(p1!=NULL) if(strstr(p1-name,check_name) /模糊查找 用的strstr（）函数 printf( 姓名: %s ,p1-name);printf( 城市: %s ,p1-add);printf( 电话: %s ,p1-tel);printf( QQ

13、: %s ,p1-qq);printf(n);printf(是否是本条记录？按1确定本条记录t按其他数字键继续n);scanf(%d,&m);if(m=1)break;p2=p1;p1=p1-next;if(p1=NULL&j=0)printf(n没有%s的通讯信息n,check_name);/修改void change (list *head)list *p1,*p2; char change_name20; FILE *fp=NULL; printf(请输入要修改的姓名n); scanf(%s,&change_name); getchar();if(head=NULL)printf(n不好

14、意思,列表为空n);p1=head;while(p1!=NULL &strcmp(change_name,p1-name)!=0)p2=p1;p1=p1-next; if(p1!=NULL & strcmp(change_name,p1-name)=0) enterdata(p1); save(head,fp);elseprintf(n%s没有被找到n,change_name);/删除void del (list *&head)list *p1,*p2;/定义临时指针char delname20;/保存要删除人的姓名FILE *fp=NULL;/文件指针int i;printf(请输入要删除人

15、的姓名:);scanf(%s,delname);if(head=NULL)printf(n =通讯录为空=n);p1=head; /通讯录不为空时，把头指针赋值给p1while(p1&(i=strcmp(delname,p1-name)/*p1指向的不是所要找的结点，且p1不是最后一个结点*/ p2=p1; /保存前驱结点地址p1=p1-next; if(i=0) printf(删除人为:%sn,p1-name);if(p1=head) head=p1-next; /若p1指向的是首结点，指第二个结点的地址给P1else p2-next=p1-next;/修改指针域head-n=head-n-

16、1; printf(刚刚删除的是:%sn,delname); free(p1);save(head,fp); else if(p1=NULL)printf(n姓名为%s的通讯信息没有被找到！n,delname);/创建void create (list *&head)list *p0,*p1,*p2; int m;/作为判断是否继续新建的条件FILE *fp=NULL;p0=(list *)malloc(LEN);p0-next=NULL;head=p0;printf(请输入信息建立通讯录：n);getchar();enterdata(p0);p2=p0;printf(是否继续按1输入，按0结

17、束);scanf(%d,&m);while(m)getchar();p1=(list *)malloc(LEN);p1-next=NULL; p2-next=p1;enterdata(p1);p2=p1;head-n = head-n+1;/表长*printf(是否继续按1输入，按0结束 );scanf(%d,&m);if(m=0)save(head,fp);/插入void insert(list *&head)list *p,*q;p=head; while(p-next)p=p-next;/遍历到最后一个结点printf(新建：n);q=(list *)malloc(LEN);q-next

18、=NULL;getchar();enterdata(q);p-next=q;head-n = head-n+1;printf(=建立完成-注意保存=n);五、测试结果题目二 便利店选址一、问题描述某小区决定在小区内部建一家便利店，现小区内部共有八栋楼，它们的地理坐标分别为：（10，20） （30，34） （19，25） （38，49.1） （9，38.1） （2，34） （5，8） （29，48）。同时，其中的住户人数分别为：30, 45, 28, 8, 36, 16, 78, 56。为了方便更多的住户购物，要求实现总体最优，请问便利店应该建立在哪里？【提示】1）便利店无论选址何处，八栋楼的居

19、民均可直接到达，即八栋楼与便利店均相邻，且距离为直线距离；2）八栋楼的居民人数为权重，应该方便大多数人，实现总体最优。二、解题思路运用精确重心算法，求出小区的重心，将便利店建在重心处即可。三、算法描述1. 确定便利店地址初始位置（xd(0),yd(0)）。2. 计算出与（xd(0),yd(0)）相应的距离权重CT(0)。3. 将（xd(0),yd(0)）代入公式中，计算出便利店地址的改进位置（xd(1),yd(1)）。4. 计算出与（xd(1),yd(1)）相应的距离权重CT(1)。5. 将CT(1)与CT(0)进行比较，若CT(1)CT(0)，则返回步骤3，将（xd(1),yd(1)）代入公

20、式中，计算出便利店地址第二次改进位置（xd(2),yd(2)）。若CT(1)CT(0)，说明初始位置（xd(0),yd(0)）便是最优解。6. 如此反复迭代计算，直至CT(k+1)CT(k)，求出（xd(k),yd(k)）这一最优解为止。四、程序设计本程序中定义了四个函数分别是choosePostion()，sum1()，sum2()，comp()；sum1(),sum2()分别计算，choosePostion()计算，comp()返回两数字差值的绝对值；#include#include#define M 10000double xM=10,30,19,38,9,2,5,29,yM=20,34

21、,25,49.1,38.1,34,8,48,rM=30,48,28,8,36,16,78,56,dM;void choosePostion(int n,double m);void main()int i,n;double min;printf(输入楼的数量： );scanf(%d,&n);while(n=0)printf(没有楼不能建超市!n);printf(请重新输入需要满足楼数： );scanf(%d,&n);printf(输入各楼的坐标（x,y），住户n);for(i=0;in;i+)printf(第%d个：坐标：,i+1);scanf(%lf,%lf,&xi,&yi);printf(住户人数:);scanf(%lf,&ri);printf(求最佳地址); i=8;printf(请给出收敛的差值min:);scanf(%lf,&min);choosePostion(i,min);double sum1(int n,double aM,double bM)int i;double s=0,p=0;for(i=0;in;i+)s+=ai*bi;for(i=0;in;i+)p+=bi;return s/p;double sum2(int n,double aM,do