算法与数据结构知识点总结.docx

算法与数据结构知识点总结
算法与数据结构知识点总结

4学习目标
1.熟练掌握基本的数据结构
2.理解相关操作的算法实现
3.掌握算法的复杂度分析方法
4.领会从数据结构的设计和实现角度优化解决实际问题的思想

4相关术语&基础知识
1.数据、数据元素
数据：对客观事物的符号表示，所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素：组成数据的、具有意义的基本单位，计算机中通常作为整体处理。
2.数据项
组成数据的不可分割的最小单位
3.数据对象
性质相同的数据元素的集合，是数据的子集
4.逻辑结构
数据对象中数据元素之间的逻辑关系；是从操作对象抽象出来的数学模型

5.物理结构（存储结构）
数据元素逻辑关系在计算机中的表示（映像）；包括数据元素的表示和逻辑关系的表示；关系到数据操作的实现

6.数据类型
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
7.抽象数据类型（ADT）
是指一个数据模型以及定义在该模型上的一组操作。
三要素：数据元素、逻辑关系、操作
8.算法的设计原则
正确性、可读性、健壮性、高效率与低存储量
9.算法效率的度量

10.常见结构的时间复杂度★
（1）顺序结构 O(1)
（2）分支结构 O(1)
（3）循环结构的时间复杂度 = 循环体内语句的频度(重复执行次数)
11.时间复杂度的计算
时间复杂度的简化求解步骤
step 1. 定位最深层循环
step 2. 由内向外逐层计算循环体的执行频度
step 3. 只保留最高阶项
step 4. 去掉最高阶项系数
得到的结果即为时间复杂度的大O阶。

12.时间复杂度的大小关系★

13.影响空间复杂度的因素
（1）程序本身所占空间
（2）输入数据所占空间
（3）辅助变量所占空间
若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

4对知识掌握的四种程度
1.了解：选择题
2.理解：知道原理，题里可能有拐弯的地方
3.掌握：算法语句填空
4.熟练掌握：整...个...算...法...
PS：以下，“要求”会展开详细内容；若无必要，“考点”不展开详细内容。

一、线性表

=考点：
1.线性表的逻辑结构和各种存储表示方法
2.定义在逻辑结构上的各种基本运算（知道名字即可）
InitList（*L）
操作结果：初始化一个空的线性表L。
DestroyList（*L）
初始条件：线性表L 已经存在。
操作结果：销毁线性表L。
ClearList（*L）
初始条件：线性表L 已经存在。
操作结果：将L 清空为空表。
ListEmpty（L）
初始条件：线性表L 已经存在。
操作结果：若L 为空返回true，否则返回false。
ListLength（L）
初始条件：线性表L 已经存在。
操作结果：返回线性表L 的元素个数。
GetElem（L，i，*e）
初始条件：线性表L 已经存在，i∈[1, ListLength ( L )]。
操作结果：将L 中第i 个位置的元素返回给e。
LocateElem（L，e，compare ( )）
初始条件：线性表L 已经存在。
操作结果：在L 中查找与给定值e 满足关系compare ( ) 的元素，无参数compare()默认为相等关系，找到后返回其第一个元素的位序，查找失败返回0。
ListInsert（L，i，e）
初始条件：线性表L 已经存在，i∈[1, ListLength ( L )+1]。
操作结果：在L 中第i 个位置插入新元素e，L 的长度加1。
ListDelete（L，i，*e）
初始条件：线性表L 已经存在且非空，i∈[1, ListLength ( L )]。
操作结果：删除L 中第i 个位置元素，并用e 返回其值，L 的长度减1。
3.在各种存储结构上如何实现这些基本运算
4.各种基本运算的时间复杂性

