数据结构考研讲义全.docx

数据结构考研讲义全.docx

《数据结构考研讲义全.docx》由会员分享，可在线阅读，更多相关《数据结构考研讲义全.docx（92页珍藏版）》请在冰点文库上搜索。

数据结构考研讲义全

绪论

0.1基本概念

1、数据结构

数据结构是指互相之间存在着一种或多种关系的数据元素的集合。

数据结构是一个二元组Data_Structure＝（D，R），其中，D是数据元素的有限集，R是D上关系的有限集。

2、逻辑结构：

是指数据之间的相互关系。

通常分为四类结构：

（1）集合：

结构中的数据元素除了同属于一种类型外，别无其它关系。

（2）线性结构：

结构中的数据元素之间存在一对一的关系。

（3）树型结构：

结构中的数据元素之间存在一对多的关系。

（4）图状结构：

结构中的数据元素之间存在多对多的关系。

3、存储结构：

是指数据结构在计算机中的表示，又称为数据的物理结构。

通常由四种基本的存储方法实现：

（1）顺序存储方式。

数据元素顺序存放，每个存储结点只含一个元素。

存储位置反映数据元素间的逻辑关系。

存储密度大。

但有些操作（如插入、删除）效率较差。

（2）链式存储方式。

每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。

指针反映数据元素间的逻辑关系。

这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。

（3）索引存储方式。

除数据元素存储在一组地址连续的存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。

（4）散列存储方式。

通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间，并将散列函数的值解释成关键字所在元素的存储地址。

其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。

2算法和算法的衡量

1、算法是对特定问题求解步骤的一种描述，是指令的有限序列。

其中每一条指令表示一个或多个操作。

算法具有下列特性：

⑴有穷性⑵确定性⑶可行性⑷输入⑸输出。

算法和程序十分相似，但又有区别。

程序不一定具有有穷性，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。

算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。

一个算法若用程序设计语言来描述，则它就是一个程序。

2、算法的时间复杂度：

以基本运算的原操作重复执行的次数作为算法的时间度量。

一般情况下，算法中基本运算次数T（n）是问题规模n（输入量的多少，称之为问题规模）的某个函数f（n），记作：

T（n）＝Ο（f（n））；也可表示T（n）＝m（f（n）），其中m为常量。

记号“O”读作“大O”，它表示随问题规模n的增大，算法执行时间T（n）的增长率和f（n）的增长率一样。

注意：

有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。

常见的渐进时间复杂度有：

Ο

（1）＜Ο（log2n）＜Ο（n）＜Ο（nlog2n）＜Ο（n2）＜Ο（n3）＜Ο（2n）＜O（n!

）＜O（nn）。

3、算法的空间复杂度：

是对一个算法在运行过程中临时占用的存储空间大小的量度。

只需要

分析除输入和程序之外的辅助变量所占额外空间。

原地工作：

若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作，空

间复杂度为O

（1）。

第一章线性表

1.1线性表的定义

线性表是一种线性结构，在一个线性表中数据元素的类型是一样的，或者说线性表是由同一类型的数据元素构成的线性结构，定义如下：

线性表是具有一样数据类型的n（n≥0）个数据元素的有限序列，通常记为：

（a1，a2，…ai-1，ai，ai+1，…an）

其中n为表长，n＝0时称为空表。

需要说明的是：

ai为序号为i的数据元素（i=1,2,…,n），通常将它的数据类型抽象为ElemType，ElemType根据具体问题而定。

1.2线性表的实现

1.2.1线性表的顺序存储结构

1.顺序表

线性表的顺序存储是指在存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。

因为存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单又自然的。

设a１的存储地址为Loc（a１），每个数据元素占d个存储地址，则第i个数据元素的地址为：

Loc（ai）=Loc（a１）+（i-1）*d1≤i≤n

这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。

线性表的动态分配顺序存储结构：

#defineLIST_INIT_SIZE100//存储空间的初始分配量

#defineLISTINCREMENT10//存储空间的分配增量

typedefstruct{

ElemType*elem;//线性表的存储空间基址

intlength;//当前长度

intlistsize;//当前已分配的存储空间

}SqList;

