城市链表实验报告

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

2、in8.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 .创建城市链表模块，即在空链表中插入新元素。故创建城市链表中包涵插入

3、模块。2 .返回位置坐标模块。3 .计算距离模块4 .插入模块。5 .更新城市信息模块6 .删除信息模块。+ void InitList_SqCity(citylist *L)±void Insert_sqCity(citylist *L)| +lvcid Create_sqCity(citylist *L)+void Get_sqCityCoord(citylist *L)+：void Get_sqCityNane (citylist *L, double xl, double yl) 一:+void Delete_sqCity(citylist *L) | +：void Find

4、CityDistance (citylist *L)+ void Update_sqCity(citylist* L) . 一,k1八15.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("城

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

6、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 流程图开始选择操

7、作创建查询插入Y退出删除更新是否退出是结束5.5 程序源代码typedef struct citylist char Name20;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("存储分配失败&q

8、uot;)；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 sqC

9、ity(citylist *L)/ 创建链表char ch100;int i;printf("输入END1出，输入其余值继续n" ); /当输入END寸，在任意输入，则退出此操作 scanf( "%s",ch);for (;strcmp(ch, "END")!=0 ; )Insert sqCity(L);printf("输入END1出，输入其余值继续n");scanf( "%s",ch);void Get sqCityCoord(citylist *L)/输入城市信息返回坐标char ch10;

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,%.2lfn" ,L->next->x,L->next->y);void Delete_sqCity(citylist *L)/删除城市信息，按名称/坐

11、标 printf(" 请输入城市名n");char ch10;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)/根据距离输出城市pr

12、intf("输入中心城市坐标");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(&qu

13、ot;城市名称 sn",L->Name);printf(" 城市坐标 %.2lf,%.2lfn",L->x,L->y);L=L->next;void Update_sqCity(citylist* L)/更新城市信息char ch10;printf("请输入您要更新的城市名n");scanf( "%s",ch);while (strcmp(L->next->Name,ch)L=L->next;if (L->next = NULL)printf("城市不存在n"

14、;);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 ( ; ;

15、 )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;s

16、canf( "%d",&choice);switch (choice)case 1:Create_sqCity(L);getchar();break;case 2:Get sqCityCoord(L);break;case 3:Insert_sqCity(L);FindCityDistance(L);break;case 7: break;if (choice = 7) break;5.6仿真结果2,查询城市信息,烂查询的城市工您葭查询的城市山东坐标是：2-00-2-003添加城市请舶入城市名请睛入城市坐标乂 y3 3添加成功4删除城市尊人要删除的城市名除要删除的城

17、市是；天津删除城市成功5更新城市斗晅人您要更新的城市名 降灌藕翳, *输入城市新坐标 翁湖市信息成功6根据距离输出城市输入中心城市坐标1 1中心城市为北京 输入距嵩 地名群济南 域币坐标2 始,2 西5.7调试心得5.7.1 错误分析：实验中出现的第一个问题是声明变量，从键盘中读入数据是显示变量未初始化，调试后发现是scanf的问题，以后的实验中应注意scanf中读入信息后是存到了地址里。5.7.2 算法复杂度的分析：所有程序 除了 InitList_SqCity复杂度为0(1),其余均为O(n)。5.7.3 收获对数据结构这门课地应用有了一定地了解，知道对线性表插入、删除等操作的实现，加深对

18、课本地理解。附录约瑟夫环: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(

19、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 查找并删除节点Status Delete Node(Node *L)for (j=1;j<=num;j+)for(i=1;i<m;i+)/i做循环变量L=L->next;m=L->va

20、lue;/ 将当前值设为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*)ma

21、lloc(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("输入第dj人的值:",i); /输入每个人的值scanf("%d",&(L->value);L->num=i;L->next=head;L=head;/构成单向循环链表 int m;int j;printf("输入初始值m的大小")；scanf("%d",&