=要求：
1.理解两种存储结构各自的特点、优缺点、适用范围
2.熟练掌握顺序表和单链表上建表、插入、删除、查找操作的算法实现及相关的复杂度分析
⑴顺序表
①建表
Status ListCreat(SqList * L) /*从屏幕逐位读入数据生成顺序表*/
{
int n , i;
printf("请输入顺序表L 的数据个数：\n") ;
scanf("%d", &n) ;
if (n > MAXSIZE)
{
printf("\n 数据个数过长，请不要超过%d！\n",MAXSIZE);
return ERROR;
}
else if(n<0)
{
printf("\n输入不合法\n");
return ERROR;
}
for(i=0 ; i < n ; i++)
{
printf("data[%d] =" , i) ;
scanf("%d",&((*L).data[i]));
}
(*L).length=n;
printf("\n") ;
return OK;
}
时间复杂度：O(n)

②插入
/* 初始条件：线性表L 已经存在，i∈[1, ListLength ( L )] */
/* 操作结果：将L 中第i 个位置插入新元素e，L 长度加1 */
int ListInsert{ SqList L, int i , ElemType e}
{
int k;
if ( L.length == MAXSIZE) /*顺序表已满*/
return ERROR;
if ( i < 1 || i > L.length + 1 ) /* i 不合法 */
return ERROR；
if ( i <= L.length ) /* 插入位置不在表尾 */
{
for ( k = L.length – 1; k >=i-1; k-- )
L.data [k+1] = L.data [k]; /* 从后向前逐位后移 */
}
L.data [i-1] = e; /* 插入新元素e */
L.length++;
return OK;
}
时间复杂度：最好O(1) 最坏O(n) 平均O(n) （依赖于插入位置i、表长n）

③删除
/* 初始条件：线性表L 已经存在，i∈[1, ListLength ( L )] */
/* 操作结果：将L 中第i 个位置元素删除，并用e 返回该元素的值，L长度减1 */
int ListDelete{ SqList L, int i , ElemType *e}
{
int k;
if ( L.length == 0 ) /*顺序表为空*/
return ERROR;
if ( i < 1 || i > L.length ) /* i 不合法 */
return ERROR；
*e = L.data [i-1]; /* 用e 返回删除元素的值 /
if ( i < L.length ) /* 删除位置不是表尾 */
{
for ( k =i; k < length; k++ )
L.data [k-1] = L.data [k]; /*删除位置后继元素逐一前移*/
}
L.length--;
return OK;
}
时间复杂度：最好O(1) 最坏O(n) 平均O(n) （依赖于插入位置i、表长n）

④查找（按位获取操作）
# define OK 1
# define ERROR 0
/* 初始条件：线性表L 已经存在，i∈[1, ListLength ( L )] */
/* 操作结果：将L 中第i 个位置的元素返回给e */
int GetElem{ SqList L, int i , ElemType *e}
{
if ( L.length == 0 || i <1 || i > L.length)
return ERROR;
*e = L.data [i-1];
return OK;
}
时间复杂度：O(1)

⑵单链表
①建表
Node* ListCreatTail() /*尾插法建立带头结点的单链表，链表长度为n，链表元素从屏幕读取,返回头结点位置*/
{
LinkList p,r,L;
int n,i;
ElemType d;
L = (LinkList)new Node;
printf("\n请输入链表L 的数据个数：\n") ;
scanf("%d", &n) ;
L->data = n;
L->next = Null;
r = L;
for(i=1 ; i <= n ; i++)
{
p = (Node*) new Node;
printf("结点%d =" , i) ;
scanf("%d",&d);
p->data = d;
p->next = Null;
r->next = p;
r = p;
printf("\nNode%d=%d\n",i,p->data);
}
printf("\n") ;
return L;
}
时间复杂度：O(n)

②插入
链表的插入：一定，二建，三后，四前
Status ListInsert{ LinkList L, int i , ElemType e}
{
Node * p, *q;
p = GetElem ( L, i-1 );
if ( p == Null) /*链表为空*/
return ERROR;
q = (Node*) malloc (sizeof (Node));
q->data = e;
q–>next = p–>next;
p–>next = q;
return OK;
}
时间复杂度： O (1)

