1、2014-2015學年第一學期的實驗報告課程名稱：算法和數(shù)據(jù)結(jié)構(gòu)實驗名稱：城市網(wǎng)絡(luò)鏈接表一、實驗?zāi)康谋敬螌嶒灥闹饕康氖鞘煜ぞ€性表的基本運算是由兩個記憶結(jié)構(gòu)實現(xiàn)的，其中以熟悉各種網(wǎng)絡(luò)鏈接表的操作為重點。 對云同步，通過這次的實驗，幫助學生復習高級語言的使用方法。二、實驗內(nèi)容(一)城市網(wǎng)絡(luò)鏈接表；將幾個城市的情報儲存在先頭節(jié)點的網(wǎng)絡(luò)鏈接表里。 節(jié)點的城市信息包括城市名稱、城市位置坐標。 利用城市名稱和位置坐標，能夠進行檢索、插入、刪除、更新等操作。(二)約瑟夫林m的初始值是20。密碼： 3，1，7，2，6，8，4 (正確的結(jié)果是6，1，4，7，2，3，5 )。 三、實驗環(huán)境vs2010、win8

2、.1四、實驗結(jié)果(一)城市網(wǎng)絡(luò)鏈接表：(一)編制城市網(wǎng)絡(luò)鏈接表格；(2)給予城市名稱，返回其位置坐標(3)給出位置坐標p和距離d，返回與p的距離在d以下的所有城市。(四)在現(xiàn)有城市網(wǎng)絡(luò)鏈接表中插入新城市；(五)更新城市信息(六)刪除某城市信息。(二)約瑟夫林m的初始值是20。密碼： 3，1，7，2，6，8，4輸出6，1，4，7，2，3，5。五、附錄城市網(wǎng)絡(luò)鏈接表：5.1問題分析在這個實驗中，由于要求操作網(wǎng)絡(luò)鏈接表的制作、老虎吧、插入、刪除、查詢等，所以使用網(wǎng)絡(luò)鏈接表。5.2設(shè)計方案該計程儀計劃大致分為以下幾個模塊1 .編制城市網(wǎng)絡(luò)鏈接表模塊。 在空網(wǎng)絡(luò)鏈接表中插入新元素。 所以，在城市關(guān)網(wǎng)絡(luò)鏈

3、接表中包含插入模塊進行制作。2 .返回位置坐標模塊。3 .計算距離模塊4 .插入模塊。5 .更新城市信息模塊6 .刪除信息模塊。5.3算法5.3.1根據(jù)中心城市坐標返回距離內(nèi)的所有城市將voidfindcitydistance (city list * l )設(shè)定為/根據(jù)距離輸出城市輸入信息和距離l=下一個；威爾！=空值)(l-x-x1) * (l-y-y1) * (l-y-y1)=dis * dis (l-x-x1) (l-y-y1) )！ 請輸入=0)打印機(城市名稱%sn ，l-name )；打印機(城市坐標%.2lf，%.2lfn ，l-x，l-y )；以下l=下一個；以下以下該算法主

4、要用于匹配定理，認為不需要實際數(shù)值，只要比較大小即可，所以只使用橫軸差的平方縱軸差的平方=距離的平方判定。由于中心城市本身也在判定范圍內(nèi)，因此加上判定條件的橫縱軸差之和不能為零。5.3.2主計程儀沖壓桿上的循環(huán)條件判定：福爾(； 表示)。printf (請選擇動作n )；printf(1.創(chuàng)建城市網(wǎng)絡(luò)鏈接定表格n )；printf(2.按名稱查找城市n )；printf(3.插入n )；printf(4.刪除n )；printf(5.城市信息更新 n )；printf(6.從中心坐標的距離看城市 n )；printf(7.退出系統(tǒng)定n )；掃描( % d ，choice )；交換機(選擇)/c

