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

《数据结构课程设计实验1_城市链表15324.pdf》由会员分享，可在线阅读，更多相关《数据结构课程设计实验1_城市链表15324.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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（）实现按照城市坐标查询的操作。删除链表记录。由 delName（）函数和 delPos（

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

4、设计 本程序包含两个模块：主程序模块和链表操作模块。其调用关系如下图所示：（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)/插入 int delNa

5、me(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);/新结点 1 2 8 9 6 7 5 4 3 10 2 2 2 2 2 11main（）.strcpy(p-name,name);p-posx=px;p-posy=py;insert(L,p);/插入新结点 printf(请输入城市名称：);sc

8、anf(%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=NULL

9、;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 LNode char name20;int posx;/横坐标 int posy;/纵坐标 struct LNode*next;LNode,*Linklist;/用于城市结点 int insert(Linklist

13、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(%d,&px);printf(请输入纵坐标

14、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-next=NULL)printf(该链表中没有元素n);else while

15、(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;printf(您要查找的是%s 城市n,p-name);printf(该城市坐标为(%d,%d)n,p-

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

17、st 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=city;else /若为空表，插到头结点之后 p=p_prior;city-

18、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 q=p-next;p-next=q-next;free(q);else p=p-next;return flag;

19、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;free(q);flag=1;printf(坐标为(%d,%d)的城市被删除n,px,py);.else p=p-next;return flag;int update(Linklist L,char name

20、20)/更新 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:);scanf(%d,&p-posx);printf(请输入纵坐标 y:);scanf(%d,&p-posy);p=p-next;return flag;int getPos(Linklist L,char name20)/给定一个城市名,返回城市坐标

21、 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(该城市坐标为:(%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

22、 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;printf(n);return flag;void main()Linklist L=NULL;printf(n *欢 迎 使 用 城 市 链 表 系 统*n);printf(*1 建 立 城 市 链 表 *n);printf(*2 插 入 链 表 记 录 *n);printf

23、(*3 查 询 链 表 记 录 *n);printf(*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

24、(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);printf(请输入横坐标 x:);scanf(%d,&px);printf(请输入纵坐标 y:);scanf(%d,&py);Linklist p=(Linklist)malloc(LEN);/新结点 strcpy(p-name,name);p-posx=px;p-

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

26、)printf(无此城市记录，查找失败！n);else if(way=2)printf(请输入横坐标x:);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 选择:);scan

27、f(%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(请输入横坐标 x:);scanf(%d,&px);printf(请输入纵坐标 y:);scanf(%d,&py);flag=delPos(L,px,py);if(flag)printf(删除坐标为(%d,%d)的城市后：n,px,py);printList(L);e

28、lse printf(无该坐标的城市，删除失败!n);else printf(ERROR!n);break;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(请输入需要返回

29、坐标的城市名称:);scanf(%s,name);printf(n);flag=getPos(L,name);if(!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）在查询和删除链表记录中，均可以根据需要按照两种方式执行链表操作，一种是按照城市的名称，一种则是按照城市的坐标实现。