【正文】 =pnext。 } else { s=(NODE*)malloc(sizeof(NODE))。 exit(0)。 ?如果讓鏈表首尾相接，構(gòu)成環(huán)形，這就是 單循環(huán)鏈表 。 ai1的標(biāo)識符為 : p?.prior, ai1的數(shù)據(jù)域標(biāo)識符為 : p?.prior ? .data ai+1的標(biāo)識符為 : p?.next, ai+1的數(shù)據(jù)域標(biāo)識符為 : p?. next ? .data p a i+1 ai a i1 下一頁 上一頁 停止放映 第 80 頁 鏈表存儲結(jié)構(gòu)的特點 插入、刪除操作極為方便 數(shù)據(jù)非連續(xù)存放、順序存取 邏輯上相鄰，物理上不一定相鄰 存儲結(jié)構(gòu)較復(fù)雜、需要額外的存儲空間 結(jié)論 ： 鏈表存儲結(jié)構(gòu)適合于表中元素頻繁變動的線性表。 j = length(head_a) 。 若 a b , 則 j 加 1 。 ( j = len_b)) { data_a = get( a, i )。 } } } 例如： 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}； 下一頁 上一頁 停止放映 第 89 頁 結(jié)束語 歡迎參加到中心網(wǎng)站 《 軟件基礎(chǔ) 》 課程的學(xué)習(xí)討論中來。 /* 取 A和 B中的元素 */ if (data_a data_b) i ++。 Step3 重復(fù)執(zhí)行 Step2 ，直到所有表都處理完為止。 while ( j = 2) { data1= get( head_a, j )。因此，建立鏈表的過程是動態(tài)生成的過程。 下一頁 上一頁 停止放映 第 71 頁 單循環(huán)鏈表 單循環(huán)鏈表表示形式： 單循環(huán)鏈表為空的條件 : head ?.next=head 表示形式為 : head ... head a1 a2 an 下一頁 上一頁 停止放映 第 72 頁 單循環(huán)鏈表特點 ?從表中任一結(jié)點出發(fā) ,均可以找到表中其它結(jié)點。 exit(0)。 snext=pnext。 } return counter。(counter == i)) return p。 int counter = 0。(counteri)) /* i次的循環(huán)處理 */ { p=pnext。 基本概念 head a1 頭指針 頭結(jié)點 首元結(jié)點 a i ... 第 i個結(jié)點 下一頁 上一頁 停止放映 第 50 頁 表示形式的統(tǒng)一 空表和非空表表示形式在頭結(jié)點上得到統(tǒng)一 空表的形式 : head ?. next = NILL 非空表的形式 : head ? . Next = Address head ^ 頭結(jié)點 head 頭結(jié)點 下一頁 上一頁 停止放映 第 51 頁 表示形式不統(tǒng)一 ?若沒有頭結(jié)點 , 空表和非空表的表示形式將不統(tǒng)一。 下一頁 上一頁 停止放映 第 48 頁 1. 鏈表有關(guān)基本概念 結(jié)點（ NODE） 表中元素的存儲單元。 delete(loc)。 int last=8。 /* i是刪除 位置 (6) */ ?元素個數(shù)減“ 1” last； /* 操作后， last 等于 8 */ ?最后，得到的結(jié)果數(shù)列是 {4,5,8,10,21,30,43,59} 下一頁 上一頁 停止放映 第 44 頁 算法 12 線性表刪除算法 delete(int i) { int k。 printf(“\n”)。x,amp。k) list[k+1]=list[k]。 /* i是插入 位置 (5) */ ? 將空出的第 6個位置，存放“ 25”。 下一頁 上一頁 停止放映 第 37 頁 線性表元素存儲示意圖 a1 a2 …. ai …. 元素序號 內(nèi)存狀態(tài) 存儲地址 1 2 …. i …. LOC(a1) LOC(a1)+1 …. LOC(a1)+(i1) …. 下一頁 上一頁 停止放映 第 38 頁 算法 11 插入算法 算法步驟 : step1 將第 n至第 i個元素后移一個存儲位置 。 線性表雖然簡單，但是應(yīng)用范圍非常廣泛。 下一頁 上一頁 停止放映 第 28 頁 高效率與低存儲量 ?處理速度快 ?存儲容量小 ?時間和空間是矛盾的、實際問題的求解往往是求得時間和空間的統(tǒng)一、折中。 常見操作有： – 輸入、檢索、插入、刪除、修改、排序等。 ? 插入、刪除操作簡單，只要修改指針即可； ? 結(jié)構(gòu)較復(fù)雜，需要額外存儲空間。 ? 任何一個 算法的設(shè)計 取決于選定的邏輯結(jié)構(gòu)；而算法的最終實現(xiàn) 依賴于采用的存儲結(jié)構(gòu)。 ? 數(shù)據(jù)結(jié)構(gòu)（ Data Structure） 是帶有結(jié)構(gòu)特征的數(shù)據(jù)元素的集合 ,三要素： DS=數(shù)據(jù)的邏輯結(jié)構(gòu) +存儲結(jié)構(gòu) +數(shù)據(jù)的運算 數(shù)據(jù)結(jié)構(gòu)是以數(shù)據(jù)為加工對象，研究數(shù)據(jù)組織方式和相關(guān)操作方法的學(xué)問。 ? 數(shù)據(jù)元素（ Element） 是數(shù)據(jù)的基本單位、數(shù)據(jù)集合中的個體。 ? 數(shù)據(jù)的 存儲結(jié)構(gòu) 是邏輯結(jié)構(gòu)在計算機中的實現(xiàn)，是依賴于計算機的；離開了機器，則無法進行任何操作。數(shù)據(jù)結(jié)點結(jié)構(gòu) : d1 ... d2 dn ^ 數(shù)據(jù)域 指針域 特點 : ? 非連續(xù)存放 ,借助指針來表示元素間的關(guān)系 。 下一頁 上一頁 停止放映 第 21 頁 ?數(shù)據(jù)運算是指對存放在物理結(jié)構(gòu)上的數(shù)據(jù) ,按定義的邏輯結(jié)構(gòu)進行的各種操作。 下一頁 上一頁 停止放映 第 27 頁 健壯性（ Robustness） ?當(dāng)輸入非法數(shù)據(jù)時，算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或進行處理；并且，處理出錯的方法應(yīng)該是返回一個表示錯誤或錯誤性質(zhì)的值并中止程序的執(zhí)行，以便在更高的抽象層次上進行處理。例如，一星期七天的英文縮寫表示： （ Sun， Mon， The， wed， Thu， Fri， Sat） 是一個線性表，其中的元素是字符串，表的長度為 7。順序表的存儲特點是：只要確定了起始位置，表中任一元素的地址都通過下列公式得到： LOC（ ai） =LOC（ a1） +（ i1） *L 1?i ?n 其中， L是元素占用存儲單元的長度。k) /* last 是元素個數(shù) (8), */ list[k+1]=list[k]。K=i1。 scanf(“%d,%d”,amp。jMAXLENGTH,j++) printf(“%d “,list[j])。k++) /* last 是元素個數(shù) (9), */ list[k1]=list[k]。 } 下一頁 上一頁 停止放映 第 45 頁 算法 12 線性表刪除算法 define MAXLENGTH 100 /* 例 12主程序 */ int list[MAXLENGTH]={5,3,1,10,7,8,1,4}。 printf(“\n”)。 ? 鏈表存儲結(jié)構(gòu) 在這兩個方面恰好是優(yōu)點： – 容易插入、刪除操作 – 不需要預(yù)分空間。 首元結(jié)點 第一個結(jié)點（ a1）。amp。 /* 否則，返回空值 */ 下一頁 上一頁 停止放映 第 63 頁 單鏈表查找算法程序 NODE *get(NODE *head, int i） ｛ NODE *p。amp。 counter++。 sdata=x。 } if(pnext==NULL) { printf(“i=表長 +1,無此結(jié)點 \n”)。 ?鏈表可以從兩個方向檢索，效果更佳；這就是 雙向循環(huán)鏈表 。 下一頁 上一頁 停止放映 第 81 頁 5. 鏈表的動態(tài)生成 鏈表是一種動態(tài)存儲結(jié)構(gòu)。 if ( j%2 == 1) j 。 若 a = b , 則將 a插入 C中 ,i、 j和 k均加 1。 data_b = get( b, j) 。 中心網(wǎng)址： 課件下載地址 : 我的 Email地址 : 答疑安排： 每星期四下午： 4： 00～ 6： 00 地點： 計教中心 102房間（ 1300大教室對面）