数据结构——学习经验

管理员

数据结构

各位读者朋友,我是你们的好朋友IT黑铁,最近巩固一下数据结构,大部分适合我当前阶段的知识都已做了简介,而其他只列出了名字的有的是省略点到即可,有些高深的暂未研究。若有错误,请多指教!

一、逻辑概念

a)线性表:数据元素之间存在一对一的关系。

b)非线性表:数据元素之间存在复杂的关系,如一队多、多对多、仅在同一域中而无其他关系。

二、存储结构(物理概念)

a)顺序表:借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

b)链表:通过存放指向下一元素的指针来表示数据元素之间的逻辑关系。

三、典型数据结构

       1.数组

       一维数组是一个数据元素单一的线性表,衍生了字符串、二维数组、广义表等处理不同逻辑的功能线性表。

       其中存储结构实现因其特性而在不同方面各有优缺点,视情况而定。

       对于二维数组,值得一提的是其矩阵的特性,可以实现压缩数据。

       2.栈和队列

      栈和队列是扩展的数组,特殊的线性表,其操作因其应用场景受限而早就了此两种数据结构,广泛应用于符合特性场景的问题中。

栈:后进先出(Last In First Out,LIFO)。关键操作函数:pop()、push()

top()。另外,栈通常可以将递归算法转换为非递归,正因为其特性与递归过程相似。

      队列:先进先出(First In First Out,FIFO)。关键操作函数:EnQueue()、DeQueue()、GetHead()。队列中需要注意的问题是顺序表的假溢出,是因为进队和出队使得头尾指针越界,通过取模运算实现循环队列,即可解决该问题,而若是链表实现的队列则无该问题,毕竟其是直接指针指向下一元素。

       3.树和二叉树

      树是一种广泛应用的数据结构,来源于生活,其逻辑结构无处不见,自顶向下,分支分布。它的术语有:结点、度、深度、有序树和无序树、兄弟、父结点、森林等。

      二叉树:最多有两个分叉的树就是二叉树,是有序树,子树也是二叉树。还有完全二叉树,满二叉树均可见名知意。

      树的存储结构,同样是各有优缺,根据用途衍生诸多数据结构,如:线索二叉树、双亲表示法、孩子表示法、孩子兄弟表示法(较为普遍,因为可以将其他树转换为二叉树)等。

       其他相关术语简介:

哈夫曼树(又称最优树),采用贪心算法首先选权小的来生成树,用于解决最优前缀码问题。

生成树:连通图(无向图的生成树),包含子图中所有顶点,但只有n-1条边。当然,有向图也有一种树叫有向树,有向树构成的有生成森林。

二叉排序树(Binary Sort Tree,二叉搜索树):根节点大于左子树的值和小于右子树的值,并且左右子树也须满足该性质。

平衡二叉树(Balanced Binary Tree,前苏联数学家Adelson-Velskii和Landis提出,又称AVL树):改进二叉排序树,因为树的高度越低搜索效率越快,在二叉排序树的基础上推出左右子树的深度之差绝对值不超过1,以此保持其高度在一个低的范围内。而要想保持,则将使用到树的旋转操作。

B树:前面的查找方式都属于内查找法,适用于内存中较小的文件,因为内查找法以结点为单位,要反复进行内、外存的交换,不使用于外存的大文件。推出B树解决问题,B树中一个结点拥有众多关键字,每个关键字也是数据,搜索原理也同样是二叉排序树的原理。其插入、删除等操作始终是当结点数据位不够时,取结点中排序后的中间位放到父节点去,父节点多余继续执行此策略,直到满足其定义。无需关注的是B树的叶子结点都在同一层次,并且不带信息,称为失败结点,引入该结点只是为了便于分析B树的查找性能。

B+树:B树的变形树,与B树和二叉搜索树的区别在于所有的叶子结点都包含了所有的关键字,而其父节点关键字通常是其子树结点中最大(或最小)的数据。有多少棵子树,结点里就有多少个关键字。

红黑树

       4.图

图同样在生活中四处可见,千变万化,最为复杂。根据具体情况分为连通图、非连通图、回路(或环)、有向图(强连通图,其极大强连通子图成为强连通分量)、无向图(连通图,其极大连通子图成为连通分量)。

树的存储结构:邻接矩阵、邻接表、逆邻接表、十字链表(将邻接表和逆邻接表结合得到两者优点的表)、邻接多重表(解决找边难的问题)。

最小生成树算法

普里姆(Prim)算法:加点法,,每次集合中一次找与当前已加入树中最短边的点,知道所有点都加进来。

克鲁斯卡尔(Kruskal)算法:加边法,每次从集合中找最短的一条边加入树中,直到所有顶点都在同一连通分量上。

       最短路径

      单源最短路径算法(Dijkstra,迪杰斯特拉):使用贪心和迭代的思想。

      任一对顶点最短路径算法(Floyd,弗洛伊德)

       拓扑排序

      检测是否图中是否有环或回路。

      拓扑排序的过程:

(1)  在有向图中选一个无前驱顶点且输出它

(2)  从图中删除该顶点和所有以它为尾的弧

(3)  重复(1)和(2),直至不存在无前驱的顶点

(4)  若此时输出的顶点树小于有向图的顶点数,则说明有向图中存在环,否则输出的顶点即为一个拓扑序列(AOV网,Activity On Vertex Network)。

关键路径

      AOE网,Activity On Edge Network。

四、经典问题

1.查找

线性表的查找:顺序查找(O(n))、折半查找(O(log2n))、分块查找(索引顺序查找)(两者之间)。

树表的查找:二叉搜索树(O(log2n))、平衡二叉树、B树、B+树。

散列表(Hash表)的查找:除了顺序查找外,上述查找方式都需要构建有序的结构,而Hash表通过函数映射,将数据映射到唯一的索引下,性能可以达到O(1)。但因为数据大、杂,函数映射通常会引起冲突,解决冲突的方法有开放地址法(包含线性探测法、二次探测法、随机探测法等)、还有链地址法。

       2.排序

              a)插入排序

       直接插入排序(O(n2))、折半插入排序(O(n2))、希尔排序(缩小增量排序)(O(n3/2)))

              b)交换排序

             冒泡排序(O(n2))、快速排序(改进的冒泡排序,O(nlog2n))

              c)选择排序

       简单选择排序(直接选择排序,O(n2))、树形选择排序(竞标赛排序,O(nlog2n))、堆排序(改进的树形选择排序,因为树形辅助存储空间较多、最大值多余比较等缺点,O(nlog2n))。

       堆:满足ki>=k2i且ki>=k2i+1 或ki<=k2i且ki<=k2i+1。

              d)归并排序(O(nlog2n))

              e)基数排序(接近O(n))

             多关键字的排序、链式基数排序

              f)外部排序

       上述排序都是内部排序,内存中完成的。这种排序适用于外存分批调入内存的排序。