数据结构课程设计实验报告 完整版Word文档格式.docx
《数据结构课程设计实验报告 完整版Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计实验报告 完整版Word文档格式.docx（48页珍藏版）》请在冰点文库上搜索。
头插法是每次将新插入的结点插入在链表的表头，而尾插法是将新插入的结点插入在链表的表尾。
本次实验用尾插法建立链表的算法设计思想及具体算法实现。
要建立链表，首先要生成结点，因此，尾插法建立链表的算法描述如下：
（1）使链表的头尾指针head、rear指向新生成的头结点（也是尾结点）；
（2）置结束标志为0（假）；
（3）While（结束标志不为真）
{
P指向新生成的结点；
读入一个通讯者数据至新结点的数据域；
将新结点链到尾结点之后；
使尾指针指向新结点；
提示：
是否结束建表，读入一个结束标志；
}
（4）尾结点指针域置空值NULL。
2.通讯者信息的插入
链表结点的插入，是要求将一个通讯者数据结点按其编号的次序插入有序通讯录表的相应位置，以保持通讯录表的有序性。
插入结点的基本思想是：
使用两个指针变量p1和p2分别指向当前刚访问过的结点和下一个待访问的结点，循环顺序查找链表，寻找插入结点的位置，其中p1指向待插入位置的前一个结点。
（1）用p1指向元链表的头结点，p2指向链表的第一个结点；
（2）while（p2!
=NULL&
&
p2->
data.num<
p->
data.num）
P1=p2;
//p1指向刚访问过的结点；
P2=p2->
next;
//p2指向表的下一个结点；
（3）插入新结点。
3.在有序表中查找指定结点
在有序链表中查找指定结点的算法基本思想是：
首先输入要查找的通讯者的编号或姓名，从表头顺序访问表中结点。
如查找成功，则返回一个指向查找到的通讯者信息的结点；
若查找失败，则返回一个空的指针值NULL。
当按编号查找时，如果需要查找的通讯者编号不在表中，则不一定需要循环比较到表尾，因为表是按编号递增有序的；
而当按姓名查找时，则要循环比较到表尾，才能确定查不到的情况。
4.通讯者记录的删除
链表上结点的删除是比较简单的，先调用查询函数，查询到要删除的结点，若没有查找到则提示“没有查找到要删除的通讯者”，若查找到根据选择删除结点即可。
5.通讯录链表的输出
通讯录链表的输出只要将表头指针赋给一个指针变量p，然后用p向后扫描，直至表尾，p为空为止。
1.3算法实现
1.菜单选择函数具体算法实现如下：
intmenu_select（）
intsn;
printf（"
通讯录管理系统\n"
）;
===============================\n"
1.通讯录链表的建立\n"
2.通讯者链表的插入\n"
3.通讯者链表的查询\n"
4.通讯者链表的删除\n"
5.通讯录链表的输出\n"
0.退出管理系统\n"
请选择0--5：
"
for（;
;
）
{
scanf（"
%d"
&
sn）;
if（sn<
0||sn>
5）
printf（"
\n\t输入错误，重选0--5:
else
break;
}
returnsn;
2.建立通讯录链表具体算法实现如下：
LinkListCreateList（void）
LinkListhead=（ListNode*）malloc（sizeof（ListNode））;
ListNode*p,*rear;
intflag=0;
rear=head;
while（flag==0）
p=（ListNode*）malloc（sizeof（ListNode））;
编号（4）姓名（8）性别电话（11）地址（31）\n"
------------------------------------\n"
%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（"
结束建表吗?
（1/0）:
"
scanf（"
flag）;
}
rear->
next=NULL;
returnhead;
3.通讯者信息的插入算法具体实现如下：
voidInsertNode（LinkListhead,ListNode*p）
ListNode*p1,*p2;
p1=head;
p2=p1->
while（p2!
=NULL&
strcmp（p2->
data.num）<
0）
p1=p2;
//p1指向刚访问过的结点
p2=p2->
//p2指向表的下一个结点
p1->
//插入p所指向的结点
next=p2;
//连接表中剩余部分
4.在有序链表中查找指定结点算法具体实现如下：
ListNode*ListFind（LinkListhead）
ListNode*p;
charnum[5];
charname[9];
intxz;
========================\n"
1.按编号查询\n"
2.按姓名查询\n"
请选择：
p=head->
//假定通讯录表带头结点
scanf（"
xz）;
if（xz==1）
请输入要查找者的编号：
%s"
num）;
getchar（）;
while（p&
strcmp（p->
data.num,num）<
p=p->
if（p==NULL||strcmp（p->
data.num,num）>
p=NULL;
//没有查到要查找的通讯者
else
if（xz==2）
{
请输入要查找者的姓名：
name）;
while（p&
strcmp（p->
data.name,name）!
=0）
p=p->
}
returnp;
5.通讯者记录的删除的算法具体实现如下：
voidDelNode（LinkListhead）
charjx;
ListNode*p,*q;
p=ListFind（head）;
//调用查找函数
if（p==NULL）
没有查到要删除的通讯者!
\n"
return;
真的要删除该结点吗?
（y/n）:
%c"
jx）;
if（jx=='
y'
||jx=='
Y'
q=head;
while（q!
q->
next!
=p）
q=q->
q->
next=p->
//删除结点
free（p）;
//释放被删除的结点空间
通讯者已被删除!
6.通讯录链表的输出的算法具体实现如下：
voidPrintList（LinkListhead）
//因为带头结点，使指向链表开始结点
编号姓名性别电话地址\n"
while（p!
=NULL）
//printf（"
p=p->
//后移一个结点
1.4程序代码
源程序如下：
/*****************************/
/*主控菜单处理测试程序main2.c*/
#include<
stdio.h>
string.h>
stdlib.h>
typedefstruct{//通讯录结点类型
//编号
//姓名
charsex[3];
//性别
charphone[13];
//电话
charaddr[31];
//地址
}DataType;
typedefstructnode{//结点类型定义
DataTypedata;
//结点数据域
structnode*next;
//结点指针域
}ListNode;
typedefListNode*LinkList;
LinkListhead;
//定义指向单链表的头指针
ListNode*p;
//定义一个指向结点的指针变量
//函数说明
intmenu_select（）;
//菜单选择函数
LinkListCreateList（void）;
//尾插法建立单链表函数
voidInsertNode（LinkListhead,ListNode*p）;
//在有序链表中插入结点
ListNode*ListFind（LinkListhead）;
//有序链表上的查找函数
voidDelNode（LinkListhead）;
//通讯录链表上结点的删除函数
voidPrintList（LinkListhead）;
//通讯录链表的输出函数
//主函数
voidmain（）
for（;
switch（menu_select（））
case1:
*********************************\n"
*通讯录链表的建立*\n"
head=CreateList（）;
case2:
*通讯者信息的添加*\n"
编号（4）姓名（8）性别电话（11）地址（31）\n"
p=（ListNode*）malloc（sizeof（ListNode））;
InsertNode（head,p）;
case3:
*通讯录信息的查询*\n"
p=ListFind（head）;
if（p!
{
printf（"
编号姓名性别电话地址\n"
----------------------------\n"
%s,%s,%s,%s,%s\n"
else
没查到要查询的通讯者!
case4:
*通讯录信息的删除*\n"
DelNode（head）;
case5:
*通讯录链表的输出*\n"
PrintList（head）;
case0:
\t再见\n"
return;
/*菜单选择函数程序*/
/*用尾插法建立通讯录链表函数*/
/*在通讯链表head中插入结点*/
/*有序通讯录链表上的查找*/
/*通讯录链表上的结点删除*/
/*通讯录链表的输出函数*/
{printf（"
%s,%s,%s,%s,%s"
\n------------------------------------\n"
1.5测试结果
上述源程序编译运行后显示如下菜单，等待用户选择：
选1后按“回车”，显示：
随后系统提示：
输入0继续，输入1退出建立通讯录链表，返回系统主控菜单：
若选择数不在0—5之间，则显示如下提示信息：
选择2实现通讯录链表的插入，插入完成又返回系统主控菜单：
选择3实现通讯录链表的查询，然后根据提示选择“按姓名查询”，完成后又返回系统主控菜单：
选择4实现通讯录链表的删除。
删除通讯录信息根据提示选择查找类型，若没有查到要删除的通寻记录系统提示：
查找到系统显示：
完成又返回系统主控菜单：
选择5实现通讯录链表的输出，完成又返回系统主控菜单：
1.6结论分析
通过本章实
升级会员 