数据结构知识点部分整理.docx

数据结构知识点部分整理.docx

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

数据结构知识点部分整理

1.数据结构的产生

（1）计算机的发展：

速度→快

计算机存储容量→大应用范围不断拓宽

价格→降

早期计算机→主要用于科学计算→处理对象：

纯数值性的信息。

（2）计算机的应用：

情报检索

60年代后企业管理乃至人类社会活动的一切领

系统工程

（3）计算机的处理对象：

数值性和非数值性（包括字符、图像、声音）

算法（还是要掌握好的一部分）

1.概念：

是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

2.算法的特性

（1）有穷性：

指有穷的步数，以及有穷的时间

（2）确定性：

每条指令必须有确切的含义，且算法只有唯一的一条执行路径，相同的输入只能是相同的输出

（3）可行性：

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

（4）输入：

一个算法有零个或多个的输入。

（5）输出：

有一个或者多个的输出，输出的是同输入有着某些特定关系的量。

3.算法的描述方法：

自然语言、程序流程图、伪代码（又有自然语言又有程序语言）、程序设计语言。

4.算法的设计目标

（1）正确性：

明确的无歧义的描述

（2）可读性：

便于阅读理解

（3）健壮性：

输入数据非法时，算法也能做出处理，而不产生不可预料的结果

（4）高时间效率：

算法时间尽量短

（5）低储存量需求：

指算法执行过程中所需要的最大存储空间要低。

5.算法效率的度量

（1）时间复杂度：

算法的执行时间是指根据该算法编制的程序在计算机上运行时所消耗的时间总量。

基本语句：

执行次数与整个算法的执行次数成正比的语句，多数情况下它是最深层循环内的语句。

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

Eg：

语句的执行次数（就是循环的次数）为n2+1，则算法的时间复杂度为

T（n）=）O（n2）

（2）空间复杂度：

算法的空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，它也是衡量算法有效性的一个指标。

算法的空间复杂度是对算法的执行过程需要的辅助空间进行度量。

通常记作

S（n）=O（f（n））

其中n为问题的规模（或大小），表示随着问题规模n的增大，算法运行所需存储量的增长率与f（n）的增长率相同。

线性表（重点掌握）

1.线性表的定义：

线性表（linearlist）是n（n≥0）个相同类型的数据元素构成的有限序列。

其中称n为线性表的长度，当n=0时，表示线性表是一个空表，即表中不包含任何元素。

一个有n个数据元素的线性表常表示为：

（a1，a2，…，an）

则常把线性表中使用的元素类型用一种通用数据类型标识符ElemType进行抽象，实际使用时可以通过typedef语句把它定义为任何一种具体类型。

若线性表中的元素为整数，则可通过下列语句把它定义为整数类型：

typedefintElemType

2.线性表的定义：

（1）序列的顺序性，限制顺序，第一个元素无前期，最后一个无后继，其他元素有且仅有一个前驱和后继

（2）有限性：

元素个数的有限，计算机处理的对象是有限的

（3）相同性：

元素取自同一个数据对象，每个元素占相同数量的存储单元。

（4）抽象性：

元素的类型是抽象的、不具体的，看具体问题。

（5）线性表的逻辑结构：

元素之前的前驱后继关系

A1称为ai+1的前驱，后者是前者的后继

3.抽象数据类型（掌握）

InitList（&L，maxsize，incresize）构造一个容量为maxsize的空线性表L

ClearList（&L）线性表L存在的前提下将线性表重置为空表

ListEmpty（L）在线性表存在的前提下，若L为空表，则返回true，否则返回false

ListLength（L）在线性表L存在的前提下，返回L中元素的个数，即线性表的长度

LocateElem（L，e）在表中找到与e相等的第一个值的位序

PriorElem（L，cure，&pre-e）cur-e是L的元素，但不是第一个，就用pre-e返回它的前驱，若操作失败，则pre-e无定义。

NextElem（L，cur-e，&next_e）cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义

ListInsert（&L，i，e）线性表L已存在且1≤i

ListDelete（&L，i，e）线性表L已存在且非空，1≤i≤LengthList（L），操作结果是删除L的第i个元素，并用e返回其值，L的长度减1。

