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

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

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

4、題)三維數組A4 5按行優先存儲方法存儲在內存 中，假設每個元素占2個存儲單元，且數組中第一個元素的存儲地址為 120 ,那么元素A345的存儲地址為()。A . 356B . 358C . 360D . 362隱藏答案【答案】B【解析】A45表示它共有4片，每片有5行，每行有6個元 素。元素A345處在3片4行5列上,是三維數組的最后一個元 素。按行優先存儲方法存儲時，它前面有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三、數組運算舉例【例】設計一個算法，實現矩陣Amn的轉置矩陣Bnm0【分析】對于一個mxn的矩陣A,其轉置矩陣是一個nxm的矩陣B ,而且, 0in-l , 0jm-lo 假設 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列元素中最大值，那么稱此元素為該矩 陣的一個馬鞍點。假設以二維數組存儲矩陣Am x n ,試編寫求出矩陣 中所有馬鞍點的算法。【分析】算法思想：先求出每行中的最小值元素，存入數組Minm之中，再求出每列的最大值元素，存入數組Maxn之中。假設某 元素既在Mini中又在Max。中，那么該元素就是馬鞍點，找出 所有這樣元素。【算法描述】void MaxMin(int A45 , int m , int n) int i , j ;int Max5 , Min4;for(i=O ; im ; i+)計算每行的最小值元素，存入Min數組中 Mi

7、ni=AiO;先假設第i行第一個元素最小，然后再與后面的元素比擬for(j = l; jn ; j + +) if(AijMini) Mini=Aig;)for(j=0 ; jn ; j + +)計算每列的最大值元素，存入Max數組中 Maxj=AOj;假設第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),將其按行優先存于一維數組A中，給出執行函數調用f30(A , 3)后矩陣B的值；(2)簡述函數f30的功能。隱藏答案【解析】矩陣B存儲在一維數組A中的初始狀態如下圖數組AA0 Al A2A3A4A5A6A7A81456789循環過程函數執行完后，數組A的狀態如以下圖外層循環內層