数据结构城市链表

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 ）构造函

3、数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.203 )、输入 “ 3” 调用函数FindCityDistance();如：当给定坐标 P (

4、3.3 , 4.4 )时,距离5时,就输出所有与 P的 距离小于等于5的城市信息。4 )、输入" 4"，调用函数Insert().进行插入新城市信息操作；如：插入城市信息：hainan(5,8),当进行查找时，能看到插入城市 的信息.证明插入成功.5 )、输入" 5"，调用函数Delete(),进行删除操作：6 )、输入"6",调用函数UpdateCity(Store),进行更新操作；7 )、输入" 7”，退出.(二)概要设计1)为了实现上述程序功能，需要定义单链表的抽象数据类型：1、为实现上述程序功能，应以有序链表表示集合

5、。ADT List数据对象：D=ai ai ElemSeti 1,2，n,n 0数据关系：Ri aia I aia D,i 2,，n基本操作：InitList(&L)操作结果：构造一个空的线性表L,即初始化表L。ListLength (L)初始条件：线性表L已存在。操作结果：求线性表 L中数据元素个数，即求表长。GetElem(L , i , &e)初始条件：线性表 L已存在，1 w i w ListLength ( L) 操作结果：用e返回L中第i个数据元素的值。LocateElem (L,e,compare()初始条件：线性表L 已存在， compare() 是数据元素判定

6、函数。操作结果：返回 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<=i<=ListLength(L)操作结果： 删除 L 的第 i 个数据元素， 并用 e 返回其值， L 的长度减 1。 ADT List2)本程序包含

7、8 个函数调用模块typedef struct CITYLIST CityList;void Init(CityList *LHead);void Insert(CityList *LHead);void Delete(CityList *LHead);void Create(CityList *LHead);void FindCity(CityList* LHead);void FindCityDistance(CityList* LHead);void UpdateCity(CityList* LHead);(三)详细设计实现概要设计中定义的所有的数据类型， 对每个操作给出伪码算法。对主程

8、序和其他模块也都需要写出伪码算法。一源程序文件名清单：Stdlib.H/头文件Stdio.H/主程序String.H/字符串处理函数的头文件Malloc.H/动态存储分配实现单元,结构类型构造 typedef struct CityList char CityName10;float X,Y;struct CityList *Next;CityList, *LHead; / 结点类型，指针类型三主程序模块：Void main ()初始化Switch () 接受命令；处理命令；四 基本函数操。void Init(CityList *LHead)LHead->Next = NULL;&quo

9、t;/建立一个带头结点的单链线性表，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-&

10、gt;CityName);/ftf针的数据域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(CityLi

11、st *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 *LHea

12、d)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

13、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->

