《数据结构课程设计通讯录管理、拓扑排序、排序查找数据.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计通讯录管理、拓扑排序、排序查找数据.doc（18页珍藏版）》请在三一文库上搜索。
1、景德镇陶瓷学院数据结构课程设计选题：通讯录管理、拓扑排序、排序查找数据学 号: 姓 名： 院 （系）： 信息工程学院 专 业：计算机科学与技术 完成日期： 2012. 06.05 指导老师： 李 娟、林卫中 目录一、通讯录管理3第1章 需求分析31.1问题定义31.2 问题分析3第2章 概要设计42.1 数据结构描述42.11 数据类型定义42.2模块设计42.21 模块之间的关系42.22 主程序流程图设计5第3章 程序设计63.1 程序演示6二、拓扑排序102.1问题描述102.2要求102.3 问题分析102.4 主要流程图112.5代码设计122.6 要实现的图122.7 程序演示13
2、三、排序查找数据143.1问题描述143.2要求143.3主要思路及代码143.4 主要流程图设计163.5 程序演示17总结18一、通讯录管理第1章 需求分析1.1问题定义 随着信息社会的高速发展与进步，人们之间的交往越来越丰富多彩，人与人之间的交往联系越来越频繁，通讯方式越来越多样化，如何保证与朋友、同学、同事、领导、亲戚等之间的联系，并能方便快捷的查找、记录、修改其相关通讯信息，越来越受到关注。对通讯录进行必要的管理与更人性化的设计，对人们实现快速得知朋友的信息提供了极大的方便，仅靠以前单独的手工记录已远远不能满足当前的需要。在通讯录管理系统中应该包含的模块有：通讯录的建立模块、插入新的
3、信息模块、在已有通讯录中进行查找模块、删除已有信息模块、显示所有通讯录信息模块、退出通讯录管理系统模块。1.2 问题分析程序运行时输入某些已知的通讯信息，在此基础之上，进行通讯录信息的查找、插入、删除及通讯录中所有信息的显示和退出该管理系统程序的操作流程。另外，还应该使用图形化界面，即要使人机界面友好，在进入通讯录之前显示主菜单供用户选择；在显示通讯录数据项目时，如果用户按下回车键，则在下面显示系统菜单。开发一个通讯录管理系统，借助计算机可以方便、快捷、灵活的管理个人的朋友及相关人员的通讯信息，了解友人相关信息，帮助与友人保持联络。第2章 概要设计2.1 数据结构描述2.11 数据类型定义(1
4、) 链表存储结构描述及函数描述typedef struct /通讯录结点类型 char num5; /编号 char name9; /姓名 char sex3; /性别 char phone13; /电话 char addr31; /地址 DataType;typedef struct node /结点类型定义 DataType data; /结点数据域 struct node *next; /结点指针域 ListNode;typedef ListNode *LinkList;LinkList head;ListNode *p;LinkList CreateList(void);/通讯录建立函
5、数void InsertNode(LinkList head,ListNode *p);/通讯录信息插入函数ListNode *ListFind(LinkList head);/通讯录信息查询函数void DelNode(LinkList head);/通讯录信息删除函数void PrintList(LinkList head);/通讯录信息输出函数LinkList WritetoText(void);/通讯录信息保存到文件函数2.2模块设计2.21 模块之间的关系功能模块图2.22 主程序流程图设计主程序流程图第3章 程序设计3.1 程序演示 通讯录链表的创建通讯录链表插入通讯录的查询通讯录
6、的删除通讯录的输出通讯录的保存二、拓扑排序2.1问题描述拓扑排序可判断AOV网络中是否存在回路，使的所有活动可排成一个线性序列，使用每个活动的所有前驱活动都排在该活动的前面。2.2要求（1）在有向图中选一个没有前驱的顶点，输出；（2）从有向图中删除该顶点及其该顶点出发的所有边；（3）重复以上两个步骤，直至全部顶点输出；注：输出所有拓扑排序可加分。2.3 问题分析 首先对有向图，我们采取邻接表作为数据结构。且将表头指针改为头结点，其数据域存放该结点的入度，入度设为零的结点即没有前趋。在建立邻接表输入之前，表头向量的每个结点的初始状态为数据域VEX（入度）为零，指针域NXET为空，每输入一条弧 建
7、立链表的一个结点，同时令k 的入度加1，因此在输入结束时，表头的两个域分别表示顶点的入度和指向链表的第一个结点指针。在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减1。（1）、查邻接表中入度为零的顶点，并进栈。（2）、当栈为空时，进行拓扑排序。（a）、退栈，输出栈顶元素V。（b）、在邻接表中查找Vj的直接后继Vk，将Vk的入度减一，并令入度减至零的顶点进栈。（3）、若栈空时输出的顶点数不是N个则说明有向回路，否则拓扑排序结束。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面
8、，借用入度为零的数据域存放带链栈的指针域（下一个入度的顶点号）。2.4 主要流程图否 拓扑排序算法流程图2.5代码设计struct node int adjvex; node* next;adjMAX;int Create(node adj,int n,int m)/邻接表建表函数，n代表定点数，m代表边数void print(int n)/邻接表打印函数void topsort(node adj,int n)/拓扑算法函数2.6 要实现的图 图一图二2.7 程序演示图一图二三、排序查找数据3.1问题描述文件中有一组无序的数据，先排序为有序序列，再进行数据查找，排序后的结果保存为文件。3.2要
9、求1） 要求从文件中读取无序数据；2） 选择已学的排序算法，尽量选用高效的算法；3.3主要思路及代码主要文件代码FILE *fp1,*fp2;if(fp1 = fopen (datafile.txt,r) =NULL)printf(File connot be opened n);exit (1) ;if(fp2 = fopen (resultfile.txt,w) =NULL)printf(File connot be opened n);exit (1) ;void SelectSort(RecType R,int n) /直接选择排序int i,j,k;RecType tmp;for(i
10、=0;in-1;i+) /做第i趟排序k=i;for(j=i+1;jn;j+) /在当前无序区Ri.n-1中选key最小的Rkif(Rj.keyRk.key)k=j; /k记下目前找到的最小关键字所在的位置if(k!=i) /交换Ri和Rktmp=Ri;Ri=Rk;Rk=tmp;int BinSearch(SeqList R,int n,KeyType j)/二分查找算法int low=0,high=n-1,mid,count=0;while (lowj) /继续在Rlow.mid-1中查找high=mid-1;elselow=mid+1; /继续在Rmid+1.high中查找return -
11、1;在相同路径创建文件datafile.tex,输入无序序列 12 13 45 56 23 43 67 34 21 78，利用直接选择排序与二分查找进行排序和查找。直接选择排序思路：再要排序的一组数中，选择最小的一个数与最先位置的数进行交换，然后在剩下的数中找最小的数与第二位置的数进行交换，如此循环到倒数第二个数与最后一个数比较为止。然而直接选择排序是一个不稳定的排序方法，适用于n较小时使用。直接选择排序的总比较次数为：n(n-1)/2,总的平均时间复杂度为O(n2)。二分查找思路：二分查找又称折半查找，是一种效率较高的查找方法。但是二分查找要求线性表式有序表，即表中记录按关键字有序。二分查找
12、要先确定要查找的范围区域，以处于中间位置的关键字与给定的关键字进行比较，若相等则查找成功，若不想等则逐步缩小范围，直到新的区间的中间记录与所查找的值先分相等或或查找区间的大小小于0（说明查找不成功）。二分查找的效率虽高，但是二分查找只适合于顺序存储结构，为保持表的有序性，在顺序结构里插入和删除都必须移动大量的记录。其平均查找长度为log2(n+1)-1。3.4 主要流程图设计二分查找算法流程图3.5 程序演示总结通过这次的课程设计，让我回顾了不少以前学习的知识，从中也让我发现了自己的很多不足，在做通讯录管理系统时，由于自己对文件这块知识不太理解，以致在做好相关插入、建表、查询、显示等函数后，不
13、知道如何保存。但最终通过看相关书籍和资料以及向同学请教，最终还是正常的运行出了自己的程序。另外发现以自己现在的知识水平，想要独立的自己编写代码还存在一定的难度，上网查询资料以及翻阅相关书籍的本领必不可少，学会运用并适当的理解也是学习中必不可少的一部分。例如很多函数的调用，如果让自己独立的编写，不得不说现在还做不到。另外，拓扑排序、排序查找这两个课题的设计，让我回顾了前段时间学习的相关知识，对拓扑排序算法有了更进一步的了解，排序查找中文件的保存在之前通讯录的基础上显得熟练了许多，没有遇到太大的问题。也让我回顾了一下排序查找方式的优缺点，对今后数据结构课程的学习知识的运用有一定的帮助。总而言之，实践总会让我们发现问题，如何更好学好编程也将是以后自己所要注意的方面。