北京网站建设 seo公司,品牌网站建设专家,学院网站建设与管理办法,怎么搞到网站在C语言的开发过程中#xff0c;灵活使用数据结构#xff0c;对提高编程效率有极大的帮助。 目录 1 数组 2 链表 3 跳表 4 栈 5 队列 6 树 7 堆 8 散列表 9 图 10 总结 数据结构想必大家都不会陌生#xff0c;对于一个成熟的程序员而言#xff0c;熟悉和掌握数据… 在C语言的开发过程中灵活使用数据结构对提高编程效率有极大的帮助。 目录 1 数组 2 链表 3 跳表 4 栈 5 队列 6 树 7 堆 8 散列表 9 图 10 总结 数据结构想必大家都不会陌生对于一个成熟的程序员而言熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合特殊的结构在不同的应用场景中往往会带来不一样的处理效率。 常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的链表、栈、队列等非线性结构包括树、图等。数据结构种类繁多本文将通过图解的方式对常用的数据结构进行理论上的介绍和讲解以方便大家掌握常用数据结构的基本知识。 1 数组
数组可以说是最基本最常见的数据结构。数组一般用来存储相同类型的数据可通过数组名和下标进行数据的访问和更新。数组中元素的存储是按照先后顺序进行的同时在内存中也是按照这个顺序进行连续存放。数组相邻元素之间的内存地址的间隔一般就是数组数据类型的大小。 2 链表
链表相较于数组除了数据域还增加了指针域用于构建链式的存储数据。链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问使得链表的自由度更高。
这表现在对节点进行增加和删除时只需要对上一节点的指针地址进行修改而无需变动其它的节点。不过事物皆有两极指针带来高自由度的同时自然会牺牲数据查找的效率和多余空间的使用。
一般常见的是有头有尾的单链表对指针域进行反向链接还可以形成双向链表或者循环链表。 链表和数组对比
链表和数组在实际的使用过程中需要根据自身的优劣势进行选择。链表和数组的异同点也是面试中高频的考察点之一。这里对单链表和数组的区别进行了对比和总结。 3 跳表
从上面的对比中可以看出链表虽然通过增加指针域提升了自由度但是却导致数据的查询效率恶化。特别是当链表长度很长的时候对数据的查询还得从头依次查询这样的效率会更低。跳表的产生就是为了解决链表过长的问题通过增加链表的多级索引来加快原始链表的查询效率。这样的方式可以让查询的时间复杂度从O(n)提升至O(logn)。 跳表通过增加的多级索引能够实现高效的动态插入和删除其效率和红黑树和平衡二叉树不相上下。目前redis和levelDB都有用到跳表。
从上图可以看出索引级的指针域除了指向下一个索引位置的指针还有一个down指针指向低一级的链表位置这样才能实现跳跃查询的目的。 4 栈
栈是一种比较简单的数据结构常用一句话描述其特性后进先出。栈本身是一个线性表但是在这个表中只有一个口子允许数据的进出。这种模式可以参考腔肠动物...即进食和排泄都用一个口...
栈的常用操作包括入栈push和出栈pop对应于数据的压入和压出。还有访问栈顶数据、判断栈是否为空和判断栈的大小等。由于栈后进先出的特性常可以作为数据操作的临时容器对数据的顺序进行调控与其它数据结构相结合可获得许多灵活的处理。 5 队列
队列是栈的兄弟结构与栈的后进先出相对应队列是一种先进先出的数据结构。顾名思义队列的数据存储是如同排队一般先存入的数据先被压出。常与栈一同配合可发挥最大的实力。 6 树
树作为一种树状的数据结构其数据节点之间的关系也如大树一样将有限个节点根据不同层次关系进行排列从而形成数据与数据之间的父子关系。常见的数的表示形式更接近“倒挂的树”因为它将根朝上叶朝下。
树的数据存储在结点中每个结点有零个或者多个子结点。没有父结点的结点在最顶端成为根节点没有非根结点有且只有一个父节点每个非根节点又可以分为多个不相交的子树。
这意味着树是具备层次关系的父子关系清晰家庭血缘关系明朗这也是树与图之间最主要的区别。 别看树好像很高级其实可看作是链表的高配版。树的实现就是对链表的指针域进行了扩充增加了多个地址指向子结点。同时将“链表”竖起来从而凸显了结点之间的层次关系更便于分析和理解。
树可以衍生出许多的结构若将指针域设置为双指针那么即可形成最常见的二叉树即每个结点最多有两个子树的树结构。二叉树根据结点的排列和数量还可进一度划分为完全二叉树、满二叉树、平衡二叉树、红黑树等。 完全二叉树除了最后一层结点其它层的结点数都达到了最大值同时最后一层的结点都是按照从左到右依次排布。 满二叉树除了最后一层其它层的结点都有两个子结点。 平衡二叉树
平衡二叉树又被称为AVL树它是一棵二叉排序树且具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。 二叉排序树是一棵空树或者若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树。 树的高度结点层次的最大值 平衡因子左子树高度 - 右子树高度 二叉排序树意味着二叉树中的数据是排好序的顺序为左结点根节点右结点这表明二叉排序树的中序遍历结果是有序的。还不懂二叉树四种遍历方式[前序遍历、中序遍历、后序遍历、层序遍历]的同学赶紧补习 平衡二叉树的产生是为了解决二叉排序树在插入时发生线性排列的现象。由于二叉排序树本身为有序当插入一个有序程度十分高的序列时生成的二叉排序树会持续在某个方向的字数上插入数据导致最终的二叉排序树会退化为链表从而使得二叉树的查询和插入效率恶化。 平衡二叉树的出现能够解决上述问题但是在构造平衡二叉树时却需要采用不同的调整方式使得二叉树在插入数据后保持平衡。主要的四种调整方式有LL左旋、RR右旋、LR先左旋再右旋、RL先右旋再左旋。这里先给大家介绍下简单的单旋转操作左旋和右旋。LR和RL本质上只是LL和RR的组合。 在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改当平衡因子大于1时就需要进行平衡化处理。从发生不平衡的结点起沿刚才回溯的路径取直接下两层的结点如果这三个结点在一条直线上则采用单旋转进行平衡化如果这三个结点位于一条折线上则采用双旋转进行平衡化。 左旋S为当前需要左旋的结点E为当前结点的父节点。 左旋的操作可以用一句话简单表示将当前结点S的左孩子旋转为当前结点父结点E的右孩子同时将父结点E旋转为当前结点S的左孩子。可用动画表示 右旋S为当前需要左旋的结点E为当前结点的父节点。右单旋是左单旋的镜像旋转。 左旋的操作同样可以用一句话简单表示将当前结点S的左孩子E的右孩子旋转为当前结点S的左孩子同时将当前结点S旋转为左孩子E的右孩子。可用动画表示 红黑树
平衡二叉树AVL为了追求高度平衡需要通过平衡处理使得左右子树的高度差必须小于等于1。高度平衡带来的好处是能够提供更高的搜索效率其最坏的查找时间复杂度都是O(logN)。但是由于需要维持这份高度平衡所付出的代价就是当对树种结点进行插入和删除时需要经过多次旋转实现复衡。这导致AVL的插入和删除效率并不高。
为了解决这样的问题能不能找一种结构能够兼顾搜索和插入删除的效率呢这时候红黑树便申请出战了。
红黑树具有五个特性 每个结点要么是红的要么是黑的。 根结点是黑的。 每个叶结点叶结点即指树尾端NIL指针或NULL结点都是黑的。 如果一个结点是红的那么它的两个儿子都是黑的。 对于任意结点而言其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。 红黑树通过将结点进行红黑着色使得原本高度平衡的树结构被稍微打乱平衡程度降低。红黑树不追求完全平衡只要求达到部分平衡。这是一种折中的方案大大提高了结点删除和插入的效率。C中的STL就常用到红黑树作为底层的数据结构。
红黑树VS平衡二叉树 除了上面所提及的树结构还有许多广泛应用在数据库、磁盘存储等场景下的树结构。比如B树、B树等。这里就先不介绍了诶下次在讲述相关存储原理的时候将会着重介绍。其实是因为懒 7 堆
了解完二叉树再来理解堆就不是什么难事了。堆通常是一个可以被看做一棵树的数组对象。堆的具体实现一般不通过指针域而是通过构建一个一维数组与二叉树的父子结点进行对应因此堆总是一颗完全二叉树。
对于任意一个父节点的序号n来说这里n从0算它的子节点的序号一定是2n12n2因此可以直接用数组来表示一个堆。
不仅如此堆还有一个性质堆中某个节点的值总是不大于或不小于其父节点的值。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 堆常用来实现优先队列在面试中经常考的问题都是与排序有关比如堆排序、topK问题等。由于堆的根节点是序列中最大或者最小值因而可以在建堆以及重建堆的过程中筛选出数据序列中的极值从而达到排序或者挑选topK值的目的。 8 散列表
散列表也叫哈希表是一种通过键值对直接访问数据的机构。在初中我们就学过一种能够将一个x值通过一个函数获得对应的一个y值的操作叫做映射。散列表的实现原理正是映射的原理通过设定的一个关键字和一个映射函数就可以直接获得访问数据的地址实现O(1)的数据访问效率。在映射的过程中事先设定的函数就是一个映射表也可以称作散列函数或者哈希函数。 散列表的实现最关键的就是散列函数的定义和选择。一般常用的有以下几种散列函数 直接寻址法取关键字或关键字的某个线性函数值为散列地址。 数字分析法通过对数据的分析发现数据中冲突较少的部分并构造散列地址。例如同学们的学号通常同一届学生的学号其中前面的部分差别不太大所以用后面的部分来构造散列地址。 平方取中法当无法确定关键字里哪几位的分布相对比较均匀时可以先求出关键字的平方值然后按需要取平方值的中间几位作为散列地址。这是因为计算平方之后的中间几位和关键字中的每一位都相关所以不同的关键字会以较高的概率产生不同的散列地址。 取随机数法使用一个随机函数取关键字的随机值作为散列地址这种方式通常用于关键字长度不同的场合。 除留取余法取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要一般取素数或者直接用 n。 确定好散列函数之后通过某个key值的确会得到一个唯一的value地址。但是却会出现一些特殊情况。即通过不同的key值可能会访问到同一个地址这个现象称之为冲突。
冲突在发生之后当在对不同的key值进行操作时会使得造成相同地址的数据发生覆盖或者丢失是非常危险的。所以在设计散列表往往还需要采用冲突解决的办法。
常用的冲突处理方式有很多常用的包括以下几种 开放地址法也叫开放寻址法实际上就是当需要存储值时对Key哈希之后发现这个地址已经有值了这时该怎么办不能放在这个地址不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希比如往后移动一个地址如果没人占用就用这个地址。如果超过最大长度则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。 再哈希法在产生冲突之后使用关键字的其他部分继续计算地址如果还是有冲突则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。 链地址法链地址法其实就是对Key通过哈希之后落在同一个地址上的值做一个链表。其实在很多高级语言的实现当中也是使用这种方式处理冲突的。 公共溢出区这种方式是建立一个公共溢出区当地址存在冲突时把新的地址放在公共溢出区里。 目前比较常用的冲突解决方法是链地址法一般可以通过数组和链表的结合达到冲突数据缓存的目的。 左侧数组的每个成员包括一个指针指向一个链表的头。每发生一个冲突的数据就将该数据作为链表的节点链接到链表尾部。这样一来就可以保证冲突的数据能够区分并顺利访问。
考虑到链表过长造成的问题还可以使用红黑树替换链表进行冲突数据的处理操作来提高散列表的查询稳定性。 9 图
图相较于上文的几个结构可能接触的不多但是在实际的应用场景中却经常出现。比方说交通中的线路图常见的思维导图都可以看作是图的具体表现形式。
图结构一般包括顶点和边顶点通常用圆圈来表示边就是这些圆圈之间的连线。边还可以根据顶点之间的关系设置不同的权重默认权重相同皆为1。此外根据边的方向性还可将图分为有向图和无向图。 图结构用抽象的图线来表示十分简单顶点和边之间的关系非常清晰明了。但是在具体的代码实现中为了将各个顶点和边的关系存储下来却不是一件易事。
邻接矩阵
目前常用的图存储方式为邻接矩阵通过所有顶点的二维矩阵来存储两个顶点之间是否相连或者存储两顶点间的边权重。 无向图的邻接矩阵是一个对称矩阵是因为边不具有方向性若能从此顶点能够到达彼顶点那么彼顶点自然也能够达到此顶点。此外由于顶点本身与本身相连没有意义所以在邻接矩阵中对角线上皆为0。 有向图由于边具有方向性因此彼此顶点之间并不能相互达到所以其邻接矩阵的对称性不再。
用邻接矩阵可以直接从二维关系中获得任意两个顶点的关系可直接判断是否相连。但是在对矩阵进行存储时却需要完整的一个二维数组。若图中顶点数过多会导致二维数组的大小剧增从而占用大量的内存空间。
而根据实际情况可以分析得图中的顶点并不是任意两个顶点间都会相连不是都需要对其边上权重进行存储。那么存储的邻接矩阵实际上会存在大量的0。虽然可以通过稀疏表示等方式对稀疏性高的矩阵进行关键信息的存储但是却增加了图存储的复杂性。
因此为了解决上述问题一种可以只存储相连顶点关系的邻接表应运而生。
邻接表
在邻接表中图的每一个顶点都是一个链表的头节点其后连接着该顶点能够直接达到的相邻顶点。相较于无向图有向图的情况更为复杂因此这里采用有向图进行实例分析。 在邻接表中每一个顶点都对应着一条链表链表中存储的是顶点能够达到的相邻顶点。存储的顺序可以按照顶点的编号顺序进行。比如上图中对于顶点B来说其通过有向边可以到达顶点A和顶点E那么其对应的邻接表中的顺序即B-A-E其它顶点亦如此。
通过邻接表可以获得从某个顶点出发能够到达的顶点从而省去了对不相连顶点的存储空间。然而这还不够。对于有向图而言图中有效信息除了从顶点“指出去”的信息还包括从别的顶点“指进来”的信息。这里的“指出去”和“指进来”可以用出度和入度来表示。 入度有向图的某个顶点作为终点的次数和。 出度有向图的某个顶点作为起点的次数和。 由此看出在对有向图进行表示时邻接表只能求出图的出度而无法求出入度。这个问题很好解决那就是增加一个表用来存储能够到达某个顶点的相邻顶点。这个表称作逆邻接表。
逆邻接表
逆邻接表与邻接表结构类似只不过图的顶点链接着能够到达该顶点的相邻顶点。也就是说邻接表时顺着图中的箭头寻找相邻顶点而逆邻接表时逆着图中的箭头寻找相邻顶点。 邻接表和逆邻接表的共同使用下就能够把一个完整的有向图结构进行表示。可以发现邻接表和逆邻接表实际上有一部分数据时重合的因此可以将两个表合二为一从而得到了所谓的十字链表。
十字链表
十字链表似乎很简单只需要通过相同的顶点分别链向以该顶点为终点和起点的相邻顶点即可。 但这并不是最优的表示方式。虽然这样的方式共用了中间的顶点存储空间但是邻接表和逆邻接表的链表节点中重复出现的顶点并没有得到重复利用反而是进行了再次存储。因此上图的表示方式还可以进行进一步优化。
十字链表优化后可通过扩展的顶点结构和边结构来进行正逆邻接表的存储下面的弧头可看作是边的箭头那端弧尾可看作是边的圆点那端 data用于存储该顶点中的数据 firstin指针用于连接以当前顶点为弧头的其他顶点构成的链表即从别的顶点指进来的顶点 firstout指针用于连接以当前顶点为弧尾的其他顶点构成的链表即从该顶点指出去的顶点 边结构通过存储两个顶点来确定一条边同时通过分别代表这两个顶点的指针来与相邻顶点进行链接 tailvex用于存储作为弧尾的顶点的编号 headvex用于存储作为弧头的顶点的编号 headlink 指针用于链接下一个存储作为弧头的顶点的节点 taillink 指针用于链接下一个存储作为弧尾的顶点的节点 以上图为例子对于顶点A而言其作为起点能够到达顶点E。因此在邻接表中顶点A要通过边AE即边04指向顶点E顶点A的firstout指针需要指向边04的tailvex。同时从B出发能够到达A所以在逆邻接表中顶点A要通过边AB即边10指向B顶点A的firstin指针需要指向边10的弧头即headlink指针。依次类推。
十字链表采用了一种看起来比较繁乱的方式对边的方向性进行了表示能够在尽可能降低存储空间的情况下增加指针保留顶点之间的方向性。具体的操作可能一时间不好弄懂建议多看几次上图弄清指针指向的意义明白正向和逆向邻接表的表示。 10 总结
数据结构博大精深没有高等数学的讳莫如深也没有量子力学的玄乎其神但是其在计算机科学的各个领域都具有强大的力量。本文试图采用图解的方式对九种数据结构进行理论上的介绍但是其实这都是不够的。
即便是简单的数组、栈、队列等结构在实际使用以及底层实现上都会有许多优化设计以及使用技巧这意味着还需要真正把它们灵活的用起来才能够算是真正意义上的熟悉和精通。但是本文可以作为常见数据结构的一个总结当你对某些结构有些淡忘的时候不妨重新回来看看。
