【正文】 3) 假設以數(shù)組 sequ[m1]存放循環(huán)隊列的元素，設變量 rear和 quelen分別為指示隊尾元素位置和隊中元素個數(shù)，試寫出入隊和出隊算法。 aij的地址為： i（ i1） /2+j 當 i?j LOC（ aij） = j（ j1） /2+i 當 ij 下一頁 上一頁 停止放映 第 90/89 頁 對稱矩陣的壓縮存儲舉例 設有 A3x3矩陣 , a11 A3x3 = a21 a22 a31 a32 a33 存于一維數(shù)組 S[6] S[6]=( a11, a21, a22, a31, a32, a33 ) 1 2 3 4 5 6 LOC(a31)=3(31)/2+1= 4 LOC(a22)=2(22)/2+2= 3 LOC(a21)=2(21)/2+1= 2 下一頁 上一頁 停止放映 第 91/89 頁 作業(yè)、思考題 1. 思考題：第 2題； 1) 試寫出?在帶頭結點的單循環(huán)鏈表中求表長的算法?。為了節(jié)省存儲空間，通常是對這類矩陣進行壓縮存儲。例如， 二維數(shù)組 Am n，可以看作 n個列向量，每個列向量 m個元素。例如， 二維數(shù)組 Am n，可以看作 m個行向量，每個行向量 n個元素。 下一頁 上一頁 停止放映 第 75/89 頁 建立關鍵字索引表 （ a） 書目如下 （ b）關鍵詞索引表 書號 書名 關鍵詞 書號索引 005 計算機數(shù)據(jù)結構 分析 03 050、 067 010 數(shù)據(jù)結構導論 基礎 023 023 數(shù)據(jù)結構基礎 結構 00 0 023 034 計算機算法設計及分析 計算機 00 034 050 數(shù)值分析簡介 設計 034 067 數(shù)值分析 數(shù)據(jù) 00 0 023 算法 034 數(shù)值 050、 067 下一頁 上一頁 停止放映 第 76/89 頁 四、數(shù)組（ Array） 數(shù)組的定義 數(shù)組的存儲結構 特殊矩陣的存儲及管理 數(shù)組的操作 下一頁 上一頁 停止放映 第 77/89 頁 數(shù)組的定義 數(shù)組是相同類型數(shù)據(jù)元素的有限集合； 數(shù)組中的各個分量稱為數(shù)組元素； 每個數(shù)組元素值可以用數(shù)組名和一個下標值唯一的確定； 下一頁 上一頁 停止放映 第 78/89 頁 數(shù)組的邏輯結構的形式定義 二維數(shù)組 2_Array=(D,R) D 是某種數(shù)據(jù)類型的有限元素集合 ,且 D={ aij|i=c1,d1,j=c2,d2,aij ?D0 } R是行、列關系的有限集合，且 R={ ROW ， COL }，又 ROW={aij,aij+1|c1?i?d1,c2?j?d21,aij,aij+1?D0} COL={aij,ai+1j|c1?i?d11,c2?j?d2,aij,ai+1j?D0} ci 是第 i維的下界 dj 是第 j維的上界 兩維數(shù)組的元素個數(shù)為 : (d1c1+1)*(d2c2+1) 下一頁 上一頁 停止放映 第 79/89 頁 N維數(shù)組的邏輯結構的形式定義 N維數(shù)組 n_Array=( D , R ) ji=ci， di， i=1， 2， … n D = aj1j2… jn| aj1… jn ? D0 R={ R1 ,R2， … Rn }，又 ck?jk?dk 1 ? k ?n , ik Ri= aj1… jn,aj1,… ji+1… jn| ci?ji?di1 aj1… ji… jn ? D0 N維數(shù)組的元素個數(shù)為 : (d1c1+1)*(d2c2+1)*… .(dn+1) = ? (dici+1) n i =1 下一頁 上一頁 停止放映 第 80/89 頁 數(shù)組元素之間的關系 二維數(shù)組 m行 n列可以看作是 m個或 n個一維數(shù)組 : Amxn = ((a11a12… a1n),(a21a22… a2n),.. (am1am2… amn)) 或 : a11 a12 a1n a21 a22 a2n Amxn = am1 am2 amn ... ... ... ... 下一頁 上一頁 停止放映 第 81/89 頁 數(shù)組的操作 數(shù)組有兩種基本的操作： – 給定下標，存取相應的數(shù)組元素； – 給定下標，修改相應數(shù)組元素的值。 – 在實際系統(tǒng)中，按圖書名檢索并不實用。 ? E L S E k : = i ? E N D 。 100 PROCEDURE P； ? 110 VAR i， j， k： REAL； ? 120 BEGIN ? 130 READ（ i， j）； ? 140 IF ij THEN k:=j? 150 ELSE k:=i? 160 END； ? 下一頁 上一頁 停止放映 第 71/89 頁 文本編輯（二） 241 201 221 261 281 P R O C E D U R E P 。 建立頁表、行表的存儲映象表。 定義一個很大的連續(xù)空間和相應的指針結構。特點： – 尋址快 – 浪費空間，存儲密度低。 S = REPLACE（ S， ’ （ XYZ） ’ ， ’ （ X+Z）‘ ） S1 = SUBSTR(S,1,5) S1 = CONCAT（ S1， SUBSTR（ S， 7， 1）） T = CONCAT（ S1， SUBSTR（ S， 3， 1）） 下一頁 上一頁 停止放映 第 64/89 頁 串的存儲結構 （ 1）順序存儲結構 – 緊縮存儲 – 非緊縮存儲 （ 2）鏈表存儲結構 – 緊縮存儲 – 非緊縮存儲 （ 3）堆結構 下一頁 上一頁 停止放映 第 65/89 頁 串的順序存儲結構 有些計算機采用的字編址方式，即數(shù)組元素的分量占 4個字節(jié)。 DATE=?20?+SUBSTR（ ’ 03/07/00?， 7， 2） +?年 ‘ CONCAT（ S1， S2）聯(lián)接 S1和 S2，組成一個新串 S=CONCAT（ ’ Str?， ’ ing?） INDEX（ S1， S2） 確定 S2在 S1中的位置。 串中任意個連續(xù)字符組成的字符子序列稱為子串 。 if (tnext = = NULL ) rear = front。 exit(1) 。 為 1,則修改頭、尾指針； step3 釋放 T。 下一頁 上一頁 停止放映 第 57/89 頁 鏈隊列的出隊操作 算法 115描述 : step1 判別隊列是否為空 。 t next = NULL 。 exit(1)。 step3 非空 ,將 T插入鏈中 ,修改 rear指針。 存儲結構的 C語言描述， struct qnode { int data ； struct qnode * next； } ； typedef struct qnode QNODE ； QNODE *front， *rear； data next 數(shù)據(jù)域 指針域 下一頁 上一頁 停止放映 第 52/89 頁 鏈隊列為空的表示 鏈隊列為空 = 表示形式： front rear ^ front rear ^ ... an a2 a1 非空隊列 下一頁 上一頁 停止放映 第 53/89 頁 鏈隊列為滿的條件 鏈滿的條件為 : T = NULL T 為新創(chuàng)建的結點 ,當沒有存儲空間時 ,T為 NULL,表示鏈隊列已滿。 step2 隊頭指針后移一個位置。 } else { rear = rear % MAXSIZE +1。 循環(huán)隊列在指針移動處理時與一般隊列不同： 下一頁 上一頁 停止放映 第 46/89