数据结构课程设计报告实验1城市链表

1、-. z数据构造课程设计实验报告实验一 链表局部选题为：城市链表需求分析创立一个带有头结点的单链表。结点中应包含城市名和城市的位置坐标。对城市链表能够利用城市名和位置坐标进展有关查找、插入、删除、更新等操作。能够对每次操作后的链表动态显示。概要设计为了实现以上功能，可以从以下3个方面着手设计。主界面设计为了实现城市链表相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以系统的各项子功能，方便用户使用本程序。本系统主控菜单运行界面如下所示。存储构造设计本系统主要采用链表构造类型来表示存储在城市链表中的信息。其中链表结点由4个分量组成：城市名name、城市的横坐标pos*、城市的纵坐标po

2、sy、指向下一个结点的指针ne*t。系统功能设计本程序设计了9个功能子菜单，其描述如下：建立城市链表。由函数creatLink()实现。该功能实现城市结点的输入以及连接。插入链表记录。由函数insert()实现。该功能实现按坐标由小到大的顺序将结点插入到链表中。查询链表记录。由searchName函数和searchPos函数实现。其中searchName实现按照城市名查询的操作，searchPos实现按照城市坐标查询的操作。删除链表记录。由delName函数和delPos函数实现。其中delName函数实现按照城市名删除的操作，delPos函数实现按照城市坐标删除的操作。显示链表记录。由pri

3、ntList函数实现。该功能实现格式化的链表输出操作，可以显示修改后的链表状态。更新链表信息。由update函数实现。该功能实现按照城市名更新城市的坐标信息。返回城市坐标。由getPos函数实现。该功能实现给定一个已存储的城市，返回其坐标信息的操作。查看与坐标P距离小于等于D的城市。由getCity函数实现。该功能实现返回与给定坐标P距离小于等于D的城市名称。退出链表系统。由e*it0实现。模块设计1模块设计本程序包含两个模块：主程序模块和链表操作模块。其调用关系如下列图所示：主程序模块链表操作模块2系统子程序及功能设计本系统共设置3个子程序，各程序的函数名及功能说明如下： Linklist

4、creatLink() /创立一个城市链表，返回头结点地址printList(Linklist L)/ 打印头结点地址为L的城市链表 int searchName(Linklist L,char name20)/以城市名查找 int searchPos(Linklist L,int p*,int py)/以城市坐标查找 int insert(Linklist L,Linklist city)/插入 int delName(Linklist L,char name20)/利用城市名称删除 int delPos(Linklist L,int p*,int py)/利用坐标删除 int update

5、(Linklist L,char name20)/更新 int getPos(Linklist L,char name20)/给定一个城市名,返回城市坐标 int getCity(Linklist L,int p*,int py,int d)/给定一个城市坐标P,返回距离小于等于d的城市void main()/主函数，实现链表各项操作的选择3函数主要调用关系图本系统3个子程序之间的主要调用关系如下图。128967543102222211main4、详细设计数据类型定义typedef struct LNode/城市结点char name20;int pos*;/横坐标int posy;/纵坐标s

