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

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

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

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

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

5、6+4*6+5個元素，每個元素占2個存儲單元。所以，元素A34的存儲地址為:loc(A345) = loc(A000 + (3*5 *6+ 4*6+5) *2=120+238=358三、數(shù)組運算舉例【例】設(shè)計一個算法，實現(xiàn)矩陣Amn的轉(zhuǎn)置矩陣Bnm0【分析】對于一個mxn的矩陣A,其轉(zhuǎn)置矩陣是一個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、在這樣的一個元素,滿足：是 第i行元素中最小值，且又是第j列元素中最大值，那么稱此元素為該矩 陣的一個馬鞍點。假設(shè)以二維數(shù)組存儲矩陣Am x n ,試編寫求出矩陣 中所有馬鞍點的算法。【分析】算法思想：先求出每行中的最小值元素，存入數(shù)組Minm之中，再求出每列的最大值元素，存入數(shù)組Maxn之中。假設(shè)某 元素既在Mini中又在Max。中，那么該元素就是馬鞍點，找出 所有這樣元素?！舅惴枋觥縱oid MaxMin(int A45 , int m , int n) int i , j ;int Max5 , Min4;for(i=O ; im ; i+)計算每行的最小值元素，存入Min數(shù)組中 Mi

7、ni=AiO;先假設(shè)第i行第一個元素最小，然后再與后面的元素比擬for(j = l; jn ; j + +) if(AijMini) Mini=Aig;)for(j=0 ; jn ; j + +)計算每列的最大值元素，存入Max數(shù)組中 Maxj=AOj;假設(shè)第j列第一個元素最大，然后再與后面的元素比擬for(i=l; iMaxj)Maxg=Aij;)for(i=0;im; i + +)for(j=0;jn;j + +)if(Mini = = Maxj)判斷是否為馬鞍點pnntf(%dz%d, ij);顯示馬鞍點【真題選解】(例題算法閱讀題)閱讀以下程序。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)簡述函數(shù)f30的功能。隱藏答案【解析】矩陣B存儲在一維數(shù)組A中的初始狀態(tài)如下圖數(shù)組AA0 Al A2A3A4A5A6A7A81456789循環(huán)過程函數(shù)執(zhí)行完后，數(shù)組A的狀態(tài)如以下圖外層循環(huán)內(nèi)層