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

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

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

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

4、creatLink() /創(chuàng)立一個城市鏈表，返回頭結(jié)點地址printList(Linklist L)/ 打印頭結(jié)點地址為L的城市鏈表 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)/給定一個城市名,返回城市坐標(biāo) int getCity(Linklist L,int p*,int py,int d)/給定一個城市坐標(biāo)P,返回距離小于等于d的城市void main()/主函數(shù)，實現(xiàn)鏈表各項操作的選擇3函數(shù)主要調(diào)用關(guān)系圖本系統(tǒng)3個子程序之間的主要調(diào)用關(guān)系如下圖。128967543102222211main4、詳細(xì)設(shè)計數(shù)據(jù)類型定義typedef struct LNode/城市結(jié)點char name20;int pos*;/橫坐標(biāo)int posy;/縱坐標(biāo)s

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

7、橫坐標(biāo)*: );scanf(%d,&p*);printf(請輸入縱坐標(biāo)y：);scanf(%d,&py);p=(Linklist)malloc(LEN); /新結(jié)點strcpy(p-name,name);p-pos*=p*;p-posy=py;insert(L,p); /插入新結(jié)點printf(請輸入城市名稱：);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é)點之后 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、測試分析實驗中遇到的問題以及對設(shè)計與實現(xiàn)的回憶討論和分析城市鏈表在開場的建立時，由于頭結(jié)點指針的判斷錯誤，導(dǎo)致鏈表頭結(jié)點中存有信息，而在后面的插入和刪除操

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

11、時空分析算法使用動態(tài)分配空間的方式執(zhí)行，故其執(zhí)行時間與鏈表記錄個數(shù)有關(guān)，如果有n個城市結(jié)點，其時間復(fù)雜度為On。經(jīng)歷和體會通過本次實驗，對于鏈表局部的相關(guān)功能，如插入、刪除、排序等相關(guān)算法進(jìn)一步熟悉了。能夠利用所學(xué)知識，解決相關(guān)問題，并能夠正確解決實驗過程中出現(xiàn)的過失。測試功能展示城市鏈表的建立在主菜單下，用戶輸入1并回車，然后按照提示建立城市鏈表，運行結(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é)點int insert(Linklist L,Linklist city);Linklist creatLink() /創(chuàng)立一個城市鏈表，返回頭結(jié)點地址Linklist L=(Linklist)malloc(LEN); /頭結(jié)點L-ne*t=NULL;Linklist p;char name20;int p*;int py;char end4=end;printf(請輸入城市名稱、橫坐標(biāo)和縱坐標(biāo)，建

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

14、結(jié)點地址為L的城市鏈表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é)點之后 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(請輸入橫坐標(biāo)*

20、: );scanf(%d,&p-pos*);printf(請輸入縱坐標(biāo)y: );scanf(%d,&p-posy);p=p-ne*t;return flag;int getPos(Linklist L,char name20)/給定一個城市名,返回城市坐標(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)/給定一個城市坐標(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(請選擇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(請輸入城市名稱：);scanf(%s,name);printf(請輸入橫坐標(biāo)*: );scanf(%d,&p*);printf(請輸入縱坐標(biāo)y: );sc

24、anf(%d,&py);Linklist p=(Linklist)malloc(LEN); /新結(jié)點strcpy(p-name,name);p-pos*=p*;p-posy=py;insert(L,p); /有序的插入新結(jié)點printf(插入后的城市鏈表為：);printList(L);else printf(nERROR: 鏈表還沒有建立，請先建立鏈表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請輸入城市名:);scanf(%s,name);flag=searchName(L,name);if(flag=0) printf(無此城市記錄，查找失敗！n);else if(way=2)printf(請輸入橫坐標(biāo)*: );scanf(%d,&p*);printf(請輸入縱坐標(biāo)y: );scanf(%d,&py);flag=searchPos(L,p*,py);if(flag=0) printf(無此城市記錄，查找失??！n);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(請輸入城市名稱: );scanf(%s,name);flag=delName(L,name);if(flag)printf(刪除%s城市后：n,name);printList(L);else printf(無該名字的城市，刪除失敗!n);else if(way=2)printf(請輸入橫坐標(biāo)*: );scanf(%d,&p*);printf(請輸入縱坐標(biāo)y: );scanf(%d,&py);flag=delPos(L,p*,py);if(fl