基于数的数据结构算法设计

张秀梅 王贺 杨阳

摘  要：“数据结构”是软件工程专业的核心专业基础课，通过学习培养学生能够分析数据对象特征，根据问题的需要，确定逻辑结构并选择合适的存储结构，实现典型算法设计及性能分析的能力。针对数据结构抽象性比较强的特点，文章采用对数的认识逐步递进的方式进行相关算法设计，不仅可以提升课程教学效率及质量，而且有利于提高学生学习的主动性和创新性。

关键词：数据结构;素数;素数环;魔方阵;数独

中图分类号：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—），女，汉族，辽宁鞍山人，讲师，硕士研究生，研究方向：中文信息处理。