【文章內(nèi)容簡介】 printf(“Enter x、 loc\n”)。 scanf(“%d,%d”,amp。x,amp。loc)。 for (j=0。jMAXLENGTH,j++) printf(“%d “,list[j])。 printf(“\n”)。 insert(loc,x)。 /* 插入操作子函數(shù) */ for (j=0。jMAXLENGTH,j++) printf(“%d “,list[j])。 printf(“\n”)。 } 下一頁 上一頁 停止放映 第 42 頁 算法 12 線性表刪除算法 算法步驟 : step1 判別指定的位置是否合法； step2 若合法，則將位置 i+1至 n上的元素前 移一個存儲位置 。 step3 表的長度 1。 線性表采用一維數(shù)組存放。 C語言描述為： define MAXLENGTH 100 int list [MAXLENGTH]； int last ； /* last 指示表中最后一個元素的序號 */ 下一頁 上一頁 停止放映 第 43 頁 刪除算法示意舉例 命題 : 設(shè)有數(shù)列 {4,5,8,10,21,25,30,43,59}，長度為 9，將第 6位的元素“ 25”刪除。 算法描述： ?從第 7個元素開始 (i+1)； ?將第 7個元素“ 30”存入第 6位，將“ 25”覆蓋，即元素左移，移動元素個數(shù)是 3（ 96）； for(k= i+1。k=last。k++) /* last 是元素個數(shù) (9), */ list[k1]=list[k]。 /* i是刪除 位置 (6) */ ?元素個數(shù)減“ 1” last； /* 操作后， last 等于 8 */ ?最后，得到的結(jié)果數(shù)列是 {4,5,8,10,21,30,43,59} 下一頁 上一頁 停止放映 第 44 頁 算法 12 線性表刪除算法 delete(int i) { int k。 if( i 1 || i last ) { printf(“表中不存在位置為 i的元素 \n”)。 exit(1)。 } for(k= i1。k=last2。k++) list[k]=list[k+1]。 last。 } 下一頁 上一頁 停止放映 第 45 頁 算法 12 線性表刪除算法 define MAXLENGTH 100 /* 例 12主程序 */ int list[MAXLENGTH]={5,3,1,10,7,8,1,4}。 int last=8。 main（） { int j,loc。 printf(“Enter loc\n”)。 scanf(“%d”,amp。loc)。 for (j=0。jMAXLENGTH,j++) printf(“%d “,list[j])。 printf(“\n”)。 delete(loc)。 /* 刪除操作子函數(shù) */ for (j=0。jMAXLENGTH,j++) printf(“%d “,list[j])。 printf(“\n”)。 } 下一頁 上一頁 停止放映 第 46 頁 順序存儲結(jié)構(gòu)的特點 ?數(shù)據(jù)連續(xù)存放、隨機存取 ?邏輯上相鄰，物理上也相鄰 ?存儲結(jié)構(gòu)簡單、易實現(xiàn) ?插入、刪除操作不便 ?存儲密度大，空間利用率高 結(jié)論 ： 順序存儲結(jié)構(gòu)適合于表中元素變動較少的情況。 下一頁 上一頁 停止放映 第 47 頁 （三 ）線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 線性表的順序存儲結(jié)構(gòu)容易實現(xiàn)，可以隨機存取表中的任意元素。 ? 順序表 缺點是： – 難于插入、刪除操作； – 需要預(yù)先分配空間，不管這些空間能否最大限度地利用。 ? 鏈表存儲結(jié)構(gòu) 在這兩個方面恰好是優(yōu)點： – 容易插入、刪除操作 – 不需要預(yù)分空間。 下一頁 上一頁 停止放映 第 48 頁 1. 鏈表有關(guān)基本概念 結(jié)點（ NODE） 表中元素的存儲單元。 鏈表存儲結(jié)構(gòu)形式為： 鏈表結(jié)構(gòu)的 C語言描述為： struct node { int data 。 struct node *next 。 }。 typedef struct node NODE； data next 數(shù)據(jù)域 指針域 下一頁 上一頁 停止放映 第 49 頁 鏈表（ Link） 由結(jié)點組成的表。 頭指針（ head） 指向鏈表中第 1個結(jié)點的指針。 頭結(jié)點 為方便操作，在頭指針和頭結(jié)點之間設(shè)置的結(jié)點。 首元結(jié)點 第一個結(jié)點（ a1）。 基本概念 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)一。 ?空表形式 : head = NULL ?非空表形式 : head ? . next = address head head a1 下一頁 上一頁 停止放映 第 52 頁 鏈表舉例 ? 由食品組成的單鏈表（不帶頭結(jié)點 ） （ biscuit,butter,cheese,eggs,grapes,jam) biscuit butter cheese jam grapes eggs ^ head 頭指針 下一頁 上一頁 停止放映 第 53 頁 單鏈表在存儲區(qū)的物理狀態(tài) Grapes 60 biscuit 61 cheese 13 eggs 1 jam NULL butter 12 存儲地址 數(shù)據(jù)域（ data）指針域（ next） 1 11 12 13 60 61 11 頭指針 head …… 下一頁 上一頁 停止放映 第 54 頁 2. 單鏈表的操作 ?指針的基本操作 ?單鏈表的查找 get ?單鏈表長度計數(shù) Count ?單鏈表的的插入 insert ?單鏈表的刪除 delete 下一頁 上一頁 停止放映 第 55 頁 指針的基本操作 ? 設(shè)指針變量 p、 q的定義為： NODE *p， *q； ? 對鏈表的操作實際上是對指針的操作。例如，要刪除結(jié)點 ai，首先要使指針 P指向 ai，即： a1 ... ... head ai an ^ p 指針 p是指向存儲單元 ai的指針，地址內(nèi)的內(nèi)容可以通過 Pdata得到，指向下個元素的指針用 pnext得到 下一頁 上一頁 停止放映 第 56 頁 指針的基本操作列表 p=（ NODE*） malloc（ sizeof（ NODE）） 申請一個結(jié)點空間 ,并將地址送入 p中 free（ p） 釋放 p指針?biāo)附Y(jié)點的空間 p=q 指針 p指向指針 q所指的結(jié)點 p=qnext 指針 p指向指針 q所指結(jié)點的后繼 p=pnext 指針 p向后移動一個結(jié)點 pnext=q 將指針 q所指結(jié)點改接為指針 p所指結(jié)點的后繼 pnext=NULL 將指針 p所指結(jié)點與后繼結(jié)點斷開 下一頁 上一頁 停止放映 第 57 頁 指針操作的舉例 1 申請一個結(jié)點空間 ,并將地址送入 p中 p 操作前狀態(tài) 操作后狀態(tài) p p=（ NODE*） malloc（ sizeof（ NODE）） 下一頁 上一頁 停止放映 第 58 頁 指針操作的舉例 2 p=pnext 指針右移一個結(jié)點位置。 ai ai1 ai+1 ai ai1 ai+1 p p 操作前狀態(tài) 操作后狀態(tài) 下一頁 上一頁 停止放映 第 59 頁 指針操作的舉例 3 p=qnext p指向 q所指結(jié)點