③删除
链表的删除：一定，二连，三放
Status ListDelete { LinkList L, int i , ElemType *e}
{
Node * p, *q;
p = GetElem ( L, i-1 );
if ( p == Null || p -> next ==Null ) /*链表为空*/
return ERROR;
q = p -> next;
*e = q->data;
p–>next = q->next;
free (q);
return OK;
}
时间复杂度： O (1)

④查找
a.按位获取
//链表不是随机存取结构
Node * GetElem{ LinkList L, int i }
{
int k; /* k 为计数器 */
LinkList p; /* 指针p 指向当前结点 */
p = L; /* 指针p 指向头结点 */
k = 1;
while ( p && k<i )
{
p = p -> next; /* p 指向下一个结点 */
++k; /* 计数器加1 */
}
if ( k==i ) /* 结点i 存在 */
return p;
else
return Null;
}
时间复杂度：最好O (1) 最坏O(n)

b.按值获取
/* 初始条件：线性表L 已经存在*/
/* 操作结果：定位L 中与给定值相等的元素，返回其位置*/
Node * LocateElem{ LinkList L, ElemType e }
{
LinkList p; /* 指针p 指向当前结点 */
p = L; /* 指针p 指向头结点 */
while ( p && p -> data != e )
p = p -> next; /* p 指向下一个结点 */
if ( !p) /* 结点i 不存在 */
return Null;
else
return p;
}
时间复杂度：最好O (1) 最坏O(n)

3.了解双向链表和循环链表的定义和特点及插入、删除操作的实现（见书和PPT）

二、栈和队列

=考点：
1.栈和队列的逻辑结构和两种存储表示方法
2.定义在逻辑结构上的各种基本运算
InitStack（&S）
操作结果：初始化一个空的栈S。
DestroyStack（&S）
初始条件：栈S已经存在。
操作结果：销毁栈S。
ClearStack（&S）
初始条件：栈S已经存在。
操作结果：将栈S清空。
StackEmpty（S）
初始条件：栈S已经存在。
操作结果：若栈S为空返回true，否则返回false。
StackLength（S）
初始条件：栈S已经存在。
操作结果：返回栈S的元素个数。
GetTop（S，&e）
初始条件：栈S已经存在且非空。
操作结果：将S的栈顶元素返回给e。
Push（&S，e）
初始条件：栈S已经存在且非空。
操作结果：新元素e入栈。
Pop（&S，&e）
初始条件：栈S已经存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。

3.在各种存储结构上如何实现这些基本运算
4.各种基本运算的时间复杂性
5.栈的常用应用

=要求：
1.理解栈和队列的异同点、栈和队列与一般线性表的不同
2.了解顺序栈的溢出和顺序队列的假溢问题
⑴顺序栈的溢出
①上溢（overflow）：栈满时再压入数据
②下溢（underflow）：栈空时再弹出数据

栈满：S.top == MAXSIZE – 1
空栈：S.top == – 1

3.熟练掌握顺序栈（两栈共享空间）、链栈、循环队列、链队列上的队列初始化、元素插入、删除的算法实现及相关的复杂度分析
⑴顺序栈（两栈共享空间）初始化
Status InitDuStack(Sqstack &S)
{
S.top1==-1;
S.top2==MAXSIZE;
return OK;
}
时间复杂度O(1)

⑵顺序栈（两栈共享空间）元素插入
/* 新元素e 入栈 */
Status Push{ SqDuStack S , SElemType e, int StackNum}
{
if ( S.top1 + 1 == S.top2 ) /* 栈满 */
return ERROR;
if ( StackNum == 1) /* 新元素压入栈1 */
S.top1 ++;
S.data[S.top1] == e; /* 新元素入栈 */
return OK;
else if (StackNum == 2)
S.top2 --;
S.data[S.top2] == e; /* 新元素入栈 */
return OK;
else return ERROR;
}
时间复杂度O(1)

