文档介绍：该【数据结构概念总结 】是由【Alone-丁丁】上传分享，文档一共【17】页，该文档可以免费在线阅读，需要了解更多关于【数据结构概念总结 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构概念总结
数据结构(C语言版)
第一章:绪论
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的科学。
数据(data)是对客观事物的符号表示,在计算机科学中是指所有以输入到计算机中并被计算机程序处理的符号的总称。
数据元素(dataelement)是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
数据对象(dataobject)是性质相同的数据元素的集合,是数据的一个子集。
数据结构(datastructure)是相互之间存在一种或多种特定关系的数据元素的集合。
根据数据结构之间关系的不同特性,通常有下列4类基本结构:集合、线性结构、树形结构、图状结构或网状结构。
抽象数据类型(ADT):是指一个数学模型以及定义在该模型上的一组操作,有“数据抽象”和“数据封装”两个重要特性。
算法(algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表
第三章:栈和队列
栈是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端有其特殊含义称为栈顶,相应地,表头端称为栈底。栈的修改是按后进先出的原则进行的,因此又称后进先出表。
队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素,在队列中,允许插入的一端称做队尾,允许删除的一端称做队头。
第四章:串
串(string)是由零个或多个字符组成的有限序列。串中任意个连续的字符组成的子序列称该串的子串,通常称字符在序列中的序号为该字符在序列中的序号为该字符的在串中的位置。
称两个串是相等的,当且仅当这两个串的值相等。也就是说,只有当两个串的长度相等,并且各个对应位置的字符都相等时才相等。
第六章:树与二叉树
树(tree)是指n(n>=0)个结点的有限集,在任意一棵非空树中:1)有且仅有一个特定的称为根。2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集,其中每一个集合本身又是一棵树。
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度。度为0的结点称为叶子或终端结点。树的度是树内各结点的度的最大值。结点的子树的根称为该结点的孩子,相应的该结点称为孩子的双亲。同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点。反之,以某结点为根的子树中的任一结点都称为该结点的子孙。
结点的层次从根开始定义起,根为第一层,根的孩子为第二层。若某结点在第l层,则其子树在第l+1层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度或高度。
如果将树中结点的各种子树看成是从左到右是有次序的,则称该树为有序树,否则称为无序树。
森林(forest)是m(m>0)棵互不相交的树的集合。
二叉树(BinaryTree)是另一种树型结构,它的特点是每个结点至多只有两棵子树,并且二叉树的子树有左右之分,其次序不能任意颠倒。
一个深度为k且有2K-1个结点的二叉树称为满二叉树。深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。
遍历二叉树:指按某条搜索路径巡访树上每个结点,使得每个结点均被访问一次,而且仅被访问一次。有先序遍历、中序遍历、后序遍历三种。
若结点有左子树,则其lchild(rchild)域指向指示其左(右)孩子,否则令lchild(rchild)域指示其前驱(后继),这种结点构成的二叉链表做为二叉树的存储结构称为线索链表。
从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。树的路径长度是从树根到每一个结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和。
假设有n个权值{w1,w2,……,wn},试构造一棵有n个叶子结点的二叉树,每个叶子结点带树为wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树或赫夫曼树。
第七章:图
在图中的数据元素通常称做顶点,<v,w>表示从v到w的一条弧,且称v为弧尾,称w为弧头,此时称图为有向图,若<v,w>表示v和w之间的一条边,此时的图称为无向图。
有n*(n-1)/2条边的无向图称为完全图。具有n(n-1)条弧的有向图称为有向完全图,有很少条边或弧的图称为稀疏图,反之称为稠密图。有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权,这种带权的图称为网。
顶点v的度是和v相关联的边的数目,记为TD(V)。
无向图G=(V,{E})中从点v到顶点v’的路径是一个顶点序列,路径的长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。序列中不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。
在无向图G中,如果从顶点v到顶点v’有路径,则称v和v’是连通的。如果对于图中任意两个顶点vi、vj∈V,vi和vj都是连通的,则称G是连通图。所谓连通分量指的是无向图中的极大连通子图。
在有向图G中,如果对于每一对vi、vj∈V,vi≠vj,从vi到vj和从vj到vi都存在路径,则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。如果在一棵生成树上添加一条边,必定构成一个环。一棵有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和小于n-1条边,则是非连通图,如果它多于n-1条边,则一定有环。但是,有n-1条边的图不一定是生成树。
如果一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向树。一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。
图的存储结构有邻接矩阵、邻接表、逆邻接表以及十字链表等。
图的遍历:指从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。
通常有两条遍历图的路径:
深度优先搜索:类似于树的先序遍历,假设从图中某顶点v出发,在访问了v之后依次从v的未被访问的邻接点出发深度优先遍历图,直到图中所有和v有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点做为起始点,重复上述过程,直至图中所有顶点都被访问到为止。
广度优先搜索:类似于村的层序遍历,假设从图中某顶点v出发,在访问了v之后依次访问它们的邻接点,并使先被访问的顶点的邻接点先于后访问的顶点的邻接点,直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点,重复上述过程,直到图中所有顶点都被访问到为止。
假若在删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的边通分量,则称顶点v为该图的一个关节点。一个没有关节点的图称为重连通图。若在连通图上至少删去k个顶点才能破坏图的连通性,则称此图的
连通度为k。
对于无向图来说,若深度优先搜索过程中遇到回边,则必定存在环,而对于有向图来说,这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。
拓扑排序(TopologicalSort):指由某个集合上的一个偏序得到该集合上的一个全序。
AOV-网:指用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网。
AOE-网:指用边表示活动的网,是一个带权的有向无环图,其中,顶点表示事件弧表示活动,权表示活动持续的时间,通常一个AOE-网可用来估算工程的完成时间。
在正常的情况(无环)下,网中只有一个入度为零的点,称做源点和一个出度为零的点,称为汇点。
在AOE-网点,路径长度最长的路径叫做关键路径,关键路径上的所有活动都是关键活动。
第九章:查找
查找表(SearchTable):是由同一类型的数据元素构成的集合。若对查找表只作查找操作,则称此类查找表为