城市鏈表實(shí)驗(yàn)報(bào)告

1、2014-2015學(xué)年第一學(xué)期實(shí)驗(yàn)報(bào)告課程名稱： 算法與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)名稱: 城市鏈表 一、 實(shí)驗(yàn)?zāi)康?本次實(shí)驗(yàn)的主要目的在于熟悉線性表的基本運(yùn)算在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，其中以熟悉 各種鏈表的操作為側(cè)重點(diǎn)。同時(shí)，通過本次實(shí)驗(yàn)幫助學(xué)生復(fù)習(xí)高級(jí)語言的使用方法.二、 實(shí)驗(yàn)內(nèi)容 （一）城市鏈表 ： 將若干城市的信息，存入一個(gè)帶頭結(jié)點(diǎn)的單鏈表.結(jié)點(diǎn)中的城市信息包括：城市名，城 市的位置坐標(biāo)。要求能夠利用城市名和位置坐標(biāo)進(jìn)行有關(guān)查找、插入、刪除、更新等操作。(二） 約瑟夫環(huán)m 的初值為 20；密碼：3，1，7，2,6，8，4（正確的結(jié)果應(yīng)為 6，1,4,7，2，3,5).三、 實(shí)驗(yàn)環(huán)境 VS2010 、w

2、in8。1四、 實(shí)驗(yàn)結(jié)果（一）城市鏈表：（1） 創(chuàng)建城市鏈表； (2) 給定一個(gè)城市名，返回其位置坐標(biāo)； (3） 給定一個(gè)位置坐標(biāo) P 和一個(gè)距離 D，返回所有與 P 的距離小于等于 D 的城市。 （4） 在已有的城市鏈表中插入一個(gè)新的城市; （5） 更新城市信息; （6） 刪除某個(gè)城市信息.（二） 約瑟夫環(huán)m 的初值為 20;密碼:3，1，7,2,6,8，4輸出 6，1,4，7，2，3,5。五、 附錄城市鏈表：5.1 問題分析該實(shí)驗(yàn)要求對(duì)鏈表實(shí)現(xiàn)創(chuàng)建，遍歷,插入,刪除，查詢等操作,故使用單鏈表。5。2 設(shè)計(jì)方案該程序大致分為以下幾個(gè)模塊:1.創(chuàng)建城市鏈表模塊，即在空鏈表中插入新元素.故創(chuàng)建城

3、市鏈表中包涵插入模塊。2.返回位置坐標(biāo)模塊。3.計(jì)算距離模塊4。插入模塊。5。更新城市信息模塊6。刪除信息模塊.5。3 算法5.3。1 根據(jù)中心城市坐標(biāo),返回在距離內(nèi)的所有城市:void FindCityDistance（citylist L)/根據(jù)距離輸出城市/輸入信息與距離L=L->next；while（L != NULL）if（L>x-x1)*(L>xx1）+(L->yy1)（Lyy1）=disdis)&&（(（L-xx1）+（L>yy1）！=0 )printf（”城市名稱sn",L-Name)；printf("城市坐標(biāo)。