⑶顺序栈（两栈共享空间）元素删除[来自网络]
//若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status Pop(SqDuStack *S , ElemType *e , int stackNumber)
{
if(stackNumber == 1)
{
if(S->top1 == 1)
return ERROR; //说明栈1已经是空栈，溢出
*e = S->data[s->top1--]; //将栈1的栈顶元素出栈
}
else if(stackNumber == 2)
{
if(S->top2 == MAXSIZE)
return ERROR; //说明栈2已经是空栈，溢出
*e = S->data[S->top2++]; //将栈2的栈顶元素出栈
}
return OK;
}
时间复杂度O(1)

⑷链栈初始化[来自网络]
void InitLinkStack (linkStack &S)
{
       S=new SNode;
       S->next=NULL;
}
时间复杂度O(1)

⑸链栈元素插入
/* 新元素e 入栈 */
Status Push ( LinkStack *S , SElemType e )
{
SNode *p = ( SNode * ) malloc ( sizeof (SNode) ); /* 动态申请结点*/
p->data = e; /* 结点赋值 */
p->next = S->top; /* 新结点插到表头 */
S->top = p; /* 栈顶指针改为新结点*/
S->length ++;
return OK;
}
时间复杂度O(1)

⑹链栈元素删除
/* 栈顶元素出栈 */
Status Pop ( LinkStack *S , SElemType *e )
{
StackNode *p;
if (StackEmpty(*S))
return ERROR;
p = S->top; /* p 指向出栈结点*/
*e = p->data; /* 返回栈顶元素 */
S->top = p->next; /* 栈顶指针下移*/
free(p); /* 释放结点空间*/
S->length --;
return OK;
}

（7）循环队列的初始化
/* 队列初始化 */
Status IntiQueue ( SqQueue *Q )
{
Q->front = 0;
Q->rear = 0;
return OK;
}
/* 求队列长度 */
int QueueLength (SqQueue Q )
{
return (Q.rear – Q.front + MAXSIZE) % MAXSIZE;
}
时间复杂度O（1）

（8）循环队列元素插入
/* 新元素e 入队列 */
Status EnQueue (SqQueue *Q , QElemType e)
{
if ((Q->rear+1)% MAXSIZE == Q->front)
return ERROR; /* 队满 */
Q->data[Q->rear] = e; /* 新元素入队 */
Q->rear = (Q->rear +1) % MAXSIZE; /* rear 指针后移，若到最后则转到数组头部 */
return OK;
}
时间复杂度O（1）

（9）循环队列元素删除[由书P65修改]
//队头元素出队
Status DeQueue (SqQueue *Q, QElemType e)
{
if(front==rear) return ERROR; /* 队空 */
e=Q->data[Q->front];
Q->front = (Q->front +1) % MAXSIZE; /* front 指针后移，若到最后则转到数组头部 */
   return OK;
  }

（10）链队列的初始化
Status InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = ( QNode * ) malloc ( sizeof (QNode) );
if (!Q.front) exit(OVERFLOW);
Q.front->next = NULL;
return OK;
}
时间复杂度O（1）

（11）链队列的元素插入
//* 新元素e 入队列 */
Status EnQueue( LinkQueue *Q , QElemType e )
{
QNode *p = ( QNode * ) malloc ( sizeof (QNode) ); /* 动态申请结点,C 语言*/
// QNode *p = New QNode; /* 动态申请结点, C++*/
if (!p) /*存储分配失败*/
exit(OVERFLOW);
p->data = e; /* 结点赋值 */
p->next = Null;
Q->rear->next = p; /* 新结点插到队尾 */
Q->rear = p; /* 新结点设置为队尾 */
return OK;
}
时间复杂度O（1）

