【正文】 data_b = get( b, j) 。 if ( j%2 == 1) j 。 ?鏈表可以從兩個(gè)方向檢索，效果更佳；這就是 雙向循環(huán)鏈表 。 sdata=x。amp。amp。 ? 鏈表存儲(chǔ)結(jié)構(gòu) 在這兩個(gè)方面恰好是優(yōu)點(diǎn)： – 容易插入、刪除操作 – 不需要預(yù)分空間。 } 下一頁(yè) 上一頁(yè) 停止放映 第 45 頁(yè) 算法 12 線性表刪除算法 define MAXLENGTH 100 /* 例 12主程序 */ int list[MAXLENGTH]={5,3,1,10,7,8,1,4}。jMAXLENGTH,j++) printf(“%d “,list[j])。K=i1。順序表的存儲(chǔ)特點(diǎn)是：只要確定了起始位置，表中任一元素的地址都通過(guò)下列公式得到： LOC（ ai） =LOC（ a1） +（ i1） *L 1?i ?n 其中， L是元素占用存儲(chǔ)單元的長(zhǎng)度。 下一頁(yè) 上一頁(yè) 停止放映 第 27 頁(yè) 健壯性（ Robustness） ?當(dāng)輸入非法數(shù)據(jù)時(shí)，算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理；并且，處理出錯(cuò)的方法應(yīng)該是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值并中止程序的執(zhí)行，以便在更高的抽象層次上進(jìn)行處理。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu) : d1 ... d2 dn ^ 數(shù)據(jù)域 指針域 特點(diǎn) : ? 非連續(xù)存放 ,借助指針來(lái)表示元素間的關(guān)系 。 ? 數(shù)據(jù)元素（ Element） 是數(shù)據(jù)的基本單位、數(shù)據(jù)集合中的個(gè)體。 ? 任何一個(gè) 算法的設(shè)計(jì) 取決于選定的邏輯結(jié)構(gòu)；而算法的最終實(shí)現(xiàn) 依賴于采用的存儲(chǔ)結(jié)構(gòu)。 常見操作有： – 輸入、檢索、插入、刪除、修改、排序等。 線性表雖然簡(jiǎn)單，但是應(yīng)用范圍非常廣泛。 /* i是插入 位置 (5) */ ? 將空出的第 6個(gè)位置，存放“ 25”。x,amp。 /* i是刪除 位置 (6) */ ?元素個(gè)數(shù)減“ 1” last； /* 操作后， last 等于 8 */ ?最后，得到的結(jié)果數(shù)列是 {4,5,8,10,21,30,43,59} 下一頁(yè) 上一頁(yè) 停止放映 第 44 頁(yè) 算法 12 線性表刪除算法 delete(int i) { int k。 delete(loc)。 基本概念 head a1 頭指針 頭結(jié)點(diǎn) 首元結(jié)點(diǎn) a i ... 第 i個(gè)結(jié)點(diǎn) 下一頁(yè) 上一頁(yè) 停止放映 第 50 頁(yè) 表示形式的統(tǒng)一 空表和非空表表示形式在頭結(jié)點(diǎn)上得到統(tǒng)一 空表的形式 : head ?. next = NILL 非空表的形式 : head ? . Next = Address head ^ 頭結(jié)點(diǎn) head 頭結(jié)點(diǎn) 下一頁(yè) 上一頁(yè) 停止放映 第 51 頁(yè) 表示形式不統(tǒng)一 ?若沒(méi)有頭結(jié)點(diǎn) , 空表和非空表的表示形式將不統(tǒng)一。 int counter = 0。 } return counter。 exit(0)。因此，建立鏈表的過(guò)程是動(dòng)態(tài)生成的過(guò)程。 Step3 重復(fù)執(zhí)行 Step2 ，直到所有表都處理完為止。 } } } 例如： 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}； 下一頁(yè) 上一頁(yè) 停止放映 第 89 頁(yè) 結(jié)束語(yǔ) 歡迎參加到中心網(wǎng)站 《 軟件基礎(chǔ) 》 課程的學(xué)習(xí)討論中來(lái)。 若 a b , 則 j 加 1 。 ai1的標(biāo)識(shí)符為 : p?.prior, ai1的數(shù)據(jù)域標(biāo)識(shí)符為 : p?.prior ? .data ai+1的標(biāo)識(shí)符為 : p?.next, ai+1的數(shù)據(jù)域標(biāo)識(shí)符為 : p?. next ? .data p a i+1 ai a i1 下一頁(yè) 上一頁(yè) 停止放映 第 80 頁(yè) 鏈表存儲(chǔ)結(jié)構(gòu)的特點(diǎn) 插入、刪除操作極為方便 數(shù)據(jù)非連續(xù)存放、順序存取 邏輯上相鄰，物理上不一定相鄰 存儲(chǔ)結(jié)構(gòu)較復(fù)雜、需要額外的存儲(chǔ)空間 結(jié)論 ： 鏈表存儲(chǔ)結(jié)構(gòu)適合于表中元素頻繁變動(dòng)的線性表。 exit(0)。 while( p!=NULL) { p=pnext。 /* 返回 i的值 */ else return NULL。 頭結(jié)點(diǎn) 為方便操作，在頭指針和頭結(jié)點(diǎn)之間設(shè)置的結(jié)點(diǎn)。jMAXLENGTH,j++) printf(“%d “,list[j])。k=last。 printf(“Enter x、 loc\n”)。ki。 下一頁(yè) 上一頁(yè) 停止放映 第 31 頁(yè) 時(shí)間復(fù)雜度舉例 （ a） X： =X+1 ； O（ 1） （ b） FOR I： =1 TO n DO X： = X+1； O（ n） （ c） FOR I： = 1 TO n DO FOR J： = 1 TO n DO O（ n2 ） X： = X+1； 下一頁(yè) 上一頁(yè) 停止放映 第 32 頁(yè) 二、線性表 是指數(shù)據(jù)元素之間的關(guān)系為一一對(duì)應(yīng)的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 特點(diǎn)： – 數(shù)據(jù)元素間無(wú)內(nèi)在聯(lián)系； – 存儲(chǔ)形式不定。 數(shù)據(jù)庫(kù)中的數(shù)據(jù)存放在計(jì)算機(jī)中的物理位置 下一頁(yè) 上一頁(yè) 停止放映 第 15 頁(yè) 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的關(guān)系 ? 數(shù)據(jù)的 邏輯結(jié)構(gòu) 是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨(dú)立于計(jì)算機(jī)的；可以在理論上、形式上進(jìn)行研究、推理、運(yùn)算等各種操作。 按某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，按一定的存儲(chǔ)方式把它存儲(chǔ)在計(jì)算機(jī)存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，叫做一個(gè)數(shù)據(jù)結(jié)構(gòu) (Data Structures)。 下一頁(yè) 上一頁(yè) 停止放映 第 19 頁(yè) 索引存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)按索引形式存放。 下一頁(yè) 上一頁(yè) 停止放映 第 29 頁(yè) 算法的描述 算法的描述方式（常用的）： 自然語(yǔ)言 流程圖 特定的表示算法的圖形 符號(hào) 算法描述 偽語(yǔ)言 包括程序設(shè)計(jì)語(yǔ)言的三 大基本結(jié)構(gòu)及自然語(yǔ)言 的一種語(yǔ)言 類語(yǔ)言 類似高級(jí)語(yǔ)言的語(yǔ)言， 例如，類 PASCAL、類 C語(yǔ)言。 step2 將 x插入到 ai1之后 。 list [i1] =x。 } 下一頁(yè) 上一頁(yè) 停止放映 第 42 頁(yè) 算法 12 線性表刪除算法 算法步驟 : step1 判別指定的位置是否合法； step2 若合法，則將位置 i+1至 n上的元素前 移一個(gè)存儲(chǔ)位置 。 main（） { int j,loc。 鏈表存儲(chǔ)結(jié)構(gòu)形式為： 鏈表結(jié)構(gòu)的 C語(yǔ)言描述為： struct node { int data 。 /* 指針右移一位 */ counter++。 else return NULL。 pnext=s。 ?找其前趨結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O（ n）。 /* 取偶數(shù)編號(hào)的元素 */ insert(head_b , data1 , 1) 。 else if (data_a data_b) j ++。amp。 下一頁(yè) 上一頁(yè) 停止放映 第 85 頁(yè) 例題一程序 void separate( NODE *head_a , NODE *head_b ) { int data1, j 。 ?在單鏈表中 ,從表的任一結(jié)點(diǎn) ai找其前趨結(jié)點(diǎn) ,時(shí)間復(fù)雜度是 O（ n）。 exit(0)。