数据结构设计报告设计.doc

1、数据结构课程设计报告数据结构课程设计报告专 业 计算机科学与技术 班 级 0902班 学 号 2009115010207 姓 名 夏丽霞 指 导 教 师 夏端峰老师 时 间 湖 北 师 范 学 院计 算 机 科 学 与 技 术 学 院目 录1、 链表的应用1.1设计要求61.2设计分析81.3算法实现101.4程序代码121.5测试结果151.6结论分析17第一章 链表的应用线性表(linear_list)是最常用而且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列，每个数据元素的具体含义在不同情况下各不相同。一个数据元素可以由若干个数据项(item)组成。线性表有顺序和链式两

2、种存储结构，后者是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。链表的结点（code）包括两个域，即数据域（存储数据元素信息的域）和指针域（存储该结点直接后继存储位置的域），在本章实验中数据域是为了描述通讯者的相关信息。有性表m同素_list 1.1 设计要求本章实验的设计要求如下： 建立一个通讯录管理系统，用以实现集中操作功能，如：但通讯录链表的建立、通讯者的插入、通讯者的查询、通讯者的删除以及通讯录表的输出等。1.2 设计分析为了实现通讯录管理系统的几种操作功能，首先做出如下总体设计框架 显示菜单项内容及输入提示 （用菜单函数的返回值经主函数后进入

3、下列相应的功能）查询通讯者信息删除通讯者信息退出管理系统显示所有通讯者信息创建通讯录链表添加新的通讯者1.3 算法实现由设计分析中的总体框架分模块来讨论算法实现u 实现循环和功能选择首先需要编写一个主控菜单驱动程序，输入05以进入相应的选择项。假设输入选择用变量mn存储，它作为menu（）函数的返回值提供给主函数中的switch语句，使用for循环来实现重复选择，并在主函数中完成这一系列操作。例如：如上所述，需要设计一个函数menu用来输出信息和处理输入，而该函数必须返回一个mn值给主函数中的switch语句。 该函数如下： int Menu()int mn;printf(通讯录管理系统n);

4、printf(=n);printf( 1.通讯录链表的建立n);printf( 2.通讯者结点的插入n);printf( 3.通讯者结点的查询n);printf( 4.通讯者结点的删除n);printf( 5.通讯录链表的输出n);printf( 0.退出管理系统n);printf(=n);printf(请选择0-5： ); for(; ;)scanf(%d,&mn);if(mn5)printf(n输入错误，重选0-5：);elsebreak;return mn;使得mn的输入值对应主函数中switch语句的case1case5，并由此完成各种功能操作。对于那些不合法的输入（比如mn的输入值大

5、于5或者小于0）则提示“输入错误”信息并要求重新输入。u 通讯录连表的建立（1）建立链表的方法有两种：头插法和尾插法头插法：头结点head有head -next=NULL再插入新结点p的循环语句中，用p-next=head -next;head -next=p； 两个语句来尾插法：定义指针 p=head;用While循环语句去实现新结点的插入并不断修改指针p的指向，以保证p一直指向单链表的最后一个结点。 （p1为新插入的结点） p-next=p1; p=p1;（2）要建立一个带头结点的单链表，首先要生成结点，本实验我采用尾插法来建立链表，因此其算法描述如下：使链表的头尾指针head、rear指

6、向新生成的头结点（当然也是链表的尾结点）；置结束标志为0（假）；while（结束标志不为真）； P指向新生成的结点； 读入一个通讯者数据至p的数据域； 将新结点插到尾结点之后； 修改指针：使尾指针指向新插入的结点； 提示信息：是否结束链表的建立，并读入一个结束标志，看是否结束循环； 尾结点指针域置空；u 通讯者信息的插入为了将一个通讯者数据结点按其编号的次序插入有序通讯录表中的相应位置，以确保通讯录链表的有序性。首先要找准插入的位置，方法：用两个指针变量p1和p2分别指向当前刚访问过的结点和下一个即将访问的结点，循环顺序查找单链表，寻找插入位置，其中p1指向待插入位置的前一个结点。算法描述如下

7、：用p1指向原通讯链表的头结点，p2指向链表的第二个结点，p为即将要插入的新结点；while(p2!=NULL& p2-data.numdata.num) p1=p2; p2=p2-next; 插入新结点p-next=p2；u 通讯者的查找要查找指定通讯者，首先必须输入要查找的通讯者的编号或是姓名，从单链表的表头开始顺序访问表中每一个结点，如果查找成功则返回一个指向该结点的指针；如果查找失败则返回一个空指针。注： 按编号查找时，由于通讯录链表是按编号进行有序排列的，故若所查找的通讯者编号不在表中则不一定需要循环从通讯链表表头比较到表尾； 而按姓名查找时则需要循环比较到表尾方可确定查不到的情况！

8、u 通讯者的删除本功能比较容易实现，值得注意的是通讯连表上结点的删除操作需要先调用查找函从表头循环比较到表尾查找到要删除的结点方可顺利完成！u 通讯录链表的输出本功能也比较容易实现，只要定义一个指针变量p且它等于链表头指针，然后用p顺序向后扫描单链表，直至表尾即可。1.4 程序代码#include#include#include#define SIZE sizeof(ListNode)typedef struct /定义数组分别存放数据域中各成员的相关信息：num name sex /phone addrchar num6; char name9;char sex3; char phone13

