第一章 算法与数据结构基础.pptVIP

算法与数据结构 2012-2 计算机与通信学院 教材与参考书 1.算法与数据结构，张永，李睿，年福中 2.数据结构, 严蔚敏,吴伟民 3.数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译?电子工业出版社 ????2001 年1月 第一部分 基本概念 第一章 算法与数据结构基础 先看一个计算机求解问题的示例 1.1问题求解分析 大家知道，要让计算机处理现实问题，首先要解决两个问题： 1．现实问题的计算机化表示问题 2．现实问题的处理过程程序化问题 前者就是选用合适的数据结构将计算机要处理的对象有效表示、存贮的问题； 后者就是选择针对具体问题的合适算法以便使计算机能够进行程序化处理的问题。这里就涉及到数据结构和算法知识。 [魔方求解问题] 一个魔方（magic square）就是一个由1到n2的整数构成的n×n的矩阵，其中每行、每列以及两个主对角线上的数字之和都相等。 当n=3时，魔方如图所示 问题是:如何一般求解? 6 1 8 7 5 3 2 9 4 当n为奇数时，Coxeter给出了产生魔方的具体过程： 1.把1放入第一行最中间的方格中； 2.向左上方移动，并按照数字的递增顺序，把数字填入空方格； 3.如果移出了魔方，即超越了魔方边界，则进入魔方对边的对应方格中； 4.如果一个方格已被填入数字，则向下继续填写方格； 5.依据上述方法，直到全部填写完毕。 本方法: 15 8 1 24 17 16 14 7 5 23 22 20 13 6 4 3 21 19 12 10 9 2 25 18 11 其它方法(右上方法): 17??24? ???1? ???8? ?15 ??23? ? 5? ???7? ?14? ?16 ? ?4? ???6? ?13? ?20? ?22 ??10??12? ?19? ?21? ???3 ??11??18? ?25? ???2? ???9  30? ?39? ?48? ???1? ?10? ?19? ?28 ??38? ?47? ???7? ???9? ?18? ?27? ?29 ??46? ???6? ???8? ?17? ?26? ?35? ?37 ? ? 5? ?14? ?16? ?25? ?34? ?36? ?45 ??13? ?15? ?24? ?33? ?42? ?44? ???4 ??21? ?23? ?32? ?41? ?43? ???3? ?12 ??22? ?31? ?40? ?49? ???2? ?11? ?20 要让计算机求解上述问题: 首先选择一个数据结构表示魔方，这里选择一个行、列各为n的数组来表示魔方； 数据结构形式化结果为（以类C语言描述）： int square[MAX_SIZE][ MAX_SIZE]; /*定义一个二维数组来表示魔方*/ 其次，将上述的产生魔方的过程算法化，用简洁的描述方式描述产生魔方的过程，即就是算法描述 （这里假定size为奇数，行、列为size）： 1）square[0][(size-1)/2]=1; /*把1放入第一行最中间的方格中 */ 2）for (count=2; count=size*size; count++){ /*依次放入其后的数字*/ /*i=0,第一行; j=(size-1)/2; 行的中间位置*/ row=(i-10)? (size-1): ( i-1); /*i=0;j=(size-1)/2; 上方*/ column=(j-10)? (size-1): ( j-1); /*左方*/ if (square[row][column]) /*下方*/ i=(++i) % size; else { /* 如果方格已被填入数字*/ i=row; j=(j-10)?(size-1) : --j; } square[i][j]=count; } 用C语言实现如下： #include stdio.h #define MAX_SIZE 15 /*魔方行列最大为15 */ void main(void) { static int square[MAX_SIZE][ MAX_SIZE]; int i, j, row, column; /* 索引*/ int