数据结构课程设计实验1 城市链表.doc

《数据结构课程设计实验1 城市链表.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计实验1 城市链表.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构课程设计实验1 城市链表.精品文档.数据结构课程设计实验报告实验一 链表部分选题为：2.4.3城市链表1、 需求分析（1） 创建一个带有头结点的单链表。（2） 结点中应包含城市名和城市的位置坐标。（3） 对城市链表能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。（4） 能够对每次操作后的链表动态显示。2、 概要设计为了实现以上功能，可以从以下3个方面着手设计。（1） 主界面设计为了实现城市链表相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本程序。本系统主控菜单运行界面如下所

2、示。（2） 存储结构设计本系统主要采用链表结构类型来表示存储在“城市链表”中的信息。其中链表结点由4个分量组成：城市名name、城市的横坐标posx、城市的纵坐标posy、指向下一个结点的指针next。（3） 系统功能设计本程序设计了9个功能子菜单，其描述如下： 建立城市链表。由函数creatLink()实现。该功能实现城市结点的输入以及连接。 插入链表记录。由函数insert()实现。该功能实现按坐标由小到大的顺序将结点插入到链表中。 查询链表记录。由searchName（）函数和searchPos（）函数实现。其中searchName（）实现按照城市名查询的操作，searchPos（）实现

3、按照城市坐标查询的操作。 删除链表记录。由delName（）函数和delPos（）函数实现。其中delName（）函数实现按照城市名删除的操作，delPos（）函数实现按照城市坐标删除的操作。 显示链表记录。由printList（）函数实现。该功能实现格式化的链表输出操作，可以显示修改后的链表状态。 更新链表信息。由update（）函数实现。该功能实现按照城市名更新城市的坐标信息。 返回城市坐标。由getPos（）函数实现。该功能实现给定一个已存储的城市，返回其坐标信息的操作。 查看与坐标P距离小于等于D的城市。由getCity（）函数实现。该功能实现返回与给定坐标P距离小于等于D的城市名称。

4、 退出链表系统。由exit（0）实现。3、 模块设计（1）模块设计本程序包含两个模块：主程序模块和链表操作模块。其调用关系如下图所示：主程序模块链表操作模块（2）系统子程序及功能设计本系统共设置3个子程序，各程序的函数名及功能说明如下： Linklist creatLink() /创建一个城市链表，返回头结点地址 printList(Linklist L)/ 打印头结点地址为L的城市链表 int searchName(Linklist L,char name20)/以城市名查找 int searchPos(Linklist L,int px,int py)/以城市坐标查找 int insert

5、(Linklist L,Linklist city)/插入 int delName(Linklist L,char name20)/利用城市名称删除 int delPos(Linklist L,int px,int py)/利用坐标删除 int update(Linklist L,char name20)/更新 int getPos(Linklist L,char name20)/给定一个城市名,返回城市坐标 int getCity(Linklist L,int px,int py,int d)/给定一个城市坐标P,返回距离小于等于d的城市 void main()/主函数，实现链表各项操作的选

6、择（3）函数主要调用关系图本系统3个子程序之间的主要调用关系如图所示。128967543102222211main（）4、详细设计（1） 数据类型定义typedef struct LNode/城市结点char name20;int posx;/横坐标int posy;/纵坐标struct LNode *next;LNode,*Linklist;（2）系统主要子程序详细设计建立城市链表Linklist creatLink() /创建一个城市链表，返回头结点地址Linklist L=(Linklist)malloc(LEN); /头结点L-next=NULL;Linklist p;char nam