14、;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(&quo

15、t; 请输入城市新名 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(" 请输入中

16、心坐标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->Cit

17、yName);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(&qu

18、ot;*n");printf("*n"); scanf("%s",&choice);printf("欢迎使用本系统n");printf("printf("I*I*n");*n");printf（"1. 创建城市链表n"）;printf（"2. 根据城市名查询城市n"）;printf（"3. 根据离中心坐标距离查询城市printf（"4. 插入新城市信息 n"）;printf（"5. 删除城市信息 n

19、"）;n");printf（"6. 更新城市信息 n"）;printf（"7. 退出 n"）;/ 以上相当于一个选择菜单，皆为提示信息printf("=n");printf(" 请输入 :");switch(choice0)case '1':/ 相当于选择1Create(Store); / 构造并创建城市信息链表 break;case '2':FindCity(Store);/根据城市名查找城市位置 break;case '3':FindCityD

20、istance(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 ;(四)

21、调试分析1 、算法的时空分析2 )由于有序表采用带头结点的有序单链表，并增设尾指针。首先对链表地长度有所限制， 存储空间不够就根据实际情况再申请。 各种操作的算法时间复杂度比较合理。 InitList, 这个操作的时间复杂度都是O( 1) 。 InsertList,DeleteList ， FindCity, FindCityDistance, UpdateCity 的时间复杂度则是 O( n ) ， n 为链表长度。3 错误分析调试时 while(strcmp(LHead->Next->CityName,CityName) 出现错误， 显示错误为 cannot convert p

22、arameter 1 from 'char' to 'const char *'前一个是 char 类型不能用于strcmp 函数，后将char CityName103、创建城市链表时，输入城市信息较为麻烦，每个城市信息输入完后，若还想输入其它城市信息，则输入任意键继续，否则输入END1出，所以在输入信息时需注意输入步骤，以免发生输入混乱。(五)用户手册1 、本试验使用的运行软件是VC+6.0。2、进入演示程序后即显示文本方式的用户界面：3 、输入相应的数据选择相应的命令，回车进入数据测试，在执行命令1 时输入END吉束，执行其它命令时以回车键结束。4接受其他命

23、令后形成相应的结构。(六)测试结果1. 执行命令 1 ：输入测试数据fujian(1.1,2.2)beijing(3.3,4.4)shanganghai(5,6)tianjing(7,8) nanjing(910,910) hangzhou(11,12) 输出结果如图：h 'E:Program FilenMicro5。情 Visual StudiaMyPrcject5ghDebug,2.执行命令2':输入GL,输出结果如下3'执行命令'3':输入中心坐标3.3,4.4 ,输入距离5,输出结果如下4 . 执行命令 4 ：输入城市名及中心坐标为 hainan

24、 和 5,8 ，并通过查询验 证已插入，结果如下堤名hinan请输入城市坐标。95 8欢迎使用本系统rp 市建除新出嬴,名查询城汇 离小心坐标距离查询城市 新城市傕息；需遥要搜索的城市名liaij-iiiaiji城市坐标为5.00,8.005 .执行命令5':输入数据beijing ,并通过查询验证数据已删除，结果如 下E 市 一 城 - 询 一 查-S-城距 询标息 表查心息 镇名装W 、币由城、币币 建<除暂 创强篇更强欢迎使用本系统表查坐售心息错名心.币渡查询城市蠲超要搜索的城市名beij lng(您要搜索的城市不存在6执行命令6':输入要更新的城市名为hangzh

25、ou ,将其信息更新为 xihu和6,77执行命令7':退出程序欢迎使用本系统市 城 询 查城距 询标息 表查坐督0息 链名心币渡 、币E城,币币 爵离 建常.人除善 创强浦量强任意键继续一（七）心得体会通过这次课程设计，我对完成一项小组任务有了更深刻地了解。首先是对程序的分析。虽然题目的要求很简单， 但我们需要更深入地思考其实质是 什么。了解实验所需要的基本程序，并用所学知识实现它。 其次是小组合作问题。我们要对每个人都有所了解，然后分配相应地任务。最后是程序地实 现。我们一起讨论了程序实现过程中所出现的问题，共同对程序加以改进。（八）团队介绍小组成员：王静 张雪彤我们一起分析城市链

26、表这个程序由哪几部分组成， 分析怎样建立一个链表及对其功能的完善， 然后根据每个模块编写程序。 写程序时先确定大致模型，再写细节，最后一起调试、修改。(九)附录：源程序清单typedef struct CityListchar CityName10;float X,Y;struct CityList *Next;CityList, *LHead; / 结点类型，指针类型void Init(CityList *LHead)LHead->Next = NULL;"/建立一个带头结点的单链线性表，LHead指向头结点。void Insert(CityList *LHead)CityL

27、ist* newNode; /定义指针结构为 cityList 型char m;newNode = (CityList*)malloc(sizeof(CityList); /生成新结点if(newNode = NULL) /验证空间申请是否成功printf(" 内存分配失败n");return; / 若分配内存不成功，则返回继续分配。printf(" 请输入城市名 n");scanf("%s",newNode->CityName);/ftf针的数据域printf(" 请输入城市坐标x,yn");scanf(&

28、quot;%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");sc

29、anf("%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&

30、quot;); 当输入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"

31、,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;print

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

33、gt;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,&am

34、p;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->X,LHead->Y);LHead = L