城市链表实验报告

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

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。五、 附录城市链表：问题分析该实验要求对链表实现创建，遍历，插入，删除，查询等操作，故使用单链表。设计方案该程序大致分为以下几个模块：1. 创建城市链表模块，即在空链表中插入新元素。故创建城市链表中包涵插入模块。2.

3、 返回位置坐标模块。3. 计算距离模块4. 插入模块。5. 更新城市信息模块6. 删除信息模块。+ void Irxit-Lis-t_Sc4City (citylist *L) , , , Flvoid Insert.sqCityfcitylist *1) " +.+ void Create,£QCity(citylist *D .1+jvoid Cet_5iCi+5*Co*i?d*L) I .司void Geft_sq,CityMante (.citylit L；. dauble double y 1) it void Dele_sqCity(city 1 ist ) .

4、f+lvoid FindCityDistance (citylist *L)+J vo i d Update_ sqCity (c ity 1 ist* L):.算法根据中心城市坐标，返回在距离内的所有城市：void FindCityDistance（citylist *L）l f,%.2吊n",L->x,L->y）;L=L->next;该算法主要用到了勾股定理，考虑到不需要实际数值，只需要大小比较，所以只用 横坐标差的平方+纵坐标差的平方 <二距离的平方判定。因中心城市本身也在判定范围之内，所以添加了判定条件横纵坐标差的和不能为零。主程序中循环条件判定：fo

5、r （ ； ； ）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);lf,%.2lfn&quo

6、t;switch (choice),L->next->>xiL2>next->y);void Delete sqCity(citylist *L)作选择操 退出lf,%.2lfn",L->x,L->y);printf("3.插入 n");printf("4.删除 n");printf("5.更新城市信息n");printf("6.根据离中心坐标距离查看城市n");printf("7.退出系统 n");printf( "n")

7、;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更新

8、城市7曩询操链查的曳子你诫息坐信小-统 城累 Mis断人END退出.输入继绫 Hext 他入城市名 ，青黠入城市坐标* y输入END退出.输入NESI继续MEMT5步入城市名1青瑜入城市坐标x v输入END退出,输入HEST醴续END2.查询城市信息输入要查询的城市二山东您要查询的城市山东坐标是：2.00,2.003添加城市青埔入城市名天京请输入城市坐标”*添加成功4删除城市鞭人要删除的城市名会要删除的城市是.天津删除城市成功曾输入您要更新的城市名iF-=富喜大城市新坐标更新城市信息成功6根据距离输出城市11调试心得错误分析：实验中出现的第一个问题是声明变量，从键盘中读入数据是显示变量未初始化

9、，调试后发现是scanf的问题，以后的实验中应注意scanf中读入信息后是存到了地址里。算法复杂度的分析：所有程序 除了 InitList_SqCity复杂度为0(1),其余均为O(n)。收获对数据结构这门课地应用有了一定地了解，知道对线性表插入、删除等操作的实现，加深对课本地理解。附录约瑟夫环：问题分析该实验要求循环连续查找信息，并删除节点，故使用单项循环链表。设计方案1 .建立单循环链表2 .产生Joseph环3 .输出顺序表算法 构成单链表void Creat JoephLink(int num)Node *head,*q,*L;L=(Node*)malloc(sizeof(Node);

10、/申请第一个数的节点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;

11、/构成单向循环链表查找并删除节点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)；源程序代码typ

12、edef 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->n

13、ext=q;L=q；printf(" 输入第dj人的值:",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->nu

14、m);/ 输出当前节点信息/删除当前节点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);运行结果4F, - -)-1 7 2 £ 8 4 IP 一 二 二 <<喷大-JI 二-rrtsl 一- LJ 打二An 2 3 4 5 6? tA-:一第第第第笫第、.正 :入人