《数据结构课程设计2.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计2.doc（29页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计题目：通讯录管理二叉树排序查找学院：信息工程学院姓名：胥诗燕班级：计科一班学号：201010510135 指导老师：林卫中 李娟2012-6-8 目 录一、 通讯录管理31、前 言32、概述43、系统设计54、详细设计65、运行结果14二、 二叉树181、需求分析182. 系统设计183、详细设计194、运行结果22三、 排序查找231、需求分析232. 系统设计233、详细设计244、运行结果27总 结28一、 通讯录管理1、前 言数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据
2、的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用，学习数据结构的最终目的是为了获得求解问题的能力。针对数据结构课程的特点，着眼于培养我们的实践能力。课程设计是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，我们都会有不同程度上的提高。2、概述1.问题描述问题描述通讯录管理是一个比较
3、实用的小型管理系统，该系统用于对通讯人员的姓名、电话号码的管理。该设计采用菜单作为应用程序的主要界面，用控制语句来改变程序执行的顺序，控制语句是实现结构化程序设计的基础。该设计的任务是利用一个简单实用的菜单，通过菜单项进行选择，实现和完成通讯录管理中常用的几个不同的功能。2.设计要求功能要求：1.建立通讯录链表；2.插入通讯录信息；3.查询通讯录信息；4.删除通讯录信息；5.输出通讯录信息。0.退出通讯录管理系统使用数字05来选择菜单项，其他输入则不起作用，并给出错误提示。规定：输入通讯录的信息：编号、姓名、性别、电话号码、地址界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相
4、关的功能要求。存储结构：利用单链表存储通讯录信息，同时要求将通讯信息相关数据存储在数据文件中。3、系统设计1.模块设计根据要求，电话簿数据以文本文件存放在文件中，故需要提供文件的输入、输出等操作；还需要保存记录以进行修改，删除，查找等操作；系统功能模块图如下：图1系统功能模块图查询通讯录信息功能细化：图2 查询通讯录信息功能细化4、详细设计1. 主界面与模块功能实现1.数据类型的选择：struct lianxiren /定义联系人； char num4; /编号char name20; /姓名 char sex10; /性别char phone15; /电话号码char addr50; /地址
5、;2.主要函数：char function(); /菜单void add(); /插入联系人信息void print(struct lianxiren a,int); /输入所有联系人信息void dele(struct lianxiren a,int); /删除联系人信息void search(struct lianxiren a,int); /查找联系人信息void search_name(struct lianxiren a,int n); /按姓名查找联系人void search_phone(struct lianxiren a,int n); /按电话号码查找联系人3.主函数及界面的
6、实现代码实现：void main() /主函数FILE *fp;if(fp=fopen(通讯录.txt,a)=NULL)printf(无法打开文件，按任意键退出!n);char a;scanf(%c,&a);exit(0);fclose(fp);for(;)int n=0;char ch;struct lianxiren tongxunlu100;struct lianxiren *p;p=tongxunlu;FILE *fp;if(fp=fopen(通讯录.txt,r)=NULL)printf(无法打开文件，按任意键退出!n);char a;scanf(%c,&a);exit(0);else
7、while(ch=fgetc(fp)!=EOF)fscanf(fp,%s%s%s%s%s,p-num,p-name,p-sex,p-phone,p-addr);p+;n+;switch(function()case 1:add();break; case 2:search(tongxunlu,n);break; case 3:dele(tongxunlu,n);break;case 4:print(tongxunlu,n);break;case 5:exit(0);char function()char choose5;printf(n*n); printf( 通 讯 录 管 理 n);pri
8、ntf( 1 插入通讯录信息 n);printf( 2 查询通讯录信息 n); printf( 3 删除通讯录信息 n);printf( 4 输出通讯录信息 n);printf( 5 退出通讯录管理 n); printf(*nn);doprintf( 请输入您的选择(1-5):);scanf(%s,choose);while(strcmp(choose,1)&strcmp(choose,2)&strcmp(choose,3)&strcmp(choose,4)&strcmp(choose,5);return choose0;4.模块功能的实现4.1 插入通讯录信息代码实现：void add()i
9、nt i;FILE *fp;if(fp=fopen(通讯录.txt,a)=NULL)printf(无法打开文件，按任意键退出!n);char a;scanf(%c,&a);exit(0);int num;printf( 您想要增加几个联系人：n);scanf( %d,&num);struct lianxiren t50;printf( 请输入联系人信息n);printf( 编号 姓名 性别 电话 地址n);printf( -n);for(i=0;inum;i+)scanf(%s%s%s%s%s,ti.num ,ti.name ,ti.sex ,ti.phone,ti.addr);printf(
10、_n);for(i=0;inum;i+)fprintf(fp,n);fprintf(fp,%s%s%s%s%s,ti.num ,ti.name ,ti.sex ,ti.phone,ti.addr);printf(*已成功添加%d个联系人*n,num);fclose(fp);4.2 查询通讯录信息代码实现：void search(struct lianxiren t,int n)int i;printf(输入选择：1按姓名查找，2按电话号码查找：);scanf(%d,&i);if(i=1) search_name(t,n);if(i=2) search_phone(t,n);void searc
11、h_name(struct lianxiren a,int n)char s20; int i,f=0; printf(输入要查找的人的名字n);scanf(%s,s);for(i=0;in;i+)if(strcmp(s,ai.name )=0)f+;printf( 您要找得人是：n);printf(-n);printf( 编号 姓名 性别 电话 地址n);printf(-n);printf(%-8s%-10s%-8s%-15s%-20sn,ai.num ,ai.name ,ai.sex ,ai.phone ,ai.addr);if(f=0)printf(没有找到符合您要求的联系人，请核查你的
12、输入!n);void search_phone(struct lianxiren a,int n)int i,f=0;char j5;printf(输入要找人的电话号码:n);scanf(%s,j);for(i=0;in;i+)if(strcmp(j,ai.phone)=0)f+;printf( 您要找得人是：n);printf(-n);printf( 编号 姓名 性别 电话 地址n);printf(-n);printf(%-8s%-10s%-8s%-15s%-20sn,ai.num ,ai.name ,ai.sex ,ai.phone ,ai.addr);if(f=0)printf(没有找到
13、符合您要求的联系人,请检查您的输入!n);4.3 删除通讯录信息代码实现：void dele(struct lianxiren a,int n)struct lianxiren temp5;char mingzi20;int i,j=0,s=0;printf(输入你要删除人得名字:);scanf(%s,mingzi);printf(n);for(i=0;in;i+)if(strcmp(mingzi,ai.name)!=0)strcpy(tempj.num,ai.num);strcpy(tempj.name,ai.name);strcpy(tempj.sex,ai.sex);strcpy(tem
14、pj.phone,ai.phone);strcpy(tempj.addr,ai.addr);j+;else s+;printf(你要删除得人得信息是：n);printf(-n);printf( 编号 姓名 性别 电话 n);printf(-n);printf(%-8s%-10s%-8s%-15s%-20sn,ai.num ,ai.name ,ai.sex ,ai.phone ,ai.addr);FILE *fp;if(fp=fopen(通讯录.txt,w)=NULL)printf(无法打开文件，按任意键退出!n);char a;scanf(%c,&a);exit(0);for(i=0;ij;i
15、+)fprintf(fp,n);fprintf(fp,%s%s%s%s%s,tempi.num,tempi.name,tempi.sex,tempi.phone,tempi.addr);if(s!=0) printf(*删除成功!*n);else printf(您所要删除的联系人不存在,请核查拼写及大小写n);fclose(fp);4.4 输出通讯录信息代码实现：void print(struct lianxiren t,int n)if(n=0)printf(*文件为空!*n);return;int i;printf(-通 讯 录-n);printf( 编号 姓名 性别 电话 地址n); p
16、rintf(-n);for(i=0;idata=ch;p-lchild=p-rchild=NULL;if (b=NULL) /p指向二叉树的根节点b=p;else /已建立根节点 switch(k)case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;2.2以括号表示法输出二叉树算法void DispBTNode(BTNode * b) /以括号表示法输出二叉树if (b!=NULL)printf(%c,b-data);if (b-lchild!=NULL|b-rchild!=NULL) printf();Disp
17、BTNode(b-lchild);if(b-rchild!=NULL)printf(,);DispBTNode(b-rchild);printf();2.3先序遍历的非递归算法void PreOrder(BTNode * b) /先序遍历的递归算法if (b!=NULL) printf(%c,b-data); /访问根节点 PreOrder(b-lchild); /递归访问左子树 PreOrder(b-rchild); /递归访问右子树 2.4中序遍历的递归算法void InOrder(BTNode * b) /中序遍历的递归算法if (b!=NULL) InOrder(b-lchild);
18、/递归访问左子树 printf(%c,b-data); /访问根节点 InOrder(b-rchild); /递归访问右子树2.5后序遍历的递归算法void PostOrder(BTNode *b) /后序遍历的递归算法if(b!=NULL) PostOrder(b-lchild); /递归访问左子树 PostOrder(b-rchild); /递归访问右子树 printf(%c,b-data); /访问根节点 2.6层次遍历算法void TravLevel(BTNode * b) /层次遍历BTNode *QuMaxSize; /定义顺序循环队列int front,rear; /定义队首和队
19、尾指针front=rear=0; /置队列为空队列if (b!=NULL)printf(%c,b-data);rear+; /终点指针为空队列Qurear=b;while (rear!=front) /队列不为空 front=(front+1) % MaxSize; b=Qufront; /队头出队列 if(b-lchild!=NULL) /输出左孩子，并入队列 printf(%c,b-lchild-data); rear=(rear+1)% MaxSize; Qurear=b-lchild; if(b-rchild!=NULL) /输出右孩子，并入队列 printf(%c,b-rchild-
20、data); rear=(rear+1)% MaxSize; Qurear=b-rchild; printf(n);2.7主函数void main()BTNode * b; CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I);printf( 二叉树b:);DispBTNode(b);printf(nn);printf( 层次遍历序列:);TravLevel(b);printf(n);printf( 先序遍历序列:n);PreOrder(b);printf(n);printf( 中序遍历序列:n);InOrder(b);printf(n);printf(
21、 后序遍历序列:n);PostOrder(b);printf(n);4、运行结果三、 排序查找1、需求分析1.问题描述文件中有一组无序的数据，先用快速排序排序为有序序列，再用二分查找进行数据查找，排序后的结果保存到文件。2. 系统设计1.流程图3、详细设计2.1定义结构：#define MAXE 20 /线性表中最多元素个数#define MAXL 100 /定义表中最多纪录个数typedef int KeyType;typedef char InfoType10;typedef struct /记录类型KeyType key; /关键字项InfoType data; /其它数据项，类型为In
22、foTypeRecType;typedef RecType SeqListMAXL; /顺序表类型2.2快速排序函数： void QuickSort(RecType R,int s,int t) /对Rs至Rt的元素进行快速排序int i=s,j=t,k;RecType temp;if(si&Rj.keytemp.key) j-; /从右向左扫描，找第一个关键字小于temp.key的Rj if(ij) /从左向右扫描，找第一个关键字大于temp.key的Ri Ri=Rj; i+; while(ij&Ri.keytemp.key) i+; /从左向右扫描，找第一个关键字大于temp.key的Ri
23、 if(ij) Rj=Ri; /从左向右扫描，找第一个关键字大于temp.key的Ri j-; Ri=temp; printf( ); /输出每一趟的排序结果 for(k=0;k10;k+) if(k=i) printf(%d,Rk.key); else printf(%4d,Rk.key); printf(n); QuickSort(R,s,i-1); /对左区间递归排序 QuickSort(R,i+1,t); /对右区间递归排序 2.3二分查找函数int BinSearch(SeqList R,int n,KeyType k) /二分查找算法int low=0,high=n-1,mid,c
24、ount=0;while(lowk) /继续在Rlow.mid-1中查找high=mid-1;elselow=mid+1; /继续在Rmid+1.high中查找return-1;2.4主函数void main()FILE *fp1,*fp2;if(fp1=fopen(QuickSort.txt,r)=NULL)printf(file cannot bo opened n);exit(1);int i=0,k,n=10;RecType RMAXE;KeyType aMAXE;while(!feof(fp1)fscanf(fp1, %d ,&ai);i+;n=i;for(i=0;in;i+)Ri.
25、key=ai;printf(n);printf( 初始关键字 ); /输出初始关键字序列for(k=0;kn;k+)printf( %4d ,Rk.key);printf(n);QuickSort(R,0,n-1);if(fp2=fopen(search.txt,w+)=NULL)printf(file cannot bo opened n);exit(1); printf( 最后结果 ); /输出最终结果for (k=0;kn;k+)printf( %4d ,Rk.key);fprintf(fp2, %d ,Rk.key);printf(nn); KeyType j; scanf( %d ,
26、&j);if(i=BinSearch(R,n,j)!=-1)printf(元素%d的位置是%dn,k,i);elseprintf(元素%d不在表中n,k);printf(n);4、运行结果QuickSort.txt内容运行结果Search.txt内容总 结通过为期两周的课程设计，我们对数据结构这门课程有了更深一步的了解。使我知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。在理论学习和上机实践的各个环节中，通过自主学习和请教老师，我收获了不少。同时在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体，指针，链表通过这次课程设计之后，我们把前面所学过的知识又重新温故了一遍。在程序的调试能力上，我也得到了许多的提高。例如：头文件的使用，变量和数组的范围问题，定义变量时出现的问题等等。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我的分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。