GetElem（L，i，&e）线性表L已存在，且1≤i≤LengthList（L），操作结果是用e返回L中第i个元素的值。

ListTraverse（L）线性表L已存在，操作结果是依次输出L中的每个数据元素。

DestroyList（&L）线性表L已存在，操作结果是撤销线性表L。

4.顺序表（重点掌握）

（1）顺序表的定义：

用一组地址连续的存储单元一次存储线性表里各个元素的存储结构称为线性表的顺序存储结构。

（常用程序设计语言中的一维数组来描述顺序表中数据元素的存储区域，也就是把线性表中相邻的元素存储在数组中相邻的位置）

特点:

逻辑上相邻的数据元素，其物理位置上也是相邻的。

（2）顺序表中程序的存储首址

假设每个数据元素占用k个存储单元，loc（ai）表示数据元素ai的存储首址，则线性表中相邻的两个元素ai与ai+1的存储首址1oc（ai）与loc（ai+1）满足下面的关系：

loc（ai+1）=1oc（ai）+k（1≤i≤n）

线性表中第i个元素ai的存储首址为：

1oc（ai）=1oc（a1）+（i-1）*k（1≤i≤n）

由于表中每个元素的存储首址都可由上面的公式计算求得，且计算所需的时间也是相同的，所以访问表中任意元素的时间都相等，具有这一特点的存储结构称为随机存取结构。

（3）

拓展：

ElemType（也有的书上称之为elemtp）是数据结构的书上为了说明问题而用的一个词。

它是elementtype（“元素的类型”）的简化体，ElemType的默认是int型。

Incrementsize貌似是增加线性表空间大小的意思

L．elem表示访问L结构体中的成员elem，L_elem表示的是一个变量或者结构体的名字

静态存储分配的顺序表：

#defineLIST_INIT_SIZE100

typedefstruct{

ElemTypeelem[LIST_INIT_SIZE];

intlength;

}SSqList;

动态存储分配的顺序表：

#defineLISTINCREMENT10

typedefstruct{

ElemType*elem;

intlength;

intlistsize;

intincrementsize;

}SqList;

辨析

A线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的；数组的长度是存放线性表的存储空间的长度，一旦存储空间分配后，这个量确定不变。

存储结构是数据及其逻辑结构在计算机中的表示

存取结构是在某种数据结构上对访问操作时间性能的描述

B顺序表是一种随机存取的存储结构”的含义为：

在顺序表这种存储结构上进行访问操作，其时间性能为O

（1）。

顺序存储：

顺序表（重点掌握）sqlist随机存储结构

（1）初始化

voidInitList_Sq（SqList&L,intxsize=LIST_INIT_SIZE,intincresize=LISTINCREMENT）

{

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

//（这里是某种数据结构，就假设这是一个线性表，它储存的元素的数据类型为ElemType（就像整型，浮点型，或者是自定义型等等），表长为LIST-INIT-SIZE，L是一个线性表，L的elem成员是这个线性表的首元素的地址，这个表达式的意思就是分配一个长度为LIST-INIT-SIZE个ElemType长度的空间并强制转换为ElemType类型的指针，将该指针的地址赋给L.elem。

这样L就是一个已经分配过空间的线性表了，它已经有了一个空的存储空间，可以放LIST-INIT-SIZE个ElemType类型的数据）

if（!

L.elem）exit

（1）;

L.length=0;

L.listsize=maxsize;

L.incrementsize=incresize;}//InitList_Sq

（2）求表长（O

（1））

intListLength_Sq（SqListL）

{

returnL.length;

}//ListLength_Sq

（3）查找（O（n））

intLocateElem_Sq（SqListL,ElemTypee）

{

for（inti=0;i

if（L.elem[i]==e）returni;

return-1;（因为C/C++中数组的下标是从0开始，所以当查找失败时不能返回0，而应该返回一个有效下标之外的整数）

}//LocateElem_Sq

（4）前插（时间复杂度为O（n））

boolListInsert_Sq（SqList&L,inti,ElemTypee）

