数据结构课程设计实验报告
实验一链表部分选题为：2.4.3—城市链表1、需求分析
（1）创建一个带有头结点的单链表。
（2）结点中应包含城市名和城市的位置坐标。
（3）对城市链表能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。
（4）能够对每次操作后的链表动态显示。
2、概要设计
为了实现以上功能，可以从以下3个方面着手设计。
（1）主界面设计
为了实现城市链表相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以系统的各项子功能，方便用户使用本程序。本系统主控菜单运行界面如下所示。
（2）存储结构设计
本系统主要采用链表结构类型来表示存储在“城市链表”中的信息。其中链表结点由4个分量组成：城市名name、城市的横坐标posx、城市的纵坐标posy、指向下一个结点的指针next。
（3）系统功能设计
本程序设计了9个功能子菜单，其描述如下：
①建立城市链表。由函数creatLink()实现。该功能实现城市结点的输入以及连
接。
②插入链表记录。由函数insert()实现。该功能实现按坐标由小到大的顺序将结
点插入到链表中。
③查询链表记录。由searchName（）函数和searchPos（）函数实现。其中
searchName（）实现按照城市名查询的操作，searchPos（）实现按照城市坐标查询的操作。
④删除链表记录。由delName（）函数和delPos（）函数实现。其中delName
（）函数实现按照城市名删除的操作，delPos（）函数实现按照城市坐标删
除的操作。
⑤ 显示链表记录。由printList （）函数实现。该功能实现格式化的链表输出操作，可以显示修改后的链表状态。
⑥ 更新链表信息。由update （）函数实现。该功能实现按照城市名更新城市的坐标信息。
⑦ 返回城市坐标。由getPos （）函数实现。该功能实现给定一个已存储的城市，返回其坐标信息的操作。
⑧ 查看与坐标P 距离小于等于D 的城市。由getCity （）函数实现。该功能实现返回与给定坐标P 距离小于等于D 的城市名称。
⑨ 退出链表系统。由exit （0）实现。
3、 模块设计
（1）模块设计
本程序包含两个模块：主程序模块和链表操作模块。其调用关系如下图所示：
（2）系统子程序及功能设计
本系统共设置3个子程序，各程序的函数名及功能说明如下：
① Linklist creatLink() //创建一个城市链表，返回头结点地址
② printList(Linklist L) // 打印头结点地址为L 的城市链表
③ int searchName(Linklist L,char name[20]) //以城市名查找
④ int searchPos(Linklist L,int px,int py) //以城市坐标查找
⑤ int insert(Linklist L,Linklist city) //插入
⑥ int delName(Linklist L,char name[20]) //利用城市名称删除
⑦ int delPos(Linklist L,int px,int py) //利用坐标删除
⑧ int update(Linklist L,char name[20]) //更新
⑨ int getPos(Linklist L,char name[20]) //给定一个城市名,返回城市坐标
⑩ int getCity(Linklist L,int px,int py,int d) //给定一个城市坐标P,返回距离小于等于d 的城市
? void main() //主函数，实现链表各项操作的选择
（3）函数主要调用关系图
本系统3个子程序之间的主要调用关系如图所示。
4、详细设计
（1）数据类型定义
typedef struct LNode{//城市结点
char name[20];
int posx;//横坐标
int posy;//纵坐标
struct LNode *next;
}LNode,*Linklist;
（2）系统主要子程序详细设计
①建立城市链表
Linklist creatLink() //创建一个城市链表，返回头结点地址
{
Linklist L=(Linklist)malloc(LEN); //头结点
L->next=NULL;
Linklist p;
char name[20];
int px;
int py;
char end[4]="end";
printf("请输入城市名称、横坐标和纵坐标，建立城市链表，以'end'为输入结束标志\n");
printf("请输入城市名称：");
scanf("%s",name);
while (strcmp(name,end))
{
printf("请输入横坐标x: ");
scanf("%d",&px);
printf("请输入纵坐标y：");
scanf("%d",&py);
p=(Linklist)malloc(LEN); //新结点
strcpy(p->name,name);
p->posx=px;
p->posy=py;
insert(L,p); //插入新结点
printf("请输入城市名称：");
scanf("%s",name);
}
return(L);
}
②插入链表记录
int insert(Linklist L,Linklist city){//插入
Linklist p=L->next;
Linklist p_prior=L;
while(p!=NULL && city->posx>=p->posx)
{
if(p->posx==city->posx && p->posy==city->posy)
{
printf("重复输入！\n");return 0;
}
p=p->next;
} //确定city插入的位置
while(p_prior->next!=p)
{
p_prior=p_prior->next;
}
if(p==NULL)
{
p=p_prior;
city->next=NULL;
p->next=city;
}
else //若为空表，插到头结点之后
{
p=p_prior;
city->next=p->next;
p->next=city;
}
return 1;
}
③按名称删除链表记录
int delName(Linklist L,char name[20]){//利用城市名称删除int flag=0;
int seat=1;
Linklist p=L;
if(p->next==NULL)
printf("该链表中没有元素,删除失败\n");
else
{
while(p->next!=NULL)
{
if(!strcmp(p->next->name,name))
{
flag=1;
printf("城市%s 被删除\n",name);
Linklist q=p->next;
p->next=q->next;
free(q);
}
else {p=p->next;}
}
}
return flag;
}
5、测试分析
（1）实验中遇到的问题以及对设计与实现的回顾讨论和分析
①城市链表在开始的建立时，由于头结点指针的判断错误，导致链表头结点中
存有信息，而在后面的插入和删除操作中并未考虑到，导致链表记录出错，指针错位。
②在链表的删除过程中，由于删除的时判断的结点，故应找到起前驱指针，一
开始并未考虑到这些，在无法删除的时候才想起来改进方法，后来设置了一个prior指针，专门找到对应结点的前驱，方便删除操作。
③课题拓展训练为为城市加入其他信息，如人口数等。考虑到此项添加仅是在
数据定义中再加入一个数据项，为了方便实验进行与演示，就没有进行扩展。
如需实现，可在Lnode的定义中，加入int num等语句。
④链表建立初期，个人的想法是按照新增结点插入按顺序插入到链表中，删除
时可以按照城市名称和城市坐标进行删除。在具体的实现过程中，使用了菜单选择的方法，方便用户使用系统。
（2）算法的时空分析
算法使用动态分配空间的方式执行，故其执行时间与链表记录个数有关，如果有n个城市结点，其时间复杂度为O（n）。
（3）经验和体会
通过本次实验，对于链表部分的相关功能，如插入、删除、排序等相关算法进一步熟悉了。能够利用所学知识，解决相关问题，并能够正确解决实验过程中出现的差错。
（4）测试功能展示
①城市链表的建立
在主菜单下，用户输入1并回车，然后按照提示建立城市链表，运行结果如下所示：
②插入链表记录
③查询链表记录：
④删除链表记录