數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告實(shí)驗(yàn)1城市鏈表

1、-. z數(shù)據(jù)構(gòu)造課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)一 鏈表局部選題為：城市鏈表需求分析創(chuàng)立一個(gè)帶有頭結(jié)點(diǎn)的單鏈表。結(jié)點(diǎn)中應(yīng)包含城市名和城市的位置坐標(biāo)。對(duì)城市鏈表能夠利用城市名和位置坐標(biāo)進(jìn)展有關(guān)查找、插入、刪除、更新等操作。能夠?qū)γ看尾僮骱蟮逆湵韯?dòng)態(tài)顯示。概要設(shè)計(jì)為了實(shí)現(xiàn)以上功能，可以從以下3個(gè)方面著手設(shè)計(jì)。主界面設(shè)計(jì)為了實(shí)現(xiàn)城市鏈表相關(guān)操作功能的管理，設(shè)計(jì)一個(gè)含有多個(gè)菜單項(xiàng)的主控菜單子程序以系統(tǒng)的各項(xiàng)子功能，方便用戶使用本程序。本系統(tǒng)主控菜單運(yùn)行界面如下所示。存儲(chǔ)構(gòu)造設(shè)計(jì)本系統(tǒng)主要采用鏈表構(gòu)造類型來表示存儲(chǔ)在城市鏈表中的信息。其中鏈表結(jié)點(diǎn)由4個(gè)分量組成：城市名name、城市的橫坐標(biāo)pos*、城市的縱坐標(biāo)po

2、sy、指向下一個(gè)結(jié)點(diǎn)的指針ne*t。系統(tǒng)功能設(shè)計(jì)本程序設(shè)計(jì)了9個(gè)功能子菜單，其描述如下：建立城市鏈表。由函數(shù)creatLink()實(shí)現(xiàn)。該功能實(shí)現(xiàn)城市結(jié)點(diǎn)的輸入以及連接。插入鏈表記錄。由函數(shù)insert()實(shí)現(xiàn)。該功能實(shí)現(xiàn)按坐標(biāo)由小到大的順序?qū)⒔Y(jié)點(diǎn)插入到鏈表中。查詢鏈表記錄。由searchName函數(shù)和searchPos函數(shù)實(shí)現(xiàn)。其中searchName實(shí)現(xiàn)按照城市名查詢的操作，searchPos實(shí)現(xiàn)按照城市坐標(biāo)查詢的操作。刪除鏈表記錄。由delName函數(shù)和delPos函數(shù)實(shí)現(xiàn)。其中delName函數(shù)實(shí)現(xiàn)按照城市名刪除的操作，delPos函數(shù)實(shí)現(xiàn)按照城市坐標(biāo)刪除的操作。顯示鏈表記錄。由pri

3、ntList函數(shù)實(shí)現(xiàn)。該功能實(shí)現(xiàn)格式化的鏈表輸出操作，可以顯示修改后的鏈表狀態(tài)。更新鏈表信息。由update函數(shù)實(shí)現(xiàn)。該功能實(shí)現(xiàn)按照城市名更新城市的坐標(biāo)信息。返回城市坐標(biāo)。由getPos函數(shù)實(shí)現(xiàn)。該功能實(shí)現(xiàn)給定一個(gè)已存儲(chǔ)的城市，返回其坐標(biāo)信息的操作。查看與坐標(biāo)P距離小于等于D的城市。由getCity函數(shù)實(shí)現(xiàn)。該功能實(shí)現(xiàn)返回與給定坐標(biāo)P距離小于等于D的城市名稱。退出鏈表系統(tǒng)。由e*it0實(shí)現(xiàn)。模塊設(shè)計(jì)1模塊設(shè)計(jì)本程序包含兩個(gè)模塊：主程序模塊和鏈表操作模塊。其調(diào)用關(guān)系如下列圖所示：主程序模塊鏈表操作模塊2系統(tǒng)子程序及功能設(shè)計(jì)本系統(tǒng)共設(shè)置3個(gè)子程序，各程序的函數(shù)名及功能說明如下： Linklist

