数据结构课程设计城市链表的设计与实现

1、数据结构课程设计题 目： 城市链表的设计与实现 二叉排序树基本操作的实现 年级 专业：09计算机科学与技术 姓 名：陈 戗 学 号： e10914049 城市链表的设计与实现i. 设计要求1. 问题描述 将若干城市信息，存入一个带头结点的单链表。节点中的城市信息包括城市名、城市位置坐标、城市人口、城市面积、城市特色等。要求能够利用城市名和位置坐标来进行查找、插入、删除、更新等操作。2. 需求分析1) 给定一个城市名，返回其位置坐标。2) 给定一个中心位置坐标p和一个距离d，返回所以与p距离小于等于d的城市。ii. 概要设计为了实现需求分析中的功能，可以从以下3方面着手设计。1. 主界面设计为了

2、实现城市链表的基本操作，设计一个包含多个菜单选项的主控制子程序以实现城市链表的各项子功能， 方便用户的使用。 本系统的主控制菜单运行界面如图1所示。 图1城市链表的主菜单2. 存储结构的设计本程序主要采链表结构类型来表示城市链表的信息。其中二叉树节点由7分量组成：城市的名称、城市的位的横坐标、城市位置的纵坐标、城市的面积、城市的人口、城市的特色，及指向自己结构体的指针。3. 系统功能设计本程序设置了6个子功能菜单，其设计如下。1) 建立城市链表。根据系统提示，选择功能项1，并根据提示逐个输入城市的名称、位置坐标、人口、面积、特色等。该功能由void create()函数实现。2) 显示全部城市

3、信息。根据系统提示，选择功能项2,即可显示全部的城市信息。该功能由print（）函数实现。3) 插入新的城市界节点信息。根据系统提示选择功能项3，可每次插入一个节点信息，如果要插入多个城市信息，需多次选择传插入功能。该功能由insert ()函数实现。4) 查询城市的信息。选择功能项4，进入查询菜单，有两种查询方式。一是跟根据城市名称查询，二是根据城市的位置坐标的距离查询。该功能由searchmenu ()和void searchname()及void searchposition()函数实现。5) 更新城市链表中不正确后过时的信息。可以通过城市名称查询到该节点，再以此输入城市名称坐标、人口、

4、面积、特色等属性。该功能由void updatecity()实现。6) 删除城市链表的节点信息。根据提示可以对城市链表中不需要的节点进行删除，删除的方式是输入城市名称，查询到该节点后删除。该功能由void delete ()函数实现。iii. 模块设计1. 模块设计本程序包含两个模块：主程序模块和二叉排序树操作模块。其调用关系如图2主程序模块城市链表的操作模块 图2模块调用示意图2. 系统子程序及其功能设计本系统共设计了9个子程序，个程序的的函数名及其功能说明如下：1) void init(citylist lhead);/创建头指针2) void create(citylist lhead)

5、;/创建城市链表3) int print(citylist lhead);/显示全部信息4) void insert(citylist lhead);/插入新城市信息5) int searchmenu(citylist lhead);/查询查询菜单6) void searchname(citylist lhead);/按名称查询7) void searchposition(citylist lhead);/按坐标查询8) void updatecity(citylist lhead);/更新城市信息9) void delete(citylist lhead);/删除城市信息3. 函数主要的调用

6、关系本系统9个子程序见的主要调用关系图3.searchname main()initcreatesearchpositionprintsearhminsertinsertenuupdatadeletesearchnameiv. 详细设计1. 数据类型定义本系统采用链表结构存储城市节点信息，节点定义如下： typedef struct citynodechar cityname30;/名称float x;/横坐标float y;/纵坐标int citypopulation;/人口float cityarea;/面积char citycharacteristic50;/特色struct cityn

7、ode *next;citynode,*citylist;2. 主要子程序的详细设计1) 城市链表的创建函数，主要用来建立城市链表。 void create(citylist lhead) int n;printf(请输入要创建的链表的城市个数：);scanf(%d,&n); for(int i=0;icityname);printf(请输入城市坐标x,y:t);scanf(%f%c%f,&newnode-x,&m,&newnode-y); printf(请输入城市的人口（万）: t);scanf(%d,&newnode-citypopulation);printf(请输入城市的面积(平方公里

8、): t);scanf(%f,&newnode-cityarea);printf(请输入城市的特色: t);scanf(%s,newnode-citycharacteristic);while(lhead-next != null)lhead = lhead-next;newnode-next = lhead-next;lhead-next = newnode;3) 城市信息查询函数如下：/*根据名称查询*/ void searchname(citylist lhead) citylist p=lhead;char sname30;if(p-next)printf(请输入您要搜索的城市名称n)

