城市链表实验报告.doc

2014-2015学年
第一学期实验报告
课程名称： 算法与数据结构
实验名称： 城市链表
一、 实验目的
本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉 各种链表的操作为侧重点。同时，通过本次实验帮助学生复习高级语言的使用方法。
二、 实验内容
（一）城市链表 ：
将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城 市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作.
（二) 约瑟夫环
m 的初值为 20；密码:3，1,7，2,6，8，4(正确的结果应为 6，1,4，7，2，3，5）.三、 实验环境
VS2010 、win8。1
四、 实验结果
(一）城市链表:
（1） 创建城市链表；
（2） 给定一个城市名,返回其位置坐标;
（3） 给定一个位置坐标 P 和一个距离 D，返回所有与 P 的距离小于等于 D 的城市。
（4） 在已有的城市链表中插入一个新的城市;
（5） 更新城市信息；
（6） 删除某个城市信息。
（二） 约瑟夫环
m 的初值为 20;密码:3，1,7,2，6,8,4
输出 6，1，4,7，2，3,5。
五、 附录
城市链表：
5。1 问题分析
该实验要求对链表实现创建,遍历,插入,删除,查询等操作,故使用单链表.
5.2 设计方案
该程序大致分为以下几个模块:
1。创建城市链表模块，即在空链表中插入新元素。故创建城市链表中包涵插入模块。
2。返回位置坐标模块。
3。计算距离模块
4。插入模块。
5。更新城市信息模块
6。删除信息模块.
5.3 算法
5.3。1 根据中心城市坐标,返回在距离内的所有城市：
void FindCityDistance（citylist *L）｛
//根据距离输出城市
……//输入信息与距离
L=L->next；
while(L != NULL）{
if（((L—〉x—x1）*(L—〉x—x1)+（L—>y-y1)＊（L->y—y1）〈=dis＊dis)&＆（((L—〉x-x1）+（L-〉y-y1））！=0 ））｛
printf（"城市名称％s\n",L—〉Name）；
printf（"城市坐标%.2lf,%。2lf\n”，L—>x,L->y）；
}
L=L->next;
｝
}
该算法主要用到了勾股定理,考虑到不需要实际数值,只需要大小比较,所以只用
横坐标差的平方+纵坐标差的平方 〈= 距离的平方 判定。
因中心城市本身也在判定范围之内，所以添加了判定条件横纵坐标差的和不能为零.
5.3。2
主程序中循环条件判定：
for（ ; ; )｛
printf（"请选择您的操作\n");
printf（”1。创建城市链表\n”);
printf(”2。根据名字查询城市\n")；
printf（"3。插入\n”);
printf（"4。删除\n”）;
printf("5.更新城市信息\n"）；
printf("6。根据离中心坐标距离查看城市\n”）;
printf（”7.退出系统\n"）;
scanf（"%d"，＆choice);
switch(choice）｛
……//case语句
case 7:break;
}
if（choice == 7)
break;
｝
若用户选择了退出系统选项，则首先跳出switch 在跳出for循环结束程序。
否

结束
是

是否退出
退出
插入
删除
更新
距离
5.4流程图
查询
创建
开始
选择操作

5。5程序源代码
typedefstruct citylist ｛
char Name[20];
double x,y;
citylist ＊next；
｝citylist， ＊L；
void InitList_SqCity（citylist ＊L）｛
//初始化节点
L—〉next = NULL;
｝
void Insert_sqCity(citylist *L）{
//在链表中插入元素
citylist* newNode；
newNode=（citylist＊)malloc（sizeof（citylist）)；
if(!newNode）
printf(”存储分配失败”);
printf（"请输入城市名\n”）；
scanf(”％s”,newNode—>Name);
printf(”请输城市坐标x y\n");
scanf（”％lf％lf”，&（newNode—>x)，&（newNode—〉y))；
while（L—〉next ！= NULL){
L = L—>next；
｝//如果非空,L指针的位置向后移
newNode—>next =L->next；
L—>next = newNode；
}
void Create_sqCity（citylist ＊L）｛
//创建链表char ch［100］；
int i；
printf(”输入END退出，输入其余值继续\n”）； //当输入END时，在任意输入，则退出此操作
scanf(”％s”，ch）;
for（；strcmp(ch,"END”）！=0 ； ）{
Insert_sqCity(L)；
printf(”输入END退出,输入其余值继续\n”)；
scanf（”％s",ch）；
｝
}
void Get_sqCityCoord（citylist ＊L）｛
//输入城市信息返回坐标
char ch［10］；
printf（”输入要查询的城市”);
scanf（"%s”，ch）;
while（L—>next!= NULL ＆＆strcmp（L—>next-〉Name，ch）)｛
L=L—〉next；
}
if(L—〉next == NULL）
printf（"城市不存在”）；
else｛
printf（”％。2lf，％。2lf\n"，L-〉next-〉x,L—〉next—〉y);
｝
}
void Delete_sqCity（citylist ＊L）｛
//删除城市信息 ，按名称/坐标
printf("请输入城市名\n"）;
char ch［10］；
scanf(”%s”,ch)；
while（L—〉next ！= NULL&＆strcmp（L—>next—>Name,ch)）｛
L=L-〉next;
｝
if（L—>next == NULL）
printf（”城市不存在”）;//删除位置不合理
L—>next=L->next—>next;
printf(”删除城市成功”);
}
void FindCityDistance（citylist ＊L){
//根据距离输出城市
printf（”输入中心城市坐标"）；
double x1，y1；
scanf（”％lf％lf"，＆x1,＆y1）;
printf(”输入距离"）；
double dis；
scanf（"%lf"，＆dis)；
L=L-〉next；
while（L ！= NULL）｛
if（(（L—〉x—x1)＊(L-〉x-x1)+(L—〉y—y1)＊（L—>y—y1）〈=dis＊dis）＆&((（L—>x-x1）+（L—〉y—y1））！=0 )){
printf（”城市名称％s\n",L—>Name）;
printf(”城市坐标%。2lf，%。2lf\n”，L—〉x，L—>y）； ｝
L=L—>next;
｝
｝
void Update_sqCity（citylist＊ L）｛
//更新城市信息
char ch［10］；
printf（"请输入您要更新的城市名\n”)；
scanf("％s”，ch）；
while（strcmp(L—>next-〉Name，ch））｛
L=L—〉next；
}
if（L—〉next == NULL）
printf("城市不存在\n"）；
printf（”请输入城市新信息：\n");
printf(”请输入城市新名\n”）;
scanf（"％s”，L-〉next—>Name）；
printf（”请输入城市新坐标\n"）； scanf（”％lf％lf"，＆（L-〉next—〉x),&（L-〉next—>y）)；
}
int main（）｛
citylist ＊L；
L=（citylist*)malloc(sizeof(citylist)）；
InitList_SqCity（L）；
for（ ； ； ）{
printf（”———-————-———-—-———--—--——--———-——--\n"）；
printf（”请选择您的操作\n”)；
printf（”1。创建城市链表\n")；
printf(”2。根据名字查询城市\n"）;
printf(”3。插入\n”）;
printf（”4。删除\n”）；
printf("5。更新城市信息\n”);
printf(”6.根据离中心坐标距离查看城市\n”);
printf("7。退出系统\n”)； printf(”-———--—-———-—-—————--——-—————-——-—-\n”)；
int choice；
scanf（"％d”,&choice）;
switch（choice){
case 1：
Create_sqCity（L）；
getchar（）;
break;
case 2：
Get_sqCityCoord（L);
break；
case 3:
Insert_sqCity(L）；
break；
case 4：
Delete_sqCity（L）；
break;
case 5：
Update_sqCity（L）；
break；
case 6：
FindCityDistance（L）;
break；
case 7:break;
｝
if（choice == 7)
break；
｝
}
5。6仿真结果
2。查询城市信息
3 添加城市
4 删除城市
5 更新城市
6 根据距离输出城市
5。7 调试心得
5。7。1错误分析:
实验中出现的第一个问题是声明变量，从键盘中读入数据是显示变量未初始化，调试后发现是scanf的问题，以后的实验中应注意scanf中读入信息后是存到了地址里.
5。7.2 算法复杂度的分析：
所有程序 除了InitList_SqCity 复杂度为O（1），其余均为O（n）。
5。7。3 收获
对数据结构这门课地应用有了一定地了解,知道对线性表插入、删除等操作的实现，加深对课本地理解.
附录
约瑟夫环:
5。1问题分析
该实验要求循环连续查找信息,并删除节点，故使用单项循环链表。
5.2设计方案
1。建立单循环链表
2。产生Joseph环
3。输出顺序表
5。3算法
5.3。1 构成单链表
void Creat_JoephLink（int num）｛
Node ＊head，＊q，＊L;
L=(Node＊）malloc(sizeof（Node））；//申请第一个数的节点
head=L;
L-〉num=1;
printf(”输入第一个人的值:”）; //输入第一个人的值
scanf（"%d”,＆（L-〉value））；
int i;
for(i=2;i〈=num;i++）{
q=（Node*）malloc（sizeof（Node）);
L—〉next=q；
L=q；
printf（"输入第%d个人的值:”，i）; //输入每个人的值
scanf（”％d”,&（L—〉value）)；
L->num=i；
｝
L—〉next=head;
L=head;//构成单向循环链表
｝
5。3.2查找并删除节点
Status Delete_Node(Node ＊L)｛
for （j=1；j〈=num;j++）｛
for（i=1；i〈m;i++）｛//i做循环变量
L=L—〉next；
｝
m=L—〉value;//将当前值设为m值
printf(”％d "，L—〉num）；//输出当前节点信息
//删除当前节点
L—〉num=L—>next-〉num；
L—>value=L->next-〉value;
q=L—>next;
L—〉next=L-〉next—〉next;
free(q）；
｝
}
5。4源程序代码
typedef struct Node{
int value;
Node ＊next；
int num;
｝Node；
void Creat_JoephLink（int num）{
Node *head，*q，＊L；
L=（Node＊)malloc（sizeof（Node））；//申请第一个数的节点
head=L；
L-〉num=1；
printf（”输入第一个人的值："）； //输入第一个人的值
scanf(”％d”，&(L-〉value)）；
int i;
for（i=2；i〈=num；i++)｛
q=（Node＊)malloc(sizeof(Node））;
L->next=q；
L=q；
printf（”输入第％d个人的值：”,i）; //输入每个人的值
scanf("%d”,＆(L—〉value)）；
L-〉num=i;
｝
L—>next=head;
L=head；//构成单向循环链表
int m；
int j；
printf（”输入初始值m的大小”）；
scanf（"%d”，&m)；
printf（"结果是：\n")；
for (j=1；j〈=num；j++）{
for(i=1；i〈m;i++）{//i做循环变量
L=L—>next;
｝
m=L—〉value；//将当前值设为m值
printf（”％d ",L—〉num)；//输出当前节点信息
//删除当前节点
L-〉num=L->next—〉num;
L—〉value=L—>next—〉value；
q=L—>next;
L—〉next=L—〉next-〉next；
free(q)；
}
｝
int main（）｛
int num；
printf（”输入人数：”); /*输入测试人的数量＊/
scanf(”％d”，＆num）；
Creat_JoephLink（num）；
｝
5。5运行结果
5.6调试心得
5。6。1错误分析
查找到第m个节点删除时出错,显示有未处理的异常,是因为节点赋值的时候有问题。
5。6.2 收获
从开始构建循环链表然后实现约瑟夫环功能的过程中,中途也遇见一些问题，但都逐一克服，整个过程进展不是很顺利，都是不停的调试，实验之后,我还对数据结构这门课有了一定的认识.在解决一个具体问题时，常常需要从具体问题中抽象出一个模型，也就是抽象数据类型,然后设计一个解决这个模型的算法。再通过其算法编出程序，进行调试、调整直至得到最终解答。