基于數的數據結構算法設計

張秀梅 王賀 楊陽

摘? 要：“數據結構”是軟件工程專業的核心專業基礎課，通過學習培養學生能夠分析數據對象特征，根據問題的需要，確定邏輯結構并選擇合適的存儲結構，實現典型算法設計及性能分析的能力。針對數據結構抽象性比較強的特點，文章采用對數的認識逐步遞進的方式進行相關算法設計，不僅可以提升課程教學效率及質量，而且有利于提高學生學習的主動性和創新性。

關鍵詞：數據結構;素數;素數環;魔方陣;數獨

中圖分類號：TP311.1? ? ? ?文獻標識碼：A 文章編號：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? 引? 言

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

1? 算法設計

數據結構指導著各種程序設計語言如何編寫程序，而算法是數據結構的靈魂，是貫穿整個“數據結構“課程的主線，如何把生活中的實際問題通過分析問題、建立模型、設計算法、編制程序、調試優化等步驟用計算機實現是學習該課程的核心所在。而算法的設計跟數學是分不開的，一個高效的算法要選取合適的數據結構，它們之間是相輔相成的，因此將一些有趣的數進行歸納，并延伸來設計相應的算法。

1.1? 簡單的數

自然數有奇數、偶數，奇偶的判斷在計算機中用模運算（%）來實現，如何判斷一個數是否為素數（只能被1和自身整除的數），進而引申出：

（1）一個大于2的偶數可以表示為兩個素數的和，即哥德巴赫猜想;

（2）如果一組整形數組任何兩個相鄰元素的和為素數，并且首尾的和也為素數，即為素數環。

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

根據n的奇偶性幻方分為：

（1）n為奇數時稱為奇幻方;

（2）n為偶數且是4的倍數時稱為雙偶幻方;

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

單偶幻方算法描述如下：

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

（2）將單偶幻方的方格分割成四個區間，按照順時針編號為A、B、C、D四個區間;

（3）每一個區間實現一個奇數幻方的填充，填充順序為A、D、B、C;

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

A， D區間交換

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

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

B， C區間交換

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

1.2? 數獨

更進一步地對另一個益智游戲——數獨（如圖2所示為初級數獨）進行介紹。數獨是由9個3*3子矩陣組成的9*9矩陣，每個子矩陣由1～9的數字組成，且每行每列不能有重復數字。該算法需要綜合運用表結構來設計，并且采用回溯算法實現對重復元素的判定，回溯法也叫試探法，每次試著往前走，一直走到不通，然后撤回，再重新試探。

算法詳細描述如下：

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

（2）預處理查詢候選數列表每一行、列和宮格查找已知數和候選數有沖突的項，并將沖突項從列表移走。繼續執行此過程修訂列表，直到候選數列表的值不再變化;

（3）查找包含有最少候選數的列表，并隨機選取一個數作為正確的數進行猜想。候選數列表中只有一個數字時為數格賦值。同時注意要有標識，以便在后續的執行過程中如果有回退可以恢復;

（4）在每一次可能的猜測過程中，通過回溯遞歸回到步驟（2）。通過這種方式，若當前情況無解的時候回溯，直到所有的候選數列表有唯一候選數;

（5）當所有的猜測都嘗試之后如果沒有解，則返回false。相反，如果宮格都被填滿，并且驗證通過，則表示數獨謎題有解。

處理相關單元格核心代碼如下：

bool flag = true;

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

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

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

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

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

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

}

//九宮內的其它四個單元

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? 結? 論

針對應用型本科人才的培養目標，注重實踐能力的教學要求，通過對生活中的數進行算法設計容易吸引學生的注意力，激發學生的學習興趣，活躍課堂氣氛，使學生將先驗知識與新知識結合起來，由被動接受知識轉變為主動接受、主動探索，知識得到內化，這不僅增強了學生對課程的興趣和學習信心，同時增強了學生的自主學習能力和探究能力，并且將上述題目在程序評測系統中展示，學生按照題目要求編寫程序并提交源代碼，評測系統編譯運行程序。通過給定的輸入數據，由提交程序進行處理，產生輸出結果，系統將該輸出結果與標準的輸出結果進行比對，必須毫無差別才算正確，這需要學生心思縝密、考慮周到。“數據結構”教學內容與實際問題有機結合，并將其作為Online Judge System軟件平臺上的實驗項目，學生完成情況較好，還培養了學生的團隊精神，使各層次的學生學習積極性均有提高，較好地完成了教學目標。

參考文獻：

[1] 劉小晶，杜選.數據結構（Java語言描述） [M].北京：清華大學出版社，2011.

[2] 王曉明.基于學生自主和協作學習的數據結構實驗教學模式探索與實踐 [J].高教學刊，2015（22）：229-230.

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

[4] SAHNI S，汪詩林，孫曉東.數據結構、算法與應用：C++語言描述 [M].北京：機械工業出版社，2001.

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