数据结构——城市链表_将若干城市的信息,存入一个带头节点的单链表。结点中的城市信息包括城市名和城市

 

一、题目的内容及要求

【问题描述】

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

【基本要求】

1. 给定一个城市名，返回其位置坐标；

（2） 给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。    

• 需求分析

城市链表系统能够实现对城市信息的登记、查询、插入、删除，以及根据城市坐标对城市进行写入和读出。

1、界面菜单

  用菜单展示功能选项，根据菜单显示，用户可以输入数字来选择相应功能选项，完成相应操作，若输入非菜单中的数字选项，则报错，进行重新选择。

2、根据城市名查找城市信息

用户根据提示进行相关操作，输入对应功能序号进行操作，显示城市的详细信息（包括城市名、城市坐标、城市介绍）

3、修改、插入、更新城市信息

 用户根据提示进行相关操作，根据提示输入数字确定是否修改、插入、更新学生信息，

4、删除城市信息    

 用户根据提示进行相应操作。输入所要删除城市名，进行删除，然后可进行选择决定是否继续执行此操输入“Y”则确定修改，输入“N”则取消修改。                                                                                    

1. 给城市名，返回其位置坐标

 用户根据提示进行相关操作，根据提示输入城市名确定是否存在这个城市，再返回其位置坐标。                                      

1. 给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市.

 用户根据提示进行相关操作，根据提示输入一个位置坐标P和一个距离D，根据计算比较，判断是否存在与P的距离小于等于D的城市，再返回其城市名。                

• 概要设计

(1)城市链表由城市名、城市坐标、城市介绍组成，这组学生信息具有相同的特性，属于同一数据对象，相邻数据元素具有序偶关系，该系统的数据是采用线性表进行存储；

(2)采用具有头节点的链表进行存储结构，实现关于城市信息处理的相关问题，运用结构体定义用一组连续的内存单元依次存放线性表的数据元素，包括存放城市名、城市坐标和城市介绍。

• 详细设计（包括数据结构的类型定义，每个操作的算法描述）

主函数中先从文件中读取学生信息，实现菜单页面选择对于城市信息进行不同的操作；登记学生信息，将文件内容读入并存放于链表中。查找、插入、删除、更新等操作主要根据输入的输出城市信息，遍历链表，依次用strcmp函数比较城市名是否相等，找到对应的结点位置，再分别进行操作。

• 源代码

#include<iostream>

#include<string.h>

#include<stdlib.h>

#include<math.h>

using namespace std;

typedef struct City{

struct City *next;//指针域

char cityname[20];//城市名

char cityinfo[100];//城市信息

float x;//x轴的距离

float y;//y轴的距离

}City,*CityList;

