数据结构课程设计实验1

1、数据结构课程设计实验报告实验一 链表部分选题为：243城市链表1、需求分析(1) 创建一个带有头结点的单链表。(2) 结点中应包含城市名和城市的位置坐标。(3) 对城市链表能够利用城市名和位置坐标进行有关查找、插入、删除、更新 等操作。(4) 能够对每次操作后的链表动态显示。2、概要设计为了实现以上功能，可以从以下 3个方面着手设计。(1) 主界面设计为了实现城市链表相关操作功能的管理，设计一个含有多个菜单项的主控菜单子 程序以系统的各项子功能，方便用户使用本程序。本系统主控菜单运行界面如下 所示。1建立：2345678 9退田槌表系统_欢迎建用礙帀错表系统欢迎使甩據帀、槌耒系统“mm查询锂衰

2、记慕*删除槌表i己录«盒护樋烹记亲*表蜃盧*墾宕気巨离小于等于D的城市：(2) 存储结构设计本系统主要采用链表结构类型来表示存储在“城市链表”中的信息。其中链表结 点由4个分量组成：城市名name城市的横坐标posx、城市的纵坐标posy、指 向下一个结点的指针next。(3) 系统功能设计本程序设计了 9个功能子菜单，其描述如下： 建立城市链表。由函数 creatLink()实现。该功能实现城市结点的输入以及连 接。 插入链表记录。由函数insert()实现。该功能实现按坐标由小到大的顺序将结 点插入到链表中。 查询链表记录。由searchName()函数和 searchPos()

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

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

5、t searchPos(Linklist L,int px,int py) /以城市坐标查找 int insert(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,i

6、nt d)给定一个城市坐标P,返回距离小于等于d的城市? void mai n() 主函数，实现链表各项操作的选择(3) 函数主要调用关系图本系统3个子程序之间的主要调用关系如图所示。11main ()829101225226234、详细设计(1) 数据类型定义typedef struct LNode 城市结点char n ame20;in t posx;/ 横坐标int posy;/纵坐标struct LNode *n ext;LNode,*Li nklist;(2) 系统主要子程序详细设计 建立城市链表Linklist creatLink() /创建一个城市链表，返回头结点地址Linkli

7、st L=(Linklist)malloc(LEN);/头结点L-> next=NULL;Lin klist p;char n ame20;int px;in t py;char en d4="e nd"'end为输入结printf("请输入城市名称、横坐标和纵坐标，建立城市链表，以束标志n");printf("请输入城市名称：");sca nf("%s", name);while (strcmp( name,e nd)printf("请输入横坐标x:");scan f("

8、;%d",&px);printf("请输入纵坐标y：");scan f("%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); 插入链表记录int insert(Linklist L,Linklist city)/ 插入Linkli

9、st 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->n

10、ext=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->nex

11、t->name,name）flag=1;printf（"城市 s 被删除 n",name）;Linklist q=p->next; p->next=q->next;free（q）;else p=p->next;return flag;5、测试分析（ 1） 实验中遇到的问题以及对设计与实现的回顾讨论和分析 城市链表在开始的建立时，由于头结点指针的判断错误，导致链表头结点中 存有信息，而在后面的插入和删除操作中并未考虑到，导致链表记录出错， 指针错位。 在链表的删除过程中，由于删除的时判断的结点，故应找到起前驱指针，一 开始并未考虑到这些，在无法删

12、除的时候才想起来改进方法，后来设置了一 个 prior 指针，专门找到对应结点的前驱，方便删除操作。 课题拓展训练为为城市加入其他信息，如人口数等。考虑到此项添加仅是在 数据定义中再加入一个数据项， 为了方便实验进行与演示， 就没有进行扩展。 如需实现，可在 Lnode 的定义中，加入 int num 等语句。 链表建立初期，个人的想法是按照新增结点插入按顺序插入到链表中，删除 时可以按照城市名称和城市坐标进行删除。在具体的实现过程中，使用了菜 单选择的方法，方便用户使用系统。（ 2） 算法的时空分析算法使用动态分配空间的方式执行， 故其执行时间与链表记录个数有关， 如果有 n 个城市结点，其

