# 数据结构与算法常用词汇

Section 1 Introduction

（storage structure） *链式(存储结构) linked （storage 链式(存储结构) structure） 算法分析 analysis of an algorithm 1. * 抽象数据类型

domain and structure of the data, along with a collection of operations that access the data. It creates a user-defined data type whose operations specify how a client may manipulate the data. 抽象数据类型定义了数据取值范围和表现结构， 以及对数据的操作。 ADT 给出了一种用户 定义的数据类型，其运算符指明了用户如何操作数据。 2. *时间复杂度 time complexity: Time complexity analysis looks at the internal structure of

2

an algorithm by analyzing its design, including the number of comparison tests, the number of iterations, the number of assignment statements used by the algorithm. 时间复杂度分析旨在检查算法的内部结构，所使用的方法是分析算法的设计，包括算法中 使用的比较、赋值等各种语句的次数。Time complexity analysis is independent of any particular computer system. The criteria measure the computational complexity of the algorithm relative to n, the number of data items in the collection. 时间复杂度分析是独立于特定的计算机系统，它用算法处理的数据元素的个数 n 来衡量算 法的计算复杂度。 3. *空间复杂度 space complexity: Space complexity is a measure of the relative amount of

internal memory used by an algorithm. It can dictate what kind of computer is capable of running the algorithm and the overall system efficiency of the algorithm. 空间复杂度用来测定算法需要的内存空间大小，它可以用来说明算法适合在何种计算机上 运行及算法的总体系统性能。

Section 2 Linear Lists

3

1.

*线性表 linear lists: A linear list is the collection of objects that are sequentially accessed.

It has a unique first and last element and each interior item has a unique successor. A linear list is a general description for structures that include arrays, stacks, queues, and linked lists. 线性表是顺序访问的对象集合。它只有唯一一个头元素和一个尾元素，中间各项都有唯一 一个后继。线性表是数组、堆栈、队列和链表等结构的统称。 2. *顺序表 sequential list: Sequential list is a kind of storage structure of linear lists that

stores elements in a sequential order. The structure holds an arbitrary number of items. The size of the list is modified by adding or deleting an item from the list, and the items in the list are referenced by their positions. 顺序表是线性表的一种存储结构，这种线性表的结构存放着任意个数的元素。表的大小通 过增加或删除表中的元素来改变，表中元素通过其位置来访问。 In a linear list, the first element occurs at the head or front of the list, and the last element occurs at the rear of the list. Each element except the first and the last has a unique predecessor and a unique successor. 在线性表中，第一个元素位于表头，最后一个元素是表尾，除第一个元素和最后一个元素 外，每一个元素都有唯一的前趋和唯一的后继。 3. 头节点 head node or header: An empty linked list contains a node, which has an

uninitialized data field. This node is called the header and initially points to itself. The role of the header is to point the first ‘real’ node in the list and hence the header is often referred to as a sentinel node. 一个空链表中包含一个结点，它有一个未经初始化的数据域。该结点叫头结点，初始化时 它指向自己。头结点的作用是指向表中第一个“真正的”结点，因此它常被称为“哨位” 结点。 4. 有序表 ordered list: An ordered list is a special type of list that maintains the elements in

ascending order. 有序表是一种特殊的表，其元素按升序排列。

4

5. 双向链表 doubly linked lists 或 bi-directional linked lists: In cases where we need to access nodes in either direction, a doubly linked list is helpful. A node in a doubly linked list contains two pointers and the data field. 当我们需要双向访问节点时，双向链表是很有用的。双向链表中的节点含有两个指针域， 一个数据域。

Section 3 Stacks and Queues

*栈 stack: A stack is a list of items that are accessible at only one end of the list. Items are

added or deleted from the list only at the top of the stack. A stack is said to have LIFO(last-in/first-out) ordering. 栈是一种只能在表的一端访问元素的表，其元素只能从栈顶端增加或删除。出入栈的顺序 为后进先出（LIFO, last-in/first-out） 。 A stack structure features operations that add and delete items. A Push operation adds an item to the top of the stack. The operation of removing an element from the stack is said to pop the stack. 栈结构就出增加和删除元素的操作。压入（push）操作往栈顶增加一个元素。从栈顶删除

5

consists of: （1）One or more stopping conditions which can be evaluated for certain parameters. （2）A recursive step in which a current value in the algorithm can be defined in terms of a previous value. Eventually, the recursive step must lead to stopping conditions. 如果一种算法的定义组成如下，则它就是递归的。 （1）对应于某些参数可以求值的一个或多个终止条件。 （2）一个递归步骤，它根据先前某次值求当前值。递归步骤最终必须导致终止条件。 3. *队列 queue: A queue is a data structure that stores elements in a list and permits data

