2023年城市链表实验报告.pdf

《2023年城市链表实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年城市链表实验报告.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2 0 23-2 023 学年第一学期实验报告课程名称：算法与数据结构实验名称：城市链表一、实 验 目 的本次实验的重要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。同时，通过本次实验帮助学生复习高级语言的使用方法。二、实 验 内 容（-）城 市 链 表：将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息涉及：城市名，城 市的位置坐标。规定可以运用城市名和位置坐标进行有关查找、插入、删除、更新等操作。（二）约瑟夫环m的初值为20;密码：3,1,7,2,6,8,4（对的的结果应为6,1,4,7,2,3,5）,三、实 验环 境V S 2023、w

2、in 8.1四、实 验 结 果（一）城 市 链 表：（1）创建城市链表；（2）给定一个城市名，返回其位置坐标；（3）给定一个位置坐标P和一个距离D,返回所有与P的距离小于等于D的城市。（4）在已有的城市链表中插入一个新的城市；（5）更新城市信息；（6）删除某个城市信息。（二）约瑟夫环m 的初值为20;密码:3,1,7,2,6,8,4输出 6,1,4,7,2,3,5。五、附 录城 市 链 表：5.1 问题分析该实验规定对链表实现创建，遍历，插入，删除，查询等操作，故使用单链表。5.2 设计方案该程序大体分为以下几个模块：1.创建城市链表模块,即在空链表中插入新元素。故创建城市链表中包涵插入模块。

3、2.返回位置坐标模块。3.计算距离模块4.插入模块。5.更新城市信息模块6.删除信息模块。+void InitList_SqCity(city 1is t*L),.|+：void Insert_sqCity(city 1 is t*L).+void C reate_sqC ity(citylist*L).Svoid Get_sqCityCoord(citylist*L)|,|+void Get_sqCityName(citylist*L,double xl,double y l)|.;+void D elete_sqC ity(citylist*L)|.1I+void FindCityDist

