数据结构C语言版

数据结构C语言版第2版第一章绪论，介绍了1.1数据结构的研究内容、 1.2数据结构的基本概念和术语、 1.3抽象数据类型的表示与实现等。

绪论

• 1.1数据结构的研究内容
  • 数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程
    • 学生学籍管理系统：一对一线性关系
    • 人机对弈问题：一对多树结构
    • 最短路径问题：多对多网状结构
• 1.2数据结构的基本概念和术语
  • 1.2.1 数据、数据元素、数据项和数据对象
    • 数据（Data）是客观事物的符号表示，是所有能输入计算机中并被计算机程序处理的符号的总称
    • 数据元素（Data Element）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
    • 数据项（Data Item）是组成数据元素的、有独立含义的、不可分割的最小单位。
    • 数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。
  • 1.2.2 数据结构
    • 逻辑结构
      • 集合结构 数据元素之间除了"属于同一集合"的关系外，别无其他关系
      • 线性结构 数据元素之间存在一对一的关系
      • 树结构 数据元素之间存在一对多的关系
      • 图结构或网状结构 数据元素之间存在多对多的关系
    • 存储结构
      • 顺序存储结构
      • 链式存储结构
  • 1.2.3 数据类型和抽象数据类型
    • 数据类型是一个值的集合和定义在这个值集上的一组操作的总称
    • 抽象数据类型（Abstract Data Type,ADT）一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括3个部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。
• 1.3抽象数据类型的表示与实现
  • （1）预定常量及类型(2）数据结构的表示（存储结构）用类型定义（typedef）描述；数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。 (3）基本操作的算法都用如下格式的函数来描述 (4）内存的动态分配与释放。(5）赋值语句(6）选择语句(7）循环语句(8）结束语句(9）输入输出语句使用C+＋流式输入输出的形式(10）基本函数
• 1.4算法和算法分析
  • 1.4.1 算法的定义及特性
    • (1）有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
    • （2）确定性。对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，算法的执行者或阅读者都能明确其含义及如何执行。
    • (3）可行性。算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
    • • (4）输入。一个算法有0个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。
    • (5）输出。一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。
  • 1.4.2 评价算法优劣的基本标准
    • (1）正确性。在合理的数据输人下，能够在有限的运行时间内得到正确的结果。
    • (2）可读性。一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法容易隐藏错误，且难于调试和修改。
    • (3）健壮性。当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。
    • (4）高效性。高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。
  • 1.4.3 算法的时间复杂度
    • 1．问题规模和语句频度
      • 一条语句的重复执行次数称作语句频度
      • 问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。
    • 2．算法的时间复杂度定义
      • 一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数An)，算法的时间量度记作： 频度为 T(n)=O((n)) 频度A 它表示随着问题规模n的增大，算法执行时间的增长率和（n）的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度
    • 3．算法的时间复杂度分析举例
      • 【例1.5】 常量阶示例。 [x++;s=0;) 两条语句频度均为1
      • 【例1.6】线性阶示例。 for(i=0;i<n;i++)(x++;s=0;) 虑 循环体内两条基本语句的频度均为A(n)=n，所以算法的时间复杂度为T(n)=O(n)，称为线性阶。
      • 【例1.7】 平方阶示例。 算 (1) x=0;y=0; (2) for(k=1;k<=n;k++) n) (3) x++; (4) for(i=1;i<=n;i++) (5) for(j=1;j<=n;j++) (6) y++; 对循环语句只需考虑循环体中语句的执行次数，以上程序段中频度最大的语句是（6)，其频度为f(n)=n2，所以该算法的时间复杂度为T(n)=O(n2)，称为平方阶。
    • 4．最好、最坏和平均时间复杂度
      • 称算法在最好情况下的时间复杂度为最好时间复杂度，是指算法计算量可能达到的最小值；称算法在最坏情况下的时间复杂度为最坏时间复杂度，是指算法计算量可能达到的最大值；算法的平均时间复杂度是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。
  • 1.4.4 算法的空间复杂度
    • 关于算法的存储空间需求，类似于算法的时间复杂度，我们采用渐近空间复杂度（Space Complexity）作为算法所需存储空间的量度，简称空间复杂度，它也是问题规模n的函数，记作： 的一 基本 S(n)=O(f(n))