数据结构城市链表.doc

中南民族大学管理学院学生实验报告实验目的1、掌握线性表链表的表示和实现；2、学会抽象定义数据类型；3、熟练掌握线性表中的查找、插入、删除和更新等操作；4、学会分析问题，设计适当的解决方案。实验内容【问题描述】将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。【基本要求】（1） 给定一个城市名，返回其位置坐标；（2） 给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。实验步骤（一）需求分析1、根据题目，我们认为我们所编的程序需要实现以下功能：（1）、创建一个城市链表，能够输入城市信息，即城市名和城市位置坐标；（2）、能够根据城市名查询其位置坐标；（3）、根据离中心坐标距离查询城市名；（4）、能够插入城市信息；（5）、能够删除城市信息；（6）、能够更新城市信息；（7）、执行完毕，退出程序。2、演示程序以用户和计算机的对话方式执行，即在在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；输入相应的数据（滤去输入中非法字符），运算结果显示在其后。3、程序执行的命令包括：（1）构造函数1；（2）构造函数2；（3）构造函数3；（4）构造函数4；（5）构造函数5；（6）构造函数6；（7）构造函数7。4、测试数据1）、输入”1”调用函数 Create()；新建城市信息: fujian(1.1,2.2) beijing(3.3,4.4) shanghai(5,6) tianjing(7,8) nanjing(910，910) hangzhou(11,12)输入END键,退出. 2）、输入”2”,调用函数FindCity()； 当键入城市名时,返回其城市坐标: 如：键入城市名”fujian”，返回坐标：1.10.2.20 3）、输入“3”调用函数FindCityDistance(); 如：当给定坐标P（3.3，4.4）时,距离5时,就输出所有与P的距离小于等于5的城市信息。 4）、输入”4”,调用函数Insert().进行插入新城市信息操作； 如:插入城市信息:hainan(5,8)，当进行查找时,能看到插入城市的信息.证明插入成功. 5）、输入”5”,调用函数Delete(),进行删除操作： 6）、输入”6”,调用函数UpdateCity(Store),进行更新操作； 7）、输入”7”,退出.（二）概要设计 1）为了实现上述程序功能，需要定义单链表的抽象数据类型：1、为实现上述程序功能，应以有序链表表示集合。ADT List数据对象：D=数据关系： 基本操作：InitList(&L)操作结果：构造一个空的线性表L，即初始化表L。 ListLength（L） 初始条件：线性表L已存在。 操作结果：求线性表L中数据元素个数，即求表长。 GetElem(L，i，&e） 初始条件：线性表L已存在，1iListLength（L） 操作结果：用e返回L中第i个数据元素的值。LocateElem（L,e,compare()） 初始条件：线性表L已存在，compare()是数据元 素判定函数。 操作结果：返回L中第一个与e满足关系compare() 的数据元素的位置。若L中不存在这样 的数据元素 ，则返回值0。 ListInsert(&L,i,e) 初始条件:线性表L已存在,1=i=ListLength(L)+1 操作结果：在L中第i个位置之前插入新的数据元素 e,L的长度加1。ListDelete(&L,i,&e) 初始条件:线性表L已存在且非空,1=iNext = NULL; /建立一个带头结点的单链线性表，LHead指向头结点。void Insert(CityList *LHead)CityList* newNode; /定义指针结构为cityList型char m;newNode = (CityList*)malloc(sizeof(CityList); /生成新结点if(newNode = NULL) /验证空间申请是否成功printf(内存分配失败n);return; /若分配内存不成功，则返回继续分配。 printf(请输入城市名n);scanf(%s,newNode-CityName);/指针的数据域printf(请输入城市坐标x,yn); scanf(%f%c%f,&newNode-X,&m,&newNode-Y); /将城市信息填入新节点中while(LHead-Next != NULL) LHead = LHead-Next;/如果非空，HLead指针的位置向后移newNode-Next = LHead-Next;LHead-Next = newNode; /将新节点插入链表void Delete(CityList *LHead)char delCity10;printf(请输入要删除的城市名n);scanf(%s,delCity);while(strcmp(LHead-Next-CityName,delCity )/从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。LHead = LHead-Next; /不相等则指针LHead下移，继续查找LHead -Next = LHead-Next-Next; /相等则删除此节点void Create(CityList *LHead)char sign20; /定义输入信息类型及长度printf(输入END退出,输入其余值继续n); /当输入END时，在任意输入，则退出此操作scanf(%s,sign);while(strcmp(sign,END) /当输入END时，再任意输入，则退出此操作Insert(LHead);printf(输入END退出,输入其余值继续n);scanf(%s,sign);void FindCity(CityList* LHead)char CityName30;int j=0;printf(请输入您要搜索的城市名n);scanf(%s,CityName);while(LHead-Next != NULL & strcmp(LHead-Next-CityName,CityName)LHead = LHead-Next;if(LHead-Next = NULL)printf(您要搜索的城市不存在n);return;Printfprintf(城市坐标为%.2f,%.2fn,LHead-X,LHead-Y);void UpdateCity(CityList* LHead)char CityName10;printf(请输入您要更新的城市名n);scanf(%s,CityName);while(strcmp(LHead-Next-CityName,CityName) /从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。LHead = LHead-Next; / 当不相等则指针LHead下移，继续查找printf(请输入城市新信息:n);printf(请输入城市新名n);scanf(%s,LHead-Next-CityName);printf(请输入城市新坐标n);scanf(%f,&LHead-Next-X);scanf(%f,&LHead-Next-Y); /输入城市新信息void FindCityDistance(CityList* LHead)char m;float x;float y;float distance;printf(请输入中心坐标x,yn);scanf(%f%c%f,&x,&m,&y);printf(请输入距离:);scanf(%f,&distance);LHead = LHead-Next;while(LHead != NULL)if(x-LHead-X)*(x-LHead-X) + (y-LHead-Y)*(y-LHead-Y) CityName);printf(城市坐标为%.2f,%.2fn,LHead-X,LHead-Y);LHead = LHead-Next;五主函数void main()CityList* LHead;CityList* Store;char choice3 = 1,2,3;LHead = (CityList*)malloc(sizeof(CityList);Init(LHead);/建立空表 Store = LHead; while(strcmp(choice,7) /当所选择等于7时，进行以下操作 printf(*n); printf(*n); printf( 欢迎使用本系统 n); 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); printf(请输入:); scanf(%s,&choice); switch(choice0)case 1: /相当于选择1Create(Store); /构造并创建城市信息链表break;case 2:FindCity(Store);/根据城市名查找城市位置break;case 3:FindCityDistance(Store);/根据所给中心坐标和距离值，返回小于等于所给距离值得节点信息。break;case 4:Insert(Store);/插入新结点break;case 5:Delete(Store);/删除结点break;case 6:UpdateCity(Store);/更新结点信息break; case 7:/退出break;default:printf(输入错误,请重新输入n);break; system(PAUSE);return ;（四）调试分析1、算法的时空分析1）由于有序表采用带头结点的有序单链表，并增设尾指针。首先对链表地长度有所限制，存储空间不够就根据实际情况再申请。各种操作的算法时间复杂度比较合理。InitList,这个操作的时间复杂度都是O（1）。InsertList, DeleteList ，FindCity, FindCityDistance, UpdateCity的时间复杂度则是O（n），n为链表长度。2错误分析调试时while(strcmp(LHead-Next-CityName,CityName)出现错误，显示错误为cannot convert parameter 1 from char to const char *前一个是char类型不能用于strcmp函数，后将char CityName103、创建城市链表时，输入城市信息较为麻烦，每个城市信息输入完后，若还想输入其它城市信息，则输入任意键继续，否则输入END退出，所以在输入信息时需注意输入步骤，以免发生输入混乱。（五）用户手册1、本试验使用的运行软件是VC+6.0。2、进入演示程序后即显示文本方式的用户界面：3、输入相应的数据选择相应的命令，回车进入数据测试，在执行命令1时输入END结束，执行其它命令时以回车键结束。4接受其他命令后形成相应的结构。（六）测试结果1.执行命令1：输入测试数据 fujian(1.1,2.2) beijing(3.3,4.4) shanganghai(5,6) tianjing(7,8) nanjing(910,910) hangzhou(11,12)输出结果如图：2.执行命令2：输入GL，输出结果如下3执行命令3：输入中心坐标3.3,4.4，输入距离5，输出结果如下4.执行命令4：输入城市名及中心坐标为hainan和5,8，并通过查询验证已插入，结果如下5.执行命令5：输入数据beijing，并通过查询验证数据已删除，结果如下6执行命令6：输入要更新的城市名为hangzhou，将其信息更新为xihu和6,77执行命令7：退出程序（7） 心得体会 通过这次课程设计，我对完成一项小组任务有了更深刻地了解。首先是对程序的分析。虽然题目的要求很简单，但我们需要更深入地思考其实质是什么。了解实验所需要的基本程序，并用所学知识实现它。其次是小组合作问题。我们要对每个人都有所了解，然后分配相应地任务。最后是程序地实现。我们一起讨论了程序实现过程中所出现的问题，共同对程序加以改进。（8） 团队介绍小组成员：王静 张雪彤我们一起分析城市链表这个程序由哪几部分组成，分析怎样建立一个链表及对其功能的完善，然后根据每个模块编写程序。写程序时先确定大致模型，再写细节，最后一起调试、修改。（九）附录：源程序清单typedef struct CityListchar CityName10;float X,Y;struct CityList *Next; CityList, *LHead; / 结点类型，指针类型void Init(CityList *LHead)LHead-Next = NULL; /建立一个带头结点的单链线性表，LHead指向头结点。void Insert(CityList *LHead)CityList* newNode; /定义指针结构为cityList型char m;newNode = (CityList*)malloc(sizeof(CityList); /生成新结点if(newNode = NULL) /验证空间申请是否成功printf(内存分配失败n);return; /若分配内存不成功，则返回继续分配。 printf(请输入城市名n);scanf(%s,newNode-CityName);/指针的数据域printf(请输入城市坐标x,yn); scanf(%f%c%f,&newNode-X,&m,&newNode-Y); /将城市信息填入新节点中while(LHead-Next != NULL) LHead = LHead-Next;/如果非空，HLead指针的位置向后移newNode-Next = LHead-Next;LHead-Next = newNode; /将新节点插入链表void Delete(CityList *LHead)char delCity10;printf(请输入要删除的城市名n);scanf(%s,delCity);while(strcmp(LHead-Next-CityName,delCity )/从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。LHead = LHead-Next; /不相等则指针LHead下移，继续查找LHead -Next = LHead-Next-Next; /相等则删除此节点void Create(CityList *LHead)char sign20; /定义输入信息类型及长度printf(输入END退出,输入其余值继续n); /当输入END时，在任意输入，则退出此操作scanf(%s,sign);while(strcmp(sign,END) /当输入END时，再任意输入，则退出此操作Insert(LHead);printf(输入END退出,输入其余值继续n);scanf(%s,sign);void FindCity(CityList* LHead)char CityName30;int j=0;printf(请输入您要搜索的城市名n);scanf(%s,CityName);while(LHead-Next != NULL & strcmp(LHead-Next-CityName,CityName)LHead = LHead-Next;if(LHead-Next = NULL)printf(您要搜索的城市不存在n);return;Printfprintf(城市坐标为%.2f,%.2fn,LHead-X,LHead-Y);void UpdateCity(CityList* LHead)char CityName10;printf(请输入您要更新的城市名n);scanf(%s,CityName);while(strcmp(LHead-Next-CityName,CityName) /从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。LHead = LHead-Next; / 当不相等则指针LHead下移，继续查找printf(请输入城市新信息:n);printf(请输入城市新名n);scanf(%s,LHead-Next-CityName);printf(请输入城市新坐标n);scanf(%f,&LHead-Next-X);scanf(%f,&LHead-Next-Y); /输入城市新信息void FindCityDistance(CityList* LHead)char m;float x;float y;float distance;printf(请输入中心坐标x,yn);scanf(%f%c%f,&x,&m,&y);printf(请输入距离:);scanf(%f,&distance);LHead = LHead-Next;while(LHead != NULL)if(x-LHead-X)*(x-LHead-X) + (y-LHead-Y)*(y-LHead-Y) CityName);printf(城市坐标为%.2f,%.2fn,LHead-X,LHead-Y);LHead = LHead-Next