数据结构知识点.doc

数据结构知识点.doc

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

复习要点：

第一章

1.相关基本概念：

数据、数据元素（基本单位）、数据项（最小单位）、算法及其特征等；

◎数据：

所有能输入到计算机中并被计算机程序处理的符号总称。

◎数据元素：

基本单位。

◎数据项：

最小单位。

◎算法特征（5点）：

有穷性；确定性；可行性；输入；输出。

2.逻辑结构、存储结构（物理结构）及其类型；

◎逻辑结构有四种基本类型：

集合、线性结构、树形结构和网状结构。

◎数据元素之间的关系有两种不同的表示方法：

顺序映象和非顺序映象，并由此得到两种不同的存储结构：

顺序存储结构和链式存储结构。

◎注：

期中考题目

数据结构分为两大类，即为逻辑结构和存储结构。

其中逻辑结构又分为线性结构和非线性结构，存储结构一共有四种（顺序、链接、索引、散列）。

3.算法分析：

语句频度（执行次数）计算、时间和空间复杂度分析。

表示方法

◎语句频度：

直接写次数。

◎时间复杂度：

O（执行次数）,如：

O（n）。

◎空间复杂度：

O（所需空间）

第二章

1.顺序表（数组）插入、删除、有序表合并算法及其移动次数计算；

12

13

21

24

28

30

42

77

数据元素

序号12345678

表示L.elem[0][1][2][3][4][5][6][7]

◎顺序表插入

算法思想：

如果要在序号5前插入元素e，需要将序号5～8向后移动一个位置。

▲移动次数为4次，公式n-i+1

◎顺序表删除

算法思想：

如果要删除序号5元素，需要将6～8依次向前移动一位

▲移动次数为3次，公式n-i

◎有序表合并

LA=（3,5,8,11）

LB=（2,6,8,9,11,15,20）

则LC=（2,3,5,6,8,8,9,11,11,15,20）

算法思想（以非递减为例）：

La和Lb非递减排列，La与Lb中元素逐个比较，较小的先插入Lc中。

▲注：

非递减是指递增排序，但元素有可能相等，与之相对的有非递增排序。

▲移动次数为（La.length+Lb.length）

2.链表（有无头节点、单双、循环）插入（前、后）、删除（前、本身、后）的指针挂接、建立（不带头节点）算法。

◎单链表

▲每个节点有数据域和指针域datanext

头a1a2a3a4a5a6

带头节点L→→→→→→→

P↑

a1a2a3a4a5a6

不带头节点L→→→→→→

P↑

单循环链表

●在P（a3）节点前插入S节点

（1）Q=P;//先让Q指向a3

（2）P=L;//P指向第一个节点（带头结点指向头结点，不带头结点指向a1）

（3）while（P->next!

=Q）P=P->next;//找到a3的前驱a2，P指向a2

（4）S->next=P->next;//P->next为a3，让S->next等于a3

（5）P->next=S;//a2指针域指向节点S

●在P（a3）节点后插入S节点

（1）S-next=P->next;

（2）P->next=S;

●删除P（a3）前一个节点

（1）Q=P;

（2）P=L;

（3）while（P->next->next!

=Q）P=P->next;//找到a1

（4）P->next=P->next->next;//让a1指针域指向a3，从而删除a2

●删除P（a3）节点

（1）Q=P;

（2）P=L;

（3）while（P->next!

=Q）P=P->next;//找到a2

（4）P->next=P->next->next;//让a2指针域指向a4，从而删除a3

●删除P（a3）后一个节点

（1）P->next=P->next->next;//让a3指针域指向a5，从而删除a4

◎双链表

▲每个节点有前驱指针、数据域、后继指针priordatanext

双循环链表

头a1a2a3a4

●在P（a2）节点前插入S节点

▲技巧：

先让S->prior和S->next与链表建立关系

注：

步骤（4）必须在步骤（3）后面

（1）S->next=P;//先让S->next指向a2

（2）S->prior=P->prior;//S->prior指向a1

（3）P->prior->next=S;//再把a1->next指向S

（4）P->prior=S;//a2->prior指向S

●在P（a2）节点后插入S节点

注：

步骤（4）必须在步骤（3）后面

（1）S->prior=P;

（2）S->next=P->next;

（3）P->next->prior=S;//a3->prior指向S

（4）P->next=S;

●删除P（a2）前一个节点a1

（1）Q=P->prior;//Q指向要被删除的a1;

（2）P->prior=P->prior->prior;//P->priro指向头

（3）P->prior->next=P;//头->next指向P

（4）free（Q）;//释放a1的存储空间

●删除P（a2）节点

（1）P->next->prior=p->prior;

（2）P->prior->next=p->next;

（3）free（P）;

●删除P（a2）后一个节点a3

（1）Q=P->next;

（2）P->next=P->next->next;//a2->next指向a4

（3）P->next->prior=P;//a4->prior=P

（4）free（Q）;//释放a3存储空间

◎建立（不带头节点）单链表

读程序：

设n为2（i取0，1）

i=0时，

p↑L↑q↑

i=1时，→

