数据结构基础知识要点.docx

数据结构基础知识要点.docx

《数据结构基础知识要点.docx》由会员分享，可在线阅读，更多相关《数据结构基础知识要点.docx（28页珍藏版）》请在冰点文库上搜索。

数据结构基础知识要点

第1章数据结构

1．定义

数据结构是计算机存储、组织数据的方式。

数据结构是抽象数据类型的物理实现。

2.数据结构包括如下几个方面：

（1）数据元素之间的逻辑关系,即数据的逻辑结构。

（2）数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。

（3）施加在该数据上的操作,即数据的运算。

2.逻辑结构类型

（1）集合结构。

交通工具的集合，动物的集合

（2）线性结构。

一对一，综合素质测评产生的学生排名

（3）树形结构。

一对多，单位的组织结构图，族谱

（4）图形结构。

多对多，生产流程、施工计划、网络建设图等

3.存储结构类型

（1）顺序存储方法。

数组

（2）链式存储方法。

链表

（3）索引存储方法

（4）散列存储方法

4.算法

通常把具体存储结构上的操作实现步骤或过程称为算法。

C语言里通常表现为解决问题的步骤

程序=算法（加工数据）+数据结构（数据的存储和组织）

5.算法的五个特征

（1）有穷性:

在有穷步之后结束。

（2）确定性:

无二义性。

（3）可行性:

可通过基本运算有限次执行来实现。

（4）有输入：

可有零个或多个。

（5）有输出:

至少有一个输出。

6.算法分析

（1）时间复杂度：

（算法的工作量大小）通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数。

算法中基本运算次数T（n）是问题规模n的某个函数f（n）,记作：

T（n）=O（f（n））

（2）空间复杂度：

实现算法所需的存储单元多少

第二章线性表

1.线性表的基本概念

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

该序列中所含元素的个数叫做线性表的长度,用n表示,n≥0。

2.线性结构的基本特征为:

（1）集合中必存在唯一的一个“第一元素”；

（2）集合中必存在唯一的一个“最后元素”；

　（3）除最后一个元素之外，均有唯一的后继（后件）；

　（4）除第一个元素之外，均有唯一的前驱（前件）。

3.定义顺序表

线性表逻辑结构

顺序表存储结构

typedefstruct

