1、第一章 ...
-
1.数据结构是研究非数值计算的程序设计中计算机的操作对象，以及它们之间的关系和操作。
2.数据相关概念：
数据：能输入计算机并能被计算机处理的各种符号的集合。是信息的载体。是对客观事物符号化的表示。能够被计算机识别、存储和加工。
数据包括：数值型数据（整数，实数）；非数值型数据（文本、图像）。
数据元素：数据的基本单位（一般作为一个整体进行处理）
即元素结点 （一整条）记录 顶点
数据项：构成数据元素的不可分割的最小单位
数据对象：性质相同的数据元素的集合
【重】数据元素是数据的一个个个体；数据对象是数据集合的子集。
3.数据结构层次：
逻辑结构 （描述数据元素之间的逻辑关系）独立于计算机，与存储无关。是从具体问题中抽象出来的数学模型。
物理结构（存储结构）数据元素及其关系在计算机存储中的结构；是数据结构在计算机中的表示。（可能会问填空）
4.逻辑结构种类
（未放到计算机实现层面就能用手写勾勒的是逻辑结构）
线性结构线性表、栈、队列、串
非线性结构图树
集合结构数据元素之间的关系仅有它们同属于一个集合这个关系
线性结构一对一
树形结构一对多
图状 网状多对多
5.存储结构的种类
（放到物理上我们怎么存--以去实现逻辑结构）
顺序存储结构以逻辑结构的关系顺着存
（连续的存储单元依次不断的存储）逻辑关系由存储位置就能表示----c 数组实现
链式存储用指针链存
（一组任意的存储单元存储数据元素），逻辑关系是用指针表示 ----c 指针实现
索引存储索引地址找
（任意的存储单元存储数据元素，但建立附加的索引表指向对应存储单元） 索引项(关键字，地址）
散列存储根据结点关键字直接计算出该节点的存储位置
对比
怎么存储数据元素怎么存储（表示）元素之间的关系c怎么实现
顺序连续的存储单元存储位置就能表示数组实现
链式任意的存储单元指针表示逻辑关系指针
索引任意的（无要求）索引表指向存储位置指针+
6.数据类型
这是计算机程序语言中的概念。因为对程序中的每个变量、常量、表达式等都要明确说明所属数据类型。
数据类型定义：一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
数据类型=值的集合+值集合上的一组操作
上述提到的有的基本数据结构可以用 数据类型来实现（数组）。栈、队列就没法直接用数据类型表示。
（c中的数据类型：
基本数据类型int char long double float
构造数据类型 数组结构共用体枚举
指针 void空类型
自定义的数据类型typedef）
数据类型的作用：约束变量取值范围；约束变量操作
7.抽象数据类型ADT(D,S,P)
一个数学模型以及定义在此数学模型上的一组操作。
抽象数据类型=数学模型+模型上的一组操作
(D,S,P) 数据对象数据关系基本操作
基本操作怎么定义：（相当于定义函数）
参数表：
初始条件：
操作结果：
8.算法
好的算法的特性：正确性、健壮性、可读性
算法效率：时间效率、空间效率（有时二者矛盾）通常事前分析算法效率。
·算法运行时间：Σ每条语句的执行次数（即语句频度）*该语句执行一次所需时间
语句执行一次要的时间随机器而异，与算法无关。所以直接假设执行每条语句所需时间均为单位时间。所以只用讨论语句频度。
·直接用算法的渐进时间复杂度O(n)。
·基本语句：算法中重复执行册数和算法的执行时间成正比的语句，且是同期执行次数最多的，对算法运行时间的贡献最大。
比较：基本语句重复执行的次数是问题规模n的某个函数f(n)
算法的时间复杂度为T(n)=O(f(n))
则 0<=T(n)<=O(n)
·算法时间复杂度 是由嵌套深度最深的那个基本语句的语句频度决定；而基本操作执行的次数有时受问题的输入数据集（问题规模）影响。所以一般考虑最坏时间复杂度。
·渐进空间复杂度 （考虑算法本身要占据的空间，输入、输出、指令、常数,变量，以及辅助空间）
作者有话说
第1章 第一章
