【正文】 – 2) 從任一結(jié)點(diǎn)找其前趨 ,時(shí)間復(fù)雜度是 O(n) ? (2) 單循環(huán)鏈表 鏈表首尾相接，構(gòu)成環(huán)形 – 特點(diǎn) : – 1) 從任一結(jié)點(diǎn)出發(fā) ,均可以找到表中其它結(jié)點(diǎn)。 exit(0)。 head a1 頭指針 頭結(jié)點(diǎn) 首元結(jié)點(diǎn) a i ... 第 i個(gè)結(jié)點(diǎn) 41 /70 設(shè)置頭結(jié)點(diǎn)的目的 (一 ) ? 使空表和非空表表示形式在頭結(jié)點(diǎn)上得到統(tǒng)一 ? (1)有頭結(jié)點(diǎn) ? 空表 : – head next = NULL ? 非空表 : – head next = 地址 head NULL 頭結(jié)點(diǎn) head 頭結(jié)點(diǎn) 42 /70 設(shè)置頭結(jié)點(diǎn)的目的 (二 ) ? (2) 沒有頭結(jié)點(diǎn) ? 表示形式不統(tǒng)一 ? 空表 : – head = NULL ? 非空表 : – head next = 地址 head head a1 43 /70 鏈表舉例 ? 由食品組成的單鏈表（ biscuit,butter,cheese,eggs,grapes,jam) ? 不帶頭結(jié)點(diǎn) : biscuit butter cheese jam grapes eggs head 頭指針 44 /70 單鏈表的存儲(chǔ)狀態(tài) ? Grapes 60 biscuit 61 cheese 13 eggs 1 jam NULL butter 12 存儲(chǔ)地址 數(shù)據(jù)域（ data） 指針域（ next） 1 11 12 13 60 61 11 頭指針 head biscuit,butter,cheese,eggs,grapes,jam 45 /70 單鏈表的操作 – 指針的基本操作 – 單鏈表的查找 get – 單鏈表的的插入 insert – 單鏈表的刪除 delete 46 /70 指針的基本操作 ? (1)定義指針變量 p、 q： – NODE *p， *q； ? (2) 對(duì)鏈表的操作就是對(duì)指針的操作。 36 /70 ? printf(“\n”)。 34 /70 算法 12 —— 線性表刪除算法 ? delete(int i) /*第 i 個(gè)元素的下標(biāo)為 I1 */ ? { int k。 ? int last=7。 23 /70 相互關(guān)系描述 ? 1） L的長(zhǎng)度為 n（ n ?0）， n=0時(shí)是空表； ? 2）除了第 1個(gè)和最后一個(gè)元素外 ,每個(gè)元素有唯一的前趨和后繼； ? 3）線性表中各元素間存在著線性關(guān)系； ? 4）均勻性；各元素?cái)?shù)據(jù)類型必須相同； ? 5）有序性；各元素是有序的，不可交換次序。 – 3) 插入、刪除操作不便（需大量移動(dòng)元素） d1 d2 …… dn 數(shù)據(jù)域 11 /70 (2) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 數(shù)據(jù)元素存放在任意存儲(chǔ)單元中，可連續(xù)存放，也可以不連續(xù)存放，用指針實(shí)現(xiàn)鏈表間的聯(lián)系。 6 /70 ? ? 線性表 堆棧 隊(duì)列 串 數(shù)組 樹 二叉樹 圖 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) DS 7 /70 4. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) ? 又稱物理結(jié)構(gòu) ? 是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示 (又稱映象 ),即數(shù)據(jù)在計(jì)算機(jī)中的存放方式。度量同時(shí)間復(fù)雜度。 exit(2)。 32 /70 ? printf(“\n”)。 ? main（） ? { int j,loc。 39 /70 鏈表的有關(guān)概念 ? 結(jié)點(diǎn)（ NODE） 表中元素的存儲(chǔ)單元。amp。 exit(0)。 68 /70 鏈表的動(dòng)態(tài)生成（方法二）從后往前 ? 算法操作步驟： ? step1 初始化； – 頭指針置 NULL,線性表元素存于 a[N]中 ,i=N1 ? step2 i = 0 循環(huán) – 1) 使 s指向新生成的結(jié)點(diǎn)， head ^ ... s ai1 ai an ai1 69 /70 – 2) sdata = a[i] ,snext = head – 3) 指針 s始終指向頭指針 head=s ? step3 結(jié)束循環(huán) , 返回頭指針 head。 ? else p=get(head,i1)。 counter++。 ? 順序表缺點(diǎn)： – 難于插入、刪除操作； – 需要預(yù)先分配空間，不管這些空間能否最大限度地利用。 ? } 35 /70 算法 12 —— 線性表刪除算法 ? define MAXLENGTH 100 /* 例 12主程序 */ ? int list[MAXLENGTH]={5,3,1,10,7,8,1,4}。j last+1。 exit(1)。用“ O（數(shù)量級(jí)）”來表示，稱為“階”。 4 /70 二 . 數(shù)據(jù)結(jié)構(gòu) ? 1. 數(shù)據(jù)結(jié)構(gòu)（ Data Structure） – 1) 研究數(shù)據(jù)及數(shù)據(jù)元素之間的關(guān)系