L↑q↑p↑L↑q↑p↑

→

L↑q↑p↑

第三章

1.栈的进出序列、栈、队列、循环队列的满/空条件;

▲由于栈的插入、删除操作是限制在栈顶进行的，因而后进栈的元素必然是先出栈，0.所以栈是“后进先出”表。

▲由于队列的输入、输出操作分别在队的两端进行，因此先入队的元素必然先输出，故队列又称为“先进先出”表

◎栈的进出序列

例题：

进栈序列为123，可能得到的出栈序列是什么？

答：

共五种123/132/213/231/321

进出栈情况（以132序列为例）：

1进栈→1出栈，输出1→2进栈→3进栈→3出栈→2出栈输出32

◎栈、队列、循环队列的满/空条件

栈空条件：

s.top=s.base;栈满条件：

s.top-s.base=stacksize;

队空条件：

Q.front=Q.rear;队满条件：

q->rear-q->front=MAXSIZE

循环队列空条件：

Q.front=Q.rear

循环队列满条件：

为避免在队满是队头指针和队尾指针也是重合的情况，规定队列中

还有一个空的存储单元时为队满，即为Q.front=（Q.rear+1）MODmaxsize（MOD为取余

运算符）。

因而，这种循环队列不适合用动态数组作为存储结构。

2.栈、队列的存储结构、基本操作算法（双向栈）;

◎栈存储结构

●顺序栈

typedefstruct{

SElemType*base;

SElemType*top;

intstacksize;

}SqStack;

●链式栈

◎队列存储结构

●顺序存储结构

●链式存储结构

◎双向栈

存储结构：

typedef struct{

    Elemtype *base[2];

    Elemtype *top[2];

}BDStacktype; //双向栈类型

初始化：

StatusInit_Stack（BDStacktype&tws,intm）//初始化一个大小为m的双向栈tws

{

    tws.base[0]=（Elemtype*）malloc（sizeof（Elemtype）*m）;

    tws.base[1]=tws.base[0]+m;

    tws.top[0]=tws.base[0];

    tws.top[1]=tws.base[1];

    returnOK;

}//Init_Stack

入栈：

Statuspush（BDStacktype&tws,inti,Elemtypex）

//x入栈,i=0表示低端栈,i=1表示高端栈

{

if（tws.top[0]>tws.top[1]）returnOVERFLOW;

//注意此时的栈满条件

if（i==0）*tws.top[0]++=x;

elseif（i==1）*tws.top[1]--=x;

elsereturnERROR;

returnOK;

}//push

出栈：

Statuspop（BDStacktype&tws,inti,Elemtype&x）

//x出栈,i=0表示低端栈,i=1表示高端栈

{

if（i==0）

{

if（tws.top[0]==tws.base[0]）returnOVERFLOW;

x=*--tws.top[0];

}

elseif（i==1）

{

if（tws.top[1]==tws.base[1]）returnOVERFLOW;

x=*++tws.top[1];

}

elsereturnERROR;

returnOK;

}//pop

第四章

1.字符串模式匹配的简单算法；

intIndex（SStringS,SStringT,intpos）

{//算法4.5

//返回子串T在主串S中第pos个字符之后的位置。

//若不存在，则函数值为0。

//其中，T非空，1≤pos≤StrLength（S）。

inti=pos;

intj=1;

while（i<=S[0]&&j<=T[0]）{

if（S[i]==T[j]）{//继续比较后继字符

++i;

++j;

}

else{//指针后退重新开始匹配

i=i-j+2;//此时i为上次开始比较位置的下一位

j=1;

}

}

if（j>T[0]）returni-T[0];

elsereturn0;

}//Index

2.计算NEXT。

j：

1234567

串：

abcabaa

next[j]：

0111232

▲技巧：

第一二个肯定是0，1！

如果要计算next[4]，找的字符串必须是以第3个字符c为结尾，第1个字符a为开头的。

以第6个为例，a前一个字母是b，以第5个字符b为结尾的ab刚好和以第1个字符为

开头的ab匹配，所以next[6]=2+1=3。

第五章

1.二维数组的地址（下标）换算；

习题5.1假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，计算：

（1）数组A的体积（即存储量）

6*8*6=288字节

（3）按行存储是，元素a14的第一个字节的地址

1000+（8*1+4）*6=1072

基址+（每行的元素个数*行数+当前列序）*每个元素所占存储单元

（4）按列存储时，元素a47的第一个字节的地址

1000+（6*7+4）*6=6276

基址+（每列的元素个数*列数+当前行序）*每个元素所占存储单元

习题5.2假设按低下标优先存储整数组A9*3*5*8时，第一个元素的字节地址是100，每个整数占四个字节。

问下列元素的存储地址是什么？

（2）a1111地址：

100+（3*5*8*1+5*8*1+8*1+1）*4=776

（3）a3125地址：

100+（3*5*8*3+5*8*1+8*2+5）*4=1784

（4）a8247地址：

100+（3*5*8*8+5*8*2+8*4+7）*4=4416

2.特殊矩阵（三角、其他有规律）压缩为一维的下标计算；

