广东专升本-计算机-数据结构满分200我186_思维导图模板

数据结构

数据结构引论

《数据结构与算法》的研究内容

随着计算机产业的发展应用领域

数值计算领域

加工处理的对象：纯粹的数值

非数值计算领域

工业检查

过程控制

管理系统

文字处理

...

数据结构的基本概念

基本概念

数据

各种符号的集合

数据元素

数据的基本单位（用于完整描述一个对象）

数据项

构成数据元素的最小单位

数据对象

（常用单位）性质相同的数据元素的集合，是数据的一个子集

数据结构

逻辑结构（从具体问题抽象出来的数学模型）

线性结构

线性表

栈（特殊线性表）

队列（特殊线性表）

字符串、数组、广义表

非线性结构

树形结构

图形结构

存储结构（物理结构）

顺序结构

链式结构

数据的运算

检索、排序、插入、删除、修改等

数据类型和抽象数据类型

基本概念

数据类型

一组性质相同的值的集合，以及定义这个值集合上的一组操作的总称

抽象数据类型

从具体问题抽象出来的一个数学模型，以及定义在此数学模型上的一组操作

包含三部分：数据对象、数据对象上关系的集合、对数据对象的基本操作的集合

抽象数据类型的实现

算法和算法分析

算法

算法的定义

对特定问题的求解方法和步骤的一种描述

算法特性

有穷性

确定性

可行性

输入

输出

评价算法的优劣的基本标准/算法设计要求

正确性

健壮性

可读性

高效性

算法分析

好的算法首先符合算法设计的要求

再主要考虑算法的效率

时间效率

算法时间复杂度

空间效率

算法空间复杂度

只需分析该算法再实现时所需要的辅助空间就可以

例

变量t——

数组b[n]——

算法的复杂度取决于

问题的规模

待处理数据的初态

衡量算法效率的方法

事前分析估算法

事后统计法

问题规模和语句频度

问题规模：算法求解问题输入量的多少

不考虑计算机的软硬件等环境因素，影响算法时间代价的最主要因素是问题规模

语句频度：一条语句的重复执行次数

设每条语句执行依次所需的时间均是单位时间，则一个算法的执行时间可用该算法中所有语句频度之和来度量

基本数据结构

线性结构

线性表

线性表的逻辑结构

线性表的逻辑定义

由个数据特性相同的元素构成的有限序列称为线性表

其中元素的个数定义为线性表的长度

时称为空表

常见的线性表的基本运算

InitList(&L)

ListLength(L)

GetElem(L,i,&e)

LocateElem(L,e)

ListInsert(&L,i,e)

ListDelete(&L,i)

线性表的顺序存储结构（顺序表）

顺序表定义及地址计算

1、顺序表的定义

顺序存储结构/顺序映像：用一组地址连续的存储单元依次存储线性表的数据元素

应用顺序存储结构的线性表称为顺序表

特点：逻辑上相邻的数据元素，其物理次序也是相邻的

2、地址的计算方法

...

只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取

所以线性表的顺序存储结构是一种随机存取的存储结构

3、顺序表类型

通常用数组来描述数据结构中的顺序存储结构

数组

基本特点

数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变

初始化

// 初始化一个长度为 5 的数组 array
int array[5];

// 元素赋值
array[0] = 2;
array[1] = 3;
array[2] = 1;
array[3] = 0;
array[4] = 2;

int array[] = {2, 3, 1, 0, 2};

顺序表的基本操作

1、初始化

1、为顺序表动态分配一个预定义大小的数组空间，使 elem 指向这段空间的基地址

2、将表的当前长度设为 0

2、取值

算法步骤

1、判断制定的位置序号 i 值是否合理 (1<=i<=L.length) 若不合理，则返回 ERROR

2、若值合理，则将第 i 个数据元素 L.elem[i-1]赋给参数 e ，通过 e 返回第 i 个数据元素的传值

由于顺序存储结构具有随机存取的特点，可以直接通过下标定位得到

顺序表取值算法的时间复杂度为

3、查找

算法步骤

1、从第一个元素起，依次和 e 相比较，若找到与 e 相等的元素 L.elem[i]，则查找成功，则返回该元素的序号

2、若查遍整个顺序表都没有找到，则查找失败，返回 0

顺序表按值查找算法的平均时间复杂度为

4、插入

一般的，在第个位置插入一个元素，需从最后一个元素即第个元素开始，依次向后移动一个位置，直至第个元素，仅当插入位置时，才无须移动结点

