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