算法 第一章

《算法 第一章》由会员分享，可在线阅读，更多相关《算法 第一章（27页珍藏版）》请在金锄头文库上搜索。

1、算法与数据结构,2010-09计算机与通信学院,教材与参考书1.算法与数据结构，张永，李睿，年福中2.数据结构, 严蔚敏,吴伟民3.数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译电子工业出版社 2001 年1月,第一部分 基本概念第一章 算法与数据结构基础先看一个计算机求解问题的示例,1.1问题求解分析,大家知道，要让计算机处理现实问题，首先要解决两个问题：1现实问题的计算机化表示问题2

2、现实问题的处理过程程序化问题前者就是选用合适的数据结构将计算机要处理的对象有效表示、存贮的问题；后者就是选择针对具体问题的合适算法以便使计算机能够进行程序化处理的问题。这里就涉及到数据结构和算法知识。,魔方求解问题一个魔方（magic square）就是一个由1到n2的整数构成的nn的矩阵，其中每行、每列以及两个主对角线上的数字之和都相等。当n=3时，魔方如图所示问题是:如何一般求解?,当n为奇数时，Coxeter给出了产生魔方的具体过程：1.把1放入第一行最中间的方格中；2.向左上方移动，并按照数字的递增顺序，把数字填入空方格；3.如果移出了魔方，即超越了魔方边界，则进入魔方对边的对应方格中

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其它方法(右上方法): 1724 1 8 15 23 5 7 14 16 4 6 13 20 22 1012 19 21 3 1118 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 4

4、3 3 12 22 31 40 49 2 11 20,要让计算机求解上述问题:首先选择一个数据结构表示魔方，这里选择一个行、列各为n的数组来表示魔方；数据结构形式化结果为（以类C语言描述）：int squareMAX_SIZE MAX_SIZE; /*定义一个二维数组来表示魔方*/,其次，将上述的产生魔方的过程算法化，用简洁的描述方式描述产生魔方的过程，即就是算法描述（这里假定size为奇数，行、列为size）：,1）square0(size-1)/2=1; /*把1放入第一行最中间的方格中 */2）for (count=2; count=size*size; count+) /*依次放入其后

5、的数字*/ /*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 (squarerowcolumn) /*下方*/ i=(+i) % size; else /* 如果方格已被填入数字*/ i=row; j=(j-10)?(size-1) : -j; squareij=count;,用C语言实现如下：,#include #define MAX_SIZE 15 /*魔方行列最大为15 */v

6、oid main(void) static int squareMAX_SIZE MAX_SIZE; int i, j, row, column; /* 索引*/ int count; /* 计数*/ int size; /* 魔方行列数*/ printf(“Enter the size of the square:”); scanf(“%d”,&size); /* check for input errors*/ if (sizeMAX_SIZE+1) printf(“Error! Size is out of rangen”); exit(1); ,for (i=1; isize; i+)

7、 for(j=0; jsize; j+) squareij=0;square0(size-1)/2=1; /* middle of first row */*i and j current position */i=0;j=(size-1)/2;for (count=2; count=size*size; count+) row=(i-10)? (size-1): ( i-1); /*up*/ column=(j-10)? (size-1): ( j-1); /*left*/ if (squarerowcolumn) /*down*/ i=(+i) % size; else /*square

8、is unoccupied*/ i=row; j=(j-10)?(size-1) : -j; squareij=count;,/*output the magic square*/printf(“Magic square of size %d:nn”,size);for (i=1; isize; i+) for(j=0; jsize; j+) printf(“%5d”, sqaureij);printf(“n”);printf(“nn”);,从上面这个实际问题的求解过程可以看出，计算机在解决问题的时候:首先是将现有的问题有效表示，即选择合适的数据结构来表示；而后将问题的求解过程形式化、程序化，

9、即建立算法。这样，计算机才可以有效识别、存储并解决相关问题。,1.2数据结构,数据结构与计算机环境下的问题求解有密切关系。什么是数据结构呢？先介绍一些概念，而后引入数据结构的定义。1数据（Data）数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图形、图像和声音等。2数据元素（Data Element）数据元素是数据的基本单位。数据元素也称为元素、结点、记录。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。3数据对象（data object）是性质相

10、同的数据元素的集合，是数据的一个子集。,4数据结构（Data Structure） 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 特别关注的是数据之间的相互关系，即数据的组织形式。数据结构的形式定义为： Data_Structure = (D, S)其中，D是数据元素的集合，S是D上关系的有限集合。,从上面定义可以知道，数据结构一般包括以下三方面内容：1）数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 2）数据元素及其

11、关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；数据的存储结构是逻辑结构用计算机语言的实现,3）数据的运算，即对数据施加的操作数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。 最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。,例1-2 学生成绩表,来看上表涉及的数据的逻辑结构、存储结构和相关运算,1) 逻辑结构表中的每一行是一个记录（数据元素），它由学号、姓名、各科成绩及平均成绩等数据项组成。表中记录之间的逻辑关系是：对表中任一记录，与它相邻且在它前面的记录（亦称为直接前趋最多只有一个；与表中任

12、一记录相邻且在其后的记录也最多只有一个。表中只有第一个记录没有直接前趋，故称为开始记录；也只有最后一个记录没有直接后继，故称之为终端记录。,2）存储结构该表的存储结构是指用计算机语言如何表示记录之间的这种关系，即表中的记录是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？,3）数据的运算在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的记录；进来新学生时要增加记录。究竟如何进行查找、删除、插入，这就是数据的运算问题。,13数据结构的分类,1. 线性结构线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始元素和一个终结元素，并且所有数据元素都最多

13、只有一个直接前趋和一个直接后继。线性表是一种典型的线性结构。栈、队列、串等都是线性结构。2. 非线性结构非线性结构的逻辑特征是：一个数据元素可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。,14 数据的四种基本存储方法,数据的存储结构可用以下四种基本存储方法得到：1.顺序存储方法该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。2. 链式存储方法该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为

14、链式存储结构，通常借助于程序语言的指针类型描述。,3.索引存储方法该方法通常在存储结点信息的同时，还建立附加的索引表。索引表由若干索引项组成。索引项的一般形式是： (关键字、地址)关键字是能唯一标识一个结点的那些数据项。4. 散列存储方法该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。,1.5 数据结构三方面的关系,数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。,