access only at the two ends of the list. An element is inserted at the rear of the list and is deleted from the front of the list. 队列是以表形式存放元素，但只允许在表的两端访问元素的数据结构，其元素只能在表尾 插入(入队)，在表头删除（出队） 。 Elements are removed from the queue in the same order in which they are stored and hence a queue provides FIFO (first-in/first-out) or FCFS(first-come /first-served) ordering. 队列删除元素的顺序和元素到达队列的顺序相同， 可称为先进先出 （FIFO, first-in/first-out） 或先到先服务（FCFS，first-come/first-served） 。 4. 优先级队列 priority queue: A queue is a data structure that provides a FIFO ordering of

elements. The queue removes the “oldest” item from the list. Applications often require a modified version of queue storage in which the item of highest priority is removed from the list. This structure is called a priority queue. 一个队列是以 FIFO 顺序访问元素的数据结构，它从中删除“最老”的元素。实际应用中 常需要另外一种队列，它删除优先级最高的元素，这种结构我们称为优先级队列。

Section 4 Strings and Arrays

6

*子串 substring 主串 primary string 空串 null string 空格串 blank string 文本编辑 text editing 模式 pattern 1.

*串 string: A string is a special form of an array that holds character data that identify

names, words, sentences, and so forth. It treats the characters as a single entity and provides operations to access character sequences within the string. 串是一种特殊形式的数组，它存放着组成名字、单词、句子等的字符数据。它将字符视为 单元实体，并提供得到字符在串中位置的操作。 2. *模式匹配 pattern matching: A common pattern matching problem involves searching for

one or more occurrences of a string in a text. 一个最普通的模式匹配问题就是在文本文件中查找串。 3. *数组 array: An array is an example of a data collection. It defines a structured data type

that holds a homogeneous list of items. A one-dimensional array is a finite, sequential list of elements of the same data type (homogeneous array). A two-dimensional array, often called a matrix, is a structured data type that is created by nesting one-dimensional arrays. Items are accessed by row and columns indices. 数组是一个数据集的例子。它定义了一个可以存放多个相同类型元素的结构化数据类型。 一维数组是一个具有有限个相同数据类型元素的顺序表（同构数组） 。二维数组通常成为 矩阵，是一种由多个一维数组合成的结构化数据类型。其元素通过行和列下标存取。 The element type of an array can include not only the built-in data type such as int or char but also user-defined class type. 数组元素的类型不但可以是原始类型如整型或字符型，也可以是用户定义的类类型。 4. 一维数组的存储 storage of one-dimensional array: A C++ one-dimensional array A is

7

logically stored as a consecutive sequence of items in memory. Each item is of the same data type. C++的一维数组 A 逻辑上在内存中连续存放，其每个元素的类型相同。 5. 二维数组的存储 storage of two-dimensional arrays: A two-dimensional array can be

initialized by assigning the items a row at a time. 二维数组可以通过一次赋值一行元素来初始化。

Section 5 Trees and Binary Trees

8

*树 tree: A tree is a hierarchical structure that consists of nodes emanating from a root. A

tree structure is characterized as a set of nodes that originates from a unique starting node called the root. Each node in a tree is the root of a subtree, which is defined by the node and all descendants of the node. 树是一种由根发散的节点所组成的层次结构由若干个节点和叶子组成的。它的特点是它是 由唯一的起始点“根（root） ”开始的“节点”集合。树中的每个节点都是一棵“子树”的 根，这个子树是由节点和节点的后代定义的。 2. *二叉树 binary tree: A binary tree is a restricted class of tree in which each parent has no

more than two children.A binary tree is a recursive structure. Each node is the root of its own subtree and has children, which are roots of the tree called the left and right subtrees of the node, respectively. 叉树是一种特定的树，在这类树中，每个双亲的孩子数不超过两个。二叉树是一种递归结 构。每个节点都是其子树的根并有孩子，这些孩子分别是被称为节点的左子树和右子树的 根。

Section 6 Graphs and Generalized Lists

9

*图 graph: A graph is a generalized hierarchical structure that is composed of a set of data

items called vertices and a set of edges that connect pairs of vertices. Graphs find applications in

10

job scheduling, transportation, and so forth. 图是一种一般化的层次结构。它由一组叫作“顶点（vertex） ”的数据项和一组连接各对顶 点的“边（edge） ”所组成。它在作业调度、运输等方面有着应用。 2. *深度优先搜索 Depth-First Search(DFS): The search algorithm uses a list L to maintain

