数据结构（C++版）王红梅.pdfVIP

数据结构 （C++版）王红梅 第⼀章 绪论 ⼀、数据结构 1、数据的逻辑结构可以分为 （1）线性结构 ⼀对⼀ 有且只有⼀ 开始和⼀ 终端结点，并且所有结点都最多只有⼀ 直接前驱和⼀ 直接后继 例如 ：线性表、栈、队列、串 （字符串 数组 ⼴义表）。 （2）⾮线性结构 ⼀对多 ⼀ 结点可能也有多 直接前驱和直接后继 例如 ：树形结构、图形结构。 数据结构从逻辑上分为四类 ： （1）集合 ：数据元素之间就是 “属于同⼀ 集合” （2）线性结构 ：数据元素之间存在着⼀对⼀的线性关系 （3）树结构 ：数据元素之间存在着⼀对多的层次关系 （4）图结构 ：数据元素之间存在着多对多的任意关系。 2、数据的存储结构 （1）顺序存储结构 ：⽤⼀组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表⽰。 （2）链接存储结构 ：⽤⼀组任意的存储单元存储数据元素，数据元素之间的逻辑关系⽤指针来表⽰ 。 3、数据的运算 ：检索、排序、插⼊、删除、修改等 ⼆、算法 1、算法的特性 ：输⼊、输出、有穷性、确定性、可⾏性。 2、算法的描述⽅法 ：⾃然语⾔、流程图、程序代码、伪代码 （类语⾔）。 3、算法设计的要求：正确性、可读性、健壮性 （鲁棒性）、抽象分级、⾼效性。 4、算法分析 ： （1）算法所耗费的时间 算法运⾏时间 = ∑ 每条语句的执⾏次数 （每条语句频度） × 该语句执⾏⼀次所需的时间 时间复杂度 ：算法所需时间的度量 （2）算法执⾏过程中所耗费的存储空间 空间复杂度 ：算法所需存储空间的度量 S （n） = O （f （n）） 第⼆章 线性表 2.1 线性表的逻辑结构 1、线性表简称表，是n （n=0） 具有相同类型的数据元素的有序列表，线性表中数据元素的 数称为线性表的长度。长度等于零时称为 空表，⼀ ⾮空表通常记为 ： L = （a1，a2，a3，...，an） 其中，ai 称为数据元素，下脚标i表⽰该元素在线性表中的位置或序号，称元素 ai 位于表的第i 位置，或称 ai 是表中的第 i 元素。a1 称 为第⼀ 元素，an 称为最后⼀ 元素，任意⼀对相邻的元素 ai- 1 和 ai 之间存在序偶关系 ai- 1,ai，且 ai- 1 称为 ai 的前驱，ai 称为 ai- 1 的后继。a1 ⽆前驱，an ⽆后继，其他每⼀ 元素有且仅有⼀ 前驱和⼀ 后继。 2、线性表的特性 ：有限性、相同性、顺序性 2.2 线性表的顺序存储结构及实现 1、线性表的顺序存储结构称为顺序表 2、顺序表的实现 （1）构造函数 ①⽆参构造函数 将顺序表长度length初始化为0 SeqListDataType::SeqList() { length = 0; } ②有参构造函数 template class DataType SeqListDataType::SeqList(DataType a ] , int n) { if (n MaxSize) { throw参数⾮法; } for (i = 0 ; i n ; i++ ) { data i] = a i] ; } length = 0 ; } （2）求线性表的长度 返回成员变量length的值 （3）查找操作 ①按位查找 时间复杂度为O （1） template class DataType DataType SeqListDataType::Get(