【数据结构基础笔记】第一章绪论之基本概念

野性酷女 2021-06-11 15:12 553阅读 0赞

**目录**

一、简要

1、涵盖内容

2、学习要求

3、参考书目

二、重要笔记

1、基本概念

2、数据结构

--------------------

# 一、简要 #

## 1、涵盖内容 ##

1、数据结构的基本概念，数据的逻辑结构、存储结构。

2、算法的定义、算法的基本特性以及算法分析的基本概念。

## 2、学习要求 ##

1、会数据结构的几种类型，基本概念；

2、掌握数据结构类型和抽象数据类型；

3、掌握算法的五个要素及特点；

4、掌握评价算法的标准，会计算时间复杂度和空间复杂度。

## 3、参考书目 ##

《数据结构（C语言版）》严蔚敏、吴伟民 编著  清华大学出版社

# 二、重要笔记 #

## 1、基本概念 ##

###   1.数据 ###

**数据是信息的载体**，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的总称。

###   2.数据元素 ###

**数据元素是数据的基本单位**，通常作为一个整体进行考虑和处理。一个数据元素可由若干**数据项**组成，**数据项是构成数据元素的不可分割的最小单位**。（例如：学生记录就是一个数据元素，它由学号，姓名，性别等数据项组成）。

###   3.数据对象 ###

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（例如：整数数据对象是集合N = \{0，1，-1，……\}）

###   4.数据类型 ###

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

（1）**原子类型：**其值不可再分的数据类型。

（2）**结构类型：**其值可以再分为若干成分的数据类型。

（3）**抽象数据类型（abstract data type ，简称ADT）：**抽象数据组织与之相关的操作。

###   5.抽象数据类型 ###

是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与其在计算机内部如何实现无关，即不论其内部结构如何变化，只要他的数学特性不变，都不影响其外部使用。通常用（数据对象、数据关系、基本操作集）这样的三元组来表示抽象数据类型。

## 2、数据结构 ##

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。包括三方面内容：**逻辑结构**，**存储结构**，**数据运算**。

**注：一个算法的设计取决于所选定的逻辑结构，算法的实现依赖于所采用的存储结构**

###   1.数据的逻辑结构 ###

逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，独立于计算机，分为线性结构和非线性结构：

**线性结构**

（1）**线性结构：**一对一。

**非线性结构**

（2）**树形结构：**一对多。

（3）**图状或网状结构：**多对多。

（4）**集合：**除同在一个集合外，没有其他关系。

![70][]

###   2.数据的存储结构 ###

数据在计算机中的表示（又称映像），又称**物理结构，**包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言实现，依赖于计算机语言，数据的存储结构主要有**：顺序存储，链式存储，索引存储，散列存储**。

（1）**顺序存储**：顺序存储方式是指将所有的数据元素放在**一段连续的存储空间**中，并使**逻辑上相邻的数据元素其对应的物理存储位置也是相邻的**（即保证逻辑位置关系与物理位置关系的一致）。顺序存储结构通常借助程序设计语言中的数组来加以实现。

**         优点**：可以实现随机存取，每个元素占用最少的存储空间。

**         缺点**：只能使用相邻的一整块存储单元，可能产生较多的外部碎片。增加、删除结点比较麻烦。

（2）**链式存储**：链式存储方式**不需要将逻辑上相邻的元素存储在物理位置相邻的位置**，也就是说**数据元素的存储具有任意性**。每个数据元素所对应的存储表示由两部分组成，一部分存储元素值本身，另一部分用于存放表示逻辑关系的指针。我们可以认为指针给出的是下一个数据元素的存储地址。

**         优点**：不会出现碎片现象，增加、删除结点比较方便。

**         缺点**：存储指针占用额外存储空间，并且只能实现顺序存取。

（3）**索引存储**：索引存储方式在存储数据元素的同时还增加了一个索引表。索引表中的每一项包括**关键字和地址**，关键字是能够唯一标示一个数据元素的数据项，地址是指示数据元素的存储地址或者存储区域的首地址的。

**         优点**：检索速度快。

**         缺点**：索引表占用较多存储空间，增加、删除结点要修改索引表，比较麻烦。

（4）**散列存储**：散列存储也称为哈希存储，这种存储方式将数据元素存储在一个连续的区域，每一个数据元素的具体存储位置是根据该数据的关键字值，通过散列（Hash）函数直接计算出来的。

**         优点**：检索，增加、删除结点速度快。

**         缺点**：若散列函数不好可能出现存储单元冲突，解决冲突会增加时间和空间开销。

###   3.数据的运算 ###

施加在数据上的运算包括运算的定义和实现。**运算的定义针对逻辑结构**，指出运算的功能；**运算的实现针对存储结构**，指出运算的具体操作步骤。

[70]: /images/20210516/49e36d48cebe4578afafc2a7db4589a4.png

【数据结构基础笔记】第一章绪论之基本概念

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关数据结构第一章绪论

相关数据结构与算法学习笔记（第一章绪论）

相关数据结构习题——第一章绪论

相关数据结构 |【第一章】概念

相关数据结构绪论-基本概念和术语

相关第一章绪论

相关数据结构学习笔记第一章绪论

相关数据结构第一章绪论作业（50分）

相关【数据结构基础笔记】第一章绪论之算法及算法分析

相关【数据结构基础笔记】第一章绪论之基本概念