第一章 绪 论

《第一章 绪 论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论§1.1为什么要学习数据结构§1.2数据结构概念历史定义1.1　数据是指对象的表示，即按照适合于通信、解释或处理（借助人或自动装置）的方式所形成的关于事实、概念或指令的表示；数据只是表示，而无含义[3]。数据是计算机科学与技术中最基本的概念，它是计算机程序要处理的“原料”，是所有被计算机识别、存储和加工处理的符号的总称[4,5]。元素、结点或顶点，数据项（也称为域或字段）数据元素（或曰数据成分）还可被称为元素、结点或顶点等。数据元素可大可小，大到可以是一篇文稿、一本书，小到可以是一个字符，甚至是计

2、算机二进制数中的一位。数据元素可由若干个数据项（也称为域或字段）组成。例1.1如表1.1所示的通讯录表，行表示一个结点（数据元素），每个结点由姓名、区号、办公电话和手机四个域（数据项）组成。表1.1通讯录表姓名区号办公电话手机赵一0105364458713911001234钱二0208963415913809771333孙三0214597652813916586666李四0246342754113804076111定义1.2数据结构由若干数据成分按照一定方式构成的复合数据以及作用于其上的函数或运算。数据成分

3、及其间的数据约束关系合称为数据结构的逻辑结构。数据结构从数学上可用适当的数学结构以及其上的函数变换统一地定义。但迄今为止，关于数据结构之定义在计算机科学技术界还未取得完全认同。有些学者认为数据结构应由数据的逻辑结构、数据的存储结构及其运算三部分组成。一个逻辑结构可形式定义为一个二元组[5]：L=(N,R)，其中，N是结点的有限集合，R是定义在集合N上的二元关系r的集合。设L=(N,R)是一个逻辑结构.r1ÎR是与线性结构、树结构和二叉树结构对应的一种关系，若a，bÎN，且(a，b)Îr1，则称a是b的前驱结

4、点，b是a的后继结点，a和b是相邻结点；若不存在aÎN使得(a，b)Îr1，则称b为始结点；若不存在bÎN使得(a，b)Îr1，则称a为终结点.r2ÎR是与图结构对应的一种关系，若a，bÎN，且关系(a，b)Îr2，则称a和b是相邻结点;对于有向图结构，若存在(a，b)Îr2，则称a是b的前驱结点，b是a的后继结点。数据的存储结构（或曰物理结构）1.2.3对数据结构的操作插入、删除、修改、排序、查找§1.3算法定义1.4[9]一个算法就是给出求解特定类型问题之运算序列的一个有穷规则集合，一个算法应具有5个重

5、要特征：1)有限性：一个算法在执行有限步骤后必然终止；2)确定性：对一个算法的每个步骤都必须给出精确的定义；对要执行的动作都必须给出针对每种情况的严格、无歧义的描述；3)输入：一个算法有0个或多个输入；4)输出：算法有1个或多个输出；5)可行性：算法中的所有操作都必须是充分基本的，因而原则上人们用纸和笔都可在有限时间内精确地完成它们。1.3.2算法的描述ADL语言例1.3欧几里得算法E[9-10]算法E(m,n.n)/*给定两个正整数m和n，算法E求它们的最大公因子（即能同时整除m和n的最大正整数），输出结

6、果在n中*/E1.[求余数]r¬m-ëm/nû´n.//有0£r

7、人们在阅读、理解、调试、修改和重用算法等方面的困难。此外，一个可读性好的算法，常常也具有相对的简单性。鲁棒性:对有缺失、有噪声或有错误的输入数据，算法具有较强的应对能力。譬如，一个鲁棒性好的算法能对输入数据进行语法检验，甚至能进行语义检验，提出修改错误的具体建议并提供重新输入数据的机会；它既不会简单地拒绝输入，也不会允许错误任意流传。说某算法A是最优的，当且仅当在被研究的解决同一问题的所有算法集合SA中，不存在算法BÎSA（B¹A）其执行的基本运算次数比算法AÎSA更少。证明一个算法是最优的，不是一件容易的

8、事。但如果能给出解决一个问题所需要的基本运算次数的下界，则任一个基本运算次数等于下界的算法都将是最优的。证明最优往往采用逼近的方法。§1.4算法的正确性证明对于一个算法来说正确性是前提，也是最重要的。要证明算法的正确性，就必须证明对于每一个合法输入，算法都会在有限的时间内输出一个满足要求的结果[10]。一旦完成了算法的设计，必须验证算法的正确性。对于明显是正确的算法（或程序），可以通过上机调试验证其正确性。所以，