（12）链队列的元素删除
/* 队头元素出队列 */
Status DeQueue( LinkQueue *Q , QElemType *e )
{
QNode *p;
if (Q->front == Q->rear) /* 队空 */
return ERROR;
p = Q->front->next; /* p 指向要出队元素所在结点 */
*e = p->data; /*用e 返回出队元素 */
Q->front->next = p->next; /* 头结点指向出队元素的下一个结点 */
if (Q->rear ==p) /* 出队前只有一个元素 */
Q->rear = Q->front;
free (p);
return OK;
}
时间复杂度O(1)

4.了解栈的常用应用，理解利用栈实现递归的原理，掌握逆波兰式的生成和计算
（1）栈的常用应用：数值转换、括号匹配、算术表达式求解、迷宫求解、实现递归
（2）利用栈实现递归的原理：见 栈和队列3 课件
（3）逆波兰式生成和计算
逆波兰表示：所有的符号都在运算数字后面出现
例：9 +（3 – 1）*3+10 / 2 中缀表示法
　　9 3 1 – 3 * + 10 2 / + 后缀表示法，不再需要括号
计算：
遇到数字就进栈
见到符号就运算
运算结果也进栈
最终结果栈底见
生成：
遇到数字就输出
符号进栈要比较
低级平级都得等
高于栈顶才能进
左边括号等匹配
右括号来了一起闪

三、串

=考点：
1.串的逻辑结构和两种存储表示方法
2.堆存储串的基本运算及复杂度分析

3.串的模式匹配

=要求：
1.理解串与线性表的不同（数据对象、操作对象）
串： 数据对象：字符集 操作对象：子串
线性表：数据对象：集合 操作对象：线形表
2.掌握串的复制操作的算法及复杂度分析

3.理解串的模式匹配思想及两种基本的模式匹配算法，掌握next数组的计算方法

（1）Brute Force算法——朴素匹配算法
思路:从主串S第i位开始的m位字符串，依次与T第1位-第m位比较，若相等，返回比较之前的i值；否则i退回，从下一位开始比较；如果从S的所有位开始都不能成功匹配T，返回0.
int Index ( SString S, SString T)
{
int i = 1, j =1;
while (i<=S[0] && j<=T[0])
{
if (S[i] == T[j] ) { i++; j++;} // 比较T 中下一字符
else { i = i –j+2; j=1;} // i 回溯，j 回溯，重新开始匹配
}
if ( j >T[0] ) return i-T[0];
else return 0;
}
时间复杂度 O(m*n) 最坏：m(n-m+1)

（2）KMP算法(克努特—莫里斯—普拉特算法)
思路：失配时，i不回溯，T尽量多滑动一段距离
int Index_KMP ( SString S, SString T)
{
int i = 1, j =1;
while (i<=S[0] && j<=T[0])
{
if (S[i] == T[j] || j == 0) { i++; j++;} // 比较T 中下一字符
else { j=next[j];} //j 回溯，重新开始匹配
}
if ( j >T[0] ) return i-T[0];
else return 0;
}

(3)next数组的计算

void get_next ( SString T, int next[])
{
int i = 1;
next[1] = 0;
j=0;
while (i<T[0])
{
if (j == 0||T[i] == T[j]) { i++; j++; next[i] = j;}
else { j=next[j];} //j回溯，重新开始匹配
}
}
（这个算法了解即可，重要是填上面那张图里的next数组的表）

四、树

=考点：
1.树、森林的基本概念、名词术语
2.树、树林与二叉树之间的转换、先序遍历、后序遍历
3.二叉树的逻辑特点、基本概念、几类特殊的二叉树
4.二叉树的基本性质
5.二叉树的顺序存储和二叉链表存储
6.二叉树的先序遍历、中序遍历、后序遍历和层次遍历
7.线索二叉树的概念、意义，二叉树的线索化、线索二叉树的遍历；
8.哈夫曼树的构造与带权路径长度(WPL)

