自考数据结构重点珍藏版Word文件下载.docx

资源描述

自考数据结构重点珍藏版Word文件下载.docx

《自考数据结构重点珍藏版Word文件下载.docx》由会员分享，可在线阅读，更多相关《自考数据结构重点珍藏版Word文件下载.docx（41页珍藏版）》请在冰点文库上搜索。

自考数据结构重点珍藏版Word文件下载.docx

是指抽象数据的组织和与之相关的操作。

可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。

抽象数据类型可以看作是描述问题的模型，它独立于具体实现。

它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。

9.算法+数据结构=程序

数据结构：

是指数据的逻辑结构和存储结构

算法：

是对数据运算的描述

10.数据的运算通过算法描述的。

算法是任意一个良定义的计算过程。

它以一个或多个值作为输入，并产生一个或多个值作为输出。

若一个算法对于每个输入实例均能终止并给出正确的结果，则称该算法是正确的。

正确的算法解决了给定的计算问题。

11.选用的算法首先应该是"

正确"

的。

此外，主要考虑如下三点：

①执行算法所耗费的时间；

②执行算法所耗费的存储空间，其中主要考虑辅助存储空间；

③算法应易于理解，易于编码，易于调试等等。

12.一个算法所耗费的时间=算法中每条语句的执行时间之和，每条语句的执行时间=语句的执行次数（即频度（FrequencyCount））×

语句执行一次所需时间。

13.算法求解问题的输入量称为问题的规模（Size）,一般用一个整数表示。

14.一个算法的时间复杂度T（n）是该算法的时间耗费，是该算法所求解问题规模n的函数。

当问题的规模n趋向无穷大时，时间复杂度T（n）的数量级（阶）称为算法的渐进时间复杂度。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

15.常见的时间复杂度按数量级递增排列依次为：

常数0

（1）、对数阶0（log2n）、线形阶0（n）、线形对数阶0（nlog2n）、平方阶0（n2）立方阶0（n3）、…、k次方阶0（nk）、指数阶0（2n）。

16.一个算法的空间复杂度S（n）定义为该算法所耗费的存储空间，它也是问题规模n的函数。

第二章线性表

1.线性表（LinearList）是由n（n≥0）个数据元素（结点）a1,a2,…,an组成的有限序列。

2.线性表的逻辑结构特征，对于非空的线性表:

①有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2；

②有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1；

③其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前趋ai-1和一个ai+1。

3.常见的线性表的基本运算:

（1）InitList（L）构造一个空的线性表L，即表的初始化。

（2）ListLength（L）求线性表L中的结点个数，即求表长。

（3）GetNode（L，i）取线性表L中的第i个结点，这里要求1≤i≤ListLength（L）

（4）LocateNode（L，x）在L中查找值为x的结点，并返回该结点在L中的位置。

若L中有多个结点的值和x相同，则返回首次找到的结点位置；

若L中没有结点的值为x，则返回一个特殊值表示查找失败。

（5）InsertList（L，x，i）在线性表L的第i个位置上插入一个值为x的新结点，使得原编号为i，i+1，…，n的结点变为编号为i+1，i+2，…，n+1的结点。

这里1≤i≤n+1，而n是原表L的长度。

插入后，表L的长度加1。

（6）DeleteList（L，i）删除线性表L的第i个结点，使得原编号为i+1，i+2，…，n的结点变成编号为i，i+1，…，n-1的结点。

这里1≤i≤n，而n是原表L的长度。

删除后表L的长度减1。

4.顺序存储方法：

把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。

顺序表（SequentialList）：

用顺序存储方法存储的线性表简称为顺序表。

顺序表是一种随机存取结构,顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。

5.顺序表中结点ai的存储地址:

LOC（ai）=LOC（a1）+（i-1）*c

1≤i≤n，

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

（1）插入：

在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置上插入新结点x。

仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。

具体算法：

voidInsertList（SeqList*L，DataTypex，inti）//将新结点

x插入L所指的顺序表的第i个结点ai的位置上

算法的时间主要花费在for循环中的结点后移语句上。

该语句的执行次数是n-i+1，在表中第i个位置插入一个结点的移动次数为n-i+1，当i=n+1：

移动结点次数为0，即算法在最好时间复杂度是O

（1），当i=1：

移动结点次数为n，即算法在最坏情况下时间复杂度是O（n）

即在顺序表上进行插入运算，平均要移动一半结点（n/2）。

（2）删除：

在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。

若i=n，则只要简单地删除终端结点，无须移动结点；

若1≤i≤n-1，则必须将表中位置i+1，i+2，…，n的结点，依次前移到位置i，i+1，…，n-1上，以填补删除操作造成的空缺。

voidDeleteList（SeqList*L,inti）//从L所指的顺序表中删除第i个结点ai

结点的移动次数由表长n和位置i决定：

i=n时，结点的移动次数为0，即为0

（1），i=1时，结点的移动次数为n-1，算法时间复杂度分别是O（n）

顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是O（n）。

7.链接方式存储的线性表简称为链表（LinkedList）。

链表的具体存储表示为：

用一组任意的存储单元来存放线性表的结点，链表中结点的逻辑次序和物理次序不一定相同（这组存储单元既可以是连续的，也可以是不连续的）。

为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链（link））。

8.链表的结点结构

：

data域--存放结点值的数据域，next域--存放结点的直接后继的地址（位置）的指针域（链域）

单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。

终端结点无后继，故终端结点的指针域为空，即NULL。

9.①生成结点变量的标准函数

　p=（ListNode*）malloc（sizeof（ListNode））；

//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中②释放结点变量空间的标准函数free（p）；

//释放p所指的结点变量空间

③结点分量的访问

方法二：

p-﹥data和p-﹥next

④指针变量p和结点变量*p的关系:

