跳转到内容

A-level 计算机/WJEC (Eduqas)/组件 1/数据结构

Add links
来自维基教科书，开放世界中的开放书籍

数据结构是**相关数据项的集合**，用于组织与现实世界问题相关的数据。它们由一维、二维或三维数组组成，这些数组根据索引存储数据；记录则基于代表性字段；栈/队列根据添加数据的顺序存储数据；二叉树包含数据节点；链表使用指针存储数据；哈希表将数据存储在一个存储表中。

数据结构有两种类型：静态和动态。静态数据结构在程序开始时具有预定义的大小，在程序运行时不能更改。静态结构的优点是内存 (RAM) 需求是已知的。动态数据结构可以在程序运行时扩展和收缩。只要内存中有足够的空间，就可以添加必要的数据。动态数据结构的唯一问题是它们更难实现。

每种数据结构都适用于不同的目的。效率的衡量标准是数据在元素数量增加时搜索所需的时间。这可以通过大 O 符号来表示。

数据结构的类型

[编辑 | 编辑源代码]

数组

[编辑 | 编辑源代码]

1D

[编辑 | 编辑源代码]
Set employees(5) As String = ["Alice", "Bob", "Cameron", "Courtney", "Daniel", "Emilia" ]

数组是**相同数据类型**的静态元素集合，以线性方式存储。每个元素都通过其索引访问，第一个元素的索引为 0，后续每个元素的索引依次递增 1。要访问数组中的数据，请指定数组的名称以及要访问的元素，例如 employees(0) 获取第一个元素的数据。

0 1 2 3 4 5
Alice Bob Cameron Courtney Daniel Emilia

2D

[编辑 | 编辑源代码]
Set employees(5, 1) = [ ["Alice", "Bob" "Cameron", "Courtney", "Daniel", "Emilia"], [ 20, 38, 23, 50, 40, 35 ] ]

二维 (2D) 数组可以看作是表格，或者更简单地说，是多个一维 (1D) 数组。要访问二维数组中的元素，必须指定要访问的列的索引和要访问的行索引。格式为 (行, 列)。要声明二维数组，使用两个方括号（一个表示二维数组的开始，另一个表示元素的开始）。

0 1 2 3 4 5
姓名 [0] Alice Bob Cameron Courtney Daniel Emilia
工资 [1] 20 38 23 50 40 35

3D

[编辑 | 编辑源代码]
Set employees(2, 1, 5) As String =

[

// Sales for the month of January.

[ ["Alice", 950] , ["Bob", 750], ["Cameron", 900], ["Courtney", 2500], ["Daniel", 2400], ["Emilia", 1500]  ],

// Sales for the month of February.

[ ["Alice", 1000] , ["Bob", 700], ["Cameron", 800], ["Courtney", 3000], ["Daniel", 2500], ["Emilia", 1700]  ]

]

三维 (3D) 数组是多个二维数组组合在一起，或者是一组表格。如果我们有表格编号、列和行，就可以访问数据（表格编号、行、列）。

2018 年 1 月的销售额
0 1 2 3 4 5
姓名 [0] Alice Bob Cameron Courtney Daniel Emilia
销售额 [1] 950 750 900 2500 2400 1500
2018 年 2 月的销售额
0 1 2 3 4 5
姓名 [0] Alice Bob Cameron Courtney Daniel Emilia
销售额 [1] 1000 700 800 3000 2500 1700


记录

[编辑 | 编辑源代码]

记录是与单个个体或实体相关的多个数据项的集合。与数组不同，记录可以包含不同类型的数据。下面显示了一个记录的示例。

客户记录
0 1 2
姓名 (字符串) Alice Bob Daniel
首字母 (字符) A B D
年龄 (整数) 24 34 18
出生日期 (日期) 08/04/1994 23/10/1984 09/12/2000

栈和队列

[编辑 | 编辑源代码]
一堆薄饼就像一个栈 - 它是一个 LIFO 结构。

栈是一个 LIFO 数据结构：后进先出。这意味着数据以与添加顺序相反的顺序删除，最近添加的条目最先删除。把它想象成一堆薄饼 - 你必须先吃掉顶部的薄饼才能吃到下面的任何薄饼。栈的一个例子是“撤销”功能；你最后写的内容是第一个被删除的内容。栈可以通过使用数组简单地实现；只需使用一个指针指向最上面的项目。将数据添加到栈中称为入栈，而从栈中删除数据称为出栈。

另一方面，队列是一个先进先出 (FIFO) 数据结构。数据按添加顺序删除，就像一个普通的队列一样。队列在打印机中使用，以确保作业按到达的顺序打印，并在键盘缓冲区中使用，以确保每个键按顺序处理。队列也可以通过使用数组实现，但这需要一个指向顶部条目的指针，以及一个指向底部的指针，使其更难有效地执行。队列中使用的两种方法是“入队”和“出队”。


出栈（删除）和入栈（添加）项目的伪代码如下

Def pop(topItem):
If Stack(topItem) = NULL Then
    Output "Stack is empty - cannot pop."
    Return NULL
Else
    Value = Stack(topItem)
    Stack(topItem) = NULL
    topItem = topItem - 1   //  We must point to the previous item in the stack.
    Return Value
