数据结构城链表

1、实验目的1、掌握线性表链表的表示和实现；2、学会抽象定义数据类型；3、熟练掌握线性表中的查找、插入、删除和更新等操作；4、学会分析问题，设计适当的解决方案。实验内容【问题描述】将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。【基本要求】(1)给定一个城市名，返回其位置坐标；(2)给定一个位置坐标P和一个距离D,返回所有与P的距离小于等于D的城市。实验步骤(一)需求分析1、根据题目，我们认为我们所编的程序需要实现以下功能：(1)、创建一个城市链表，能够输入城市信息，即城市名和城市位置坐标；

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

3、中南民族大学管理学院学生实验报告新建城市信息：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.203 )、输入“3”调用函数FindCityDistance();如：当给定坐标P(3.3,4.4)时,距离5时,就输出所有与P的距离小于等于5的城市信息。4 )、输入"4

4、",调用函数Insert().进行插入新城市信息操作；如：插入城市信息：hainan(5,8),当进行查找时，能看到插入城市的信息.证明插入成功.5 )、输入"5"，调用函数Delete(),进行删除操作：6 )、输入"6",调用函数UpdateCity(Store),进行更新操作；7 )、输入"7”，退出.(二)概要设计1)为了实现上述程序功能，需要定义单链表的抽象数据类型：1、为实现上述程序功能，应以有序链表表示集合。ADTList数据对象：D4aiai亡ElemSet,i=1,2，n,n至0数据关系：Rra,aanaLD,i=2

5、,，n基本操作：InitList(&L)操作结果：构造一个空的线性表L,即初始化表L。ListLength(L)初始条件：线性表L已存在。操作结果：求线性表L中数据元素个数，即求表长。GetElem(L,i,&e)初始条件：线性表L已存在，1wiwListLength(L)操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e,compare()中南民族大学管理学院学生实验报告初始条件：线性表L已存在，compare()是数据元素判定函数。操作结果：返回L中第一个与e满足关系compare()的数据元素的位置。若L中不存在这样的数据元素，则返回值0。ListIn

6、sert(&L,i,e)初始条件：线性表L已存在，1<=i<=ListLength(L)+1操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空,1<=i<=ListLength(L)操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ADTList2)本程序包含8个函数调用模块typedefstructCITYLISTCityList;voidInit(CityList*LHead);voidInsert(CityList*LHead);voidDele

7、te(CityList*LHead);voidCreate(CityList*LHead);voidFindCity(CityList*LHead);voidFindCityDistance(CityList*LHead);voidUpdateCity(CityList*LHead);(三)详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。一.源程序文件名清单：Stdlib.H/Stdio.H/String.H/Malloc.H/二.结构类型构造头文件主程序字符串处理函数的头文件动态存储分配实现单元typedefstructCityLi

