上一篇中，我們布置了一道關(guān)于二維數(shù)組使用的練習(xí)題堕担。大家做的都不錯(cuò)介褥，我們今天來仔細(xì)分析一下這道題目座掘，看看有沒有你沒有掌握的知識(shí)點(diǎn)。
1. 題目
給出任意一個(gè)N * N的矩陣柔滔，將里面的數(shù)字按照從左上到右下由小到大排序溢陪，之后計(jì)算出新矩陣對(duì)角線上的數(shù)字總和（每個(gè)位置只參與一次計(jì)算）。例如：
給出左邊這個(gè)矩陣睛廊，先把它轉(zhuǎn)換成右邊的矩陣形真，之后計(jì)算對(duì)角線上的數(shù)字之和：1 + 5 + 9 + 3 + 7 = 25
2. 分析
首先，這道題給出的是“任意一個(gè)N * N的矩陣”超全，我故意沒有具體定義咆霜，就是希望大家自己設(shè)計(jì)數(shù)據(jù)的輸入方式。大部分人都使用了從鍵盤輸入的方式嘶朱，這樣是最靈活的蛾坯。不過，每次Debug都要從鍵盤輸入那么多數(shù)字還是挺麻煩的疏遏。有另外一種辦法是把需要調(diào)試的數(shù)據(jù)寫在一個(gè)文本文件里脉课，通過程序讀入數(shù)據(jù)再計(jì)算救军。學(xué)到文件處理的同學(xué)可以自己試試，這不在我們今天要討論的范圍內(nèi)倘零。
按照從易到難的原則唱遭，我們先把這道題簡化成一個(gè)特定的矩陣（圖中的矩陣）來設(shè)計(jì)程序。現(xiàn)在我們來對(duì)這個(gè)程序做功能分解呈驶。
2.1 數(shù)據(jù)結(jié)構(gòu)
作為一門課程“數(shù)據(jù)結(jié)構(gòu)”被妖魔化了很多年拷泽，所有學(xué)計(jì)算機(jī)的孩子都在沒開始學(xué)的時(shí)候就被嚇到了。從本質(zhì)上講袖瞻，數(shù)據(jù)結(jié)構(gòu)就是存儲(chǔ)數(shù)據(jù)的一些復(fù)雜的數(shù)據(jù)類型而已跌穗。這道題既然涉及矩陣，那一定會(huì)用到二維數(shù)組虏辫。
2.2 二維數(shù)組的打印
雖然題目中并沒有要求大家打印這個(gè)矩陣蚌吸，但在實(shí)際編程和Debug過程中，我們需要通過打印來查看自己每個(gè)子功能的實(shí)現(xiàn)是否正確砌庄，因此需要打印羹唠。
打印二維數(shù)組是教科書上的例題，相信大家一定會(huì)寫娄昆。如果不會(huì)佩微，快去百度。
2.3 排序
排序算法我們學(xué)過很多萌焰，最有名的就是冒泡排序哺眯。不過對(duì)于這個(gè)二維數(shù)組鼠冕，好像冒泡不是很合適述雾。沒關(guān)系，我們會(huì)找到辦法的存炮。
2.4 計(jì)算對(duì)角線
這是對(duì)二維數(shù)組的一種具體的使用方法撼玄。大家肯定會(huì)夺姑，只不過我們要找到一個(gè)相對(duì)簡單的方法就要多思考一下了。
目前掌猛，通過我們的分析盏浙，這個(gè)程序就涉及這幾個(gè)子功能。下面我們來具體實(shí)現(xiàn)它們荔茬。
今天我們要使用一種“搭積木”的方式來完成這個(gè)程序废膘。具體就是把每個(gè)子功能通過一個(gè)函數(shù)來實(shí)現(xiàn)，之后通過函數(shù)調(diào)用把這些子功能拼在一起完成整個(gè)程序的功能慕蔚。
3. 二維數(shù)組的打印
首先我們要定義一個(gè)固定大小的二維數(shù)組丐黄，我們使用一個(gè)全局變量來實(shí)現(xiàn)。
#define SIZE 3
int g_arr[SIZE][SIZE] =
{ 3, 4, 9,
6, 2, 7,
5, 1, 8
};
這個(gè)二維數(shù)組中的數(shù)據(jù)就是題目中給出的那個(gè)例子坊萝。接下來我們定義一個(gè)打印二維數(shù)組的函數(shù)孵稽。
void PrintfMatrix(int arr[][SIZE])
{
int i, j;
for (i = 0; i < SIZE; i++)
{
for (j = 0; j < SIZE; j++)
{
printf("%5d", arr[i][j]);
}
printf("\n");
}
}
這段代碼應(yīng)該不用解釋了许起，唯一要說的就是二維數(shù)組的傳參形式十偶。由于不能通過數(shù)組名知道二維數(shù)組的行數(shù)和列數(shù)菩鲜，因此需要通過列數(shù)來規(guī)定數(shù)組的形式。
注意惦积，形參arr并沒有開辟新的空間接校，而是使用形參提供的內(nèi)存空間。
4. 冒泡排序
幾乎所有人都會(huì)寫冒泡排序狮崩，對(duì)于這個(gè)題目蛛勉，這個(gè)簡單的排序方法完全夠用。很多人的難點(diǎn)都是如何對(duì)二維數(shù)組排序睦柴，有人寫了非常復(fù)雜的嵌套循環(huán)诽凌。這里我們先定義一個(gè)自己熟悉的一維數(shù)組排序函數(shù)。
void Sort(int* pArr, int num)
{
int t;
for (int i = 0; i < num - 1; i++)
{
for (int j = i + 1; j < num; j++)
{
if (pArr[i] > pArr[j])
{
t = pArr[i];
pArr[i] = pArr[j];
pArr[j] = t;
}
}
}
}
這里設(shè)計(jì)參數(shù)時(shí)用了指針坦敌，目的是為了使用實(shí)參的地址侣诵。我又要提一次指針和數(shù)組的關(guān)系了，之前的系列里反復(fù)強(qiáng)調(diào)的他倆是一回事狱窘，使用過程中可以相互替換的杜顺，不清楚的可以參考21天C語言代碼訓(xùn)練營（第四天）。指針變量pArr可以當(dāng)做數(shù)組名去使用蘸炸，pArr[i]其實(shí)就相當(dāng)于*(pArr + i)躬络。
如果你還沒有學(xué)到指針，沒關(guān)系搭儒，把函數(shù)聲明改成這樣就行：
void Sort(int pArr[], int num)
其它部分不需要任何修改穷当。這部分不細(xì)說了，如果有誰還不清楚我們可以在微信群里繼續(xù)討論淹禾。
最后的問題就是一維數(shù)組的排序函數(shù)跟我們的二維數(shù)組有什么關(guān)系呢膘滨，一會(huì)兒再說。
5. 計(jì)算對(duì)角線
寫這篇文章時(shí)只有兩個(gè)人提交了代碼稀拐，我們就用他們的代碼作為參考火邓。
5.1 算法一
先看一下Aha_斌寫的計(jì)算對(duì)角線之和的函數(shù)：
int countMatrix()//計(jì)算矩陣對(duì)角線之和
{
int result = 0;
int i, j;
for (i = 0; i < g_matrixSize; i++)
{
for (j = 0; j < g_matrixSize; j++)
{
if (i == j || i + j == g_matrixSize - 1)
{
result = g_arry[i][j] + result;
}
}
}
return result;
}
這個(gè)函數(shù)在功能上沒有任何問題，它的邏輯有兩部分：
- 遍歷二維數(shù)組德撬，通過嵌套for循環(huán)完成
- 判斷每個(gè)元素是否在對(duì)角線上铲咨，如果是就做累加
這個(gè)算法最大的好處是每個(gè)元素只訪問一次，不會(huì)出現(xiàn)分別計(jì)算對(duì)角線時(shí)會(huì)有相交位置的重復(fù)計(jì)算蜓洪。
這段代碼寫的也比較規(guī)整纤勒，風(fēng)格統(tǒng)一，變量命名規(guī)范隆檀。邏輯結(jié)構(gòu)設(shè)計(jì)的也比較合理摇天。有個(gè)別問題需要注意：
result = g_arry[i][j] + result;
最好寫成
result += g_arry[i][j];
另外粹湃，不在對(duì)角線上的元素訪問可以省略掉。
5.2 算法二
再看看滿天星55的實(shí)現(xiàn)方法泉坐。
//計(jì)算對(duì)角線之和
for(i=0;i<N;i++)
sum+=b[i][i]+b[i][N-1-i];
if(N%2==1)
sum-=b[N/2][N/2];
printf("對(duì)角線之和為 %d\n",sum);
這個(gè)算法看起來比簡短为鳄，通過一個(gè)循環(huán)遍歷了全部位于對(duì)角線上的元素。其中有個(gè)特殊情況就是當(dāng)行數(shù)為奇數(shù)時(shí)腕让，正中間的元素會(huì)被重復(fù)計(jì)算一次孤钦，因此要用一個(gè)if語句把它減去。邏輯清晰纯丸，考慮的也比較全面偏形。
從代碼風(fēng)格的角度來說，這段代碼不如上一段Aha_斌的代碼清晰觉鼻。因?yàn)樗鄙倭嗽撚械目崭窨∨ぁＴ赩S中，IDE會(huì)自動(dòng)幫你加上一些空格坠陈，目的是讓代碼讀起來更清晰萨惑。也許滿天星55并不覺得看著有什么不舒服，但還是建議你養(yǎng)成加入空格的習(xí)慣畅姊。
另外需要格外強(qiáng)調(diào)的是咒钟，if和for這種關(guān)鍵字，當(dāng)內(nèi)部代碼塊中只有一行代碼時(shí)若未，雖然可以省略大括號(hào)朱嘴，但我建議大家依然寫上。原因我在之前的文章里說過了粗合，這里就不贅述了萍嬉。如果滿天星55不明白，可以在微信群里交流隙疚。
5.3 算法三
前兩種方法中壤追，我個(gè)人更喜歡第二種，我做了一點(diǎn)點(diǎn)修改供屉。
int CalculateSum(int arr[][SIZE])
{
int sum = 0;
for (int i = 0; i < SIZE; i++)
{
sum += arr[i][i];
arr[i][i] = 0;
sum += arr[i][SIZE - 1 - i];
}
return sum;
}
依然是用一個(gè)循環(huán)遍歷兩條對(duì)角線行冰，唯一的不同是我在第一次訪問之后把一條對(duì)角線的值修改成0，這樣在第二條對(duì)角線訪問到重復(fù)元素時(shí)并不會(huì)影響最終的結(jié)果伶丐。
這里要注意悼做，我用了傳參的方式把二維數(shù)組傳入CalculateSum()函數(shù)中，并沒有使用全局變量哗魂。這也是代碼解耦的重要思想之一肛走，盡可能地少用全局變量。
6. 一維數(shù)組和二維數(shù)組
首先录别，我們要知道對(duì)于計(jì)算機(jī)而言朽色，二維數(shù)組在內(nèi)存中的形式是什么邻吞。如下圖：
通過這張圖我們可以看出，二維數(shù)組在內(nèi)存中也是一塊連續(xù)的區(qū)域葫男。這和一維數(shù)組完全相同抱冷。無論是一維數(shù)組還是二維數(shù)組，它們的數(shù)組名都表示了這塊內(nèi)存區(qū)域中第一個(gè)元素的地址腾誉。
于是徘层，我們現(xiàn)在就可以利用前面寫的對(duì)一維數(shù)組排序的函數(shù)對(duì)二維數(shù)組g_arr進(jìn)行排序了：
Sort((int*)g_arr, SIZE * SIZE);
注意：這里的g_arr需要強(qiáng)制類型轉(zhuǎn)換成指針才能正確賦值峻呕。
7. 功能整合
最后就是搭積木的最后一步了利职，在main函數(shù)中把子功能整合在一起。
int main()
{
int ret;
printf("原始矩陣：\n");
PrintfMatrix(g_arr);
Sort((int*)g_arr, SIZE * SIZE);
printf("排序后矩陣：\n");
PrintfMatrix(g_arr);
printf("對(duì)角線之和：\n");
ret = CalculateSum(g_arr);
printf("%d\n", ret);
}
執(zhí)行結(jié)果如下：
8. 動(dòng)態(tài)二維數(shù)組
肯定有人要問瘦癌，如果需要用一組空間保存大小不固定的二維數(shù)組怎么辦呢猪贪？辦法有很多。
8.1 固定大空間
由于每次二維數(shù)組需要的空間不同讯私，所以要有足夠的空間热押。簡單的方案是在棧空間中定義一個(gè)足夠大的二維數(shù)組斤寇。
#define MAX_SIZE 100
int g_arr[MAX_SIZE][MAX_SIZE];
這么做有兩個(gè)問題：
首先桶癣，MAX_SIZE畢竟是一個(gè)有限的數(shù)字，缺乏靈活性娘锁。另外牙寞，這樣每次使用的都是這個(gè)巨大二維數(shù)組的一部分，它的空間不是連續(xù)的莫秆，因此不能用一維數(shù)組的方式進(jìn)行排序间雀。
8.2 動(dòng)態(tài)申請(qǐng)空間
根據(jù)需要?jiǎng)討B(tài)地從堆中申請(qǐng)需要的空間。一維數(shù)組的動(dòng)態(tài)申請(qǐng)大家一定都會(huì)：
#define SIZE 10
int* p = (int*)malloc(SIZE * SIZE * sizeof(int));
這樣申請(qǐng)出的空間是連續(xù)的镊屎，把它當(dāng)二維數(shù)組使用就可以實(shí)現(xiàn)需要的功能惹挟。
注意：malloc申請(qǐng)的空間在程序結(jié)束前一定要用free函數(shù)釋放。
8.3 動(dòng)態(tài)申請(qǐng)二維數(shù)組
二維數(shù)組的動(dòng)態(tài)申請(qǐng)相對(duì)復(fù)雜一些：
#define SIZE 10
int** p = (int **)malloc(SIZE * sizeof(int *));
if (NULL == p)
{
return;
}
for (i = 0; i < SIZE; i++)
{
*(p + i) = (int*)malloc(SIZE * sizeof(int));
}
這種方式相對(duì)復(fù)雜一些缝驳，并不常用连锯。
以上幾種方式有興趣的同學(xué)可以自己去試試，在練習(xí)的過程中你會(huì)發(fā)現(xiàn)更多有意思的東西用狱。歡迎隨時(shí)在微信群里討論运怖。
9. 課后作業(yè)
如圖所示，有一個(gè)6 * 6的迷宮齿拂，左上角為入口驳规，右下角為出口。圖中0的位置可以走署海，1的位置不能走吗购。請(qǐng)編程找出唯一的一條通過迷宮的路医男。
我是天花板，讓我們一起在軟件開發(fā)中自我迭代捻勉。
如有任何問題镀梭，歡迎與我聯(lián)系。
