2014-2015学年第一学期实验报告课程名称：算法与数据结构实验名称：城市链表一、实验目的本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。

同时，通过本次实验帮助学生复习高级语言的使用方法。

二、实验内容（一）城市链表：将若干城市的信息，存入一个带头结点的单链表。

结点中的城市信息包括：城市名，城市的位置坐标。

要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。

(二) 约瑟夫环m 的初值为 20；密码：3，1，7，2，6，8，4（正确的结果应为 6，1，4，7，2，3，5）。

三、实验环境VS2010 、四、实验结果（一）城市链表:（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.计算距离模块4.插入模块。

5.更新城市信息模块6.删除信息模块。

算法根据中心城市坐标，返回在距离内的所有城市：void FindCityDistance(citylist *L){l f,%.2lf\n",L->x,L->y);}L=L->next;}}该算法主要用到了勾股定理，考虑到不需要实际数值，只需要大小比较，所以只用横坐标差的平方+纵坐标差的平方 <= 距离的平方判定。

因中心城市本身也在判定范围之内，所以添加了判定条件横纵坐标差的和不能为零。

主程序中循环条件判定：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){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;}}仿真结果2.查询城市信息3 添加城市4 删除城市5 更新城市6 根据距离输出城市调试心得错误分析：实验中出现的第一个问题是声明变量，从键盘中读入数据是显示变量未初始化，调试后发现是scanf的问题，以后的实验中应注意scanf中读入信息后是存到了地址里。

算法复杂度的分析：所有程序除了InitList_SqCity 复杂度为O(1),其余均为O(n)。

收获对数据结构这门课地应用有了一定地了解，知道对线性表插入、删除等操作的实现，加深对课本地理解。

附录约瑟夫环：问题分析该实验要求循环连续查找信息，并删除节点，故使用单项循环链表。

设计方案1.建立单循环链表2.产生Joseph环3.输出顺序表算法构成单链表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->next=q;L=q;printf("输入第%d个人的值:",i); //输入每个人的值scanf("%d",&(L->value));L->num=i;}L->next=head;L=head;//构成单向循环链表}查找并删除节点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);}}源程序代码typedef 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->next=q;L=q;printf("输入第%d个人的值:",i); //输入每个人的值scanf("%d",&(L->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;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);}}int main(){int num;printf("输入人数："); /*输入测试人的数量*/ scanf("%d",&num);Creat_JoephLink(num);}运行结果调试心得错误分析查找到第m个节点删除时出错，显示有未处理的异常，是因为节点赋值的时候有问题。

收获从开始构建循环链表然后实现约瑟夫环功能的过程中，中途也遇见一些问题，但都逐一克服，整个过程进展不是很顺利，都是不停的调试，实验之后，我还对数据结构这门课有了一定的认识。

在解决一个具体问题时，常常需要从具体问题中抽象出一个模型，也就是抽象数据类型，然后设计一个解决这个模型的算法。

再通过其算法编出程序，进行调试、调整直至得到最终解答。