城市链表(实验报告)

本科学生综合性实验报告

学 院： 软件与通信工程学院 课程名称： 数据结构与算法 专业班级： 09通信工程1班 姓 名： 王燕 学 号： 0093731

学生实验报告（1）

学生姓名 王燕 学号 0093731 同组人 实验项目 城市链表 □必修 □选修 □演示性实验 □验证性实验 □操作性实验 □综合性实验 实验地点 指导教师 H113 蒋娜 实验仪器台号 实验日期及节次 周一5、6、7节 一、实验目的

1．掌握用 C语言调试程序的基本方法。

2．掌握线性表的基本运算，如创建、插入、删除等。

二、实验内容

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

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

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

三、实验要求

1．用C++/C完成算法设计和程序设计并上机调试通过。 2. 实验过程中学生调试完成，需向教师演示实验过程和结果。 3．撰写实验报告，提供实验结果和数据。

4．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。

5. 采用上机情况、程序质量、实习报告相结合的形式，满分为100分。 四、实验仪器

1. WindowsXP以上操作系统； 2. Visual C++6.0语言环境； 3. 每人一台PC机。

五、实验内容和步骤

1．启动Windows XP操作系统

打开计算机，启动Windows XP操作系统。

2．创建工作文件夹

创建Visual C++ 6.0的工作文件夹。

3．启动Visual C++ 6.0

建立一个空工程LinkList,在建立一个源文件citylinklist 4.编写代码如下：

#include #include #include #include #include typedef struct Node { char CityName[10]; float CityPoistion[2]; struct Node *next; }Node, * LinkList;

void InitList(LinkList * H) { * H=(LinkList)malloc(sizeof(Node)); (* H)->next=NULL; }

//建立城市信息链表，以城市名“no”作为结束标识符 void CreateCity(LinkList H) { Node * r, * s;; char name[10]; float x,y; r=H; printf(\"请输入若干个城市的信息！(以城市名no结束)\\n城市名 scanf(\"%s%f%f\ while(strcmp(name,\"no\")!=0) { s=(Node*)malloc(sizeof(Node)); strcpy(s->CityName,name); s->CityPoistion[0]=x; s->CityPoistion[1]=y; r->next=s; r=s;

