【文章內(nèi)容簡介】 雙向鏈表 2． 雙向鏈表運算的算法 雙向鏈表刪除的算法 (算法 ) Datatype DeleteList_DuL(DuLNode *L,DuLNode *p)/*刪除雙向鏈表 L中 p指針所指的元素，并將被刪除的結點的值作為函數(shù)值返回 */ { x=pdata。 /* 使刪除結點的值賦給 x */ ppriornext=pnext。 /* 使 p結點的前驅結點的后繼指針指向 p結點的后繼結點 */ pnextprior=pprior。 /* 使 p結點的后繼結點的向前指針指向 p結點的前驅結點 */ free(p)。 /* 釋放 p所指被刪除的結點 */ return (x)。 /* 返回被刪除結點的值 */ } 雙向鏈表 2． 雙向鏈表運算的算法 在雙向鏈表 L中插入元素的算法 (算法 ) InserterList_DuL(DuLNode *L,DuLNode *p, Datatype e) /*將 e元素插入到雙向鏈表 L中 p指針所指的元素的前邊 */ { s=(struct DuLNode *)malloc(sizeof(struct DuLNode))。 /* 申請一個結點，讓指針 s指向它 */ sdata=x。 /* 將 x送入新結點 */ snext=p。 /* 使新結點的后繼指針指向 p結點 */ sprior=pprior。 /* 使新結點的前驅指針指向 p結點的前驅結點 */ ppriornext=s。 /* 使 p結點的前驅結點的后繼指針指向新結點 */ pprior=s。 /* 使 p結點的前驅指針指向新結點 */ } 鏈表的上機實習 ? 實習 1 ? 實習 2 ? 實習 3 實習 1 編寫完整程序。程序中包括下列函數(shù)，在主程序中調(diào)用各函數(shù)，實現(xiàn)對單鏈表 L的相關操作 (算法 )。 void createlist (L) 功能：輸入 n個元素，存放在單鏈表 L中，可按順序輸出 L中的元素。 void insert (L, I, x) 功能：輸入 x，并將 x插入到鏈表 L中，作為鏈表的第 i個元素，并按順序輸出 L中的元素。 void delete(L, i, x) 功能：將鏈表 L中第 i個元素刪除，將刪除的元素值賦給形參 x并顯示出來，并按順序輸出 L中的元素。 實習 1 void print(L) 功能：將鏈表 L的元素值輸出。 在主菜單中提供下列菜單： 1建立鏈表 L 2插入元素 3刪除元素 4顯示鏈表中的各元素 0退出 程序參見 P18. 實習 2 設線性表 A=(a1， a2， a3， … ， an)以帶頭結點的單鏈表作為存儲結構 。 編寫一個函數(shù) ， 對 A進行調(diào)整 ， 使得當 n為奇數(shù)時 A=(a2,a4,… ,an1,a1,a3,… ， an)；當 n為偶數(shù)時 A=(a2,a4,… , an,a1,a3,… ， an1)。 (算法 ) 具體算法如下： Regulate(nodetype *p) /* p是指向表頭結點的指針 */ { nodetype *p1,*p2,*q。 p1=p。 q=p1next。 p2=qnext。 while(p2) { qnext=p2next。 p2next=p1next。 p1next=p2 p1=p2。 q=qnext。 p2=qnext。 } } 實習 3 假設以帶頭結點的單循環(huán)鏈表作非遞減有序線性表的存儲結構 。 請設計一個時間復雜度為 O(n)的算法 ， 刪除表中所有數(shù)值相同的多余元素 ， 并釋放結點空間 。 例如：(7， 10， 10， 21， 30， 42， 42， 42， 51， 70)， 經(jīng)算法操作后變?yōu)椋?(7， 10， 21， 30， 42， 51， 70)。 (算法 ) 具體算法如下： DeleteEq(nodetype *L) { nodetype *p ,*p1, *p2。 p1=Lnext。 p=p1next。 while(p) { if(p1data==pdata) { p2=p。 p=pnext。 p1next= p。 free(p2)。 } else { p1=p。 p=pnext。 } } } 習 題 ? 1 填空題 ? 2 選擇題 ? 3 簡答題 ? 4 算法題 習 題 __填空題 (1) 鏈表中邏輯上相鄰的元素的物理位置 ____________相連 。 (2) 在單鏈表中除首結點外 ， 任意結點的存儲位置都由 __________結點中的指針指示 。 (3) 在單鏈表中 ， 設置頭結點的作用是在插入或刪除首結點時不必對____________進行處理 。 (4) 已帶表頭結點的單鏈表 L， 指針 p指向 L鏈表中的一個結點 ， 指針 q是指向 L鏈表外的一個結點 ， 則： ① 在指針 p所指結點后插入 q所指結點的語句序列是 __________________； ② 在指針 p所指結點前插入 q所指結點的語句序列是 _________________； ③ 將 q所指結點插入在鏈表首結點的語句序列是 __________________； ④ 將 q所指結點插入在鏈表尾結點的語句序列是 ___________________。 習 題 __填空題 (5) 已知帶表頭結點的單鏈表 L， 指針 p指向 L鏈表中的一個結點 (非首結點 ． 非尾結點 )， 則： ① 刪除指針 p所指結點的直接后繼結點的語句是 ______________________； ② 刪除指針 p所指結點的直接前驅結點的語句序列是 __________________； ③ 刪除指針 p所指結點的語句序列是 ______________________； ④ 刪除首結點的語句序列是 ______________________； ⑤ 刪除尾結點的語句序列是 ______________________。 (6) 已知指針 p指向雙向鏈表中的一個結點 (非首結點 ， 非尾結點 )， 則： ① 將結點 s插入在指針 p所指結點的直接后繼位置的語句是 _____________； ② 將結點 s插入在指針 p所指結點的直接前驅位置的語句是 ___________； ③ 刪除指針 p所指結點的直接后繼結點的語句序列是 __________________； ④ 刪除指針 p所指結點的直接前驅結點的語句序列是 __________________； ⑤ 刪除指針 p所指結點的語句序列是 ______________________。 習 題 __填空題 (7) 線性表的存儲結構有順序存儲和 ______________存儲兩種 。 (8) 線性表的元素長度為 4， 在順序存儲結構下 LOC(ai)=2021， 則 LOC(ai+1)= ____。 (9) 線性表 a的元素長度為 L， 在順序存儲結構下 Loc(ai)=Loc(a1)+________。 (10) 在線性表的鏈式存儲結構中 ， 某結點的指針字段指向該結點的 ____兩種存儲 。 (11) 線性表的元素長度為 4， Loc(a1)=1000， 則 Loc(a3)= ___________。 (12) 在 下 圖所示的鏈表中 ， 若在指針 p所指的結點之后插入數(shù)據(jù)字段相繼為 a和 b的兩個結點 ， 則可用下列兩個語句實現(xiàn)該操作 ， 它們依次是 ______和 _______。 習 題 __填空題 習 題 __單項選擇題 ( 1 ) 下列說法正確的是 _ _ _ _ _ _ _ _ _ _ _ _ 。 A . 線性表的邏輯順序與存儲順序總是一致的 B . 線性表的鏈式存儲結構中，內(nèi)存中可用的存儲單元可以是連續(xù)的， 可以不連續(xù) C. 線性表的順序存儲結構優(yōu)于鏈式存儲結構 D. 每種數(shù)據(jù)結構都具有插入、刪除和查找三種基本運算 (2 ) L 是線性表，已知 L i s t L e n g t h ( L ) 的值是 5 ，經(jīng)運算 D el et eL i s t (L ,2 ) 后L i s t L e n g t h ( L ) 的值是 _ _ _ _ _ _ _ _ _ _ _ _ 。 A. 5 B. 0 C. 4 D. 6 (3 ) 線性表中哪些元素只有一個直接前驅和一個直接后繼 _ _ _ _ _ _ _ _ _ _ _ _ 。 A. 首元素 B. 尾元素 C. 中間的元素 D. 所有的元素 習 題 __單項選擇題 (4 ) 線性表 L 經(jīng)運算 I n i t L i s t ( L ) 后，函數(shù) E m p t y ( L ) 的值是 _ _ _ _ _ _ _ _ _ _ _ _ 。 A . 0 B. fal s e C. 1 D. n u l l (5 ) 指針 P 指向循環(huán)鏈表 L 的首元素的條件是 _ _ _ _ _ _ _ _ _ _ _ _ 。 A . p = = L B . p n es t = = L C . L n e s t = = p D . p n es t = = n u l l (6 ) 線性表中各元素之間的關系是 _ _ _ _ _ _ _ _ _ _ _ _ 關系。 A. 層次 B. 網(wǎng)狀 C. 有序 D. 集合 習 題 __單項選擇題 (7 ) 在單鏈表的一個結點中有 _ _ _ _ _ _ _ _ _ _ _ _ 個指針。 A . 1 B . 2 C . 0 D . 3 (8 ) 在雙向鏈表的一個結點中有 _ _ _ _ _ _ _ _ _ _ _ _ 個指針。 A . 1 B . 2 C . 0 D . 3 (9 ) 指針 p 所指的元素是雙向循環(huán)鏈表 L 的尾元素的條件是 _ _ _ _ _ _ _ _ _ _ _ _ 。 A . p ==L B . p == n u l l C. p p ri o r= = L D. p n e x t = = L 習 題 __單項選擇題 (1 0 ) p 和 q 兩個指針分別指向雙向循環(huán)鏈表 L 的兩個元素， p 所指元素是 q 所指元素的后繼的條件是 _ _ _ _ _ _ _ _ _ _ _ _ 。 A. p == q B. q n e x t = =p C . p n e x t = =q D. q n e x t = =p n e x t (1 1 ) 兩指針 p 和 q ，分別指向單鏈表的兩個元素， p 所指元素是 q 所指元素的前驅的條件是 _ _ _ _ _ _ _ _ _ _ _ _ 。 A . p n e x t =q B. q n e x t = p C. p = q D . p n e x t =q n e x t (1 2 ) 指針 p 指向線性鏈表Ｌ的首元素的條件是 _ _ _ _ _ _ _ _ _ _ _ _ 。 A . p == L B. L n e x t = = p C. p n e x t = = Ｌ D. p n e x t = =n u l l 習 題 __單項選擇題 (1 3 ) 在長度為 n 的順序表的第 i (1 ≤ i≤ n + 1 ) 個位置上插入一個元素，元素的移動次數(shù)為 _ _ _ _ _ _ _ _ _ _ _ _ 。 A. n i +1 B. n i C. i D. i 1 ( 14 ) 對于只在表的首尾兩端進行插入操作的線性表，宜采用的存儲結構為_ _ _ _ _ _ _ _ _ _ _ _ 。 A. 順序表 B. 用頭指針表示的單循環(huán) 鏈表 C. 用尾指針表示的單循環(huán)鏈表 D. 單