第1章 绪论
1.数据结构的定义
数据－＞数据元素 －＞数据项数据结构是指数据以及相互之间的联系。包括：
（1）数据的逻辑结构。
（2）数据的存储结构（物理结构）。
（3）施加在该数据上的运算。
数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。
数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。但运算的实现与数据的存储结构有关。
逻辑结构主要有两大类：
（1）线性结构
（2）非线性结构：
1）树形结构
2）图形结构存储结构分为如下四种：
（1）顺序存储方法
（2）链式存储方法
（3）索引存储方法
（4）散列存储方法
2.抽象数据类型
抽象数据类型（Abstract Data Type简写为ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。
3.什么是算法
算法是对特定问题求解步骤的一种描述，它是指令的有限序列 。
算法的五个重要的特性,
（1）有穷性 （2）确定性 （3）可行性 （4）有输入 （5）有输出
4.算法分析
(1)算法的时间复杂度：是指其基本运算在算法中重复执行的次数。
算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作：
T(n)=O(f(n))
记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。
(2)算法空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度 。
对于空间复杂度为O(1)的算法称为原地工作或就地工作算法。
第2章 线性表
1.线性表的定义
线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n≥0。当n=0时，表示线性表是一个空表，即表中不包含任何元素。
1.线性表的顺序存储结构—顺序表
typedef struct
{ ElemType elem[MaxSize]; /*存放顺序表元素*/
int length; /*存放顺序表的长度*/
} SqList;
顺序表基本运算的实现
插入数据元素算法：元素移动的次数不仅与表长n有关 ；插入一个元素时所需移动元素的平均次数 n／2。平均时间复杂度为O(n)。
删除数据元素算法:元素移动的次数也与表长n有关 。删除一个元素时所需移动元素的平均次数为(n-1)/2。删除算法的平均时间复杂度为O(n)。
【例2.1】 设计一个算法，将x插入到一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。
void Insert(SqList &A,ElemType x)
{ int i=0,j;
while (i<A.length && AS.elem[i]<x) i++;
for (j=A.length-1;j>=i;j--)
A.elem[j+1]=A.elem[j];
A.elem[i]=x;
A.length++; }
2.线性表的链式存储结构—链表
定义单链表结点类型:
typedef struct LNode
{ ElemType data;
struct LNode *next; /*指向后继结点*/
} LinkList;
定义双链表结点类型:
typedef struct DNode
{ ElemType data;
struct DNode *prior; /*指向前驱结点*/
struct DNode *next; /*指向后继结点*/
} DLinkList;
（1）单链表基本运算的实现
重点：头插法建表和尾插法建表算法，它是很多算法设计的基础。
【例2.1】 设C={a1,b1,a2,b2,…,an,bn}为一线性表，采用带头结点的hc单链表存放，编写一个就地算法，将其拆分为两个线性表，使得,A={a1,a2,…,an}，C={b1,b2,…,bn}
void fun(LinkList *hc,LinkList *&ha,LinkList *&hb)
{ LinkList *p=hc->next,*ra,*rb;
ha=hc; /*ha的头结点利用hc的头结点*/
ra=ha; /*ra始终指向ha的末尾结点*/
hb=(LinkList *)malloc(sizeof(LinkList)); /*创建hb头结点*/
rb=hb; /*rb始终指向hb的末尾结点*/
while (p!=NULL)
{ ra->next=p;ra=p; /*将*p链到ha单链表未尾*/
p=p->next;
if (p!=NULL)
{ rb->next=p;rb=p; /*将*p链到hb单链表未尾*/
p=p->next; } }
ra=rb=NULL; } /*两个尾结点的next域置空*/
整个算法实际上是采用尾插法建表。
（2）双链表基本运算的实现
重点：插入和删除结点的算法。
（3）循环链表基本运算的实现
重点：判断最后一个结点。
第3章 栈和队列
3.1 栈
1.栈的定义
栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。
2.栈的顺序存储结构及其基本运算实现
typedef struct
{ ElemType elem[MaxSize];
int top; /*栈指针*/
} SqStack;
栈空条件:s->top==-1
栈满条件:s->top==MaxSize-1
3.栈的链式存储结构及其基本运算的实现
typedef struct linknode
{
ElemType data; /*数据域*/
struct linknode *next; /*指针域*/
} LiStack;
带头结点的单链表来实现(也可不带头结点)
栈空条件:s->next==NULL
栈满条件:?
3.2 队列
1.队列的定义
队列简称队，它也是一种运算受限的线性表，其限制仅允许在表的一端进行插入，而在表的另一端进行删除。进行插入的一端称做队尾（rear），进行删除的一端称做队首（front）。
2.队列的顺序存储结构及其基本运算的实现
typedef struct
{ ElemType elem[MaxSize]；
int front,rear；/*队首和队尾指针*/
} SqQueue；
把数组的前端和后端连接起来，形成一个环形的顺序表，即把存储队列元素的表从逻辑上看成一个环，称为循环队列。
循环队列首尾相连，当队首指针front=MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取余的运算(％)来实现：
队首指针进1：front=(front+1)％MaxSize
队尾指针进1：rear=(rear+1)％MaxSize
队空条件：q->rear==q->front
队满条件：(q->rear+1) % MaxSize==q->front
3.队列的链式存储结构及其基本运算的实现
struct qnode
{ ElemType data;
struct qnode *next;
} QNode;
typedef struct
{ QNode *front;
QNode *rear;
} LiQueue;
第4章 串
1.串的定义
串（或字符串)，是由零个或多个字符组成的有穷序列。含零个字符的串称为空串，用Ф表示。串中所含字符的个数称为该串的长度（或串长）。
2.串的顺序存储结构－顺序串
3.串的链式存储结构－链串
KMP算法不作要求。
第5章 数组和稀疏矩阵
1,数组的定义
数组是n（n＞1）个相同类型数据元素
a1，a2，…，an
构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。
2.数组的顺序存储结构
对于数组A[c1..d1,c2..d2],
以行序为主序,
LOC(ai,j)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*k
以列序为主序
LOC(ai,j)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*k
3.特殊矩阵的压缩存储
(1) 对称矩阵
若一个n阶方阵A[n][n]中的元素满足ai,j=aj,i（0≤i，j≤n-1），则称其为n阶对称矩阵。
A[0..n-1][0..n-1]->B[0..n(n+1)/2]
i(i+1)/2 +j 当i≥j时
k=
j(j+1)/2 +i 当i＜j时
(2)三角矩阵 采用类似的压缩方法.
4.稀疏矩阵
(1) 三元组表示 (2) 十字链表表示
各种表示的基本思路。
【 例5.1】 二维数组A[4][4]（即A[0..3][0..3]）的元素起始地址是loc(A[0][0])=1000，元素的长度为2，则loc(A[2][2])为多少？ 答：Loc(A[2][2])=Loc(A[0][0])+[(2-0)*(3-0+1)+(2-0)]*2=1020。
第6章 树和二叉树
6.1 树
1.树的定义
树是由n（n≥0）个结点组成的有限集合（记为T）。其中，
如果n=0，它是一棵空树，这是树的特例；
如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点，简称为根（root），其余结点可分为m （m>0）个互不相交的有限集T1,，T2，…，Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。
2.树的表示法 (逻辑表示方法)
(1) 树形表示法
(2) 文氏图表示法
(3) 凹入表示法
(4) 括号表示法
3.树的遍历先根遍历算法为：
（1）访问根结点；
（2）按照从左到右的次序先根遍历根结点的每一棵子树。
后根遍历算法为：
（1）按照从左到右的次序后根遍历根结点的每一棵子树；
（2）访问根结点。
4.树(森林)与二叉树之间的相互转换
6.2 二叉树
1.二叉树的定义
二叉树也称为二次树或二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。
完全二叉树,满二叉树的定义
2.二叉树性质性质1 非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1.
性质2 非空二叉树上第i层上至多有2i-1个结点（i≥1）。
性质3 高度为h的二叉树至多有2h-1个结点（h≥1） 。
性质4 完全二叉树的性质 。
性质5 具有n个（n＞0）结点的完全二叉树的高度为log2n+1或log2n+1。
【例6.1】将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为 。
A.98 B.99 C.50 D.48
答：A
【例6.2】 深度为5的二叉树至多有 个结点。
A.16 B.32 C.31 D.10
答：相同满度时满二叉树结点最多，h=5的满二叉树结点个数=25-1=31。本题答案应为C。
3.二叉树存储结构
（1）二叉树的顺序存储结构
（2）二叉链存储结构
typedef struct node
{ ElemType data; /*数据元素*/
struct node *lchild; /*指向左孩子*/
struct node *rchild; /*指向右孩子*/
} BTNode;
4.二叉树的遍历
（1） 先序遍历
void preorder（BTNode ＊t）
{ printf(“%d”,t->data);
preorder(t->lchild);
preorder(t->rchild); }
（2） 中序遍历
void inorder（BTNode ＊t）
{ inorder(t->lchild);
printf(“%d”,t->data);
inorder(t->rchild); }
（3）后序遍历
void postorder（BTNode ＊t）
{ postorder(t->lchild);
postorder(t->rchild);
printf(“%d”,t->data); }
注意：重点掌握基于遍历的递归算法设计。
5.二叉树的构造
任何n（n≥0）个不同结点的二又树，都可由它的中序序列和先序序列惟一地确定。
任何n（n≥0）个不同结点的二又树，都可由它的中序序列和后序序列惟一地确定。
掌握它们的构造方法。
6.线索二叉树
(1)线索二叉树的概念
对于具有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域，又由于只有n-1个结点被有效指针所指向（树根结点没有被有效指针域所指向），则共有2n-(n-1)=n+1个空链域。
遍历二叉树的结果是一个结点的线性序列。可以利用这些空链域存放指向结点的前驱和后继结点的指针。这样的指向该线性序列中的“前驱”和“后继”的指针，称作线索。
对二叉树以某种方式遍历使其变为线索二叉树的过程称作按该方式对二叉树进行线索化。
(2) 二叉树进行线索化的过程
不要求掌握算法。
6.3 哈夫曼树
1.哈夫曼树的定义在n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树（或最优二叉树） 。
2.哈夫曼树的构造过程
3.哈夫曼编码的构造过程
第7章 广义表相关概念:
一个广义表中所含元素的个数称为它的长度.
一个广义表中括号嵌套的最大次数为它的深度.
表的第一个元素a1为广义表GL的表头，其余部分(a2，…，ai，ai+1，…，an)为GL的表尾,
第8章 图
1.图的基本概念
(1)顶点的度、入度和出度
(2)完全图
(3)子图
(4)路径和路径长度
(5)连通、连通图和连通分量
(6)强连通图和强连通分量
(7)权和网
2.图的存储结构
(1) 邻接矩阵存储方法
(2)邻接表存储方法
掌握两种存储方法的优缺点，同一种功能在不同存储结构上的实现算法。
3.图的遍历
（1）深度优先搜索遍历
void DFS(ALGraph *G,int v)
{ ArcNode*p;Visited[v]=1; /*置已访问标记*/
printf("%d ",v); /*输出被访问顶点的编号*/
p=G->adjlist[v].firstarc; /*p指向顶点v的第一条弧的弧头结点*/
while (p!=NULL)
{ if (visited[p->adjvex]==0)
DFS(G,p->adjvex);
p=p->nextarc; }} /*p指向顶点v的下一条弧的弧头结点*/
（2）广度优先搜索遍历
void BFS(ALGraph *G,int v)
{ ArcNode *p;
int queue[MAXV],front=0,rear=0; /*定义循环队列并初始化*/
int visited[MAXV]; /*定义存放结点的访问标志的数组*/
int w,i;
for (i=0;i<G->n;i++) visited[i]=0; /*访问标志数组初始化*/
printf("%2d",v);
visited[v]=1; /*置已访问标记*/
rear=(rear+1)%MAXV;
queue[rear]=v; /*v进队*/
while (front!=rear) /*若队列不空时循环*/
{ front=(front+1)%MAXV;
w=queue[front]; /*出队并赋给w*/
p=G->adjlist[w].firstarc;
while (p!=NULL)
{ if (visited[p->adjvex]==0)
{ printf("%2d",p->adjvex);
visited[p->adjvex]=1;
rear=(rear+1)%MAXV;
queue[rear]=p->adjvex; }
p=p->nextarc; } }
printf("\n");}
(3)非连通图的遍历
采用深度优先搜索遍历非连通无向图的算法如下：
DFS1(ALGraph *g)
{ int i;
for (i=0;i<g->n;i+)
if (visited[i]==0)
DFS(g,i); }
采用广度优先搜索遍历非连通无向图的算法如下：
BFS1(ALGraph *g)
{ int i;
for (i=0;i<g->n;i+)
if (visited[i]==0)
BFS(g,i); }
【例7.1】 试以邻接表为存储结构，分别写出基于DFS和BPS遍历的算法来判别顶点i和顶点j(i≠j)之间是否有路径。
解：先置全局变量visited[]为0，然后从顶点i开始进行某种遍历，遍历之后，若visited[j]=0，说明顶点i与顶点j之间没有路径；否则说明它们之间存在路径。
基于DFS遍历的算法如下：
int visited[MaxVertexNum];
int DFSTrave(ALGraph *G，int i，int j)
{ int k;
for (k=0;k<G->n;k++) visited[k]=0;
DFS(G，i); //从顶点i开始进行深度优先遍历
if (visited[j]==0) return 0;
else return 1; }
基于BFS遍历的算法如下：
int visited[MaxVertexNum];
int DFSTrave(ALGraph *G，int i，int j)
{ int k;
for (k=0;k<G->n;k++)
visited[k]=0;
BFS(G，i); //从顶点i开始进行广度优先遍历
if (visited[j]==0) return 0;
else return 1; }?
4.最小生成树
（1）普里姆算法过程 不要求编写算法。
（2）克鲁斯卡尔算法过程 不要求编写算法。
5.最短路径
（1）狄克斯特拉算法过程 不要求掌握算法。
（2）弗洛伊德算法过程 不要求掌握算法。
拓扑排序和关键路径不作考试内容。
第9章 查找
1.线性表的查找 在顺序表上进行。
（1）顺序查找 （过程和算法）
（2）二分查找 （过程和算法）
（3）分块查找 (只需过程)
2,树表的查找 二叉排序树
（1）定义
（2）查找（过程和算法）
（3）插入和删除（过程）
3.哈希表查找
（1） 哈希函数（除留余数法 ）
（2） 哈希冲突解决方法 （线性探查法 ）
第10章 内 排 序
各种排序方法的过程和算法设计。 外排序和文件部分不作要求。
1.数据结构的定义
数据－＞数据元素 －＞数据项数据结构是指数据以及相互之间的联系。包括：
（1）数据的逻辑结构。
（2）数据的存储结构（物理结构）。
（3）施加在该数据上的运算。
数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。
数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。但运算的实现与数据的存储结构有关。
逻辑结构主要有两大类：
（1）线性结构
（2）非线性结构：
1）树形结构
2）图形结构存储结构分为如下四种：
（1）顺序存储方法
（2）链式存储方法
（3）索引存储方法
（4）散列存储方法
2.抽象数据类型
抽象数据类型（Abstract Data Type简写为ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。
3.什么是算法
算法是对特定问题求解步骤的一种描述，它是指令的有限序列 。
算法的五个重要的特性,
（1）有穷性 （2）确定性 （3）可行性 （4）有输入 （5）有输出
4.算法分析
(1)算法的时间复杂度：是指其基本运算在算法中重复执行的次数。
算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作：
T(n)=O(f(n))
记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。
(2)算法空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度 。
对于空间复杂度为O(1)的算法称为原地工作或就地工作算法。
第2章 线性表
1.线性表的定义
线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n≥0。当n=0时，表示线性表是一个空表，即表中不包含任何元素。
1.线性表的顺序存储结构—顺序表
typedef struct
{ ElemType elem[MaxSize]; /*存放顺序表元素*/
int length; /*存放顺序表的长度*/
} SqList;
顺序表基本运算的实现
插入数据元素算法：元素移动的次数不仅与表长n有关 ；插入一个元素时所需移动元素的平均次数 n／2。平均时间复杂度为O(n)。
删除数据元素算法:元素移动的次数也与表长n有关 。删除一个元素时所需移动元素的平均次数为(n-1)/2。删除算法的平均时间复杂度为O(n)。
【例2.1】 设计一个算法，将x插入到一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。
void Insert(SqList &A,ElemType x)
{ int i=0,j;
while (i<A.length && AS.elem[i]<x) i++;
for (j=A.length-1;j>=i;j--)
A.elem[j+1]=A.elem[j];
A.elem[i]=x;
A.length++; }
2.线性表的链式存储结构—链表
定义单链表结点类型:
typedef struct LNode
{ ElemType data;
struct LNode *next; /*指向后继结点*/
} LinkList;
定义双链表结点类型:
typedef struct DNode
{ ElemType data;
struct DNode *prior; /*指向前驱结点*/
struct DNode *next; /*指向后继结点*/
} DLinkList;
（1）单链表基本运算的实现
重点：头插法建表和尾插法建表算法，它是很多算法设计的基础。
【例2.1】 设C={a1,b1,a2,b2,…,an,bn}为一线性表，采用带头结点的hc单链表存放，编写一个就地算法，将其拆分为两个线性表，使得,A={a1,a2,…,an}，C={b1,b2,…,bn}
void fun(LinkList *hc,LinkList *&ha,LinkList *&hb)
{ LinkList *p=hc->next,*ra,*rb;
ha=hc; /*ha的头结点利用hc的头结点*/
ra=ha; /*ra始终指向ha的末尾结点*/
hb=(LinkList *)malloc(sizeof(LinkList)); /*创建hb头结点*/
rb=hb; /*rb始终指向hb的末尾结点*/
while (p!=NULL)
{ ra->next=p;ra=p; /*将*p链到ha单链表未尾*/
p=p->next;
if (p!=NULL)
{ rb->next=p;rb=p; /*将*p链到hb单链表未尾*/
p=p->next; } }
ra=rb=NULL; } /*两个尾结点的next域置空*/
整个算法实际上是采用尾插法建表。
（2）双链表基本运算的实现
重点：插入和删除结点的算法。
（3）循环链表基本运算的实现
重点：判断最后一个结点。
第3章 栈和队列
3.1 栈
1.栈的定义
栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。
2.栈的顺序存储结构及其基本运算实现
typedef struct
{ ElemType elem[MaxSize];
int top; /*栈指针*/
} SqStack;
栈空条件:s->top==-1
栈满条件:s->top==MaxSize-1
3.栈的链式存储结构及其基本运算的实现
typedef struct linknode
{
ElemType data; /*数据域*/
struct linknode *next; /*指针域*/
} LiStack;
带头结点的单链表来实现(也可不带头结点)
栈空条件:s->next==NULL
栈满条件:?
3.2 队列
1.队列的定义
队列简称队，它也是一种运算受限的线性表，其限制仅允许在表的一端进行插入，而在表的另一端进行删除。进行插入的一端称做队尾（rear），进行删除的一端称做队首（front）。
2.队列的顺序存储结构及其基本运算的实现
typedef struct
{ ElemType elem[MaxSize]；
int front,rear；/*队首和队尾指针*/
} SqQueue；
把数组的前端和后端连接起来，形成一个环形的顺序表，即把存储队列元素的表从逻辑上看成一个环，称为循环队列。
循环队列首尾相连，当队首指针front=MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取余的运算(％)来实现：
队首指针进1：front=(front+1)％MaxSize
队尾指针进1：rear=(rear+1)％MaxSize
队空条件：q->rear==q->front
队满条件：(q->rear+1) % MaxSize==q->front
3.队列的链式存储结构及其基本运算的实现
struct qnode
{ ElemType data;
struct qnode *next;
} QNode;
typedef struct
{ QNode *front;
QNode *rear;
} LiQueue;
第4章 串
1.串的定义
串（或字符串)，是由零个或多个字符组成的有穷序列。含零个字符的串称为空串，用Ф表示。串中所含字符的个数称为该串的长度（或串长）。
2.串的顺序存储结构－顺序串
3.串的链式存储结构－链串
KMP算法不作要求。
第5章 数组和稀疏矩阵
1,数组的定义
数组是n（n＞1）个相同类型数据元素
a1，a2，…，an
构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。
2.数组的顺序存储结构
对于数组A[c1..d1,c2..d2],
以行序为主序,
LOC(ai,j)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*k
以列序为主序
LOC(ai,j)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*k
3.特殊矩阵的压缩存储
(1) 对称矩阵
若一个n阶方阵A[n][n]中的元素满足ai,j=aj,i（0≤i，j≤n-1），则称其为n阶对称矩阵。
A[0..n-1][0..n-1]->B[0..n(n+1)/2]
i(i+1)/2 +j 当i≥j时
k=
j(j+1)/2 +i 当i＜j时
(2)三角矩阵 采用类似的压缩方法.
4.稀疏矩阵
(1) 三元组表示 (2) 十字链表表示
各种表示的基本思路。
【 例5.1】 二维数组A[4][4]（即A[0..3][0..3]）的元素起始地址是loc(A[0][0])=1000，元素的长度为2，则loc(A[2][2])为多少？ 答：Loc(A[2][2])=Loc(A[0][0])+[(2-0)*(3-0+1)+(2-0)]*2=1020。
第6章 树和二叉树
6.1 树
1.树的定义
树是由n（n≥0）个结点组成的有限集合（记为T）。其中，
如果n=0，它是一棵空树，这是树的特例；
如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点，简称为根（root），其余结点可分为m （m>0）个互不相交的有限集T1,，T2，…，Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。
2.树的表示法 (逻辑表示方法)
(1) 树形表示法
(2) 文氏图表示法
(3) 凹入表示法
(4) 括号表示法
3.树的遍历先根遍历算法为：
（1）访问根结点；
（2）按照从左到右的次序先根遍历根结点的每一棵子树。
后根遍历算法为：
（1）按照从左到右的次序后根遍历根结点的每一棵子树；
（2）访问根结点。
4.树(森林)与二叉树之间的相互转换
6.2 二叉树
1.二叉树的定义
二叉树也称为二次树或二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。
完全二叉树,满二叉树的定义
2.二叉树性质性质1 非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1.
性质2 非空二叉树上第i层上至多有2i-1个结点（i≥1）。
性质3 高度为h的二叉树至多有2h-1个结点（h≥1） 。
性质4 完全二叉树的性质 。
性质5 具有n个（n＞0）结点的完全二叉树的高度为log2n+1或log2n+1。
【例6.1】将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为 。
A.98 B.99 C.50 D.48
答：A
【例6.2】 深度为5的二叉树至多有 个结点。
A.16 B.32 C.31 D.10
答：相同满度时满二叉树结点最多，h=5的满二叉树结点个数=25-1=31。本题答案应为C。
3.二叉树存储结构
（1）二叉树的顺序存储结构
（2）二叉链存储结构
typedef struct node
{ ElemType data; /*数据元素*/
struct node *lchild; /*指向左孩子*/
struct node *rchild; /*指向右孩子*/
} BTNode;
4.二叉树的遍历
（1） 先序遍历
void preorder（BTNode ＊t）
{ printf(“%d”,t->data);
preorder(t->lchild);
preorder(t->rchild); }
（2） 中序遍历
void inorder（BTNode ＊t）
{ inorder(t->lchild);
printf(“%d”,t->data);
inorder(t->rchild); }
（3）后序遍历
void postorder（BTNode ＊t）
{ postorder(t->lchild);
postorder(t->rchild);
printf(“%d”,t->data); }
注意：重点掌握基于遍历的递归算法设计。
5.二叉树的构造
任何n（n≥0）个不同结点的二又树，都可由它的中序序列和先序序列惟一地确定。
任何n（n≥0）个不同结点的二又树，都可由它的中序序列和后序序列惟一地确定。
掌握它们的构造方法。
6.线索二叉树
(1)线索二叉树的概念
对于具有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域，又由于只有n-1个结点被有效指针所指向（树根结点没有被有效指针域所指向），则共有2n-(n-1)=n+1个空链域。
遍历二叉树的结果是一个结点的线性序列。可以利用这些空链域存放指向结点的前驱和后继结点的指针。这样的指向该线性序列中的“前驱”和“后继”的指针，称作线索。
对二叉树以某种方式遍历使其变为线索二叉树的过程称作按该方式对二叉树进行线索化。
(2) 二叉树进行线索化的过程
不要求掌握算法。
6.3 哈夫曼树
1.哈夫曼树的定义在n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树（或最优二叉树） 。
2.哈夫曼树的构造过程
3.哈夫曼编码的构造过程
第7章 广义表相关概念:
一个广义表中所含元素的个数称为它的长度.
一个广义表中括号嵌套的最大次数为它的深度.
表的第一个元素a1为广义表GL的表头，其余部分(a2，…，ai，ai+1，…，an)为GL的表尾,
第8章 图
1.图的基本概念
(1)顶点的度、入度和出度
(2)完全图
(3)子图
(4)路径和路径长度
(5)连通、连通图和连通分量
(6)强连通图和强连通分量
(7)权和网
2.图的存储结构
(1) 邻接矩阵存储方法
(2)邻接表存储方法
掌握两种存储方法的优缺点，同一种功能在不同存储结构上的实现算法。
3.图的遍历
（1）深度优先搜索遍历
void DFS(ALGraph *G,int v)
{ ArcNode*p;Visited[v]=1; /*置已访问标记*/
printf("%d ",v); /*输出被访问顶点的编号*/
p=G->adjlist[v].firstarc; /*p指向顶点v的第一条弧的弧头结点*/
while (p!=NULL)
{ if (visited[p->adjvex]==0)
DFS(G,p->adjvex);
p=p->nextarc; }} /*p指向顶点v的下一条弧的弧头结点*/
（2）广度优先搜索遍历
void BFS(ALGraph *G,int v)
{ ArcNode *p;
int queue[MAXV],front=0,rear=0; /*定义循环队列并初始化*/
int visited[MAXV]; /*定义存放结点的访问标志的数组*/
int w,i;
for (i=0;i<G->n;i++) visited[i]=0; /*访问标志数组初始化*/
printf("%2d",v);
visited[v]=1; /*置已访问标记*/
rear=(rear+1)%MAXV;
queue[rear]=v; /*v进队*/
while (front!=rear) /*若队列不空时循环*/
{ front=(front+1)%MAXV;
w=queue[front]; /*出队并赋给w*/
p=G->adjlist[w].firstarc;
while (p!=NULL)
{ if (visited[p->adjvex]==0)
{ printf("%2d",p->adjvex);
visited[p->adjvex]=1;
rear=(rear+1)%MAXV;
queue[rear]=p->adjvex; }
p=p->nextarc; } }
printf("\n");}
(3)非连通图的遍历
采用深度优先搜索遍历非连通无向图的算法如下：
DFS1(ALGraph *g)
{ int i;
for (i=0;i<g->n;i+)
if (visited[i]==0)
DFS(g,i); }
采用广度优先搜索遍历非连通无向图的算法如下：
BFS1(ALGraph *g)
{ int i;
for (i=0;i<g->n;i+)
if (visited[i]==0)
BFS(g,i); }
【例7.1】 试以邻接表为存储结构，分别写出基于DFS和BPS遍历的算法来判别顶点i和顶点j(i≠j)之间是否有路径。
解：先置全局变量visited[]为0，然后从顶点i开始进行某种遍历，遍历之后，若visited[j]=0，说明顶点i与顶点j之间没有路径；否则说明它们之间存在路径。
基于DFS遍历的算法如下：
int visited[MaxVertexNum];
int DFSTrave(ALGraph *G，int i，int j)
{ int k;
for (k=0;k<G->n;k++) visited[k]=0;
DFS(G，i); //从顶点i开始进行深度优先遍历
if (visited[j]==0) return 0;
else return 1; }
基于BFS遍历的算法如下：
int visited[MaxVertexNum];
int DFSTrave(ALGraph *G，int i，int j)
{ int k;
for (k=0;k<G->n;k++)
visited[k]=0;
BFS(G，i); //从顶点i开始进行广度优先遍历
if (visited[j]==0) return 0;
else return 1; }?
4.最小生成树
（1）普里姆算法过程 不要求编写算法。
（2）克鲁斯卡尔算法过程 不要求编写算法。
5.最短路径
（1）狄克斯特拉算法过程 不要求掌握算法。
（2）弗洛伊德算法过程 不要求掌握算法。
拓扑排序和关键路径不作考试内容。
第9章 查找
1.线性表的查找 在顺序表上进行。
（1）顺序查找 （过程和算法）
（2）二分查找 （过程和算法）
（3）分块查找 (只需过程)
2,树表的查找 二叉排序树
（1）定义
（2）查找（过程和算法）
（3）插入和删除（过程）
3.哈希表查找
（1） 哈希函数（除留余数法 ）
（2） 哈希冲突解决方法 （线性探查法 ）
第10章 内 排 序
各种排序方法的过程和算法设计。 外排序和文件部分不作要求。
