《数据结构》总复习

第1章绪论第6章树和二叉树

第2章线性表第7章广义表

第3章栈和队列第8章图

第4章串第9章查找

第5章数组和稀疏矩阵第10章内排序

1

第1章绪论

1.数据结构的定义

数据-〉数据元素->数据项

数据结构是指数据以及相互之间的联系。包括:

(1)数据的逻辑结构。

(2)数据的存储结构(物理结构)。

(3)施加在该数据上的运算。

数据的逻辑结构是从逻辑关系上描述数据，它

与数据的存储无关，是独立于计算机的。

数据的存储结构是逻辑结构用计算机语言的实

现（亦称为映象），它是依赖于计算机语言的。

数据的运算是定义在数据的逻辑结构上的，每

种逻辑结构都有一组相应的运算。但运算的实现与

数据的存储结构有关。

逻辑结构主要有两大类:

(1)线性结构

(2)非线性结构：

1)树形结构

2)图形结构

存储结构分为如下四种:

(1)顺序存储方法

(2)链式存储方法

(3)索引存储方法

(4)散列存储方法

2.抽象数据类型

抽象数据类型（AbstractDataType简写为

ADT）指的是用户进行软件系统设计时从问题的数

学模型中抽象出来的逻辑数据结构和逻辑数据结构

上的运算，而不考虑计算机的具体存储结构和运算

的具体实现算法。

3.什么是算法

算法是对特定问题求解步骤的一种描述，它

是指令的有限序列。

算法的五个重要的特性：

有

家

性

(1)

确

走

(2)性

可

行

性

(3)

入

输

有

(4)

出

输

有

(5)

4.算法分析,

(1)算法的时间复杂度：是指其基本运算

在算法中重复执行的次数。

算法中基本运算次数T(n)是问题规模n的某

个函数f(n),记作：

T(n)=O(f(n))

记号读作“大它表示随问题规

模n的增大算法执行时间的增长率和f(n)的增长

率相同。

(2)算法空间复杂度：是对一个算法在运行过

程中临时占用的存储空间大小的量度。

对于空间复杂度为0(1)的算法称为原地工

作或就地工作算法。

第2章线性表

1.线性表的定义

线性表是具有相同特性的数据元素的一个有

限序列。该序列中所含元素的个数叫做线性表的

长度，用n表示，n>0o当n=0时，表示线性表是

一个空表，即表中不包含任何元素。

1.线性表的顺序存储结构一顺序表

typedefstruct

|

ElemTypeelem[MaxSize];

/*存放顺序表元素刃

intlength;

/*存放顺序表的长度*/

}SqList;

顺序表基本运算的实现

插入数据元素算法：元素移动的次数不仅与表

长n有关；插入一个元素时所需移动元素的平均次

数n/2。平均时间复杂度为O(n)。

删除数据元素算法:元素移动的次数也与

表长n有关。删除一个元素时所需移动元素的

平均次数为(n-l)/2。删除算法的平均时间复杂

度为O(n)。

1

【例2.1]设计一个算法，招1x插入到一个有序

（从小到大排序）的线性表（顺序存储结构）的适当

位置上，并保持线性表的有序性。

voidInsert(SqList&A,ElemTypex)

inti=0J;

while(i<A.length&&AS.elem[i]<x)i++;

forg=A.length-l;j>=i;j-)

A.elem[j+l]=A.elem[j];

A.elem[i]=x;

A.length++;

2.线性表的链式存储结构一链表

定义单链表结点类型：

typedefstructLNode

ElemTypedata;

structLNode*next;

/*指向后继结点*/

}LinkList;

定义双链表结点类型：

typedefstructDNode

(

ElemTypedata;

structDNode*prior;

/*指向前驱结点*/

structDNode*next;

/*指向后继结点*/

}DLinkList;

(1)单链表基本运算的实现

重点：头插法建表和尾插法建表算法，它是

很多算法设计的基础。

【例24】设C={apbDa2，b2,…,a^bn}为一线

性表，采用带头结点的he单链表存放，编写

一个就地算法，将其拆分为两个线性表，使

得：

A—{a],a2，・.”an})C—{b0b2,•••,，}

voidfun(LinkListLinkList*&h%

LinkList*&hb)

