第2章之線性鏈表-資料下載頁
2025-09-19 16:22本頁面
【導讀】由于邏輯上相鄰的元素其。元素的地址信息。指針的數(shù)據(jù)元素稱為結(jié)點。問題而定，本節(jié)也將其設(shè)定為ElemType類型，表的頭指針，本節(jié)用head表示。置的元素時進行的特殊程序處理。鏈表由結(jié)點組成的表。之間設(shè)置的結(jié)點。首元結(jié)點第一個結(jié)點。若沒有頭結(jié)點,空表和非空表的表示形式不統(tǒng)一。這個定義是自引用類型的。也可向其他變量賦值。p=q->nextp指向q所指結(jié)點的后繼.step3每循環(huán)一次,P后移一個位置,step4循環(huán)結(jié)束,返回計數(shù)器值。{if(i<1)cout<<”不存在第”<<i<<”個元素”;
【正文】 鏈表當前位置的指針 Step2 i和 j均分別 ≤ len_a和 len_b的循環(huán) 分別取出兩個表中的當前元素進行比較 ： 若 a b , 則 i 加 1 。 若 a b , 則 j 加 1 。 若 a = b , 則將 a插入 C中 ,i、 j和 k均加 1。 Step3 重復執(zhí)行 Step2 ，直到所有表都處理完為止。 下一頁 上一頁 停止放映 [第 37頁 /41] 例題二示意圖 A a1 a2 a3 … ai ai+1 … an B b1 b2 b3 … bi bi+1 … bm 比較） i j A a1 a2 a3 … ai ai+1 … an B b1 b2 b3 … bi bi+1 … bm 比較） i j 若 ab, 則 i++ A a1 a2 a3 … ai ai+1 … an B b1 b2 b3 … bi bi+1 … bm 比較） i j 若 ab, 則 j++ 下一頁 上一頁 停止放映 [第 38頁 /41] 例題二程序 void separate(LinkListamp。 head_a, LinkListamp。 head_b, LinkListamp。 head_c) { int i=1， j=1， k=1， len_a, len_b, data_a, data_b 。 len_a = length(a) 。 len_b = length(b) 。 /* 求 a和 b的長度 */ while ( ( i = len_a)amp。amp。 ( j = len_b)) { data_a = find( a, i )。 data_b = find( b, j) 。 /* 取 A和 B中的元素 */ if (data_a data_b) i ++。 else if (data_a data_b) j ++。 else if ( data_a == data_b) { insert ( c, data_a, k )。 k ++ 。 i ++ 。 j++。 } } } 例如： A = { 1,3,5}， B={2,3,6}, C={}； Step1 從 A中取出 1和 B中 2比較， i ++； Step2 從 A中取出 3和 B中 2比較， j ++； Step3 從 A中取出 3和 B中 3比較，將 3插入 C中，得結(jié)果： C={ 3}； 下一頁 上一頁 停止放映 [第 39頁 /41] 鏈表應用舉例 約瑟夫環(huán)問題可以解釋為： 將整數(shù) 1至 n圍成一個圓圈，假定從某個整數(shù)開始順時針從 1數(shù)到 m時，令該位置整數(shù)出列；然后再從下一數(shù)開始，順時針從 1數(shù)到第 m時再令其出列，如此下去，直到圓圈中無整數(shù)為止。請寫出所有數(shù)字出列的順序。 【 例 22】 約瑟夫環(huán)（單鏈表） 例：整數(shù) 10，從 1開始到 4，則輸出為： 4 8 2 7 3 10 9 1 6 5 下一頁 上一頁 停止放映 [第 40頁 /41] 鏈表存儲結(jié)構(gòu)的特點 插入、刪除操作極為方便 數(shù)據(jù)非連續(xù)存放、順序存取 邏輯上相鄰，物理上不一定相鄰 存儲結(jié)構(gòu)較復雜、需要額外的存儲空間 結(jié)論 ： 鏈表存儲結(jié)構(gòu)適合于表中元素頻繁變動的線性表。 下一頁 上一頁 停止放映 [第 41頁 /41] 結(jié)束語 歡迎參加到中心網(wǎng)站 《 軟件開發(fā)技術(shù)基礎(chǔ) 》課程的學習討論中來。 中心網(wǎng)址： 課件下載地址 : 我的 Email地址 : 答疑安排： 每星期五下午： 3:00～ 6:00 地點： 計教中心 505房間
教學課件相關(guān)推薦
鄂ICP備17016276號-1