End If


Def Push(Value, TopItem):
If Stack Is Full Then
    Output "Stack is full - cannot push."
Else
    TopItem = TopItem + 1
    Stack(TopItem) = Value
    Output "Item added to the stack."
End If

你还应该知道入队和出队方法的伪代码

Def Enqueue(Data)
If Queue Is Full Then



   Output "Queue is full - cannot enqueue."



Else



   TopItem = TopItem + 1
   Queue(TopItem) = Data
   Return TRUE



End If



Def Dequeue
If Queue Is Empty Then



   Output "Queue is empty - cannot dequeue."



Else



   Data = Queue(BottomItem)
   BottomItem = BottomItem + 1
   Return TRUE



End If

链表

[编辑 | 编辑源代码]

链表是数据元素的集合，其中**每个元素都包含数据本身以及指向下一个元素的指针**。最后一个元素有一个指向无效值的指针 (NULL)，表示列表的结束。使用链表的优点是可以在不重新排列所有其他元素的情况下将新项目插入链表。链表可以使用二维表实现，其中每行的第一个条目包含数据，而第二个条目是指针，包含指向下一个数据点的行索引。要从链表中删除数据，请调整其之前的节点使其指向其后的项目，从而绕过链接，但保留项目的顺序。

  • This is a linked list with pointers and a rogue value "null".
    这是一个带有指针和无效值“null”的链表。

二叉（查找）树

[编辑 | 编辑源代码]

二叉查找树由节点和它们之间的链接组成。每个节点最多有两个节点从它延伸出来，类似于家谱或因数树的设计。二叉查找树最重要的方面是，左分支上的数据必须小于根节点中的数据，而右分支上的数据必须大于根节点中存储的数据。如果节点均匀分布在树中，则二叉树被称为平衡的，这将产生最小的高度。不平衡的树在一侧的节点比另一侧多得多。

这是一个大致平衡的二叉树，根节点为“8”

有三种主要方法可以遍历二叉查找树。它们是

  • 先序遍历 (**N**LR) - 从根节点开始，遍历左子树，然后遍历右子树。这将得到 8, 3, 1, 6, 4, 7, 10, 14, 13
  • 中序遍历 (LNR) - 遍历左子树，访问根节点，然后遍历右子树。这将给出 1, 3, 4, 6, 7, 8, 10, 13, 14
  • 后序遍历 (LRN) - 遍历左子树，然后遍历右子树，最后访问根节点。这将给出 1, 4, 7, 6, 3, 13, 14, 10, 8

要将数据添加到二叉搜索树中，首先将新条目与当前节点进行比较。如果新数据更大，则沿着右指针移动，否则沿着左指针移动。重复此过程，直到没有可供选择的指针。在此处创建一个新的指针，指向比较结果指示的方向，并将新数据插入到末尾。如果您被要求根据数据列表绘制二叉搜索树，请按照此程序对每个数据片段进行操作，顺序很重要。

您可以被要求使用二维数组（表格）来表示二叉树。每个元素将从左到右具有一个数字 ID（8 将是 1，3 将是 2，10 将是 3 等）。这可以像使用链表一样完成，每一行包含数据、左指针和右指针（如果不存在指针，则使用 NULL）。

ID 左指针 数据 右指针
1 2 8 3
2 4 3 5
3 NULL 10 6
4 NULL 1 NULL
5 7 6 8
6 9 14 NULL
7 NULL 4 NULL
8 NULL 7 NULL
9 NULL 13 NULL

哈希表

[编辑 | 编辑源代码]

哈希表是一种特殊类型的数据结构，其中数据的特性用于决定数据的存储位置。哈希表有两个主要部分 - 哈希函数和存储表。

哈希函数在哈希表中起着关键作用。它是一个只有开发人员知道的秘密函数，它决定数据应该存储的位置，基于从数据本身的属性推导出的可复制计算。哈希函数通常非常复杂，但一个简单的例子可以是length(data) MOD 11。这将找到数据条目中的字符数，然后找到该值除以 11 后的余数。返回的数字可以作为存储表中的索引。

数据输入前的数组
0 1 2 3 4 5 6 7 8 9 10
开始数据 哈希函数操作 结束数组位置
54 54 MOD 11 10
26 26 MOD 11 4
93 93 MOD 11 5
17 17 MOD 11 6
77 77 MOD 11 0
31 31 MOD 11 9
数据输入后的数组
0 1 2 3 4 5 6 7 8 9 10
77 26 93 17 31 54

使用哈希表的问题也源于哈希函数。使用一个能够将数据均匀地分布在表中，最好是分布在一个较宽范围内的哈希函数非常重要，以避免两个不同的数据片段写入同一个索引。然而，这在实践中是不现实的，特别是如果哈希算法只有有限的输出数量。一个更实用的解决方案是在每个索引处使用一个新的数据结构，以允许多个条目存储在那里。这可能是一个链表，甚至可能是一个具有其自身哈希函数的新哈希表，但这也会增加数据存储和检索所需的时间。

取自 "https://wikibooks.cn/w/index.php?title=A-level_Computing/WJEC_(Eduqas)/Component_1/Data_structures&oldid=4371060"
华夏公益教科书