数据结构与算法知识小结2

数据结构与算法知识小结2
小结1总结了数据结构与算法的大体理解，现在主要分享具体的算法结构。
线性表的基本运算
（1） 求表长——求线性表中元素的个数。
（2） 遍历——从左到右或从右到左扫描或读取表中的各元素。
（3） 按编号查找——找出表中的第n个元素。
（4） 按特征查找——按某个特定值查找线性表。
（5） 插入：InsertList（L,X,3）——在第i个位置上（即原第i个元素前）插入一个新元素。（顺序表的插入：首先得判断顺序表是否已经满了，如果满了就不能进行插入操作，未满时将后面的元素从最后一个开始依次往后移，到要插入的位置为空时才能插入元素，L增大。）
L：顺序表长度 ； X：插入元素 ； 3：要插入的位置
（6） 删除：Delete（L,3） ——删除原表中的第i个元素。（顺序表的删除：删除某位置的元素，在它之后的元素依次往前移动，没有则不用，L减小。注意：删除前要备份删除的元素）
L：顺序表长度 ； 3：要删除的位置
（7） 排序——按元素某个特征值的递增或递减排序，重排表中各元素。
链表不是地址连续的空间，他的插入和删除不需要移动元素。
堆栈
堆栈的基本运算：
（1） StackInit()：初始化堆栈
（2） StackEmpty(s)：判断堆栈s是否为空
（3） StackLength(s)： 求堆栈s的长度
（4） GetTop(s)： 获取栈顶元素的值
（5） Push(s,e)： 将元素e进栈
（6） Pop(s)：出栈（删除栈顶元素）
栈有两种存储结构，分别为顺序栈和链栈。
顺序栈：后进先出原则（LIFO），进入时top先移动然后元素再进来；出去时元素先出去top后移动。注意：只有栈顶能够操作
判断栈满：top=Maxsize-1 判断栈空：top=-1
出入栈代码如下：

队列：先进先出原则（FIFO），他是只能在表的一端（队尾 rear）做插入运算，另一端（队首 front）做删除运算的一种队列，简称队。插入运算也称为入队，反之删除运算称之为出队。
队列也有两种存储结构，分别为顺序队列和链式队列。
顺序队列：入队时先判断队列是否满了，未满时入队是rear移动，即rear+1；出队时front移动，即front++。
顺序队列判断队空：front=rear=-1 顺序队列判断队满：rearMaxsize-1
在rearMaxsize-1时可以判断为队满（溢出），但是有些时候会是假溢出，为了避免这种问题，可以使用循环队列。
循环队列：指的是把数组的前端和后端连接起来形成一个环形的表。入队时先判断循环队列是否满了，未满时入队是front=（front+1）% MaxSize；出队时rear =（rear +1）% MaxSize 。
初始化时front=rear=0
循环队列判断队空：frontrear
循环队列判断队满：front（rear+1）% MaxSize
字符串
字符串：字符串是由数字、字母或任意其他符号组成的一串字符，简称串。它是编程语言中表示文本的数据类型（string），是数据元素类型都为字符的一种线性表。
目前我常用到字符串的运算有Insert、Delete、Replace、Equal、Length。
注意：字符串的长度是可以为0的。
数组与矩阵
数组是有序的元素序列，它的存储方式是有序的，数组中有多个值，它的元素个数不能小于或等于1，它的元素的地址是连续的。
数组有一维数组、二维数组、三维数组、四维数组、五维数组。一维数组的每一个元素都是一维数组，构成二维数组。所以可以这样比喻，二维数组是一页纸，三维数组是一本书，四维数组是书架，五维数组是图书馆。
矩阵是一个按照长方阵列排列的复数或实数组合。
特殊矩阵：零矩阵、方阵、对角矩阵、单位矩阵、上或下三角形矩阵、行或列矩阵。
树
树：每棵树的根节点只有一个直接前驱，但是直接后继可以为0个或多个。
二叉树是规定每个结点至多只有两个孩子的树，它是树形结构中最典型、最常用的结构，所以这里以二叉树为例：
设访问根节点记作T，遍历根的左子数记作L，遍历根的右子数记作R 。

下图来自博客—龙跃十二