void INitCity(CityList &head){//初始链表和城市基本数据信息

head->next=NULL;//头结点置空

CityList head1=new City;

head1=head;

CityList newcity1=new City;

if(head1->next==NULL){

strcpy(newcity1->cityname,"十堰市");

strcpy(newcity1->cityinfo,"十堰市有着悠久的历史,被誉为中国卡车之都，中国商用车之都");

newcity1->x=6;

newcity1->y=10;

head1->next=newcity1;

head1=head1->next;

head1->next=NULL;}

CityList newcity2=new City;

if(head1->next==NULL){

strcpy(newcity2->cityname,"武汉市");

strcpy(newcity2->cityinfo,"武汉市是长江经济带核高水平科技创新中心、商贸物流中心和国际交往中心等为支撑的国家中心城市。");

newcity2->x=3;

newcity2->y=9;

newcity1->next=newcity2;

head1=head1->next;

head1->next=NULL;}

CityList newcity3=new City;

if(head1->next==NULL){

strcpy(newcity3->cityname,"宜昌市");

strcpy(newcity3->cityinfo,"宜昌市BRT是全国单条线路最长、车站最多的快速公交系统。");

newcity3->x=3;

newcity3->y=7;

head1->next=newcity3;

head1=head1->next;

head1->next=NULL;}

CityList newcity4=new City;

if(head1->next==NULL){

strcpy(newcity4->cityname,"襄阳市");

strcpy(newcity4->cityinfo,"襄阳市是国家历史文化名城，国务院批复确定的湖北省新型工业基地和鄂西北中心城市。");

newcity4->x=7;

newcity4->y=7;

head1->next=newcity4;

head1=head1->next;

head1->next=NULL;}

CityList newcity5= new City;

if (head1->next == NULL) {

strcpy(newcity5->cityname, "孝感市");

strcpy(newcity5->cityinfo, "孝感市位于湖北省中部的历史文化名城，拥有优美的自然景观。");

newcity5->x = 7;

newcity5->y = 5;

head1->next=newcity5;

head1=head1->next;

head1->next=NULL;}

CityList newcity6 = new City;

if (head1->next == NULL) {

strcpy(newcity6->cityname, "黄冈市");

strcpy(newcity6->cityinfo, "黄冈市位于湖北省东部，是中国的“口腔医学之都”。");

newcity6->x = 7;

newcity6->y = 3;

head1->next=newcity6;

head1=head1->next;

head1->next=NULL; }

CityList newcity7= new City;

if (head1->next == NULL) {

strcpy(newcity7->cityname, "随州市");

strcpy(newcity7->cityinfo, "随州市位于湖北省东部，是一个以农业为主导产业的城市。");

    newcity7->x = 7;

newcity7->y = 1;

head1->next=newcity7;

head1=head1->next;

head1->next=NULL;}

CityList newcity8 = new City;

if (head1->next == NULL) {

strcpy(newcity8->cityname, "黄石市");

strcpy(newcity8->cityinfo, "黄石市位于湖北省中部，国著名的“铜都”。");

newcity8->x = 14;

newcity8->y = 9;

head1->next=newcity8;

head1=head1->next;

head1->next=NULL; }

CityList newcity9 = new City;

if (head1->next == NULL) {

strcpy(newcity9->cityname, "荆门市");

strcpy(newcity9->cityinfo, "荆门市，素有“荆楚门户”之称。");

newcity9->x = 14;

newcity9->y = 6;

head1->next=newcity9;

head1=head1->next;

head1->next=NULL;}

CityList newcity10 = new City;

if (head1->next == NULL) {

strcpy(newcity10->cityname, "荆州市");

strcpy(newcity10->cityinfo, "荆州市是重要的公路交通枢纽和长江中游重要港口城市。");

newcity10->x = 14;

newcity10->y = 4;

head1->next=newcity10;

head1=head1->next;

head1->next=NULL;}

CityList newcity11 = new City;

if (head1->next == NULL) {

strcpy(newcity11->cityname, "咸宁市");

strcpy(newcity11->cityinfo, "咸宁市素有“湖北南大门”之称，国家森林城市等荣誉称号。");

newcity11->x = 14;

newcity11->y = 2;

head1->next=newcity11;

head1=head1->next;

head1->next=NULL;}   }

void MapShow(){//城市平面图

cout<<"-----------------------------城市平面图-----------------------------------------"<<endl;

    cout<<"******************************************************************************"<<endl;

    cout<<"**----------------------------<1>十堰市（6,10）                         **"<<endl;

    cout<<"**                         |                                          **"<<endl;  

    cout<<"**--<2>武汉市(3,9)------- |-------------------<8>黄石市(14,9)      **"<<endl;

    cout<<"**    |                     |                    |                    **"<<endl;

    cout<<"**    |                      |                    |                 **"<<endl;

    cout<<"**--<3>宜昌市(3,7)-----------<4>襄阳市(7,7)       |                 **"<<endl;

    cout<<"**---- |--------------------------|--------------------<9>荆门市(14,6)    **"<<endl;

    cout<<"**    |                       |                   |                 **"<<endl;

    cout<<"**--- -|-------------------------<5>孝感市(7,5）     |                 **"<<endl;

    cout<<"**    |                       |                   |                 **"<<endl;

    cout<<"**-----|--------------------------|------------------<10>荆州市(14,4)    **"<<endl;

    cout<<"**    |                       |                   |                 **"<<endl;

    cout<<"**--- -|-------------------------<6>黄冈市(7,3)      |                  **"<<endl;

    cout<<"**    |        ---->东        |                   |                  **"<<endl;

    cout<<"**-|---------|-------- -|-------------<11>咸宁市(14,2) **"<<endl;

    cout<<"**    |          北           |                    |                 **"<<endl;

    cout<<"**---- |-------------------------<7>随州市(7,1)       |                 **"<<endl;

    cout<<"**_____|_________________________|______________________|___________________**"<<endl;

    cout<<">>Enter键返回主界面继续进行选择"<<endl; }

void View(){

cout<<"_____________________________________________________________________________ "<<endl;

cout<<"|                  欢迎使用十堰市平面图系统                           |"<<endl;

cout<<"|                                                                     |"<<endl;

cout<<"|                  1.查看城市平面图                                   |"<<endl;

cout<<"|                  2.根据城市名查找城市信息                           |"<<endl;

    cout<<"|                  3.根据坐标查找城市信息                             |"<<endl;

cout<<"|                  4.插入城市信息                                     |"<<endl;

cout<<"|                  5.删除城市信息                                     |"<<endl;

cout<<"|                  6.更新城市信息                                     |"<<endl;

cout<<"|                  7.给城市名，返回其位置坐标                         |"<<endl;

cout<<"|   8.给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市.|"<<endl;

cout<<"|                 9.退出                                               |"<<endl;

cout<<"|____________________________________________________________________________|"<<endl;}