9、;scanf(%s,sname);while(p-next != null & strcmp(p-next-cityname,sname)p = p-next;if(p-next = null)printf(您要搜索的城市不存在n);return;printf(城市坐标为：n,p-next-x,p-next-y);elseprintf(链表未建立，请先建立链表n);/*根据坐标查询*/void searchposition(citylist lhead)char m;float x1;float y1;citylist p=lhead;int distance;if(p-next)printf

10、(请输入中心坐标x,yn);scanf(%f%c%f,&x1,&m,&y1);printf(请输入距离:);scanf(%d,&distance);printf(距中心坐标的城市的距离为,x1,y1); printf(%d的城市有:n,distance);p = p-next;while(p != null)if(x1-p-x)*(x1-p-x) + (y1-p-y)*(y1-p-y) cityname);printf(n,p-x,p-y);p = p-next;elseprintf(链表未建立，请先建立链表n);v. 测试分析1. 城市链表的建立首先进入主菜单，如图1。在主菜单下，用户根据菜

11、单的选项输入1，然后按照提示依次输入城市节点的属性。运行的结果如图4. 图4城市链表的建立2. 打印城市链表的所有节点信息在主菜单下，用户选择2，可以打印出全部的节点信息。运行的结果如图5. 图5全部节点信息3. 插入节点信息信息在主菜单下，用户选择3，可以插入一个新的节点信息。运行的结果如图6. 图6插入新的节点4. 删除城市链表的节点信息在主菜单下，用户选择6，首先通过输入关键字查询相关信息。运行的结果如图7. 图7删除节点信息5. 查找城市链表的节点在主菜单下，用户选择4，进入查找菜单，有两种查询方式。运行的结果如图8.和图9。 图8按城市名称查找节点信息 图9按城市位置和距离查找vi.

12、 原程序清单 #include#include#include#include/*城市链表*/typedef struct citynodechar cityname30;/名称float x;/横坐标float y;/纵坐标int citypopulation;/人口float cityarea;/面积char citycharacteristic50;/特色struct citynode *next;citynode,*citylist;void init(citylist lhead);/创建头指针void create(citylist lhead);/创建城市链表int print(

13、citylist lhead);/显示全部信息void insert(citylist lhead);/插入新城市信息int searchmenu(citylist lhead);/查询查询菜单void searchname(citylist lhead);/按名称查询void searchposition(citylist lhead);/按坐标查询void updatecity(citylist lhead);/更新城市信息void delete(citylist lhead);/删除城市信息/*初始化*/void init(citylist lhead)lhead-next = null

14、;/*创建城市链表*/void create(citylist lhead) int n;printf(请输入要创建的链表的城市个数：);scanf(%d,&n); for(int i=0;icityname);printf(请输入城市坐标x,y:t);scanf(%f%c%f,&newnode-x,&m,&newnode-y); printf(请输入城市的人口（万）: t);scanf(%d,&newnode-citypopulation);printf(请输入城市的面积(平方公里): t);scanf(%f,&newnode-cityarea);printf(请输入城市的特色: t);sc

15、anf(%s,newnode-citycharacteristic);while(lhead-next != null)lhead = lhead-next;newnode-next = lhead-next;lhead-next = newnode;/*显示全部城市信息*/int print(citylist lhead)citylist p=lhead;if(p-next)p=p-next;printf( 全部城市信息为 :n);printf(*n);printf(名称t坐标t人口t面积t特色n);while(p)printf(%st,p-cityname);printf(%.f,%.f)

16、t,p-x,p-y);printf(%dt,p-citypopulation);printf(%.ft,p-cityarea);printf(%sn,p-citycharacteristic);p = p-next;elseprintf(链表未建立，请先建立链表n);return 0;/*查询城市信息*/int searchmenu(citylist lhead)citylist p=lhead;int s; printf(#n);printf(| 查询菜单 |n); printf(|n);printf(| 1.按名称查询 |n);printf(| 2.按坐标查询 |n);printf(| 3

17、.返回上级菜单 |n);printf(#n);scanf(%d,&s); switch(s)case 1:searchname(p);break;case 2:searchposition(p);break;case 3:break;default:printf(输入错误,请重新输入n);break;return 0;/*根据名称查询*/void searchname(citylist lhead) citylist p=lhead;char sname30;if(p-next)printf(请输入您要搜索的城市名称n);scanf(%s,sname);while(p-next != null

18、 & strcmp(p-next-cityname,sname)p = p-next;if(p-next = null)printf(您要搜索的城市不存在n);return;printf(城市坐标为：n,p-next-x,p-next-y);elseprintf(链表未建立，请先建立链表n);/*根据坐标查询*/void searchposition(citylist lhead)char m;float x1;float y1;citylist p=lhead;int distance;if(p-next)printf(请输入中心坐标x,yn);scanf(%f%c%f,&x1,&m,&y1

19、);printf(请输入距离:);scanf(%d,&distance);printf(距中心坐标的城市的距离为,x1,y1); printf(%d的城市有:n,distance);p = p-next;while(p != null)if(x1-p-x)*(x1-p-x) + (y1-p-y)*(y1-p-y) cityname);printf(n,p-x,p-y);p = p-next;elseprintf(链表未建立，请先建立链表n);/*更新城市*/void updatecity(citylist lhead)char updname30;printf(请输入您要更新的城市名:n);s