scanf(\"%s%f%f\ } r->next=NULL; }

//在某个城市后面插入一个城市信息 int InsertCity(LinkList L) {

Node *p,*q;

经度 纬度\\n\");

char cityname[10],name[10]; //name为定位城市名，cityname为要插入城市信息的城市名 float x,y,x1,y1; //x1,y1是定位城市位置坐标，x,y是要插入城市信息的城市位置坐标 int flag; printf(\"请选择插入方式 (0 按城市名插入, 1 按城市位置坐标插入)：\"); scanf(\"%d\ switch(flag) { case 0: p=L;

printf(\"请输入在那个城市名后插入城市信息：\"); scanf(\"%s\ getchar(); while((p!=NULL)&&(strcmp(p->CityName,name)!=0)) p=p->next; if(p==NULL) { printf(\"没有找到城市名为 %s 的城市，插入位置不当！\\n\ } else { printf(\"在城市 %s 后插入一个城市信息：\\n城市名 经度 纬度\\n\ scanf(\"%s%f%f\ q=(Node*)malloc(sizeof(Node)); strcpy(q->CityName,cityname); q->CityPoistion[0]=x; q->CityPoistion[1]=y; q->next=p->next; p->next=q; }

break; case 1: p=L; printf(\"请输入在哪个城市位置坐标后插入城市信息：\"); scanf(\"%f%f\ getchar(); while((p!=NULL)&&(p->CityPoistion[0]!=x1)&&(p->CityPoistion[1]!=y1)) p=p->next; if(p==NULL) { printf(\"没有找到满足坐标为(%.2f , %.2f)的城市，插入位置不当！\\n\ } else { printf(\"在城市坐标为(%.2f , %.2f)的城市后面插入一个城市信息\\n城市名 经度 纬度\\n\

scanf(\"%s%f%f\

q=(Node*)malloc(sizeof(Node)); strcpy(q->CityName,cityname); q->CityPoistion[0]=x; q->CityPoistion[1]=y; q->next=p->next; p->next=q; } break; }

return 1; }

//删除一个城市信息

int DeleteCity(LinkList L) { Node *p,*q; char name[10]; //name是要删除城市信息的城市名 float x1,y1; //x,y是要删除城市信息的城市位置坐标 int flag; printf(\"请选择删除方式 (0 按城市名删除, 1 按城市坐标删除): \"); scanf(\"%d\ switch(flag) { case 0: p=L; q=p->next; printf(\"请输入要删除城市信息的城市名：\"); scanf(\"%s\

while(q!=NULL && strcmp(q->CityName,name)!=0) { q=q->next; p=p->next; } if(q==NULL) { printf(\"没有找到城市名为 %s 的城市，删除不成功！\\n\ } else { p->next=q->next;

printf(\"删除了城市 %s 的信息.\\n\ free(q); }

break; case 1: p=L; q=p->next;

printf(\"请输入要删除城市信息的城市位置坐标：\"); scanf(\"%f%f\ while((q!=NULL)&&(q->CityPoistion[0]!=x1)&&(q->CityPoistion[1]!=y1)) { q=q->next; p=p->next; } if(q==NULL) { printf(\"没有找到满足坐标为(%.2f , %.2f)的城市，删除不成功！\\n\ } else { printf(\"删除了城市 %s 的信息.\\n\ p->next=q->next; free(q); } break; }

return 1; }

//查找一个城市信息 int FindCity(LinkList L) {

Node *p;

char name[10]; //name是要查找城市信息的城市名 float x1,y1; //x,y是要查找城市信息的城市位置坐标 int flag;

printf(\"请选择查找方式 (0 按城市名查找, 1 按城市位置坐标查找)： \"); scanf(\"%d\ switch(flag) { case 0: p=L->next; printf(\"请输入要查找城市信息的城市名：\"); scanf(\"%s\ while(p!=NULL&&strcmp(p->CityName,name)!=0) p=p->next; if(p==NULL) { printf(\"没有找到城市名为 %s 的城市！\\n\ } else { printf(\"城市名为 %s 的城市位置坐标(%.2f , %.2f)\\n\

为

} break; case 1: p=L->next;

printf(\"请输入要查找城市信息的城市位置坐标：\"); scanf(\"%f%f\ while((p!=NULL)&&(p->CityPoistion[0]!=x1)&&(p->CityPoistion[1]!=y1)) p=p->next; if(p==NULL) { printf(\"没有找到城市位置坐标为(%.2f , %.2f)的城市！\\n\ } else

printf(\"城市位置坐标为(%.2f , %.2f)的是城市名为 %s \\n\ break; } return 1; }

//计算二维坐标两点间的距离

float Length(float x1,float y1,float x2,float y2) { float l; l=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)); return l; }

//以某点为中心找到所有小于某个距离的城市 void SubDAround(LinkList L) { Node * q; int n=0; float px,py,d; q=L->next; printf(\"请输入中心坐标点坐标以及距离：\"); scanf(\"%f%f%f\ printf(\"距中心坐标点(%.2f , %.2f) %.2f 的城市有：\\n\ while(q!=NULL) { if(Length(px,py,q->CityPoistion[0],q->CityPoistion[1])<=d) { printf(\"%s %.2f %.2f\\n\ q=q->next; n++; } else q=q->next;

} if(n==0) printf(\"没有任何城市符合条件！\\n\"); }

//显示所有城市信息

void DisplayCity(LinkList L) { Node * p; p=L->next; printf(\"城市名 经度 纬度\\n\"); while(p!=NULL) { printf(\"%s %.2f %.2f\\n\ p=p->next; } }

void main() { int k=1; LinkList CLL; InitList(&CLL); while(k) { printf(\"\\n\\n\\\城市信息管理系统\\n\\n\"); printf(\"\\\1.建立一个城市信息链表\\n\"); printf(\"\\\2.查找一个城市信息\\n\"); printf(\"\\\3.插入一个城市信息\\n\"); printf(\"\\\4.删除一个城市信息\\n\"); printf(\"\\\5.显示所有城市信息\\n\"); printf(\"\\\6.距某点小于某距离的所有城市信息\\n\"); printf(\"\\\0.退出\\n\"); printf(\"请选择操作项目：\"); scanf(\"%d\ system(\"cls\"); switch(k) { case 1:CreateCity(CLL);system(\"pause\");break; case 2:FindCity(CLL);system(\"pause\");break; case 3:InsertCity(CLL);system(\"pause\");break; case 4:DeleteCity(CLL);system(\"pause\");break; case 5:DisplayCity(CLL);system(\"pause\");break; case 6:SubDAround(CLL);system(\"pause\");break; case 0:break; } system(\"cls\"); } }

5.编译、运行，结果如下：

开始界面：

建立城市城市信息链表：

显示建立城市信息链表后的内容：

按城市名查找城市信息，而且查找成功：

按城市名查找城市信息，但查找不成功：

按城市坐标查找城市信息，而且查找成功：

按城市名查找城市信息，但查找不成功：

按城市名在某个城市后面插入一个城市信息，而且插入成功：

按城市名在某个城市后面插入一个城市信息，但插入不成功：

按城市坐标在某个城市后面插入一个城市信息，而且插入成功：

按城市坐标在某个城市后面插入一个城市信息，但插入不成功：

显示插入城市信息后城市链表的内容：

按城市名删除一个城市信息，而且删除成功：

按城市名删除一个城市信息，但删除不成功：

按城市坐标删除一个城市信息，而且删除成功：

按城市坐标删除一个城市信息，但删除不成功：

显示删除一些城市信息后城市链表的内容：

寻找以某点中心小于某个距离的所有城市信息，而且寻找成功：

寻找以某点中心小于某个距离的所有城市信息，但寻找不成功：

选择退出后的页面：

四、结论

1、实验结果

实现了在城市链表中利用城市名和位置坐标进行有关查找、插入、删除、更新基本要求的操作。同时也实现了拓展要求中的给定一个城市名，返回其位置坐标； 给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市的要求。

2、分析讨论

我的编程要求是全面，界面友好，具有主动控制权。这个程序结果绝对是我自己编出来的，在主函数中我要到了分支选择语句switch()，并且用了清屏函数system(“cls”)来保持友好的界面。其中“建立一个城市信息链表”既是初始化链表信息的操作，也是在已有信息的情况下对城市链表进行更新的操作，在该函数体中采用循环，并以城市名no结束链表的初始化或更新。查找、插入、删除一个城市信息这几个操作都具有选择权与自主输入权，可以选择按城市名或者城市位置

坐标进行查找、插入、删除，同时每一个操作项目都有操作不成功是的语句。在插入操作中，本来可以直接把一个城市信息插在链表最后面，但为了体现插入操作的特征，我给它安排了定位点，即在某个城市名或城市位置坐标后面插入一个城市信息。我还额外定义了一个显示城市链表所以信息的函数DisplayCity(),在删除或者插入一个或多个城市信息后可以显示城市链表里信息的变化。

五、指导教师评语及成绩：

评语：

成绩：

指导教师签名：

批阅日期：