数据结构知识点全面总结精华版.doc

数据结构知识点全面总结精华版.doc

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

第1章绪论

内容提要：

◆数据结构研究的内容。

针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。

数据结构涵盖的内容：

◆基本概念：

数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。

数据——所有能被计算机识别、存储和处理的符号的集合。

数据元素——是数据的基本单位，具有完整确定的实际意义。

数据对象——具有相同性质的数据元素的集合，是数据的一个子集。

数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：

Data_Structure=（D,R）

数据类型——是一个值的集合和定义在该值上的一组操作的总称。

抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，

它由基本的数据类型构成。

◆算法的定义及五个特征。

算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

算法的基本特性：

输入、输出、有穷性、确定性、可行性

◆算法设计要求。

①正确性、②可读性、③健壮性、④效率与低存储量需求

◆算法分析。

时间复杂度、空间复杂度、稳定性

学习重点：

◆数据结构的“三要素”：

逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。

◆用计算语句频度来估算算法的时间复杂度。

第二章线性表

内容提要：

◆线性表的逻辑结构定义，对线性表定义的操作。

线性表的定义：

用数据元素的有限序列表示

◆线性表的存储结构：

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

顺序存储定义：

把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

链式存储结构:

其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。

通过指针来实现！

◆线性表的操作在两种存储结构中的实现。

数据结构的基本运算：

修改、插入、删除、查找、排序

1）修改——通过数组的下标便可访问某个特定元素并修改之。

核心语句:

V[i]=x;

顺序表修改操作的时间效率是O

（1）

2）插入——在线性表的第i个位置前插入一个元素

实现步骤：

①将第n至第i位的元素向后移动一个位置；

②将要插入的元素写到第i个位置；

③表长加1。

注意：

事先应判断:

插入位置i是否合法?

表是否已满?

应当符合条件：

1≤i≤n+1或i=[1,n+1]

核心语句：

for（j=n;j>=i;j--）

a[j+1]=a[j];

a[i]=x;

n++;

插入时的平均移动次数为：

n（n+1）/2÷（n+1）＝n/2≈O（n）

3）删除——删除线性表的第i个位置上的元素

实现步骤：

①将第i+1至第n位的元素向前移动一个位置；

②表长减1。

注意：

事先需要判断，删除位置i是否合法?

应当符合条件：

1≤i≤n或i=[1,n]

核心语句：

for（j=i+1;j<=n;j++）

a[j-1]=a[j];

n--;

顺序表删除一元素的时间效率为:

T（n）=（n-1）/2≈O（n）

顺序表插入、删除算法的平均空间复杂度为O

（1）

单链表：

（1）

用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。

#include

#include

typedefstructnode{

chardata;

structnode*next;

}node;

node*p,*q,*head;//一般需要3个指针变量

intn;//数据元素的个数

intm=sizeof（node）;/*结构类型定义好之后，每个node类型的长度就固定了，

m求一次即可*/

voidbuild（）//字母链表的生成。

要一个个慢慢链入

{

inti;

head=（node*）malloc（m）;//m=sizeof（node）前面已求出

p=head;

for（i=1;i<26;i++）//因尾结点要特殊处理，故i≠26

{

p->data=i+‘a’-1;//第一个结点值为字符a

p->next=（node*）malloc（m）;//为后继结点“挖坑”！

p=p->next；}//让指针变量P指向后一个结点

p->data=i+‘a’-1;//最后一个元素要单独处理

p->next=NULL;//单链表尾结点的指针域要置空！

}

}

voiddisplay（）//字母链表的输出

{

p=head;

while（p）//当指针不空时循环（仅限于无头结点的情况）

{

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

p=p->next;//让指针不断“顺藤摸瓜”

}

}

（2）单链表的修改（或读取）

思路：

要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，

然后才能：

p>data=new_value

读取第i个数据元素的核心语句是：

Linklist*find（Linklist*head,inti）

{

intj=1;

Linklist*p;

P=head->next;

While（（p!

=NULL）&&（j

{

p=p->next;

j++;

}

returnp;

}

3.单链表的插入

链表插入的核心语句：

Step1：

s->next=p->next;

Step2：

p->next=s；

6.单链表的删除

删除动作的核心语句（要借助辅助指针变量q）：

q=p->next;//首先保存b的指针，靠它才能找到c；

p->next=q->next;//将a、c两结点相连，淘汰b结点；

free（q）；//彻底释放b结点空间

7.双向链表的插入操作：

设p已指向第i元素，请在第i元素前插入元素x：

①ai-1的后继从ai（指针是p）变为x（指针是s）:

s->next=p;p->prior->next=s;

②ai的前驱从ai-1（指针是p->prior）变为x（指针是s）;

s->prior=p->prior;p->prior=s;

8.双向链表的删除操作：

设p指向第i个元素，删除第i个元素

后继方向：

