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;w hile(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程序源代码typedef struct 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中读入信息后是存到了地址里。