数据结构教程
数据结构教程,数据结构来源,1968 年,美国 Donald E. Knuth 教授在《计算机程序设计艺术》第一卷《基本算法》中系统阐述了数据的逻辑结构和存储结构及其操作,开创了数据结构课程体系。
什么是算法
什么是算法,算法是什么,算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。
数据结构由来
数据结构作为一门独立的课程在国外 1968 年开始设立。在这之前,它的某些内容曾在其他课程,如表处理语言中所有阐述。
数据结构概念
有关数据结构的相关概念,主要包括数据、数据元素、数据项、数据对象以及数据结构等。
数据逻辑结构
数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构,以及对数据的各种操作。因此,主要有三个方面的内容:
数据物理结构
数据的物理结构在很多书中也叫做存储结构,是指数据的逻辑结构在计算机中的存储形式。
常见的数据结构
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等。
时间复杂度
算法复杂度是指算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。
空间复杂度
一个算法的空间复杂度(Space Complexity) S(n) 定义为该算法所耗费的存储空间,它也是问题规模 n 的函数。渐近空间复杂度也常常简称为空间复杂度。
数组详解
数组是在程序设计中,为了处理方便, 把具有相同类型的若干元素按无序的形式组织起来的一种形式,是用于储存多个相同类型数据的集合。通过使用数组,可以在很大程度上缩短和简化程序代码,从而提高应用程序的效率。
数组操作
数组的常用操作主要包括,数组的初始化、数组元素的插入、数组元素的删除、数组追加元素、获取元素、数组排序、数组倒置以及数组的遍历等。
链表详解
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表操作
链表的常用操作主要包括,链表的创建、遍历、判断是否为空、获取链表的长度、在链表指定的位置插入节点、删除链表指定位置的元素以及给链表排序。
栈详解
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。
栈操作详解
栈的常用操作主要包括,栈的初始化、判断是否为空、元素入栈、元素出栈、遍历以及给清空栈元素等。
队列详解
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作
队列操作详解
队列的常用操作主要包括,队列的初始化、判断是否为空、元素入队列、元素出队列、遍历以及给清空队列元素等。
递归详解
递归就是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
递归求阶乘
N 的阶乘就是从 1 一直乘以到 N 本身,比如 5 的阶乘就是 `5! = 5*4*3*2*1`,6 的阶乘就是
递归求和
求 1 到 N 的和就是从 1 一直加到 N 本身,比如求 1 到 5 的和就是 `SUM(5) = 5+4+3+2+1`,6 的和就是 `SUM(6) = 6+5+4+3+2+1`。同时,我们可以看出,其实 6 的和也可以简化为 `SUM(6) = 6 + SUM(5)`。
递归求斐波那契数列
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……
递归解汉诺塔
汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着 64 片黄金圆盘。
树详解
树由 n(n>=1) 个有限结点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
二叉树操作详解
二叉树的常用操作主要包括,二叉树的创建、二叉树的先序遍历、中序遍历和后续遍历等。