数据结构课程设计2

1、数据结构课程设计数据结构课程设计题目：题目：通讯录管理通讯录管理二叉树二叉树排序查找排序查找学院：信息工程学院姓名：胥诗燕班级：计科一班学号：201010510135 指导老师：林卫中 李娟2012-6-8 目目 录录一、一、 通讯录管理通讯录管理.3 31、前 言 .32、概述.43、系统设计.54、详细设计.65、运行结果.14二、二、 二叉树二叉树.18181、需求分析.182. 系统设计 .183、详细设计.194、运行结果.22三、三、 排序查找排序查找.23231、需求分析.232. 系统设计 .233、详细设计.244、运行结果.27总总 结结.2828一、一、 通讯录管理通讯录

2、管理1 1、前、前 言言数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用，学习数据结构的最终目的是为了获得求解问题的能力。针对数据结构课程的特点，着眼于培养我们的实践能力。课程设计是为了加强编程能力的

3、培养，鼓励学生使用新兴的编程语言。相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，我们都会有不同程度上的提高。2 2、概述、概述1.1.问题描述问题描述问题描述通讯录管理是一个比较实用的小型管理系统，该系统用于对通讯人员的姓名、电话号码的管理。该设计采用菜单作为应用程序的主要界面，用控制语句来改变程序执行的顺序，控制语句是实现结构化程序设计的基础。该设计的任务是利用一个简单实用的菜单，通过菜单项进行选择，实现和完成通讯录管理中常用的几个不同的功能。2.2.设计要求设计要求功能要求：1.建立通讯录链表；2.插入通讯录信息；3.查询通讯录信息；4.删除通讯录信息；5.输出通讯录信息。0

4、.退出通讯录管理系统使用数字 05 来选择菜单项，其他输入则不起作用，并给出错误提示。规定：输入通讯录的信息：编号、姓名、性别、电话号码、地址界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：利用单链表存储通讯录信息，同时要求将通讯信息相关数据存储在数据文件中。3 3、系统设计、系统设计1.1.模块设计模块设计根据要求，电话簿数据以文本文件存放在文件中，故需要提供文件的输入、输出等操作；还需要保存记录以进行修改，删除，查找等操作；系统功能模块图如下：图 1 系统功能模块图查询通讯录信息功能细化：图 2 查询通讯录信息功能细化4 4、详细设计、详细设计1.

5、1. 主界面与模块功能实现主界面与模块功能实现1.1.数据类型的选择：数据类型的选择：struct lianxiren /定义联系人； char num4; /编号char name20; /姓名 char sex10; /性别char phone15; /电话号码char addr50; /地址;2.2.主要函数：主要函数：char function(); /菜单void add(); /插入联系人信息void print(struct lianxiren a,int); /输入所有联系人信息void dele(struct lianxiren a,int); /删除联系人信息void se

6、arch(struct lianxiren a,int); /查找联系人信息void search_name(struct lianxiren a,int n); /按姓名查找联系人void search_phone(struct lianxiren a,int n); /按电话号码查找联系人3.3.主函数及界面的实现主函数及界面的实现代码实现：代码实现：void main() /主函数file *fp;if(fp=fopen(通讯录.txt,a)=null)printf(无法打开文件，按任意键退出!n);char a;scanf(%c,&a);exit(0);fclose(fp);f

7、or(;)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);elsewhile(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();brea

8、k; 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);printf( 1 插入通讯录信息 n);printf( 2 查询通讯录信息 n); printf( 3 删除通讯录信息 n);printf( 4 输出通讯录信息 n);printf( 5 退出通讯录管理 n); printf(*nn);dopr

