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

数据结构课程设计实验报告

实验一链表局部选题为：一城市链表

1、需求分析

(1)创立一个带有头结点的单链表。

(2)结点中应包含城市名和城市的位置坐标。

(3)对城市链表能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。

(4)能够对每次操作后的SS表动态显示。

2、概要设计

为了实现以上功能，可以从以下3个方面着手设计。

(1)主界面设计

为了实现城市链表相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以链

接系统的各项子功能，方便用户使用本程序。本系统主控菜单运行界面如下所示。

丽

鳏

欢

领

表

襄

1链

2录

记

表

槌

3录

记

表

槌

4录

记

表

槌

5后

槌

心

记

6表

7w标

星

8霍

睢

塞

9w表

统

链

币

城

菽

请选择1-9：

12)存储结构设计

本系统主要采用链表结构类型来表示存储在“城市链表”中的信息。其中链表结点由4个

分量组成：城市名name^城市的横坐标posx、城市的纵坐标posy、指向下一个结点的指

针nexto

(3)系统功能设计

本程序设计了9个功能子菜单，其描述如下：

①建立城市链表。由函数crealLink。实现。该功能实现城市结点的输入以及连接。

②插入链表记录。由函数insert。实现。该功能实现按坐标由小到大的顺序将结点插入到链

表中。

③查询链表记录。由searchName()函数和searchPos()函数实现。其中searchName()

实现按照城市名查询的操作，searchPos0实现按照城市坐标查询的操作。

④删除链表记录。由dclNamc()函数和dclPos()函数实现。其中delName()函数实

现按照城市名删除的操作，delPos()函数实现按照城市坐标删除的操作。

⑤显示链表记录。由prinlList1)函数实现。该功能实现格式化的链表输出操作，可以显

示修改后的链表状态。

⑥更新链表信息。由update〔)函数实现。该功能实现按照城市名更新城市的坐标信息。

⑦返回城市坐标。由getPos()函数实现。该功能实现给定一个已存储的城市，返回其坐

标信息的操作。

⑧查看与坐标P距离小于等于D的城市。由getCity()函数实现。该功能实现返回与给

定坐标P距图小于等于D的城市名称。

©退出链表系统。由exit9)实现。

3、模块设计

(1)模块设计

本程序包含两个模块：主程序模块和链表操作模块。其调用关系如下列图所示:

主程序模块链表操作模块

(2)系统子程序及功能设

本系统共设置3个子程序，各程序的函数名及功能说明如下：

①LinklistcrealLink()//创立一个城市链表，返回头结点地址

②printList(LinklistL)//打印头结点地址为L的城市链表

③intsearchName(LinklistL,charname[20])〃以城市,名查找

④intsearchPos(LinklistL,intpx,intpy)〃以城市坐标查找

⑤intinsert(LinklistL,Linklistcity)〃插入

@intdelName(LinklistL,charnameL20J)〃利用城市名称删除

⑦inidelPos(LinklisiL,inipx,inipy)〃利用坐标删除

⑧iniupdate(LinklislL,charname[20])//更新

⑨intgetPos(LinklistL,charname[2()])//给定一个城市名,返回城市坐标

⑩inigelCity(LinklislL,intpx,intpy,inld)//给定一个城市坐标P,返回距离小于等于d的

城市

⑪voidmain()〃主函数，实现链表各项操作的选择

(3)函数主要调用关系图

本系统3个子程序之间的主要调用关系如下图。

4、详

细设计

（1）数据类型定义

typedefstructLNode{〃城市结点

charname[20];

intposx;〃横坐标

intposy;//纵坐标

structLNode*next;

}LNode,*Linklist;

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

①建立城市链表

LinklistcreatLink()//创立一个城市链表，返回头结点地址

