数据结构（一）基本概念

在计算机科学中，数据结构（英语：data structure）是计算机中存储、组织数据的方式。
——维基百科

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。

它包含三方面的内容，逻辑关系、存储关系及操作。

逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的

数据的逻辑结构分为线性结构和非线性结构

1. 集合结构（元素同属于一个集合，元素之间不存在任何关系）
2. 线性结构（元素只存在一对一的关系）
3. 树形结构（元素之间存在一种一对多的层次关系）
4. 图形结构（元素之间存在多对多的关系）

存储结构

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

存储结构可以分为两类：

• 顺序存储：存储的物理位置相邻。（p.s. 物理位置即信息在计算机中的位置。）
• 链式存储：存储的物理位置未必相邻，通过记录相邻元素的物理位置来找到相邻元素。
• 索引存储：类似于目录。
• 散列存储：通过关键字直接计算出元素的物理地址。

C 语言实现顺序存储：

1
2

int arr[6] = {1,2,3,4,5,6};  // 定义数组并初始化
printf("%d \n", arr[3]);

顺序结构的优点：

1. 充分利用所有的存储单元，不会出现碎片现象

缺点：

1. 需要额外空间用来存放下一结点的指针
2. 只能实现顺序存储

C 语言实现链式存储：

1
2
3
4
5
6
7
8
9
10
11

typedef struct Lnode
{
    Element data;
    struct Lnode *next;
}Lnode, *LinkList;

// 定义一个指针
Lnode *L;
L = (LinkList)malloc(sizfof(Lnode));
A->next = B;
B->next = C;

链式结构的优点：

1. 可以实现随机存取
2. 每个元素占用最少的空间

缺点：

1. 只能使用整块的存储单元，会产生较多的碎片

在上面的例子中，A 只知道 B 的地址，B 只知道 C 的地址，A 不能直接访问到 C，因为它不知道 C 的地址。

这就是链式结构只能实现顺序存储的原因。

常用算法

数据结构研究的内容，就是如何按一定的逻辑结构（线性结构还是树形结构），把数据组织起来，并选择适当的存储结构（顺序存储还是链式存储）把逻辑结构组织好的数据存储到计算机的储存器里。

算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般有以下几种常用运算：

• 检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
• 插入：往数据结构中增加新的节点。
• 删除：把指定的结点从数据结构中去掉。
• 更新：改变指定节点的一个或多个字段的值。
• 排序：把节点按某种指定的顺序重新排列。例如递增或递减。