算法与及数据结构实验报告

算法与及数据结构实验报告word教育资料第一学期实验报告课程名称：算法与数据结构实验名称：城市链表一、实验目的算法与及数据结构实验报告全文共22页，当前为第1页。本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。同时，通过本次实验帮助学生复习高级语言的使用方法。算法与及数据结构实验报告全文共22页，当前为第1页。二、实验内容（一）城市链表：将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。(二)约瑟夫环m的初值为20；密码：3，1，7，2，6，8，4（正确的结果应为6，1，4，7，2，3，5）。三、实验环境VS2010、win8.1四、实验结果（一）城市链表:（1）创建城市链表；（2）给定一个城市名，返回其位置坐标；（3）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。（4）在已有的城市链表中插入一个新的城市；（5）更新城市信息；（6）删除某个城市信息。算法与及数据结构实验报告全文共22页，当前为第2页。(二)约瑟夫环算法与及数据结构实验报告全文共22页，当前为第2页。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.更新城市信息模块6.删除信息模块。5.3算法算法与及数据结构实验报告全文共22页，当前为第3页。5.3.1根据中心城市坐标，返回在距离内的所有城市：算法与及数据结构实验报告全文共22页，当前为第3页。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("城市名称%s\n",L->Name); printf("城市坐标%.2lf,%.2lf\n",L->x,L->y); } L=L->next; }}该算法主要用到了勾股定理，考虑到不需要实际数值，只需要大小比较，所以只用横坐标差的平方+纵坐标差的平方<=距离的平方判定。因中心城市本身也在判定范围之内，所以添加了判定条件横纵坐标差的和不能为零。5.3.2主程序中循环条件判定：for(;;){算法与及数据结构实验报告全文共22页，当前为第4页。 printf("请选择您的操作\n");算法与及数据结构实验报告全文共22页，当前为第4页。 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){ ……//case语句 case7:break; } if(choice==7) break; } 若用户选择了退出系统选项，则首先跳出switch在跳出for循环结束程序。算法与及数据结构实验报告全文共22页，当前为第5页。算法与及数据结构实验报告全文共22页，当前为第5页。否结束是是否退出退出插入删除更新距离5.4流程图否结束是是否退出退出插入删除更新距离查询创建开始查询创建开始选择操作算法与及数据结构实验报告全文共22页，当前为第6页。算法与及数据结构实验报告全文共22页，当前为第6页。 5.5程序源代码typedefstructcitylist{ charName[20]; doublex,y;citylist*next;}citylist,*L;voidInitList_SqCity(citylist*L){//初始化节点L->next=NULL;}voidInsert_sqCity(citylist*L){ //在链表中插入元素 citylist*newNode; newNode=(citylist*)malloc(sizeof(citylist)); if(!newNode)算法与及数据结构实验报告全文共22页，当前为第7页。 printf("存储分配失败");算法与及数据结构实验报告全文共22页，当前为第7页。 printf("请输入城市名\n"); scanf("%s",newNode->Name); printf("请输城市坐标xy\n"); scanf("%lf%lf",&(newNode->x),&(newNode->y)); while(L->next!=NULL){ L=L->next; }//如果非空，L指针的位置向后移 newNode->next=L->next; L->next=newNode;}voidCreate_sqCity(citylist*L){ //创建链表 charch[100]; inti; printf("输入END退出,输入其余值继续\n");//当输入END时，在任意输入，则退出此操作 scanf("%s",ch); for(;strcmp(ch,"END")!=0;){ Insert_sqCity(L);算法与及数据结构实验报告全文共22页，当前为第8页。printf("输入END退出,输入其余值继续\n");算法与及数据结构实验报告全文共22页，当前为第8页。 scanf("%s",ch); } }voidGet_sqCityCoord(citylist*L){ //输入城市信息返回坐标 charch[10]; printf("输入要查询的城市"); scanf("%s",ch); while(L->next!=NULL&&strcmp(L->next->Name,ch)){ L=L->next; } if(L->next==NULL) printf("城市不存在"); else{算法与及数据结构实验报告全文共22页，当前为第9页。 printf("%.2lf,%.2lf\n",L->next->x,L->next->y);算法与及数据结构实验报告全文共22页，当前为第9页。 }}voidDelete_sqCity(citylist*L){ //删除城市信息，按名称/坐标 printf("请输入城市名\n"); charch[10]; 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("删除城市成功");}voidFindCityDistance(citylist*L){ //根据距离输出城市算法与及数据结构实验报告全文共22页，当前为第10页。 printf("输入中心城市坐标");算法与及数据结构实验报告全文共22页，当前为第10页。 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)+(L->y-y1))!=0)){ printf("城市名称%s\n",L->Name); printf("城市坐标%.2lf,%.2lf\n",L->x,L->y); } L=L->next; }}voidUpdate_sqCity(citylist*L){ //更新城市信息 charch[10]; printf("请输入您要更新的城市名\n"); scanf("%s",ch);算法与及数据结构实验报告全文共22页，当前为第11页。 while(strcmp(L->next->Name,ch)){算法与及数据结构实验报告全文共22页，当前为第11页。 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));}intmain(){ citylist*L; L=(citylist*)malloc(sizeof(citylist)); InitList_SqCity(L); for(;;){ printf("-----------------------------------\n"); printf("请选择您的操作\n"); printf("1.创建城市链表\n"); printf("2.根据名字查询城市\n");算法与及数据结构实验报告全文共22页，当前为第12页。 printf("3.插入\n");算法与及数据结构实验报告全文共22页，当前为第12页。 printf("4.删除\n"); printf("5.更新城市信息\n"); printf("6.根据离中心坐标距离查看城市\n"); printf("7.退出系统\n"); printf("-----------------------------------\n"); intchoice; scanf("%d",&choice); switch(choice){ case1: Create_sqCity(L); getchar(); break; case2: Get_sqCityCoord(L); break; case3: Insert_sqCity(L); break; case4: Delete_sqCity(L); break;算法与及数据结构实验报告全文共22页，当前为第13页。 case5:算法与及数据结构实验报告全文共22页，当前为第13页。 Update_sqCity(L); break; case6: FindCityDistance(L); break; case7:break; } if(choice==7) break; } }算法与及数据结构实验报告全文共22页，当前为第14页。5.6仿真结果算法与及数据结构实验报告全文共22页，当前为第14页。2.查询城市信息3添加城市4删除城市算法与及数据结构实验报告全文共22页，当前为第15页。5更新城市算法与及数据结构实验报告全文共22页，当前为第15页。6根据距离输出城市5.7调试心得5.7.1错误分析：实验中出现的第一个问题是声明变量，从键盘中读入数据是显示变量未初始化，调试后发现是scanf的问题，以后的实验中应注意scanf中读入信息后是存到了地址里。5.7.2算法复杂度的分析：所有程序除了InitList_SqCity复杂度为O(1),其余均为O(n)。5.7.3收获 对数据结构这门课地应用有了一定地了解，知道对线性表插入、删除等操作的实现，加深对课本地理解。算法与及数据结构实验报告全文共22页，当前为第16页。附录算法与及数据结构实验报告全文共22页，当前为第16页。约瑟夫环：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;printf("输入第一个人的值:");//输入第一个人的值scanf("%d",&(L->value));inti;for(i=2;i<=num;i++){q=(Node*)malloc(sizeof(Node));L->next=q;算法与及数据结构实验报告全文共22页，当前为第17页。L=q;算法与及数据结构实验报告全文共22页，当前为第17页。printf("输入第%d个人的值:",i);//输入每个人的值scanf("%d",&(L->value));L->num=i;}L->next=head;L=head;//构成单向循环链表}5.3.2查找并删除节点StatusDelete_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;算法与及数据结构实验报告全文共22页，当前为第18页。q=L->next;算法与及数据结构实验报告全文共22页，当前为第18页。L->next=L->next->next;free(q);}}5.4源程序代码typedefstructNode{intvalue;Node*next;intnum;}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));算法与及数据结构实验报告全文共22页，当前为第19页。L->next=q;算法与及数据结构实验报告全文共22页，当前为第19页。L=q;printf("输入第%d个人的值:",i);//输入每个人的值scanf("%d",&(L->value));L->num=i;}L->next=head;L=head;//构成单向循环链表intm;intj;printf("输入初始值m的大小");scanf("%d