第 1章 绪论第 2章 线性表第 3章 栈和队列第 4章 串第 5章 数组和稀疏矩阵第 6章 树和二叉树第 8章 图数据结构总复习第 9章 查找第 10章 内排序第 7章 广义表第 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;
带头结点的单链表来实现 (也可不带头结点 )
…
lhead
a 1 a n ∧ a 2
栈底结点 栈顶结点 头结点栈空条件,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阶对称矩阵。
i(i+1)/2 +j 当 i≥j时
k=
j(j+1)/2 +i 当 i＜ j时
A[0..n-1][0..n-1]->B[0..n(n+1)/2]
(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章 树和二叉树
1.树的定义树 是由 n（ n≥0） 个结点组成的有限集合 （ 记为 T） 。
其中,
如果 n=0,它是一棵空树,这是树的特例；
如果 n>0,这 n个结点中存在 （ 有仅存在 ） 一个结点作为树的根结点,简称为根 （ root）,其余结点可分为
m （ m>0） 个互不相交的有限集 T1,,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根
root的子树 。
6.1 树
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.哈夫曼编码的构造过程相关概念,
一个广义表中所含元素的个数称为它的 长度,
一个广义表中括号嵌套的最大次数为它的 深度,
表的第一个元素 a1为广义表 GL的 表头,其余部分 (a2,…,ai,ai+1,…,an)为 GL的 表尾,
第 7章 广义表第 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;
带头结点的单链表来实现 (也可不带头结点 )
…
lhead
a 1 a n ∧ a 2
栈底结点 栈顶结点 头结点栈空条件,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阶对称矩阵。
i(i+1)/2 +j 当 i≥j时
k=
j(j+1)/2 +i 当 i＜ j时
A[0..n-1][0..n-1]->B[0..n(n+1)/2]
(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章 树和二叉树
1.树的定义树 是由 n（ n≥0） 个结点组成的有限集合 （ 记为 T） 。
其中,
如果 n=0,它是一棵空树,这是树的特例；
如果 n>0,这 n个结点中存在 （ 有仅存在 ） 一个结点作为树的根结点,简称为根 （ root）,其余结点可分为
m （ m>0） 个互不相交的有限集 T1,,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根
root的子树 。
6.1 树
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.哈夫曼编码的构造过程相关概念,
一个广义表中所含元素的个数称为它的 长度,
一个广义表中括号嵌套的最大次数为它的 深度,
表的第一个元素 a1为广义表 GL的 表头,其余部分 (a2,…,ai,ai+1,…,an)为 GL的 表尾,
第 7章 广义表第 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章 内 排 序各种排序方法的 过程 和算法设计。
外排序和文件部分不作要求。
