数据结构课程设计2.doc

数据结构课程设计 1 数据结构课程设计数据结构课程设计 题目：题目：通讯录管理通讯录管理 二叉树二叉树 排序查找排序查找 学院：信息工程学院 姓名：胥诗燕 班级：计科一班 学号：201010510135 指导老师：林卫中 李娟 2012-6-8 数据结构课程设计 2 目目 录录 一、一、 通讯录管理通讯录管理3 3 1、前 言 3 2、概述.4 3、系统设计.5 4、详细设计.6 5、运行结果14 二、二、 二叉树二叉树1818 1、需求分析18 2. 系统设计 18 3、详细设计19 4、运行结果22 三、三、 排序查找排序查找2323 1、需求分析23 2. 系统设计 23 3、详细设计24 4、运行结果27 总总 结结2828 数据结构课程设计 3 一、一、 通讯录管理通讯录管理 1 1、前、前 言言 数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业 课之间的桥梁。通过本门课程的学习，我们应该能透彻地理解各种数据对象的 特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和 解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习 和工作，也有着重要的意义。 数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的 课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践 能力有着极为重要的作用，学习数据结构的最终目的是为了获得求解问题的能 力。针对数据结构课程的特点，着眼于培养我们的实践能力。课程设计是为了 加强编程能力的培养，鼓励学生使用新兴的编程语言。相信通过数据结构课程 实践，无论是理论知识，还是实践动手能力，我们都会有不同程度上的提高。 数据结构课程设计 4 2 2、概述、概述 1.1.问题描述问题描述 问题描述通讯录管理是一个比较实用的小型管理系统，该系统用于对通讯 人员的姓名、电话号码的管理。该设计采用菜单作为应用程序的主要界面，用 控制语句来改变程序执行的顺序，控制语句是实现结构化程序设计的基础。该 设计的任务是利用一个简单实用的菜单，通过菜单项进行选择，实现和完成通 讯录管理中常用的几个不同的功能。 2.2.设计要求设计要求 功能要求： 1.建立通讯录链表； 2.插入通讯录信息； 3.查询通讯录信息； 4.删除通讯录信息； 5.输出通讯录信息。 0.退出通讯录管理系统 使用数字 05 来选择菜单项，其他输入则不起作用，并给出错误提示。 规定：输入通讯录的信息：编号、姓名、性别、电话号码、地址 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成 相关的功能要求。 存储结构：利用单链表存储通讯录信息，同时要求将通讯信息相关数据存 储在数据文件中。 数据结构课程设计 5 3 3、系统设计、系统设计 1.1.模块设计模块设计 根据要求，电话簿数据以文本文件存放在文件中，故需要提供文件的输入、 输出等操作；还需要保存记录以进行修改，删除，查找等操作； 系统功能模块图如下： 图 1 系统功能模块图 查询通讯录信息功能细化： 图 2 查询通讯录信息功能细化 数据结构课程设计 6 4 4、详细设计、详细设计 1.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 search(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; 数据结构课程设计 7 if(fp=fopen(“通讯录.txt“,“a“)=null) printf(“无法打开文件，按任意键退出!n“); char a; scanf(“%c“, 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“, exit(0); else 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“); 数据结构课程设计 8 printf(“ 通 讯 录 管 理 n“); printf(“ 1 插入通讯录信息 n“); printf(“ 2 查询通讯录信息 n“); printf(“ 3 删除通讯录信息 n“); printf(“ 4 输出通讯录信息 n“); printf(“ 5 退出通讯录管理 n“); printf(“*nn “); do printf(“ 请输入您的选择(1-5):“); scanf(“%s“,choose); while(strcmp(choose,“1“) return choose0; 4.4.模块功能的实现模块功能的实现 4.14.1 插入通讯录信息插入通讯录信息 代码实现：代码实现： void add() int i; file *fp; 数据结构课程设计 9 if(fp=fopen(“通讯录.txt“,“a“)=null) printf(“无法打开文件，按任意键退出!n“); char a; scanf(“%c“, exit(0); int num; printf(“ 您想要增加几个联系人：n“); scanf(“ %d“, struct lianxiren t50; printf(“ 请输入联系人信息n“); printf(“ 编号 姓名 性别 电话 地址n“); printf(“ - 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.22.2 以括号表示法输出二叉树算法以括号表示法输出二叉树算法 void dispbtnode(btnode * b) /以括号表示法输出二叉树 if (b!=null) printf(“%c“,b-data); if (b-lchild!=null|b-rchild!=null) printf(“(“); dispbtnode(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 (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) /层次遍历 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; 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(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 /定义表中最多纪录个数 typedef int keytype; typedef char infotype10; typedef struct /记录类型 keytype key; /关键字项 infotype data; /其它数据项，类型为 infotype rectype; 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 /从右向左扫描，找第一个关键字小于 temp.key 的 rj if(ik) /继续在 rlowmid-1中查找 high=mid-1; else low=mid+1; /继续在 rmid+1high中查找 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 “, i+; n=i; for(i=0;in;i+) ri.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+) p