大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第四章：多維數(shù)組和廣義表-第一節(jié)-多維數(shù)組和運(yùn)算

1、本章概覽當(dāng)前講授一.知識(shí)結(jié)構(gòu)C多維數(shù)組的定義多維數(shù)組 多維數(shù)組的順序存儲(chǔ)對(duì)稱矩陣矩陣的壓縮存儲(chǔ)1三角矩陣多維數(shù)組J稀疏矩陣和廣義表r廣義表的定義 主 J 廣義表基本運(yùn)算（X不r工廣義表的存儲(chǔ)結(jié)構(gòu)I廣義表基本運(yùn)算的實(shí)現(xiàn)（略講）二、本章重難點(diǎn)本要求考生熟悉數(shù)組在按行優(yōu)先順序的存儲(chǔ)結(jié)構(gòu)中元素地址的計(jì)算 方法；熟悉特殊矩陣在壓縮存儲(chǔ)時(shí)的下標(biāo)變換方法；理解稀疏矩陣的 三元組表存儲(chǔ)表示方法及有關(guān)算法；熟悉廣義表的有關(guān)概念，理解廣 義表的括號(hào)表示和圖形表示；掌握廣義表的求表頭和表尾的運(yùn)算。本章重點(diǎn)是多維數(shù)組的存儲(chǔ)方式、矩陣的壓縮存儲(chǔ)、廣義表的表頭 和表尾的求解；難點(diǎn)是壓縮存儲(chǔ)特殊矩陣和稀疏矩陣的各種運(yùn)算及應(yīng)

