数据结构简单总结

hanyujianke 2020-03-28

一、思维导图

数据结构简单总结

二、重要概念

一.数据结构

1.逻辑结构

集合、线性结构、树形结构、图形结构。

2.存储结构

常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。

3.算法分析

1)目标:正确性、可使用性、可读性、健壮性、时间效率高与储存量低

2)方法:事后估计法、事前分析估算法

3)两个角度:时间复杂度、空间复杂度。二者不可能都为最低,需维持一个合适的平衡。

二.线性表

1.定义

具有相同特性的数据元素的一个有限序列。

其中每个元素都是一对一的相互关系。

2.普通线性表

1)顺序表

特点:逻辑上相邻且物理地址也相邻;实现随机存储(快速访问)。

2)链表

特点:线性表中的数据元素存放在一组地址任意的存储节点,节点之间使用“”进行连接。

分为单链表、双链表、循环链表。

3.栈

一种特殊的线性表——只能在一端进行插入、删除操作的线性表。

根据存储结构可以分为两种,顺序栈和链栈。

基本运算

InitStack(&S):初始化栈

DestroyStack(&S):销毁栈

StackEmpty(&S):判断栈是否为空

Push(&S,e):进栈

Pop(&S,&e):出栈

GetTop(S,&e):取栈顶元素

PS:进栈和出栈可是穿插进行

4.队列

队列是一种只能在一端进行插入,在另一端进行删除操作的线性表。

也可根据存储结构分为顺序队列和链队列。

基本运算

InitQueue(&q):初始化队列

DestroyQueue(&q):销毁队列

QueueEmpty(&q):判断队列是否为空

enQueue(&q,e):入队列

deQueue(&q,&e):出队列

顺序队列
  • 队空条件:front=rear

  • 队满条件:(rear+1)%MaxSize=front

  • 入队操作:rear=(rear+1)%MaxSize;将新元素放在rear处;

  • 出队操作:front=(front+1)%MaxSize;取出front处元素;

5.串(地位重要)

基本概念:是由零个或多个字符组成的有限序列;串是数据元素为单个字符的特殊线性表

串一般分为主串和子串。

串的模式匹配

1)BF算法

1.将主串和子串的字符一个个进行比较,当字符不匹配时回溯到i=i-j+1;

2.最好时间复杂度O(m)。

3.最坏时间复杂度O(n*m)。

2)KMP算法

1.利用已经部分匹配的结果来消除主串的回溯。

2.平均时间复杂度为O(n+m)。

三、疑难问题

1.编程中遇到的答案错误,但不知到发生在哪。

我通过将每个步骤的值输出然后进行观察,检查数据到哪一步发生与预料中不同的结果,然后对该步骤进行修改,再检验,最后得出想要的代码。

相关推荐