数据结构考试复习

复习课第一章

基本概念一、数据与数据结构二、数据类型是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位

数据类型

是一个值的集合和定义在此集合上的一组操作的总称。

不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构关系的映象方法：（表示x,y的方法）顺序映象以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C而C是一个隐含值，整个存储结构中只含数据元素本身的信息xy链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx

算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1．有穷性

2．确定性3．可行性4．有输入5．有输出算法算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性2.可读性3．健壮性4．高效率与低存储量需求

假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))称T(n)为算法的(渐近)时间复杂度。算法=控制结构+原操作（固有数据类型的操作）算法的执行时间

=原操作(i)的执行次数×原操作(i)的执行时间

算法的执行时间

与

原操作执行次数之和

成正比

从算法中选取一种对于所研究的问题来说是基本操作

的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。例一两个矩阵相乘voidmult(inta[],intb[],int&c[]){

//以二维数组存储矩阵元素，c为a和b的乘积

for(i=1;i<=n;++i)

for(j=1;j<=n;++j){c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作时间复杂度:

O(n3)例二选择排序voidselect_sort(int&a[],intn){

//将a中整数序列重新排列成自小至大有序的整数序列。

}//select_sort基本操作:

比较(数据元素)操作时间复杂度:

O(n2)j=i;//

选择第i个最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}例三起泡排序voidbubble_sort(int&a[],intn){

//将a中整数序列重新排列成自小至大有序的整数序列。for

(i=n-1,change=TRUE;i>1&&change;--i)}//bubble_sort基本操作:

赋值操作时间复杂度:

O(n2){

change=FALSE;

//change为元素进行交换标志

for(j=0;j<i;++j)

if(a[j]>a[j+1])

{

a[j]←→a[j+1];

change=TRUE;}}//一趟起泡算法的存储空间需求算法的空间复杂度定义为:

表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。S(n)=O(g(n))第二章

线性表一、线性表的类型定义二、线性表类型的实现抽象数据类型线性表的定义如下：ADTList{

数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{称n

为线性表的表长;

称n=0

时的线性表为空表。}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),

称i为ai在线性表中的位序。}∈读作属于

假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。

现要求一个新的集合

A＝A∪B。∪是联集∩是交集例最简单的一种顺序映象方法是：

令y的存储位置和x的存储位置相邻。顺序映象——

以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>。

用一组地址连续的存储单元

依次存放线性表中的数据元素

a1a2

…ai-1ai

…an线性表的起始地址称作线性表的基地址以“存储位置相邻”表示有序对<ai-1，ai>

即：LOC(ai)=LOC(ai-1)+C

一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置

LOC(ai)=

LOC(a1)+(i-1)×C

↑基地址

用一组地址任意的存储单元存放线性表中的数据元素。单链表以元素(数据元素的映象)

+指针(指示后继元素存储位置)=结点

(表示数据元素或数据元素的映象)以“结点的序列”表示线性表

称作链表

以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。头结点

a1a2…...an^头指针头指针

有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空

在单链表中删除第

i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq

1.双向链表其它形式的链表typedefstructDuLNode{ElemTypedata;

//数据域

structDuLNode*prior;

//指向前驱的指针域

structDuLNode*next;

//

指向后继的指针域}

DuLNode,*DuLinkList;

最后一个结点的指针域的指针又指回第一个结点的链表a1a2…...an2.循环链表

和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。双向循环链表空表非空表a1a2…...an第三章

栈和队列一、栈的类型定义和实现二、队列的类型定义和实现通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

