線性表的邏輯結(jié)構(gòu)及其基本操作【精品-ppt】(編輯修改稿)
2024-11-14 19:01 本頁面
【文章內(nèi)容簡介】 snext＝ p。 ppriornext＝ s。 pprior＝ s。 } 2021/11/12 38 ① ② ③ ④ s ⑤ p x a ⑥ 2021/11/12 39 雙鏈表的刪除操作 DELETENODEp(dlinklist *p) { ppriornext＝ pnext。 pnextprior＝ pprior。 free(p)。 } 2021/11/12 40 靜態(tài)鏈表的定義如下： define maxsize 1024 //存儲池最大容量 typedef int datatype。 typedef int cursor。 typedef struct //結(jié)點(diǎn)類型 { datatype data。 cursor next。 } node。 node nodepool[maxsize]。 //存儲池 cursor av。 2021/11/12 41 初始化可用空間表 av INITIALIZE() { int i。 for (i=0。imaxsize1。i++) nodepool[i].next＝ i+1。 nodepool[maxsize1].next＝ NULL。 av＝ 1。 } 2021/11/12 42 1 2 3 4 ? NULL 1 data next av Maxsize1 Maxsize1 2021/11/12 43 結(jié)點(diǎn)的分配算法 cursor GETNODE() { cursor p。 if (av==NULL) p＝ NULL。 else { p＝ av。 av＝ nodepool[av].next。 } return p。 } 2021/11/12 44 結(jié)點(diǎn)的回收算法 FREENODE(cursor p) { nodepool[p].next＝ av。 av＝ p。 } 2021/11/12 45 靜態(tài)鏈表查找算法 cursor FINDSTLIST(cursor L,int i) { cursor p。 int j。 p＝ L。 j＝ 0。 while ((nodepool[p].next!=NULL)amp。amp。(ji)) { p＝ nodepool[p].next。 j++。 } if (i==j) return(p)。 else return NULL。 } 2021/11/12 46 靜態(tài)鏈表插入算法 int INSERTSTLIST(cursor L,datatype x,int i) { cursor p,s。 p＝ FINDSTLIST(L,i1)。 if (p!=NULL) { s＝ GETNODE()。 if (s==NULL) { printf(“error\n”)。 return NULL。} else { nodepool[s].data＝ x。 nodepool[s].next＝ nodepool[p].next。 nodepool[p].next＝ s。 return(1)。 } } else { printf(“error\n”)。 retur NULL。} } 2021/11/12 47 靜態(tài)鏈表刪除算法 DELETESTLIST(cursor L,int i) { cursor p,q。 p＝ FINDSTLIST(L,i1)。 if ((p!=NULL)amp。amp。(nodepool[p].next!=NULL) { q＝ nodepool[p].next。 nodepool[p].next＝ nodepool[q].next。 FREENODE(q)。 } else printf(“error\n”)。 } 2021/11/12 48 順序表與鏈表的 比較 基于空間的考慮 基于時(shí)間的考慮 基于語言的考慮 2021/11/12 49 應(yīng)用實(shí)例 以單鏈表存儲結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆轉(zhuǎn) 全局變量法 參數(shù)法 2021/11/12 50 la 單鏈表的逆轉(zhuǎn) la la la la p q p q p p 2021/11/12 51 linklist *la。 Void convers1() linklist *p,*q。 p = lanext。 lanext = NULL。 While (p != NULL)。 { q = p。 p = pnext。 qnext = lanext。 lanext = q。 } 2021/11/12 52 Void convers2(linklist *la) linklist *p,*q。 p = lanext。 lanext = NULL。 While (p != NULL)。 { q = p。 p = pnext。 qnext = lanext。 lanext = q。 } 2021/11/12 53 例：在一個(gè)給定的線性表中刪除元素值在 x到 y之間的所有元素，要求以較高的效率實(shí)現(xiàn) 算法思想： 先將向量 A中所有在 x到 y之間的元素置成一個(gè)特殊的值 0， 并不立即刪除它們 ， 然后從最后向前依次掃描 ， 刪除為 0的元素 ， 移動后面的元素 。 2021/11/12 54 void del(A,n,x,y) int A[ ]。 int n,x,y。 { int i,k。 for (i=1。 i=n。 i++) if (A[i]=x amp。amp。 A[i]=y) A[i]=0。 for (i=n。 i=1。 i) if (A[i]=0) { for (k=i。 k=(n1)。 k++) A[k] = A[k+1]。 n。 } } 2021/11/12 55 例：用不多于 3n/2的平均比較次數(shù)，在一個(gè)線性表中找出最大和最小值的元素 void maxmin(A,n) int A[]。 int n。 { int max, min, i。 for (i=2。 i=n。 i++) if (A[i] max) max = A[i]。 else if (A[i] min) min = A[i]。 printf(“max = %d, min = %d \n”, max, min)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1