没有合适的资源?快使用搜索试试~ 我知道了~
个人考试国家电网概括的一点点复习内容
需积分: 1 0 下载量 47 浏览量
2023-12-03
20:14:43
上传
评论
收藏 3.5MB DOCX 举报
温馨提示
试读
33页
感觉自己复习了,弄了这个,想要上传一下,做个纪念
资源推荐
资源详情
资源评论
数据结构与算法
1. 数据结构基本概念
数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经
过这些运算后所得到的新结构仍然是原来的结构类型。
1) 数据:所有能被输入到计算机中,且能被计算机处理的符号的集合。是计算机操作的对象的总称。
2) 数据元素:数据(集合)中的一个“个体”,数据及结构中讨论的基本单位
3) 数据项:数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。
4) 数据类型:在一种程序设计语言中,变量所具有的数据种类。整型、浮点型、字符型等等
5) 逻辑结构:数据之间的相互关系。
集合 结构中的数据元素除了同属于一种类型外,别无其它关系。
线性结构 数据元素之间一对一的关系
树形结构 数据元素之间一对多的关系
图状结构或网状结构 结构中的数据元素之间存在多对多的关系
6) 物理结构/存储结构:数据在计算机中的表示。物理结构是描述数据具体在内存中的存储(如:顺序结构、
链式结构、索引结构、哈希结构)等
7) 在数据结构中,从逻辑上可以将其分为线性结构和非线性结构
8) 数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。实现应用程序是“逻辑
结构”,存储的是“物理结构”。逻辑结构主要是对该结构操作的设定,物理结构是描述数据具体在内存中的存
储(如:顺序结构、链式结构、索引结构、希哈结构)等。
9) 顺序存储结构中,线性表的逻辑顺序和物理顺序总是一致的。但在链式存储结构中,线性表的逻辑顺序和
物理顺序一般是不同的。
10) 算法五个特性: 有穷性、确定性、可行性、输入、输出
11) 算法设计要求:正确性、可读性、健壮性、高效率与低存储量需求。(好的算法)
12) 算法的描述有伪程序、流程图、N-S 结构图等。E-R 图是实体联系模型,不是程序的描述方式。
13) 设计算法在执行时间时需要考虑:算法选用的规模、问题的规模
14) 时间复杂度:算法的执行时间与原操作执行次数之和成正比。时间复杂度有小到大:O(1)、O(logn)、
O(n)、O(nlogn)、O(n2)、O(n3)。幂次时间复杂度有小到大 O(2n)、O(n!)、O(nn)
15) 空间复杂度:若输入数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的辅
助变量所占额外空间。
2. 线性表
线性表是一种典型的线性结构。头结点无前驱有一个后继,尾节点无后继有一个前驱。链表只能顺序查找,定位一
个元素的时间为 O(N),删除一个元素的时间为 O(1).
1) 线性表的顺序存储结构:把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种
方法存储的线性表简称顺序表。是一种随机存取的存储结构。顺序存储指内存地址是一块的,随机存取指
访问时可以按下标随机访问,存储和存取是不一样的。如果是存储,则是指按顺序的,如果是存取,则是
可以随机的,可以利用元素下标进行。数组比线性表速度更快的是:原地逆序、返回中间节点、选择随机
节点。
2) 便于线性表的构造和任意元素的访问
3) 插入:插入新结点,之后结点后移。平均时间复杂度:O(n)
4) 删除:删除节点,之后结点前移。平均时间复杂度:O(n)
5) 线性链表:用一组任意的存储单元来依次存放线性表的结点,这组存储单元即可以是连续的,也可以
是不连续的,甚至是零散分布在内存中的任意位置上的。因此,链表中结点的逻辑次序和物理次序不一定
相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址。
data 域是数据域,用来存放结点的值。next 是指针域(亦称链域),用来存放结点的直接后继的地址(或
位置)。不需要事先估计存储空间大小。
6) 单链表中每个结点的存储地址是存放在其前趋结点 next 域中,而开始结点无前趋,故应设头指针 head
指向开始结点。同时,由于最后一个结点无后继,故结点的指针域为空,即 NULL。头插法建表(逆序)、尾
插法建表(顺序)。增加头结点的目的是算法实现上的方便,但增大了内存开销。
7) 查找:只能从链表的头指针出发,顺链域 next 逐个结点往下搜索,直到搜索到第 i 个结点为止。因此,
链表不是随机存取结构。
8) 插入:先找到表的第 i-1 的存储位置,然后插入。新结点先连后继,再连前驱。
9) 删除:首先找到 ai-1 的存储位置 p。然后令 p–>next 指向 ai 的直接后继结点,即把 ai 从链上摘下。
最后释放结点 ai 的空间.r=p->next;p->next=r->next;delete r。
10) 判断一个单向链表中是否存在环的最佳方法是快慢指针。
11) 静态链表:用一维数组来实现线性链表,这种用一维数组表示的线性链表,称为静态链表。静态:体
现在表的容量是一定的。(数组的大小);链表:插入与删除同前面所述的动态链表方法相同。静态链表中
指针表示的是下一元素在数组中的位置。
12) 静态链表是用数组实现的,是顺序的存储结构,在物理地址上是连续的,而且需要预先分配大小。动
态链表是用申请内存函数(C 是 malloc,C++是 new)动态申请内存的,所以在链表的长度上没有限制。动
态链表因为是动态申请内存的,所以每个节点的物理地址不连续,要通过指针来顺序访问。静态链表在插
入、删除时也是通过修改指针域来实现的,与动态链表没有什么分别
13) 循环链表:是一种头尾相接的链表。其特点是无须增加存储量,仅对表的链接方式稍作改变,即可使
得表处理更加方便灵活。
14) 在单链表中,将终端结点的指针域 NULL 改为指向表头结点的或开始结点,就得到了单链形式的循环链
表,并简单称为单循环链表。由于循环链表中没有 NULL 指针,故涉及遍历操作时,其终止条件就不再像
非循环链表那样判断 p 或 p—>next 是否为空,而是判断它们是否等于某一指定指针,如头指针或尾指针
等。
15) 双向链表:在单链表的每个结点里再增加一个指向其直接前趋的指针域 prior。这样就形成的链表中有
两个方向不同的链。双链表一般由头指针唯一确定的,将头结点和尾结点链接起来构成循环链表,并称之
为 双 向 链 表 。 设 指 针 p 指 向 某 一 结 点 , 则 双 向 链 表 结 构 的 对 称 性 可 用 下 式 描 述 :
p—>prior—>next=p=p—>next—>prior。从两个方向搜索双链表,比从一个方向搜索双链表的方差要小。
16) 插入:先搞定插入节点的前驱和后继,再搞定后结点的前驱,最后搞定前结点的后继。
17) 在有序双向链表中定位删除一个元素的平均时间复杂度为 O(n)
18) 可以直接删除当前指针所指向的节点。而不需要像单向链表中,删除一个元素必须找到其前驱。因此
在插入数据时,单向链表和双向链表操作复杂度相同,而删除数据时,双向链表的性能优于单向链表
3. 栈和队列
栈
栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈
底(Bottom)。先进后出。top= -1 时为空栈,top=0 只能说明栈中只有一个元素,并且元素进栈时 top 应该自增
顺序存储栈:顺序存储结构
链栈:链式存储结构。插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。通常不会
出现栈满的情况。 不需要判断栈满但需要判断栈空。
两个栈共用静态存储空间,对头使用也存在空间溢出问题。栈 1 的底在 v[1],栈 2 的底在 V[m],则栈满的
条件是 top[1]+1=top[2]。
基本操作:删除栈顶元素、判断栈是否为空以及将栈置为空栈等
对于 n 各元素的入栈问题,可能的出栈顺序有 C(2n,n)/(n+1)个。
堆栈溢出一般是循环的递归调用、大数据结构的局部变量导致的
应用,代码:
进制转换
括号匹配的检验
行编辑程序
迷宫求解:若当前位置“可通”,则纳入路径,继续前进;若当前位置“不可通”,则后退,换方向继续探
索;若四周“均无通路”,则将当前位置从路径中删除出去。
表达式求解:前缀、中缀、后缀。
操作数之间的相对次序不变;
运算符的相对次序不同;
中缀式丢失了括弧信息,致使运算的次序不确定
前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式
后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠
它的两个操作数构成一个最小表达式。
实现递归:多个函数嵌套调用的规则是:后调用先返回。
浏览器历史纪录,Android 中的最近任务,Activity 的启动模式,CPU 中栈的实现,Word 自动保存,解析
计算式,解析 xml/json。解析 XML 时,需要校验节点是否闭合,节点闭合的话,有头尾符号相对应,遇到头符
号将其放入栈中,遇到尾符号时,弹出栈的内容,看是否有与之对应的头符号,栈的特性刚好符合符号匹配的
就近原则。
不是所有的递归程序都需要栈来保护现场,比方说求阶乘的,是单向递归,直接用循环去替代从 1 乘到 n
就是结果了,另外一些需要栈保存的也可以用队列等来替代。不是所有的递归转化为非递归都要用到栈。转化
为非递归主要有两种方法:对于尾递归或单向递归,可以用循环结构算法代替
队列
队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入,而在另一端进行删除。允许删
除的一端称为队头(front),允许插入的一端称为队尾(rear)。先进先出。
顺序队列:顺序存储结构。当头尾指针相等时队列为空。在非空队列里,头指针始终指向队头前一个位置,
而尾指针始终指向队尾元素的实际位置
循环队列。在循环队列中进行出队、入队操作时,头尾指针仍要加 1,朝前移动。只不过当头尾指针指向
向量上界(MaxSize-1)时,其加 1 操作的结果是指向向量的下界 0。除非向量空间真的被队列元素全部占用,
否则不会上溢。因此,除一些简单的应用外,真正实用的顺序队列是循环队列。故队空和队满时头尾指针均相
等。因此,我们无法通过 front=rear 来判断队列“空”还是“满”
链队列:链式存储结构。限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾
做插入操作,为此再增加一个尾指针,指向链表的最后一个结点。
设尾指针的循环链表表示队列,则入队和出队算法的时间复杂度均为 O(1)。用循环链表表示队列,必定有
链表的头结点,入队操作在链表尾插入,直接插入在尾指针指向的节点后面,时间复杂度是常数级的;出队操
作在链表表头进行,也就是删除表头指向的节点,时间复杂度也是常数级的。
队空条件:rear==front,但是一般需要引入新的标记来说明栈满还是栈空,比如每个位置布尔值
队满条件:(rear+1) % QueueSize==front,其中 QueueSize 为循环队列的最大长度
计算队列长度:(rear-front+QueueSize)% QueueSize
入队:(rear+1)% QueueSize
出队:(front+1)% QueueSize
假设以数组 A[N]为容量存放循环队列的元素,其头指针是 front,当前队列有 X 个元素,则队列的尾指针值
为(front+X mod N)
串
串(String)是零个或多个字符组成的有限序列。长度为零的串称为空串(Empty String),它不包含任何字
符。通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意:空串和空白串的不同,例如“ ”
和“”分别表示长度为 1 的空白串和长度为 0 的空串。
串的表示和实现:
定长顺序存储表示。静态存储分配的顺序表。
堆分配存储表示。存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表
串的链式存储结构。
串匹配:将主串称为目标串,子串称之为模式串。蛮力法匹配。KMP 算法匹配。
4. 数组、数组的压缩存储与字符串
矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、
对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造成
很大的空间浪费。为节约存储空间和算法(程序)运行时间,通常会采用压缩存储的方法。
1) 对角矩阵:指除了主对角线以外的元素都为零的矩阵,即对 任意 i ≠ j (1≤ i , j ≤n),都有 M(i,
j)=0。由于只有主对角线上有非零元素,只需存储主对角线上的元素即可。
2) 三角矩阵:指上三角或下三角的元素都为零的矩阵。同样地,只需存储其中一部分非零元素,可以节省存储空
间。
3) 对称矩阵:指矩阵中的元素关于主对角线对称的矩阵。由于对称矩阵的非零元素有一定的规律,可以只存储其
中一部分元素,从而减少存储空间。
4) 稀疏矩阵:指大部分元素为零的矩阵。传统的按行优先次序存储方法会浪费大量空间来存储零元素,因此采用
压缩存储的方法更为合适。常见的压缩存储方法有:压缩稠密行(CSR)、压缩稠密列(CSC)、坐标列表(COO)
等。
5. 树和二叉树
树:n 个结点的有限集合(n>=0)n 为 0 时为空树。树中有一个根结点,它没有直接前驱,有零个或多个直接后继,
根结点之外的 n-1 个结点可以划分成 m 个互不相交的有限集,这些有限集称为根的子树(子树互不相交)
二叉树:有限的结点的集合,由根结点和不相交的二叉子树组成
二叉树的五种形态:
满足以下两个条件的树形结构叫做二叉树:
� 每个结点至多只有两棵子树
� 二叉树的子树有左右之分,其次序不能颠倒。树可以有序可以无序
因此树和二叉树结构不等价
其它定义和基本术语:
� 结点的度:结点直接后继的个数
� 树的度:树的所有结点的度的最大值
� 叶子结点:也称终端结点,即度为 0 的结点
� 分支结点:也称非终端结点,即度不为 0 的结点
� 孩子结点:结点的直接后继
� 双亲结点:结点的直接前驱
� 兄弟结点:同一双亲结点的孩子结点互称兄弟结点
概念区分:树的深度、树的高度、结点的高度
� 对于整棵树而言,树的深度=树的高度,即树中所有结点层次的最大值,从上往下数
� 结点的高度不同于树的高度和深度,结点的高度指指从该结点到叶子结点的最长简单路径的边的条数,从
下往上数(不同教材对结点的高度定义不同,有的从叶结点开始从 1 计数,有的从叶结点开始从 0 计数)
满二叉树与完全二叉树
� 满二叉树:每层结点均满,每层均具有最大结点数,又称完美二叉树
� 完全二叉树:与满二叉树的编号对应,但不要求每层均具有最大结点数
区别于联系:满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树
二叉树的遍历
按某种搜索路径,使二叉树每个结点均被访问且仅被访问一次。二叉树的遍历按其构成以及访问结点的顺序分为
四种方式,即先序遍历、中序遍历、后序遍历、层次遍历
用 L、D、R 分别表示遍历左子树、访问根结点、遍历有子树
先序遍历:DLR(根左右)
中序遍历:LDR(左根右)
后序遍历:LRD(左右根)
层序遍历:按层次进行遍历
先序遍历非递归算法——核心思想:借用栈结构进行父结点的暂存
中序遍历非递归算法——核心思想:借用栈结构进行父结点的暂存
剩余32页未读,继续阅读
资源评论
而眠
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功