Polaris-hzn8

第四章：串与数组 一、串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,...

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