<> = 为什么学习数据结构 = == 计算机是什么 == 计算机是一种处理数据的机器 {{{ 输入=〉存储 =〉输出 || 处理 }}} == 计算机处理数据的分类 == 数值数据：整数、浮点数等数值类型。与这类数据相关的问题有：线性方程的求解，矩阵求逆，微分方程求解等。在计算机发展初期，人们使用计算机主要是解决这类问题。现在主要是在解决工程学、经济学的问题中使用。 处理这类数据的知识叫做：数值计算。 == 计算机处理数据的分类 == 非数值数据：这类数据的类型多样，比如：文字，图像，声音，视频等等。这类数据的数据量巨大。随着计算机应用领域的扩大和软、硬件的发展，这类数据所占的比例越来越多，也越来越重要。（据统计，当今处理非数值性问题占用了90%以上的机器时间。）数据元素之间的相互关系一般无法用数学方程加以描述。 如何描述此类数据，并对此类数据进行有效的处理，成为了严峻的问题。解决此类问题的知识，被称为：数据结构。 == 非数值问题求解 == 著名的瑞士计算机科学家沃思（N.Wirth）教授曾提出： {{{ 算法+数据结构=程序 }}} * 数据结构：是指数据的逻辑结构和存储结构 * 算法：是对数据运算的描述 解决非数值问题的关键不再是分析数学和计算方法，而是要设计出适当的数据结构来存储数据，并在此基础上设计出有效的算法，来对数据进行需要的处理。 == 例子：电话号码查询问题 == 设计一个查询某个城市的私人电话号码的程序。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。 要解此问题首先构造一张电话号码登记表。表中每个结点存放两个数据项： 姓名和电话号码。要写出好的查找算法，取决于这张表的结构及存储方式。最简单的方式是将表中结点顺序地存储在计算机中。查找时从头开始依次查对姓名，直到找出正确的姓名或是找遍整个表均没有找到为止。 这种查找算法对于一个不大的单位或许是可行的，但对一个有成千上万私人电话的城市就不实用了。 == 例子：田径赛的时间安排问题 == 假设某校的田径选拔赛共设六个项目的比赛，即跳高、跳远、标枪、铅球、100米和200米短跑，规定每个选手至多参加三个项目的比赛。现有五名选手报名比赛，选手所选择的项目如参赛选手比赛项目表所示。现在要求设计一个竞赛日程安排表，使得在尽可以短的时间内安排完比赛。 || ||跳高||跳远||标枪||铅球||100米||200米|| ||A|| ||○ || || ||○ ||○ || ||B|| || || || || || || ||C|| || ||○ ||○ || || || ||D|| ||○ || || ||○ || || ||E||○ ||○ || || ||○ || || == 关于数据结构课程 == 这门课程是计算机相关专业的核心课程，在众多的计算机系统软件和应用软件中都要用到各种数据结构。仅掌握计算机语言是难以应付众多复杂的课题的，要想有效地使用计算机语言，必须学好数据结构的有关知识。 学习内容： * 数据结构的基础知识与运用 * 算法的简单分析与设计 后继课程：数据库，操作系统等都要数据结构知识 == 如何学习数据结构 == 数据结构课程理论结合实践，难度比较大 {{attachment:1new.png}} == 参考资源 == * 《数据结构》严蔚敏，吴伟民 * 《Fundamentals of Data Structures in C》Ellis Horowitz * 数据结构自考网http://student.zjzk.cn/course_ware/data_structure/web/main.htm == C语言基础 == 使用C语言进行课堂讲授 C语言中的重点： * 结构体 * 指针 * 数组 * 内存动态分配与释放 参考资料： * 《C程序设计语言》第二版，K&R == 离散数学基础 == 这是数据结构的理论基础 主要相关知识： * 图论（图、树） 参考资料 = 数据结构中的基本概念 = == 数据结构的基本概念 == * 数据（Data）：是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。数据的范畴包括：整数、实数、字符串、图像和声音等。 * 数据元素（Data Element）是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。 == 数据的逻辑结构 == 数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure） 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 == 逻辑结构的表示 == B = (K, R) K：数据元素的集合，比如：{a, b, c, d,e} R：数据元素之间的关系的集合，比如：{, ,,} ：a是b的前驱节点，b是a的后继节点 {{attachment:2.png}} == 逻辑数据结构分类 == * 线性结构：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。栈、队列、字符串等都是线性结构。<
> {{attachment:3.png}} * 非线性结构：一个结点可能有多个直接前趋和直接后继。树和图等数据结构都是非线性结构。 * 树：只有一个前驱，可能有多个后继<
> {{attachment:4.png}} * 图：有多个前驱和多个后继<
> {{attachment:5.png}} == 数据的存储结构 == 数据元素及其逻辑关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure） 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。 == 数据的基本存储结构 == * 顺序存储结构（Sequential Storage Structure）：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 * 链式存储结构（Linked Storage Structure）：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。通常借助于程序语言的指针类型描述。 * 索引存储结构：该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由若干索引项组成。索引项的一般形式是：(关键字、地址)。关键字是能唯一标识一个结点的那些数据项，地址指示结点所在的存储位置。 * 散列存储结构：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储结构，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构可以采用不同的存储结构来表示。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 存储密度：数据所占空间与数据结构所占空间的比。一定≤1 == 数据的运算 == 数据的运算，即对数据施加的操作。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。 最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。 == 数据结构 == 数据结构就是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。 存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。 数据的运算也是数据结构不可分割的一个方面：在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。 【例】若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。 更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。 == 抽象数据类型（Abstract Data Type） == ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 一个ADT可描述为： {{{ ADT ADT-Name{ 数据对象： …… 数据元素之间逻辑关系： …… 操作： Operation1://操作1 Operation2://操作2 …… } }}} = 算法和算法的度量 = == 算法 == 为了求解某问题，必须给出一系列的运算规则，这一系列的运算规则是有限的，表达了求解问题方法和步骤，这就是一个算法。 一个算法可以用自然语言描述，也可以用高级程序设计语言描述，也可以用伪代码描述。本课程采用C语言对算法进行描述。实验中采用C/C++都可以。 == 例子 == 写一个算法，计算n! {{{ 让i=1, s=1 如果i>n则转第6步 s = s * i i = i +1 转第2步 计算结束，s为n!的值 }}} 还有其他算法吗？ == 五个重要特性 == * 有穷性：算法的执行必须在有限步内结束。 * 确定性：算法的每一个步骤必须是确定的无二义性的。 * 输入：算法可以有0个或多个输入。 * 输出：算法一定有输出结果 * 可行性：算法中的运算都必须是可以实现的。 == 算法的正确性 == * 正确的算法：若一个算法对于每个输入实例均能终止并给出正确的结果，则称该算法是正确的。正确的算法解决了给定的计算问题。 * 不正确的算法：一个不正确的算法是指对某些输入实例不终止，或者虽然终止但给出的结果不是所渴望得到的答案。 == 评价算法的好坏 == 求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？选用的算法首先应该是“正确”的。 主要考虑如下三点： * 执行算法所耗费的时间； * 执行算法所耗费的存储空间，其中主要考虑辅助存储空间； * 算法应易于理解，易于编码，易于调试等等。 == 算法的选择 == 一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触：要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。 因此我们只能根据具体情况有所侧重： * 若该程序使用次数较少，则力求算法简明易懂； * 对于反复多次使用的程序，应尽可能选用快速的算法； * 若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。 == 算法执行时间的分析 == 一个算法所耗费的时间=算法中每条语句的执行时间之和 每条语句的执行时间=语句的执行次数（频度）×语句执行一次所需时间 算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。 若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。 == 例子：求矩阵乘积 == {{{#!cplusplus void mult(int a[n][n], int b[n][n], int c[n][n]) { int i, j, k; for (i=0; i