a record of visited vertices and a stack S to store adjacent vertices. After placing the initial vertex on the stack, we begin an iterative process that pops a vertex from the stack and then visits the vertex. We terminate when the stack is empty and return the list of visited vertices. 搜索算法用表 L 维护被访问顶点的记录，用堆栈 S 存储邻接顶点。在将初始顶点放入堆栈 以后，开始迭代过程，从堆栈中弹出一个顶点并访问它。当堆栈为空时过程终止并返回被 访问过的顶点表。 3. *宽度优先搜索 Breadth-First Search(BFS): The breadth-first search uses a queue as does

the level order scan of a binary tree. The algorithm uses the techniques developed for the depth-first search. Vertices are placed in a queue instead of a stack. An iterative process removes vertices from the queue until it is empty. 与二叉树的逐层扫描一样，宽度优先搜索使用队列。除此之外，该算法使用与深度优先搜 索相同的技术。即顶点是放到队列中而非堆栈中。迭代过程从队列中删除顶点直到队列空 为止。

Section 7 Searching
*静态查找表 static search table *动态查找表 dynamic search table 主关键字 primary key 次关键字 second key *查找 searching *平均查找长度 Average Search Length(ASL) 斐波那契查找 Fibonacci search 斐波那契序列 Fibonacci numbers *索引顺序查找 indexed sequential search *分块查找 blocking search *二叉排序树 binary sort tree

11

*链地址法 chaining-address method *直接定址 immediately allocate 随机数法 random number method 折叠法 folding method 移位叠加 shift folding 数字分析法 digit analysis method 间界叠加 folding at the boundaries 平方取中 mid-square method 估值函数 evaluation function *再哈希 rehash *装填因子 load factor

search for and retrieve data. In each structure, a Find method takes a key and traverses the list looking for a matching data item. 查找表是一系列允许客户程序搜索和取出数据的表结构。每种结构都有一个 Find（查找） 方法，它以关键字为参数，遍历表以找到匹配的数据项。 2. *顺序查找 sequential search: A sequential search looks for an item in a list using a target

value called the key. The algorithm begins at a user-supplied index, called start, and traverses the remaining items in the list, comparing each item with the key. The scan continues until the key is found or the list is exhausted. If the key is found, the function returns the index of the matched element in the list; otherwise, the value –1 is returned. 顺序查找用一个称为关键字 Key 的目标值来查找表中的元素。 该算法从用户给出的起点开 始，遍历表中的后续元素，并将元素值与 Key 比较，直到元素值与 Key 值相等或到表尾。 如果找到 Key 值，函数返回该元素在表中的位置；否则，返回-1。 3. 有序表 ordered list: An ordered list is a special type of list that maintains the elements in

12

ascending order. 有序表是一种特殊的表，其元素按升序排列。 4. *折半查找 binary search: The sequential search applies to any list. If the list is ordered,

an algorithm, called the binary search, provides an improved search technique. 顺序查找可适用于任意表。若被查找的表有序，则可用折半查找算法来查找，它是一种改 进的查找算法。 5. *二叉查找树 binary search tree: In a binary search tree, for each node, the data values in

the left subtree are less than the value of the node and the data values in the right subtree are greater than or equal to the value of the node. 在二叉查找树中，对每个节点，其左子树中的数据值都小于节点本身的值，而右子树中的 数据值都大于或等于节点的值。 6. （ *平衡二叉树 AVL 树） balanced binary tree 或 height-balanced tree: Binary search tree

is designed for rapid access to data. Ideally, the tree is reasonably balanced and has height approximately O(log2n). With some data, however, a binary search tree can be degenerate. In that case, the height is O(n) and access to the data is significantly slowed. We develop AVL tree in which every node is height-balanced. By this we mean that for each node in an AVL tree, the difference in height of its two subtree is at most 1. 二叉搜索树是为快速访问数据而设计的。 理想情况下， 树是平衡分布的， 其高度为 O(log2n)。 但对有些数据来说，二叉搜索树也可能是退化的。那时树高将是 O(n)，访问数据的速度将 明显变慢。我们要设计的是各节点具有平衡高度的 AVL 树。也就是说，在 AVL 树中任一 节点的两个子树的高度差最多为 1。 7. *哈希函数 hash function : In most applications, a key is used to provide an indirect

reference to the data. A function, called a hash function, maps the key into a range of integers and then uses the integer value to access the data. 在多数应用中，关键字用来提供对数据的间接引用。哈希函数是将关键字映射到一定范围 的整数内，然后用整数值来访问数据。 A hash function must map a key to a integer value in the range 0 to n-1. Its design should limit

13

collisions and guarantee efficient execution. 哈希函数必须将关键字映射为 0 到 n-1 范围内的整数值。其设计必须考虑减少冲突并保证 执行效率。 8. 除留余数法 division method: The division method is the most commonly used hashing