=要求：
1.掌握树、森林、二叉树的相关概念
树：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：
（1）有且仅有一个特定的称为根(Root) 的结点；
（2）其余的结点可分为m(m>=0) 个互不相交的子集T1,T2,T3…Tm, 其中每个子集又是一棵树，并称其为子树(Subtree) 。
森林：互不相交的树的集合
二叉树：由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。是有序数。
树结点：包含一个数据元素及若干指向子树的分支
孩子结点：结点的子树的根称为该结点的孩子
双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲
兄弟结点：同一双亲的孩子结点
堂兄结点：同一层上结点
结点层次：根结点所在层为第一层；下一层为第二层，依此类推
树的高（深）度： 树中最大的结点层
结点的度：结点子树的个数
树的度：树中最大的结点度
叶子结点：也叫终端结点，是度为0的结点
分枝结点：度不为0的结点（非终端结点）
有序树：子树有序的树，如：家族树
无序树：不考虑子树的顺序

2.理解二叉树的基本性质
性质1： 在二叉树的第 i 层上至多有2i-1 个结点。
性质2： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）。
性质3： 对任何一棵二叉树，若它含有n0 个叶子结点、 n2 个度为 2 的结点，则必存在关系式： n0 = n2+1。
性质4：具有 n 个结点的完全二叉树的深度为 ëlog2nû+1.
性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i（1<=i<=n),有：
（1）如果i＝1， 则结点i无双亲，是二叉树的根；如果i>1， 则其双亲的编号是 i/2(整除）。
（2）如果2i>n， 无左孩子；否则，其左孩子是结点2i。
（3） 如果2i＋1>n， 则结点i无右孩子；否则，其右孩子是结点2i＋1。

3.掌握二叉树的两种存储结构
（1）顺序存储结构
用一组地址连续的存储单元存储二叉树中的数据元素
按照完全二叉树的编号顺序存储在一维数组中
一般二叉树可能浪费大量存储空间（可采用扩展二叉树）

（2）链式存储结构：
二叉链表
三叉链表

4.熟练掌握二叉树的四种遍历方法，以及二叉链表存储结构下的各种遍历算法的实现
(1)层序[来自网络]
void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{
/* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。*/
/* 层序遍历二叉树T算法(利用队列)，对每个数据元素调用函数Visit */
SqQueue q;
QElemType p;
if(T)
{
InitQueue(&q);
EnQueue(&q,T);
while(!QueueEmpty(q))
{
DeQueue(&q,&p);
Visit(p->data);
if(p->lchild!=NULL) EnQueue(&q,p->lchild);
if(p->rchild!=NULL) EnQueue(&q,p->rchild);
}
printf("/n");
}
}

（2）先序：先遍历根结点，再遍历左子树，最后遍历右子树。
PreOrderTraversal( BiTree T)
{
if(T!=NULL)
{
printf(“%c/n”,T->data);
PreOrderTraversal(T->lchild);
PreOrderTraversal(T->rchild);
}
else return;
}

(3)中序：先遍历左子树，再遍历根结点，最后遍历右子树。
InOrderTraversal( BiTree T)
{
if(T!=NULL)
{
InOrderTraversal(T->lchild);
printf(“%c/n”,T->data);
InOrderTraversal(T->rchild);
}
else return;
}

(4)后序：先遍历左子树， 再遍历右子树， 最后遍历根结点。
PostOrderTraversal( BiTree T)
{
if(T!=NULL)
{
printf(“%c/n”,T->data);
PostOrderTraversal(T->lchild);
PostOrderTraversal(T->rchild);
}
else return;
}

5.理解通过遍历序列确定二叉树的方法，掌握先序序列输入下的二叉树的生成算法的实现
(1)通过两个遍历序列确定二叉树的方法（重要）:
先序+中序；后序+中序
（大家自己找例子做一下这种题吧，这个挺重要的）
(2)先序序列输入下的二叉树的生成算法
void CreatBiTree (BiTree T)
{
TElemType ch;
scanf (“%c”,&ch);
if ( ch == ‘#’)
*T = Null;
else
{
*T = (BiTree) malloc(sizeof(BiTNode));
if (!*T) exit(OVERFLOW); // 结点空间申请失败
(*T)->data = ch; /生成根结点
CreatBiTree (&(*T)->lchild); //构造左子树
CreatBiTree(&(*T)->rchild); //构造右子树
}
}

6.理解二叉树中序线索化的步骤及线索二叉树的遍历步骤，掌握中序线索链表的画法，
(1)二叉树中序线索化：
①建立二叉树
②遍历二叉树，在遍历过程中修改空指针为前驱或后继结点（借助一个指针指向当前访问结点的前驱）

(2)线索二叉树的遍历：
① p=T->lchild; p指向线索链表的根结点；
②若线索链表非空，循环：
（a）顺着p左孩子指针找到最左下结点；访问之；
（b）若p所指结点的右孩子域为线索， p的右孩子结点即为后继结点循环： p=p->rchild； 并访问p所指结点；
（c） 一旦线索“中断”，p所指结点的右孩子域为右孩子指针， p=p->rchild， 使 p指向右孩子结点；

(3)中序线索链表的画法：

7.掌握哈夫曼树的构造过程及带全路径长度的计算
(1)哈夫曼树的构造过程：
1)根据给定的n个权值，构造n棵只有一个根结点的二叉树，n个权值分别是这些二叉树根结点的权。设F是由这n棵二叉树构成的集合
2)在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和；
3)从F中删除这两颗树，并将新树加入F；
4)重复 2) 和3)，直到F中只含一颗树为止；
(2)树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 li
结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积