20、canf(%s,updname);while(strcmp(lhead-next-cityname,updname)lhead = lhead-next;printf(请输入城市新名n);scanf(%s,lhead-next-cityname);printf(请输入城市新坐标n);scanf(%f,&lhead-next-x);scanf(%f,&lhead-next-y);printf(请输入城市的新人口（万）n);scanf(%d,&lhead-next-citypopulation);printf(请输入城市的新面积（平方公里）n);scanf(%f,&lhead-next-citya

21、rea);printf(请输入城市的新特色n);scanf(%s,lhead-next-citycharacteristic);/*删除城市*/void delete(citylist lhead)char delname30;printf(请输入要删除的城市名称:n);scanf(%s,delname);while(strcmp(lhead-next-cityname,delname)lhead = lhead-next;lhead -next = lhead-next-next;void main() system(color 1e);citylist lhead;int select;l

22、head = (citylist )malloc(sizeof(citynode);/建立头指针 init(lhead); citylist p= lhead; while(select!=8) printf(#n); printf(# 欢迎使城市链表系统 #n); printf(|n); printf(|* 1.创建城市链表 *|n); printf(|* 2.显示全部城市信息 *|n); printf(|* 3.插入新的城市 *|n); printf(|* 4.查询城市信息 *|n); printf(|* 5.更新城市信息 *|n); printf(|* 6.删除城市信息 *|n); pr

23、intf(|* 7.退出 *|n); printf(#n); scanf(%d,&select); switch(select) case 1:create(p);break;case 2:print(p);break;case 3:insert(p);break;case 4:searchmenu(p);break;case 5:updatecity(p);break;case 6:delete(p);break; case 7: break;default:printf(输入错误,请重新输入n);break; vii. 用户手册执行本程序后，即进入系统的主菜单。用户可以根据菜单的提示选择相

24、应的数字，进入相应的子菜单。本系统没有提供一次删除或依次插入多个城市信息功能，如果要一次操作多个城市信息，需多次选择相同的步骤。较为麻烦。viii. 小结 本系统能较好的实现城市链表的基本操作，但由于过于简单存在许多不足，特别是在功能上。再调试本程序时，出现了诸如，链表的操作，指针的应用等一些数据结构和c语言面基础性的错误，消耗了较多时间。总之此次课设让我深刻认识到了理论和实践的巨大差异，对自己今后的职业生涯有一定的帮助。二叉排序树的基本操作的实现ix. 设计要求3. 问题描述 从磁盘读入一组数据，建立二叉排序树并对其进行查找、遍历、插入、删除等基本操作。4. 需求分析建立二叉排序树并对其进行

25、查找，包括成功和不成功两种情况。x. 概要设计为了实现需求分析中的功能，可以从以下3方面着手设计。4. 主界面设计为了方便对二叉排序树的基本操作，设计一个包含多个菜单选项的主控制子程序以实现二叉排序树的各项功能。本系统的主控制菜单运行界面如图1所示。图1二叉排序树的基本操作的主菜单5. 存储结构的设计本程序主要采二叉树结构类型来表示二叉排序树。其中二叉树节点由1个表示关键字的分量组成，还有指向该左孩子和右孩子的指针。6. 系统功能设计本程序设置了5个子功能菜单，其设计如下。1) 建立二叉排序树。根据系统提示，输入节点的关键字，并以0作为结束的标识符。该功能由bstree create()函数实

26、现。2) 插入二叉排序新的节点信息。每次只能够插入一个节点信息，如果该节点已经存在，则不插入。该功能由bstree insert(y)函数实现。3) 查询二叉排序树的信息。每次进行查询，成功则显示“查询到该节点”，不成功则“显示查询不到该节点“该功能由bstree search()函数实现。4) 删除二叉排序树的节点信息。可以对二叉排序树中不需要的节点进行删除，删除的方式是输入关键字，查询到该节点后删除。该功能由bstree delete()函数实现。 5) 遍历二叉排序树。遍历二叉排序树可以显示该二叉排序树的全部节点信息。该功能由void traverse()实现。xi. 模块设计4. 模块

