通讯录管理系统的设计和实现

南通大学二○一一～二○一二学年第一学期计算机科学与技术学院课程设计报告书课程名称：数据结构课程设计班级：计101学号：1013022015姓名：徐鹏指导教师：顾颀二○一二年一月2设计题目:通讯录管理系统的设计与实现1.需求分析1.1描述要求编程解决的问题，给出程序要达到的具体要求1.1.1基本要求①设计通讯录数据的逻辑结构和物理结构②通讯录至少包括下列数据信息：姓名、电话、单位等。③完成图示基本功能。④软件易用，操作简单。⑤根据自己使用通讯录的体会，扩充其他功能，如按姓名查找、按号码查找、按序号删除等。⑥设计足够多的测试用例。1.1.2较高要求①数据输入有效性的检验：如姓名不能为空、号码中不能有非法字符等。②提供分组管理的相关功能，如：分组显示、加入组、组创建、组查询等。③可视化的界面设计。1.2测试案例设计，包括以下两方面案例：1.2.1合理的输入，给出的合理的输出输入：1张三12345678计1012-102输出：输入成功!1.2.2不合理的输入，给出的输出输入：2李四12**5678计1012-102输出：电话号码中出现非法输入请重新输入:2.概要设计2.1功能划分与定义，功能结构图基本功能模块如下图所示：输入显示查找插入删除保存读入排序修改移动退出主程序3输入：记录的输入。显示：通讯录显示。查找：按指定的方式，输入关键字，查找指定记录。插入：实现记录的添加或在指定位置插入新纪录。删除：提供指定记录的删除功能。保存：将内存中正在被操作的通讯录以文件形式保存到磁盘。读入：保存的逆操作，将存在磁盘里的通讯录文件读取到内存中。排序：按指定关键字对通讯录进行排序。修改：提供修改某条记录的功能。移动：移动记录在通讯录中的存储位置，使其被查找或显示时的位序前移或后移。退出：结束程序运行。2.2给出数据的逻辑设计、抽象的数据类型描述（1）数据域描述通讯录的相关信息，每个人的基本信息含有多个属性，其中包括姓名、电话、单位等，为此可根据人员信息建立结构体，类型定义如下：structDatatype{intid;//编号charname[10];//姓名charphone[12];//电话charclass[10];//单位};3.详细设计3.1数据的存储设计根据通讯录的设计要求，可使用单链表实现该通讯系统的功能，链表节点只含一个数据域和一个指针，线性表的链式存储结构如下：structNode{Datatypedata;//数据域，存放表元素Node*next;//指针域，指向下一个结点};3.2界面设计，包括菜单、数据输入输出格式等主菜单：查找联系人子菜单：显示通讯录子菜单：1-添加联系人1-按序号查找1-按序号显示2-查找联系人2-按姓名查找2-按姓名显示3-修改联系人3-按号码查找3-按号码显示4-删除联系人5-移动联系人6-显示通讯录7-退出4数据输入格式：请输入联系人的相关信息编号：1姓名：张三电话：1300000001单位：计102住址：2-102数据输出格式：编号姓名电话单位住址1张三130000001计1022-1023.2各功能的算法描述，可采用伪码、流程图、N-S图等方式读入函数intRead()，将存在磁盘中的文件读到内存中。是是否打开源文件否新建元素结点Nodes读取文件到新建节点的数据域返回新结点链入表尾s-next=p-nextp-next=s读入数据关闭文件保存函数intWrite()，将内存中正在被操作的通讯录以文件形式保存到磁盘。是否打开源文件是否P!=NULL将该节点数据写入磁盘return1p=p-next关闭文件return05排序函数voidSort()，分别按姓名和号码进行排序char(*a)[12]=newchar[n][12]char(*b)[12]=newchar[n][12]inti=0,j,tNode*p=Head-next;p!=NULLp-data.id=i+1;sort1[i]=sort2[i]=p-data.id;strcpy(a[i],p-data.name);strcpy(b[i],p-data.phone);p=p-next;i++;i=1inj=0jn-j是strcmp(a[j],a[j+1])0否t=sort1[j];sort1[j]=sort1[j+1];sort1[j+1]=t;是strcmp(b[j],b[j+1])0否t=sort2[j];sort2[j]=sort2[j+1];sort2[j+1]=t;delete[]a;delete[]b;输入函数DatatypeInput()，输入数据，并进行数据的校验输出：请输入联系人的相关信息输入编号cinid输入姓名cinname输入电话cinphone电话号码出现非法字符输入单位cindanwei输入地址cinaddress6显示函数voidPrintall()，显示通讯录Node*p;p=Head-next选择显示方式1.按编号2.按姓名3.按号码i=0i=0i=0in按链表顺序输出个节点数据in按姓名索引表sort1[]输出个节点数据in按号码索引表sort2[]输出个节点数据插入函数，intInsert(inti)，在表中第i个位置插入元素j=0Node*p;p=Head;ji-1p=p-nextj++Nodess-data=Input()s-next=p-nextp-next=s删除函数voidDelete(inti)，删除表中第i个元素Node*p,*qp=Headp-next&&p-next-data.id!=ip=p-nextq=p-nextp-next=q-nextdeleteq7查找函数intSearch()，通过序号查找Node*p;p=Head-next;选择查找方式1-按序号查找2-按姓名查找3-按号码查找cinicharch[12];cinchcharch[12]cinch;p-data.id!=ip=p-next;p&&strcmp(p-data.name,ch)p=p-next;p&&strcmp(p-data.phone,ch)p=p-next;Showlist();p=NULL是否p=NULL是否returnp-data.idreturn0returnp-data.idreturn0returnp-data.id移动函数intMove(inti)，移动联系人资料Node*p=Head,*q=Head;k=0cinjkj-1p=p-nextk++q-data.id!=iq=q-nextDelete(i)q-next=p-nextp-next=q8修改函数voidAmend(inti)，修改联系人资料，i为要修改的联系人的位置。Node*pp=Head-nextp-data.id!=ip=p-nextp-data=Input4.调试、测试、分析4.1给出软件使用说明及测试案例的运行情况的记录运行程序，显示主菜单①选择操作1，输入联系人的相关信息②选择操作2，查找联系人显示查找子菜单，程序提供三种查找方式选择查找方式19选择查找方式2选择查找方式3③选择操作3：修改联系人系统提示首先选择查找方式，找到该联系人，显示该联系人的原始信息，然后输入该联系人的修改信息，修改成功。④选择操作4：删除联系人首先也是查找到该联系人，显示该联系人的原始信息，然后删除。10⑤选择操作5：移动联系人输入移动的目标位置⑥选择操作6：显示通讯录显示显示子菜单，系统提供3种显示方式选择1-按编号显示选择2-按姓名显示选择3-按号码显示11⑦选择操作7结束运行，将内存中正在被操作的通讯录以文件形式保存到磁盘。4.2对主要算法进行复杂度分析①排序函数Sort()，采用冒泡排序法，时间复杂度为O(n2)②移动函数intMove(inti)，插入函数intInsert(inti)，删除函数voidDelete(inti)，修改函数voidAmend(inti)，查找函数intSearch()算法的时间主要耗费在查找数据的位置上，时间复杂度为O(n)③输出函数voidPrintall()，采用两层循环，外层for循环统计输出节点数目，内循环在链表上查找对应的节点，故时间复杂度为O(n2)5.总结与体会本实验程序主要使用了有头结点单链表的基本操作算法，包括创建表、元素插入、元素删除、元素查找、元素移动等。链式存储的优点是结点空间的动态分配使得无需预先确定存储空间，而且结点的前驱与后继靠指针指示，因此在链表中任何位置上进行插入和删除，只需修改指针，无需移动元素。链表的缺点就是只能顺序访问，查找结点需要从头指针进入逐个查找。由于存储中需存储数据元素信息以外的存储空间，用于存储数据元素之间的逻辑关系，所以其存储密度低于顺序表。另外，该程序还涉及到文件的读取和写入相关知识，既要会将存在磁盘中的文件读到内存中，也要能将内存中正在被操作的通讯录以文件形式保存到磁盘。程序设计时考虑到数据的校验问题，在数据生效之前，对输入数据的合法性进行验证，以免非法数据的输入。由于功能较多，本程序采用了多级菜单的形式。第一次做这种综合程序的设计，题目涉及的问题比较多，程序规模比较大，在设计的过程中遇到了不小的困难。在自己的努力和同学的帮助下，最终还是实现了这个程序，同时自己的编程能力也在程序的一个个错误的修正中得到提高。6.附：源程序main.cpp#includeiostream#includefstream#includeLinkList.hintmain(){inti,choice;LinkListL;L.Read();//将存在磁盘里的通讯录文件读取到内存中L.Sort();//更新索引表12do{//显示主菜单cout1-添加联系人\n;cout2-查找联系人\n;cout3-修改联系人\n;cout4-删除联系人\n;cout5-移动联系人\n;cout6-显示通讯录\n;cout7-退出\n;coutEnterchoice:;cinchoice;switch(choice){case1:cout请输入插入的位置:;cini;L.Insert(i);L.Sort();//当源数据表数据发生变化（如修改、插入、删除、移动）时，及时更新索引表break;case2:L.Search();break;case3://删除指定位置元素i=L.Search();//函数返回值为联系人的序号if(i==0)break;else{L.Amend(i);L.Sort();//更新索引表break;}case4:i=L.Search();//函数返回值为联系人的序号if(i==0)break;else{L.Delete(i);cout删除成功!endl;L.Sort();//更新索引表break;}case5:i=L.Search();//函数返回值为联系人的序号13if(i==0)break;else{L.Move(i);L.Sort();//更新索引表break;}case6:L.Printall();break;case7://退出cout结束运行endl;break;default://cout错误选项\n;break;}}while(choice!=7);//L.Write();//将内存中正在被操作的通讯录以文件形式保存到磁盘return0;}linklist.h#includefstream#includestringusingnamespacestd;#ifndefMY_1#defineMY_1structDatatype{intid;//编号charname[12];//姓名charphone[12];//电话chardanwei[12];//单位charaddress[12];//住址};structNod