{intj;

if（i<0||i>L.length）returnfalse;

if（L.length>=L.listsize）

{

L.elem=（ElemType*）realloc（L.elem,（L.listsize+L.incrementsize）*sizeof（ElemType））;

if（!

L.elem）exit

（1）;

L.listsize+=L.incrementsize;

}

for（j=L.length;j>i;j--）

L.elem[j]=L.elem[j-1];

L.elem[i]=e;

L.length++;

returntrue;

}//ListInsert_Sq

（拓展：

A：

realloc动态内存调整先判断当前的指针是否有足够的连续空间，如果有，扩大，并且将mem_address返回，如果空间不够，先按照newsize指定的大小分配空间。

B：

malloc动态内存分布向系统申请分配指定size个字节的内存空间。

返回类型是void*类型。

void*表示未确定类型的指针。

C,C++规定，void*类型可以通过类型转换强制转换为任何其它类型的指针

C：

sizeofC语言中判断数据类型或者表达式长度符

D：

incrementsize增量大小，增补一段空间）

E：

calloc动态内存分配并清零：

功能：

在内存的动态存储区中分配n个长度为size的连续空间，函数返回一个指向分配起始地址的指针；如果分配不成功，返回NULL

F:

_alloca，内存分配函数，与malloc,calloc,realloc类似·，但是注意一个重要的区别，_alloca是在栈（stack）上申请空间，用完马上就释放。

（5）删除（时间复杂度为O（n））

boolListDelete_Sq（SqList&L,inti,ElemType&e）

{

intj;if（i<0||i>=L.length）returnfalse;

if（L.length<=0）returnfalse;（首先判断删除的位置是否合理）

e=L.elem[i];

for（j=i+1;j<=L.length-1;j++）

L.elem[j-1]=L.elem[j];（元素依次向前移，同时线性表长度减1）

L.length--;

returntrue;

}//ListDelete_Sq

（6）取数据元素

boolGetElem_Sq（SqListL,inti,ElemType&e）

{

if（i<0||i>L.length）returnfalse;

if（L.length<=0）returnfalse;

e=L.elem[i];

returntrue;

}//GetElem_Sq

（7）顺序表的遍历（O（n），n为顺序表的长度，遍历就是打印出这个表里的所有数据元素）

Traverse横穿

（拓展：

cout<

A：

cout<

则输出：

****a4个*和字符a共占5个位置）

B：

charx[]="12345678";

chary[]="123456789abcd";

cout<

白白12345678

cout<

12345678

cout<

123456789abcd

（8）撤销顺序表

voidDestroyList_Sq（SqList&L）

{

free（L.elem）;

L.elem=NULL;

L.listsize=0;

L.length=0;

}//DestroyList_Sq

在顺序表上的各种操作中，插入和删除是时间复杂度最高的操作，时间主要消费在移动数据元素中，所需移动数据元素的个数和两个因素有关：

其一是顺序表的长度；其二是被插或被删元素在顺序表中的位置

以插入为例，假设Pi为在第i（i从0开始）个数据元素之前插入一个数据元素的概率，则在长度为n的顺序表中插入一个数据元素时所需移动数据元素的平均次数

假设在顺序表的任何位置上插入数据元素都是等概率的

即

同理，可推出在顺序表中删除一个数据元素的平均移动次数为

链式存储：

链表Linklist

（1）定义

用一组任意的存储单元存储在线性表里的各元素，这些存储单元可以连续也可以不连续，为了反映元素在线性表中的前后位置关系，除了元素本身的信息外还需要添加一个或者多个指针域，来表示另一个数据元素在内存中的存储首址，这叫做线性表的链式存储结构，且其特点是逻辑上相邻的元素其物理位置不一定相邻。

链表的结点结构

存储数据元素的数据域和存储另一数据元素的地址的指针域组成了数据元素的存储映像，称为结点

链表的分类

A：

根据指针个数，单链表（结点中一个指针域）；多重链表（结点中多个指针域）

B：

根据结点中指针的链接方式：

普通链接和循环链接

（2）单链表

A：

定义

最简单的一种链式存储结构，一个结点只含一个指针域，指针域用来存放其后继结点的地址。

B：

结点结构描述（node结点）

typedefstructNode{

ElemTypedata;

structNode*next;

}LNode,*LinkList;（typedef为C语言的关键字，作用是为一种数据类型定义一个新名字。

