文档介绍：数据结构和算法设计与分析
谈到计算机方面的专业课程,我觉得数据结构算是一门必不可少的课了,它是计算机从业和研究人员了解、开发及最大程度的利用计算机硬件的一种工具。数据结构与算法分析是两门紧密联系的课程,算法要靠好的数据结构来实现,二者的关系是密不可分的,谈到算法不得不讲数据结构,谈数据结构也不可避免的要了解算法,好的算法一定有一个好的数据结构,很多算法实际上是对某种数据结构实行的一种变换,研究算法也就是研究在实行变换过程中数据的动态性质。这两门课程分别是我在大二和研一的时候学的,因为它们密切的联系,这里将其放在一起总结如下。
什么是数据结构呢?研究数据的逻辑结构和存储结构(物理结构)以及它们之间的关系,且为该结构定义相应的运算设计相应的算法。这里的数据是指可输入到计算机能被程序处理的符号的集合。其中,数据的逻辑结构是指数据之间逻辑关系的描述,逻辑结构的分类有线性结构、树形结构和图结构。数据的存储结构是指数据在计算机中存储结构,也称为物理结构,它有4类基本的存储映射方法:;;;。在程序设计语言中,数据结构直接反映在数据类型上,比如一个整型变量就是一个节点,根据类型给他分配内存单元。抽象数据类型:一组值以及在这些值上定义的操作集合,它是描述数据结构的一种理论工具,其特点是把数据结构作为独立于应用程序的一种抽象代数结构。
线性表结构:由一系列元素组成的有序的序列,除了第一个元素和最后一个元素外,每个元素都只有一个直接前趋和直接后继,元素的个数称为线性表的长度。它的存储方式有顺序存储和链式存储。顺序存储方式它的优点是存储单元是连续的,适合快速访问元素内容,链表的特点是动态申请内存空间,并通过指针来链接结点,按照线性表的前驱关系把一个个结点链接起来,这样可以动态地根据需要分配内存空间,经常用于插入新结点或删除节点的需要,链表还可以根据结点中指针个数分为单链表、双链表、循环链表等。在线性表结构中有两类特别的线性表:栈和队列。栈是一种限制访问端口的线性表,常称为后进先出表。正是这种特殊的性质使得栈的用途非常广泛,比如在计算表达式的值时处理运算符的先后次序,另外一个大的用处就是递归了,hanoi 塔就是最典型的用了递归的思想,在算法中,也有很多运用递归思想的例子。队列也属于限制访问点的线性表,它的特点就是加入和删除元素都只能在队列的一端进行,即队列首出,队列尾进,最大的特点是先来先服务,先进先出。因
为这个特点,队列常被用作消息缓冲器。
在算法设计中,顺序表主要用于检索,而利用栈中的递归思想在算法中则应用非常广泛,如递归排序,分治算法等。
树结构:是一种非常重要的非线性数据结构,它是由一个根结点和若干叶结点组成的树状结构,除了根结点每个结点只能有一个父节点,可以有若干子结点,若干个树结构还可以构成森林,树的存储结构也分为顺序存储和链式存储,最典型的是左孩子右兄弟法。在树结构中比较重要的算法就是周游(遍历)树,有先根次序、后根次序以及中根次序。树结构中有几类非常重要的特殊树结构,如二叉树,B树,B+树等,其中,二叉树应用最为广泛。
二叉树:是指每个结点最多有两个子结点的树结构,具体细分,根据叶子结点的特性可分为满二叉树、完全二叉树等。二叉树的遍历也分为深度优先和广度优先。另外,二叉树有几条非常重要的