(

LinklistL=(Linklist)malloc(LEN);〃头结点

L->next=NULL;

Linklistp;

charnamc[20];

intpx;

intpy;

charend[4]="end";

printf(”请输入城市名称、横坐标和纵坐标，建立城市链表，以And为输入结束标志\n”);

printf("请输入城市名称：”)；

scanf("%sH,name);

while(strcmp(name,end))

(

primf(“清输入横坐标x:");

scanf("%d",&px);

printf("请输入纵坐标y：");

scanf(M%d",&py);

p=(Linklist)malloc(LEN);〃新结点

strcpy(p->name,name);

p->posx=px;

p->posy=py;

inserl(L,p);〃插入新结点

printf(”请输入城市名称：”)；

scanf(M%sM,name);

)

retum(L);

)

②插入链表记录

intinserl(LinklistL,Linklistcity){〃插入

Linklistp=L->next;

Linklistp_prior=L;

while(p!=NULL&&city->posx>=p->posx)

(

if(p->posx==city->posx&&p->posy==city->posy)

(

primf("重复输入!\nH);retum0;

)

p=p->next;

}//确定city插入的位置

while(p_prior->next!=p)

到对应结点的前驱，方便删除操作。

③课题拓展训练为为城市参加其他信息，如人口数等。考虑到此项添加仅是在数据定义中

再参加一个数据项，为了方便实验进行与演示，就没有进行扩展。如需实现，可在Lnode

的定义中，参加ininum等语句。

④链表建立初期，个人的想法是按照新增结点插入按顺序插入到链表中，删除时可以按照

城市名称和城市坐标进行删除。在具体的实现过程中，使用了菜单项选择择的方法，方

便用户使用系统。

(2)算法的时空分析

算法使用动态分配空间的方式执行，故其执行时间与链表记录个数有关，如果有n个城市

结点，其时间麦杂度为O(n)o

13)经验和体会

通过本次实验，对于链表局部的相关功能，如插入、删除、排序等相关算法进一步熟悉了。

能够利用所学知识，解决相关问题，并能够正确解决实验过程中出现的过失。

(4)测试功能展示

®城市链表的建立

在主菜单下，用户输入1并回车，然后按照提示建立城市链表，运行结果如下所示：

■叶:\计算机'在校课程卷靠结构课程设计'城市链表\Debug\城市链表.exe・

领触

添统

女

表

工

槌

■B链

2B录

记

录

3槌

记

鹦

录

4槌

记

5录

槌

息

6记

槌

7标

星

暨

城市

8离〃

睢

梦

9SI槌

H统

貂充

蠡

城

菽

呼

先

I主

I1

k

呈9:

I'名

币

I入

k

星、横坐标和纵坐标，建立城币链表，以，end，为输入结束标志

I

I也

典

k星：hefei

名

•入

IX:

坐

k星

典12

I入

I耨

星

k市32

表

人

I刖

I

kD

E镇：end

市

建

V城.

城市坐标

hefei<12,32)

选择-9：.

②插入链表记录

选2

在

、

1-称

会

EB乖:w

住

入1

E0坐X2

住:

0&45

后

E城

插

表

为

城市坐标

hefei<12,32)

wuhan<21,45>

选择1-9：

③查询链表记录:

近择1-9：3

皤查找方式：.按城市名

12.按城币坐标选择：1

1月:输2城市省:hefei

源妻查我电是hefei城币

吃;城币里标为<12,32)

远择1-9：3

验查找方式：1.按城市名

t«?2.按城市坐标选择：2

鱼凄查卷城币坐标为“2,32〉

该城市星hefei

④删除链表记录

、TI2

A

1-入

、

称

、

T也h

KS:e

入

T、2

K坐;

入

T、Axy::2

城

k链^

后

k表7

^/

城市坐标

hefei<12,32>

uuhan<21,45>

选14

9:

1-欠

选

按

方

^式1

•■

清1?按城市坐标选择：2

坐

人X12

聚

清^

坐32

为y

坐

蕾

市被

<删除

82>白向

坐

标

12为

删

城

,3232，币后

<1/：

城市

坐标

uuhan<21,45)

选择1-9：

⑤显示链表记录

选择工-9：5

当前链表记录如下:

——至底――

uuhan<21,45>

选择一9：

©更新链表信息

K先

.T

A上

\fl-9：6

1耳

K俞人需要更新的城市名称:wuhan

你

^的

城币

番

坐THwuhan

<

标x：23

坐

请

4林y：32

信

币息成功！

1-9:

⑦返回城市坐标

选择1-9：?

请输入需要返回坐标的城市名称Mihan

查

您

看的

城市

该

标vmhan

市

坐〉

玩:<23,32

1-9:

⑧查看与坐标P距离小于等于D的城市

先

-

主

E023

主

EO

H-21

al

-E

以

选98

七

1-翻

入

月p

注坐柢二23

入P

E0离坐标y：43

注

入8

目：1

不存在与坐标<23,43）距离小于1的城币

选择1-9：

6、源程序清单

#include<stdio.h>

#include<stdlib.h>

#inckide<string.h>

#include<math.h>

#dcfincLENsizcof(LNodc)

typedefstructLNode{

charname[20];

intposx;//横坐标

intposy;〃纵坐标

structLNode*next;

}LNode,*Linklist;

〃用于城市结点

intinsert(LinklistL,Linklistcity);

LinklistcreatLink。〃创立一个城市链表，返回头结点地址

LinklistL=(Linklist)malloc(LEN);〃头结点

L->next=NULL;

Linklistp;

charname[20];

intpx;

intpy;

charcnd[4]="cnd";

printff请输入城市名称、横坐标和纵坐标，建立城市链表，以'end为输入结束标志5”);

printf(”请输入城市名称：”)；

scanf("%s",name);

while(strcmp(name,end))

(

printf("请输入横坐标x:”);

scanf(M%d",&px);

printf("请输入纵坐标y：");

scanf("%d",&py);

p=(Linklist)malloc(LEN);//新结点

strcpy(p->name,name);

p->posx=px;

p->posy=py;

insert(L,p);〃插入新结点

printf("请输入城市名称：");

scanf("%sM,name);

)

return(L);

)

voidprintList(LinklistL)

(〃打印头结点地址为L的城市链表

printf(M\n------------------------\n");

printf("城市\t坐标\n")；

printf(M-.................................\n");

Linklistp=L->next;

intn=l;

if(L->next==NULL)printf("该链表中没有元素\n");

else

whilc(p!=NULL)

(

printf("%s",p->name);

printf(',\t(%d,%d)\nu,p->posx,p->posy);

p=p->next;

)

printf(M-.................................\n");

return;

intsearchName(LinklistL,charname[20]){〃以城市名查找

intflag=O;

Linklistp=L->next;

if(L->next==NULL)printf("该链表中没有元素，查找失败\n")；

else

{

whiIe(p!=NULL){

if(!strcmp(p->name,name))

(

flag=l;

printf("您要查找的是%s城市\n”,p->name);

printf("该城市坐标为(%d,%d)\n",p->posx,p->posy);

I

p=p->next;

1

}

returnflag;

}

intsearchPos(LinklistL,intpx,intpy){〃以城市坐标查找

intflag=O;

Linklistp=L->next;

if(L->next==NULL)printf("该链表中没有元素，查找失败\n”)；

else

(

whi!e(p!=NULL){

if(p->posx==px&&p->posy==py)

(

flag=l;

printf("您要查找城市坐标为(%d,%d)\n",p->posx,p->posy);

printf("该城市是%s\n",p->name);

)

p=p->next;

)

)

returnflag;

)

intinsert(LinklistL,Linklistcity){〃插入

Linklistp=L->next;

Linklistp_prior=L;

while(p!=NULL&&city->posx>=p->posx)

if(p>>posx==city->posx&&p->posy==city->posy)

printf("重复输入!\nn);return0;

I

p=p->next;

}//确定city插入的位置

while(p_prior->next!=p)

{

p_prior=p_prior->next;

}

if(p==NULL)

(

p=p_prior;

city->next=NULL;

p->next=city;

)

else〃假设为空表，插到头结点之后

(

p=p_prior;

city->next=p->next;

p->next=city;

)

return1;

)

intdelName(LinklistL,charname[20]){〃利用城市名称删除

intflag=0;

intseat=1;

Linklistp=L;

if(p->next==NULL)

printf("该链表中没有元素删除失败\n“);

else

(

whilc(p->next!=NULL)

{

if(!strcmp(p->next->name,name))

(

flag=l;

printf("城市%s被删除\n",name);

Linklistq=p->next;

p->ncxt=q->ncxt;

free(q);

)

else{p=p->next;J

)

returnflag;

}

intdelPos(LinklistL,intpx,intpy){〃利用坐标删除

intflag=O;

Linklistp=L;

if(p->next==NULL)

primf("该链表中没有元素，删除失败\n");

else

(

vvhilc(p->ncxt!=NLLL)

(

if(p->next->posx==px&&p->ncxt->posy==py)

(

Linklistq=p->next;

p->next=q->next;

free(q);

flag=l;

printf("坐标为(%d,%d)的城市被删除'n”,px,py);

)

else{p=p->next;}

)

)

returnflag;

}

intupdate(LinklistL,charname[20]){〃更新

intflag=0;

Linklistp=L->next;

if(L->nex匚=NULL||L=NULL)printf("该链表中没有元素，更新失败\n");

else

(

while(p!=NULL){

if(!strcmp(p->namc,namc))

(

flag=l;

printf("您要更新的是%s城市\n",p->name);

printf(”请输入横坐标x:");

scanf(u%d",&p->posx);

printf("请输入纵坐标y:");

scanf(0%dH,&p->posy);

)

p=p->next;

}

returnflag;

intgetPos(LinklistL,charname[20]){〃给定一个城市名,返回城市坐标

intflag=O;

Linklistp=L->next;

if(L〉nexl=NULL||L==NULL)prinifT该链表中没有元素,返回坐标失败\n)

else

{

while(p!=NULL){

if(!strcmp(p->name,name))

(

flag=l;

printf("您要查看的是%s城市\n”,p->namc);

printf("该城市坐标为:(%d,%d)\iT,p・>posxp>posy);

}

p=p->next;

1

)

returnflag;

)

intgetCity(LinklistL,intpx,intpy,intd){〃给定一个城市坐标P,返回距离小于等于d的城市

intflag=();

doubledistance;

Linklistp=L->next;

if(L->next==NULL||L==NULL)printf("该链表中没有元素,返回坐标失败\n")；

else

(

while(p!=NULL){

distance=sqrt((p->posx-px)A2+(p->posy-py)A2);

if(distance<=d)

(

flag=l;

printf("该城市为:％s",p->name);

)

p=p->next;

)

)

printf("\n");

returnflag;

1

voidmain()

(

LinklistL=NULL;

printf("\n**************欢送使用j城市链.表系统**************

printf(M*1建立城市链表"n")；

*2插入链表记录次\n");

printf(H*3查询链表记录*\n"）;

printf(M*4删除链表记录*\n”）；

printf("*5显示链表记录*\n"）；

printfC'*6更新链表信息"n”）；

printf("*7返回城市坐标*\n”）；

printf(H*8查看与坐标P距离小于等于D的城市*\n"）;

printf("*9退出链表系统叭n”）；

*************欢送使用城I|J链表系统****************\n')

intmain_flag=O;

intflag;

intmenu;

printf("请选择1-9：”)；

scanf("%d”,&menu);

while(menu)

(

switch(menu)

(

case1://建立城市链表

(

L=crealLink();

printf("建立城市链表：”)；

prinlList(L);

main_flag=l;

break;

)

case2:〃插入链表记录

(

if(main_flag==l)

(

charnamc[20];

intpx,py;

printf(”请输入城市名称：”)；

scanf("%s",narne);

printf(”请输入横坐标x:”)；

scanf("%d",&px);

printf("请输入纵坐标y:")；

scanf("%d",&py);

Linklistp=(Linklist)malloc(LEN);〃新结点

strcpy(p->namc,namc);

p->posx=px;

p->posy=py;

insert(L,p);〃有序的插入新结点

printf(”插入后的城市链表为：”)；

printList(L);

}

elseprintf("\nERROR:链表还没有建立，请先建立链表\n");

break;

)

case3:〃查询链表记录

(

intway;

charname[20];

intpx,py;

if(L!=NULL)

(

if(main_flag)

{

printfC,选择查找方式：1.按城市名2.按城市坐标\t选择

scanf("%d",&way);

if(way==l)

(

printf(u\n请输入城市名:")；

scanf("%s",name);

flag=searchName(L,name);

if(flag=O)prin【f("无此城市记录，查找失败！\n")；

)

elseif(way==2)

(

printf("请输入横坐标x:")；

scanf("％d”,&px);

printf("请输入纵坐标y:")；

scanf("％d”,&py);

flag=searchPos(L,px,py);

if(flag==0)printf("无此城市记录，查找失败！\nn);

}

elseprintf("城市链表中无记录!\n");

}

break;

}

elseprintf("链表中无记录!\n");

break;

(

case4://删除链表记录

(

intway;

charname[20];

intpx,py;

printf("选择捌除方式：1.按城市名称2.按城市坐标\t选择:")；

scanf(n%dH,&way);

if(way==l)

printf（"请输入城市名称:"）;

scanf("%s",name);

flag=delName(L,name);

if(flag)

(

printf("删除％$城市后：\n",name);

printList(L);