(

LinkList*p=hc->next/ra/rb;

ha=hc;/*ha的头结点利用he的头结点*/

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.栈的顺序存储结构及其基本运算实现

typedefstruct

{

ElemTypeelem[MaxSize];

inttop;/*栈指针*/

}SqStack;

栈空条件:s->top==-1

栈满条件:s->top==MaxSize-l

3.栈的链式存储结构及其基本运算的实现

typedefstructlinknode

{

ElemTypedata;/*数据域*/

structlinknode*next;/*指针域*/

}LiStack;

带头结点的单链表来实现（也可不带头结点）

Ihead

栈空条件:s->next==NULL

栈满条件:？

3.2队列

1.队列的定义

・队列简称队，它也是一种运算受限的线性

表，其限制仅允许在表的一端进行插入，而在

表的另一端进行删除。进行插入的一端称做队

尾(rear)，进行删除的一端称做队首

(front)o

2.队列的顺序存储结构及其基本运算的实现

typedefstruct

(

ElemTypeelem[MaxSize];

intfront,rear;/*队首和队尾指针*/

}SqQueue;

把数组的前端和后端连接起来，形成一个环形的顺序

表，即把存储队列元素的表从逻辑上看成一个环，称为循

环队列。

循环队列首尾相连，当队首指针front=MaxSize・l后,

再前进一个位置就自动到0,这可以利用除法取余的运算

(%)来实现：

队首指针进1:front=(front+l)%MaxSize

队尾指针进1:rear=(rear+l)%MaxSize

队空条件：q->rear==q->front

队满条件：(q・>rear+l)%MaxSize==q->front

3.队列的链式存储结构及其基本运算的实现

structqnode

(

ElemTypedata;

structqnode*next;

}QNode;

typedefstruct

(

QNode/front;

QNode*rear;

}LiQueue;

第4章串

1•串的定义

串（或字符串），是由零个或多个字符组成的有穷

序列。含零个字符的串称为空串，用中表示。串中所

含字符的个数称为该串的长度（或串长）。

2•串的顺序存储结构-顺序串

3.串的链式存储结构一链串

KMP算法不作要求。

第5章数组和稀疏矩阵

1.教组的定义

数组是n(n>l)个相同类型数据元素

a1?a??•••?2口

构成的有限序列，且该有限序列存储在一块地址

连续的内存单元中。

2.数组的顺序存储结箱

对于数组人忙1・・(11«2・@]

以行序为主序：

LOC(%尸LOC(acic2)+Ki0)*(d2，+l)+(j0)]*k

以列序为主序

LOC(,尸LOC(F2)+[(jY2)*(di0+l)+(k)]*k

3.特殊矩阵的压缩存储:>

(1)对称矩阵

若一个n阶方阵Z[n][n]中的元素满足4可=2币(09

j<n-l),则称其为n阶对称矩阵。

A[0..n-l][0..n-l]->B[0..n(n+l)/2]

.i(i+l)/2+j当日时

k=1

〔j(j+l)/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[2H2])为多少?

答：Loc(A[2][2])=Loc(A[0][0])+[(2-0)*(3-

0+1)+(2-0)]*2=1020。

第6章树和二叉树

6.1树

L树的定义

树是由n（n>0）个结点组成的有限集合（记为T）。

其中，

如果n=0，它是一棵空树,这是树的特例；

如果n>0,这n个结点中存在（有仅存在）一个结点

作为树的根结点，简称为根（root）,其余结点可分为

m（m>0）个互不相交的有限集T2,…，Tm,其

中每一棵子集本身又是一棵符合本定义的树，称为根

树:""------------—一—

2.树的表示法(逻辑表示方法)

(1)树形表示法

(2)文氏图表示法

(3)凹入表示法

(4)括号表示法

3.树■的遍历

先根遍历算法为：

(1)访问根结点；

(2)按照从左到右的次序先根遍历根结点的每一

棵子树。

后根遍历算法为：

(1)按照从左到右的次序后根遍历根结点的每一

棵子树；

(2)访问根结点。

4.树（森林）与二叉树之间的相互转换

6.2二叉树

1.二叉树的定义

二叉树也称为二次树或二分树，它是有限的

结点集合，这个集合或者是空，或者由一个根结

点和两棵互不相交的称为左子树和右子树的二叉

树组成。

完全二叉树，满二叉树的定义

2.二叉树性质:>

性质1非空二叉树上叶结点数等于双分支结点

数力口1。^110=02+1.

性质2非空二叉树上第i层上至多有2川个结点

(i>l)o

性质3高度为h的二叉树至多有2也1个结点

(h>l)o

性质4完全二叉树的性质。

性质5具有n个(!>〉0)结点的完全二叉树的高

度为「logzn+l］或I_log2n」+L

.【例6.11将一棵有100个结点的完全二叉树从根

这一层开始，每一层从左到右依次对结点进行编号,

根结点的编号为L则编号为49的结点的左孩子编

号为_。

A.98B.99C.50D.48

答：A

【例6.2］深度为5的二叉树至多有一个结点。

