數(shù)據(jù)結(jié)構(gòu)(c)嚴蔚敏-(數(shù)組與廣義表)-資料下載頁
2025-07-25 09:07本頁面
【正文】 else preright=paright。 p=pa。pa=paright。 //從行鏈表中刪除 if([pj]==p) [pj]=cp[pj]=pdown。 else cp[pj]down=pdown。 //從列鏈表中刪除 free (p)。 }//else }//while }//for }//OLMatrix_Add 時間復(fù)雜度為 O( ta+tb) Data Structure Page 38 2022/8/22 廣義表的定義 ?廣義表 (列表 ) ? 是線性表的推廣 ，廣泛地應(yīng)用于人工智能等領(lǐng)域的表處理語言LISP語言。 ? 一般記作 LS=(a1,a2,…,an) (n?0) ? 名稱： LS； ? 長度： n； ? 原子： ai是單個元素，一般用小寫字母表示； ? 子表： ai是廣義表，一般用大寫字母表示。 ? 表頭 (Head)： 非空廣義表 LS的第一個數(shù)據(jù)元素 a1； ? 表尾 (Tail)： 非空廣義表 LS除第一個數(shù)據(jù)元素 外的 其余數(shù)據(jù)元 素構(gòu)成的廣義表 (a2,…,an) 。 Data Structure Page 39 2022/8/22 特性 A=() F=(b,(c,d,e)) E=(b,(c),(d,e)) D=(E,A,F) C=(A,D,F) B=(a,B)=(a,(a,(a,v...))) ? 廣義表中的數(shù)據(jù)元素有固定的相對次序； ? 廣義表的元素可以是子表，而子表的元素還可以是子表。 ? 廣義表可以為其它列表共享。 ? 廣義表可以是一個遞歸的表。 廣義表與數(shù)組的區(qū)別 Data Structure Page 40 2022/8/22 操作 —— 長度 A=() F=(b,(c,d,e)) E=(b,(c),(d,e)) D=(E,A,F) C=(A,D,F) B=(a,B)=(a,(a,(a,v...))) 廣義表中元素的 “ 長度 應(yīng)由最外層括弧中的 逗號 來定。 A的長度為 0 F的長度為 2 E的長度為 3 D的長度為 3 C的長度為 3 B的長度為 2 Data Structure Page 41 2022/8/22 操作 —— 取表頭、取表尾 F=(b,(c,d,e)) GetHead(F)=b GetTail(F)=((c,d,e))=F1 GetHead(F1)=(c,d,e)=F2， GetTail(F1)=( ) GetHead(F2)=c， GetTail(F2)=(d,e)=F3 GetHead(F3)=d， GetTail(F3)=(e)=F4 GetHead(F4)=e， GetTail(F4)=( ) ? 兩個操作只對非空表有意義； ? 取表頭的結(jié)果可能是原子，也可能是個廣義表； ? 取表尾 必定 是個廣義表，但可能是個空的廣義表。 Data Structure Page 42 2022/8/22 廣義表的存儲結(jié)構(gòu) ?采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。 ?廣義表的結(jié)點 ? 表結(jié)點 ? 原子結(jié)點 表結(jié)點 tag=1 hp tp 原子結(jié)點 tag=0 atom 標(biāo)志域 標(biāo)志域 表頭指 針 表尾指針 值域 Data Structure Page 43 2022/8/22 A=() B=(e) C=(a,(b,c,d)) D=(A,B,C) E=(a,E) 1 ? 1 ? 1 1 1 1 1 ? 1 ? 1 ? 1 1 ? 0 a 0 a 0 e 0 d 0 b 0 c A B C D E 1 ? ? Data Structure Page 44 2022/8/22 另一種結(jié)點結(jié)構(gòu) 表結(jié)點 tag=1 hp tp 原子結(jié)點 tag=0 atom tp 標(biāo)志域 標(biāo)志域 表頭指 針 值域 同層下一個元素指針 同層下一個元素指針 Data Structure Page 45 2022/8/22 A=() B=(e) C=(a,(b,c,d)) D=(A,B,C) E=(a,E) 1 ? 1 ? 1 ? 1 ? 1 ? 1 1 ? 0 a 0 a 0 e ? 0 d ? 0 b 0 c B C D E A 1 ? ? 1 ? 1 ? Data Structure Page 46 2022/8/22 本章小結(jié) ?了解 數(shù)組的類型定義 及其在高級語言中實現(xiàn)的方法。 ?數(shù)組的特點是一種多維的線性結(jié)構(gòu)，并只進行存取或修改某個元素的值，因此它只需要 采用順序存儲結(jié)構(gòu) 。 ?介紹了 稀疏矩陣的三種表示方法 。至于在具體應(yīng)用問題中采用哪一種表示法這取決于該矩陣主要進行什么樣的運算。 ?廣義表是一種 遞歸定義的線性結(jié)構(gòu) ，因此它兼有線性結(jié)構(gòu)和層次結(jié)構(gòu)的特點。 Data Structure Page 47 2022/8/22 基礎(chǔ)知識題 (數(shù)組部分 ) ?假設(shè)有二維數(shù)組 A6 8，每個元素用相鄰的 6個字節(jié)存儲，存儲器按字節(jié)編址。已知 A的起始存儲位置 (基地址 )為 1000，計算： ? 數(shù)組 A 的存儲） 。 ? 數(shù)組 A 的最后一個元素 a5,7 的第一個字節(jié)的地址 。 ? 按行存儲時，元素 a1,4 的第一個字節(jié)的地址 。 ? 按列存儲時，元素 a4,7 的第一個字節(jié)的地址。 Data Structure Page 48 2022/8/22 ?假設(shè)按低下標(biāo)優(yōu)先存儲整數(shù)數(shù)組 A9 3 5 8時，第一個元素的字節(jié)地址是 100，每個整數(shù)占四個字節(jié)。問下列元素的存儲地址是什么？ (1) a0000 (2) a1111 (3) a3125 (4) a8247 ?按高下標(biāo)優(yōu)先存儲方式 (以最右的下標(biāo)為主序 )，順序列出數(shù)組 A2 2 3 3 中所有元素 ai,j,k,l，為了簡化表達，可以只列出 (i,j,k,l) 的序列。 ?設(shè)有上三角矩陣 (aij)n n，將其上三角元素逐行存于數(shù)組 B[m] 中 ( m 充分大 ) ，使得 B[k]=aij 且 k=f1(i)+f2(j)+c。試推導(dǎo)出函數(shù) f1， f2 和常數(shù) c (要求 f1 和 f2 中不含常數(shù)項 )。 Data Structure Page 49 2022/8/22 ?設(shè)有三對角矩陣 (aij)n n，將其三條對角線上的元素存于數(shù)組 B[3][n] 中，使得元素 B[u][v]=aij，試推導(dǎo)出從(i,j) 到 (u， v) 的下標(biāo)變換公式。 ?設(shè)有三對角矩陣 (aij)n n，將其三條對角線上的元素逐行地存于數(shù)組 B[3n2] 中，使得 B[k]=aij，求： (1) 用 i,j 表示 k 的下標(biāo)變換公式； (2) 用 k 表示 i， j 的下標(biāo)變換公式。 Data Structure Page 50 2022/8/22 基礎(chǔ)知識題 (廣義表部分 ) ?求下列廣義表操作的結(jié)果： ?GetHead((p,h,w))。 ?GetTail((b,k,p,h))。 ?GetHead(((a,b),(c,d)))。 ?GetTail(((a,b),(c,d)))。 ?GetHead(GetTail(((a,b),(c,d))))。 ?GetTail(GetHead(((a,b),(c,d))))。 ?GetHead(GetTail(GetHead(((a,b),(c,d)))))。 ?GetTail(GetHead(GetTail(((a,b),(c,d)))))。 Data Structure Page 51 2022/8/22 ?利用廣義表的 GetHead 和 GetTail 操作寫出函數(shù)表達式，把原子 banana 分別從下列廣義表中分離出來。 ?L1 = (apple,pear,banana,orange)。 ?L2 = ((apple,pear),(banana,orange))。 ?L3 = (((apple),(pear),(banana),(orange)))。 ?L4 = (apple,(pear),((banana)),(((orange))))。 ?L5 = ((((apple))),((pear)),(banana),orange)。 ?L6 = ((((apple),pear),banana),orange)。 ?L7 = (apple,(pear,(banana),orange))。 Data Structure Page 52 2022/8/22 ?畫出下列廣義表的存儲結(jié)構(gòu)圖。 ?((( )), a, ((b, c), ( ), d), (((e)))) ?((((a), b)), ((( ), (d)), (e, f))) ?已知右側(cè)各圖為廣義表的存儲結(jié)構(gòu)圖，寫出各圖表示的廣義表。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1