基于數(shù)的數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)

張秀梅 王賀 楊陽(yáng)

摘? 要：“數(shù)據(jù)結(jié)構(gòu)”是軟件工程專業(yè)的核心專業(yè)基礎(chǔ)課，通過(guò)學(xué)習(xí)培養(yǎng)學(xué)生能夠分析數(shù)據(jù)對(duì)象特征，根據(jù)問(wèn)題的需要，確定邏輯結(jié)構(gòu)并選擇合適的存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)典型算法設(shè)計(jì)及性能分析的能力。針對(duì)數(shù)據(jù)結(jié)構(gòu)抽象性比較強(qiáng)的特點(diǎn)，文章采用對(duì)數(shù)的認(rèn)識(shí)逐步遞進(jìn)的方式進(jìn)行相關(guān)算法設(shè)計(jì)，不僅可以提升課程教學(xué)效率及質(zhì)量，而且有利于提高學(xué)生學(xué)習(xí)的主動(dòng)性和創(chuàng)新性。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);素?cái)?shù);素?cái)?shù)環(huán);魔方陣;數(shù)獨(dú)

中圖分類號(hào)：TP311.1? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）07-0024-03

Design of Data Structure Algorithm Based on Number

ZHANG Xiumei，WANG He，YANG Yang

（School of Computer Science and Software Engineering，University of Science and Technology Liaoning，Anshan? 114051，China）

Abstract：“Data Structure” is the core professional basic course of software engineering major，through learning to train students to be able to analyze the characteristics of data objects，according to the needs of the problem，determine the logical structure and choose the appropriate storage structure，to achieve the ability of typical algorithm design and performance analysis. In view of the characteristics of abstract data structure，this paper adopts the logarithmic method to design the relevant algorithm step by step，which can not only improve the teaching efficiency and quality，but also improve the initiative and innovation of students.

Keywords：data structure;prime number;prime ring;magic square;Sudoku

0? 引? 言

“數(shù)據(jù)結(jié)構(gòu)”作為計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課程，是計(jì)算機(jī)考研的必考科目之一，是計(jì)算機(jī)軟件水平考試、計(jì)算機(jī)等級(jí)考試等相關(guān)考試的必考內(nèi)容之一，還是“操作系統(tǒng)”“編譯原理”“數(shù)據(jù)庫(kù)”“軟件工程”“人工智能”等其他課程的基礎(chǔ)?！皵?shù)據(jù)結(jié)構(gòu)”課程的教學(xué)內(nèi)容比較多，知識(shí)點(diǎn)相對(duì)分散，目前該課程的教學(xué)活動(dòng)都是按照線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)、查找和排序[1]的順序進(jìn)行，其教學(xué)過(guò)程往往是單向灌輸，沒(méi)有師生間的雙向互動(dòng)，沒(méi)有足夠時(shí)間和空間讓學(xué)生進(jìn)行深層次思考，很少注重學(xué)生思維判斷能力以及分析、解決問(wèn)題能力的培養(yǎng)。同時(shí)，由于前期程序設(shè)計(jì)語(yǔ)言課程掌握得不好，導(dǎo)致學(xué)習(xí)該課程時(shí)感到無(wú)從下手，而且“數(shù)據(jù)結(jié)構(gòu)”內(nèi)容比較枯燥，很難激發(fā)學(xué)生的學(xué)習(xí)熱情[2，3]。鑒于此，在課程教學(xué)中如何選擇適當(dāng)?shù)捻?xiàng)目，既能激發(fā)學(xué)生的學(xué)習(xí)興趣，又能培養(yǎng)學(xué)生的邏輯思維能力，考慮引入現(xiàn)實(shí)中有關(guān)數(shù)的問(wèn)題，以“有趣的數(shù)”開始展開教學(xué)活動(dòng)來(lái)拓展學(xué)生思維，培養(yǎng)了學(xué)生實(shí)際動(dòng)手能力和分析解決問(wèn)題能力，為今后其他課程的學(xué)習(xí)打下良好的基礎(chǔ)。

1? 算法設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)指導(dǎo)著各種程序設(shè)計(jì)語(yǔ)言如何編寫程序，而算法是數(shù)據(jù)結(jié)構(gòu)的靈魂，是貫穿整個(gè)“數(shù)據(jù)結(jié)構(gòu)“課程的主線，如何把生活中的實(shí)際問(wèn)題通過(guò)分析問(wèn)題、建立模型、設(shè)計(jì)算法、編制程序、調(diào)試優(yōu)化等步驟用計(jì)算機(jī)實(shí)現(xiàn)是學(xué)習(xí)該課程的核心所在。而算法的設(shè)計(jì)跟數(shù)學(xué)是分不開的，一個(gè)高效的算法要選取合適的數(shù)據(jù)結(jié)構(gòu)，它們之間是相輔相成的，因此將一些有趣的數(shù)進(jìn)行歸納，并延伸來(lái)設(shè)計(jì)相應(yīng)的算法。

