【Mark】数据结构（C语言版）

• 值得记的

第1章 绪论

• 编写好的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系
• 在对弈问题中，计算机操作的对象是对弈过程中可能出现的棋盘状态——称为格局
• 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科
• 可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程
• 数据结构的定义为：一个二元组
  Data_Structure = (D, S)元素的集合 + 关系的集合
• 数据的逻辑结构，就是关系
• 一个位串表示一个数据元素，也叫元素、结点，其中数据项就对应子位串
• 顺序映像借助相对位置表示元素之间的逻辑关系，非顺序映像借助指针(Pointer)
• 任何一个算法的设计取决于选定的数据(逻辑)结构，而算法的实现依赖于采用的存储结构
• 数据类型(Data Type)，用以刻画(程序)操作对象的特性，
  是一个值的集合和定义在这个值集上的一组操作的总称
  明显或隐含的规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作
• 原子类型，不可分解，例如C的基本类型
• 结构类型，可分解
• 数据结构可以看成是“一组具有相同结构的值”，则结构类型可以看成由一种数据结构和定义在其上的一组操作组成
• 引入数据类型的目的，
  从硬件看，是作为解释计算机内存中信息含义的一种手段
  对用户，实现了信息的屏蔽，即，将一切用户不必了解的细节都封装在类型中
• 抽象数据类型(Abstract Data Type)，是指一个数学模型以及定义在该模型上的一组操作，ADT的定义仅取决于它的一组逻辑特性
• 固有数据类型，各处理器中已定义并实现的数据类型
• 一个软件系统的框架应建立在数据之上，而不是建立在操作之上（后者是传统软件设计方法所为）
• 原子类型(Atomic Data Type)，已说过，例如100位的整数
• 固定聚合类型(Fixed-Aggregate Data Type)，其值，成分数目确定，例如复数
• 可变聚合类型(Variable-Aggregate Data Type)，其值，成分数目不确定，例如“一个有序整数序列”
• 多形数据类型(Polymorphic Data Type)，元素特性可以很复杂，但元素之间关系相同，基本操作也相同
• 预定义常量和类型

//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
// Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef int ElemType;	//由用户使用时自行定义

• 一般而言，a、b、c、d、e等用作数据元素名，i、j、k、l、m、n等用作整型变量名，p、q、r等用作指针变量名
• 引用调用的参数传递方式，以&打头的参数即为引用参数（返回操作结果，包含状态变化等）
• 链接: ADT_Triplet三元组的实现.
• 算法，指令的有限序列
• 衡量一个程序是否合格的标准：
  程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果
• 可读性(Readability) 好，有助于人对算法的理解
• 健壮性(Robustness)，输入数据非法时程序的反应和处理，处理出错的方法应是返回一个表示错误或错误性质的值，而不是打印错误信息或异常，并终止程序的执行，以便在更高的抽象层次上进行处理（总是觉得这句话有问题。。。）
• 效率与低存储量需求，现在更偏向于高效
• 事前分析：对算法所消耗资源的一种估算方法
• 一个特定算法“运行工作量”的大小，只依赖于问题的规模(通常用整数量n表示)，或者说，它是问题规模的函数。（运算规模）
• 从算法中选取一种对于所研究问题(或算法类型)来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度
• 渐近时间复杂度(Asymptotic Time Complexity)，随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。（时间复杂度）
• 链接: ADT_起泡排序的实现.
• 平均时间复杂度难以确定，更常用的办法是，讨论算法在最坏情况下的时间复杂度，即分析最坏情况以估算算法执行时间的一个上界
• 额外空间，除输入和程序本身之外的，需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间
• 原地工作，额外空间相对于输入数据量来说是常量时

第2章 线性表

• 线性表（linear_list）是最常见且最简单的一种数据结构
• 在每一个数据元素由若干数据项(item)组成时，称数据元素为记录，含有大量记录的线性表叫文件
• 线性表的顺序表表示指的是用一组地址连续的存储单元依次存储线性表的数据元素