int QuerNName(CityList &head)//根据城市名查找城市信息

{   CityList head1 = new City;

    head1=head;

    head1 = head1->next;

char tempcityname[10];

cout<<"请输入要查询的城市名："<<endl;

cin>>tempcityname;

while(head1!=NULL)

{    

    if(strcmp(head1->cityname,tempcityname)==0){

     cout<<"城市名："<<head1->cityname<<endl;

     cout<<"城市介绍："<<head1->cityinfo<<endl;

cout<<"城市坐标：("<<head1->x<<","<<head1->y<<")"<<endl;

return 1;}

    else if(head1->next==NULL){

     cout<<"未找到所要查询的城市名！"<<endl;

     return 1;}

head1 = head1->next; }  

return 0; }

//根据坐标查找城市信息

int QuerxyName(CityList &head)

{   CityList head1 = new City;

    head1=head;

float x,y;

cout<<"请输入要查询城市名的横、纵坐标："<<endl;

cin>>x>>y;

while(head1!=NULL)

{   head1 = head1->next;

    if(head1->x==x&&head1->y==y){

     cout<<"城市名："<<head1->cityname<<endl;

     cout<<"城市介绍："<<head1->cityinfo<<endl;

cout<<"城市坐标：("<<head1->x<<","<<head1->y<<")"<<endl;

return 1;}

    else if(head1->next==NULL){

     cout<<"未找到所要查询的城市名！"<<endl;

     return 1;}   }  

return 0; }

int insertCity(CityList &head){//定点插入

    CityList head1 = new City;

    head1=head;

    head1 = head1->next;

    int index;//插入序号

    char cityname1[10];//插入城市姓名

char cityinfo1[200];//插入城市介绍

float x1,y1;

cout<<"请输入城市插入序号："<<endl;

cin>>index;

if(index<0) {

cout<<"输入序号"<<index<<"错误，请重新输入"<<endl;

cin>>index;}

cout<<"请输入城市插入城市名："<<endl;

cin>>cityname1;

cout<<"请输入城市插入介绍："<<endl;

cin>>cityinfo1;

cout<<"请输入城市插入x,y坐标："<<endl;

cin>>x1>>y1;

//通过循环判断是否有重复城市名和坐标

while(head1!=NULL){

    if(strcmp(head1->cityname,cityname1)==0){

     cout<<"你插入的城市名已经存在！"<<endl;  

return 1;}

else if(head1->x==x1&&head1->y==y1){

     cout<<"你插入的城市坐标已经存在！"<<endl;  

return 1;}

head1 = head1->next; }  

    head1=head;

while(--index){

//找到了index位置的那个节点

    head1 = head1->next;   

if(head1 == NULL)

  return 1;}

CityList newNode1 = new City;//创建节点

if(newNode1 == NULL)

 return 0;

strcpy(newNode1->cityname ,cityname1);

strcpy(newNode1->cityinfo ,cityinfo1);

newNode1->x = x1;

newNode1->y = y1;

//通过上述代码的循环找到了index位置的节点并赋值给head

newNode1->next = head1->next;

head1->next=newNode1;

return 0;}  

int DelCity(CityList &head) {//根据城市名删除

CityList head1 = new City;

    head1=head;

char cityname1[10];

char choose;

cout<<"请输入要删除的城市名："<<endl;

cin>>cityname1;

while(strcmp(head1->next->cityname,cityname1)) {

head1=head1->next;

if(head1->next==NULL) {

cout<<"没有查找到要删除的城市名！"<<endl;

return 0;}  }

CityList temp=head1;//删除城市前的一个城市

CityList del=head1->next;//删除城市

cout<<"你要删除的城市信息为："<<endl;

cout<<"城市名："<<del->cityname<<endl;

cout<<"城市介绍："<<del->cityinfo<<endl;

cout<<"城市坐标：("<<del->x<<","<<del->y<<")"<<endl;

cout<<"Y(yes)是确认删除，N(no)是否点请确认是否删除"<<endl;

cin>>choose;

if(choose=='Y'){

temp->next=del->next;

free(del);

cout<<"删除成功！"<<endl; }

else if(choose=='N'){

cout<<"删除已取消！"<<endl; }

return 0;}

int UpdateCity(CityList &head){//更新城市信息

CityList head1 = new City;

    head1=head;

    head1=head1->next;

if(head1->next==NULL){

cout<<"城市链表为空，请先添加城市！"<<endl;

return 0; }

char cityname1[10];

cout<<"请输入要更新的城市名："<<endl;

cin>>cityname1;

while(head1!=NULL){

if(strcmp(head1->cityname,cityname1)==0){

    cout<<"请输入城市名："<<endl;

    cin>>head1->cityname;

    cout<<"请输入城市介绍："<<endl;

    cin>>head1->cityinfo;

    cout<<"请输入城市横坐标x："<<endl;

      cin>>head1->x;

    cout<<"请输入城市纵坐标y："<<endl;

    cin>>head1->y;

    return 1;}

head1=head1->next;}

if(head1==NULL){

cout<<"没有查询到要更新的城市名"<<endl;

return 1; }

return 0;}

