数据结构：空间复杂度成果

在对算法进行空间复杂度分析时，只需考查辅助变量所占用的空间。为了实现递归需要一个递归栈，递归算法的空间复杂度需要根据递归深度来确定。例1.8用C++语言描述的数组求和算法如下，计算其空间复杂度。A.正确性和空间复杂度B.易读性和健壮性C.数据复杂性和程序复杂性D.时间复杂度和空间复杂度5.数据采用链式存储结构时，要求（）。

理论教育 2023-11-01

算法特性-数据结构-数据结构

算法是对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示计算机的一个或多个操作。例1.3设计一个算法，计算表示取整）。两者的区别是，算法必须满足有穷性，而程序可以不满足有穷性。

理论教育 2023-11-01

数据结构堆分配存储表示

堆分配存储表示用一组地址连续的存储单元存放串字符序列，它们的存储空间可以在程序执行过程中动态分配。用pos存储连续相同字符构成的串的开始位置，max存储连续相同字符构成的串的最大长度，初始值置为0，用C++描述的算法如下：

理论教育 2023-11-01

数据结构|串的基本概念与子串定位算法

an"，其中S是串名，双引号中的字符序列是串的值，ai代表一个字符，可以是字母、数字或其他符号。串中所包含的字符数量称为串的长度。例如，""是长度为1的空格串，""是长度为0的空格串。当且仅当两个串的长度相等，且其对应位置上的字符均相等时，两个串相等。串中任意个连续字符组成的子序列被称为该串的子串。子串在主串中的位置用子串的首字符在主串的位置来表示。用C++描述的算法如下：

理论教育 2023-11-01

数据结构：排序的基本概念

若具有相同关键字的数据元素之间的相对次序发生变化，则称这种排序方法是不稳定的。内部排序是外部排序的基础，本章讨论内部排序方法。

理论教育 2023-11-01

数据结构:哈希表基本概念

哈希表又被称为散列表，是一种将元素的存储位置与该元素的关键字之间建立对应关系的线性表存储结构。这种情况被称为哈希冲突。根据抽屉原理，冲突是不可能完全避免的。为此在设计哈希表时应当尽量减少冲突的发生，在冲突发生时应寻找解决冲突的方法。

理论教育 2023-11-01

数据结构：查找概念详解

在介绍各种查找算法之前，本节先介绍一些基本概念。查找表是同一类型数据元素（或记录）构成的集合，与4种数据关系中的集合结构对应。由于集合中数据元素之间存在着完全松散的关系，因此，查找表往往要借助其他数据结构来实现相关算法。查找是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素的过程。

理论教育 2023-11-01

数据结构：数据类型与抽象数据类型

抽象数据类型中的数据对象、数据操作的声明与数据对象的表示、实现相互分离。抽象数据类型有两个重要特征：数据抽象和数据封装。n元组的抽象数据类型定义如下：抽象数据类型可通过基本数据类型来表示和实现，即利用处理器中已经存在的数据类型说明新的结构类型，用已经实现的操作组合实现新的操作。本书采用C++中的类作为抽象数据类型的描述工具。

理论教育 2023-11-01

数据结构：有序表ADT的描述

有序表的抽象数据类型描述如下：有序表中数据元素的逻辑关系与线性表中数据元素的逻辑关系完全相同，可以采用顺序表和链表进行存储。用C++语言描述的算法如下：例2.13已知一个单循环链表存放一组按值非递减的数据元素，设计一个插入元素x的算法，插入后链表仍然按值非递减排列。

理论教育 2023-11-01

时间复杂度-数据结构

例1.5已知n为正整数，计算20+21+22+…，其语句频度为该程序段的时间复杂度为O，通常称为对数阶。例1.6已知选择排序算法如下，分析其时间复杂度。其语句频度为时间复杂度只需要取最高阶的项，并忽略常数和系数。该算法的时间复杂度为O。该算法是一个三重循环，基本运算为A[i][k]×B[k][j]，语句频度为该算法的时间复杂度为O。不同的时间复杂度存在如下关系：

理论教育 2023-11-01