指针变量p的值——结点地址,结点变量*p的值——结点内容

10.建立单链表:

（1）头插法建表：

从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。

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

①//生成新结点

s->

data=ch;

②//将读入的数据放入新结点的数据域中

next=head;

③

head=s;

④

（2）尾插法建表：

从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。

①//生成新结点

if（head!

=NULL）

//新结点插入空表

else

r->

next=s;

③//将新结点插到*r之后

r=s;

④//尾指针指向新表尾

（3）尾插法建带头结点的单链表：

头结点及作用：

头结点是在链表的开始结点之前附加一个结点。

它具有两个优点:

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

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

头结点数据域的阴影表示该部分不存储信息。

在有的应用中可用于存放表长等附加信息。

r=head;

尾指针初值也指向头结点

while（（ch=getchar（））!

\n'

）{

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

//生成新结点

//将读入的数据放入新结点的数据域中

}

next=NULL;

//终端结点的指针域置空，或空表的头结点指针域置空

以上三个算法的时间复杂度均为O（n）。

11.单链表上的查找：

（1）链表不是随机存取结构

在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。

因此，链表不是随机存取结构。

（2）查找的思想方法

计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。

当p扫描下一个结点时，计数器j相应地加1。

当j=i时，指针p所指的结点就是要找的第i个结点。

而当p指针指为null且j≠i时，则表示找不到第i个结点。

头结点可看做是第0个结点。

p=head;

j=0;

//从头结点开始扫描

while（p->

next&

i）{//顺指针向后扫描，直到p->

next为NULL或i=j为止

p=p->

next;

j++;

if（i==j）

returnp;

//找到了第i个结点

elsereturnNULL;

//当i<

0或i>

0时，找不到第i个结点

时间复杂度：

在等概率假设下，平均时间复杂度为：

为n/2=O（n）

（2）按值查找：

ListNode*p=head->

//从开始结点比较。

表非空，p初始值指向开始结点

while（p&

p->

data!

=key）//直到p为NULL或p->

data为key为止

//扫描下一结点

//若p=NULL，则查找失败，否则p指向值为key的结点

时间复杂度为：

O（n）

12.插入运算：

插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。

具体步骤：

（1）找到ai-1存储位置p

（2）生成一个数据域为x的新结点*s

（3）令结点*p的指针域指向新结点

（4）新结点的指针域指向结点ai。

p=GetNode（head,i-1）①;

//寻找第i-1个结点

if（p==NULL）//i<

1或i>

n+1时插入位置i有错

Error（"

positionerror"

）；

②

data=x;

③s->

next=p->

next④;

⑤

算法的时间主要耗费在查找操作GetNode上，故时间复杂度亦为O（n）。

13.删除运算

删除运算是将表的第i个结点删去。

（1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）

（2）令p-＞next指向ai的直接后继结点（即把ai从链上摘下）

（3）释放结点ai的空间，将其归还给"

存储池"

。

p=GetNode（head,i-1）;

①//找到第i-1个结点

if（p==NULL||p->

next==NULL）//i<

n时，删除位置错

）;

//退出程序运行

r=p->

②//使r指向被删除的结点ai

next=r->

next③;

//将ai从链上摘下

free（r）;

④//释放结点ai的空间给存储池

算法的时间复杂度也是O（n）。

链表上实现的插入和删除运算，无须移动结点，仅需修改指针。

14.单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。

判断空链表的条件是head==head->

15.仅设尾指针的单循环链表:

用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O

（1）。

而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。

判断空链表的条件为rear==rear->

16.循环链表：

循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。

若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O

（1）。

LinkListConnect（LinkListA,LinkListB）

{//假设A，B为非空循环链表的尾指针

LinkListp=A->

//①保存A表的头结点位置

A->

next=B->

next->

//②B表的开始结点链接到A表尾

free（B->

next）;

//③释放B表的头结点

B->

next=p;

//④

returnB;

//返回新循环链表的尾指针

循环链表中没有NULL指针。

涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。

在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。

而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。

17.双向链表:

双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。

①双链表由头指针head惟一确定的。

②带头结点的双链表的某些运算变得方便。

③将头结点和尾结点链接起来，为双（向）循环链表。

18.双向链表的前插和删除本结点操作

①双链表的前插操作

voidDInsertBefore（DListNode*p,DataTypex）{//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL

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

//①

//②

prior=p->

prior;

//③

prior->

//⑤

prior=s;

//⑥

②双链表上删除结点*p自身的操作

voidDDeleteNode（DListNode*p）

{//在带头结点的双链表中，删除结点*p，设*p为非终端结点

free（p）;

与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。

上述两个算法的时间复杂度均为O

（1）。

19.存储密度（StorageDensity）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即,存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）。

20.顺序表和链表比较

顺序表和链表各有短长。

在实际应用中究竟选用哪一种存储结构呢？

这要根据具体问题的要求和性质来决定。

通常有以下几方面的考虑：

顺序表

链表

分配方式

静态分配。

程序执行之前必须明确规定存储规模。

若线性表长度n变化较大，则存储规模难于预先确定估计过大将造成空间浪费，估计太小又将使空间溢出机会增多。

动态分配只要内存空间尚有空闲，就不会产生溢出。

因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。

存储密度

为1。

当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。

存取方式

随机存取结构，对表中任一结点都可在O

（1）时间内直接取得线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜。

顺序存取结构，链表中的结点，需从头指针起顺着链扫描才能取得。

插入删除操作

在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。

在链表中的任何位置上进行插入和删除，都只需要修改指针。

对于频繁进行插入和删除的线性表，宜采用链表做存储结构。

若表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜

第三章栈

1.栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

（1）通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。

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

（3）栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。

栈的修改是按后进先出的原则进行。

每次删除（退栈）的总是当前栈中"