线性表栈队列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n栈和队列是两种常用的数据类型Push(&S,e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。

a1a2ane……Pop(&S,&e)

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1

……

栈类型的实现顺序栈链栈

EnQueue(&Q,e)

初始条件：队列Q已存在。

操作结果：插入元素e为Q的新的队尾元素。a1a2ane……

DeQueue(&Q,&e)

初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。a1a2an……

队列类型的实现链队列——链式映象循环队列——顺序映象typedefstruct{//链队列类型

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列#defineMAXQSIZE100//最大队列长度

typedefstruct{QElemType*base;//动态分配存储空间

intfront;//头指针，若队列不空，

//指向队列头元素

intrear;//尾指针，若队列不空，指向

//队列尾元素的下一个位置

}SqQueue;循环队列——顺序映象第四章

串一、串的数据类型定义二、串的表示与实现一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示串的块链存储表示也可用链表来存储串值，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。存储密度

=数据元素所占存储位实际分配的存储位第五章

数组与广义表一、数组的类型定义和实现二、广义表的类型定义和实现数组的顺序表示和实现

类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是一个一维的结构。

有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。例如：

称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j

的存储位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

推广到一般情况，可得到n维数组数据元素存储位置的映象关系

称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1<in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为

0.05的矩阵为稀疏矩阵。稀疏矩阵的压缩存储何谓稀疏矩阵？十字链表30050-100200011314522-1312^^^^^^^广义表是递归定义的线性结构，LS=(1,2,,n)其中：i

或为原子或为广义表例如:A=()F=(d,(e))D=((a,(b,c)),F)C=(A,D,F)B=(a,B)=(a,(a,(a,,)))广义表是一个多层次的线性结构例如：D=(E,F)其中:

E=(a,

(b,

c))

F=(d,(e))DEFa()d()bce第六章

树和二叉树一、树和二叉树的类型定义二、二叉树的遍历三、哈夫曼树与哈夫曼编码~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素

(无前驱)

根结点

(无前驱)最后一个数据元素

(无后继)多个叶子结点

(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcdefghij

性质1：

在二叉树的第i

层上至多有2i-1个结点。(i≥1)用归纳法证明：

归纳基：

归纳假设：

归纳证明：i=1

层时，只有一个根结点：

2i-1=20=1；假设对所有的j，1≤j

i，命题成立；二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1

。性质2：

深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：

基于上一条性质，深度为k的二叉树上的结点数至多为

20+21+

+2k-1=2k-1

。

性质3：

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为

2

的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。

性质4：

具有n个结点的完全二叉树的深度为

log2n+1。证明：设完全二叉树的深度为k则根据第二条性质得2k-1≤n<2k

即

k-1≤log2n<k

因为k只能是整数，因此，k=log2n

+1。性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1

至n

的编号，则对完全二叉树中任意一个编号为i

的结点：

(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；

(2)若2i>n，则该结点无左孩子，

否则，编号为2i的结点为其左孩子结点；

(3)若2i+1>n，则该结点无右孩子结点，

否则，编号为2i+1的结点为其右孩子结点。二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示例如:ABCDEF

ABDCEF

0123456789101112131401326二、二叉树的链式存储表示1.二叉链表2．三叉链表3．双亲链表4．线索链表

“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，

每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法哈夫曼树与

哈夫曼编码

最优树的定义

如何构造最优树

前缀编码

最优树的定义树的路径长度定义为：

树中每个结点的路径长度之和。

结点的路径长度定义为：

从根结点到该结点的路径上分支的数目。

树的带权路径长度定义为：

树中所有叶子结点的带权路径长度之和

WPL(T)=wklk(对所有叶子结点)。

在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。例如：

指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。前缀编码

利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。第七章

图一、图的存储表示二、图的遍历三、最小生成树与最短路径顶点的出度:以顶点v为弧尾的弧的数目；ABECF对有向图来说，顶点的入度:以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3有向图的邻接矩阵为非对称矩阵ABECF142301201234ABCDE有向图的邻接表ABECF可见，在有向图的邻接表中不易找到指向该顶点的弧。图的遍历

从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索广度优先搜索最小生成树

假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？问题：

构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。算法二：（克鲁斯卡尔算法）该问题等价于：算法一：（普里姆算法）两点之间的

最短路径问题

求从某个源点到其余各点的最短路径

每一对顶点之间的最短路径

求从源点到其余各点的最短路径的算法的基本思想:

依最短路径的长度递增的次序求得各条路径源点v1…其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。v2第九章

查找一、静态查找表二、动态查找树表三、哈希表(n)(1)(n)(1)(nlogn)综合上一节讨论的几种查找表的特性：查找插入删除无序顺序表

无序线性链表有序顺序表

有序线性链表

静态查找树表(n)(n)(logn)(n)(logn)(1)(1)(n)(1)(nlogn)（1）若它的左子树不空，则左子树上

所有结点的值均小于根结点的值；二叉排序树：

二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上

所有结点的值均大于根结点的值；

二叉平衡树是二叉查找树的另一种形式，其特点为：

树中每个结点的左、右子树深度之差的绝对值不大于1。例如:548254821是平衡树不是平衡树查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，哈希表是什么？

查找的过程为给定值依次和关键字集合中各个关键字进行比较，

查找的效率取决于和给定值进行比较的关键字个数。构造哈希函数的方法

对数字的关键字可有下列构造方法：

若是非数字关键字，则需先对其进行数字化处理。1.

直接定址法3.平方取中法5.除留余数法4.折叠法6.随机数法2.数字分析法处理冲突的方法

“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。1.开放定址法2.链地址法第十章

排序一、排序的定义二、内部排序方法的分类一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23