4、ance(c ity list*L)+void Update_sqCity(city 1 is t*L)|._ 八 r5.3 算法5.3.1根据中心城市坐标,返回在距离内的所有城市：vo i d F in dCi t yDis t a nce(ci t y lis t*L)根据距离输出城市输入信息与距离L=L-next;o w h i 1 e(L!=NU LL)i f(L-x-x l)*(L-x-x 1)+(L-y-y 1)*(L-y y l)x-x l)+(L-y y 1)!=0 )o 3 P p in tf(城市名称snL-N a m e);。pr i n t f(城市坐标%.2 Ifn

5、u,L-x,L-y)；L=L-next;）该算法重要用到了勾股定理，考虑到不需要实际数值，只需要大小比较，所以只用横坐标差的平方+纵坐标差的平方 next=NULL；)void Insert_ sqCity(c i ty 1 is t*L)。/在链表中插入元素c ity l i st*ne wN o de：3 newNode=(c it y 1 i st*)mal 1 oc(si z eof(c it y li s t)；。i f (!newNode)叩rin t f(存储分派失败”)；-p rin tf(“请输入城市名n );scanf(%s,newNode-N am e);叩rin t f

6、C 请输城市坐标x y n );scanf(%1 f%l f&(n e wNod e-x),&(newNo d e-y);while(L n e x t!=NUL L)。L=L-ne x t；。假如非空，L指针的位置向后移 newN ode ne x t =L-next;L-n e x t=newNode;vo i d Create_sqCi t y(ci t y lis t*L)。创建链表 cha r ch lO 0;in t i;pr i nt f（输入END退出，输入其余值继续n”）；当输入END时，在任意输入，则退出此操作s c a n f(H%s,ch);f o r(；s tr c

7、mp(ch,END)!=0；)I n s e rt_s q C ity(L)；P r i n t f (输入 E ND退出，输入其余值继续n );scanf(%s,ch);)void Ge t _ sqC i t y Coo r d(c ity 1 is t*L)/输入城市信息返回坐标 ch a r c h 10;0 pr i n tf(输入要查询的城市”)；。scan f(%s，ch);aw hile(L-next!=NULL&s t rcm p(L-next-N am ech)L=L-n e x t;i f(L-n e x t=NULL)。p ri n t f (城市不存在“)；o e l

8、se p rin t f(%.2 If,%.2 1 f n,L-n ext x,L-next-y);)v o id D e le te_sqC ity(ci t y lis t*L)。删除城市信息，按名称/坐标P r i n tf(请输入城市名n ”)；。c h a r ch10;sc a nf(”%s ,c h)；。wh i le(L-nex t!=NULL&S t rcmp(L-n e x t-N a m e,c h)。L=L-next；i f(L-n e x t=NULL)-p r in t f(城 市不存在”)；删除位置不合理L-next=L-next-nex t;。pr i n tf

9、(删除城市成功”);)void F i n dC i tyD i sta nee(c ity l i st*L)根据距离输出城市p rirrtf(输入中心城市坐标);3dou b le x l,y 1；scanf(%l f%1 f,&x l,&y 1 )；P rin t长“输入距离)；0doiib 1 e d is;s c a n f(%lf,&d is );。L=L next;w h i 1 e(L!=NU L L)。i f(L-x-x 1)*(L x-x l)+(L y y l)*(L-y-y 1 )xx 1 )+(L-y-y l)!=0)。pr i n tf(城市名称s n，L-Nam

10、e);f p r i n t f(城 市坐标 .2 1 f,%.2 1 fn L-x,L-y);L=L next；)v o id Upd ate_sqC ity(c ity l i s t*L)/更新城市信息o c h a r ch 1 0;p r i n t f (请输入您要更新的城市名n“)；scanf(%s,ch);wh i le (strcm p(L n e xt-N a m e,c h)o L=L-n e x t;。i f (L-ne x t =NU L L)。叩 r in tf(“城市不存在n );o p rin t f(请输入城市新信息：n )；。p r in tf(”请输入城市

11、新名 n )；s canf(%s ,L-ne x t-Name);叩 r i n t f (请输入城市新坐标n”)；sea n f(%1 f%lf,&(L-n e x t-x)&(L-ne x t-y);)in t mai n()c ity l i s t*L;o L=(c ity lis t*)m alloc(size o f(c ity l i s t);In itL ist_ S q C ity(L);0 fo r(；)。p r in tf(-一-n )；。p r i n tf(请选择您的操作n“)；p r in t f(l创建城市链表n”)；。pr i n t f(“2.根据名字查询城

12、市 n”)；P r i n tf(3.插入n”)；。p r in tf(H4.删除n);op r i n t f (5.更新城市信息n“)；。p r in tf(6.根据离中心坐标距离查看城市n”)；s p r in tf(7.退出系统 n”)；pr i n tf(n-n);。i n t c h o ic e;o sc a n f(%d ,&ch o i c e)；s。s w itc h(choice)。case 1：。C r e ate_ s q C ity(L)；s g e tc h a r()；。break;ca s e 2：Ge t _ sqC i t yCoo r d(L);brea

13、 k;。case 3:。Insert_ sqCit y(L);。b reak；。c as e 4:o 。D e 1 ete_ s qCity(L);。b r e ak;。c a s e 5：。Up d a te_s q C ity(L)；o。b reak;case 6：。&F i n d Ci t y D istanc e(L)。b re a k；。c ase 7:b r ea k;。i f(cho i ce=7)。bre a k;)5.6仿真结果市城篥询襄查的电子你破名息坐信、D个统亶除选创主月L二n-1 2 3 4 5 6 7输入END退出，输入NEXT继续NEXT惮入城市名请输入城市坐标

14、x y1 1输入END退出.输入NEST继续NEXT旗入城市名请输入城市坐标x y2 2输入END退出，输入NEST继续END5更新城市熊入您要更新的城市名请加入城市新值息:请魏入赧币新老济南 一请输入城市新坐标2 2更新城市信息成功6 根据距离输出城市余人中心城市坐标1 1但心城市为北京愉入距高京市名掷舁南城市坐标2.2.0。5.7 调试心得5.7.1 错误分析：实验中出现的第一个问题是声明变量，从键盘中读入数据是显示变量未初始化，调试后发现是scanf的问题，以后的实验中应注意scan f 中读入信息后是存到了地址里。5.7.2 算法复杂度的分析：所有程序 除了InitLi s t _Sq

15、City复杂度为O(1),其余均为0(n).5.7.3 收获对数据结构这门课地应用有了一定地了解，知道对线性表插入、删除等操作的实现，加深对课本地理解。附录约瑟夫环:5.1 问题分析该实验规定循环连续查找信息，并删除节点，故使用单项循环链表。5.2 设计方案1.建立单循环链表2.产生Jose ph环3.输出顺序表5.3算法5.3.1构成单链表void Creat_3 o e p h L ink(int n u m)Node*h ea d,*q,*L;L=(Node*)malloc(sizeo f(Nod e);申请第一个数的节点head二L;L-num=l;p r in t f(输 入 第 一

16、 个 人 的 值 输 入 第一个人的值scanf(%d,&(L-value);i nt i;f o r(i=2;i n e xt=q；L=q；prin t f(输入第d个人的值：,i)；输入每个人的值scanf(%d“，&(L-value);L-n um=i;)L-n e x t=head;L=hea d;/构成单向循环链表)5.3.2查找并删除节点S t a tus Delet e _Node(N o d e*L)fo r(j=l；j V=num;j+)fo r(i=l：inext;)m=L v a lu e /将当前值设为m值pr i n t f(%d，Lnum);/输出当前节点信息/删除

17、当前节点L-num=L-next num;L-valu e=L-n e xt-val u e;q=L ne x t;L-n e xt=L nex t-ne x t;f r ee(q)；)5.4源程序代码t ypedef s tr u c t N o dei n t value;N o d e *nex t;in t num；No d e;voi d C r e a t _3oeph L in k(i n t num)Node*hea d,*q,*L;L=(Node*)ma 1 loc(sizeof(Node)；/申请第一个数的节点he a d=L；L-num=l；p rin t f(“输入第一

18、个人的值：”)；输入第一个人的值scanf(%d ,&(L-value)；in t i;fo r(i=2;i next=q;L=q；p r in tf(输入第1个人的值：，i);/输入每个人的值scanf(%d ,&(L-v a lu e );L n um=i;)L-ne x t=head;L=h e a d；构成单向循环链表in t m;in t j;p r in t f(输入初始值m的大小”)；s can f(%d，&m);p r in t f(结果是：n );fo r(j=1 ；j=num;j+)f o r(i=1 ;i n ext;)m=L-valu e;将当前值设为m值pr i n

19、t f (n%d，L-n u m);/输出当前节点信息删除当前节点L-num=L-ne x t-num；L-value=L-nex t va 1 u e;q=L-n e x t;L nex t=L-n e xt-n e x t；fre e(q);)in t mai n()in t num;prin t f（输入人数：）；/*输入测试人的数量*/scanf(%d,&num);Cre a t _ J oep h Link(n u m);)5.5 运营结果n第第第第第第第.目正人入入入入入入入IA果i傕/癌食=-&:大7绘人人；一%ATTTXlTn费-2345671D:bu ptssecd saI la b0102Debuc:31726840247235.6 调试心得5.6.1错误分析查找到第m 个节点删除时犯错，显示有未解决的异常，是由于节点赋值的时候有问题。5.6.2 收获从开始构建循环链表然后实现约瑟夫环功能的过程中，半途也碰见一些问题，但都逐个克服，整个过程进展不是很顺利，都是不断的调试，实验之后，我还对数据结构这门课有了一定的结识。在解决个具体问题时，经常需要从具体问题中抽象出一个模型，也就是抽象数据类型，然后设计一个解决这个模型的算法。再通过其算法编出程序，进行调试、调整直至得到最终解答。