顺序表插入算法的平均时间复杂度为

5、删除

算法步骤

1、判断删除位置 i 是否合法，若不合法则返回ERROR

2、将第 i+1 个至第 n 个的元素依次向前移动一个位置（i=n时无须移动）

3、表长-1

顺序表删除算法的平均时间复杂度为

线性表的链式存储结构（链表）

单链表

定义与表示

单链表的定义

用一组任意的存储单元存储线性表的元素。这组存储单元可以是连续的，也可以是不连续的

单链表的每个结点中只包含一个指针域

单链表是非随机存取的存储结构。要取第i个据元素必须从头指针出发顺链进行寻找也称为顺序存取的存储结构

头结点

便于首元结点的处理

并于空表和非空表的统一处理

头结点、头指针、首元结点的区别

首元结点是指链表中存储的一个数据元素的结点

头结点是在首元节点之前附设的一个节点，其指针域指向首元结点

头指针是指链表中第一个结点的指针

基本操作

（1）初始化

单链表的初始化操作就是构造一个空表

1）生成新的结点作为头结点。用头指针L指向头结点。

2）头结点的指针域置空

（2）取值

1）用指针 P 指向首元结点，用 j 做计数器，初值赋为 1

2）从首元结点开始依次顺着链域 next 向下访问，只要指向当前结点的指针 P 不为空，并且没有达到序号 i 的结点，则循环执行以下操作

p 指向下一个结点

计数器 j 相应加 1

3）退出循环时，如果指针 p 为空或者计数器 j 大于 i，说明指定的序号 i 值不合法（i 大于表长 n 或 i 小于等于 0）取值失败返回 ERROR；否则取值成功。此时若 j 等于 i，p 所指向的节点就是要找的第 i 个结点，用参数 e 保存当前节点的数据域，返回OK。

算法平均时间复杂度为 O(n)

（3）查找

链表中按值查找的过程和顺序表类似。从链表首元结点出发，依次将节点值的和给定值 E 进行比较，返回查找结果。

1）用指针P指向首元结点

2）从首元结点开始，一次顺着链域next向下查找，只要指向当前结点的指针P不为空。并且P所指结点的数据域不等于给定值E，则循环执行操作：P指向下一个节点

3）返回P，若查找成功批次实际为节点的地址值，若查找失败，P的值即为null

算法平均时间复杂度为 O(n)

（4）插入

s->next=p->next；p->next=s

1）查找结点 a(i-1) 并由指针 p 指向该结点

2）生成一个新结点 *s

3）将新结点 *s 的数据域置为e

4）将新结点 *s 的指针域指向a(i)

5）将结点 *p 的指针域指向新结点 *s。

算法平均时间复杂度为 O(n)

（5）删除

要删除单链表中指定位置的元素，同插入元素一样。首先应该找到该位置的前驱节点

1）查找结点 a(i-1) 并由指针 p 指向该结点

2）临时保存待删除结点 a(i) 的地址在 q 中。以备释放。

3）将结点 *p 的指针域指向 a(i) 的直接后继结点

4）释放节点 a(i) 的空间

p->next=p->next->next

算法平均时间复杂度为 O(n)

（6）创建单链表

前插法：是通过将新结点逐个插入链表的头部（头结点之后）来创建链表

后插法：将新结点逐个插入到链表的尾部来创建链表

链表的基本操作

单链表删除结点

p.next ——> q.next

单链表插入结点

s.next ——> a2

p.next ——> x

双（向）链表删除结点

1、t->prior->next = t->next

2、t->next->prior = t->prior

原则：保证链不断

循环链表

单循环链表

在循环链表中，从任意一个节点出发都可以找到表中其他节点称作单链的循环链表，简称单循环链表

双循环链表

在链表的每一个结点中设置两个指针，一个指向后继结点，一个指向前驱结点。形成双链表，简称双链表。

顺序表和链表的比较

存储空间的分配

当线性表的长度变化比较大，难以预估存储规模时，宜采用链表作为存储结构

当线性表的长度变化不变，易于事先确定其大小时，以采用顺序表作为存储结构

存储密度的大小

顺序表是由数组实现的，它是一种随机存取结构，取值操作的效率高

链表是一种顺序存取结构，按位置访问。取值操作的效率低

若线性表的主要操作是和元素位置紧密相关的取值操作，很少做插入或删除时已采用顺序表作为存储结构。

对于频繁进行插入或删除操作的线性表一采用链表作为存储结构

