第3單元線性數(shù)據(jù)結(jié)構(gòu)二-wenkub.com
2025-07-17 10:04 本頁(yè)面
【正文】 – 假設(shè)以數(shù)組 sequ[m1]存放循環(huán)隊(duì)列的元素，設(shè)變量 rear和 quelen分別為指示隊(duì)尾元素位置和隊(duì)中元素個(gè)數(shù)，試寫出入隊(duì)和出隊(duì)算法。 ? Aij在一維數(shù)組中的地址為： ? i（ i1） /2+j 當(dāng) i?j ? LOC(aij) = ? j（ j1） /2+i 當(dāng) ij 51/53 對(duì)稱矩陣的壓縮存儲(chǔ) ? 設(shè)有 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(21)/2+2= 3 – LOC(a21)=2(21)/2+1= 2 52/53 ? 常見(jiàn)的特殊矩陣 : –對(duì)稱矩陣 存儲(chǔ)主對(duì)角線以上 (下 )的元素 –上 (下 )三角矩陣 只存儲(chǔ)三角陣元素； –帶狀矩陣 只存儲(chǔ)帶狀元素； ? (2) 稀疏矩陣的壓縮存儲(chǔ) – 利用三元組只存儲(chǔ)非零元素； – 三元組 : (i,j,aij) 53/53 作業(yè)、思考題 ? 思考題： – 試寫出“在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中求表長(zhǎng)的算法”。 ? 數(shù)組中的每個(gè)元素由元素的兩個(gè)下標(biāo)表達(dá)式唯一的確定。 –指針用來(lái)指示串在堆中的位置 –例如， a=?BEI?， b=? JING?， c=??，d=?SHANGHAI?； 串名串長(zhǎng) 起始地址 a 3 1 b 5 4 c 0 9 d 8 9 B E I J I N G S H A N G H A I 43/53 三 .數(shù)組 ? 數(shù)組的定義 ? 數(shù)組是有限個(gè)數(shù)組元素的集合 ? 數(shù)組中所有元素有相同的數(shù)據(jù)類型 ? 每個(gè)數(shù)組元素值可以用數(shù)組名和一組下標(biāo)值唯一的確定； 44/53 ? m行 n列二維數(shù)組可以看作是 m個(gè)或 n個(gè)一維數(shù)組 : – Amxn = ((a11a12…a1n),(a21a22…a2n),.. – (am1am2…amn)) – 或 : a11 a12 a1n – a21 a22 a2n ? Amxn = – am1 am2 amn ... ... ... ... 45/53 ? 兩種基本的操作： –給定下標(biāo)，存取相應(yīng)的數(shù)組元素； –給定下標(biāo)，修改相應(yīng)數(shù)組元素的值。 –隊(duì)列長(zhǎng)度大于 1,只修改頭結(jié)點(diǎn)指針域 an NULL front rear Queue Queue front rear NULL an ^ T Queue Queue front rear rear front a1 an NULL a1 a2 ... a2 ^ ... an NULL 36/53 棧的應(yīng)用 例 1: 遞歸過(guò)程 ? 計(jì)算 5的階乘（ 5!=5 4 3 2 1） – { if ( n = = 1) return (1)。 rear = t。 ? t = (QNODE*)malloc(sizeof(QNODE))。 ? step2 判別 T是否為 NULL。若空 ,則顯示‘下溢’ 。 else rear=rear+1。 ? 解決方法 – 1) 整個(gè)隊(duì)列左移 ,費(fèi)時(shí) – 2) 隊(duì)列的首尾相連 循環(huán)隊(duì)列 ? 目的 –隊(duì)列中真正沒(méi)有空位置時(shí)，才產(chǎn)生溢出。 ? rear：隊(duì)尾指針 。 ? } 20/53 三、隊(duì)列 ? 1. 隊(duì)列概念 – 1) 只允許在表的一端進(jìn)行刪除操作，在表的另一端進(jìn)行插入的特殊線性表。 } ? else
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1