2、 用。第一節(jié)多維數(shù)組和運(yùn)算當(dāng)前講授一、多維數(shù)組的定義1、一維數(shù)組是一種元素個(gè)數(shù)固定的線性表。2、多維數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，可以看成是線性表的推廣，一個(gè)n維數(shù)組 可視為其數(shù)據(jù)元素為n-1維數(shù)組的線性表。二、數(shù)組的順序存儲(chǔ)通常采用順序存儲(chǔ)結(jié)構(gòu)來存放數(shù)組。對(duì)二維數(shù)組可有兩種存儲(chǔ)方 法：一種是以行序?yàn)橹餍虻拇鎯?chǔ)方式，另一種是以列序?yàn)橹餍虻拇鎯?chǔ) 方式。在C語言中，采用以行為主序存儲(chǔ)。（1）對(duì)于C語言的二維數(shù)組Amn,下標(biāo)從0開始，假設(shè)一個(gè)數(shù)組元素占數(shù)組元素占d個(gè)存儲(chǔ)單元，那么二維數(shù)組中任數(shù)組元素占d個(gè)存儲(chǔ)單元，數(shù)組元素占d個(gè)存儲(chǔ)單元，那么二維數(shù)組中任元素的存儲(chǔ)位置loc(Aij) = loc(A00

3、)+(i *n + j) * d【真題選解】（例題單項(xiàng)選擇題）二維數(shù)組A4 5按行優(yōu)先順序存儲(chǔ)，假設(shè)每個(gè)元素 占2個(gè)存儲(chǔ)單元，且第一個(gè)元素A的存儲(chǔ)地址為1000 ,那么數(shù)組 元素A32的存儲(chǔ)地址為（）A . 1012B . 1017C . 1034D . 1036隱藏答案【答案】C【解析】loc(A32) = loc(A00) + (3 *5 + 2) * 2=1000+34=1034(2 )對(duì)于C語言的三維數(shù)組Amnp,下標(biāo)從0開始，假設(shè)一 個(gè)數(shù)組元素占d個(gè)存儲(chǔ)單元，那么三維數(shù)組中任一元素的存儲(chǔ)loc(Aijk) = loc(A000 + (i *n *p+j*p+k) * d(例題單項(xiàng)選擇

4、題)三維數(shù)組A4 5按行優(yōu)先存儲(chǔ)方法存儲(chǔ)在內(nèi)存 中，假設(shè)每個(gè)元素占2個(gè)存儲(chǔ)單元，且數(shù)組中第一個(gè)元素的存儲(chǔ)地址為 120 ,那么元素A345的存儲(chǔ)地址為()。A . 356B . 358C . 360D . 362隱藏答案【答案】B【解析】A45表示它共有4片，每片有5行，每行有6個(gè)元 素。元素A345處在3片4行5列上,是三維數(shù)組的最后一個(gè)元 素。按行優(yōu)先存儲(chǔ)方法存儲(chǔ)時(shí)，它前面有3個(gè)完整的片，每片有5*6 個(gè)元素，3片有3*5*6個(gè)元素；在它所在片的4行之前，有4個(gè)完整 的行，每行有6個(gè)元素，因此它所在片所在行之前有4*6個(gè)元素；在 它所在行所在列之前還有5個(gè)元素。因此，在它之前總共有3*5*

5、6+4*6+5個(gè)元素，每個(gè)元素占2個(gè)存儲(chǔ)單元。所以，元素A34的存儲(chǔ)地址為:loc(A345) = loc(A000 + (3*5 *6+ 4*6+5) *2=120+238=358三、數(shù)組運(yùn)算舉例【例】設(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)矩陣Amn的轉(zhuǎn)置矩陣Bnm0【分析】對(duì)于一個(gè)mxn的矩陣A,其轉(zhuǎn)置矩陣是一個(gè)nxm的矩陣B ,而且, 0in-l , 0jm-lo 假設(shè) m=5 , , n=8e【算法描述】void trsmat(int a8 , int b5 , int m , int n) int i J;for(j=O;jm;j + +)for(i=0;in;i+)bij=aji;【例】如果矩陣A中存

6、在這樣的一個(gè)元素,滿足：是 第i行元素中最小值，且又是第j列元素中最大值，那么稱此元素為該矩 陣的一個(gè)馬鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ)矩陣Am x n ,試編寫求出矩陣 中所有馬鞍點(diǎn)的算法。【分析】算法思想：先求出每行中的最小值元素，存入數(shù)組Minm之中，再求出每列的最大值元素，存入數(shù)組Maxn之中。假設(shè)某 元素既在Mini中又在Max。中，那么該元素就是馬鞍點(diǎn)，找出 所有這樣元素?！舅惴枋觥縱oid MaxMin(int A45 , int m , int n) int i , j ;int Max5 , Min4;for(i=O ; im ; i+)計(jì)算每行的最小值元素，存入Min數(shù)組中 Mi

7、ni=AiO;先假設(shè)第i行第一個(gè)元素最小，然后再與后面的元素比擬for(j = l; jn ; j + +) if(AijMini) Mini=Aig;)for(j=0 ; jn ; j + +)計(jì)算每列的最大值元素，存入Max數(shù)組中 Maxj=AOj;假設(shè)第j列第一個(gè)元素最大，然后再與后面的元素比擬for(i=l; iMaxj)Maxg=Aij;)for(i=0;im; i + +)for(j=0;jn;j + +)if(Mini = = Maxj)判斷是否為馬鞍點(diǎn)pnntf(%dz%d, ij);顯示馬鞍點(diǎn)【真題選解】(例題算法閱讀題)閱讀以下程序。void f3O(int A , int n) intfor(i = l ; in ; i + +)for(j=0 ; ji ; j + +) m=Ai*n+j ; Ai*n+j與 An + i值交換Ai*n+j=Aj*n + i;Aj*n + i = m ;)回答以下問題：T23、B= 456(1)矩陣1789),將其按行優(yōu)先存于一維數(shù)組A中，給出執(zhí)行函數(shù)調(diào)用f30(A , 3)后矩陣B的值；(2)簡(jiǎn)述函數(shù)f30的功能。隱藏答案【解析】矩陣B存儲(chǔ)在一維數(shù)組A中的初始狀態(tài)如下圖數(shù)組AA0 Al A2A3A4A5A6A7A81456789循環(huán)過程函數(shù)執(zhí)行完后，數(shù)組A的狀態(tài)如以下圖外層循環(huán)內(nèi)層