顺序存储与链式存储对比

线性表的应用

线性表的合并

1）分别获取 LA 表长 m 和 LB 表长 n

2）从 LB 中第 1 个数据元素开始，循环 n 次执行以下操作

从 LB 中查找第 i 个元素赋给 e

在 LA 中查找元素一如果不存在，则将 E 插入在 LA 的最后

有序表的合并

顺序有序表的合并

1）创建一个表长为 m+n 的空表 LC

2）指针 pc 初始化，指向 LC 的第一个元素

3）指针 pa 和 pb 初始化，分别指向 LA 和 LB 的第一元素

4）当指针 pa 和 pd 均未到达相应表尾时，则依次比较 pa 和 pd 所指向的元素值，从 LA 或 LB 中取元素值较小的结点插入到 LC 的最后

5）如果 pb 已到达 LB 的表尾，依次将 LA 的剩余元素插入到 LC 的最后

6）如果 pa 已到达 LA 的表尾，依次将 LB 的剩余元素插入到 LC 的最后

链式有序表的合并

1）指针 pa 和 pd 初始化，分别指向 LA 和 LB 的第一结点

2）LC 的结点取值为 LA 的头结点

3）指针 pc 初始化，指向 LC 的头结点

4）当指针 pa 和 pb 均未到达相应表尾时，则依次比较 pa 和 pb 所指向的元素值，从 LA 或 LB 中取元素值较小的结点插入到 LC 的最后

5）将非空表的剩余部分插入 pc 所指结点之后

6）释放 LB 的头结点

栈和队列

栈

基本特点

栈是一种具有「后进先出」特点的抽象数据结构，可使用数组或链表实现。

栈是限定仅在表尾进行插入或删除操作的线性表，他也有两种存储表示方法

顺序栈

存储空间预分配，可能会出现空间闲置或栈满溢出现象

链栈

是指采用链式存储结构实现的栈，通常采用单链表来表示

存储空间动态分配，不会出现空间闲置或栈满溢出现象

元素不一定排好队连续地进栈，有时某一元素可能会进栈后立刻出栈，然后下一个元素才会进栈。

也就是说元素进栈后，不一定会依次出栈

栈的基本运算

初始化

InitStack(&S)

顺序栈

为顺序栈动态分配一个预定义大小的数组空间

链栈

构造一个空栈，直接将栈顶指针置空即可

入栈与出栈

入栈：Push(&S,x)

顺序栈

入栈操作是指在栈顶插入一个新的元素，需要判断栈是否满

通过常用操作「入栈 push()」,「出栈 pop()」，展示了栈的先入后出特性

stk.push(1); // 元素 1 入栈
stk.push(2); // 元素 2 入栈
stk.pop(); // 出栈 -> 元素 2
stk.pop(); // 出栈 -> 元素 1

链栈

与顺序栈不同的是，链栈在入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个结点空间

出栈：Pop(&S,&x)

顺序栈

出栈操作是将栈顶元素删除，需要判断栈是否空

链栈

与顺序栈一样，链栈在出栈前也需要判断栈是否为空，不同的是，链栈在出栈后需要释放出栈元素的栈顶空间

取栈顶元素

GetTop(S)

顺序栈

当栈非空时，此操作返回当前栈顶元素的值，栈顶指针保持不变

链栈

与顺序栈一样，当栈非空时，此操作返回当前栈顶元素的值，栈顶指针S保持不变

判断栈是否为空

StackEmpty(S)

栈与递归

采用递归算法解决问题

定义是递归的

分治法

递归求解问题的条件

（1）能够将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同仅是处理的对象，并且这些处理对象更小，而且变化有规律。

该问题的规模缩小到一定的程度就可以容易地解决

该问题可以分解为若干个规模较小的相同问题

利用该问题分解出的子问题的解可以合并为该问题的解

该问题所分解出的各个子问题是相互独立的

（2）必须有一个明确的递归出口，或称递归的边界

分解——解决——合并

数据结构是递归的

问题的解法是递归的

用栈实现递归·

当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，调用函数和被调用函数之间的链接及信息交换必须通过栈来实现。

递归算法的效率分析

时间复杂度的分析

递归算法：

计算Hanoi塔递归算法的时间复杂度：

空间复杂度的分析

递归算法：

计算阶乘问题、Hanoi塔问题的递归算法的空间复杂度

利用栈将递归转换为非递归的方法

递归：通过重复将问题分解成同类的子问题而解决问题的方法

