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

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

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

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

4、计（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(Linklist L,Linklist city) /插入 in

5、t 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() /主函数，实现链表各项操作的选择（3）函数主要调用关系图本系统3个子程序之间的主要

6、调用关系如图所示。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 name20; int px; int py; char end4=end; printf

7、(请输入城市名称、横坐标和纵坐标，建立城市链表，以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(请输入城市名称：); scanf(%s,name); return(L)

8、;插入链表记录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=NULL; p-next=ci

9、ty; 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); Linklis

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

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

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

13、Linklist L,Linklist city);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

14、(%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(请输入城市名称：); 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-ne

15、xt=NULL) printf(该链表中没有元素n); else while(p!=NULL) printf(%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); else while(p!=NULL) if(!strcmp(p-name,name) flag=1; pr

16、intf(您要查找的是 %s 城市n,p-name); printf(该城市坐标为 (%d,%d) n,p-posx,p-posy); 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); else while(p!=NULL) if(p-posx=px&p-posy=py) flag=1; printf(您要查找城市坐标为 (%d,%d) n,p-posx,p-posy

17、); printf(该城市是 %sn,p-name); p=p-next; return flag;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

18、=NULL) p=p_prior; city-next=NULL; 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

19、; printf(城市 %s 被删除n,name); Linklist q=p-next; p-next=q-next; free(q); else p=p-next; return flag;int delPos(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;

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

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

22、:(%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; Linklist p=L-next; if(L-next=NULL|L=NULL)printf(该链表中没有元素,返回坐标失败n); else while(p!=NULL) distance=sqrt(p-posx-px)2+(p-posy-py)2); if(distancename); p=p-next;

23、 printf(n); return 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 退出链表系统

24、*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(建立城市链表：); printList(L); main_flag=1; break; case 2:/插入链表记录 if(main_flag=1) char name20; int px,py; printf(请输入城市名称：); scanf(%s,name); prin

25、tf(请输入横坐标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(插入后的城市链表为：); printList(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: ); scanf(%d,&px);