27、设计本程序包含两个模块：主程序模块和二叉排序树操作模块。其调用关系如图2主程序模块二叉排序树操作模块 图2模块调用示意图5. 系统子程序及其功能设计本系统共设计了5个子程序，个程序的的函数名及其功能说明如下：1) bstree create(); /创建二叉排序树2) bstree insert(bstree tree,int key); /插入3) bstree search(bstree tree,int key); /查找4) void traverse(bstree tree); /遍历5) bstree delete(bstree tree,int key); /删除信息6. 函数主

28、要的调用关系本系统9个子程序见的主要调用关系图3.main()main()insert()search( )traverse ()delete ()xii. 详细设计3. 数据类型定义本系统采用二叉树结构存储节点信息，节点定义如下： typedef struct bstnodeint key;struct bstnode *lchild,*rchild;bstnode,* bstree;4. 主要子程序的详细设计1) 二叉排序树的创建函数，主要用来建立二叉排序树。 bstree create() int key;bstree tree=null; /初始化空树scanf(%d,&key); w

29、hile(key!=0)tree=insert(tree,key); /逐个插入节点scanf(%d,&key);return tree;2) 二叉排序插入函数如下： bstree insert(bstree tree,int key)bstree p=tree;bstree s,f;while (p!=null)f=p; if(key=p-key) return tree; if(keykey) p=p-lchild; else p=p-rchild;s=(bstree)malloc(sizeof(bstnode);s-key=key;s-lchild=null;s-rchild=null;

30、if(tree=null) return s; /新节点为二叉排序树的根if(keykey) f-lchild=s; else f-rchild=s; return tree; 3) 二叉排序树查询函数如下： bstree search(bstree tree,int key)bstree p=tree; int flag=0; while(p!=null) if(p-key=key) printf(查询到该节点！);flag=1;return(p);break;if (keykey) p=p-lchild; else p=p-rchild; if(flag=0)printf(查询不到关键字为

31、%d的节点！,key);return null; xiii. 测试分析6. 二叉排序树的建立首先进入主菜单，如图1。在主菜单下，用户根据菜单的选项输入1，然后按照提示建立二叉排序树，并以0未结束符。运行的结果如图4. 图4二叉排序树的建立7. 遍历二叉树的节点信息在主菜单下，用户选择4，可以打印出全部的节点信息。运行的结果如图5. 图5遍历二叉排序树8. 插入节点信息信息在主菜单下，用户选择2，可以插入一个新的节点信息。运行的结果如图6.图6插入新的节点9. 查询二叉树的节点信息在主菜单下，用户选择3，首先通过输入关键字查询相关信息。运行的结果如图7. 图7查询节点信息10. 删除二叉树的节点

32、在主菜单下，用户选择5，可以通过输入要删除的关键字来删除该节点的全部信息。运行的结果如图8. 图8删除二叉排序树的节点xiv. 原程序清单#include#include#include/*二叉排序树的数据结构*/typedef struct bstnodeint key;struct bstnode *lchild,*rchild;bstnode,* bstree;bstree create(); /创建二叉排序树bstree insert(bstree tree,int key); /插入bstree search(bstree tree,int key); /查找void travers

33、e(bstree tree); /遍历bstree delete(bstree tree,int key); /删除/*创建二叉排序树*/bstree create() int key;bstree tree=null; /初始化空树scanf(%d,&key); while(key!=0)tree=insert(tree,key); /逐个插入节点scanf(%d,&key);return tree;/*插入*/ bstree insert(bstree tree,int key)bstree p=tree;bstree s,f;while (p!=null)f=p; if(key=p-ke

34、y) return tree; if(keykey) p=p-lchild; else p=p-rchild;s=(bstree)malloc(sizeof(bstnode);s-key=key;s-lchild=null;s-rchild=null;if(tree=null) return s; /新节点为二叉排序树的根if(keykey) f-lchild=s; else f-rchild=s; return tree;/*查找*/bstree search(bstree tree,int key)bstree p=tree; int flag=0; while(p!=null) if(p

35、-key=key) printf(查询到该节点！);flag=1;return(p);break;if (keykey) p=p-lchild; else p=p-rchild; if(flag=0)printf(查询不到关键字为%d的节点！,key);return null; /*遍历*/void traverse(bstree tree)if(tree) traverse(tree-lchild); printf(%4d,tree-key); traverse(tree-rchild); /*删除*/bstree delete(bstree tree,int key)bstree p=tr

36、ee; bstree f,s,q; f=null;while(p) /查找关键字为key的节点if(p-key=key) break; f=p; if(p-keykey) p=p-lchild;else p=p-rchild;if (p=null) return tree; if (p-lchild=null)|(p-rchild=null) if(f=null) if(p-lchild=null) tree=p-rchild;else tree=p-lchild;else if (p-lchild=null) if(f-lchild=p) f-lchild=p-rchild; else f-rchild=p-rchild; else if(f-lchild=p) f-lchild=p-lchild; else f-lchild=p-lchild; free(p);el