A.16B.32C.31D.10

答：相同满度时满二叉树结点最多，h=5的满

二叉树结点个数=25・1=31。本题答案应为C。

3.二叉树存储结构

(1)二叉树的顺序存储结构

(2)二叉链存储结构

typedefstructnode

{ElemTypedata;/*数据元素*/

structnode^Ichild;/*指向左孩子*/

structnode*rchild;/*指向右孩子*/

}BTNode;

4.二叉树的遍历

(1)先序遍历

voidpreorder(BTNode*t)

printf(^%d9\t->data);

preorder(t->lchild);

preorder(t->rchild);

(2)中序遍历

voidinorder(BTNode*t)

{

inorder(t->lchild);

printf(u%d9\t->data);

inorder(t->rchild);

(3)后序遍历

voidpostorder(BTNode*t)

(

postorder(t->lchild);

postorder(t->rchild);

printf(66%d9\t->data);

注意：重点掌握基于遍历的递归算法设计。

5.二叉树的构造

任何n(n>0)个不同结点的二又树，都

可由它的中序序列和先序序列惟一地确定。

任何n(n>0)个不同结点的二又树，都

可由它的中序序列和后序序列惟一地确定。

掌握它们的构造方法。

■

6.线索二叉树一一一

⑴线索二叉树的概念

对于具有n个结点的二叉树，采用二叉链存储

结构时，每个结点有两个指针域，总共有2n个指

针域，又由于只有n・l个结点被有效指针所指向

（树根结点没有被有效指针域所指向），则共有

个空链域。

遍历二叉树的结果是一个结点的线性序列。可以

的

利用这些空链域存放指向结点的前驱和后继结点

后

指针。这样的指向该线性序列中的“前驱”和“

继”的指针，称作线索。

对二叉树以某种方式遍历使其变为线索二叉树

的过程称作按该方式对二叉树进行线索化。

(2)二叉树进行线索化的过程

不要求掌握算法。

63哈夫寺时

L哈夫曼树的定义

在n个带权叶子结点构成的所有二叉树中，

带权路径长度WPL最小的二叉树称为哈夫曼树

（或最优二叉树）。

2.哈夫曼树的构造过程

3.哈夫曼编码的构造过程

第7章广义表

相关概念：

一个广义表中所含元素的个数称为它的长度..

一个广义表中括号嵌套的最大次数为它的深度.

表的第一个元素a1为广义表GL的表头，其余部

分如为的表尾.

(a2,•…ai+1,•…a)GL

第8章图

1.图的基本概念

(1)顶点的度、入度和出度

⑵完全图

(3)子图

(4)路径和路径长度

(5)连通、连通图和连通分量

(6)强连通图和强连通分量

⑺权和网

2.图的存储结构

(1)邻接矩阵存储方法

(2)邻接表存储方法

掌握两种存储方法的优缺点，

同一种功能在不同存储结构上的实

现算法。

3.图的遍历

(1)深度优先搜索遍历

voidDFS(ALGraph*G,intv)

(

ArcNode*p;Visited[v]=1;/*置已访问标记*/

printf(n%d!\v);/*输出被访问顶点的编号*/

p=G->adjlist[v].firstare;

/*p指向顶点v的第一条弧的弧头结点刃

while(p!=NULL)

{if(visited[p->adjvex]==0)

DFS(G,p->adjvex);

p=p->nextarc;

/*p指向顶点v的下一条弧的弧头结点*/

(2)广度优先搜索遍历"-----

voidBFS(ALGraph*G,intv「‘

{ArcNode*p;

intqueue[MAXV]5front=05rear=0;

/*定义循环队列并初始化*/

intvisited[MAXV];

/*定义存放结点的访问标志的数组*/

intw,i;

for(i=0;i<G->n;i++)visited[i]=0;

/*访问标志数组初始化*/

printf(n%2df;v);

visited[v]=l;/*置已访问标记*/

―rear=(rear+l)%MAXV;——_

queue[rear]=v;/*v进队*/

while(front!=rear)/*若队列不空时循环*/

{front=(front+l)%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]=l;

rear=(rear+l)%MAXV;

queue[rear]=p->adjvex;

)

p=p->nextarc;

printf(n\nn);

■

，(3)非连通图的遍历一•/

采用深度优先搜索遍历非连通无向图的算法如下:

DFSl(ALGraph*g)

{

inti;

for(i=0;i<g->n;i+)

if(visited[i]==0)

DFS(gJ);

采用广度优先搜索遍历非连通无向图的算法如下:

BFSl(ALGraph*g)

inti;

for(i=0;i<g->n;i+)

if(visited[i]==0)

BFS(g4)；

【例