1.1? 簡(jiǎn)單的數(shù)

自然數(shù)有奇數(shù)、偶數(shù)，奇偶的判斷在計(jì)算機(jī)中用模運(yùn)算（%）來(lái)實(shí)現(xiàn)，如何判斷一個(gè)數(shù)是否為素?cái)?shù)（只能被1和自身整除的數(shù)），進(jìn)而引申出：

（1）一個(gè)大于2的偶數(shù)可以表示為兩個(gè)素?cái)?shù)的和，即哥德巴赫猜想;

（2）如果一組整形數(shù)組任何兩個(gè)相鄰元素的和為素?cái)?shù)，并且首尾的和也為素?cái)?shù)，即為素?cái)?shù)環(huán)。

上面的數(shù)據(jù)涉及到的是一個(gè)數(shù)或一行數(shù)據(jù)，接下來(lái)看看工程上應(yīng)用比較多的矩陣，即多行數(shù)據(jù)。數(shù)字填充游戲——魔方陣（幻方），幻方游戲的規(guī)則：將1到n2的數(shù)字組成n*n階方陣，每條對(duì)角線，每行與每列的數(shù)字和都相等，和為n*（n2+1）/2。

根據(jù)n的奇偶性幻方分為：

（1）n為奇數(shù)時(shí)稱為奇幻方;

（2）n為偶數(shù)且是4的倍數(shù)時(shí)稱為雙偶幻方;

（3）n為偶數(shù)且不是4的倍數(shù)時(shí)稱為單偶幻方（圖1為6階幻方）。

單偶幻方算法描述如下：

（1）編寫奇數(shù)幻方，采用“左上行法”，即在當(dāng)前元素的左上角位置填充元素;

（2）將單偶幻方的方格分割成四個(gè)區(qū)間，按照順時(shí)針編號(hào)為A、B、C、D四個(gè)區(qū)間;

（3）每一個(gè)區(qū)間實(shí)現(xiàn)一個(gè)奇數(shù)幻方的填充，填充順序?yàn)锳、D、B、C;

（4）分別將A、D區(qū)間和B、C區(qū)間的指定元素交換：

A， D區(qū)間交換

line是中間行，magic[row][k + m]和magic[n / 2 + row][k + col]互換;

其它行， magic[row][m]和magic[n / 2 + row][col]互換;

B， C區(qū)間交換

magic[col][3 * n / 4 - l]和magic[n / 2 + col][3 * n / 4 - row]交換

1.2? 數(shù)獨(dú)

更進(jìn)一步地對(duì)另一個(gè)益智游戲——數(shù)獨(dú)（如圖2所示為初級(jí)數(shù)獨(dú)）進(jìn)行介紹。數(shù)獨(dú)是由9個(gè)3*3子矩陣組成的9*9矩陣，每個(gè)子矩陣由1～9的數(shù)字組成，且每行每列不能有重復(fù)數(shù)字。該算法需要綜合運(yùn)用表結(jié)構(gòu)來(lái)設(shè)計(jì)，并且采用回溯算法實(shí)現(xiàn)對(duì)重復(fù)元素的判定，回溯法也叫試探法，每次試著往前走，一直走到不通，然后撤回，再重新試探。

算法詳細(xì)描述如下：

（1）如圖2所示，建立一個(gè)9*9整形矩陣作為數(shù)獨(dú)棋盤結(jié)構(gòu)，分割成9個(gè)3*3的小宮格（數(shù)獨(dú)又稱為九宮格），每一個(gè)元素稱為數(shù)格。對(duì)每個(gè)數(shù)格設(shè)計(jì)一個(gè)候選數(shù)列表，里面包含的候選數(shù)為1～9的數(shù)字，對(duì)于已經(jīng)確定的，列表里就只有一個(gè)已知數(shù)，而對(duì)于待填數(shù)格，則將所有可能的候選數(shù)填入;

（2）預(yù)處理查詢候選數(shù)列表每一行、列和宮格查找已知數(shù)和候選數(shù)有沖突的項(xiàng)，并將沖突項(xiàng)從列表移走。繼續(xù)執(zhí)行此過(guò)程修訂列表，直到候選數(shù)列表的值不再變化;

