datestructure

第一章：绪论 一、基本概念1.Data数据Data数据：是能够输入计算机且能被计算机处理的各种符号的集合。 Data数据包括： 数值型数据：整数、实数 非数值型数据：文字、图像、图形、声音等 2.DataElement数据元素DataElement数据元素（元素/记录/结点/顶点）：是Data数据的基本单位，在计算机程序中通常被作为一个整体进行考虑和处理 3.DataItem数据项DataItem数据项：是构成数据元素的不可分割的最小单位。 数据三者之间的关系：数据 > 数据元素 >...

第二章：线性表 一、线性表线性表：具有相同特性的数据元素的一个有限序列，数据元素的个数定义为表的长度。 线性表ADT的定义如下： 1234567891011ADT List { 数据对象: D = {ai | ai属于Element, (i = 1, 2, ..., n)} 数据关系: R = {<ai-1, ai> | ai-1, ai属于D, (i = 1, 2, ..., n)} 基本操作: InitList(&L); DestroyList(&L); ListInsert(&L, i, e); ListDelete(&L, i, &e);} ADT...

第三章：栈与队列 栈Stack和队列是线性表的子集，是限定插入和删除只能在表的端点进行的线性表。 一、顺序栈栈Stack是一个特殊的线性表，限定仅在一端（通常是表尾/栈顶）进行插入和删除操作的线性表。 栈的特点： 逻辑结构：与线性表相同 存储结构：用顺序栈或链栈均可，顺序栈更为常见 运算规则：只能在栈顶进行运算，访问结点时按照后进先出的LIFO原则 实现方式：关键在于入栈与出栈函数，具体实现顺序栈与链栈不同。 栈的相关问题： 数制转换 表达式求值 括号匹配的检验 八皇后问题 迷宫求解 函数调用 递归调用的实现 行编辑程序 1.顺序栈（1）顺序栈表示：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈底一般在低地址端。 123456#define MAXSIZE 100typedef struct { SElemType *base; SElemType *top; int stackSize;}...

第四章：串与数组 一、串String串是指零个or多个任意字符串组成的有限序列。 123456789101112131415161718ADT String { 数据对象： 数据关系： 基本操作： StrAssign(&T, chars); StrCompare(S, T); StrLength(s); Concat(&T, S1, S2); SubString(&Sub, S, pos, len); StrCopy(&T, S); StrEmpty(S); ClearString(&S); Index(S, T, pos);//字符串匹配算法 Replace(&S, T, V); StrInsert(&S, pos, T); StrDelete(&S, pos, len); DestroyString(&S);} ADT...

第五章：BT（上） 一、BT概述1.概念 根结点：非空树中无前驱结点的结点 分支结点：度!=0 非终端结点则称为分支结点 内部结点：除开根节点以外的分支结点称为内部结点 叶子结点：度== 0则称为叶子结点 结点的度：结点有几个孩子（分支） 树的度Degree：树内各节点度的最大值 树的深度/高度Depth：树中结点的最大层次 2.T性质： 3.BT性质： 4.特殊二叉树： 二、BT存储结构1.顺序二叉树 实现：按照满二叉树的结点层次编号，用数组依次存放二叉树中的数据元素，结点关系蕴含在元素的存储位置中。 缺点：深度为k的二叉树只有k个结点的单支树需要长度为2k-1的一维数组（存储空间浪费），适于存储满二叉树和完全二叉树。 12345678//顺序存储#define MAXTSIZE 100struct TreeNode { ElemType value; bool isEmpty;};TreeNode SqBiTree[MAXTSIZE];for (int i = 0; i < MAXTSIZE; ++i)...

第五章：二叉树（下） 一、树与森林1.树存储结构（1）双亲表示法：实现：定义结构数组存放树的结点，每个结点含两个域（找双亲容易、找孩子难） 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中的位置。 12345678910#define MAXTSIZE 100typedef struct PTNode { ElemType data; int parent;//双亲位置域} PTNode;typedef struct { PTNode nodes[MAXTSIZE]; int r;//根结点的位置 int n;//结点的个数} PTree; （2）孩子链表表示法：实现：将每个结点的孩子结点排列用单链表存储，而n个头指针又组成一个线性表用顺序表存储（找孩子容易、找双亲难） 123456789101112131415//孩子结点结构：child + nexttypedef struct CTNode { int child; struct CTNode...

第六章：图（上） 一、基本概念1.图G相关概念：1234Graph = (Vertex, Edge)G = (V, E)//V:顶点（数据元素）的有穷非空集合//E:边的有穷集合 无向图：每条边都是无方向的 有向图：每条边都是有方向的 完全图：任意两个点都有一条边相连 稀疏图：有很少边/弧的图 稠密图：有较多边/弧的图 网：边/弧带有权重的图 2.顶点V相关概念： 邻接：边/弧相连的两个顶点之间的关系，例如：(vi, vj)称为vi和vj互为邻接点、<vi, vj>称vi邻接到vj，vj邻接于vi 关联/依附：边/弧与顶点之间的关系，例如：(vi, vj)/<vi,...

第七章：查找 主关键字：可唯一标识记录的关键字 次关键字：用以识别若干记录的关键字 关键字的平均比较次数，平均查找长度ASL（Average Search Length） $$ASL = \sum_{i=1}^np_ic_i$$ 参数 说明 n 记录的个数 pi 查找到第i个记录的概率 ci 查找到第i个记录所需的比较次数 一、线性表的查找1.顺序查找应用范围：顺序表或线性表表示的静态查找表（表内元素无序） 12345typedef struct { ElemType *R;//表基址 int length;//表长} SSTable;//Sequential Search TableSSTable ST;//定义顺序表ST 注意到每执行一次循环都要进行两次比较， ...

第七章：查找 主关键字：可唯一标识记录的关键字 次关键字：用以识别若干记录的关键字 关键字的平均比较次数，平均查找长度ASL（Average Search Length） $$ASL = \sum_{i=1}^np_ic_i$$ 参数 说明 n 记录的个数 pi 查找到第i个记录的概率 ci 查找到第i个记录所需的比较次数 一、线性表的查找1.顺序查找应用范围：顺序表或线性表表示的静态查找表（表内元素无序） 12345typedef struct { ElemType *R;//表基址 int length;//表长} SSTable;//Sequential Search TableSSTable ST;//定义顺序表ST 注意到每执行一次循环都要进行两次比较， ...

第八章：排序 分类标准 类别1 类别2 按存储介质 内部排序：数据量不大数据在内存，无需内外存交换数据 外部排序：数据量较大数据在外存（文件排序） 按比较器个数 串行排序：单处理机（同一时刻比较一对元素） 并行排序：多处理机（同一时刻比较多对元素） 按主要操作 比较排序：使用比较的方法，包括插入排序、交换排序、选择排序、归并排序 基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置 按辅助空间 原地排序：辅助空间用量为O(1) 非原地排序 按稳定性 稳定排序：使任何数值相等的元素，排序以后相对次序不变 非稳定排序 按自然性 自然排序：输入数据越有序，排序的速度越快 非自然排序 外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。 排序稳定性只对结构类型的数据排序有意义，例如student类型 排序方法是否稳定，并不能衡量一个排序算法的优劣 123456//案例中使用的数据结构#define MAXLENGTH 50typedef struct { int...