13、时间复杂度为 O（n）。（ 3） 经验和体会 通过本次实验，对于链表部分的相关功能，如插入、删除、排序等相关算法进一 步熟悉了。能够利用所学知识， 解决相关问题， 并能够正确解决实验过程中出现 的差错。（ 4） 测试功能展示 城市链表的建立在主菜单下， 用户输入 1并回车，然后按照提示建立城市链表， 运行结果如下所 示：插入链表记录1-入入入石称：wuhanri _坐拯）C 21坐标护4& 城市犍表为:亦市 坐标hefeL <12,32> uu.han <21,45 >进择1 -丫 :查询链表记录:按城市名厦按城帀坐标选择：1i- i 3 e吕 rF F 2 e

14、elh h c 1=雪 市的标谥坐坐城h 饗坐疋?! 人章帀查帀 请sw诜T査1¥总K=51坐氛按城市坐标 选择：2删除链表记录$1-9； 4按城帀坐标选择;1轨赊方专严按城市名称 删入城帀务耙hefei績1日"1城rt JH：戒市 坐标wuilian <2145*1e称X:城 -入人入后 选请>请搐坐标iefei <12>32>.juhan <(21.45按城市坐标 选择：2除: 删后 被币、帀城 X2 2 U ? -1 3 & 2 < 3一 >>:X y 2 2式箱叮 4方坐坐12为 9:® 标 1

15、-奥入対坐 1.1E市 坐标wuhan<21 j. 45 >选择n 显示链表记录 更新链表信息 返回城市坐标 查看与坐标P距离小于等于D的城市18 n 坐坐：” - n 勺. 9 p p IM7 1-入入入帀 主辰青青盘3 32 4« v*X y 坐坐？ 瘀辭 - n 一 7 F p是 1-入入入 选淸请请篠籃坐标斶切距离小卩的城市6、源程序清单#i nclude<stdio.h>#i nclude<stdlib.h>#i nclude<stri ng.h>#in clude<math.h>#define LEN sizeo

16、f(LNode)typedef struct LNodechar n ame20;in t posx;/ 横坐标int posy;/纵坐标struct LNode *n ext;LNode,*Li nklist;用于城市结点in t in sert(L in klist L,L in klist city);Linklist creatLink() /创建一个城市链表，返回头结点地址Linklist L=(Linklist)malloc(LEN);/头结点L-> next=NULL;Lin klist p;char n ame20;int px;in t py;char en d4=&q

17、uot;e nd"'en d为输入结printf("请输入城市名称、横坐标和纵坐标，建立城市链表，以束标志n");printf("请输入城市名称：");sca nf("%s", name);while (strcmp( name,e nd)printf("请输入横坐标x:");scan f("%d",&px);printf("请输入纵坐标y：");scan f("%d"，&py);p=(Linklist)malloc(LE

18、N); / 新结点strcpy(p->n ame ,n ame);p->posx=px;p->posy=py;in sert(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

19、 n=1; if(L->next=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->nex

20、t=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 searchPos(Linklist L,int px,int py)/ 以城市坐标查找int flag=0;Linklis

21、t 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(Linklist L,Linklis

22、t 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

23、) 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(!s

24、trcmp(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 delPos(Linklist L,int px,int py)/ 利用坐标删除int flag=0;Linklist p=L;if(p->next=NULL)printf(" 该链表中没有元素 ,删除失败 n");else while(p->

25、;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)/ 更新int flag=0;Linklist p=L->next; if(L->next=N

26、ULL|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

27、;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"

28、,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");elsewhile(p!=NULL)dista nee二sqrt(p->posx-px)A2+(p->posy-py)A2)

29、;if(distance<=d)flag=1;printf(" 该城市为 :%s ",p->name);p=p->next;printf("n");return flag;void main()Linklist L=NULL;printf("n*n");printf("*n");printf("*n");printf("*n");printf("*n");printf("*n");printf("*n&quo

30、t;);printf("欢迎使用城市链表系统1 建立城市链表2 插 入链表记录3 查 询链表记录4 删 除链表记录5 显 示链表记录6 更 新链表信息7 返回城市坐标*n");printf(" 市 *n");8 查看与坐标 P 距离小于等于 D 的城printf("9 退 出链表系统*n");printf("*欢迎使用城市链表系统*n");int main_flag=0;int flag;int menu;printf(" 请选择 1-9： ");scanf("%d",&am

31、p;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);printf(

32、" 请输入纵坐标 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 n

33、ame20;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:

34、");scanf("%d",&px);printf(" 请输入纵坐标 y: ");scanf("%d",&py);flag=searchPos(L,px,py);if(flag=0) printf(" 无此城市记录，查找失败！ n"); else prin tf("城市链表中无记录！n");break;else printf("链表中无记录！n");break;case 4:/删除链表记录int way;char name20;int px,py;p

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