2.顺序表上基本运算的实现

（1）顺序表的初始化

顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为引用参数，

首先动态分配存储空间，然后，将length置为0，表示表中没有数据元素。

intInit_SqList（SqList&L）{

L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;

if（!

L.elem）exit（OVERFLOW）;//存储分配失败

L.length=0;

L.listsize=LIST_INIT_SIZE;//初始存储容量

returnOK;

}

（2）插入运算

线性表的插入是指在表的第i（i的取值围：

1≤i≤n+1）个位置上插入一个值为x的新元素，

插入后使原表长为n的表:

（a1，a2，...，ai-1，ai，ai+1，...，an）

成为表长为n+1表:

（a1，a2，...，ai-1，x，ai，ai+1，...，an）。

顺序表上完成这一运算则通过以下步骤进行：

①将ai～an顺序向下移动，为新元素让出位置；（注意数据的移动方向：

从后往前依次后移一个元素）

②将x置入空出的第i个位置；

③修改表长。

intInsert_SqList（SqList&L，inti，ElemTypex）{

if（i<1||i>L.length+1）returnERROR;//插入位置不合法

if（L.length>=L.listsize）returnOVERFLOW;//当前存储空间已满,不能插入

//需注意的是，若是采用动态分配的顺序表，当存储空间已满时也可增加分配

q=&（L.elem[i-1]）;//q指示插入位置

for（p=&（L.elem[L.length-1]）;p>=q;--p）

*（p+1）=*p;//插入位置与之后的元素右移

*q=e;//插入e

++L.length;//表长增1

returnOK;

}

顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入x，从ai到an都要向下移动一个位置，共需要移动n－i＋1个元素。

（3）删除运算

线性表的删除运算是指将表中第i（i的取值围为：

1≤i≤n）个元素从线性表中去掉，

删除后使原表长为n的线性表：

（a1，a2，...，ai-1，ai，ai+1，...，an）

成为表长为n－1的线性表：

（a1，a2，...，ai-1，ai+1，...，an）。

顺序表上完成这一运算的步骤如下：

①将ai+1～an顺序向上移动；（注意数据的移动方向：

从前往后依次前移一个元素）

②修改表长。

intDelete_SqList（SqList&L;inti）{

if（（i<1）||（i>L.length））returnERROR;//删除位置不合法

p=&（L.elem[i-1]）;//p为被删除元素的位置

e=*p;//被删除元素的值赋给e

q=L.elem+L.length-1;//表尾元素的位置

for（++p;p<=q;++p）

*（p-1）=*p;//被删除元素之后的元素左移

--L.length;//表长减1

returnOK;

}

顺序表的删除运算与插入运算一样，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素，顺序表的插入、删除需移动大量元素O（n）；但在尾端插入、删除效率高O

（1）。

1.2.2线性表的链式存储结构

1.2.2.1单链表

1.链表表示

链表是通过一组任意的存储单元来存储线性表中的数据元素的。

为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存储单元的地址，这两部分信息组成一个“结点”，结点的结构如图所示。

其中，存放数据元素信息的称为数据域，存放其后继地址的称为指针域。

因此n个元素的线性表通过每个结点的指针域拉成了一个“链”，称之为链表。

因为每个结点中只有一个指向后继的指针，所以称其为单链表。

线性表的单链表存储结构C语言描述下：

typedefstructLNode{

ElemTypedata;//数据域

structLNode*next;//指针域

}LNode，*LinkList;

LinkListL；//L为单链表的头指针

通常用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L、H中，头指针为“NULL”则表示一个空表。

2.单链表上基本运算的实现

（1）建立单链表

单链表结点结构

datanext

●头插法——在链表的头部插入结点建立单链表

链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始，每读入一个数据元素则申请一个结点，然后插在链表的头部。

LinkListCreateListF（）{

LinkListL=NULL；//空表

LNode*s;

intx;//设数据元素的类型为int

scanf（＂%d＂,&x）;

while（x!

=flag）{

s=（LNode*）malloc（sizeof（LNode））;

s->data=x;

s->next=L;L=s;

scanf（＂%d＂,&x）;

}

returnL;

}