ai-1的后继由ai（指针p）变为ai+1（指针p->next）;

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

前驱方向：

ai+1的前驱由ai（指针p）变为ai-1（指针p->prior）;

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

◆数组的逻辑结构定义及存储

数组：

由一组名字相同、下标不同的变量构成

N维数组的特点：

n个下标，每个元素受到n个关系约束

一个n维数组可以看成是由若干个n－1维数组组成的线性表。

存储：

事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。

在二维数组中，我们既可以规定按行存储，也可以规定按列存储。

设一般的二维数组是A[c1..d1,c2..d2]，

则行优先存储时的地址公式为：

二维数组列优先存储的通式为：

◆稀疏矩阵（含特殊矩阵）的存储及运算。

稀疏矩阵：

矩阵中非零元素的个数较少（一般小于5%）

学习重点：

◆线性表的逻辑结构，指线性表的数据元素间存在着线性关系。

在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。

◆顺序存储结构用一维数组表示，给定下标，可以存取相应元素，属于随机存取的存储结构。

◆链表操作中应注意不要使链意外“断开”。

因此，若在某结点前插入一个元素，或删除某元素，必须知道该元素的前驱结点的指针。

◆掌握通过画出结点图来进行链表（单链表、循环链表等）的生成、插入、删除、遍历等操作。

◆数组（主要是二维）在以行序/列序为主的存储中的地址计算方法。

◆稀疏矩阵的三元组表存储结构。

◆稀疏矩阵的十字链表存储方法。

补充重点：

1.每个存储结点都包含两部分：

数据域和指针域（链域）

2.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

3.在链表中设置头结点有什么好处？

头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。

4.如何表示空表？

（1）无头结点时，当头指针的值为空时表示空表；

（2）有头结点时，当头结点的指针域为空时表示空表。

5.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？

因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。

6.sizeof（x）——计算变量x的长度（字节数）；

malloc（m）—开辟m字节长度的地址空间，并返回这段空间的首地址；

free（p）——释放指针p所指变量的存储空间，即彻底删除一个变量。

7.链表的运算效率分析：

（1）查找

因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O（n）。

（2）插入和删除

因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O

（1）。

但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是O（n）。

例：

在n个结点的单链表中要删除已知结点*P，需找到它的前驱结点的地址，其时间复杂度为O（n）

8.顺序存储和链式存储的区别和优缺点？

顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。

顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。

　　链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

链式存储的优点是插入或删除元素时很方便，使用灵活。

缺点是存储密度小，存储空间利用率低。

◆顺序表适宜于做查找这样的静态操作；

◆链表宜于做插入、删除这样的动态操作。

◆若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；

◆若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

9.判断：

“数组的处理比其它复杂的结构要简单”，对吗？

答：

对的。

因为——

①数组中各元素具有统一的类型；

②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。

③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。

10.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。

11.写出右图所示稀疏矩阵的压缩存储形式。

解：

介绍3种存储形式。

法1：

用线性表表示：

（（1,2,12），（1,3,9），（3,1,-3），（3,5,14），

（4,3,24），（5,2,18），（6,1,15），（6,4,-7））

法2：

用十字链表表示

用途：

方便稀疏矩阵的加减运算

方法：

每个非0元素占用5个域

法3：

用三元组矩阵表示：

稀疏矩阵压缩存储的缺点：

将失去随机存取功能

代码：

1.用数组V来存放26个英文字母组成的线性表（a，b，c，…，z），写出在顺序结构上生成和显示该表的C语言程序。

charV[30];

voidbuild（）//字母线性表的生成，即建表操作

{

inti;

V[0]='a';

for（i=1;i<=n-1;i++）

V[i]=V[i-1]+1;

}

voiddisplay（）//字母线性表的显示，即读表操作

{

inti;

for（i=0;i<=n-1;i++）

printf（"%c",v[i]）;

printf（"\n"）;

}

voidmain（void）//主函数，字母线性表的生成和输出

{

n=26;//n是表长，是数据元素的个数，而不是V的实际下标

build（）;

display（）;

}

第三章栈和队列

内容提要：

◆从数据结构角度来讲，栈和队列也是线性表，其操作是线性表操作的子集，属操作受限的线性表。

但从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型。

◆栈的定义及操作。

栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。

插入元素到栈顶的操作，称为入栈。

从栈顶删除最后一个元素的操作，称为出栈。

对于向上生成的堆栈:

入栈口诀：

堆栈指针top“先压后加”:

S[top++]=an+1

出栈口诀：

堆栈指针top“先减后弹”:

e=S[--top]

◆栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。

顺序栈入栈函数PUSH（）

statusPush（ElemTypee）

{if（top>M）{上溢}

elses[top++]=e;

}

顺序栈出栈函数POP（）

statusPop（）

{if（top=L）{下溢}

else{e=s[--top];return（e）;}

}

