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

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

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

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

3、Name函数实现依据城市名删除的操作， delPos函数实现依据城市坐标删除的操作。 显示链表记录。由 printList函数实现。该功能实现格式化的链表输出操作，可以显示修改后的链表状态。 更链表信息。由 update函数实现。该功能实现依据城市名更城市的坐标信息。 返回城市坐标。由getPos函数实现。该功能实现给定一个已存储的城市， 返回其坐标信息的操作。 查看与坐标 P 距离小于等于 D 的城市。由getCity函数实现。该功能实现返回与给定坐标 P 距离小于等于 D 的城市名称。 退出链表系统。由 exit0实现。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 delName(Linklist

5、 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 个子程序之间的主要调用关系如下图。11main123456

6、78910222224、具体设计（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=city;else/

9、假设为空表，插到头结点之后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“);elsewhile(p-next!=NULL)if(!strcmp(p-next-name,name)flag=1;printf(“城市 %s 被删除n“,name); Linklist q=p-next;p-next=

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

11、进展与演示，就没有进展扩展。如需实现，可在 Lnode 的定义中，参加 int num 等语句。 链表建立初期，个人的想法是依据增结点插入按挨次插入到链表中，删除时可以依据城市名称和城市坐标进展删除。在具体的实现过程中，使用了菜单项选择择的方法，便利用户使用系统。（2） 算法的时空分析算法使用动态安排空间的方式执行，故其执行时间与链表记录个数有关，假设有n 个城市结点，其时间简单度为 On。（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

13、 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(“nn“);printf(“城市t 坐标n“);printf(“n“);Linklist p=L-next; int n=1;if(L-next=NULL) printf(“

15、该链表中没有元素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“); elsewhile(p!=NULL)if(!strcmp(p-name,name)flag=1;printf(“您要查找的是 %s 城市n

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

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

18、ULL; 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“);elsewhile(p-next!=NULL)if(!strcmp(p-next-name,name)flag=1;printf(“城市 %s 被删除n“,name); Linklist q=p

19、-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“);elsewhile(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,

20、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“); 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-pos

21、y);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“); 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 ge

22、tCity(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“); elsewhile(p!=NULL)distance=sqrt(p-posx-px)2+(p-posy-py)2); if(distancename);p=p-next;printf(“n“); return flag;void mainLinklist L=NULL;printf(

23、“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

24、“); 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);printf(“请输入横坐标 x: “);scanf(“%d“,&px

25、);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)选择: “);print

26、f(“ 选择查找方式： 1.按城市名2.按城市坐标 tscanf(“%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);printf(“请输入纵坐标 y: “);scanf(“%d“,&py); flag=searchPos(L,px,py);if(flag=0) printf(“无此城市记录，查找失败！n“);

27、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); flag=delName(L,name); if(flag)printf(“删除%s 城市后：n“,name); printList(L);else printf(“无该名

28、字的城市，删除失败!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“); break;case 5:/显示链表记录printf(“当前链表记录如下：“); printList(L);break;case

29、 6:/更链表信息char name20;printf(“请输入需要更的城市名称:“); scanf(“%s“,name);printf(“n“); flag=update(L,name); if(flag)printf(“更城市信息成功！n“);elseprintf(“记录中不存在此城市！n“);break;case 7:/返回城市坐标char name20;printf(“请输入需要返回坐标的城市名称:“); scanf(“%s“,name);printf(“n“); flag=getPos(L,name); if(!flag)printf(“记录中不存在此城市！n“);break;cas

30、e 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)n“,px,py,d);break;printf(“ 不存在与坐标 (%d,%d)距离小于%d的城市case 9: exit(0);/退出链表系统default:printf(“n 菜单项选择择错误，请重输入!n“);printf(“选择 1-9：“);scanf(“%d“,&menu);7、 用户使用手册（1） 本程序执行文件为“城市链表.exe”。（2） 进入本系统后，可以选择菜单功能项，首先选择功能 1 建立城市链表的根本数据前方可进展 2-8 的功能。（3） 在查询和删除链表记录中，均可以依据需要依据两种方式执行链表操作， 一种是依据城市的名称，一种则是依据城市的坐标实现。