●尾插法——在单链表的尾部插入结点建立单链表

头插入建立单链表简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插入的方法。

因为每次是将新结点插入到链表的尾部，所以需加入一个指针r用来始终指向链表中的尾结点，以便能够将新结点插入到链表的尾部。

初始状态，头指针L=NULL，尾指针r=NULL;按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到r所指结点的后面，然后r指向新结点（注意第一个结点有所不同）。

LinkListCreateListR1（）{

LinkListL=NULL;

LNode*s,*r=NULL;

intx;//设数据元素的类型为int

scanf（＂%d＂,&x）;

while（x!

=flag）{

s=（LNode*）malloc（sizeof（LNode））;

s->data=x;

if（L==NULL）L=s;//第一个结点的处理

elser->next=s;//其它结点的处理

r=s;//r指向新的尾结点

scanf（＂%d＂,&x）;

}

if（r!

=NULL）r->next=NULL;//对于非空表，最后结点的指针域放空指针

returnL;

}

在算法CreateListR1中，第一个结点的处理和其它结点是不同的，原因是第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整个链表的指针，需要放在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。

“第一个结点”的问题在很多操作中都会遇到，如在链表中插入结点时，将结点插在第一个位置和其它位置是不同的，在链表中删除结点时，删除第一个结点和其它结点的处理也是不同的，等等。

为了方便操作，有时在链表的头部加入一个“头结点”，头结点的类型与数据结点一致，标识链表的头指针变量L中存放该结点的地址，这样即使是空表，头指针变量L也不为空了。

头结点的加入使得“第一个结点”的问题不再存在，也使得“空表”和“非空表”的处理成为一致。

头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，空表时为空。

尾插法建立带头结点的单链表，将算法CreateListR1改写成算法CreateListR2形式。

LinkListCreateListR2（）{

LinkListL=（LNode*）malloc（sizeof（LNode））;

L->next=NULL；//空表

LNode*s,*r=L;

intx;//设数据元素的类型为int

scanf（＂%d＂,&x）;

while（x!

=flag）{

s=（LNode*）malloc（sizeof（LNode））;

s->data=x;

r->next=s;

r=s;//r指向新的尾结点

scanf（＂%d＂,&x）;

}

r->next=NULL;

returnL;

}

因此，头结点的加入会带来以下两个优点：

第一个优点：

由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；

第二个优点：

无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。

在以后的算法中不加说明则认为单链表是带头结点的。

（2）查找操作

●按序号查找Get_LinkList（L,i）

从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止，没有第ｉ个结点时返回空。

LNode*Get_LinkList（LinkListL,inti）;{

LNode*p=L;

intj=0;

while（p->next!

=NULL&&j

p=p->next;j++;

}

if（j==i）returnp;

elsereturnNULL;

}

（3）插入运算

●后插结点：

设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面，插入示意图如图所示。

操作如下：

①s->next=p->next;

②p->next=s;

注意：

两个指针的操作顺序不能交换。

（4）删除运算

●删除结点

设p指向单链表中某结点，删除*p。

操作过程如图。

要实现对结点*p的删除，首先要找到*p的前驱结点*q，然后完成指针的操作即可。

操作如下：

①q=L;

while（q->next!

=p）

q=q->next;//找*p的直接前驱

②q->next=p->next;

free（p）;

因为找*p前驱的时间复杂度为O（n），所以该操作的时间复杂度为O（n）

通过上面的基本操作我们得知：

（1）单链表上插入、删除一个结点，必须知道其前驱结点。

（2）单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。

1.2.2.2循环链表

对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。

在单循环链表上的操作基本上与非循环链表一样，只是将原来判断指针是否为NULL变为是否是头指针而已，没有其它较大的变化。

对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使得操作效率得以提高。

1.2.2.3双向链表

单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p->next，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，也就是说找后继的时间性能是O

（1），找前驱的时间性能是O（n），如果也希望找前驱的时间性能达到O

（1），则只能付出空间的代价：

每个结点再加一个指向前驱的指针域，结点的结构为如图所示，用这种结点组成的链表称为双向链表。

线性表的双向链表存储结构C语言描述下：

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior,*next;

}DuLNode,*DuLinkList;