◆队列的定义及操作，队列的删除在一端（队尾），而插入则在队列的另一端（队头）。

因此在两种存储结构中，都需要队头和队尾两个指针。

队列：

只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

链队列

结点类型定义：

typedefStructQNode{

QElemTypedata;//元素

StructQNode*next;//指向下一结点的指针

}Qnode,*QueuePtr;

链队列类型定义：

typedefstruct{

QueuePtrfront;//队首指针

QueuePtrrear;//队尾指针

}LinkQueue;

链队示意图：

①空链队的特征：

front=rear

②链队会满吗？

一般不会，因为删除时有free动作。

除非内存不足！

③入队（尾部插入）：

rear->next=S;rear=S;

出队（头部删除）：

front->next=p->next;

2.顺序队

顺序队类型定义：

#defineQUEUE-MAXSIZE100//最大队列长度

typedefstruct{

QElemType*base;//队列的基址

intfront;//队首指针

intrear;//队尾指针

}SqQueue

建队核心语句：

q.base=（QElemType*）malloc（sizeof（QElemType）

*QUEUE_MAXSIZE;//分配空间

顺序队示意图：

循环队列：

队空条件:

front=rear（初始化时：

front=rear）

队满条件：

front=（rear+1）%N（N=maxsize）

队列长度（即数据元素个数）：

L=（N＋rear－front）%N

1）初始化一个空队列

StatusInitQueue（SqQueue&q）//初始化空循环队列q

{

q.base=（QElemType*）malloc（sizeof（QElemType）

*QUEUE_MAXSIZE）;//分配空间

if（!

q.base）exit（OVERFLOW）;//内存分配失败，退出程序

q.front=q.rear=0;//置空队列

returnOK;

}//InitQueue;

2）入队操作

StatusEnQueue（SqQueue&q,QElemTypee）

{//向循环队列q的队尾加入一个元素e

if（（q.rear+1）%QUEUE_MAXSIZE==q.front）

returnERROR;//队满则上溢，无法再入队

q.rear=（q.rear+1）%QUEUE_MAXSIZE;

q.base[q.rear]=e;//新元素e入队

returnOK;

}//EnQueue;

3）出队操作

StatusDeQueue（SqQueue&q,QElemType&e）

{//若队列不空，删除循环队列q的队头元素，

//由e返回其值，并返回OK

if（q.front==q.rear）returnERROR;//队列空

q.front=（q.front+1）%QUEUE_MAXSIZE;

e=q.base[q.front];

returnOK;

}//DeQueue

◆链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法。

补充重点：

1.为什么要设计堆栈？

它有什么独特用途？

①调用函数或子程序非它莫属；

②递归运算的有力工具；

③用于保护现场和恢复现场；

④简化了程序设计的问题。

2.为什么要设计队列？

它有什么独特用途？

①离散事件的模拟（模拟事件发生的先后顺序,例如CPU芯片中的指令译码队列）；

②操作系统中的作业调度（一个CPU执行多个作业）；

③简化程序设计。

3.什么叫“假溢出”？

如何解决？

答：

在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。

解决假溢出的途径———采用循环队列。

4.在一个循环队列中，若约定队首指针指向队首元素的前一个位置。

那么，从循环队列中删除一个元素时，其操作是先移动队首位置，后取出元素。

5.线性表、栈、队的异同点：

相同点：

逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。

不同点：

①运算规则不同：

线性表为随机存取；

而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；

队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

②用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。

第四章串

内容提要 ：

◆串是数据元素为字符的线性表，串的定义及操作。

串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。

串比较：

intstrcmp（char*s1,char*s2）;

求串长：

intstrlen（char*s）;

串连接：

charstrcat（char*to,char*from）

子串T定位：

charstrchr（char*s,char*c）;

◆串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小”的问题。

模式匹配算法 。

串有三种机内表示方法：

模式匹配算法 ：

算法目的：

确定主串中所含子串第一次出现的位置（定位）

定位问题称为串的模式匹配，典型函数为Index（S,T,pos）

BF算法的实现—即编写Index（S,T,pos）函数

BF算法设计思想：

将主串S的第pos个字符和模式T的第1个字符比较，

若相等，继续逐个比较后续字符；

若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。

直到主串S的一个连续子串字符序列与模式T相等。

返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。

否则，匹配失败，返回值0。

IntIndex_BP（SStringS,SStringT,intpos）

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

若不存在，则函数值为0.

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

i=pos;j=1;

while（i<=S[0]&&j<=T[0]）//如果i,j二指针在正常长度范围，

{

if（S[i]==T[j]）{++i,++j;}//则继续比较后续字符

else{i=i-j+2;j=1;}//若不相等，指针后退重新开始匹配

}

if（j>T[0]）returni-T[0];//T子串指针j正常到尾，说明匹配成功，elsereturn0;//否则属于i>S[0]情况，i先到尾就不正常

}//I