int Returnxy(CityList &head){//给定一个城市名，返回其位置坐标；

CityList head1 = new City;

    head1=head;

    head1 = head1->next;

char tempcityname[10];

cout<<"请输入要查询的城市名："<<endl;

cin>>tempcityname;

while(head1!=NULL){  

    if(strcmp(head1->cityname,tempcityname)==0){

cout<<"城市坐标：("<<head1->x<<","<<head1->y<<")"<<endl;

return 1; }

    else if(head1->next==NULL){

     cout<<"未找到所要查询的城市名！"<<endl;

     return 1;}

head1 = head1->next; }  

return 0; }

int FoundCity(CityList &head){//给位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。

CityList head1 = new City;

    head1=head;

    head1=head1->next;

    float temp_x,temp_y,temp_D;

    int x,y;

    int D;

    int number=0;

    cout<<"请输入位置坐标P，横坐标x,纵坐标y:"<<endl;

cin>>x>>y;

cout<<"请输入一个距离D:"<<endl;

cin>>D;

while(head1!=NULL){

temp_x=fabs(x-head1->x);

temp_y=fabs(x-head1->y);

temp_D=sqrt(temp_x*temp_x+temp_y*temp_y);

if(temp_D<=D){cout<<head1->cityname<<" ";

                       number++; }

      head1=head1->next;}

if(number==0)

  cout<<"没有符合的城市！"<<endl; }

int main(){

CityList head=new City;

INitCity(head);

int choice;

do{ View();

   cout<<"请输入你的选择的功能序号："<<endl;

   cin>>choice;

switch(choice){

case 1:  MapShow();system("pause");system("cls");break;

case 2:  QuerNName(head); system("pause");system("cls");break;

case 3:  QuerxyName(head); system("pause");system("cls");break;

case 4:  insertCity(head);system("pause");system("cls");break;

case 5:  DelCity(head);system("pause");system("cls");break;

case 6:  UpdateCity(head);system("pause");system("cls");break;

case 7:  Returnxy(head);system("pause");system("cls");break;

case 8:  FoundCity(head);system("pause");system("cls");break;

case 9:  exit(0);system("pause");system("cls");

case 10:  system("pause");system("cls"); View();

default:  cout<<"未找到此序号的功能，请输入有效选项序号！"<<endl; break; }

}while(choice);

return 0;}

• 运行结果及分析

进入页面菜单，选择相应操作：

 

 

选择选项1登记操作，查看城市平面图：

选择选项2，根据城市名查找城市信息：

选择选项3，进行查询操作：

选择选项4，根据坐标查找城市信息操作：

选择选项5，删除城市信息：

选择选项6，删除城市信息：

 

选择选项7，删除城市信息：

选择选项8，删除城市信息：

选择选项9，删除城市信息：

 

收获及体会，总结

完成了这次的数据结构课设报告，我收获了许多有用的知识，让我对数据结构这门课程有了更深的了解和学习也加深了对c语言编程能力，这次的课程设计是一次很好的对于数据结构这门课程的自我检验，让我在这次课设中做到查漏补缺，巩固相应的知识点。在这次编程的过程中，我也遇到了很多难题，在读取学生信息也就是输出学生信息这个程序时遇到了困难，代码一直报错，但在查询相关资料以及同学的帮助下，才发现自己在实现这个功能的代码写错了，及时修正也能正常运行了，让我感到非常开心。数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储在计算机中，并在这些数据上定义了一个运算集合，在这次的课设中，巩固了我对链表表的建立以及应用的相关知识，通过对学生信息管理系统的编程，开阔了我的思路，在课本遇到不懂的理论知识通过实践也豁然开朗了，在敲代码上还不够熟练，经常会出现一些小问题，所以今后要加强对代码的敲打学习。C语言是计算机程序设计的重要理论基础，在我们以后的学习和工作中都有着十分重要的地位。要学好这种语言，仅仅学习课本上的知识是不够的，还要经常自己动手，有较强的实践能力。只有多动手，经常编写程序，才能发现我们学习上的漏洞和自己的不足，并在实践中解决这些问题，不断提高自己转化知识的能力。回顾起此次课程设计，至今我仍感慨颇多，通过这次课程设计使我懂得了理论与实践相结合是很重要的，只有理论和知识是远远不够的，只有把所学的理论知识结合起来，从理论中得出结论，从而提高自己的实际动手能力和独立思考能力。