technique, requiring two steps. First the key must be transformed into an integer and then the value must be telescoped into the range 0 to n-1 using the remainder operator. In practice, the division method is used in most hashing applications. 除留取余法（division method）是最常用的哈希技术，它分为两个步骤。首先必须将关键 字转换成整数值，然后再用求余数运算符将这一值缩到 0~n-1 的范围内。在实际的哈希应 用中，除留取余法用得最多。

Section 8 Sorting

14

*基数排序 radix sorting * 最高位优先 (MSD) *最低位优先 (LSD) *链式基数排序 linked radix sorting 磁带排序 sorting with tapes 间隙 gap 寻查时间 seek time 等待时间 latency time 传输时间 transmission time 段 segment 归并段 merging segment 有序段 sorted segment 1. Least Significant Digit first Most Significant Digit first

*排序 sorting: Sorting is the process of arranging a group of data elements into some

desired order according to rules dependent upon a key or several keys contained in each data element. 排序是根据每个数据元素中所含关键字所确定的规则,将一组数据元素排列成某种所需次 序的过程。 2. *选择排序 selection sort: Given a group of data items in random order, the selection sort

repeatedly selects the smallest item from the group and moves it to a list that is forming in ascending order. 对以随机顺序排列的一组数据项，选择排序将反复地从组中挑选出最小的数据项并将它移 到正在形成的按升序排列的表中。

15

Section 9 File

16

1.

*文件 file: A file is the record collection of the same type. The stored data on the external

device along with the transfer operations define a data structure, called a (logical ) file, that has the important advantage of holding greater amounts of information than typically resides in memory. 文件是类型相同的记录集合。外部设备上存储的数据及转换操作定义了一个（逻辑）文件数 据结构。它在存放大量信息方面比传统的只在内存驻留信息方法占有很大优势。 Two types of disk files are text files and binary files. A text file contains ASCII characters and is printable whereas a binary file contains pure binary data. 磁盘文件有两种类型：文本文件和二进制文件。文本文件中存放可打印的 ASCII 字符，而 二进制文件中存放纯粹的二进制数据。 2. 记录 record: A record is a structure that bundles items of different types into a single object.

The items in the record are called fields. Like an array, a record has a access operator that allows for direct access to each field. 记录是将多个不同类型的元素组合成一个单独对象的结构。 记录中的元素称为域。 和数组一 样，记录也可以通过存储操作符直接访问各个域。 二进制文件 binary file: A binary file consists of data records that vary from a single character(byte) to more complex structures that include integers, floating point values, and arrays. 二进制文件是由数据记录构成的，这些数据记录可以是单个字符（字节） ，也可以是更复杂 的结构，如整数、浮点数以及数组。

17

（表达式的）后 缀表示 7 （表达式的）前 缀表示 8 （表达式的）中 缀表示 7 （节点的）度 7 2-路插入排序 13 AOE-网 9 AOV-网 9 遍历 7 不稳定 13 抽象 1 存储密度 2 带权路径长度 8 单键排序 13 递归 4 多键排序 13 二叉链表 7 反序 13 关键活动 9 孩子表示法 7 孩子兄弟表示法 7 汇点 9 简单图 9 间接寻址 2 渐进复杂度 1 基本语句 1 结点 2 克鲁斯卡尔算法 9 链队列 4 链栈 4 路径长度 8 模式 6 逆序 13 普里姆算法 9 三叉链表 7 三元组顺序表 6 始点 9 十字链表 6 双链表 2 双亲表示法 7 双亲孩子表示法 7 顺序存取 2 顺序栈 4 随机存取 2 同构 7 头尾表示法 9 尾标志 2 尾指针 2 稳定 13 问题规模 1 线索 7 源点 9 正序 13 终点 9 主串 5 败者树 14 边 9 表插入排序 13 表达式求值 4 并行操作处理 14 不定长(文件) 15 层、层次 7 插入查找 13 插入排序 13 查找 10 查找表 11 冲突 11 冲突的解决 11 抽象数据类型 1 稠密图 9 出度 8 除留余数法 13 传输时间 14 串 6 磁带排序 14 次关键字 10 存储结构 1 存储密度 6 大 O 记法 1

18

IT常用英文词汇
IT常用英文词汇_英语学习_外语学习_教育专区。第一部分、计算机算法常用术语中英对照 Data Structures 基本数据结构 Dictionaries 字典 Priority Queues 堆 Graph Data ...
Java常用词汇汇总
Java常用词汇汇总_计算机软件及应用_IT/计算机_专业资料。算法常用术语中英对照 Data...算法常用术语中英对照 Data Structures 基本数据结构 Dictionaries 字典 Priority ...