◎下三角矩阵压缩为一维数组（记忆公式）

▲技巧：

推荐把公式

（2）背下来（i,j,R范围都是从0开始），其他根据范围变化公式

（1）若1<=i,j<=n,0<=k<=n（n+1）/2-1

当i>=j时，k=i（i-1）/2+j-1;

当i

（2）若0<=i,j<=n-1,0<=k<=n（n+1）/2-1

//注意i,j是0到n-1，下面的公式相当于把

（1）中i变成i+1,j变成j+1

当i>=j时，k=（i+1）i/2+j;

当j

（3）若1<=i,j<=n,1<=k<=n（n+1）/2

//注意R是1到n（n+1）/2，下面公式相当于把

（1）中k变成k-1

当i>=j时，k=i（i-1）/2+j;

当i

（4）若0<=i,j<=n-1,1<=k <=n（n+1）/2

当i>=j时，k=（i+1）i/2+j+1;

当i

3.稀疏矩阵的三元组表示。

4.稀疏矩阵应用的算法。

（略）

第六章

1.二叉树的性质；

性质1：

。

性质2：

深度为k的二叉树至多有个结点（k³1）。

性质3：

对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

性质4：

。

性质5：

如果对一棵有n个结点的完全二叉树的结点按层序编号，

则对任一结点i（1£i£n），有：

（1）如果i=1，则结点i是二叉树的根，无双亲；

如果i>1，则其双亲是ëi/2û。

（2）如果2i>n，则结点i无左孩子；

如果2i£n，则其左孩子是2i。

（3）如果2i+1>n，则结点i无右孩子；

如果2i+1£n，则其右孩子是2i+1。

2.二叉树的先序、中序、后序、层次遍历过程；算法（如：

求二叉树的高度或结点个数）树的先序、后序、层次遍历过程；

二叉树遍历过程：

先（根）序遍历：

根→左子树→右子树

中（根）序遍历：

左子树→根→右子树

后（根）序遍历：

左子树→右子树→根

层次遍历：

从上到下，从左往右，逐个遍历

树的遍历过程：

先根（次序）遍历：

先访问根结点，然后依次先根遍历根的每棵子树（根→子树）

后跟（次序）遍历：

先依次后根遍历每棵子树，然后访问根结点（子树→根）

层次遍历：

从上到下，从左往右，逐个遍历

▲注：

树与二叉树相互转化后

树的先根遍历相当于二叉树的先序遍历

树的后根遍历相当于二叉树的中序遍历

3.给出两个遍历序列，画出树（二叉树、树）

习题6.23画出和下列已知序列对应的树T：

（1）树的先根次序访问序列为GFKDAIEBCHJ;

（2）树的后根次序访问序列为DIAEKFCJHBG。

注：

树的后根遍历相当于二叉树的中序遍历

G

①由

（1）知G为根；

⑵G为根，联系

（2）知G无右子树；

③观察

（1），F为G左子树；

F

④根据③，观察

（2）知DIAEK在F左边，

CJHB在F右边；

B

K

⑤观察

（1），K为F左子树；

⑥根据⑤，观察

（2）知K无右子树；

⑦观察

（1），D为K左子树；

C

D

⑧根据⑦，观察

（2）知D无左子树；

⑨观察

（1），A为D右子树；

⑩观察

（2），IE分别为A左右子树；

A

H

F的右子树自行观察判断。

J

E

I

4.二叉树与树相互转换；

◎树转化成二叉树：

规则：

树的最左孩子变成二叉树左子树，该左孩子的兄弟变成二叉树左子树的右子树

注：

原树中B为A最左孩子，C,D为B兄弟，变成二叉树后C成为B右子树，D成为C右子树。

◎二叉树转化成树

5.求哈夫曼树和给出编码、带权路径长度计算。

习题6.26假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.21,0.10。

试为这8个字母设计哈夫曼编码，并求带权路径长度

设这8个结点为A、B、C、D、E、F、G、H，其相应的权为7、19、2、6、32、3、21、10。

①当前未用权：

7、19、2、6、32、3、21、10，选出2、3构造出5。

⑵当前未用权：

7、19、6、32、21、10、5，选出5、6构造出11。

③当前未用权：

7、19、32、21、10、11，选出7、10构造出17。

④当前未用权：

19、32、21、11、17，选出11、17构造出28。

⑤当前未用权：

19、32、21、28，选出19、21构造出40。

⑥当前未用权：

32、28、40，选出32、28构造出60。

⑦剩下权：

40、60，构造出100

▲编码：

树的左分支为0，右分支为1。

得到哈夫曼编码为A:

1101B:

01C:

11111D:

1110E:

10F:

11110G:

00H:

1100

带权路径长度：

（7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4）/100=2.61

▲注：

该公式为：

A路径长*A权+B路径长*B权+…+H路径长*H权，因为设的权值是原来的100倍，所以结果除以100。

第七章

1.邻接矩阵、邻接表存储结构及其特征；

注：

以有向图G1为例（有路径用1，否则0）

v1v2v3v4

v10110

v20000

v30001

v41000

注：

以有向图G1为例

标号0123

00110

1