9、;char addr31;DataType;/结点类型定义typedef struct nodeDataType data; struct node *next; ListNode,*LinkList; /定义一个struct类型的变量ListNode和一个指向/struct的指针变量LinkList head,p;/11111111111菜单int Menu()int mn;printf(通讯录管理系统n);printf(=n);printf( 1.通讯录链表的建立n);printf( 2.通讯者结点的插入n);printf( 3.通讯者结点的查询n);printf( 4.通讯者结点的删除n

10、);printf( 5.通讯录链表的输出n);printf( 0.退出管理系统n);printf(=n);printf(请选择0-5： );for(; ;)scanf(%d,&mn);if(mn5)printf(n输入错误，重选0-5：);elsebreak;return mn;/222222222222222通讯录链表的建立struct node *CreateList() struct node *head,*p1,*p;/char t5 ;/memset(t,0,sizeof(t) ;int flag=0;printf(输入:学号（6位数字） 姓名（5个汉字） 性别（2个汉字） 电话（d

11、ata.num,p1-data.name,p1-data.sex,p1-data.phone, p1-data.addr); p-next=p1;p=p1;printf(请输入flag 1结束0继续n) ;scanf(%d,&flag) ;if(flag=1)break ;p-next=NULL;/printf(-&-6666-n);return head;/33333333333333333插入新的通讯者void InsertNode(LinkList head,LinkList p)ListNode *p1,*p2;p1=head;p2=p1-next;while(p2!=NULL&str

12、cmp(p2-data.num,p-data.num)next; p-next=p2; p1-next=p; /444444444444444444通讯者的查找ListNode *ListFind(LinkList head)ListNode *p;char num5;char name9;int xz;printf(=n);printf( 1.按编号查询 n);printf( 2.按姓名查询 n);printf(=n);printf( 请 选 择：);p=head-next; /通讯录链表带头结点scanf(%d,&xz);if(xz=1)printf(请输入要查找者的编号：);scanf(

13、%s,&num);getchar(); / -while(p&strcmp(p-data.num,num)next;if(p=NULL|strcmp(p-data.num,num)0)p=NULL; /没有查到想要查找的通讯者elseif(xz=2)printf(请输入要查找者的姓名：);scanf(%s,&name);getchar(); /-while(p&strcmp(p-data.name,name)!=0)p=p-next;return p;/55555555555555555通讯者的删除void DelNode(LinkList head)char jx;ListNode *p,*

14、q;p=ListFind(head); /调用查找函数if(p=NULL)printf(没有查到要删除的通讯者！n);return;printf(真的要删除该结点吗？(y/n):);scanf(%c,&jx);/getchar();if(jx=y|jx=Y)q=head;while(q!=NULL&q-next!=p)q=q-next;q-next=p-next; /删除结点free(p);printf(通讯者已被删除！n);/66666666666通讯录链表的输出void PrintList(struct node * head)struct node *p1;p1=head-next; p

15、rintf( 学号 姓名 性别 电话 地址 n);printf( -n);while(p1!=NULL)printf(%s,%s,%s,%s,%sn,p1-data.num,p1-data.name,p1-data.sex,p1-data.phone,p1-data.addr);printf(-n); p1=p1-next;/主函数void main()for( ; ; )switch (Menu()case 1:printf(*n);printf(* 通 讯 录 链 表 的 建 立 *n);printf(*n);head=CreateList();break;case 2:printf(*n

16、);printf(* 通 讯 者 信 息 的 添 加 *n);printf(*n);printf(编号（6）姓名（5个汉字）性别（2个汉字） 电话（data.num,p-data.name,p-data.sex,p-data.phone,p-data.addr);InsertNode(head,p);break;case 3:printf(*n);printf(* 通 讯 录 信 息 的 查 询 *n);printf(*n);p=ListFind(head);if(p!=NULL)printf(编号 姓 名 性别 联系电话 地 址n);printf(-n);printf(%s,%s,%s,%s

17、,%sn,p-data.num,p-data.name,p-data.sex,p-data.phone,p-data.addr);printf(-n);elseprintf(没查到要查询的通讯者！n);break;case 4:printf(*n);printf(* 通 讯 录 信 息 的 删 除 *n);printf(*n);DelNode(head); /删除结点信息break;case 5:printf(*n);printf(* 通 讯 录 链 表 的 输 出 *n);printf(*n);PrintList(head);break;case 0:printf(t 退出管理系统！n);r

18、eturn;1.5 测试结果1.6 结论分析 本章的设计练习总的来说还是比较成功的，很好的实现了通讯录链表的建立、插入、删除、查询以及输出功能。感觉出现问题最多的模块就是创建通讯录链表，在手动输入通讯者相关信息时总是会出现这样那样的错误导致输出时不能正确显示通讯者各个信息的准确值。一开始做这个课程设计的时候总是对链表的建立很不满意，不明白为什么是用scanf(%s%s%s%s%s,p1-data.num,p1-data.name,p1-data.sex,p1-data.phone, p1-data.addr)；语句计算机就可以将“09021 夏丽霞 女 12345678912 湖北省黄石市”分

19、别正确读入num-name-sex-phone-addr中，而不是用scanf(%s%s%s%s%s )语句来实现。上机实验做得越多就会越来越发觉：课本上的理论知识固然很重要但是没有实际的动手编程加上坚持不懈的改动和完善，想要编出好的程序来根本就是无稽之谈！同时我还认识到其实编写代码并不那么可怕，认认真真地进行设计分析、算法分析以及总体的框架搞清楚，先总体把握在逐步进行模块展开也是程序设计的关键所在！ 课程设计是一次不断学习如何完善自己程序设计，让它更简单，更容易理解，更美观，更好的实现功能的过程。这对于我的实际操作能力也有很大的帮助。我相信通过以后认真的学习和持之以恒的实践，必将会有更多的收获。计算机科学与技术学院 0902班 夏丽霞