五、图

=考点：
1.图的逻辑结构、相关概念及术语
2.图的邻接矩阵和邻接表、逆邻接表存储方法
3.图的深度优先搜索DFS与广度优先搜索BFS
4.最小生成树、最短路径、AOV网与拓扑排序、AOE网与关键路径

=要求：
5.理解图的逻辑结构、分类及相关术语
图G 由两个集合V 和E 组成，记作 G=(V, E)
n V 是顶点的有穷非空集合
nE 是V 中顶点偶对的有穷集,这些顶点偶对称边 。
n E 可以为空集，若E为空，则图G 只有顶点没有边

(1) 顶点和边(弧)
n 线性表中把数据元素叫做元素，树中叫结点，在图中叫做 顶点（Vertex ） 。
n 线性表可以没有元素（空表），树可以没有结点（空树），而图是非空的。
n 图中顶点之间是多对多的关系，用边表示
n 无向边(Edge) ：顶点vi 和vj 之间的边没有方向
n 用无序偶表示(vi, vj)
n 有向边( 弧Arc) ：顶点vi 和vj 之间的边有方向
n 用有序偶表示<vi, vj>
n vi 称为为弧的 起点( 弧尾) ，vj 称为弧的终点( 弧头)

(2) 有向图和无向图
在图G 中，如果代表边的顶点偶对是无序的，则称G为无向图 ，否则为有向图。

(3) 简单图
在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称为简单图。
(4) 邻接点
n 在无向图中 ， 若存在一条边 （Vi, Vj ） ， 则称Vi 和Vj 互为邻接点（Adjacent ）
n 边 （vi ，vj ） 与顶点vi 和vj 相关联
n 在有向图中 ， 若存在一条弧<V i , V j > ， 称V i邻接到V j ，V j 邻接自V i ，V i 和V j 互为邻接点 。
(5) 顶点的度、入度和出度
n 在无向图中，与顶点v 相邻接的边数称为 该顶点的度 ，记为D(v) 。
n 在有向图中，顶点v 的度又分为 入度 和 出度 两种：
n 以顶点v 为终点( 弧头) 的弧的数目称为顶点v 的 入度 ，记为ID(v) ；
n 以顶点