4、creatLink() /創(chuàng)立一個(gè)城市鏈表，返回頭結(jié)點(diǎn)地址printList(Linklist L)/ 打印頭結(jié)點(diǎn)地址為L(zhǎng)的城市鏈表 int searchName(Linklist L,char name20)/以城市名查找 int searchPos(Linklist L,int p*,int py)/以城市坐標(biāo)查找 int insert(Linklist L,Linklist city)/插入 int delName(Linklist L,char name20)/利用城市名稱刪除 int delPos(Linklist L,int p*,int py)/利用坐標(biāo)刪除 int update

5、(Linklist L,char name20)/更新 int getPos(Linklist L,char name20)/給定一個(gè)城市名,返回城市坐標(biāo) int getCity(Linklist L,int p*,int py,int d)/給定一個(gè)城市坐標(biāo)P,返回距離小于等于d的城市void main()/主函數(shù)，實(shí)現(xiàn)鏈表各項(xiàng)操作的選擇3函數(shù)主要調(diào)用關(guān)系圖本系統(tǒng)3個(gè)子程序之間的主要調(diào)用關(guān)系如下圖。128967543102222211main4、詳細(xì)設(shè)計(jì)數(shù)據(jù)類型定義typedef struct LNode/城市結(jié)點(diǎn)char name20;int pos*;/橫坐標(biāo)int posy;/縱坐標(biāo)s