和单链表类似，双向链表通常也是用头指针标识，也可以带头结点。

（1）双向链表中结点的插入：

设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如所示。

操作如下：

①s->prior=p->prior;

②p->prior->next=s;

③s->next=p;

④p->prior=s;

指针操作的顺序不是唯一的，但也不是任意的，操作①必须要放到操作④的前面完成，否则*p的前驱结点的指针就丢掉了。

（2）双向链表中结点的删除：

设p指向双向链表中某结点，删除*p。

操作示意图如图所示。

操作如下：

①p->prior->next=p->next;

②p->next->prior=p->prior;

free（p）;

1.2.2.4顺序表和链表的比较

总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。

通常“较稳定”

的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。

第二章栈、队列和数组

2.1栈

2.1.1栈的定义

栈是限制在表的一端进行插入和删除的线性表。

允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。

当表中没有元素时称为空栈。

2.1.2栈的存储实现和运算实现

栈是运算受限的线性表，线性表的存储结构对栈也是适用的，只是操作不同而已。

利用顺序存储方式实现的栈称为顺序栈。

与线性表类似，栈的动态分配顺序存储结构如下：

#defineSTACK_INIT_SIZE100//存储空间的初始分配量

#defineSTACKINCREMENT10//存储空间的分配增量

typedefstruct{

SElemType*base;//在栈构造之前和销毁之后，base的值为NULL

SElemType*top;//栈顶指针

intstacksize;//当前已分配的存储空间

}SqStack;

需要注意，在栈的动态分配顺序存储结构中，base始终指向栈底元素，非空栈中的top始终在栈顶元素的下一个位置。

下面是顺序栈上常用的基本操作的实现。

（1）入栈：

若栈不满，则将e插入栈顶。

intPush（SqStack&S,SElemTypee）{

if（S.top-S.base>=S.stacksize）

{……}//栈满，追加存储空间

*S.top++=e;//top始终在栈顶元素的下一个位置

returnOK;

}

（2）出栈：

若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR。

intPop（SqStack&S,SElemType&e）{

if（S.top==S.base）returnERROR;

e=*--S.top;

returnOK;

}

出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。

通常栈空常作为一种控制转移的条件。

2.1.3栈的应用举例

由于栈的“先进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。

1．数制转换

十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：

假设现要编制一个满足下列要求的程序：

对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。

由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。

因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。

算法思想：

当N>0时重复

（1），

（2）

（1）若N≠0，则将N%r压入栈s中，执行

（2）;若N=0，将栈s的容依次出栈，算法结束。

（2）用N/r代替N。

voidconversion（）{

InitStack（S）;//构造空栈

scanf（"%d",N）;

while（N）{

Push（S,N%8）;

N=N/8;

}

while（!

StackEmpty（S））{

Pop（S,e）;

printf（"%d",e）;

}}

2..表达式求值

表达式求值是程序设计语言编译中一个最基本的问题，它的实现也是需要栈的加入。

下面的算法是由运算符优先法对表达式求值。

在此仅限于讨论只含二目运算符的算术表达式。

（1）中缀表达式求值：

中缀表达式：

每个二目运算符在两个运算量的中间，假设所讨论的算术运算符包括：

+、-、*、/、%、^（乘方）和括号（）。

设运算规则为：

．运算符的优先级为：

（）——>^——>＊、/、%——>+、-；

．有括号出现时先算括号的，后算括号外的，多层括号，由向外进行；

．乘方连续出现时先算最右面的。

表达式作为一个满足表达式语法规则的串存储，如表达式“3*2^（4+2*2-１*3）-5”,它的的求值过程为：

自左向右扫描表达式，当扫描到3*2时不能马上计算，因为后面可能还有更高的运算，正确的处理过程是：

需要两个栈：

对象栈s1和运算符栈s2。

当自左至右扫描表达式的每一个字符时，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从运算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符。

中缀表达式表达式“3*2^（4+2*2-１*3）-5”求值过程中两个栈的状态情况见图所示。

图中缀表达式3*2^（4+2*2-1*3）-5的求值过程

为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式，后缀表达式的运算符在运算对象之