（3）查找包含有最少候選數(shù)的列表，并隨機(jī)選取一個(gè)數(shù)作為正確的數(shù)進(jìn)行猜想。候選數(shù)列表中只有一個(gè)數(shù)字時(shí)為數(shù)格賦值。同時(shí)注意要有標(biāo)識(shí)，以便在后續(xù)的執(zhí)行過(guò)程中如果有回退可以恢復(fù);

（4）在每一次可能的猜測(cè)過(guò)程中，通過(guò)回溯遞歸回到步驟（2）。通過(guò)這種方式，若當(dāng)前情況無(wú)解的時(shí)候回溯，直到所有的候選數(shù)列表有唯一候選數(shù);

（5）當(dāng)所有的猜測(cè)都嘗試之后如果沒(méi)有解，則返回false。相反，如果宮格都被填滿，并且驗(yàn)證通過(guò)，則表示數(shù)獨(dú)謎題有解。

處理相關(guān)單元格核心代碼如下：

bool flag = true;

Cell cell = table[index / 9][ index % 9];

for （inti = 0; i< 9; i++）

{ if （i ！= index / 9） //同列單元格，可以排除兩個(gè)宮格

flag&= cellMethod（table， i， index % 9， index）;

if （i ！= index % 9） //同行單元格，可以排除兩個(gè)宮格

flag&= cellMethod（table， index / 9， i， index）;

}

//九宮內(nèi)的其它四個(gè)單元

for （inti = nineCells[index / 9]; i

{for （int j = nineCells[index % 9]; j

if （i ！= index / 9 && j ！= index % 9）

flag&= cellMethod（table， i， j， index）;

}

if （cellMethod == RecoverCellCandidate）

cell.Value = 0;

return flag;

2? 結(jié)? 論

針對(duì)應(yīng)用型本科人才的培養(yǎng)目標(biāo)，注重實(shí)踐能力的教學(xué)要求，通過(guò)對(duì)生活中的數(shù)進(jìn)行算法設(shè)計(jì)容易吸引學(xué)生的注意力，激發(fā)學(xué)生的學(xué)習(xí)興趣，活躍課堂氣氛，使學(xué)生將先驗(yàn)知識(shí)與新知識(shí)結(jié)合起來(lái)，由被動(dòng)接受知識(shí)轉(zhuǎn)變?yōu)橹鲃?dòng)接受、主動(dòng)探索，知識(shí)得到內(nèi)化，這不僅增強(qiáng)了學(xué)生對(duì)課程的興趣和學(xué)習(xí)信心，同時(shí)增強(qiáng)了學(xué)生的自主學(xué)習(xí)能力和探究能力，并且將上述題目在程序評(píng)測(cè)系統(tǒng)中展示，學(xué)生按照題目要求編寫程序并提交源代碼，評(píng)測(cè)系統(tǒng)編譯運(yùn)行程序。通過(guò)給定的輸入數(shù)據(jù)，由提交程序進(jìn)行處理，產(chǎn)生輸出結(jié)果，系統(tǒng)將該輸出結(jié)果與標(biāo)準(zhǔn)的輸出結(jié)果進(jìn)行比對(duì)，必須毫無(wú)差別才算正確，這需要學(xué)生心思縝密、考慮周到?！皵?shù)據(jù)結(jié)構(gòu)”教學(xué)內(nèi)容與實(shí)際問(wèn)題有機(jī)結(jié)合，并將其作為Online Judge System軟件平臺(tái)上的實(shí)驗(yàn)項(xiàng)目，學(xué)生完成情況較好，還培養(yǎng)了學(xué)生的團(tuán)隊(duì)精神，使各層次的學(xué)生學(xué)習(xí)積極性均有提高，較好地完成了教學(xué)目標(biāo)。

參考文獻(xiàn)：

[1] 劉小晶，杜選.數(shù)據(jù)結(jié)構(gòu)（Java語(yǔ)言描述） [M].北京：清華大學(xué)出版社，2011.

[2] 王曉明.基于學(xué)生自主和協(xié)作學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)模式探索與實(shí)踐 [J].高教學(xué)刊，2015（22）：229-230.

[3] 劉家瑛，郭煒，李文新.算法基礎(chǔ)與在線實(shí)踐 [M].北京：高等教育出版社，2017.

[4] SAHNI S，汪詩(shī)林，孫曉東.數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用：C++語(yǔ)言描述 [M].北京：機(jī)械工業(yè)出版社，2001.

作者簡(jiǎn)介：張秀梅（1978—），女，漢族，遼寧鞍山人，講師，碩士研究生，研究方向：中文信息處理。