城市链表实验报告

1、城市链表实验报告2014-2015学年第一学期实验报告课程名称：算法与数据结构实验名称：城市链表一、实验目的本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。同时，通过本次实验帮助学生复习高级语言的使用方法。二、实验内容(一)城市链表：将若干城市的信息存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名与位置坐标进行有关查找、插入、删除、更新等操作。(二)约瑟夫环m的初值为20;密码:3,1,7,2,6,8,4(正确的结果应为6,1,4,7,235)。三、实验环境VS2010、win8、1四、实验结果(一)

2、城市链表：(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、更

3、新城市信息模块6、删除信息模块。+voidIixLt-Li£-t_SqCity(citylist+voidInsert_sQCityfcitylist*L)|j+voidCreate,sqCity(citylist*1)+1voidCet_s1C1+5C0ard(cit.ylist*L).一+voidi-tyNanije(.citylitdaubl?doubley1).,.itvoidDelete,sqCity(citylist/)|+ivoidFindCityDistance(cityList礼)；,；+JvoidUpdate_sqCit7(city1ist*L)：.r*i4/*t

4、5、3算法5、3、1根据中心城市坐标，返回在距离内的所有城市：voidFindCityDistance(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("城市名称%sn",L->Name);printf("城市坐标2lf,%、2lfn",L->x,L->y)

5、;L=L->next;该算法主要用到了勾股定理，考虑到不需要实际数值，只需要大小比较，所以只用横坐标差的平方+纵坐标差的平方<二距离的平方判定。因中心城市本身也在判定范围之内，所以添加了判定条件横纵坐标差的与不能为零。5、3、2主程序中循环条件判定：for(;)printf("请选择您的操作n");printf("1、创建城市链表n");printf("2、根据名字查询城市n");printf("3、插入n");printf("4、删除n");printf("5、更新城市信

6、息n");printf("6、根据离中心坐标距离查瞧城市n");printf("7、退出系统n");scanf("%d",&choice);switch(choice)/case语句case7:break;if(choice=7)break;若用户选择了退出系统选项，则首先跳出switch在跳出for循环结束程序。开始5、4流程图5、5程序源代码typedefstructcitylistcharName20;double x,y;citylist *next;选择操作citylist,*L;voidInitList_

7、SqCity(citylist*L)创建/初始化节点L->next = NULL;if (!newNode)printf（"存储分配失败"）；、printf（"请输入城市名n"）;就正否退.7由scanf("%s",newNode->Name);山printf("请输城市坐标xyn");scanf("%lf%lf",&(newNode->x),&(newNode->y);while (L->next != NULL)结束_L=L->next;/

8、如果非空，L指针的位置向后移newNode->next=L->next;L->next=newNode;voidCreate_sqCity(citylist*L)/创建链表charch100;inti;printf("输入END1出，输入其余值继续n");/当输入END寸，在任意输入，则退出此操作scanf("%s",ch);for(;strcmp(ch,"END")!=0;)Insert_sqCity(L);printf("输入END1出，输入其余值继续n");scanf("%s&qu

9、ot;,ch);voidGet_sqCityCoord(citylist*L)/输入城市信息返回坐标charch10;printf("输入要查询的城市")；scanf("%s",ch);while(L->next!=NULL&&strcmp(L->next->Name,ch)L=L->next;if(L->next=NULL)|printf("城市不存在")；elseprintf("%、2lf,%、2lfn",L->next->x,L->next-&g

10、t;y);voidDelete_sqCity(citylist*L)/删除城市信息，按名称/坐标printf("请输入城市名n");charch10;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("删除城市成功");voidFin

11、dCityDistance(citylist*L)/根据距离输出城市printf("输入中心城市坐标");doublex1,y1;scanf("%lf%lf",&x1,&y1);printf("输入距离");doubledis;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)+

12、(L->y-y1)!=0)printf("城市名称sn",L->Name);printf("城市坐标%2lf,%、2lfn",L->x,L->y);L=L->next;voidUpdatesqCity(citylist*L)/更新城市信息charch10;printf("请输入您要更新的城市名n");scanf("%s",ch);while(strcmp(L->next->Name,ch)L=L->next;if(L->next=NULL)printf(&quo

13、t;城市不存在n");printf("请输入城市新信息：n");printf("请输入城市新名n");scanf("%s",L->next->Name);printf("请输入城市新坐标n");scanf("%lf%lf",&(L->next->x),&(L->next->y);intmain()citylist*L;L=(citylist*)malloc(sizeof(citylist);InitListSqCity(L);for(

14、;)printf("nprintf("请选择您的操作n");printf("1、创建城市链表n");printf("2、根据名字查询城市n");printf("3、插入n");printf("4、删除n");printf("5、更新城市伯息n");|printf("6、根据离中心坐标距离查瞧城市n");printf("7、退出系统n");printf("nintchoice;scanf("%d",

15、&choice);switch(choice)Icase1:CreatesqCity(L);getchar();break;case2: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;|case7:break;if(choice=7)|break;I5、6仿真结果巾心里标距离查看城市色里入城市名请输入城市坐标2、查询城市信息近入END退

16、出，输入HEXT维续疝入城市名1U印请输入城市坐标x y箭入END退出.输入NESI继绫能入END退出.输入NEST继续浦人要查询的城市：山东您苧查询的城市山东坐标是.2-00,2.003添加城市庙理5入城市名夫建一-清丽，一城市土化ky33添加成功4删除城市醯人要删除的城市名除要册(I除的城市是】天津删除城市成功情入您要更新的城市名请输人被市防坐标 更新地小信息成功5更新城市6根据距离输出城市5、7调试心得5、7、1错误分析：实验中出现的第一个问题就是声明变量，从键盘中读入数据就是显示变量未初始化，调试后发现就是scanf的问题，以后的实验中应注意scanf中读入信息后就是存到了地址里。5、

17、7、2算法复杂度的分析：所有程序除了InitList_SqCity复杂度为0(1),其余均为O(n)。5、7、3收获对数据结构这门课地应用有了一定地了解，知道对线性表插入、删除等操作的实现加深对课本地理解。附录约瑟夫环：5、1问题分析该实验要求循环连续查找信息，并删除节点，故使用单项循环链表。5、2设计方案1、建立单循环链表2、产生Joseph环3、输出顺序表5、3算法5、3、1构成单链表voidCreat_JoephLink(intnum)Node*head,*q,*L;L=(Node*)malloc(sizeof(Node);/申请第一个数的节点head=L;L->num=1;pri

18、ntf("输入第一个人的值：")；输入第一个人的值scanf("%d",&(L->value);inti;for(i=2;i<=num;i+)q=(Node*)malloc(sizeof(Node);L->next=q;L=q;printf("输入第dj人的值:",i);/输入每个人的值scanf("%d",&(L->value);L->num=i;L->next=head;L=head;/构成单向循环链表5、3、2查找并删除节点StatusDelete_Node

19、(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源程序代码typedefstructNodeintvalue;Node*next;int

20、num;Node;voidCreat_JoephLink(intnum)Node*head,*q,*L;L=(Node*)malloc(sizeof(Node);/申请第一个数的节点head=L;L->num=1;printf("输入第一个人的值：")；输入第一个人的值scanf("%d",&(L->value);|inti；for(i=2;i<=num;i+)q=(Node*)malloc(sizeof(Node);L->next=q;L=q;lprintf("输入第dj人的值:",i);/输入每个人的值scanf("%d",&(L->value);L->num=i;L->next=head;L=head;/构成单向循环链表intm;intj；printf("输入初始值m的大小")；scanf("%d",&m);printf(&qu