2022年城市链表实验报告.pdf

《2022年城市链表实验报告.pdf》由会员分享，可在线阅读，更多相关《2022年城市链表实验报告.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、 、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、创建城市链表模块,即在空链表中插

3、入新元素。故创建城市链表中包涵插入模块。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 10 页 - - - - - - - - - - 城市链表实验报告2、返回位置坐标模块。3、计算距离模块4、插入模块。5、更新城市信息模块6、删除信息模块。5、3 算法5、3、1 根据中心城市坐标,返回在距离内的所有城市: void FindCityDistance(citylist *L) / 根据距离输出城市 / 输入信息与距离L=L-next; while(L != NULL) if(L-x-x1)*

4、(L-x-x1)+(L-y-y1)*(L-y-y1)x-x1)+(L-y-y1)!=0 ) printf(城市名称 %sn,L-Name); printf(城市坐标 % 、2lf,%、2lfn,L-x,L-y); L=L-next; 该算法主要用到了勾股定理, 考虑到不需要实际数值, 只需要大小比较, 所以只用横坐标差的平方+纵坐标差的平方 next = NULL; void Insert_sqCity(citylist *L) / 在链表中插入元素citylist* newNode; newNode=(citylist*)malloc(sizeof(citylist); if (!newNo

5、de) printf( 存储分配失败 ); printf(请输入城市名 n ); scanf(%s ,newNode-Name); printf(请输城市坐标 x yn); 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 ch100; int i; printf(输入 END 退出, 输入其余值

6、继续 n ); /当输入 END 时, 在任意输入 , 则退出此操作scanf(%s ,ch); for (;strcmp(ch,END )!=0 ; ) Insert_sqCity(L); printf( 输入 END 退出 , 输入其余值继续 n ); scanf(%s ,ch); 创建查询插入删除更新距离退出就 是 否 退出就是结束开始选择操作否精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 10 页 - - - - - - - - - - 城市链表实验报告 void Get_sqCit

7、yCoord(citylist *L) / 输入城市信息返回坐标char ch10; 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) / 删除城市信息 , 按名称 / 坐标printf(请输入城市名 n); char ch10; scanf(%

8、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;

9、 while (L != NULL) if (L-x-x1)*(L-x-x1)+(L-y-y1)*(L-y-y1)x-x1)+(L-y-y1)!=0 ) printf(城市名称 %sn,L-Name); printf(城市坐标 % 、2lf,% 、2lfn,L-x,L-y); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 10 页 - - - - - - - - - - 城市链表实验报告L=L-next; void Update_sqCity(citylist* L) / 更新城市信息cha

10、r ch10; 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(citylis

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

12、; break ; case 2: Get_sqCityCoord(L); break ; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 10 页 - - - - - - - - - - 城市链表实验报告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:

13、 break ; if (choice = 7) break ; 5、6 仿真结果2、查询城市信息3 添加城市精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 10 页 - - - - - - - - - - 城市链表实验报告4 删除城市5 更新城市6 根据距离输出城市5、7 调试心得5、7、1 错误分析 : 实验中出现的第一个问题就是声明变量,从键盘中读入数据就是显示变量未初始化,调试后发现就是scanf 的问题 ,以后的实验中应注意scanf 中读入信息后就是存到了地址里。5、7、2 算法复

14、杂度的分析: 所有程序除了InitList_SqCity 复杂度为 O(1), 其余均为 O(n) 。5、7、3 收获对数据结构这门课地应用有了一定地了解,知道对线性表插入、删除等操作的实现,加深对课本地理解。附录约瑟夫环 : 5、1 问题分析精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 10 页 - - - - - - - - - - 城市链表实验报告该实验要求循环连续查找信息,并删除节点 ,故使用单项循环链表。5、2 设计方案1、建立单循环链表2、产生 Joseph环3、输出顺序表5、3

15、 算法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;inext=q; L=q; printf(输入第 %d个人的值 :,i); /输入每个人的值scanf(%d,&(L-value); L-num=i; L-next=head; L=head;/构成单向循环链表 5、3、2 查找并删除

16、节点Status Delete_Node(Node *L) for (j=1;j=num;j+) for(i=1;inext; 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 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共

17、 10 页 - - - - - - - - - - 城市链表实验报告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;inext=q; L=q; printf(输入第 %d个人的值 :,i); /输入每个人的值scanf(%d,&(L-

18、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;inext; 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; pr

19、intf(输入人数 :); /*输入测试人的数量*/ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 10 页 - - - - - - - - - - 城市链表实验报告scanf(%d,&num); Creat_JoephLink(num); 5、5 运行结果5、6 调试心得5、6、1 错误分析查找到第 m 个节点删除时出错,显示有未处理的异常,就是因为节点赋值的时候有问题。5、6、2 收获从开始构建循环链表然后实现约瑟夫环功能的过程中, 中途也遇见一些问题, 但都逐一克服 , 整个过程进展不就是很顺利, 都就是不停的调试, 实验之后 , 我还对数据结构这门课有了一定的认识。在解决一个具体问题时, 常常需要从具体问题中抽象出一个模型, 也就就是抽象数据类型 , 然后设计一个解决这个模型的算法。再通过其算法编出程序, 进行调试、调整直至得到最终解答。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 10 页 - - - - - - - - - -