1、数据结构课程设计实验报告 完整版第一章 链表的应用线性表是数据结构中最简单、最常用的一种线性结构，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继课程的学习。线性表的顺序存储结构，即顺序表的概念相对比较简单，因此，本章的主要任务是使用有关单链表的操作来实现通讯录信息系统的管理。1.1设计要求本章的设计实验要求使用有关链表的操作来实现通讯录信息系统的管理。为了验证算法，通讯录管理包括单通讯录链表的建立、通讯者的插入、通讯者的删除、通讯者的查询及通讯录表的输出等。主控菜单的设计要求使用数字05来选择菜单项，其他输入则不起作用。程序运行后，给出6个菜单项的内容和输入提示： 1通讯录链表的建
2、立 2. 通讯者结点的插入 3. 通讯者结点的查询 4. 通讯者结点的删除 5. 通讯录链表的输出 0. 退出管理系统请选择05：1.2设计分析1.2.1主控菜单函数设计分析1.实现循环和功能选择 首先编写一个主控菜单驱动程序，输入05以进入相应选择项。假设输入选择用变量sn存储，它作为menu_select函数的返回值给switch语句。使用for循环实现重复选择，并在主函数main()中实现。 实际使用时，只有选择大于5或小于0的值，程序才能结束运行，这就要使用循环控制。这里使用for循环语句实现菜单的循环选择，为了结束程序的运行，使用了“return”语句，也可以使用“exit(0);”
3、语句。2.得到sn的合理值 如前所述，应该设计一个函数用来输出提示信息和处理输入，这个函数应该返回一个数值sn，以便供给switch语句使用。假设函数名为menu_select,对于sn的输入值，在switch中case语句对应数字15，对于不符合要求的输入，提示输入错误并要求重新输入。将该函数与主函数合在一起，编译运行程序，即可检查并验证菜单选择是否正确。1.2.2功能函数设计分析1.建立通讯录链表的设计 这里实际上是要求建立一个带头结点的单链表。建立单链表有两种方法，一种称之为头插法，另一种称为尾插法。头插法是每次将新插入的结点插入在链表的表头，而尾插法是将新插入的结点插入在链表的表尾。本
4、次实验用尾插法建立链表的算法设计思想及具体算法实现。 要建立链表，首先要生成结点，因此，尾插法建立链表的算法描述如下： （1）使链表的头尾指针head、rear指向新生成的头结点（也是尾结点）； （2）置结束标志为0（假）； （3）While（结束标志不为真） P指向新生成的结点； 读入一个通讯者数据至新结点的数据域； 将新结点链到尾结点之后； 使尾指针指向新结点； 提示：是否结束建表，读入一个结束标志； （4）尾结点指针域置空值NULL。2.通讯者信息的插入 链表结点的插入，是要求将一个通讯者数据结点按其编号的次序插入有序通讯录表的相应位置，以保持通讯录表的有序性。插入结点的基本思想是：使用
5、两个指针变量p1和p2分别指向当前刚访问过的结点和下一个待访问的结点，循环顺序查找链表，寻找插入结点的位置，其中p1指向待插入位置的前一个结点。（1）用p1指向元链表的头结点，p2指向链表的第一个结点；（2）while(p2 != NULL & p2-data.num data.num) P1=p2;/p1指向刚访问过的结点； P2=p2-next;/p2指向表的下一个结点；（3）插入新结点。3.在有序表中查找指定结点在有序链表中查找指定结点的算法基本思想是：首先输入要查找的通讯者的编号或姓名，从表头顺序访问表中结点。如查找成功，则返回一个指向查找到的通讯者信息的结点；若查找失败，则返回一个空
6、的指针值NULL。当按编号查找时，如果需要查找的通讯者编号不在表中，则不一定需要循环比较到表尾，因为表是按编号递增有序的；而当按姓名查找时，则要循环比较到表尾，才能确定查不到的情况。4.通讯者记录的删除 链表上结点的删除是比较简单的，先调用查询函数，查询到要删除的结点，若没有查找到则提示“没有查找到要删除的通讯者”，若查找到根据选择删除结点即可。5.通讯录链表的输出 通讯录链表的输出只要将表头指针赋给一个指针变量p，然后用p向后扫描，直至表尾，p为空为止。1.3算法实现1.菜单选择函数具体算法实现如下：int menu_select() int sn; printf( 通讯录管理系统 n);
7、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,&sn); if (sn5) printf(nt输入错误，重选0-5: ); else break; return sn;2.建立通讯录链表具体算法实现如下：LinkList CreateList(void) Li
8、nkList head=(ListNode *)malloc(sizeof(ListNode); ListNode *p,*rear; int flag=0; rear=head; while (flag=0) p=(ListNode *)malloc(sizeof(ListNode); printf(编号(4) 姓名(8) 性别电话(11) 地址(31)n); printf(-n); scanf(%s%s%s%s%s,p-data.num,p-data.name,p-data.sex,p-data.phone,p-data.addr); rear-next=p; rear=p; printf
9、(结束建表吗?(1/0):); scanf(%d,&flag); rear-next=NULL; return head;3.通讯者信息的插入算法具体实现如下：void InsertNode(LinkList head,ListNode *p) ListNode *p1,*p2; p1=head; p2=p1-next; while (p2!=NULL & strcmp(p2-data.num,p-data.num)next;/p2指向表的下一个结点 p1-next=p;/插入p所指向的结点 p-next=p2;/连接表中剩余部分4. 在有序链表中查找指定结点算法具体实现如下：ListNode
10、 * 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(%s,num); getchar(); while (p& strcmp(p-data.num,num)next; if (p=NULL|st
11、rcmp(p-data.num,num)0) p=NULL;/没有查到要查找的通讯者 else if (xz=2) printf(请输入要查找者的姓名：); scanf(%s,name); while(p&strcmp(p-data.name,name)!=0) p=p-next; return p;5.通讯者记录的删除的算法具体实现如下：void DelNode(LinkList head) char jx; ListNode *p,*q; p=ListFind(head);/调用查找函数 if (p=NULL) printf(没有查到要删除的通讯者!n); return; printf(真
12、的要删除该结点吗?(y/n): ); scanf(%c,&jx); if (jx=y|jx=Y) q=head; while (q!=NULL & q-next!=p) q=q-next; q-next=p-next;/删除结点 free(p);/释放被删除的结点空间 printf(通讯者已被删除!n); 6.通讯录链表的输出的算法具体实现如下：void PrintList(LinkList head) ListNode *p; p=head-next;/因为带头结点，使指向链表开始结点 printf(编号 姓名 性别 电话 地址n); printf(-n); while(p!=NULL) p
13、rintf(%s%s%s%s%s,p-data.num,p-data.name,p-data.sex,p-data.phone,p-data.addr); /printf(-n); p=p-next;/后移一个结点 1.4程序代码源程序如下：/*/*主控菜单处理测试程序main2.c*/*/#include #include #include typedef struct /通讯录结点类型 char num5;/编号 char name9;/姓名 char sex3;/性别 char phone13;/电话 char addr31;/地址DataType;typedef struct node
14、/结点类型定义 DataType data;/结点数据域 struct node * next;/结点指针域ListNode;typedef ListNode * LinkList;LinkList head;/定义指向单链表的头指针ListNode *p;/定义一个指向结点的指针变量/函数说明int menu_select();/菜单选择函数LinkList CreateList(void);/尾插法建立单链表函数void InsertNode(LinkList head,ListNode *p);/在有序链表中插入结点ListNode *ListFind(LinkList head);/有
15、序链表上的查找函数void DelNode(LinkList head);/通讯录链表上结点的删除函数void PrintList(LinkList head);/通讯录链表的输出函数/主函数void main() for(;) switch(menu_select() case 1: printf(*n); printf(* 通 讯 录 链 表 的 建 立 *n); printf(*n); head=CreateList(); break; case 2: printf(*n); printf(* 通 讯 者 信 息 的 添 加 *n); printf(*n); printf(编号(4)姓名
16、(8)性别电话(11)地址(31)n); printf(*n); p=(ListNode *)malloc(sizeof(ListNode); scanf(%s%s%s%s%s,p-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); pri
17、ntf(-n); printf(%s,%s,%s,%s,%sn,p-data.num,p-data.name,p-data.sex,p-data.phone,p-data.addr); printf(-n); else printf(没查到要查询的通讯者!n); break; case 4: printf(*n); printf(* 通 讯 录 信 息 的 删 除 *n); printf(*n); DelNode(head); break; case 5: printf(*n); printf(* 通 讯 录 链 表 的 输 出 *n); printf(*n); PrintList(head)
18、; break; case 0: printf(t再 见n); return; /*菜单选择函数程序*/int menu_select() int sn; printf( 通讯录管理系统 n); 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,&sn); if
19、(sn5) printf(nt输入错误，重选0-5: ); else break; return sn;/*用尾插法建立通讯录链表函数*/LinkList CreateList(void) LinkList head=(ListNode *)malloc(sizeof(ListNode); ListNode *p,*rear; int flag=0; rear=head; while (flag=0) p=(ListNode *)malloc(sizeof(ListNode); printf(编号(4) 姓名(8) 性别电话(11) 地址(31)n); printf(-n); scanf(%s
20、%s%s%s%s,p-data.num,p-data.name,p-data.sex,p-data.phone,p-data.addr); rear-next=p; rear=p; printf(结束建表吗?(1/0):); scanf(%d,&flag); rear-next=NULL; return head;/*在通讯链表head中插入结点*/void InsertNode(LinkList head,ListNode *p) ListNode *p1,*p2; p1=head; p2=p1-next; while (p2!=NULL & strcmp(p2-data.num,p-dat
21、a.num)next;/p2指向表的下一个结点 p1-next=p;/插入p所指向的结点 p-next=p2;/连接表中剩余部分/*有序通讯录链表上的查找*/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(请输入要
22、查找者的编号：); scanf(%s,num); getchar(); while (p& strcmp(p-data.num,num)next; if (p=NULL|strcmp(p-data.num,num)0) p=NULL;/没有查到要查找的通讯者 else if (xz=2) printf(请输入要查找者的姓名：); scanf(%s,name); while(p&strcmp(p-data.name,name)!=0) p=p-next; return p;/*通讯录链表上的结点删除*/void DelNode(LinkList head) char jx; ListNode *
23、p,*q; p=ListFind(head);/调用查找函数 if (p=NULL) printf(没有查到要删除的通讯者!n); return; printf(真的要删除该结点吗?(y/n): ); scanf(%c,&jx); if (jx=y|jx=Y) q=head; while (q!=NULL & q-next!=p) q=q-next; q-next=p-next;/删除结点 free(p);/释放被删除的结点空间 printf(通讯者已被删除!n); /*通讯录链表的输出函数*/void PrintList(LinkList head) ListNode *p; p=head-
24、next;/因为带头结点，使指向链表开始结点 printf(编号 姓名 性别 电话 地址n); printf(-n); while(p!=NULL) printf(%s,%s,%s,%s,%s,p-data.num,p-data.name,p-data.sex,p-data.phone,p-data.addr); printf(n-n); p=p-next;/后移一个结点 1.5测试结果 上述源程序编译运行后显示如下菜单，等待用户选择： 选1后按“回车”，显示： 随后系统提示： 输入0继续，输入1退出建立通讯录链表，返回系统主控菜单： 若选择数不在05之间，则显示如下提示信息： 选择2实现通讯录链表的插入，插入完成又返回系统主控菜单： 选择3实现通讯录链表的查询，然后根据提示选择“按姓名查询”，完成后又返回系统主控菜单： 选择4实现通讯录链表的删除。删除通讯录信息根据提示选择查找类型，若没有查到要删除的通寻记录系统提示：查找到系统显示：完成又返回系统主控菜单：选择5实现通讯录链表的输出，完成又返回系统主控菜单：1.6结论分析 通过本章实
