基本数据结构与算法

《基本数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基本数据结构与算法一、数据结构的基本概念1、数据信息载体，能够被计算机识别、存储和加工处理。可以是数值数据（整数、实数），也可以是非数值数据（声音、图像等）。2、数据项是数据的具有独立含义的不可分割的最小标识单位，如成绩表中学号、姓名。3、数据元素（又称结点、记录）一个数据元素由若干数据项组成，是数据的基本单位，通常作为一个整体进行考虑和处理。4、数据对象具有相同性质的数据元素的集合。是数据的一个子集。5、数据结构相互之间存在着一种或多种关系的数据元素的集合。（1）研究内容◆数据的逻辑结构：各数据元素之间的逻辑关系。◆数据的存储结构：各数据元素在计算机中的存储

2、关系。◆对各种数据结构进行的运算：添加、删除、排序等。（2）研究目的一是提高数据处理的速度；二是尽量节省在数据处理过程中所占用的计算机存储空间。（3）常见的数据结构类型◆集合：元素间为松散的关系（属于关系）。◆线性结构：元素间为一对一关系。◆树形结构：元素间为一对多关系。特点：结点间具有分层次的连接关系。◆图状结构：元素间为多对多关系。特点：结点间的连结是任意的，数据元素之间存在多个对多个关系。（4）包含信息◆表示数据元素的信息。◆表示各数据元素之间的前后件关系。（5）有关概念◆结点：组成数据结构的数据元素称为一个结点。◆前后件关系：数据元素之间的固有关系可以

3、用前后件关系（前驱与后继关系）描述。◆根节点：在数据结构中，没有前件的节点称为根结点。◆叶子节点：没有后件的结点称为终端结点或叶子结点。6、数据结构的逻辑结构（1）数据的逻辑结构数据之间的相互关系，被称为数据的逻辑结构。（2）逻辑结构分类根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据逻辑结构分为：线性结构与非线性结构。（3）线性结构数据元素之间存在一个对一个的前后次序关系。◆特点：有且只有一个根结点每个结点最多有一个前件，也最多有一个后件。（4）非线性结构一个数据结构如果不是线性结构，则称之为非线性结构。◆特点：数据元素的前后关系复杂，一个结点

4、既可以有多个前件，也可以有多个后件，如集合、树型、图形结构属于非线性结构。◆集合结构：数据元素间的关系是属于同一个集合。◆树型结构：数据元素之间存在一个对多个的关系。◆图形结构：数据元素之间存在多个对多个的关系。7、数据结构的存储结构数据的逻辑结构在计算机存储空间中的存放形式。数据存储结构中不仅存放各数据元素信息，还存放前后件关系的信息。（1）特点存储结构研究的是逻辑结构用计算机语言实现，依赖于计算机语言。一种数据结构可以根据需要采用多种不同的存储结构，常用的存储结构有顺序、链接与索引等存储方式。数据的存储结构不同，解决问题的方法就有所不同，数据处理的效率也是

5、不同的。（2）实现方式◆顺序存储方式逻辑上相邻的元素存储在物理位置相邻的存储单元中；主要用于线性结构；通常借助于数组来实现。◆链式存储方式对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示；通常借助于指针类型实现。链式存储方式特点：每个结点由两部分组成，一部分存放数据，另一部分存储指向前件或后件结点的指针域；逻辑上相邻的结点物理上不必相连；数据运算（插入和删除等）灵活。◆索引存储方法和散列存储方法8、数据的运算在数据的逻辑结构上定义的操作算法。◆常见运算：插入、删除、查找、排序和更新等。◆分类：加工型运算，运算改变了数据结构的值；引

6、用型运算，不改变值，只查询或求得结构值。◆注意：数据的运算定义在逻辑结构上，而具体的实现都要在数据的存储结构上即计算机内进行。9、数据类型及其分类数据类型是一个值的集合和定义在这个值集上的一组操作的总称。分类：（1）非结构的原子类型原子类型的值是不可分解的。如：程序设计语言中的基本类型（整型，实型，字符型，指针类型和空类型）。（2）结构类型结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。二、算法及算法分析1、算法的基本概念（1）定义为解决某个特定问题而采取的确定且有限的步骤。◆用计算机解决一个具体问题时，大

7、致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型；然后设计一个解此数学模型的算法；最后采用一种计算机语言编出程序，调试、修改直至得到最终答案。（2）算法特性◆有穷性：一个算法应包含有限个操作步骤，而且每一步都应在有限时间内完成。◆确定性：算法中每一条指令必须有确切的含义，确保不会产生二义性。◆可行性：算法中指定的操作都是可以通过基本运算执行有限次后实现。◆输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象集合。◆输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。2、算法的基本要素及描述（1）算法基本要素构成◆对

8、数据对象的运算和操作：算术运算，加、减