8、stcharCityName10;floatX,Y;structCityList*Next;中南民族大学管理学院学生实验报告QtyList,*LHead;结点类型,指针类型三.主程序模块：Voidmain()(初始化Switch0接受命令；处理命令；四.基本函数操。voidInit(CityList*LHead)LHead->Next=NULL;/建立一个带头结点的单链线性表，LHead指向头结点。voidInsert(CityList*LHead)CityList*newNode;/定义指针结构为cityList型charm;newNode=(CityList*)malloc(size

9、of(CityList);/件成新结点if(newNode=NULL)/险证空间申请是否成功printf("内存分配失败n");return;/若分配内存不成功，则返回继续分配。printf("请输入城市名n");scanf("%s",newNode->CityName);/ftf针的数据域printf("请输入城市坐标x,yn");scanf("%f%c%f",&newNode->X,&m,&newNode->Y);/将城市信息填入新节点中while(

10、LHead->Next!=NULL)LHead=LHead->Next;/如果非空,HLead指针的位置向后移newNode->Next=LHead->Next;LHead->Next=newNode;将新节点插入链表中南民族大学管理学院学生实验报告voidDelete(CityList*LHead)(chardelCity10;printf("请输入要删除的城市名n");scanf("%s",delCity);while(strcmp(LHead->Next->CityName,delCity)从LHead指向

11、得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。(LHead=LHead->Next;/不相等则指针LHead下移，继续查找LHead->Next=LHead->Next->Next;相等则删除此节点voidCreate(CityList*LHead)(charsign20;定义输入信息类型及长度printf("输入END退出，输入其余值继续n");当输入END时，在任意输入，则退出此操作scanf("%s",sign);while(strcmp(sign,"END")/当输入END时，再任意输入

12、，则退出此操作(Insert(LHead);printf("输入END退出，输入其余值继续n");scanf("%s",sign);voidFindCity(CityList*LHead)(charCityName30;intj=0;printf("请输入您要搜索的城市名n");scanf("%s",CityName);while(LHead->Next!=NULL&&strcmp(LHead->Next->CityName,CityName)(LHead=LHead->Ne

13、xt;中南民族大学管理学院学生实验报告)if(LHead->Next=NULL)(printf("您要搜索的城市不存在n");return;)Printfprintf("城市坐标为.2f,%.2fn",LHead->X,LHead->Y);)voidUpdateCity(CityList*LHead)(charCityName10;printf("请输入您要更新的城市名n");scanf("%s",CityName);while(strcmp(LHead->Next->CityName

14、,CityName)/从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。(LHead=LHead->Next;/当不相等则指针LHead下移，继续查找)printf("请输入城市新信息：n");printf("请输入城市新名n");scanf("%s",LHead->Next->CityName);printf("请输入城市新坐标n");scanf("%f',&LHead->Next->X);scanf("%f',

15、&LHead->Next->Y);/输入城市新信息voidFindCityDistance(CityList*LHead)(charm;floatx;floaty;floatdistance;printf("请输入中心坐标x,yn");scanf("%f%c%f',&x,&m,&y);printf(”请输入距离:");中南民族大学管理学院学生实验报告scanf("%f",&distance);LHead=LHead->Next;while(LHead!=NULL)if(

16、x-LHead->X)*(x-LHead->X+(y-LHead->Y)*(y-LHead->Y<=distance*distance)printf("城市名为sn",LHead->CityName);printf("城市坐标为%.2f,%.2fn",LHead->X,LHead->Y);LHead=LHead->Next;五.主函数voidmain()CityList*LHead;CityList*Store;charchoice3=1,2,3;LHead=(CityList*)malloc(siz

17、eof(CityList);Init(LHead);/建立空表7时，进行以下操Store=LHead;while(strcmp(choice,"7")/当所选择等于printf("*n");printf("*n");单,printf("printf('printf('欢迎使用本系统I*I*n");*n");printf（"1.创建城市链表n"）;printf（"2.根据城市名查询城市n"）;printf（"3.根据离中心坐标距离查询城市pr

18、intf("4.插入新城市信息n");printf("5.删除城市信息n");printf("6.更新城市信息n");printf("7.退出n");皆为提示信息printf("=:printf("请输入:");n");n");/以上相当于一个选择菜An");中南民族大学管理学院学生实验报告scanf("%s",&choice);switch(choice0)case'1':相当于选择1Create(Store)

19、;/构造并创建城市信息链表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;d

20、efault:printf("输入错误，请重新输入n");break;system("PAUSE");return;(四)调试分析1、算法的时空分析1)由于有序表采用带头结点的有序单链表，并增设尾指针。首先对链表地长度有所限制，存储空间不够就根据实际情况再申请。各种操作的算法时间复杂度比较合理。InitList,这个操作的时间复杂度都是O(1)。InsertList,中南民族大学管理学院学生实验报告DeleteList,FindCity,FindCityDistance,UpdateCity的时间复杂度则是O(n),n为链表长度。2.错误分析调试时whi

21、le(strcmp(LHead->Next->CityName,CityName)出现错误，显示错误为'cannotconvertparameter1from'char'to'constchar*''前一个是char类型不能用于strcmp函数，后将charCityName103、创建城市链表时，输入城市信息较为麻烦，每个城市信息输入完后，若还想输入其它城市信息，则输入任意键继续，否则输入ENM出，所以在输入信息时需注意输入步骤，以免发生输入混乱。(五)用户手册1、本试验使用的运行软件是VC+6.0。2、进入演示程序后即显示文本方式的

22、用户界面：欢迎使用本系统市城询蛰市市城距询膂心表杳一坐督心息链名心市堪、市工城市市遣离建<除工创量请输入:3、输入相应的数据选择相应的命令，回车进入数据测试，在执行命令1'时输入END吉束，执行其它命令时以回车键结束。4接受其他命令后形成相应的结构。(六)测试结果中南民族大学管理学院学生实验报告1 .执行命令1':输入测试数据fujian(1.1,2.2)beijing(3.3,4.4)shanganghai(5,6)'E:PnogramFil?sMicrosottVisualStLidiQMyPrajBctsghD?bug中南民族大学管理学院学生实验报告tian

23、jing(7,8)nanjing(910,910)hangzhou(11,12)输出结果如图：2 .执行命令2':输入GL,输出结果如下请输入;2请瑞入您要搜索的城市名Fujian城市坐标为1,血2.2目3'执行命令'3':输入中心坐标3.3,4.4,输入距离5,输出结果如下欢迎使用本系统表A籍名心市市$城市币谭离建<除备11090rl-j1i3a5心离Fu为be为sh为:3中4距为标为标靠人入4.人名坐名坐名坐3输乔宜产产科而4.执行命令4'：输入城市名及中心坐标为hainan和5,8,并通过查询验证已插入，结果如下中南民族大学管理学院学生实验报

24、告城市币石心市渡翳婕市名iainan者输入城市坐标XTiS欢迎使用本系统表查坐售心自少链名心币一市E城市币WW离建除电创卷矍船底要搜索的城市名hainan城市坐标为5.140,8.0U5.执行命令5':输入数据beijing,并通过查询验证数据已删除，结果如下中南民族大学管理学院学生实验报告表查坐息链名心市售、币E城市币簧高建除需创矗错名心市市*城市市法离建<除窜爵删除的城市名*eijiing欢迎使用本系统请掰入=2请孺入您要搜索的城市名heijinsi您要搜索的城市不存在6执行命令6':输入要更新的城市名为hangzhou,将其信息更新为xihu和6,7中南民族大学管理

25、学院学生实验报告询城生哧距常查询城市.吉顿人工青输入您要更新的城市名欢迎使用本系统表查坐售心息链名心市市£城市币建<除意噩储藕耍息:病输入城币新名ilm青榆入城市新坐标-7表杳-坐善心思错名心市一.币$城币币簧离建<除番7执行命令'T:退出程序欢迎使用本系统请健人二7请转任意键继续一.（七）心得体会通过这次课程设计，我对完成一项小组任务有了更深刻地了解。首先是对程序的分析。虽然题目的要求很简单，但我们需要更深入地思考其实质是什么。了解实验所需要的基本程序，并用所学知识实现它。其次是小组合作中南民族大学管理学院学生实验报告问题。我们要对每个人都有所了解，然后分配相应

26、地任务。最后是程序地实现。我们一起讨论了程序实现过程中所出现的问题，共同对程序加以改进。（八）团队介绍小组成员：王静张雪彤我们一起分析城市链表这个程序由哪几部分组成，分析怎样建立一个链表及对其功能的完善，然后根据每个模块编写程序。写程序时先确定大致模型，再写细节，最后一起调试、修改。(九)附录：源程序清单typedefstructCityListcharCityName10;floatX,Y;structCityList*Next;CityList,*LHead;结点类型,指针类型voidInit(CityList*LHead)LHead->Next=NULL;"/建立一个带头

27、结点的单链线性表，LHead指向头结点。voidInsert(CityList*LHead)CityList*newNode;/定义指针结构为cityList型charm;newNode=(CityList*)malloc(sizeof(CityList);/件成新结点if(newNode=NULL)阴佥证空间申请是否成功printf("内存分配失败n");return;/若分配内存不成功，则返回继续分配。printf("请输入城市名n");scanf("%s",newNode->CityName);/ftf针的数据域print

28、f("请输入城市坐标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;)将新节点插入链表voidDelete(CityList*LHead)(chardelCity10;p

29、rintf("请输入要删除的城市名n");scanf("%s",delCity);while(strcmp(LHead->Next->CityName,delCity)从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。(LHead=LHead->Next;/不相等则指针LHead下移，继续查找)LHead->Next=LHead->Next->Next;相等则删除此节点)voidCreate(CityList*LHead)(charsign20;定义输入信息类型及长度printf("

30、;输入END退出，输入其余值继续n");当输入END时，在任意输入，则退出此操作scanf("%s",sign);while(strcmp(sign,"END")/当输入END时，再任意输入，则退出此操作(Insert(LHead);printf("输入END退出，输入其余值继续n");scanf("%s",sign);)voidFindCity(CityList*LHead)(charCityName30;intj=0;printf("请输入您要搜索的城市名n");中南民族大学管理学

31、院学生实验报告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);voidUpdateCity(CityList*LHead)char

32、CityName10;printf("请输入您要更新的城市名n");scanf("%s",CityName);while(strcmp(LHead->Next->CityName,CityName)/从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。LHead=LHead->Next;/当不相等则指针LHead下移，继续查找printf("请输入城市新信息：n");printf("请输入城市新名n");scanf("%s",LHead->Nex

33、t->CityName);printf("请输入城市新坐标n");scanf("%f',&LHead->Next->X);scanf("%f',&LHead->Next->Y);/输入城市新信息voidFindCityDistance(CityList*LHead)charm;floatx;中南民族大学管理学院学生实验报告floaty;floatdistance;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<=distance*distance)printf("城市名为%sn",LHead->CityName);printf("城市坐标为.2f,%.2fn",LHead