一、基本概念

luffy 12/9/2023 data-structure_c

# 什么是数据结构

数据(data)：是描述客观事物的数和字符的集合。
数据元素(dataelement)：数据的基本单位(例如,200902班中的每个学生记录都是一个数据元素)。一个数据元素可以由若干个数据项组成。
数据项(data item)：是数据最小单位，也称为字段或域。例如，200902班中的每个数据元素(即学生记录)是由学号、姓名、性别和班号等数据项组成的。
数据对象(data object)：是指性质相同的数据元素的集合,它是数据的一个子集。
数据结构(data strueture)：是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合。因此,我们可以把数据结构看成是带结构的数据元素的集合。包含三个方面：逻辑结构、存储结构和对数据的运算。

逻辑结构：两个要素：数据元素和关系

四种基本逻辑结构：集合结构，线性结构，树结构，图结构

集合结构：集合通常是由一组无序的, 不能重复的元素构成。
线性结构：线性结构(linear structure)是指该结构中的数据元素之间存在一对一的关系。其特点是开始元素和终端元素都是唯一的，除了开始元素和终端元素以外,其余元素都有且仅有一个前驱元素，有且仅有一个后继元素。代表线性表。
树形结构：树形结构是指该结构中的数据元素之间存在一对多的关系。其特点是除了开始元素以外，每个元素有且仅有一个前驱元素,除了终端元素以外，每个元素有一个或多个后继元素。二叉树就是一种典型的树形结构。
图形结构：图形结构是指该结构中的数据元素之间存在多对多的关系。其特点是每个元素的前驱元素和后继元素的个数可以是任意的。树形结构和图形结构统称为非线性结构。

非线性结构：树，二叉树，有向图，无向图线性结构：线性表（线性表，栈与队列，字符串，数组，广义表）

具体可以参考图：

数据逻辑结构在计算存储器中的存储表示称为数据的存储结构

4种常用的存储方法：顺序存储结构、链式存储方法、索引存储结构、哈希(或散列)存储方法

顺序存储结构：将数据元素存放在地址连续的存储单元里，逻辑上相邻的元素其存储的物理位置也相邻。可实现对元素的随机存储，对元素的插入和删除操作要移动一系列元素，比如数组。
链式存储方法：数据放在任意的存储单元里，逻辑上相邻的元素存储的物理位置不一定相邻。便于元素的插入和删除，不用移动一系列元素；但是不能随机存储(按照下标)；存储空间利用率低，有一部分空间要来存放下一个节点的地址。
索引存储结构：索引存储结构(indexedstoragestructure)是指在存储数据元素信息的同时还建立附加的索引表。存储所有数据元素信息的表称为主数据表,其中每个数据元素有一个关键字和对应的存储地址。索引存储结构的优点是查找效率高。其缺点是需要建立索引表，从而增加了空间开销。
哈希(或散列)存储方法：哈希(或散列)存储结构(hashedstoragestructure)的基本思想是根据元素的关键字通过哈希(或散列)函数直接计算出一个值,并将这个值作为该元素的存储地址。

【例1】以下属于逻辑结构的时___。

A. 顺序表 B. 哈希表 C. 有序表 D. 单链表

【例2】以下不属于存储结构是___。

A. 栈 B. 线索树 C. 哈希表 D. 单链表

栈是一种逻辑结构，通常有顺序栈和链栈两种存储结构。

【例3】在决定选取何种类型的存储结构时，一般不多考虑___。

A. 各节点的值如何 B. 节点的个数多少

C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便