Boo's Blog

Stay foolish, Stay hungry

在计算机科学中,数据结构(英语: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 的地址。

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

常用算法

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

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

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

评论