7、e20;int px;int py;char end4=end;printf(请输入城市名称、横坐标和纵坐标，建立城市链表，以end为输入结束标志n);printf(请输入城市名称：);scanf(%s,name);while (strcmp(name,end)printf(请输入横坐标x: );scanf(%d,&px);printf(请输入纵坐标y：);scanf(%d,&py);p=(Linklist)malloc(LEN); /新结点strcpy(p-name,name);p-posx=px;p-posy=py;insert(L,p); /插入新结点printf(请输入城市名称：);s

8、canf(%s,name);return(L);插入链表记录int insert(Linklist L,Linklist city)/插入Linklist p=L-next;Linklist p_prior=L;while(p!=NULL & city-posx=p-posx)if(p-posx=city-posx & p-posy=city-posy)printf(重复输入！n);return 0;p=p-next; /确定city插入的位置while(p_prior-next!=p)p_prior=p_prior-next;if(p=NULL) p=p_prior;city-next=NU

9、LL;p-next=city;else /若为空表，插到头结点之后p=p_prior;city-next=p-next; p-next=city; return 1;按名称删除链表记录int delName(Linklist L,char name20)/利用城市名称删除int flag=0;int seat=1;Linklist p=L;if(p-next=NULL)printf(该链表中没有元素,删除失败n);else while(p-next!=NULL)if(!strcmp(p-next-name,name)flag=1;printf(城市 %s 被删除n,name);Linklist

10、 q=p-next;p-next=q-next;free(q);else p=p-next;return flag;5、测试分析（1） 实验中遇到的问题以及对设计与实现的回顾讨论和分析 城市链表在开始的建立时，由于头结点指针的判断错误，导致链表头结点中存有信息，而在后面的插入和删除操作中并未考虑到，导致链表记录出错，指针错位。 在链表的删除过程中，由于删除的时判断的结点，故应找到起前驱指针，一开始并未考虑到这些，在无法删除的时候才想起来改进方法，后来设置了一个prior指针，专门找到对应结点的前驱，方便删除操作。 课题拓展训练为为城市加入其他信息，如人口数等。考虑到此项添加仅是在数据定义中再加

11、入一个数据项，为了方便实验进行与演示，就没有进行扩展。如需实现，可在Lnode的定义中，加入int num等语句。 链表建立初期，个人的想法是按照新增结点插入按顺序插入到链表中，删除时可以按照城市名称和城市坐标进行删除。在具体的实现过程中，使用了菜单选择的方法，方便用户使用系统。（2） 算法的时空分析算法使用动态分配空间的方式执行，故其执行时间与链表记录个数有关，如果有n个城市结点，其时间复杂度为O（n）。（3） 经验和体会通过本次实验，对于链表部分的相关功能，如插入、删除、排序等相关算法进一步熟悉了。能够利用所学知识，解决相关问题，并能够正确解决实验过程中出现的差错。（4） 测试功能展示 城

12、市链表的建立在主菜单下，用户输入1并回车，然后按照提示建立城市链表，运行结果如下所示： 插入链表记录 查询链表记录： 删除链表记录 显示链表记录 更新链表信息 返回城市坐标 查看与坐标P距离小于等于D的城市6、 源程序清单#include#include#include#include#define LEN sizeof(LNode)typedef struct LNodechar name20;int posx;/横坐标int posy;/纵坐标struct LNode *next;LNode,*Linklist;/用于城市结点int insert(Linklist L,Linklist c

13、ity);Linklist creatLink() /创建一个城市链表，返回头结点地址Linklist L=(Linklist)malloc(LEN); /头结点L-next=NULL;Linklist p;char name20;int px;int py;char end4=end;printf(请输入城市名称、横坐标和纵坐标，建立城市链表，以end为输入结束标志n);printf(请输入城市名称：);scanf(%s,name);while (strcmp(name,end)printf(请输入横坐标x: );scanf(%d,&px);printf(请输入纵坐标y：);scanf(%d

14、,&py);p=(Linklist)malloc(LEN); /新结点strcpy(p-name,name);p-posx=px;p-posy=py;insert(L,p); /插入新结点printf(请输入城市名称：);scanf(%s,name);return(L);void printList(Linklist L) / 打印头结点地址为L的城市链表printf(n-n);printf(城市t坐标n);printf(-n);Linklist p=L-next;int n=1;if(L-next=NULL) printf(该链表中没有元素n);else while(p!=NULL)prin

15、tf(%s,p-name);printf(t(%d,%d)n,p-posx,p-posy);p=p-next;printf(-n);return ;int searchName(Linklist L,char name20)/以城市名查找int flag=0;Linklist p=L-next;if(L-next=NULL)printf(该链表中没有元素,查找失败n);elsewhile(p!=NULL)if(!strcmp(p-name,name)flag=1;printf(您要查找的是 %s 城市n,p-name);printf(该城市坐标为 (%d,%d) n,p-posx,p-posy

16、);p=p-next;return flag;int searchPos(Linklist L,int px,int py)/以城市坐标查找int flag=0;Linklist p=L-next;if(L-next=NULL)printf(该链表中没有元素,查找失败n);elsewhile(p!=NULL)if(p-posx=px&p-posy=py)flag=1;printf(您要查找城市坐标为 (%d,%d) n,p-posx,p-posy);printf(该城市是 %sn,p-name);p=p-next;return flag;int insert(Linklist L,Linkli

17、st city)/插入Linklist p=L-next;Linklist p_prior=L;while(p!=NULL & city-posx=p-posx)if(p-posx=city-posx & p-posy=city-posy)printf(重复输入！n);return 0;p=p-next; /确定city插入的位置while(p_prior-next!=p)p_prior=p_prior-next;if(p=NULL) p=p_prior;city-next=NULL;p-next=city;else /若为空表，插到头结点之后p=p_prior;city-next=p-nex

18、t; p-next=city; return 1;int delName(Linklist L,char name20)/利用城市名称删除int flag=0;int seat=1;Linklist p=L;if(p-next=NULL)printf(该链表中没有元素,删除失败n);else while(p-next!=NULL)if(!strcmp(p-next-name,name)flag=1;printf(城市 %s 被删除n,name);Linklist q=p-next;p-next=q-next;free(q);else p=p-next;return flag;int delPo

19、s(Linklist L,int px,int py)/利用坐标删除int flag=0;Linklist p=L;if(p-next=NULL)printf(该链表中没有元素,删除失败n);else while(p-next !=NULL)if(p-next-posx=px&p-next-posy=py)Linklist q=p-next;p-next=q-next;free(q);flag=1;printf(坐标为 (%d,%d) 的城市被删除n,px,py);else p=p-next;return flag;int update(Linklist L,char name20)/更新in

20、t flag=0;Linklist p=L-next;if(L-next=NULL|L=NULL)printf(该链表中没有元素,更新失败n);elsewhile(p!=NULL)if(!strcmp(p-name,name)flag=1;printf(您要更新的是 %s 城市n,p-name);printf(请输入横坐标x: );scanf(%d,&p-posx);printf(请输入纵坐标y: );scanf(%d,&p-posy);p=p-next;return flag;int getPos(Linklist L,char name20)/给定一个城市名,返回城市坐标int flag=

21、0;Linklist p=L-next;if(L-next=NULL|L=NULL)printf(该链表中没有元素,返回坐标失败n);elsewhile(p!=NULL)if(!strcmp(p-name,name)flag=1;printf(您要查看的是 %s 城市n,p-name);printf(该城市坐标为:(%d,%d) n,p-posx,p-posy);p=p-next;return flag;int getCity(Linklist L,int px,int py,int d)/给定一个城市坐标P,返回距离小于等于d的城市int flag=0;double distance;Lin

22、klist p=L-next;if(L-next=NULL|L=NULL)printf(该链表中没有元素,返回坐标失败n);elsewhile(p!=NULL)distance=sqrt(p-posx-px)2+(p-posy-py)2);if(distancename);p=p-next;printf(n);return flag;void main()Linklist L=NULL;printf(n * 欢迎使用城市链表系统*n);printf( * 1 建立城市链表 *n); printf( * 2 插入链表记录 *n);printf( * 3 查询链表记录 *n);printf( *

23、4 删除链表记录 *n);printf( * 5 显示链表记录 *n);printf( * 6 更新链表信息 *n);printf( * 7 返回城市坐标 *n);printf( * 8 查看与坐标P距离小于等于D的城市 *n);printf( * 9 退出链表系统 *n); printf( * 欢迎使用城市链表系统*n);int main_flag=0;int flag;int menu;printf(请选择1-9：);scanf(%d,&menu);while(menu)switch(menu)case 1:/建立城市链表 L=creatLink();printf(建立城市链表：);pri

24、ntList(L);main_flag=1;break;case 2:/插入链表记录if(main_flag=1)char name20;int px,py;printf(请输入城市名称：);scanf(%s,name);printf(请输入横坐标x: );scanf(%d,&px);printf(请输入纵坐标y: );scanf(%d,&py);Linklist p=(Linklist)malloc(LEN); /新结点strcpy(p-name,name);p-posx=px;p-posy=py;insert(L,p); /有序的插入新结点printf(插入后的城市链表为：);printL

25、ist(L);else printf(nERROR: 链表还没有建立，请先建立链表n);break;case 3:/查询链表记录int way;char name20;int px,py;if(L!=NULL)if(main_flag)printf( 选择查找方式： 1.按城市名 2.按城市坐标 t选择: );scanf(%d,&way);if(way=1)printf(n请输入城市名:);scanf(%s,name);flag=searchName(L,name);if(flag=0) printf(无此城市记录，查找失败！n);else if(way=2)printf(请输入横坐标x: )

26、;scanf(%d,&px);printf(请输入纵坐标y: );scanf(%d,&py);flag=searchPos(L,px,py);if(flag=0) printf(无此城市记录，查找失败！n);else printf(城市链表中无记录！n);break;else printf(链表中无记录！n);break;case 4:/删除链表记录int way;char name20;int px,py;printf(选择删除方式：1.按城市名称 2. 按城市坐标 t选择: );scanf(%d,&way);if(way=1)printf(请输入城市名称: );scanf(%s,name)

27、;flag=delName(L,name);if(flag)printf(删除%s城市后：n,name);printList(L);else printf(无该名字的城市，删除失败!n);else if(way=2)printf(请输入横坐标x: );scanf(%d,&px);printf(请输入纵坐标y: );scanf(%d,&py);flag=delPos(L,px,py);if(flag)printf(删除坐标为(%d,%d)的城市后：n,px,py);printList(L);else printf(无该坐标的城市，删除失败!n);else printf(ERROR!n);brea

28、k;case 5:/显示链表记录printf(当前链表记录如下：);printList(L);break;case 6:/更新链表信息char name20;printf(请输入需要更新的城市名称:);scanf(%s,name);printf(n);flag=update(L,name);if(flag)printf(更新城市信息成功！n);else printf(记录中不存在此城市！n);break;case 7:/返回城市坐标char name20;printf(请输入需要返回坐标的城市名称:);scanf(%s,name);printf(n);flag=getPos(L,name);i

29、f(!flag)printf(记录中不存在此城市！n);break;case 8:/查看与坐标P距离小于等于D的城市int px,py,d;printf(请输入P的横坐标x: );scanf(%d,&px);printf(请输入P的纵坐标y: );scanf(%d,&py);printf(请输入距离d: );scanf(%d,&d);flag=getCity(L,px,py,d);if(!flag)printf(不存在与坐标 (%d,%d) 距离小于%d的城市n,px,py,d);break;case 9: exit(0);/退出链表系统default: printf(n菜单选择错误，请重新输入!n);printf(选择1-9：);scanf(%d,&menu);7、 用户使用手册（1）本程序执行文件为“城市链表.exe”。（2）进入本系统后，可以选择菜单功能项，首先选择功能1建立城市链表的基本数据后方可进行2-8的功能。（3）在查询和删除链表记录中，均可以根据需要按照两种方式执行链表操作，一种是按照城市的名称，一种则是按照城市的坐标实现。