数据结构总复习资料（完整版）

2018数据结构总复习

第一章 概论

1.1数据结构的定义和分类

1.数据结构的定义

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

2.数据结构包括的内容

（1）逻辑结构：数据元素之间的逻辑关系。

（2）存储结构：数据元素及其关系在计算机存储器内的表示。 （3）操作：数据的运算（检索、排序、插入、删除、修改）。

1.2为什么学习数据结构

1.学习数据结构的作用

（1）计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 （2）同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。

（3）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。

2.电话号码查询问题

（1）要写出好的查找算法，取决于这张表的结构及存储方式。 （2）电话号码表的结构和存储方式决定了查找（算法）的效率。

1.3算法的概念和特点

1.算法的概念和特点

算法是由若干条指令组成的有穷序列，具有以下特点： （1）输入：具有0个或多个输入的外界量。 （2）输出：至少产生1个输出。

（3）有穷性：每一条指令的执行次数必须是有限的。 （4）确定性：每条指令的含义都必须明确，无二义性。 （5）可行性：每条指令的执行时间都是有限的。

2.算法与程序的区别

（1）一个程序不一定满足有穷性，但算法一定。

（2）程序中的指令必须是机器可执行的，而算法无此限制。

（3）一个算法若用机器可执行的语言来描述，则它就是一个程序。

1 / 62

1.4算法分析

1.时间复杂度

算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐近时间复杂度，简称时间复杂度。算法效率的度量，采用时间复杂度。

常见函数的时间复杂度按数量递增排列及增长率： 常数阶O(1)

对数阶O(log2n) 线性阶O(n)

线性对数阶O(n log2n)

2

平方阶O(n)

3

立方阶O(n) ……

k

k次方阶O(n)

n

指数阶O(2)

2.空间复杂度

空间复杂度是指算法在计算机内执行时所需存储空间的度量，记作：S(n) = O(f(n))。

3.算法分析的目的

目的在于选择合适算法和改进算法

1.5 例题

例1：

for ( i=1; i

y = y+1; //语句1

for ( j=0; j<=(2*n); j++ )

x++; //语句2

}

解：语句1频度为(n-1)；语句2频度为(n-1)*(2n+1)=2n2-n-1，因此时间复杂度T(n)=2n2-2=O(n2)。

例2：

i=1; //语句1 while (i<=n)

i=i*2; //语句2

解：语句1频度为1；设语句2频度为f(n)，则有2f(n)<=n，即f(n)<=log2n，去极大值，f(n)=log2n，因此时间复杂度T(n)=1+log2n=O(log2n)。

2 / 62

第二章 线性表

2.1 线性表的概念和运算

1.线性表的概念

线性表是 n (n≥0) 个类型相同的数据元素组成的有限序列。其中数据元素的个数n为线性表的长度，当n=0时称为空表。

2.线性表的特点

对于非空的线性表，有且仅有一个开始结点和一个终端结点；开始结点没有直接前趋，有且仅有一个直接后继；终端结点没有直接后继，有且仅有一个直接前趋；其余任何结点有且仅有一个直接前趋和一个直接后继。

3.线性表的计算

(1) 置空表 SETNULL(L) ：将线性表L置为空表。

(2) 求长度 LENGTH(L) ：返回是线性表L中结点的个数。

(3) 取结点 GET(L, i ) ：当1 ≤ i ≤ LENGTH(L)时，返回线性表L中的第 i 个结点，否则返回NULL。

(4) 定位 LOCATE(L, x) ：当线性表L中存在一个值为x的结点时，结果是该结点的位置；若表L中存在多个值为x的结点，则返回首次找到的结点位置；若表L中不存在值为x的结点，则返回一个特殊值表示值为x的结点不存在。

(5) 插入 INSERT(L, x, i) ：在线性表L的第i个位置插入一个值为x的新结点。这里1 ≤ i ≤ n+1，n是原表L的长度。

(6) 删除 DELETE(L, i) ：删除线性表L的第i个结点。这里1 ≤ i ≤ n，n是原表L的长度。

2.2 线性表的存储结构

1.顺序存储：

（1）定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。简言之，逻辑上相邻，物理上也相邻。

（2）顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现。 （3）地址计算：设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则地址计算公式：LOC(ai) = LOC(a1) + ( i-1)*L。

（4）结构定义：

#define MAXSIZE 1024 //线性表的最大长度 typedef int datatype; //线性表数据元素类型 typedef struct {

datatype data[MAXSIZE];

int last; //指示线性表的终端结点在表中的下标值 }sequenlist;

2.链式存储：

3 / 62

（1）特点：用一组任意的存储单元存储线性表的数据元素，利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素，每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息。 （2）头指针、头节点、开始节点 头指针是指向链表中第一个结点（或为头结点或开始结点）的指针，单链表可由一个头指针唯一确定。

头结点是在链表的开始结点之前附设的一个结点；数据域内只放空表标志和表长等信息； 开始结点是指链表中存储线性表第一个数据元素a1的结点。 （3）空表的表示

无头结点时，当头指针的值为空时表示空表； 有头结点时，当头结点的指针域为空时表示空表。 （4）结构定义

typedef int datatype; //线性表数据元素类型 typedef struct node {

datatype data; //数据域 struct node *next; //指针域 } linklist;

3.存储结构比较

（1）优缺点

顺序存储的优点是存储密度大(＝1)，存储空间利用率高。缺点是插入或删除元素时不方便。适合做查找这样的静态操作。

链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小(<1），存储空间利用率低。适合做做插入、删除这样的动态操作。

（2）线性表的顺序存储与链式存储对线性表的运算比较

顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

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

（3）时间复杂度和存储密度比较

顺序存储存储密度=1，链式存储<1。顺序表中访问任意一结点的时间复杂度均为O(1)，但是在插入和删除时时间复杂度为O(n)。链表时间复杂度为O(n)。

4.单链表操作

（1）查找

void findValue(Linklist *head ,int x){ Linklist *t; t = head->next;

while(t!=NULL && t->data !=x) t=t->next; if(t->data == x)

printf(\成功找到\\n\ else

printf(\没有找到\\n\}

（2）插入

void insert(Linklist *head,int x){

4 / 62