最大—最小堆
最大堆示例]] 最小堆示例]] 最小—最大堆（Min-Max Heap）是最大层和最小层交替出现的二叉树，即最大层结点的子節點属于最小层，最小层结点的子節點属于最大层。以最大（小）层结n点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。 介绍 最大堆和最小堆是二叉堆的两种形式。 最大堆：根结点的键值是所有堆结点键值中最大者的堆。 最小堆：根结点的键值是所有堆结点键值中最小者的堆。 而最大—最小堆集结了最大…
标签：#数据结构
共 69 篇文章
集合 (计算机科学)
在计算机科学中，集合是一组可变数量的数据项（也可能是0个）的组合，这些数据项可能共享某些特征，需要以某种操作方式一起进行操作。一般来讲，这些数据项的类型是相同的，或基类相同（若使用的语言支持继承）。列表（或数组）通常不被认为是集合，因为其大小固定，但事实上它常常在实现中作为某些形式的集合使用。 集合的种类包括列表，集，多重集，树和图。枚举类型可以是列表或集。 列表 在列表中，数据项的顺序是确定的，也可以存在多个相同的数据项。列表支持的操…
朱迪矩陣
朱迪矩陣（Judy array）是一个计算机科学和软件工程学中的名词，是一种高性能、低内存消耗的数据结构，实现了关联数组的功能。与普通数组不同，Judy array可以是稀疏的，这一点更像是散列表，而非数组。Judy array可以用整形或字符串作为键值来存储、查询数据，它最大的优势是可动态自动扩展，高性能，节省内存并且易于使用。 由于Judy array在操作速度和内存使用上都非常高效，同时并不需要特殊配置或初始化，使得它可以用来替换…
关系 (数据库)
在关系模型中，关系是描述现实世界的实体及其之间各种联系的单一的数据结构。由关系的名称和一组具有共同属性的无序的多元组构成。关系可以看做是一个笛卡尔积的有限子集，笛卡尔积中的元组并不是全都有意义，只有有意义的那些才能成为关系。 :例如给定两个域：X1 = {1，2，3}和X2 = {一，二，三} ::这两个域的笛卡尔积是一个由9个二元组组成的集合：X1 × X2 = {（1，一），（1，二），（1，三），（2，一），（2，二），（2，三）…
双端队列
双端队列（deque，全名double-ended queue）是一种具有佇列;}-和堆疊;}-性质的抽象数据类型。双端队列中的元素可以从两端弹出，插入和删除操作限定在-{zh-hans:队列; zh-hant:佇列;}-的两邊进行。 操作 双端队列可以在队列任意一端入队和出队。此外，经常还会有一个查看（Peek）操作，返回该端的数据而不将其出队。 操作的名称依语言的不同而不同；主流实现包括： 外部链接 [http://java.sun…
顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。 存储结构 / c2-1.h 线性表的动态分配顺序存储结构 / #define LIST_INIT_SIZE 10 / 线性表存储空间的初始分配量 / #define LIST_INCREMENT 2 …
查找表
在计算机科学中，查找表（Lookup Table）是用简单的查询操作替换运行时计算的数组或者关联数组这样的数据结构。由于从内存中提取数值经常要比复杂的计算速度快很多，所以这样得到的速度提升是很显著的。 一个经典的例子就是三角函數表。每次计算所需的正弦值在一些应用中可能会慢得无法忍受，为了避免这种情况，应用程序可以在刚开始的一段时间计算一定数量的角度的正弦值，譬如计算每个整数角度的正弦值，在后面的程序需要正弦值的时候，使用查找表从内存中提…
结构体 (C语言)
在C语言中，结构体（struct）指的是一种数据结构，是C语言中复合数据类型（aggregate data type）的一类。结构体可以被声明为变量、指针或数组等，用以实现较复杂的数据结构。结构体同时也是一些元素的集合，这些元素称为结构体的成员（member），且这些成员可以为不同的类型，成员一般用名字访问。 定义与声明 结构体的定义如下所示，struct为结构体关键字，tag为结构体的标志，member-list为结构体成员列表，其必…
0-1原理
0-1原理（0-1 Principle）是由美国斯坦福大学著名的计算机教授高德纳（Donald Ervin Knuth）提出来的，他在《计算机程序设计艺术》的第三卷：排序与选择中，提出并论证了这个原理。 0-1原理：如果一个排序网络能够正确地对任何0-1序列排序，那么它就能对任意数组成的任意序列正确排序。 这条原理的作用是很大的，为了验证一个n输入排序网络的正确性，我们不必检验所有数字构成的任意长为n的序列，而只需检验 2^n个0-1序…