附注说明:上图中删完尾节点之后,新链表的尾节点下标应为n-1。不过由于作图时只做了尾节点,故用图中的n2节点代替。
删除尾节点的代码如下:
③. 删除非头尾节点,如图
删除非头尾节点的代码如下:
4.查询节点:在链表中找到你想要找的那个节点。此操作是根据数据域的内容来完成的。查询只能从表头开始,当要找的节点的数据域内容与当前不相符时,只需让当前节点指向下一结点即可,如此这样,直到找到那个节点。
附注:此操作就不在这用图和代码说明了。
5.修改节点:修改某个节点数据域的内容。首先查询到这个节点,然后对这个节点数据域的内容进行修改。
附注:同上
ok,链表的几种操作介绍完了,接下来我们来总结一下链表的几个特点。
链式存储结构的特点:
1.易插入,易删除。不用移动节点,只需改变节点中指针的指向。
2.查询速度慢:每进行一次查询,都要从表头开始,速度慢,效率低。
扩展阅读
链表:http://public.whut.edu.cn/comptsci/web/data/512.htm
第二节 树形存储结构
所谓树形存储结构,就是数据元素与元素之间存在着一对多关系的数据结构。在树形存储结构中,树的根节点没有前驱结点,其余的每个节点有且只有一个前驱结点,除叶子结点没有后续节点外,其他节点的后续节点可以有一个或者多个。
如下图就是一棵简单的树形结构:
说到树形结构,我们最先想到的就是二叉树。我们常常利用二叉树这种结构来解决一些算法方面的问题,比如堆排序、二分检索等。所以在树形结构这节我只重点详解二叉树结构。那么二叉树到底是怎样的呢?如下图就是一颗简单的二叉树:
附注:有关树的概念以及一些性质在此不做解释,有意者请到百科一览。
二叉树的类型描述如下:
二叉树的操作:创建节二叉树,创建节点,遍历二叉树,求二叉树的深度。
1.创建二叉树:声明一棵树并为其申请存储空间。
2.创建节点:除根节点之外,二叉树的节点有左右节点之分。
创建节点的代码如下:
3.遍历二叉树:分为先序遍历、中序遍历、后续遍历。
①.先序遍历:若二叉树非空,则依次执行如下操作:
(1) 访问根结点;
(2) 遍历左子树;
(3) 遍历右子树。
如图:
先序遍历的代码如下:
②.中序遍历:若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)访问根结点;
(3)遍历右子树。
如图:
中序遍历的代码如下:
③.后续遍历:若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)遍历右子树;
(3)访问根结点。如图:
后续遍历的代码如下:4.求二叉树的深度:树中所有结点层次的最大值,也称高度。二叉树的深度表示如下图:
求二叉树深度的代码如下:好了,二叉树的几种操作介绍完了。
拓展阅读
二叉树:http://student.zjzk.cn/course_ware/data_structure/web/DOWNLOAD/%CA%FD%BE%DD%BD%E1%B9%B9%D3%EB%CB%E3%B7%A82.htm
赫夫曼编码:http://blog.csdn.net/fengchaokobe/article/details/6969217
第三节 图型存储结构
所谓图形结构,就是数据元素与元素之间的关系是任意的,任意两个元素之间均可相关,即每个节点可能有多个前驱结点和多个后继结点,因此图形结构的存储一般是采用链接的方式。图分为有向图和无向图两种结构,如下图
通过图,我们可以判断两个点之间是不是具有连通性;通过图,我们还可以计算两个点之间的最小距离是多少;通过图,我们还可以根据不同的要求,寻找不同的合适路径。
1.图的结构有好几种,在实际应用中需根据具体的情况选择合适的结点结构和表结构。常用的有数组结构、邻接表。
①.数组结构
数组结构的类型描述如下:
附注:当前图为无向图时,图中某两个顶点VA和VB构成一条边时,其权值可表示为EdgeType arc[VA][VB];当前图为有向图时,图中某两个顶点VA和VB构成一条边时,并且是由VA指向VB,其权值可表示为EdgeType arc[VA][VB],如果是由VB指向VA,其权值可表示为EdgeType arc[VB][VA]。
②.邻接表
邻接表的类型描述如下:
2.图的遍历:从图中的某一节点出发访问图中的其余节点,且使每一节点仅被访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和求路径等算法的基础。图的遍历分为深度优先遍历和广度优先遍历,且它们对无向图和有向图均适用。
①. 深度优先遍历
定义说明:假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点V为初始出发点,则深度优先遍历可定义如下:首先访问出发点V,并将其标记为已访问过;然后依次从V出发搜索v的每个邻接点W。若W未曾访问过,则以W为新的出发点继续进行深度优先遍历,直至图中所有和源点V有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。
深度遍历过程如下图:
②. 广度优先遍历
定义说明:假设从图中某顶点V出发,在访问了V之后一次访问V的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点,重复上述过程,直至图中所有顶点都被访问到为止。换句话说,广度优先遍历图的过程是以V为起点,由近至远,依次访问和V有路径相同且路径长度为1,2,...的顶点。广度遍历过程如下图:
扩展阅读
最小生成树:Prim算法,Kruskal算法
最短路径:Dijkstra算法,Floyd算法
第四节 结束语
想想,写写,画画......
相关推荐
数据结构与算法 数据结构与算法详解 学习编程基础知识储备
数据结构与算法学习辅导及习题详解.张乃孝版
数据结构与算法学习辅导及习题详解.张乃孝版.04年10月
算法与数据结构课件、习题、习题详细解答;这将对你的专业学习提供极大的帮助
几种压缩算法详解几种压缩算法详解几种压缩算法详解几种压缩算法详解几种压缩算法详解几种压缩算法详解几种压缩算法详解几种压缩算法详解几种压缩算法详解几种压缩算法详解几种压缩算法详解几种压缩算法详解几种压缩...
1.1 数据结构的基本概念和术语 1.1.1 引言 1.1.2 数据结构有关概念及术语 1.1.3 数据结构和抽象数据类型(ADT) 1.2 算法描述与分析 1.2.1 什么是算法 1.2.2 算法描述工具——C语言 1.2.3 算法分析技术初步...
数据结构与算法 学习辅导及习题详解 张乃孝版
详解了一些经典算法和数据结构,希望对大家有帮助,鄙人能力有限,代码出错的地方请大家多多指正
本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系,难点是算法复杂度的分析方法。 需要达到<识记>层次的基本概念和术语有:数据、数据元素、数据项、数据结构。特别是数据结构的...
数据结构 链式存储结构基本算法,我自己全部实现过了,没问题。
数据结构18种算法数据结构18种算法数据结构18种算法数据结构18种算法数据结构18种算法数据结构18种算法数据结构数据结构18种算法数据结构18种算法18种算法数据结构18种算法
严蔚敏数据结构kmp算法详解PPT学习教案.pptx
资源名称:数据结构与算法视频课程(59集)资源目录:【】mysql视频教程第41讲存储过程【】数据结构与算法_1.10算法的评价【】数据结构与算法_1.1编程的灵魂:数据结构 算法【】数据结构与算法_1.2算法的作用:猜...
数据结构是计算机存储、组织数据的...数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
数据结构与算法分析——C++语言描述第三版源码 数据结构算法C++版本
数据结构与算法学习辅导及习题详解
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
详解数据结构算法与C++ 有C++的数据结构算法的详解