巨白
开发工具与关键技术：数据结构与算法
作者：陈芝番
撰写时间：2020.4.23
字符串是什么？简单的理解是由数字,字母，下划线组成的一串字符。字符串为符号或数值的一个连续序列，如一串字符或二进制数字串。
1.串的定义
串是字符串的简称。在数据结构中，串是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以说串是一个有穷的字符序列。
记作：s=”s0s1…sn-1”(n≥0)
串是一种特殊的线性表，其特征体现在数据元素是一个字符。
2.串的赋值运算
算法代码实现如下：
/*将存放在字符数组t中的串常量赋给s*/
void Assign(SeqString *s, char t[])
{
int j = 0; //数组下标从0开始
for(; t[j] != '\0'; j++)
{
s->ch[j] = t[j];
}
s->ch[j] = t[j];
s->StrLength = j;
printf("%s\n", s->ch);
}/*Assign*/
3.所谓数组，是有序的元素序列。
4.如何理解二维数组？
一维数组的每个元素都是一维数组。
数组的基本操作主要包括访问和修改。
5.矩阵是一个按照长方阵列排列的复数或实数集合。
6.几种特殊矩阵
（1）零矩阵：内部元素全部为零。一般用0m*n表示
（2）方阵：对于行数和列数相等的矩阵。
（3）对角矩阵：方阵中元素A ij=0时,A是一个对角矩阵。
（4）单位矩阵：对角矩阵A的元素，A i i = 1时，A称为n阶单位矩阵。
7.树的定义
树是由n（n 》0）个节点组成的有限集合T。
如果n= 0,称为空树。
如果n>0,则满足。
有一个特定的称之为根（root）的节点，它只有直接后继，但没有直接前驱。
除根以外的其它节点划分为m（m>0）个互不相交的有限集合下，T1，T2.....,Tm,每个集合又是一棵树，并且称之为根的子树。
每颗子树的根节点有且仅有一个直接前驱，但可以有0个或多个直接后继。
树是由n（n》0）个节点构成的有限集合T，当n= 0时T称为空树；否则，在任一非空树T中：
（1）有且仅有一个特定的节点，它没有前驱节点，称其为根节点；
（2）剩下的节点可分为m（m》0）个互不相交的子集T1，T2，......，Tm,其中每个子集本身又是一棵树，并称其为根的子树。
注：树的定义具有递归性，即“树中还有树”。
树的递归定义揭示出了树的固有特性。
注：由于子树的互不相交性，树中每个节点只属于一棵树（子树），且树中的每一个节点都是该树中某一棵子树的根。
8.树的表示方法
（1）直观（树形，倒置树）表示法
（2）嵌套集合（文氏图）表示法
（3）凹入表（缩进）表示法
（4）广义表（嵌套括号）表示法
满二叉树：深度为K，且有2^n-1
特点：每一层上的节点都是最大的节点。
完全二叉树：深度为K，有n个节点，每一个节点都与深度为K的满二叉树中编号从1至N的节点的节点一一对应。
特点：叶子节点只可能在层次最大的两层出现。
注：满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。
9.先根遍历二叉树
例1：
取三种遍历次序:
先根遍历：A>B>D>C
中根遍历：B>D>A>C
后根遍历：D>B>C>A
例2：
【1】先根遍历二叉树的递归定义为:
若二叉树为空，则空操作；
否则，
（1）访问根节点（T）;
（2）先根遍历左子树（L）；
（3）先根遍历右子树（R）；
遍历结果：A>B>D>E>H>I>J>K>C>F>G
先根遍历的递归算法：
Void preOrderIter（struct node * root）
{
If （root == Null）return;
Stack<struct node * > s;
S. push（root）;
While（！S.empty（））
{
Struct node * nd = s.top（）；
Cout << nd ->data << “”；
s.pop（）；
If（nd->right !=NULL）
s.push（nd->right）;
If（nd->left !=NULL）
S.push（nd->left）;
}
Cout << end1;
}
【2】中根遍历二叉树的递归定义为:
若二叉树为空，则空操作；
否则，
（4）中根遍历左子树（L）；
（5）访问根节点（T）;
（6）中根遍历右子树（R）；
遍历结果：D>B>H>E>J>I>K>A>F>C>G
中根遍历的递归算法：
【3】后根遍历二叉树的递归定义为:
若二叉树为空，则空操作；
否则，
（7）后根遍历左子树（L）；
（8）后根遍历右子树（R）；
（9）访问根节点（T）;
遍历结果：D>H>J>K>I>E>B>F>G>C>A
后根遍历的递归算法：
Void PostOrder（BiTree bt）{
If(bt){
PostOrder(bt->lchild);
PostOrder(bt->rchild);
Cout<<bt->data<<“”;
}
}
10.哈夫曼树的基本概念：
路径长度：两个节点之间路径长度是连接两节点的路径的分支树。
树的路径长度：根节点到各节点的路径之和。
具有不同路径长度的二叉树
节点的带权路径长度
从根节点到某节点的路径长度与该节点所带的权值的乘积。
树的带权路径长度
树的所有叶子节点带权路径长度之和：
Wk表示第K个节点的权值
Lk指的是K这个节点到根节点的路径长度
哈夫曼树：假设有N个权值{W1，W2，......,Wn}是构造有N个叶子节点的二叉树，每个叶子节点拥有一个权值W，则其中带权路径长度为WPL最小二叉树，称为最优二叉树或哈夫曼树。
哈夫曼树中，权值最大节点离根最近
特点：哈夫曼树中没有度为1的节点。
感悟：
字符串，数组与二叉树之间存在必然的关系，一个二叉树可以转换成一个由括号和整数组成的字符串。而且字符串与原始二叉树之间存在一对一映射关系的空括号对。对字符串与数组基本定义深入理解，真正做到知其然，也知其所以然。遇到问题尽量自己动手解决，上网查资料或请教别人，但是要自己动手才会真正了解和学会。
作者：陈芝番
撰写时间：2020.4.23
字符串是什么？简单的理解是由数字,字母，下划线组成的一串字符。字符串为符号或数值的一个连续序列，如一串字符或二进制数字串。
1.串的定义
串是字符串的简称。在数据结构中，串是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以说串是一个有穷的字符序列。
记作：s=”s0s1…sn-1”(n≥0)
串是一种特殊的线性表，其特征体现在数据元素是一个字符。
2.串的赋值运算
算法代码实现如下：
/*将存放在字符数组t中的串常量赋给s*/
void Assign(SeqString *s, char t[])
{
int j = 0; //数组下标从0开始
for(; t[j] != '\0'; j++)
{
s->ch[j] = t[j];
}
s->ch[j] = t[j];
s->StrLength = j;
printf("%s\n", s->ch);
}/*Assign*/
3.所谓数组，是有序的元素序列。
4.如何理解二维数组？
一维数组的每个元素都是一维数组。
数组的基本操作主要包括访问和修改。
5.矩阵是一个按照长方阵列排列的复数或实数集合。
6.几种特殊矩阵
（1）零矩阵：内部元素全部为零。一般用0m*n表示
（2）方阵：对于行数和列数相等的矩阵。
（3）对角矩阵：方阵中元素A ij=0时,A是一个对角矩阵。
（4）单位矩阵：对角矩阵A的元素，A i i = 1时，A称为n阶单位矩阵。
7.树的定义
树是由n（n 》0）个节点组成的有限集合T。
如果n= 0,称为空树。
如果n>0,则满足。
有一个特定的称之为根（root）的节点，它只有直接后继，但没有直接前驱。
除根以外的其它节点划分为m（m>0）个互不相交的有限集合下，T1，T2.....,Tm,每个集合又是一棵树，并且称之为根的子树。
每颗子树的根节点有且仅有一个直接前驱，但可以有0个或多个直接后继。
树是由n（n》0）个节点构成的有限集合T，当n= 0时T称为空树；否则，在任一非空树T中：
（1）有且仅有一个特定的节点，它没有前驱节点，称其为根节点；
（2）剩下的节点可分为m（m》0）个互不相交的子集T1，T2，......，Tm,其中每个子集本身又是一棵树，并称其为根的子树。
注：树的定义具有递归性，即“树中还有树”。
树的递归定义揭示出了树的固有特性。
注：由于子树的互不相交性，树中每个节点只属于一棵树（子树），且树中的每一个节点都是该树中某一棵子树的根。
8.树的表示方法
（1）直观（树形，倒置树）表示法
（2）嵌套集合（文氏图）表示法
（3）凹入表（缩进）表示法
（4）广义表（嵌套括号）表示法
满二叉树：深度为K，且有2^n-1
特点：每一层上的节点都是最大的节点。
完全二叉树：深度为K，有n个节点，每一个节点都与深度为K的满二叉树中编号从1至N的节点的节点一一对应。
特点：叶子节点只可能在层次最大的两层出现。
注：满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。
9.先根遍历二叉树
例1：
取三种遍历次序:
先根遍历：A>B>D>C
中根遍历：B>D>A>C
后根遍历：D>B>C>A
例2：
【1】先根遍历二叉树的递归定义为:
若二叉树为空，则空操作；
否则，
（1）访问根节点（T）;
（2）先根遍历左子树（L）；
（3）先根遍历右子树（R）；
遍历结果：A>B>D>E>H>I>J>K>C>F>G
先根遍历的递归算法：
Void preOrderIter（struct node * root）
{
If （root == Null）return;
Stack<struct node * > s;
S. push（root）;
While（！S.empty（））
{
Struct node * nd = s.top（）；
Cout << nd ->data << “”；
s.pop（）；
If（nd->right !=NULL）
s.push（nd->right）;
If（nd->left !=NULL）
S.push（nd->left）;
}
Cout << end1;
}
【2】中根遍历二叉树的递归定义为:
若二叉树为空，则空操作；
否则，
（4）中根遍历左子树（L）；
（5）访问根节点（T）;
（6）中根遍历右子树（R）；
遍历结果：D>B>H>E>J>I>K>A>F>C>G
中根遍历的递归算法：
【3】后根遍历二叉树的递归定义为:
若二叉树为空，则空操作；
否则，
（7）后根遍历左子树（L）；
（8）后根遍历右子树（R）；
（9）访问根节点（T）;
遍历结果：D>H>J>K>I>E>B>F>G>C>A
后根遍历的递归算法：
Void PostOrder（BiTree bt）{
If(bt){
PostOrder(bt->lchild);
PostOrder(bt->rchild);
Cout<<bt->data<<“”;
}
}
10.哈夫曼树的基本概念：
路径长度：两个节点之间路径长度是连接两节点的路径的分支树。
树的路径长度：根节点到各节点的路径之和。
具有不同路径长度的二叉树
节点的带权路径长度
从根节点到某节点的路径长度与该节点所带的权值的乘积。
树的带权路径长度
树的所有叶子节点带权路径长度之和：
Wk表示第K个节点的权值
Lk指的是K这个节点到根节点的路径长度
哈夫曼树：假设有N个权值{W1，W2，......,Wn}是构造有N个叶子节点的二叉树，每个叶子节点拥有一个权值W，则其中带权路径长度为WPL最小二叉树，称为最优二叉树或哈夫曼树。
哈夫曼树中，权值最大节点离根最近
特点：哈夫曼树中没有度为1的节点。
感悟：
字符串，数组与二叉树之间存在必然的关系，一个二叉树可以转换成一个由括号和整数组成的字符串。而且字符串与原始二叉树之间存在一对一映射关系的空括号对。对字符串与数组基本定义深入理解，真正做到知其然，也知其所以然。遇到问题尽量自己动手解决，上网查资料或请教别人，但是要自己动手才会真正了解和学会。