{

ElemTypedata[MAXCOUNT];序表上的运算及其实现

（1）.建立顺序表CreateList

创建一个空的顺序表，要完成线性表所需空间的分配和其他初始化设置。

（2）求线性表的长度ListLength

（3）输出线性表DispList

（4）在线性表中的指定位置插入一个元素InsertElem

（5）根据键值查找指定元素FindElemByNum

（6）获取指定位置的元素信息GetElem

（7）删除指定位置的元素DelElem

（8）释放线性表DestroyList

5.线性表的链式存储——单链表（data域和指针域next）

由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素,即数据元素之间是一对一的逻辑关系,所以当进行链式存储时,一种最简单也最常用的方法是:

在每个结点中除包含有数据域外,只设置一个指针域,用以指向其后继结点,这样构成的链接表称为线性单向链接表,简称单链表；

7.单链表的定义

LinkList类型的定义如下:

typedefstructLNode/*定义单链表结点类型*/

{

ElemTypedata;

structLNode*next;/*指向后继结点*/

}LinkList;

8.顺序表上的运算及其实现

1、创建单链表LinkList*CreateList（）;

2、初始化单链表voidInitList（LinkList*list）;

3、释放单链表voidDestroyList（LinkList*list）;

4、获取单链表中元素的数量intListLength（LinkList*list）;

5、输出单链表中的所有数据voidDispList（LinkList*list）;

6、获取单链表中指定位置的元素intGetElem（LinkList*list,intloc,ElemType*pElem）;

7、根据键值查找指定元素intFindElemByNum（LinkList*list,char*keyCh,ElemType*pElem）;

8、采用头插法向单链表中插入一个元素

intInsertElem_Head（LinkList*list,ElemTypemyElem）;

9、采用尾插法向单链表中插入一个元素

intInsertElem_Foot（LinkList*list,ElemTypemyElem）;

10、向单链表中的指定位置插入一个元素

ntInsertElem_Loc（LinkList*list,intloc,ElemTypemyElem）;

11、删除指定位置的元素

intDelElem（LinkList*list,intloc,ElemType*pElem）;

9.线性表的链式存储——双链表（data域指针域next和pre前驱）

对于双链表,采用类似于单链表的类型定义,其DLinkList类型的定义如下:

typedefstructDNode/*定义双链表结点类型*/

{

ElemTypedata;

structDNode*prior;/*指向前驱结点*/

structDNode*next;/*指向后继结点*/

}DLinkList

在双链表中p所指的结点之后插入一个*s结点。

其操作语句描述为:

s->next=p->next;/*将s插入到p之后*/

p->next->prior=s;

s->prior=p;

p->next=s;

归纳起来,删除双链表L中*p结点的后续结点。

其操作语句描述为:

p->next=q->next;

q->next->prior=p;

10.循环链表

循环链表是另一种形式的链式存储结构。

它的特点是表中最后一个结点的指针域不再是空,而是指向表头结点,整个链表形成一个环。

由此,从表中任一结点出发均可找到链表中其他结点。

带头结点的单向循环链表和双向循环链表如下图

第三章栈和队列

1.栈的定义及基本运算

栈是限定只能在表尾进行插入和删除的线性表，并将表尾称为栈顶，表头称为栈底。

栈的基本运算如下：

（1）判栈空IsEmpty（S）.若栈为空则返回“真“，否则返回”假“；

（2）入栈操作（压栈）Push（S,x）将新元素压入栈中，使其成为栈顶元素；

（3）出栈操作（弹栈）Pop（S,x）若栈不空则返回栈顶元素，并从栈中删除栈顶元素，否则返回NULL；

（4）取栈顶元素GetTop（s,x）若栈不空则返回栈顶元素，否则返回NULL；

（5）置空栈Clear（s）将当前栈设定为空栈；

2.顺序栈的存储结构及算法实现

1>顺序栈

顺序栈利用一组连续的存储单元存放从栈底到栈顶的诸元素。

typedefstruct

{

int*data;

intcapacity;

inttop;

}Stack;

2>顺序栈的基本运算的实现

（1）入栈操作intPush（StackS,Datatypex）；

（2）出栈操作intPop（Stacks,Datatype*x）；

（3）取栈顶操作intGetTop（StackS,Datatype*x）；

3.栈的链表存储结构

1>栈可以用单链表作为存储结构，链表的结点结构描述如下：

typedefcharElemType;

typedefstructLsnode

{

ElemTypedata;

structLsnode*next;

}Lsnode;出栈操作

链栈出栈操作的含义是：

从链栈中弹出栈顶结点并返回该结点中的元素值。

对该操作应设置一个参数，即在参数中指定一个链栈。

假设指定的链栈top,出栈操作取名为pop，则该操作可表示为:

ElemTypePop（Lsnode*top）

操作的功能为从由top指向的链栈中弹出栈顶结点并返回该结点中的元素值。

4.队列的基本操作

进队算法:

根据队列的结构，若队尾指针不在队的最大长度上，则首先队尾指针加１，元素进队，否则就是队满，无法进队。

ADDQUEUE（queue，r，f，in）

/*在queue队列中进一个元素in，f和r分别是队首和队尾的标志*/

{

if（r==n）

{

printf（"队满"）;

}

else

{

r++;

queue[r]=in;

}

}

出队算法:

出队首先要判断队列中是否有元素，即R是否等于F，R=F可能出现在初态，也可能出现在出队、进队的动态变化中。

DELQUEUE（queue，r，f，out）

/*在queue队列中退出一个元素到out，f和r分别是队首和队尾的标志*/

{

if（f==r）

　{

printf（"队空"）;

}

else

out=queue[++f];

}

5.链队的存储结构及其运算

当队空时，Front=NULL；Rear=NULL；所谓队满，是指在可利用的空间表中，所有的结点被取完，即AV=NULL时，才表示队满。

根据队列的操作特点，进队和退队分别在表的两端进行，具体表现为“先进先出”。

从链队的结构可看出，进队的基本操作步骤为（设进队结点的地址为x）：

Rear->next=x；

x->next=NULL；

Rear=x；

第四章串

1.串的基本概念

串结构的形式化定义为：

String=（D，R）

其中，D={ai︱ai∈character，i=1，2…n，n≥0}，R={︱ai-1，ai∈D，i=1，2，…n}串的基本运算有：

（1）初始化ClearString（s）：

初始化串s。

（2）StrAssign（s，ch）：

串赋值。

（3）StrCopy（s，t）：

串复制。

（4）StrConcat（t，s1，s2）：

串联接。

（5）求串长StrLen（s）：

返回s串的元素个数，即s串的长度。

（6）串比较StrCom（s，t）

（7）求子串SubStr（t，s，pos，len）：

返回s串的第pos个字符起始的长度为len的子串。

（8）插入运算StrInsert（s，pos，t）：

把串t的值插入到串s的第pos个字符之后。

（9）删除运算StrDel（s，pos，len）：

将串s中从第pos字符起始的长度为len的子串删除。

（10）子串定位StrIndex（s，t，pos）：

从主串s的第pos个字符起定位串s中是否存在和串t值相等的子串，若存在，则返回子串t在主串s中第一次出现的位置，否则，返回函数值0。

（11）置换运算StrReplace（s，pos，len,t）：

用t串置换s串中第pos字符开始的连续的len个字符。

2.串的定长顺序存储及运算实现

1>定长顺序串的基本运算实现

（1）求串长

（2）串的联接

（3）求子串

（4）子串的插入

（5）子串的删除

（6）串的置换

2>在堆式动态存储分配下的串的几种常见运算的实现。

（1）串赋值StrAssign（t，chars）

（2）串联接StrConcat（t，s1，s2）

（3）求子串SubString（t,s,pos,len）

（4）插入函数StrInsert（s,pos,t）

（5）删除函数StrDelete（s,pos,t）

3.串的块链存储表示

顺序串上的插入和删除操作运算需要移动大量的字符。

因此，可以采用单链表方式来存储串值，串的这种链式存储结构简称为链串。

但在利用链表存储串值时，每个结点既可以存放一个字符，也可以存放多个字符，即存在一个“结点大小”的问题。

结点的大小是指结点的数据域可存放字符的个数。

第六章树和二叉树

1.树的表示

（1）树形表示法。

这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象

（2）文氏图表示法。

使用集合以及集合的包含关系描述树结构。

（3）凹入表示法。

使用线段的伸缩描述树结构。

（4）括号表示法。

将树的根结点写在括号的左边,

除根结点之外的其余结点写在括号中并用逗号

间隔来描述树结构。

2.树的基本术语

1.结点的度与树的度：

树中某个结点的子树的个数称为该结点的度。

树中各结点的度的最大值称为树的度,通常将度为m的树称为m次树。

2.分支结点与叶结点：

度不为零的结点称为非终端结点,又叫分支结点。

度为零的结点称为终端结点或叶结点。

在分支结点中,每个结点的分支数就是该结点的度。

3.路径与路径长度：

如果一棵树中的一串结点n1,n2,…,nk,有如下关系：

结点ni是ni+1的父结点（1≤i

4.孩子结点、双亲结点和兄弟结点：

在一棵树中,每个结点的后继,被称作该结点的孩子结点（或子女结点）。

相应地,该结点被称作孩子结点的双亲结点（或父母结点）。

具有同一双亲的孩子结点互为兄弟结点。

进一步推广这些关系,可以把每个结点的所有子树中的结点称为该结点的子孙结点,从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点

5.结点的层次和树的高度：

树中的每个结点都处在一定的层次上。

结点的层次从树根开始定义,根结点为第1层,它的孩子结点为第2层,以此类推,一个结点所在的层次为其双亲结点所在的层次加1。

树中结点的最大层次称为树的高度（或树的深度）。

6.有序树和无序树：

若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则称为有序树,否则称为无序树。

7.森林：

n（n＞0）个互不相交的树的集合称为森林。

森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。

反之,只要给n棵独立的树加上一个结点,并把这n棵树作为该结点的子树,则森林就变成了树。

3.树的性质

性质1树中的结点数等于所有结点的度数加1。

性质2度为m的树中第i层上至多有mi-1个结点,这里应有i≥1。

性质3高度为h的m次树至多有个结点。

性质4具有n个结点的m次树的最小高度为?

logm（n（m-1）+1）?

。

4.树的特点：

①树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。

②树中所有结点可以有零个或多个后继结点。

5.树的基本运算

树的运算主要分为三大类：

第一类,寻找满足某种特定关系的结点,如寻找当前结点的双亲结点等；

第二类,插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；

第三类,遍历树中每个结点,这里着重介绍。

树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。

树的遍历运算的算法主要有先根遍历和后根遍历两种。

注意,下面的先根遍历和后根遍历算法都是递归的。

1.先根遍历

先根遍历过程为：

（1）访问根结点；

（2）按照从左到右的次序先根遍历根结点的每一棵子树。

2.后根遍历

后根遍历过程为：

（1）按照从左到右的次序后根遍历根结点的每一棵子树；

（2）访问根结点。

6.二叉树的定义

二叉树（BinaryTree）是n（n≥0）个结点的有限集合。

它或为空树（n＝0），或为非空树；对于非空树有：

（1）有一个特定的称之为根的结点；

（2）根结点以外的其余结点分别由两棵互不相交的称之为左子树和右子树的二叉树组成。

这个递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成的。

由于左、右子树也是二叉树，则由二叉树的定义，它们也可以为空。

由此，二叉树可以有五种基本形态

7.二叉树的重要性质

性质1二叉树第i（i≥1）层上至多有2i-1个结点。

性质2深度为k（k≥1）的二叉树至多有2k－1个结点。

性质3在任意二叉树中，若叶子结点（即度为零的结点）个数为n0，度为1的结点个数n1，度为2的结点个数为n2，那么n0=n2+1。

性质4具有n个（n＞0）结点的完全二叉树的高度为?

log2n+1?

或?

log2n?

+1。

性质5若对有n（1≤i≤n）个结点的完全二叉树进行顺序编号，那么，对于编号为i（i≥1）的结点：

当i=1时，该结点为根，它无双亲结点；

当i＞1时，该结点的双亲结点编号为?

i/2?

；

若2i≤n，则有编号为2i的左孩子，否则没有左孩子；

若2i+1≤n，则有编号为2i+1的右孩子，否则没有右孩子。

满二叉树：

深度为k且含有2k－1个结点的二叉树为满二叉树，这种树的特点是每层上的结点数都是最大结点数

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。

如图所示，（a）图就是一棵满二叉树，（b）图则不是满二叉树，因为，虽然其所有结点要么是含有左右子树的分支结点，要么是叶子结点，但由于其叶子未在同一层上，故不是满二叉树

完全二叉树：

深度为k，含有n个结点的二叉树，当且仅当每个结点的编号与相应满二叉树结点顺序号从1到n相对应时，则称此二叉树为完全二叉树

显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

如图所示（a）为一棵完全二叉树，（b）不是完全二叉树。

8.二叉树的顺序存储结构

二叉树的顺序存储结构中结点的存放次序是：

对该树中每个结点进行编号,其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。

若把二叉树存储到一维数组中,则该编号就是下标值加1（注意,C/C++语言中数组的起始下标为0）。

树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同

9.二叉树的链式存储结构

data表示值域,用于存储对应的数据元素,lchild和rchild分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点（即左、右子树的根结点）的存储位置

下图（a）给出一棵二叉树的二叉链表存储表示。

二叉链表也可以带头结点的方式存放，如图（b）所示。

二叉链表存储表示可描述为：

typedefstructbitnode

{

datatypedata;

structbitnode*lchild;*rchild;/*左右孩子指针域*/

}BiTNode,*BiTree;

定义指针变量，用来存放根结点地址，通常用该指针标识一个二叉树：

BiTreet;

10.二叉树遍历的概念

二叉树的遍历是指按照一定次序访问树中所有结点,并且每个结点仅被访问一次的过程。

它是最基本的运算,是二叉树中所有其他运算的基础。

1.先序遍历（DLR）

先序遍历二叉树的过程是：

（1）访问根结点；

（2）先序遍历左子树；

（3）先序遍历右子树。

voidPreOrder（BiTreebt）

{

if（bt==NULL）return;/*递归调用的结束条件*/

Visit（bt）;/*访问根结点*/

PreOrder（bt?

>lchild）;/*先序递归遍历bt的左子树*/

PreOrder（bt?

>rchild）;/*先序递归遍历bt的右子树*/

}

2.中序遍历（LDR）

中序遍历二叉树的过程是：

（1）中序遍历左子树；

（2）访问根结点；

（3）中序遍历右子树。

voidInOrder（BiTreebt）

{

if（bt==NULL）return;/*递归调用的结束条件*/

InOrder（bt?

>lchild）;/*中序递归遍历bt的左子树*/

Visit（bt）;/*访问根结点*/

InOrder（bt?

>rchild）;/*中序递归遍历bt的右子树*/

}

3.后序遍历（LRD）

后序遍历二叉树的过程是：

（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根结点。

voidPostOrder（BiTreebt）

{

if（bt==NULL）return;/*递归调用的结束条件*/

PostOrder（bt?

>lchild）;/*后序递归遍历bt的左子树*/

PostOrder（bt?

>rchild）;/*后序递归遍历bt的右子树*/

Visite（bt）;/*访问根结点*/

}

4.层次遍历

　其过程是：

　若二叉树非空（假设其高度为h），则：

（1）访问根结点（第1层）；

（2）从左到右访问第2层的所有结点；

　（3）从左到右访问第3层的所有结点、…、第h层的所有结点。

11.二叉树基本运算概述

（1）创建二叉树CreateBTNode（*b,*str）：

根据二叉树括号表示法的字符串*str生成对应的链式存储结构。

**Initiate（bt）：

建立一棵空的二叉树bt，并返回bt。

二叉树带不带头结点，可根据具体需要而定。

建立一棵空的带头结点的二叉树

BiTreeInitiate（）/*建立一棵空的带头结点的二叉树*/

{

BiTNode*bt;

bt=（BiTNode*）malloc（sizeof（BiTNode））;

bt?

>lchild=NULL

bt?

>rchild=NULL;

returnbt;

}

建立一棵空的不带头结点的二叉树

BiTreeInitiate（）/*初始建立一棵空的不带头结点的二叉树*/

{

BiTNode*bt;

bt=NULL;

returnbt;

}

在主函数中，可以通过如下方式调用Initiate函数：

main（）

{

BiTreet;/*定义根结点指针变量*/

t=Initiate（）;

voidDispBiTNode（BiTreeT）

{

if（T!

=NULL）

{

printf（"%c",T->data）;

if（T->lchild!

=NULL||T->rchild!

=NULL）

{

printf（"（"）;

DispBiTNode（T->lchild）;

printf（","）;

DispBiTNode（T->rchild）;

printf（"）"）;

}

}

}

……

}

**voidDispBTree（*bt）

算法：

对于非空二叉树bt：

先输出其元素值

当其有左孩子或右孩子时

输出（

递归输出左子树

输出，

递归输出右子树

输出）

（2）查找结点FindNode（*b,x）：

在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。

（3）找孩子结点LchildNode（p）和RchildNode（p）：

分别求二叉树中结点*p的左孩子结点和右孩子结点

（4）求高度BTNodeDepth（*b）：

求二叉树b的高度。

若二叉树为空,则其高度为0；否则,其高度等于左子树与右子树中的最大高度加l。

（5）输出二叉树DispBTNode（*b）：

以括号表示法输出一棵二叉树。

12.由遍历序列恢复二叉树（递归思想）

1、依据遍历定义：

由二叉树的先序序列和中序序列可唯