通过调用函数自身来进行递归

优缺点：结构清晰、可读性强；但效率低，调用栈层数太多时可能会溢出

队列

基本特点

队列是一种具有「先进先出」特点的抽象数据结构，可使用链表实现。

队列又称先入先出表，FIFO表

队列是限定只在表头（队头）进行删除操作，只在表尾（队尾）进行插入的线性表

队列也有两种存储表示，顺序和链式表示

队列的运算和操作实现

队列的基本运算

初始化

queue que;

入队与出队

通过常用操作「入队 push()」,「出队 pop()」，展示了队列的先入先出特性

que.push(1); // 元素 1 入队
que.push(2); // 元素 2 入队
que.pop(); // 出队 -> 元素 1
que.pop(); // 出队 -> 元素 2

顺序队列的表示

循环队列及操作实现

循环队列可以解决顺序队列的“假溢出”问题

求队列长度

对于非循环队列，尾指针和头指针的差值就是队列长度

循环队列则：(tail-head+size)%size

入队与出队

入队：队尾插入一个新的元素

出队：将队头元素删除

取队头元素

链队及操作实现

链队的定义及存储结构

链队是指采用链式存储结构实现的队列

初始化

链队的初始化：构造一个只有一个头结点的空队

入队与出队

链队再出队后需要释放队头元素的所占空间

取队头元素

优先队列

定义

一个以集合为基础的抽象数据类型，其结点必定包括一种性质：有序

优先队列中的每一个元素都有一个优先级

简单实现

有序链表

二叉搜索树

无序链表

优先级树和堆

优先级树

优先级堆

可并优先队列

左偏树

左偏树的合并运算

串、数组和广义表

串

基本概念

串是由零个或多个字符组成的有限序列

串的长度

串中所包含的字符个数

串的大小

串中所包含的字符个数+1('\0')

空串

零个字符的串称为空串，其长度为零，它不包含任何字符，是任意串的子串

子串

串中任何个连续字符组成的子序列

主串

包含子串的串

空格串

由一个空格串组成的串称为空格串，其长度为串空格字符的字数

空格串不是空串

当且仅当两个串的值相等时称两个串是相等的

求子串数目

主串：n

子串：

串的基本运算

（1）求串长：int strlen(char *s)

（2）串复制：char *strcpy(char *to,char *from)

（3）串联接：char *strcat(char *to,char *from)

（4）串比较：int strcmp(char *s1,char *s2)

串的存储结构

顺序存储结构

链式存储结构

简称“链串”

子串的定位运算

又称“串的模式匹配”或“串匹配”

找子串在主串中首次出现的位置

在串匹配中，将主串称为目标串，子串称为模式串

广义表

定义

广义表是n个表元素组成的有限序列，是线性表的推广

通常用递归的形式进行定义

线性和非线性之间的一种过渡结构

长度 & 深度

LS1=(a，(b，c)，(d，(e，f)))

长度为 3

深度为 3

D=(a,D)=(a,(a,(a,(...))))

长度为 2

深度为

表示规则

E=( )

E是一个空表，长度为0

L=(a,b)

L是长度为2的广义表，两个元素都是原子，因此它是一个线性表

（1）广义表的元素可以是子表

A=(x,L)=(x,(a,b))

A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L

B=(A,y)=((x,(a,b)),y)

B是长度为2的广义表，第一个元素是表A，第二个元素是原子y

C=(A,B)=((x,(a,b)),((x,(a,b)),y))

C是长度为2的广义表，两个元素都是子表

（2）广义表可为其他广义表所共享

（3）广义表可以是一个递归的表

D=(a,D)=(a,(a,(a,(...))))

D是一个递归的表，长度为2，第一个元素是原子a，第二个元素是D自身，展开后它是一个无限的广义表

图形表示

基本运算

取表头：GetHead(Ls)

深度为 1 的表的第一个元素为表头

可以是广义表或单个元素

取表尾：GetTail(Ls)

除表头外的所有元素为表尾

其结果必定是广义表(子表)的形式

矩阵

矩阵的压缩存储

高阶矩阵包含许多相同的元素和零元素，为节省空间

采用多个值相同的元素只分配一个空间、零元素不存储的策略

非线性结构

树和二叉树

树

以分支关系定义的层次结构

有且只有一个称之为根的结点

除根之外的其余结点可以分为m（m>0）颗子树，称为根的子树

广东专升本-计算机-数据结构满分200我186

模板简介

猜你喜欢

相关文章