这里的数据类型包括内部数据类型（int,char等）和自定义的数据类型（struct等）。

在编程中使用typedef目的一般有两个，一个是给变量一个易记且意义明确的新名字，另一个是简化一些比较复杂的类型声明。

）

C：

单链表的逻辑表示：

头结点：

单链表中第一个结点。

表头指针：

存放单链表中第一个结点的地址。

表尾结点：

单链表中最后一个结点，表尾结点的指针域指针为空。

开始结点：

存放线性表的第一个元素的结点。

注意：

头结点在链表中并不是必须的，仅仅是为了操作上的方便。

单链表（linklist非随机存储结构，重点掌握）

（1）初始化

voidInitList_L（LinkList&L）

{

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

if（!

L）exit

（1）;

L->next=NULL;

}//InitList_L

（2）求表长

intListLength_L（LinkListL）

{

LinkListp;intk=0;p=L->next;

while（p）

{

k++;p=p->next;

}

returnk;

}//ListLength_L

->运算符叫做“指向结构体成员运算符”，是C语言和C++语言的一个运算符，用处是使用一个指向结构体或对象的指针访问其内成员。

（3）查找

LNode*LocateElem_L（LinkListL,ElemTypee）{

LinkListp;

p=L->next;

while（p&&p->data!

=e）（意思就是p!

=NULL的意思，先判断p不为NULL，否则直接p->data，当p为NULL的时候会出异常。

）

p=p->next;

returnp;

}//LocateElem_L

（4）插入

两个语句顺序不可以改变，否则不可以进行插入操作

boolListInsert_L（LinkListL,inti,ElemTypee）

{

LinkListp,s;

intj;

p=L;j=0;

while（p->next&&jnext;j++;}

if（j!

=i-1）returnfalse;

if（（s=（LNode*）malloc（sizeof（LNode）））==NULL）

exit

（1）;

s->data=e;

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

returntrue;

}//ListInsert_L

（&&两边都要是true才会true，逻辑运算符；&与运算，eg：

1&0=0,1&1=1,0&0=0,0&1=0；||逻辑或运算，一个满足则true）

（5）删除

boolListDelete_L（LinkListL,inti,ElemType&e）

{

LinkListp,q;

intj;

p=L;j=0;

while（p->next&&p->next->next&&jnext;j++;}

if（j!

=i-1）returnfalse;

q=p->next;

p->next=q->next;

e=q->data;free（q）;

returntrue;

}//ListDelete_L（while中的条件表达式中的“p->next->next”是为了保证第i个结点存在）

（6）取元素

boolGetElem_L（LinkListL,inti,ElemType&e）

{

LinkListp;

intj;

p=L;j=0;

while（p->next&&jnext;j++;}

if（j!

=i）returnfalse;

e=p->data;

returntrue;

}//GetElem_L

取元素操作与删除元素操作基本类同，主要差别是取数据元素时指针定位在第i个结点，并且不删除ai结点

（7）创建单链表

尾插法

voidCreateList_L_Rear（LinkList&L,ElemTypea[],intn）

{

LinkListp,q;inti;

L=（LinkList）malloc（sizeof（LNode））;

q=L;

for（i=0;i

{

p=（LinkList）malloc（sizeof（LNode））;

p->data=a[i];

q->next=p;

q=p;

}

q->next=NULL;

}//CreateList_L_Rear

头插法

voidCreateList_L_Front（LinkList&L,ElemTypea[],intn）

{

LinkListp;inti;

L=（LinkList）malloc（sizeof（LNode））;

L->next=NULL;

for（i=n-1;i>=0;i--）

{

p=（LinkList）malloc（sizeof（LNode））;

p->data=a[i];

p->next=L->next;

L->next=p;

}

}//CreateList_L_Front

（8）单链表的遍历

voidListTraverse_L（LinkListL）

{

LinkListp=L->next;

while（p）

{cout<data;

p=p->next;

}

cout<

}//ListTraverse_L

（9）撤销单链表

voidDestroyList_L（LinkList&L）

{

LinkListp,p1;

p=L;

while（p）

{p1=p;

p=p->next;

free（p1）;

}

L=NULL;

}//DestroyList_L