数据结构知识点总结

第一章

数据结构概念——数据结构，数据元素，数据项，数据类型，抽象数据类型，算法，等。

数据结构定义——指互相有关联的数据元素的集合，用D_S=( D, S )

或 S=( D, R) 表示。

数据结构内容——数据的逻辑结构、存储结构和运算

算法效率指标——时间效率（时间复杂度）和空间效率（空间复杂度）

总结：数据的逻辑结构和存储结构

数据的逻辑结构是数据的机外表示，数据的存储

结构是数据的机内表示。

(2) 一种数据的逻辑结构可以用多种存储结构来存储。

(3) 数据结构的基本操作是定义（存在）于逻辑结构，计算机程序设计过程中实现于存储结构。

(4) 采用不同的存储结构，其数据处理的效率往往是不同的。

数据结构？有限个同构数据元素的集合，存在着一定的结构关系，可进行一定的运算。

算法--是对特定问题求解步骤的一种描述，是指令的有限序列。

算法有5个基本特性：

有穷性、确定性、可行性、输入和输出

第二章

1. 数据的逻辑结构是指数据元素之间的逻辑关系，

是用户按使用需要建立的。对

2. 线性表的逻辑结构定义是唯一的，不依赖于计算机。对

3. 线性结构反映结点间的逻辑关系是一对一的。对

4. 一维向量是线性表，但二维或N维数组不是。错 5. “同一数据逻辑结构中的所有数据元素都具有相同的

特性”是指数据元素所包含的数据项的个数都相等。错

插入概率p(i)=1/(n+1) ，删除概率q(i)=1/n

插入操作时间效率（平均移动次数）2)1(11)1(1111ninninpEniniiis删除操作时间效率（平均移动次数）

21)(1)(11ninninqEniniidl线性表顺序存储结构特点：逻辑关系上相邻的两个元素

在物理存储位置上也相邻；

优点：可以随机存取表中任一元素;无需为表示表中元素

1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

◆ 数据：指能够被计算机识别、存储和加工处理的信息载体。

◆ 数据元素：就是数据的基本单位，在某些情况下数据项组成。

◆ 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

◆ 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

◆ 逻辑结构：指各数据元素之间的逻辑关系。

◆ 存储结构：就是数据的逻辑结构用计算机语言的实现。

◆ 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。

◆ 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

◆

例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。

那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢?

是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?

这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。(所以各位赶快学C语言吧)。

最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

第1章 绪论

1.1 数据结构的基本概念

数据元是数据的基本单位，一个数据元素可由若干个数据项完成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据类型是一个值的集合和定义在此集合上一组操作的总称。

• 原子类型：其值不可再分的数据类型

• 结构类型：其值可以再分解为若干成分（分量）的数据类型

• 抽象数据类型：抽象数据组织和与之相关的操作

抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。通常用（数据对象、数据关系、基本操作集）这样的三元组来表示。

#关键词：数据，数据元素，数据对象，数据类型，数据结构

数据结构的三要素：

1. 逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，独立于计算机。分为线性结构和非线性结构，线性表、栈、队列属于线性结构，树、图、集合属于非线性结构。

2. 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构，包括数据元素的表示和关系的表示，依赖于计算机语言，分为顺序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、增加、删除快）。

3. 数据的运算：包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

1.2 算法和算法评价

算法是对特定问题求解步骤的一种描述，有五个特性：有穷性、确定性、可行性、输入、输出。一个算法有零个或多个的输入，有一个或多个的输出。

时间复杂度是指该语句在算法中被重复执行的次数，不仅依赖于问题的规模n，也取决于待输入数据的性质。一般指最坏情况下的时间复杂度。

空间复杂度定义为该算法所耗费的存储空间。算法原地工作是指算法所需辅助空间是常量，即O(1)。

数据结构 知识点总结

一、数据结构基础概念

数据结构是指数据元素之间的关系，以及对数据元素进行操作的方法的总称。数据结构是计算机科学中非常基础的概念，它为计算机程序的设计和实现提供了基础架构。数据结构的研究内容包括数据的逻辑结构、数据的存储结构以及对数据进行操作的算法。

1.1 数据结构的分类

数据结构可以根据数据的逻辑关系和数据的物理存储方式进行分类，常见的数据结构分类包括线性结构、树形结构、图结构等。

1.2 数据结构的基本概念

（1）数据元素：数据结构中的基本单位，可以是原子类型或者复合类型。

（2）数据项：数据元素中的一个组成部分，通常是基本类型。

（3）数据结构的逻辑结构：指数据元素之间的逻辑关系，包括线性结构、树形结构、图结构等。

（4）数据结构的存储结构：指数据元素在计算机内存中的存储方式，包括顺序存储结构和链式存储结构等。

1.3 数据结构的特点

数据结构具有以下几个特点：

（1）抽象性：数据结构是对现实世界中的数据进行抽象和模型化的结果。

（2）实用性：数据结构是在解决实际问题中得出的经验总结，是具有广泛应用价值的。

（3）形式化：数据结构具有精确的数学定义和描述，可以进行分析和证明。

（4）计算性：数据结构是为了使计算机程序更加高效而存在的。

二、线性结构

线性结构是数据元素之间存在一对一的关系，是一种最简单的数据结构。常见的线性结构包括数组、链表、栈和队列等。

2.1 线性表

线性表是数据元素之间存在一对一的关系的数据结构，可以采用顺序存储结构或者链式存储结构实现。 （1）顺序存储结构：线性表采用数组的方式进行存储，数据元素在内存中连续存储。

（2）链式存储结构：线性表采用链表的方式进行存储，数据元素在内存中非连续存储，通过指针将它们进行连接。

2.2 栈

栈是一种特殊的线性表，只允许在一端进行插入和删除操作，这一端称为栈顶。栈的操作遵循后进先出（LIFO）的原则。

2.3 队列