城市链表-数据结构课程设计

设计题目<一>： 2.4.3城市链表查询系统 一、设计要求 1．问题描述

将若干个城市的信息，存入一个带头结点的单链表。结点中的城市信息包含城市名和城市的位置坐标。要求能够利用城市名和位置坐标进行相关查找、插入、删除、更新等操作。

2．需求分析

（1）、创建一个城市链表，能够输入城市信息，即城市名和城市位置坐标； （2）、能够根据城市名查询其位置坐标； （3）、根据离中心坐标距离查询城市名； （4）、能够插入城市信息； （5）、能够删除城市信息； （6）、能够更新城市信息； （7）、执行完毕，退出程序。

二、概要设计 1．主界面设计

为了实现串基本操作演示系统各功能的管理，本系统设计一个含有多个菜单项的主控单，方便用户使用。本系统主控菜单运行界面如图1所示。

图1 城市链表操作系统主菜单

2．存储结构设计

1

数据结构课程设计报告

typedef struct CityList {

char CityName[10]; float X,Y;

struct CityList *Next;

}CityList, *LHead; // 结点类型，指针类型

3．系统功能设计

(1)创建城市链表。有函数void Create（）实现。调用主函数main（）和插入函数Insert（）来完成创建操作。

(2)查找操作。有函数void FindCity（）和函数void FindCityDistance（）实现。在创建链表的基础上正向和反向查找城市的信息。

(3)插入操作。有函数void Insert（）实现。根据用户的输入，系统自动在原有的链表中插入新的信息。

(4)删除操作。有函数void Delete（）实现。根据用户的输入，系统自动判断是否存在该信息，若存在，就给出提示进行删除操作，否则提示不存在输入的信息。

(5)更新操作。有函数void UpdateCity（）实现。根据用户的输入，系统自动判断是否存在该信息，若存在，就给出替换信息，否则提示不存在该信息并返回。

(6)退出操作。当用户选择7时即退出本系统，有主函数中的选择函数switch来实现。

三、模块设计 1．模块设计

本程序包含8个函数模块，其调用关系如图2所示。

主程序模块

子功能模块

图2模块调用关系示意图

2．系统子程序及功能设计

(1) typedef struct CITYLIST CityList; // 定义结构类型 (2) void Init(CityList *LHead); //初始化函数操作 (3) void Insert(CityList *LHead); //插入函数

2

数据结构课程设计报告

(4) void Delete(CityList *LHead); //删除函数 (5) void Create(CityList *LHead); //创建函数 (6) void FindCity(CityList* LHead); //查找城市操作

(7) void FindCityDistance(CityList* LHead); //根据中心坐标和距离进行的查找操作 (8) void UpdateCity(CityList* L //更新函数

3．函数主要调用关系图

1 2 4 5 6 7 8 main() 3 图3 系统函数调用关系图

四、详细设计 1．数据类型定义

(1)源程序文件名清单： #include #include

#include //字符串处理函数的头文件 #include //动态存储分配实现单元 #include (2)结构类型构造 typedef struct CityList {

char CityName[10]; float X,Y;

struct CityList *Next;

}CityList, *LHead; // 结点类型，指针类型

2．系统主要子程序详细设计

3

数据结构课程设计报告

(1).//****插入操作 void Insert(CityList *LHead) {

CityList* newNode; //定义指针结构为cityList型 char m;

newNode = (CityList*)malloc(sizeof(CityList)); //生成新结点 }

(2).//****删除操作