4、2lf,。2lfn"，Lx，L-y）；L=L>next; 該算法主要用到了勾股定理,考慮到不需要實(shí)際數(shù)值，只需要大小比較，所以只用橫坐標(biāo)差的平方+縱坐標(biāo)差的平方 <= 距離的平方 判定. 因中心城市本身也在判定范圍之內(nèi)，所以添加了判定條件橫縱坐標(biāo)差的和不能為零。5。3。2主程序中循環(huán)條件判定：for( ； ； ）printf（"請(qǐng)選擇您的操作n”)；printf（”1。創(chuàng)建城市鏈表n”）；printf("2.根據(jù)名字查詢城市n”）;printf（”3.插入n"）；printf(”4.刪除n”）;printf(”5。更新城市信息n”）;prin

5、tf（"6。根據(jù)離中心坐標(biāo)距離查看城市n”）;printf("7。退出系統(tǒng)n”);scanf（”%d"，choice）；switch（choice)/case語句case 7：break;if(choice = 7)break；若用戶選擇了退出系統(tǒng)選項(xiàng),則首先跳出switch 在跳出for循環(huán)結(jié)束程序。否結(jié)束是是否退出退出插入刪除更新距離5.4流程圖查詢創(chuàng)建開始選擇操作5.5程序源代碼typedefstruct citylist char Name20；double x，y; citylist next；citylist， L；void InitList_SqCi

6、ty(citylist L)/初始化節(jié)點(diǎn) Lnext = NULL；void Insert_sqCity（citylist L）/在鏈表中插入元素citylist newNode；newNode=（citylist*）malloc（sizeof（citylist);if（!newNode）printf（”存儲(chǔ)分配失敗”）；printf("請(qǐng)輸入城市名n”)；scanf(”s”，newNodeName)；printf(”請(qǐng)輸城市坐標(biāo)x yn”)；scanf（”%lflf”，&（newNodex），&（newNode>y）;while（L>next ！= NU

7、LL) L = L>next; /如果非空，L指針的位置向后移 newNodenext =Lnext； L-next = newNode；void Create_sqCity（citylist L)/創(chuàng)建鏈表char ch100；int i；printf（"輸入END退出，輸入其余值繼續(xù)n"）； /當(dāng)輸入END時(shí),在任意輸入，則退出此操作scanf(”s”,ch）;for(；strcmp（ch，”END”)！=0 ; ）Insert_sqCity(L）； printf（”輸入END退出，輸入其余值繼續(xù)n"）; scanf(”s”,ch)；void Get_s

8、qCityCoord（citylist *L)/輸入城市信息返回坐標(biāo)char ch10；printf（”輸入要查詢的城市"）；scanf（”%s"，ch)；while（Lnext！= NULL &strcmp（L-nextName,ch)L=Lnext；if（L>next = NULL）printf（”城市不存在”）；elseprintf（"。2lf，.2lfn",L-next>x,L-nexty）；void Delete_sqCity（citylist L）/刪除城市信息 ，按名稱/坐標(biāo)printf（”請(qǐng)輸入城市名n"）；