6、truct LNode *ne*t;LNode,*Linklist;2系统主要子程序详细设计建立城市链表Linklist creatLink() /创立一个城市链表，返回头结点地址Linklist L=(Linklist)malloc(LEN); /头结点L-ne*t=NULL;Linklist p;char name20;int p*;int py;char end4=end;printf(请输入城市名称、横坐标和纵坐标，建立城市链表，以end为输入完毕标志n);printf(请输入城市名称：);scanf(%s,name);while (strcmp(name,end)printf(请输入

7、横坐标*: );scanf(%d,&p*);printf(请输入纵坐标y：);scanf(%d,&py);p=(Linklist)malloc(LEN); /新结点strcpy(p-name,name);p-pos*=p*;p-posy=py;insert(L,p); /插入新结点printf(请输入城市名称：);scanf(%s,name);return(L);插入链表记录int insert(Linklist L,Linklist city)/插入Linklist p=L-ne*t;Linklist p_prior=L;while(p!=NULL & city-pos*=p-pos*)if

8、(p-pos*=city-pos* & p-posy=city-posy)printf(重复输入！n);return 0;p=p-ne*t; /确定city插入的位置while(p_prior-ne*t!=p)p_prior=p_prior-ne*t;if(p=NULL) p=p_prior;city-ne*t=NULL;p-ne*t=city; else /假设为空表，插到头结点之后 p=p_prior;city-ne*t=p-ne*t; p-ne*t=city; return 1;按名称删除链表记录int delName(Linklist L,char name20)/利用城市名称删除in

9、t flag=0;int seat=1;Linklist p=L;if(p-ne*t=NULL)printf(该链表中没有元素,删除失败n);else while(p-ne*t!=NULL) if(!strcmp(p-ne*t-name,name)flag=1;printf(城市 %s 被删除n,name);Linklist q=p-ne*t;p-ne*t=q-ne*t;free(q);else p=p-ne*t;return flag;5、测试分析实验中遇到的问题以及对设计与实现的回忆讨论和分析城市链表在开场的建立时，由于头结点指针的判断错误，导致链表头结点中存有信息，而在后面的插入和删除操

10、作中并未考虑到，导致链表记录出错，指针错位。在链表的删除过程中，由于删除的时判断的结点，故应找到起前驱指针，一开场并未考虑到这些，在无法删除的时候才想起来改良方法，后来设置了一个prior指针，专门找到对应结点的前驱，方便删除操作。课题拓展训练为为城市参加其他信息，如人口数等。考虑到此项添加仅是在数据定义中再参加一个数据项，为了方便实验进展与演示，就没有进展扩展。如需实现，可在Lnode的定义中，参加int num等语句。链表建立初期，个人的想法是按照新增结点插入按顺序插入到链表中，删除时可以按照城市名称和城市坐标进展删除。在具体的实现过程中，使用了菜单项选择择的方法，方便用户使用系统。算法的

11、时空分析算法使用动态分配空间的方式执行，故其执行时间与链表记录个数有关，如果有n个城市结点，其时间复杂度为On。经历和体会通过本次实验，对于链表局部的相关功能，如插入、删除、排序等相关算法进一步熟悉了。能够利用所学知识，解决相关问题，并能够正确解决实验过程中出现的过失。测试功能展示城市链表的建立在主菜单下，用户输入1并回车，然后按照提示建立城市链表，运行结果如下所示：插入链表记录查询链表记录：删除链表记录显示链表记录更新链表信息返回城市坐标查看与坐标P距离小于等于D的城市源程序清单#include#include#include#include#define LEN sizeof(LNode)

12、typedef struct LNodechar name20;int pos*;/横坐标int posy;/纵坐标struct LNode *ne*t;LNode,*Linklist;/用于城市结点int insert(Linklist L,Linklist city);Linklist creatLink() /创立一个城市链表，返回头结点地址Linklist L=(Linklist)malloc(LEN); /头结点L-ne*t=NULL;Linklist p;char name20;int p*;int py;char end4=end;printf(请输入城市名称、横坐标和纵坐标，建

13、立城市链表，以end为输入完毕标志n);printf(请输入城市名称：);scanf(%s,name);while (strcmp(name,end)printf(请输入横坐标*: );scanf(%d,&p*);printf(请输入纵坐标y：);scanf(%d,&py);p=(Linklist)malloc(LEN); /新结点strcpy(p-name,name);p-pos*=p*;p-posy=py;insert(L,p); /插入新结点printf(请输入城市名称：);scanf(%s,name);return(L);void printList(Linklist L) / 打印头

14、结点地址为L的城市链表printf(n-n);printf(城市t坐标n);printf(-n);Linklist p=L-ne*t;int n=1;if(L-ne*t=NULL) printf(该链表中没有元素n);else while(p!=NULL)printf(%s,p-name);printf(t(%d,%d)n,p-pos*,p-posy);p=p-ne*t;printf(-n);return ;int searchName(Linklist L,char name20)/以城市名查找int flag=0;Linklist p=L-ne*t;if(L-ne*t=NULL)print

15、f(该链表中没有元素,查找失败n);elsewhile(p!=NULL)if(!strcmp(p-name,name)flag=1;printf(您要查找的是 %s 城市n,p-name);printf(该城市坐标为 (%d,%d) n,p-pos*,p-posy);p=p-ne*t;return flag;int searchPos(Linklist L,int p*,int py)/以城市坐标查找int flag=0;Linklist p=L-ne*t;if(L-ne*t=NULL)printf(该链表中没有元素,查找失败n);elsewhile(p!=NULL)if(p-pos*=p*&

16、p-posy=py)flag=1;printf(您要查找城市坐标为 (%d,%d) n,p-pos*,p-posy);printf(该城市是 %sn,p-name);p=p-ne*t;return flag;int insert(Linklist L,Linklist city)/插入Linklist p=L-ne*t;Linklist p_prior=L;while(p!=NULL & city-pos*=p-pos*)if(p-pos*=city-pos* & p-posy=city-posy)printf(重复输入！n);return 0;p=p-ne*t; /确定city插入的位置wh

17、ile(p_prior-ne*t!=p)p_prior=p_prior-ne*t;if(p=NULL) p=p_prior;city-ne*t=NULL;p-ne*t=city; else /假设为空表，插到头结点之后 p=p_prior;city-ne*t=p-ne*t; p-ne*t=city; return 1;int delName(Linklist L,char name20)/利用城市名称删除int flag=0;int seat=1;Linklist p=L;if(p-ne*t=NULL)printf(该链表中没有元素,删除失败n);else while(p-ne*t!=NULL

18、) if(!strcmp(p-ne*t-name,name)flag=1;printf(城市 %s 被删除n,name);Linklist q=p-ne*t;p-ne*t=q-ne*t;free(q);else p=p-ne*t;return flag;int delPos(Linklist L,int p*,int py)/利用坐标删除int flag=0;Linklist p=L;if(p-ne*t=NULL)printf(该链表中没有元素,删除失败n);else while(p-ne*t !=NULL) if(p-ne*t-pos*=p*&p-ne*t-posy=py)Linklist

19、q=p-ne*t;p-ne*t=q-ne*t;free(q);flag=1;printf(坐标为 (%d,%d) 的城市被删除n,p*,py);else p=p-ne*t;return flag;int update(Linklist L,char name20)/更新int flag=0;Linklist p=L-ne*t;if(L-ne*t=NULL|L=NULL)printf(该链表中没有元素,更新失败n);elsewhile(p!=NULL)if(!strcmp(p-name,name)flag=1;printf(您要更新的是 %s 城市n,p-name);printf(请输入横坐标*

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

21、d) n,p-pos*,p-posy);p=p-ne*t;return flag;int getCity(Linklist L,int p*,int py,int d)/给定一个城市坐标P,返回距离小于等于d的城市int flag=0;double distance;Linklist p=L-ne*t;if(L-ne*t=NULL|L=NULL)printf(该链表中没有元素,返回坐标失败n);elsewhile(p!=NULL)distance=sqrt(p-pos*-p*)2+(p-posy-py)2);if(distancename);p=p-ne*t;printf(n);return

22、flag;void main()Linklist L=NULL;printf(n * 欢送使用城市链表系统*n);printf( * 1 建立城市链表 *n); printf( * 2 插入链表记录 *n);printf( * 3 查询链表记录 *n);printf( * 4 删除链表记录 *n);printf( * 5 显示链表记录 *n);printf( * 6 更新链表信息 *n);printf( * 7 返回城市坐标 *n);printf( * 8 查看与坐标P距离小于等于D的城市 *n);printf( * 9 退出链表系统 *n); printf( * 欢送使用城市链表系统*n);

23、int main_flag=0;int flag;int menu;printf(请选择1-9：);scanf(%d,&menu);while(menu)switch(menu)case 1:/建立城市链表 L=creatLink();printf(建立城市链表：);printList(L);main_flag=1;break;case 2:/插入链表记录if(main_flag=1)char name20;int p*,py;printf(请输入城市名称：);scanf(%s,name);printf(请输入横坐标*: );scanf(%d,&p*);printf(请输入纵坐标y: );sc

24、anf(%d,&py);Linklist p=(Linklist)malloc(LEN); /新结点strcpy(p-name,name);p-pos*=p*;p-posy=py;insert(L,p); /有序的插入新结点printf(插入后的城市链表为：);printList(L);else printf(nERROR: 链表还没有建立，请先建立链表n);break;case 3:/查询链表记录 int way;char name20;int p*,py;if(L!=NULL)if(main_flag)printf( 选择查找方式： 1.按城市名 2.按城市坐标 t选择: );scanf(

25、%d,&way);if(way=1)printf(n请输入城市名:);scanf(%s,name);flag=searchName(L,name);if(flag=0) printf(无此城市记录，查找失败！n);else if(way=2)printf(请输入横坐标*: );scanf(%d,&p*);printf(请输入纵坐标y: );scanf(%d,&py);flag=searchPos(L,p*,py);if(flag=0) printf(无此城市记录，查找失败！n);else printf(城市链表中无记录！n);break;else printf(链表中无记录！n);break;

26、case 4:/删除链表记录int way;char name20;int p*,py;printf(选择删除方式：1.按城市名称 2. 按城市坐标 t选择: );scanf(%d,&way);if(way=1)printf(请输入城市名称: );scanf(%s,name);flag=delName(L,name);if(flag)printf(删除%s城市后：n,name);printList(L);else printf(无该名字的城市，删除失败!n);else if(way=2)printf(请输入横坐标*: );scanf(%d,&p*);printf(请输入纵坐标y: );scanf(%d,&py);flag=delPos(L,p*,py);if(fl