void Delete(CityList *LHead) {

char delCity[10];

printf(\"请输入要删除的城市名称并回车:\"); scanf(\"%s\if(LHead->Next == NULL) {

4

if(newNode == NULL) //验证空间申请是否成功 { }

printf(\"请输入城市名称并回车:\");

scanf(\"%s\ //指针的数据域 printf(\"请输入城市坐标x,y并回车:\");

scanf(\"%f%c%f\ //将城市信息填入新节点中 while(LHead->Next != NULL) { }

printf(\"已成功插入新城市信息!\\n\"); newNode->Next = LHead->Next;

LHead->Next = newNode; //将新节点插入链表

LHead = LHead->Next; //如果非空，HLead指针的位置向后移 printf(\"内存分配失败\\n\");

return; //若分配内存不成功，则返回继续分配。

数据结构课程设计报告

}

printf(\"您删除的城市不存在,请先创建城市!\\n\"); return;

while(strcmp(LHead->Next->CityName,delCity ))

//从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。 }

(3). //****更新操作

void UpdateCity(CityList* LHead) {

char CityName[10];

printf(\"请输入您要更新的城市名称并回车:\"); scanf(\"%s\ {

printf(\"您要更新的城市不存在，请先创建城市!\\n\");

if(LHead->Next == NULL)

{ }

LHead ->Next = LHead->Next->Next; //相等则删除此节点 printf(\"以成功删除此城市信息!\\n\");

LHead = LHead->Next; //不相等则指针LHead下移，继续查找

return; }

while(strcmp(LHead->Next->CityName,CityName))

//从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。

{ }

printf(\"请输入城市新信息.\\n\"); //输入城市新信息 printf(\"请输入城市新名并回车:\"); scanf(\"%s\printf(\"请输入城市新坐标并回车:\");

5

LHead = LHead->Next; //当不相等则指针LHead下移，继续查找

数据结构课程设计报告

}

scanf(\"%f\scanf(\"%f\printf(\"已成功更新城市信息!\\n\");

(4). //****正向查找操作 void FindCity(CityList* LHead) { }

(5). //****反向查找操作

void FindCityDistance(CityList* LHead) { //给定坐标和距离返回城市名

char m; float x; float y; float distance;

printf(\"请输入中心坐标x,y:\"); scanf(\"%f%c%f\

6

char CityName[30]; int j=0;

printf(\"请输入您要查找的城市名称并回车:\"); scanf(\"%s\

while(LHead->Next != NULL && strcmp(LHead->Next->CityName,CityName)) { }

if(LHead->Next == NULL) { }

printf(\"已找到该城市,坐标为:%.2f,%.2f\\n\

printf(\"您要查找的城市不存在,请先创建城市!\\n\"); return;

LHead = LHead->Next;

数据结构课程设计报告

}

printf(\"请输入距离:\"); scanf(\"%f\

if(LHead->Next == NULL) {

printf(\"您要查找的城市不存在,请先创建城市!\\n\"); return; }

LHead = LHead->Next; while(LHead != NULL) { }

if((x-LHead->X)*(x-LHead->X) + (y-LHead->Y)*(y-LHead->Y) <= distance*distance) { }

LHead = LHead->Next;

printf(\"已找到该城市,名称为:%s\\n\

printf(\"已找到该城市,坐标为:%.2f,%.2f\\n\

五、测试分析

系统运行主界面如图1所示。 各子系统测试运行结果如下。

1. 创建城市链表

在主菜单下，输入1并回车，根据提示进行创建城市信息。运行结果如图4所示。

7

数据结构课程设计报告

图4 城市链表的创建

2. 查询操作

然后返回主菜单，输入2并回车，根据提示输入查找的城市信息。运行结果如图5所示。

图5 城市查询运行界面

3. 根据位置坐标和距离查询城市

在主菜单下，输入3并回车，根据提示输入查找的城市信息。运行结果如图6所示。

8

数据结构课程设计报告

图6 根据位置坐标和距离进行查询

4.插入操作

在主菜单下，输入4并回车，根据提示插入城市信息。运行结果如图7所示。

图7 城市信息的插入

4. 删除操作

在主菜单下，输入5并回车，根据提示进行删除城市信息操作。运行结果如图8所示。

图8 城市信息的删除

5. 更新操作

在主菜单下，输入6并回车，根据提示进行城市信息的修改。运行结果如图9所示。

9

数据结构课程设计报告

图9 城市信息的更新

6． 退出。

在主菜单下，输入7并回车，即可退出本程序。

六、用户手册

(1)本程序执行文件为“城市链表操作系统.exe”。

(2)进入本系统之后，随即显示系统主菜单界面。用户可在该界面下按提示信息输入命令。

七、调试报告

(1) 错误分析

调试时while(strcmp(LHead->Next->CityName,CityName))出现错误，显示错误为‘cannot convert parameter 1 from 'char' to 'const char *'’前一个是char类型不能用于strcmp函数，后将char CityName[10]

(2) 创建城市链表时，输入城市信息较为麻烦，每个城市信息输入完后，若还想输入其它城市信息，则输入任意键继续，否则输入END退出，所以在输入信息时需注意输入步骤，以免发生输入混乱。

(3)花了一个礼拜来弄这个程序，结果做完后，虽然能成功运行，但还是有很多bug，反复的调试，修改，我头都晕了，程序员真的很难做啊。

八、程序清单

#include #include

#include //字符串处理函数的头文件 #include //动态存储分配实现单元 #include

10

数据结构课程设计报告

//****结构类型构造 typedef struct CityList {

char CityName[10]; float X,Y;

struct CityList *Next;

}CityList, *LHead; // 结点类型，指针类型

//****初始化操作 void Init(CityList *LHead)

{ //建立一个带头结点的单链线性表，LHead指向头结点 }

//****插入操作

void Insert(CityList *LHead) {

CityList* newNode; //定义指针结构为cityList型 char m;

LHead->Next = NULL;

newNode = (CityList*)malloc(sizeof(CityList)); //生成新结点

if(newNode == NULL) //验证空间申请是否成功 { }

printf(\"请输入城市名称并回车:\");

scanf(\"%s\ //指针的数据域 printf(\"请输入城市坐标x,y并回车:\");

scanf(\"%f%c%f\ //将城市信息填入新节点中 while(LHead->Next != NULL)

11

printf(\"内存分配失败\\n\");

return; //若分配内存不成功，则返回继续分配。

数据结构课程设计报告

}

{ }

printf(\"已成功插入新城市信息!\\n\"); newNode->Next = LHead->Next;

LHead->Next = newNode; //将新节点插入链表

LHead = LHead->Next; //如果非空，HLead指针的位置向后移

//****删除操作

void Delete(CityList *LHead) {

char delCity[10];

printf(\"请输入要删除的城市名称并回车:\"); scanf(\"%s\if(LHead->Next == NULL) { }

while(strcmp(LHead->Next->CityName,delCity ))

printf(\"您删除的城市不存在,请先创建城市!\\n\"); return;

//从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。 }

//****创建选择项操作 void Create(CityList *LHead) {

12

{ }

LHead ->Next = LHead->Next->Next; //相等则删除此节点 printf(\"以成功删除此城市信息!\\n\");

LHead = LHead->Next; //不相等则指针LHead下移，继续查找

数据结构课程设计报告

char sign[20]; //定义输入信息类型及长度

printf(\"【输入任意值后并回车，开始创建城市链表】or【输入END返回主菜单】\\n\");

//当输入END时，在任意输入，则退出此操作

scanf(\"%s\

while(strcmp(sign,\"END\")) //当输入END时，再任意输入，则退出此操作 {

Insert(LHead);

printf(\"【输入任意值后并回车，开始创建城市链表】or【输入END返回主菜单】

\\n\"); }

//****更新操作

void UpdateCity(CityList* LHead) {

char CityName[10];

printf(\"请输入您要更新的城市名称并回车:\"); scanf(\"%s\ {

printf(\"您要更新的城市不存在，请先创建城市!\\n\");

if(LHead->Next == NULL)

}

scanf(\"%s\

return; }

while(strcmp(LHead->Next->CityName,CityName))

//从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。

{ }

printf(\"请输入城市新信息.\\n\"); //输入城市新信息 printf(\"请输入城市新名称并回车:\");

13

LHead = LHead->Next; //当不相等则指针LHead下移，继续查找

数据结构课程设计报告

scanf(\"%s\printf(\"请输入城市新坐标并回车:\"); scanf(\"%f\scanf(\"%f\printf(\"已成功更新城市信息!\\n\");

}

//****正向查找操作

void FindCity(CityList* LHead) { }

//****反向查找操作

void FindCityDistance(CityList* LHead) { //给定坐标和距离返回城市名

char m; float x;

14

char CityName[30]; int j=0;

printf(\"请输入您要查找的城市名称并回车:\"); scanf(\"%s\

while(LHead->Next != NULL && strcmp(LHead->Next->CityName,CityName)) { }

if(LHead->Next == NULL) { }

printf(\"已找到该城市,坐标为:%.2f,%.2f\\n\

printf(\"您要查找的城市不存在,请先创建城市!\\n\"); return;

LHead = LHead->Next;

数据结构课程设计报告

}

float y; float distance;

printf(\"请输入中心坐标x,y:\"); scanf(\"%f%c%f\printf(\"请输入距离:\"); scanf(\"%f\

if(LHead->Next == NULL) {

printf(\"您要查找的城市不存在,请先创建城市!\\n\"); return; }

LHead = LHead->Next; while(LHead != NULL) { }

if((x-LHead->X)*(x-LHead->X) + (y-LHead->Y)*(y-LHead->Y) <= distance*distance) { }

LHead = LHead->Next;

printf(\"已找到该城市,名称为:%s\\n\

printf(\"已找到该城市,坐标为:%.2f,%.2f\\n\

//****主函数，设定界面 void main() {

system(\"color 0E\"); CityList* LHead; CityList* Store; char choice[3] = {1,2,3};

LHead = (CityList*)malloc(sizeof(CityList));

15

数据结构课程设计报告

Init(LHead); //建立空表 Store = LHead;

while(strcmp(choice,\"7\")) //操作界面 {

printf(\"********************************************\\n\"); printf(\"|=======→欢迎使用城市链表操作系统←=======|\\n\"); printf(\"|__________________________________________|\\n\"); printf(\"|*→ 1.创建城市链表 *|\\n\"); printf(\"|*→ 2.根据城市名查询城市 *|\\n\");

printf(\"|*→ 3.根据离中心坐标距离查询城市 *|\\n\");

printf(\"|*→ 4.插入新城市信息 *|\\n\"); printf(\"|*→ 5.删除城市信息 *|\\n\"); printf(\"|*→ 6.更新城市信息 *|\\n\"); printf(\"|*→ 7.退出 *|\\n\");

printf(\"|*→ 【小辉辉 制作 QQ-417933681】 *|\\n\"); printf(\"￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣\\n\"); printf(\"请看菜单输入您的选择并回车:\"); scanf(\"%s\

switch(choice[0])

{

case '1':

Create(Store); //构造并创建城市信息链表 break;

case '2':

FindCity(Store); //根据城市名查找城市位置 break;

case '3':

FindCityDistance(Store); //根据所给中心坐标和距离值，返回小于等于

所给距离值得节点信息。

break;

16

case '4':

数据结构课程设计报告

Insert(Store); //插入新结点 break;

case '5':

Delete(Store); //删除结点 break;

case '6':

UpdateCity(Store); //更新结点信息 break;

case '7': //退出

break;

default:

printf(\"您的输入错误,请看菜单选择\\n\"); break;

} } }

system(\"PAUSE\"); return ;

17