9、char ch10；scanf("%s”，ch）;while（Lnext != NULL&strcmp（Lnext>Name,ch）L=Lnext;if（L>next = NULL）printf（”城市不存在”）;/刪除位置不合理Lnext=L>nextnext； printf（”刪除城市成功”）;void FindCityDistance（citylist *L）/根據(jù)距離輸出城市printf（”輸入中心城市坐標(biāo)”)；double x1，y1；scanf(”%lflf"，x1，&y1）；printf（”輸入距離"）;double

10、 dis；scanf（"%lf"，&dis)；L=L-next;while(L != NULL）if（Lx-x1)*（Lxx1）+（Lyy1)（Lyy1)=disdis）&（(Lxx1）+(L->yy1）)！=0 ）printf（”城市名稱%sn”,LName）；printf（”城市坐標(biāo)%。2lf,。2lfn",Lx，Ly);L=Lnext;void Update_sqCity（citylist* L)/更新城市信息char ch10；printf（"請(qǐng)輸入您要更新的城市名n"）；scanf(”s”，ch)； while(

11、strcmp（L>nextName，ch）L=L-next；if(L-next = NULL)printf(”城市不存在n”）；printf(”請(qǐng)輸入城市新信息：n”); printf（”請(qǐng)輸入城市新名n")； scanf（"s”,L-nextName）； printf("請(qǐng)輸入城市新坐標(biāo)n"）； scanf（"lf%lf”，&(Lnextx），（Lnext>y）; int main（）citylist L；L=（citylist)malloc（sizeof（citylist)；InitList_SqCity（L）;for（

12、 ； ； )printf("-n”）;printf（”請(qǐng)選擇您的操作n”）;printf（"1。創(chuàng)建城市鏈表n"）;printf("2.根據(jù)名字查詢城市n”)；printf("3。插入n”）;printf(”4。刪除n"）；printf("5.更新城市信息n")；printf（"6。根據(jù)離中心坐標(biāo)距離查看城市n”）;printf（"7.退出系統(tǒng)n”）；printf("-n”）；int choice；scanf（”%d”，choice）；switch（choice)case 1：Crea

13、te_sqCity（L)；getchar(）；break;case 2：Get_sqCityCoord（L）;break；case 3：Insert_sqCity（L);break；case 4：Delete_sqCity（L）;break;case 5：Update_sqCity(L)；break;case 6： FindCityDistance(L)；break;case 7：break；if(choice = 7)break； 5。6仿真結(jié)果2。查詢城市信息3 添加城市4 刪除城市5 更新城市6 根據(jù)距離輸出城市5。7 調(diào)試心得5.7.1錯(cuò)誤分析：實(shí)驗(yàn)中出現(xiàn)的第一個(gè)問題是聲明變量,從鍵盤

14、中讀入數(shù)據(jù)是顯示變量未初始化，調(diào)試后發(fā)現(xiàn)是scanf的問題，以后的實(shí)驗(yàn)中應(yīng)注意scanf中讀入信息后是存到了地址里。5.7。2 算法復(fù)雜度的分析: 所有程序 除了InitList_SqCity 復(fù)雜度為O（1）,其余均為O（n）。5.7。3 收獲對(duì)數(shù)據(jù)結(jié)構(gòu)這門課地應(yīng)用有了一定地了解,知道對(duì)線性表插入、刪除等操作的實(shí)現(xiàn)，加深對(duì)課本地理解。附錄約瑟夫環(huán)：5.1問題分析該實(shí)驗(yàn)要求循環(huán)連續(xù)查找信息,并刪除節(jié)點(diǎn)，故使用單項(xiàng)循環(huán)鏈表.5。2設(shè)計(jì)方案1。建立單循環(huán)鏈表 2。產(chǎn)生Joseph環(huán)3。輸出順序表5。3算法5.3。1 構(gòu)成單鏈表void Creat_JoephLink(int num)Node he

15、ad，q，L；L=（Node*）malloc（sizeof(Node）；/申請(qǐng)第一個(gè)數(shù)的節(jié)點(diǎn)head=L；L-num=1；printf（”輸入第一個(gè)人的值：”）； /輸入第一個(gè)人的值 scanf（”d"，(Lvalue）；int i；for（i=2;i=num；i+)q=(Node）malloc（sizeof（Node)）；Lnext=q；L=q；printf（”輸入第d個(gè)人的值："，i）; /輸入每個(gè)人的值scanf（”d",（L-value）;Lnum=i；L>next=head; L=head;/構(gòu)成單向循環(huán)鏈表5。3。2查找并刪除節(jié)點(diǎn)Status D

16、elete_Node（Node L）for (j=1;j=num；j+）for（i=1;i<m；i+)/i做循環(huán)變量L=Lnext；m=Lvalue;/將當(dāng)前值設(shè)為m值printf（”%d ”，L->num)；/輸出當(dāng)前節(jié)點(diǎn)信息/刪除當(dāng)前節(jié)點(diǎn)L-num=L-nextnum; Lvalue=Lnext>value；q=L-next；L>next=L-nextnext；free（q）； 5.4源程序代碼typedef struct Nodeint value；Node next；int num；Node；void Creat_JoephLink（int num)Node h

17、ead，q,*L;L=(Node)malloc（sizeof（Node）)；/申請(qǐng)第一個(gè)數(shù)的節(jié)點(diǎn)head=L；Lnum=1；printf（”輸入第一個(gè)人的值:”）； /輸入第一個(gè)人的值 scanf（”d”，&（Lvalue)；int i；for（i=2；i=num;i+)q=(Node)malloc（sizeof（Node)；L-next=q；L=q;printf(”輸入第d個(gè)人的值：”,i)； /輸入每個(gè)人的值scanf("d”,&（L-value）；Lnum=i;Lnext=head； L=head；/構(gòu)成單向循環(huán)鏈表int m；int j；printf（”輸入初始值m的大小"）;scanf(”d",m）； printf（"結(jié)果是:n"）；for （j=1；j=num；j+）for(i=1；im；i+)/i做循環(huán)變量L=Lnext；m=Lvalue；/將當(dāng)前值設(shè)為m值printf（”d "，L>num);/輸出當(dāng)前節(jié)點(diǎn)信息/刪除當(dāng)前節(jié)點(diǎn)L-num=Lnext>num； L>value=Lnextvalue；q=L>next;Lnext=L-next>next；free(q);int main(）int num;printf（”輸入人數(shù):")；