9、intf( 请输入您的选择(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.模块功能的实现模块功能的实现4.14.1 插入通讯录信息插入通讯录信息代码实现：代码实现：void add()int i;file *fp;if(fp=fopen(通讯录.txt,a)=null)printf(无法打开文件，按任意键退出!n);char a;scanf(%

10、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.sex ,ti.phone,ti.addr);printf(_n);for(i=0;inum;i+)fprintf(fp,n);fprintf(fp,%s%s%s%s%s,ti.num ,

11、,ti.sex ,ti.phone,ti.addr);printf(*已成功添加%d 个联系人*n,num);fclose(fp);4.24.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 search_name(struct lianxiren a,int n)char s20; int i,f=

12、0; printf(输入要查找的人的名字n);scanf(%s,s);for(i=0;in;i+)if(strcmp(s, )=0)f+;printf( 您要找得人是：n);printf(-n);printf( 编号 姓名 性别 电话 地址n);printf(-n);printf(%-8s%-10s%-8s%-15s%-20sn,ai.num , ,ai.sex ,ai.phone ,ai.addr);if(f=0)printf(没有找到符合您要求的联系人，请核查你的输入!n);void search_phone(struct lianxiren a,int n)i

13、nt 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.sex ,ai.phone ,ai.addr);if(f=0)printf(没有找到符合您要求的联系人,请检查您的输入!n);4.34.3 删除通讯录信息删除通讯录信息代码实现：代码实

14、现：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,)!=0)strcpy(tempj.num,ai.num);strcpy(,);strcpy(tempj.sex,ai.sex);strcpy(tempj.phone,ai.phone);strcpy(tempj.add

15、r,ai.addr);j+;else s+;printf(你要删除得人得信息是：n);printf(-n);printf( 编号 姓名 性别 电话 n);printf(-n);printf(%-8s%-10s%-8s%-15s%-20sn,ai.num , ,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+)fprintf(fp,n);fprintf(fp,%s%s

16、%s%s%s,tempi.num,,tempi.sex,tempi.phone,tempi.addr);if(s!=0) printf(*删除成功!*n);else printf(您所要删除的联系人不存在,请核查拼写及大小写n);fclose(fp);4.44.4 输出通讯录信息输出通讯录信息代码实现：代码实现：void print(struct lianxiren t,int n)if(n=0)printf(*文件为空!*n);return;int i;printf(-通 讯 录-n);printf( 编号 姓名 性别 电话 地址n); printf(-n);for(i=

17、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.22.2 以括号表示法输出二叉树算法以括号表示法输出二叉树算法void dispbtnode(btnode * b) /以括号表示法输出二叉树if (b!=null)printf(%c,b-data);if (b-lchild!=null|b-rchild!=null) printf();di

18、spbtnode(b-lchild);if(b-rchild!=null)printf(,);dispbtnode(b-rchild);printf();2.32.3 先序遍历的非递归算法先序遍历的非递归算法void preorder(btnode * b) /先序遍历的递归算法if (b!=null) printf(%c,b-data); /访问根节点 preorder(b-lchild); /递归访问左子树 preorder(b-rchild); /递归访问右子树 2.42.4 中序遍历的递归算法中序遍历的递归算法void inorder(btnode * b) /中序遍历的递归算法if

19、(b!=null) inorder(b-lchild); /递归访问左子树 printf(%c,b-data); /访问根节点 inorder(b-rchild); /递归访问右子树2.52.5 后序遍历的递归算后序遍历的递归算法法void postorder(btnode *b) /后序遍历的递归算法if(b!=null) postorder(b-lchild); /递归访问左子树 postorder(b-rchild); /递归访问右子树 printf(%c,b-data); /访问根节点 2.62.6 层次遍历算法层次遍历算法void travlevel(btnode * b) /层次遍

20、历btnode *qumaxsize; /定义顺序循环队列int front,rear; /定义队首和队尾指针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

21、; if(b-rchild!=null) /输出右孩子，并入队列 printf(%c,b-rchild-data); rear=(rear+1)% maxsize; qurear=b-rchild; printf(n);2.72.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

22、(b);printf(n);printf( 中序遍历序列:n);inorder(b);printf(n);printf( 后序遍历序列:n);postorder(b);printf(n);4 4、运行结果、运行结果三、三、 排序查找排序查找1 1、需求分析、需求分析1.1.问题描述问题描述文件中有一组无序的数据，先用快速排序排序为有序序列，再用二分查找进行数据查找，排序后的结果保存到文件。2.2. 系统设计系统设计1.1.流程图流程图3 3、详细设计、详细设计2.12.1 定义结构：定义结构：#define maxe 20 /线性表中最多元素个数#define maxl 100 /定义表中最多

23、纪录个数typedef int keytype;typedef char infotype10;typedef struct /记录类型keytype key; /关键字项infotype data; /其它数据项，类型为 infotyperectype;typedef rectype seqlistmaxl; /顺序表类型2.22.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-; /从

24、右向左扫描，找第一个关键字小于temp.key 的 rj if(ij) /从左向右扫描，找第一个关键字大于temp.key 的 ri ri=rj; i+; while(ij&ri.keytemp.key) i+; /从左向右扫描，找第一个关键字大于temp.key 的 ri 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)

25、; quicksort(r,s,i-1); /对左区间递归排序 quicksort(r,i+1,t); /对右区间递归排序 2.32.3 二分查找函数二分查找函数int binsearch(seqlist r,int n,keytype k) /二分查找算法int low=0,high=n-1,mid,count=0;while(lowk) /继续在 rlow.mid-1中查找high=mid-1;elselow=mid+1; /继续在 rmid+1.high中查找return-1;2.42.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;fo