6、truct LNode *ne*t;LNode,*Linklist;2系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)建立城市鏈表Linklist creatLink() /創(chuàng)立一個(gè)城市鏈表，返回頭結(jié)點(diǎn)地址Linklist L=(Linklist)malloc(LEN); /頭結(jié)點(diǎn)L-ne*t=NULL;Linklist p;char name20;int p*;int py;char end4=end;printf(請(qǐng)輸入城市名稱、橫坐標(biāo)和縱坐標(biāo)，建立城市鏈表，以end為輸入完畢標(biāo)志n);printf(請(qǐng)輸入城市名稱：);scanf(%s,name);while (strcmp(name,end)printf(請(qǐng)輸入

7、橫坐標(biāo)*: );scanf(%d,&p*);printf(請(qǐng)輸入縱坐標(biāo)y：);scanf(%d,&py);p=(Linklist)malloc(LEN); /新結(jié)點(diǎn)strcpy(p-name,name);p-pos*=p*;p-posy=py;insert(L,p); /插入新結(jié)點(diǎn)printf(請(qǐng)輸入城市名稱：);scanf(%s,name);return(L);插入鏈表記錄int insert(Linklist L,Linklist city)/插入Linklist p=L-ne*t;Linklist p_prior=L;while(p!=NULL & city-pos*=p-pos*)if

8、(p-pos*=city-pos* & p-posy=city-posy)printf(重復(fù)輸入！n);return 0;p=p-ne*t; /確定city插入的位置while(p_prior-ne*t!=p)p_prior=p_prior-ne*t;if(p=NULL) p=p_prior;city-ne*t=NULL;p-ne*t=city; else /假設(shè)為空表，插到頭結(jié)點(diǎn)之后 p=p_prior;city-ne*t=p-ne*t; p-ne*t=city; return 1;按名稱刪除鏈表記錄int delName(Linklist L,char name20)/利用城市名稱刪除in

9、t flag=0;int seat=1;Linklist p=L;if(p-ne*t=NULL)printf(該鏈表中沒有元素,刪除失敗n);else while(p-ne*t!=NULL) if(!strcmp(p-ne*t-name,name)flag=1;printf(城市 %s 被刪除n,name);Linklist q=p-ne*t;p-ne*t=q-ne*t;free(q);else p=p-ne*t;return flag;5、測(cè)試分析實(shí)驗(yàn)中遇到的問題以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回憶討論和分析城市鏈表在開場(chǎng)的建立時(shí)，由于頭結(jié)點(diǎn)指針的判斷錯(cuò)誤，導(dǎo)致鏈表頭結(jié)點(diǎn)中存有信息，而在后面的插入和刪除操

10、作中并未考慮到，導(dǎo)致鏈表記錄出錯(cuò)，指針錯(cuò)位。在鏈表的刪除過程中，由于刪除的時(shí)判斷的結(jié)點(diǎn)，故應(yīng)找到起前驅(qū)指針，一開場(chǎng)并未考慮到這些，在無法刪除的時(shí)候才想起來改良方法，后來設(shè)置了一個(gè)prior指針，專門找到對(duì)應(yīng)結(jié)點(diǎn)的前驅(qū)，方便刪除操作。課題拓展訓(xùn)練為為城市參加其他信息，如人口數(shù)等。考慮到此項(xiàng)添加僅是在數(shù)據(jù)定義中再參加一個(gè)數(shù)據(jù)項(xiàng)，為了方便實(shí)驗(yàn)進(jìn)展與演示，就沒有進(jìn)展擴(kuò)展。如需實(shí)現(xiàn)，可在Lnode的定義中，參加int num等語(yǔ)句。鏈表建立初期，個(gè)人的想法是按照新增結(jié)點(diǎn)插入按順序插入到鏈表中，刪除時(shí)可以按照城市名稱和城市坐標(biāo)進(jìn)展刪除。在具體的實(shí)現(xiàn)過程中，使用了菜單項(xiàng)選擇擇的方法，方便用戶使用系統(tǒng)。算法的

11、時(shí)空分析算法使用動(dòng)態(tài)分配空間的方式執(zhí)行，故其執(zhí)行時(shí)間與鏈表記錄個(gè)數(shù)有關(guān)，如果有n個(gè)城市結(jié)點(diǎn)，其時(shí)間復(fù)雜度為On。經(jīng)歷和體會(huì)通過本次實(shí)驗(yàn)，對(duì)于鏈表局部的相關(guān)功能，如插入、刪除、排序等相關(guān)算法進(jìn)一步熟悉了。能夠利用所學(xué)知識(shí)，解決相關(guān)問題，并能夠正確解決實(shí)驗(yàn)過程中出現(xiàn)的過失。測(cè)試功能展示城市鏈表的建立在主菜單下，用戶輸入1并回車，然后按照提示建立城市鏈表，運(yùn)行結(jié)果如下所示：插入鏈表記錄查詢鏈表記錄：刪除鏈表記錄顯示鏈表記錄更新鏈表信息返回城市坐標(biāo)查看與坐標(biāo)P距離小于等于D的城市源程序清單#include#include#include#include#define LEN sizeof(LNode)

12、typedef struct LNodechar name20;int pos*;/橫坐標(biāo)int posy;/縱坐標(biāo)struct LNode *ne*t;LNode,*Linklist;/用于城市結(jié)點(diǎn)int insert(Linklist L,Linklist city);Linklist creatLink() /創(chuàng)立一個(gè)城市鏈表，返回頭結(jié)點(diǎn)地址Linklist L=(Linklist)malloc(LEN); /頭結(jié)點(diǎn)L-ne*t=NULL;Linklist p;char name20;int p*;int py;char end4=end;printf(請(qǐng)輸入城市名稱、橫坐標(biāo)和縱坐標(biāo)，建

13、立城市鏈表，以end為輸入完畢標(biāo)志n);printf(請(qǐng)輸入城市名稱：);scanf(%s,name);while (strcmp(name,end)printf(請(qǐng)輸入橫坐標(biāo)*: );scanf(%d,&p*);printf(請(qǐng)輸入縱坐標(biāo)y：);scanf(%d,&py);p=(Linklist)malloc(LEN); /新結(jié)點(diǎn)strcpy(p-name,name);p-pos*=p*;p-posy=py;insert(L,p); /插入新結(jié)點(diǎn)printf(請(qǐng)輸入城市名稱：);scanf(%s,name);return(L);void printList(Linklist L) / 打印頭

14、結(jié)點(diǎn)地址為L(zhǎng)的城市鏈表printf(n-n);printf(城市t坐標(biāo)n);printf(-n);Linklist p=L-ne*t;int n=1;if(L-ne*t=NULL) printf(該鏈表中沒有元素n);else while(p!=NULL)printf(%s,p-name);printf(t(%d,%d)n,p-pos*,p-posy);p=p-ne*t;printf(-n);return ;int searchName(Linklist L,char name20)/以城市名查找int flag=0;Linklist p=L-ne*t;if(L-ne*t=NULL)print

15、f(該鏈表中沒有元素,查找失敗n);elsewhile(p!=NULL)if(!strcmp(p-name,name)flag=1;printf(您要查找的是 %s 城市n,p-name);printf(該城市坐標(biāo)為 (%d,%d) n,p-pos*,p-posy);p=p-ne*t;return flag;int searchPos(Linklist L,int p*,int py)/以城市坐標(biāo)查找int flag=0;Linklist p=L-ne*t;if(L-ne*t=NULL)printf(該鏈表中沒有元素,查找失敗n);elsewhile(p!=NULL)if(p-pos*=p*&

16、p-posy=py)flag=1;printf(您要查找城市坐標(biāo)為 (%d,%d) n,p-pos*,p-posy);printf(該城市是 %sn,p-name);p=p-ne*t;return flag;int insert(Linklist L,Linklist city)/插入Linklist p=L-ne*t;Linklist p_prior=L;while(p!=NULL & city-pos*=p-pos*)if(p-pos*=city-pos* & p-posy=city-posy)printf(重復(fù)輸入！n);return 0;p=p-ne*t; /確定city插入的位置wh

17、ile(p_prior-ne*t!=p)p_prior=p_prior-ne*t;if(p=NULL) p=p_prior;city-ne*t=NULL;p-ne*t=city; else /假設(shè)為空表，插到頭結(jié)點(diǎn)之后 p=p_prior;city-ne*t=p-ne*t; p-ne*t=city; return 1;int delName(Linklist L,char name20)/利用城市名稱刪除int flag=0;int seat=1;Linklist p=L;if(p-ne*t=NULL)printf(該鏈表中沒有元素,刪除失敗n);else while(p-ne*t!=NULL

18、) if(!strcmp(p-ne*t-name,name)flag=1;printf(城市 %s 被刪除n,name);Linklist q=p-ne*t;p-ne*t=q-ne*t;free(q);else p=p-ne*t;return flag;int delPos(Linklist L,int p*,int py)/利用坐標(biāo)刪除int flag=0;Linklist p=L;if(p-ne*t=NULL)printf(該鏈表中沒有元素,刪除失敗n);else while(p-ne*t !=NULL) if(p-ne*t-pos*=p*&p-ne*t-posy=py)Linklist

19、q=p-ne*t;p-ne*t=q-ne*t;free(q);flag=1;printf(坐標(biāo)為 (%d,%d) 的城市被刪除n,p*,py);else p=p-ne*t;return flag;int update(Linklist L,char name20)/更新int flag=0;Linklist p=L-ne*t;if(L-ne*t=NULL|L=NULL)printf(該鏈表中沒有元素,更新失敗n);elsewhile(p!=NULL)if(!strcmp(p-name,name)flag=1;printf(您要更新的是 %s 城市n,p-name);printf(請(qǐng)輸入橫坐標(biāo)*

20、: );scanf(%d,&p-pos*);printf(請(qǐng)輸入縱坐標(biāo)y: );scanf(%d,&p-posy);p=p-ne*t;return flag;int getPos(Linklist L,char name20)/給定一個(gè)城市名,返回城市坐標(biāo)int flag=0;Linklist p=L-ne*t;if(L-ne*t=NULL|L=NULL)printf(該鏈表中沒有元素,返回坐標(biāo)失敗n);elsewhile(p!=NULL)if(!strcmp(p-name,name)flag=1;printf(您要查看的是 %s 城市n,p-name);printf(該城市坐標(biāo)為:(%d,%

21、d) n,p-pos*,p-posy);p=p-ne*t;return flag;int getCity(Linklist L,int p*,int py,int d)/給定一個(gè)城市坐標(biāo)P,返回距離小于等于d的城市int flag=0;double distance;Linklist p=L-ne*t;if(L-ne*t=NULL|L=NULL)printf(該鏈表中沒有元素,返回坐標(biāo)失敗n);elsewhile(p!=NULL)distance=sqrt(p-pos*-p*)2+(p-posy-py)2);if(distancename);p=p-ne*t;printf(n);return

22、flag;void main()Linklist L=NULL;printf(n * 歡送使用城市鏈表系統(tǒng)*n);printf( * 1 建立城市鏈表 *n); printf( * 2 插入鏈表記錄 *n);printf( * 3 查詢鏈表記錄 *n);printf( * 4 刪除鏈表記錄 *n);printf( * 5 顯示鏈表記錄 *n);printf( * 6 更新鏈表信息 *n);printf( * 7 返回城市坐標(biāo) *n);printf( * 8 查看與坐標(biāo)P距離小于等于D的城市 *n);printf( * 9 退出鏈表系統(tǒng) *n); printf( * 歡送使用城市鏈表系統(tǒng)*n);

23、int main_flag=0;int flag;int menu;printf(請(qǐng)選擇1-9：);scanf(%d,&menu);while(menu)switch(menu)case 1:/建立城市鏈表 L=creatLink();printf(建立城市鏈表：);printList(L);main_flag=1;break;case 2:/插入鏈表記錄if(main_flag=1)char name20;int p*,py;printf(請(qǐng)輸入城市名稱：);scanf(%s,name);printf(請(qǐng)輸入橫坐標(biāo)*: );scanf(%d,&p*);printf(請(qǐng)輸入縱坐標(biāo)y: );sc

24、anf(%d,&py);Linklist p=(Linklist)malloc(LEN); /新結(jié)點(diǎn)strcpy(p-name,name);p-pos*=p*;p-posy=py;insert(L,p); /有序的插入新結(jié)點(diǎn)printf(插入后的城市鏈表為：);printList(L);else printf(nERROR: 鏈表還沒有建立，請(qǐng)先建立鏈表n);break;case 3:/查詢鏈表記錄 int way;char name20;int p*,py;if(L!=NULL)if(main_flag)printf( 選擇查找方式： 1.按城市名 2.按城市坐標(biāo) t選擇: );scanf(

25、%d,&way);if(way=1)printf(n請(qǐng)輸入城市名:);scanf(%s,name);flag=searchName(L,name);if(flag=0) printf(無此城市記錄，查找失敗！n);else if(way=2)printf(請(qǐng)輸入橫坐標(biāo)*: );scanf(%d,&p*);printf(請(qǐng)輸入縱坐標(biāo)y: );scanf(%d,&py);flag=searchPos(L,p*,py);if(flag=0) printf(無此城市記錄，查找失?。);else printf(城市鏈表中無記錄！n);break;else printf(鏈表中無記錄！n);break;

26、case 4:/刪除鏈表記錄int way;char name20;int p*,py;printf(選擇刪除方式：1.按城市名稱 2. 按城市坐標(biāo) t選擇: );scanf(%d,&way);if(way=1)printf(請(qǐng)輸入城市名稱: );scanf(%s,name);flag=delName(L,name);if(flag)printf(刪除%s城市后：n,name);printList(L);else printf(無該名字的城市，刪除失敗!n);else if(way=2)printf(請(qǐng)輸入橫坐標(biāo)*: );scanf(%d,&p*);printf(請(qǐng)輸入縱坐標(biāo)y: );scanf(%d,&py);flag=delPos(L,p*,py);if(fl