5、ase文case 73360中斷；以下if (選擇=7)break；以下用戶選擇退出系統(tǒng)的選項時，首先退出switch并退出for循環(huán)。否結(jié)束。是的，是的。是否結(jié)束退出插入刪除更新距離5.4程序流程圖查詢作成開始。選擇操作5.5普計程儀拉姆原代碼類型結(jié)構(gòu)屬性列表。char name20；雙倍x，y；city list *下一步；citylist、*l；語音列表_ sq city (語音列表* l ) |/初始化節(jié)點下一個=空值；以下語音插入_ sq city (地點列表* l ) |/在網(wǎng)絡(luò)鏈接表格中插入元素city list *新節(jié)點；新節(jié)點=(city list * ) malloc (尺

6、寸(city list ) )；國際貨幣基金組織新節(jié)點)printf (存儲分配失敗 )；printf (請輸入城市名稱n )；掃描( % s ，新節(jié)點名稱)；printf (城市坐標x yn )；掃描(“% lf % lf”、“新節(jié)點- x”、“新節(jié)點- y”)；(l -下一個！=空值)l=下一個；/如果不為空，則l指針的位置向后移動新節(jié)點下一個=l -下一個；下一個節(jié)點；以下voidacreate _ sq city (城市列表* l ) |/網(wǎng)絡(luò)鏈接表char ch100；英特爾；輸入printf(end結(jié)束，然后輸入剩馀的值繼續(xù)n )； 輸入/end時，以任意輸入結(jié)束掃描( % s ，

7、ch )；福爾(； 超時空要塞！=0； 中)表示英特爾國際機場輸入printf(end結(jié)束，然后輸入剩馀的值繼續(xù)n )；掃描( % s ，ch )；以下以下將void get _ sqcitycoord (地點列表* l ) )轉(zhuǎn)換為/輸入城市信息返回坐標卡爾卡爾printf (請輸入要查詢的城市 )；掃描( % s ，ch )；(l -下一個！=空strcmp (下一個名稱，ch ) ) 2l=下一個；以下if (l -下一個=空值)printf (城市不存在 )；艾露絲打印機( %.2 lf，%.2lfn ，l-next-x，l-next-y )；以下以下語音刪除_ sq city (城市

8、列表* l ) /刪除城市信息，按名稱/坐標printf (請輸入城市名稱n )；卡爾卡爾掃描( % s ，ch )；(l -下一個！=nullstrcmp (l -下一個名稱，ch)l=下一個；以下if (l -下一個=空值)printf (城市不存在 )； /刪除位置是不合理的下一個=下一個；printf (成功刪除城市 )；以下將voidfindcitydistance (city list * l )設(shè)定為/根據(jù)距離輸出城市printf (輸入關(guān)中心城市點坐標 )；雙精靈x 1，y1；掃描( % lf % lf ，x1，y1)；printf (輸入距離 )；雙面碟；掃描( % lf ，

9、dis )；l=下一個；威爾！=空值)(l-x-x1) * (l-y-y1) * (l-y-y1)=dis * dis (l-x-x1) (l-y-y1) )！ 請輸入=0)打印機(城市名稱%sn ，l-name )；打印機(城市坐標%.2lf，%.2lfn ，l-x，l-y )； 以下l=下一個；以下以下voidapdate _ sq city (城市列表* l ) |/更新城市信息卡爾卡爾printf (請輸入要更新的城市名稱n )；掃描( % s ，ch )；輸入while (strcmp (下一個名稱，ch ) )。 2l=下一個；以下if (l -下一個=空值)printf (城市不

10、存在 )；請輸入printf (城市的新信息：n )。 ）printf (請輸入城市的新名稱n )；掃描( % s ，下一個名稱)；printf (請輸入城市的新坐標n )； 掃描(“% lf % lf”、(l-next-x )、(l-next-y ) )；以下英特曼()城市列表* l；l=(天空列表* ) malloc (天空列表)；初始列表(l )福爾(； 表示)。打印機(打印機)；printf (請選擇動作n )；printf(1.創(chuàng)建城市網(wǎng)絡(luò)鏈接定表格n )；printf(2.按名稱查找城市n )；printf(3.插入n )；printf(4.刪除n )；printf(5.城市信息更

11、新 n )；printf(6.從中心坐標的距離看城市 n )；printf(7.退出系統(tǒng)定n )； 打印機(打印機)；英國選擇；掃描( % d ，選擇)；交換機(選擇)case 1:創(chuàng)建時間(l )getchar ()；中斷；case 2:get_sqcitycoord(l中斷；case 3:英特爾國際機場中斷；case 4:刪除地址(l )中斷；case 5:更新時間(l )中斷；case 6:財務(wù)差距(l )中斷；case 73360中斷；以下if (選擇=7)中斷；以下以下5.6模擬結(jié)果2 .查詢城市信息增加三個城市刪除四個城市更新五個城市按六個距離輸出城市5.7調(diào)整心得體會5.7.1錯

12、誤分析：實驗中的問題是，聲明變量，從關(guān)牛鼻子板讀取數(shù)據(jù)，表示變量沒有初始化，調(diào)試后發(fā)現(xiàn)了scanf問題，在今后的實驗中，必須注意將信息讀取到scanf后存在地址。5.7.2算法復雜性分析：所有項目群的initlist_sqcity的復雜性為o(1)，其馀的為o(n )。5.7.3收獲對數(shù)據(jù)結(jié)構(gòu)這一課地的應(yīng)用有一定的理解，了解了線性表的插入、刪除等操作的實現(xiàn)，加深了對教科書地的理解。附錄約瑟夫林：5.1問題分析在這個實驗中，使用了單個循環(huán)網(wǎng)絡(luò)鏈接表，因為需要遞歸地連續(xù)檢索信息和刪除節(jié)點。5.2設(shè)計方案1 .制作單循環(huán)網(wǎng)絡(luò)鏈接表生成joseph循環(huán)3 .輸出順序表5.3算法5.3.1構(gòu)成網(wǎng)絡(luò)鏈接表將voidacreat _ joephalink (國內(nèi))節(jié)點頭、*q、*l；l=(節(jié)點* ) malloc (節(jié)點)； /申請前幾個節(jié)點頭=l；l -數(shù)=1；printf (第一個人的值： )； /輸入第一個人的值掃描( % d ，(l -值) )；英特爾；for(i=2； i=數(shù)字； 表示i )q=(節(jié)點* ) malloc (節(jié)點)；下一個=q；l=q；printf (輸入個人%d的值： ，i )/輸入各人的值掃描( % d ，(l -值) )；l -數(shù)=i；以下下一個=頭；l=頭； /構(gòu)成單向式循環(huán)網(wǎng)絡(luò)鏈接表以下5.3.2查找和刪