-
第二章线性表
一、
顺序表和链表的优缺点
1.
顺序表
定义：
用一组连续的存储单元
（地址连续）
依次存放线性表的各个数据元素。
即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。
?
优点
?
逻辑相邻，物理相邻
?
可随机存取任一元素
?
存储空间使用紧凑
?
缺点
?
插入、
删
除操作需要移动大量的元素
（平均约需移动一半结点，
当
n
很大时，
算法的效率较低）
?
预先分配空间需按最大空间分配，利用不充分
?
表容量难以扩充
2.
链式存储结构
定义：
由分别表示
a
1
,a
2
,
…
,a
i-1
,a
i
,
…
,a
n
的
N
个结点依次相链构成的链表，
称为
线性表的链式存储表示
优势：
(1)
能有效利用存储空间；
动态存储分配的结构，
不需预先为线性表分配足够大的空间，
而是向系统
“
随
用随取
”
，在删除元素时可同时释放空间。
(2)
用
“
指
针
”
指示数据元素之间的后继关系，
便
于进行
“
插入
”
、
“
删除
”
等操作；
插入或删除时只需要修改指针，而不需要元素移动。
劣势：
(1)
不能随机存取数据元素；
(2)
丢失了一些顺序表的长处，如线性表的
“
表长
”
和数据元素在线性表中的<
/p>
“
位序
”
，在单
链表中都看不见了。如，不便于在表尾插入元素，需遍历整个
表才能找到插入的位置。<
/p>
二、
单链表中删除一个节点和插入一个节点的语句操作，
p29
1.
插入元素操作
算法基
本思想：
首先找到相应结点，然后修改相应指针。
假定在
a
，
b
之间插入结点
X
，
s
指向
X, p
指向
a
，指针修改语句为：
s->next=p->next; p->next =s;
2.
删除元素操作
算法基本思想
:
首先找到第
i-1
个结点，然后修改相应指针。
删除<
/p>
b
结点，其中，
P
指向
a
，指针修改语句为：
p->next=p->next->next
；
三、
单链表的就地逆置习题集
2.22
算法的基本思想：
以单链表作存储结构进行就地逆置的正确做法
应该是：将
原链表的头结点和第一个元素结点断开（令其指针域为空）
< br>，先构成一个新的空
表，然后将原链表中各结点，从第一个结点起，依次插入这个
新表的头部（即令
每个插入的结点成为新的第一个元素结点）
。
算法思路：
依次取原链表中的每个结点，将其作为第一个结点插入到新链表
中去，指针
p
用来指向当前结点，
p
为空时结束。
void
reverse (Linklist H){
LNode
*p;
p=H->next;
/*p
指向第一个数据结点
*/
H->next=NULL;
/*
将原链表置为空表
H*/
while (p){
q=p;
p=p->next;
q->next=H->next;
/*
将当前结点插到头结点的后面
*/
H->next=q;
}
}
第三章栈和队列
一、
栈和队列的特性
1.
特点
栈必须按
“
后进先出
< br>”
（
LIFO
）的规则进行操作
，仅限在表尾进行插入和删
除的操作。
队列（
FIFO
）必须按
“
先进先出
”
的规则进行操作，队尾插入，队头删
除。
二、
循环队列为空和满的判定方法，
p63
队空条件：
front == rear;
队满条件：
(rear + 1) % maxSize ==
front
第四章串
一、模式匹配的改进算法
求
Next
数组
1)
Next[j]
的定义
2)
求解
next[j]
示例
j
模式串
Next[j]
1
a
0
2
b
1
3
a
1
4
a
2
5
b
2
6
c
3
7
a
1
8
c
2
第五章数组与广义表
一、对称矩阵和上（下）三角矩阵的压缩存储
1.
对称矩阵的压缩存储
若一个
n
阶方阵
A
中的元素满足
a
i,j
=a
j,i
(1≤i,j≤n),
则
称其为
n
阶对称矩阵
。
（
1
）只存储对称矩阵中上三角或下三角中的元素
（
2
）将
n
2
个元素压缩存储到
n(n+1)/2
个元素的空间中，以一个一维数组作
为
A
的存储空间。
?
i<
/p>
(
i
?
1)
?
j
?
1,
当
i
?
j
?
?
2
k
?
?
?
j
(
j
?
1)
?
i
?
1,
当
i
?
j
?
?
< br>2
2.
下三角矩阵的压缩存储
B[n(n+1)/2+1]
?
i
(
i
?
1)
?
j
?
1,
当
i
?
j
?
?
2
k
?
< br>?
?
n
(
n
?
1)
,
当
i
?
j
?<
/p>
?
2
3.
上三角矩阵的压缩存储
B[n(n+1)/2+1]
?
(
i
?
1)(2
n<
/p>
?
i
?
2)
?
j
?
i
,
当
i
?
j
?
?
2
< br>k
?
?
n
(
n
?
1)
?
,
当
i
?<
/p>
j
?
?
2
二、理解广义表的取表头和表尾的操作
1.
广义表的表头
< br>(Head)
和表尾
(Tail)
：
当广义表
LS=(a
1
,a
2
,…,a
i
,…,a
n
)
非空时，
称第一个元素
< br>a
1
为广义表的表头，
其余
元素组成的表
(a
2
, a
3
, …,a
n
)
称为广义表的表尾。
表头可能是原子，
也可能是广义表，
但表尾一定是广义表。
2.
取表头
GetHead(LS) =
a
1
。
3.
取表尾
GetTail(LS) =
(a
2
,a
3
,…,a
n
)
。
4.
取表头表尾示例
①
B=(e)
GetHead(B) = e;
GetTail(B) = ( ).
②
A=(a, ((b, c), d, e))
GetTail(A)=(((b, c), d, e))
GetHead( GetTail(A))=((b, c), d, e)
GetHead( GetHead( GetTail(A))) = (b,
c).
③
A=( );
B = ( ( ) )
A
空表，长度
0
，深
度
1
，无表头和表尾；
B
长度
1
，深度
2
，表头
(
)
，表尾
(
)
。
第六章树和二叉树
一、
二叉树先序、中序和后序的关系
p154
1.
二叉树遍历的概念
二叉树的遍历是指按照一定次序访问树中所有结点
,
并且每个结点仅被访问一次
的过程。它是最基本的运算
,
是二叉树中所有其他运算的基础。
2.
先序遍历（
DLR
）操作过程：
若二叉树为空，则空操作，否则
(1)
访问根结点；
(2)
按先序遍历左子树；
(3)
按先序遍历右子树。
3.
中序遍历（
LDR
）操作过程：
< br>
若二叉树为空，则空操作，否则：
(1)
按中序遍历左子树；
(2)
访问根结点；
(3)
按中序遍历右子树。
4.
后序遍历（
LRD
）操作过程：
< br>
若二叉树为空，则空操作，否则：
(1)
按后序遍历左子树；
(2)
按后序遍历右子树；
(3)
访问根结点。
5.
遍历示例：
6.
强调：
给定结点的前序序列和中序序列可以唯一确定一棵二叉树。
见
P
154
例
6-5
，必须掌握。
二、
二叉树向森林的转换
1.
将一棵二叉树还原为树或森林，具体方法如下：
（
1
）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩
子的右孩
子
……
都与该结点的双亲结点
用线连起来。
（
2
< br>）删掉原二叉树中所有双亲结点与右孩子结点的连线。
（
3
）整理由（
1
）
、
（
2
）两步所得到的树或森林，使之结构层次分明。
2.
二叉树到森林的转换示例
C
A
E
F
D
H
I
J
(a)
添加连线
G
B
C
A
E
F
D
H
I
J
(b)
删除右孩
子结点的连线
G
A
E
< br>B
B
C
D
G
F
H
I
J
(c)
整理
三、
算法：
题
目要求：
实现一次遍历二叉树即可求得根结点到树中每个叶结点的路径，
试用
C
语言描述该算法。
以二
叉链表存储表示二叉树，
结点的结构为
(lchild,
data,
rchild)
。
————树节点结构——————
Typedef
struct
BInode{
TElemType
data;
Struct
Binode
*lchild,rchild;
}
Binode,*BiTree;
void AllPath(Bitree T,
Stack
&S)//
输出二叉树上从根到所有叶子结点的路径
{
if(T)
{
Push(S,T->data);
if(!T->Left&&!T->Right)//
如果左指针
和右指针同时为空，才说明该节点为
叶子节点
PrintStack(S);
else
{
AllPath(T->Left,S);
AllPath(T->Right,S);
}
Pop(S);
}
四、
哈夫曼树
1.
构造哈夫曼树
(
哈夫曼算法
)
①
由给定的
n
个权值
{W
1
,W
2
,...,W
n
},
构造
n
棵只有一个叶子
结点的二叉树
,
从
而得到一个二叉树的
集合
F={T
1
,T
< br>2
,...,T
n
};
②
在
F
中选取根结点的权值最小和次小的两棵二叉树作为左、
右子树构造一
棵新的二叉树
,
这棵新的二叉树根结点
的权值为其左、右子树根结点权值
之和
;
③
在集合
F
中删除作为左、右子树的两棵二叉树
,
并将新建立的二叉树加入
到集合
F
中<
/p>
;
④
重复<
/p>
(2)
、
(3)
两步
,
当
F
中
只剩下一棵二叉树时
,
这棵二叉树便是所要建立的
哈夫曼树。
2.
哈夫曼构造示例：
3.
哈夫曼编码（最优前缀编码）
16
前缀编码：任一字符的编码都不是另一个字符的编码的前缀。
0
1
d
9
右图对应的哈夫曼编码如下：
1
0
a
：
000
b
：
001
c
：
01
d
：
1
4
c
0
1
a
b
哈夫曼编码树中没有度为
1
的结点。
n
个叶子结
点，共有
2n-1
个结点。
强调
：建立的哈弗曼树不唯一，编码
也不唯一，但是不同哈弗曼编码的树的
带权路径长度都是一样的，都是最小的。
第七章图
一
.
图邻接矩阵的表示方法
1.
邻接矩阵表示法（数组表示法）
?
图
G
是一个具有
n
个顶点的无权图，
G
的邻接矩阵是具有如下性质的
n×n
矩阵
A
：
?
?
1,
<
/p>
若
(
v
i
,
v
j
)
或
?
v
i
,
v
j
??
< br>V
A
[
i
,
j
]
?
?
?
?
0,
其它
?
若图
G
是一个有
n
个顶点的网，则它的邻接矩阵是具有如下性质的
n×n
矩阵
A
：
?
?
w
ij
,
若
(
v
i
,
v
j
)
或
?
v
i
,
v
j<
/p>
??
V
A
[
i
,
j
]
?
?
?
?
?
,
其它
邻接矩阵表示法示例：
1
?<
/p>
0
1
0
1
1
?
?
1
0
1
1
0
?
2
3
0
?
?
<
/p>
A
1
?
?
0
1
0
1
1
?
?
?
4
1
1
< br>1
0
1
?
?
?
(a)
?
1
0
1
1
0
?
?
<
/p>
?
0
1
0
1
0
?
1
?
0
0<
/p>
1
1
0
?
?
?
2
3
0
A
2
?
?
0
0
0
1
1
?
?
?
0
0
0
0
< br>0
?
?
4
?
?
1
0
0
1
0
?
?
(b)
邻接矩阵表示法类型描述?
＃
define
MAX_VERTEX_NUM
20
//
最多顶点个数?
＃
define
INFINITY
INT_MAX
//
表示极大值∞?
typedef
enum{DG,
DN,
UDG,
UDN}
GraphKind;
typedef
struct
ArcCell{
?
VRType
adj;
InfoType
*info;
?
} ArcCell,
AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef
struct{
VertexType
vexs<
/p>
［
MAX_VERTEX_NUM];
//
顶点向量
AdjMatrix
arcs;
?
//
邻接矩阵
int
vexnum,
arcnum;
//
图的顶点数和弧数?
GraphKind
kind;
//
图的种类标志?
-
-
-
-
-
-
-
-
-
上一篇：shp文件格式
下一篇：判断点在多边形内的多种写法