数据结构是什么？ 程序 = 数据结构 + 算法数据结构是什么呢？ 数据是对客观事务的符号表示 ，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称。那为何加上**“结构”**两字？数据元素是数据的基本单位 ，而任何问题中，数据元素都不是独立存在的，它们之间总是存在着某种关系，这种数据元素之间的关系我们称之为结构 。数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 集合：只有同属于一个集合的关系，没有其他关系 线性结构：结构中的数据元素之间存在一个对一个的关系 树形结构：结构中的数据元素之间存在一个对多个的关系 图状结构或者网状结构：图状结构或者网状结构 何为逻辑结构和存储结构？ 数据元素之间的逻辑关系，称之为逻辑结构 ，也就是我们定义了对操作对象的一种数学描述。但是我们还必须知道在计算机中如何表示它。数据结构在计算机中的表示（又称为映像），称之为数据的物理结构，又称存储结构 。顺序映像和非顺序映像 ，并且由此得到两种不同的存储结构：顺序存储结构 和链式存储结构 ，比如顺序存储结构，我们要表示复数z1 =3.0 - 2.3i ,可以直接借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系：指针 表示数据元素之间的逻辑关系，同样是z1 =3.0 - 2.3i ，先找到下一个是 100，是一个地址，根据地址找到真实的数据-2.3i:位（bit） 位 。也就是我们常见的类似01010101010这种数据，计算机的底层就是各种晶体管，电路板，所以不管是什么数据，即使是图片，声音，在最底层也是0和1,如果有八条电路，那么每条电路有自己的闭合状态，有8个2相乘，2^8^，也就是256种不同的信号。 原码：用第一位表示符号，其余位表示值 反码：正数的补码反码是其本身，负数的反码是符号位保持不变，其余位取反。 补码：正数的补码是其本身，负数的补码是在其反码的基础上 + 1 为什么有了原码还要反码和补码？ 0010001135
+ 11011101 -35
-------------------------
00000000 00010001135
+ 11011011 -37
-------------------------
11111110 -2 ~：按位取反 &：按为与运算 |：按位或运算 ^：按位异或 <<: 带符号左移，比如35(00100011),左移一位为 70(01000110),-35(11011101)左移一位为-70(10111010) >>：带符号右移，比如35(00100011),右移一位为 17(00010001),-35(11011101)左移一位为-18(11101110) <<<:无符号左移，比如35(00100011),左移一位为70(01000110) >>>:无符号右移，比如-35(11011101),右移一位为110(01101110) x ^= y; y ^= x; x ^= y;:交换 s &= ~(1 << k):第k位置0 要说哪里使用位运算比较经典，那么要数布隆过滤器 ，需要了解详情的可以参考：http://aphysia.cn/archives/cachebloomfilter布隆过滤器是什么呢？ 重点是多个hash函数，可以将数据hash到不同的位上，也只有这些位全部为1的时候，我们才能判断该数据已经存在 布隆过滤器，判断存在的元素，可能不存在，但是判断不存在的元素，一定不存在。 ，因为判断不存在说明至少有一位hash出来是对不上的。数组 存在唯一的第一个的数据元素 存在唯一被称为最后一个的数据元素 除了第一个以外，集合中每一个元素均有一个前驱 除了最后一个元素之外，集合中的每一个数据元素都有一个后继元素 线性表包括下面几种： 数组：查询 / 更新快，查找/删除慢 链表 队列 栈 数组是线性表的一种，线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素 ：int[] nums = new int[100];
int[] nums = {1,2,3,4,5};
Object[] Objects = new Object[100];int nums[100];
package datastruction;
import java.util.Arrays;
public class MyArray {
private int[] data;
private int elementCount;
private int length;
public MyArray(int max) {
length = max;
data = new int[max];
elementCount = 0;
}
public void add(int value) {
if (elementCount == length) {
length = 2 * length;
data = Arrays.copyOf(data, length);
}
data[elementCount] = value;
elementCount++;
}
public int find(int searchKey) {
int i;
for (i = 0; i < elementCount; i++) {
if (data[i] == searchKey)
break;
}
if (i == elementCount) {
return -1;
}
return i;
}
public boolean delete(int value) {
int i = find(value);
if (i == -1) {
return false;
}
for (int j = i; j < elementCount - 1; j++) {
data[j] = data[j + 1];
}
elementCount--;
return true;
}
public boolean update(int oldValue, int newValue) {
int i = find(oldValue);
if (i == -1) {
return false;
}
data[i] = newValue;
return true;
}
}
// 测试类
public class Test {
public static void main(String[] args) {
MyArray myArray = new MyArray(2);
myArray.add(1);
myArray.add(2);
myArray.add(3);
myArray.delete(2);
System.out.println(myArray);
}
}链表 链表在计算机的存储中不是连续的，而是前一个节点存储了后一个节点的指针（地址），通过地址找到后一个节点。 单向链表 ：链表中的每一个结点，都有且只有一个指针指向下一个结点，并且最后一个节点指向空。 双向链表 ：每个节点都有两个指针（为方便，我们称之为前指针 ，后指针 ），分别指向上一个节点和下一个节点，第一个节点的前指针指向NULL，最后一个节点的后指针指向NULL 循环链表 ：每一个节点的指针指向下一个节点，并且最后一个节点的指针指向第一个节点（虽然是循环链表，但是必要的时候还需要标识头结点或者尾节点，避免死循环） 复杂链表 ：每一个链表有一个后指针，指向下一个节点，同时有一个随机指针，指向任意一个结点。 查询：O(n),需要遍历链表 插入：O(1)，修改前后指针即可 删除：O(1)，同样是修改前后指针即可 修改：不需要查询则为O(1)，需要查询则为O(n) 链表的结构代码怎么表示呢？ // 结点
typedef struct LNode{
// 数据
ElemType data;
// 下一个节点的指针
struct LNode *next;
}*Link,*Position;
// 链表
typedef struct{
// 头结点，尾节点
Link head,tail;
// 长度
int len;
}LinkList;public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}class ListNode<T> {
T val;
ListNode next = null;
ListNode(T val) {
this.val = val;
}
}
public class MyList<T> {
private ListNode<T> head;
private ListNode<T> tail;
private int size;
public MyList() {
this.head = null;
this.tail = null;
this.size = 0;
}
public void add(T element) {
add(size, element);
}
public void add(int index, T element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表长度范围");
}
ListNode current = new ListNode(element);
if (index == 0) {
if (head == null) {
head = current;
tail = current;
} else {
current.next = head;
head = current;
}
} else if (index == size) {
tail.next = current;
tail = current;
} else {
ListNode preNode = get(index - 1);
current.next = preNode.next;
preNode.next = current;
}
size++;
}
public ListNode get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表长度");
}
ListNode temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
}
public ListNode delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
ListNode node = null;
if (index == 0) {
node = head;
head = head.next;
} else if (index == size - 1) {
ListNode preNode = get(index - 1);
node = tail;
preNode.next = null;
tail = preNode;
} else {
ListNode pre = get(index - 1);
pre.next = pre.next.next;
node = pre.next;
}
size--;
return node;
}
public void update(int index, T element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
ListNode node = get(index);
node.val = element;
}
public void display() {
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val + " -> ");
temp = temp.next;
}
System.out.println("");
}
}public class Test {
public static void main(String[] args) {
MyList myList = new MyList();
myList.add(1);
myList.add(2);
// 1->2
myList.display();
// 1
System.out.println(myList.get(0).val);
myList.update(1,3);
// 1->3
myList.display();
myList.add(4);
// 1->3->4
myList.display();
myList.delete(1);
// 1->4
myList.display();
}
}1 -> 2 ->
1
1 -> 3 ->
1 -> 3 -> 4 ->
1 -> 4 ->跳表 节点只有一份，都是同一个节点，只是为了好看，弄了两份，实际上是同一个节点，有两个指针，比如 1 ，既指向2，也指向5 ）：跳表(SkipList，全称跳跃表)是用于有序元素序列快速搜索查找的一个数据结构，跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，实现也比红黑树简单很多。栈 先进后出 ，就像是一个桶，只能不断的放在上面，取出来的时候，也只能不断的取出最上面的数据。要想取出底层的数据，只有等到上面的数据都取出来，才能做到。当然，如果有这种需求，我们一般会使用双向队列。import java.util.Arrays;
public class MyStack<T> {
private T[] data;
private int length = 2;
private int maxIndex;
public MyStack() {
data = (T[]) new Object[length];
maxIndex = -1;
}
public void push(T element) {
if (isFull()) {
length = 2 * length;
data = Arrays.copyOf(data, length);
}
data[maxIndex + 1] = element;
maxIndex++;
}
public T pop() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("栈内没有数据");
} else {
T[] newdata = (T[]) new Object[data.length - 1];
for (int i = 0; i < data.length - 1; i++) {
newdata[i] = data[i];
}
T element = data[maxIndex];
maxIndex--;
data = newdata;
return element;
}
}
private boolean isFull() {
return data.length - 1 == maxIndex;
}
public boolean isEmpty() {
return maxIndex == -1;
}
public void display() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]+" ");
}
System.out.println("");
}
}public class MyStackTest {
public static void main(String[] args) {
MyStack<Integer> myStack = new MyStack<>();
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.display();
System.out.println(myStack.pop());
myStack.display();
}
}1 2 3 4
4
1 2 3队列 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。class Node<T> {
public T data;
public Node next;
public Node(T data) {
this.data = data;
}
}
public class MyQueue<T> {
private Node<T> head;
private Node<T> rear;
private int size;
public MyQueue() {
size = 0;
}
public void pushBack(T element) {
Node newNode = new Node(element);
if (isEmpty()) {
head = newNode;
} else {
rear.next = newNode;
}
rear = newNode;
size++;
}
public boolean isEmpty() {
return head == null;
}
public T popFront() {
if (isEmpty()) {
throw new NullPointerException("队列没有数据");
} else {
Node<T> node = head;
head = head.next;
size--;
return node.data;
}
}
public void dispaly() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data +" -> ");
temp = temp.next;
}
System.out.println("");
}
}public class MyStackTest {
public static void main(String[] args) {
MyStack<Integer> myStack = new MyStack<>();
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.display();
System.out.println(myStack.pop());
myStack.display();
}
}1 -> 2 -> 3 ->
1
2 -> 3 ->
2
3 -> 单向队列：也就是我们说的普通队列，先进先出。 双向队列：可以从不同方向进出队列 优先队列：内部是自动排序的，按照一定顺序出队列 阻塞队列：从队列取出元素的时候，队列没有元素则会阻塞，同样如果队列满了，往队列里面放入元素也会被阻塞。 循环队列：可以理解为一个循环链表，但是一般需要标识出头尾节点，防止死循环，尾节点的next指向头结点。 队列一般可以用来保存需要顺序的数据，或者保存任务，在树的层次遍历中可以使用队列解决，一般广度优先搜索都可以使用队列解决。哈希表 散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。 直接定址法：取出关键字或者关键字的某个线性函数的值为哈希函数，比如H(key) = key或者H(key) = a * key + b 数字分析法：对于可能出现的数值全部了解，取关键字的若干数位组成哈希地址 平方取中法：取关键字平方后的中间几位作为哈希地址 折叠法：将关键字分割成为位数相同的几部分（最后一部分的位数可以不同），取这几部分的叠加和（舍去进位），作为哈希地址。 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即hash(k)=k mod p，p< =m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。 随机数法：取关键字的随机函数值作为它的哈希地址。 但是这些方法，都无法避免哈希冲突，只能有意识的减少。那处理hash冲突，一般有哪些方法呢？ 开放地址法：hash计算后，如果该位置已经有数据，那么对该地址+1，也就是往后找，知道找到一个空的位置。 重新hash法：发生哈希冲突后，可以使用另外的hash函数重新极计算，找到空的hash地址,如果有，还可以再叠加hash函数。 链地址法：所有hash值一样的,链接成为一个链表，挂在数组后面。 建立公共溢出区：不常见，意思是所有元素，如果和表中的元素hash冲突，都弄到另外一个表，也叫溢出表。 Java里面，用的就是链地址法：红黑树 ，红黑树有一定的规则去平衡子树，避免退化成为链表，影响查询效率。树 树是一种数据结构，它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。(百度百科) 节点的度：一个节点含有的子树的个数称为该节点的度 树的度：一棵树中，最大的节点度称为树的度； 叶节点或终端节点：度为零的节点； 非终端节点或分支节点：度不为零的节点； 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 兄弟节点：具有相同父节点的节点互称为兄弟节点； 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推； 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0； 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0； 堂兄弟节点：父节点在同一层的节点互为堂兄弟； 节点的祖先：从根到该节点所经分支上的所有节点； 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 有序树：将树种的节点的各个子树看成从左至右是有次序的（不能互换），则应该称该树为有序树，否则为无序树 第一个孩子：在有序树中最左边的子树的根称为第一个孩子 最后一个孩子：在有序树种最右边的子树的根称为最后一个孩子 森林：由m（m>=0）棵互不相交的树的集合称为森林； 树，其实我们最常用的是二叉树：public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
} 前序遍历：遍历顺序 根节点 --> 左子节点 --> 右子节点 中序遍历：遍历顺序 左子节点 --> 根节点 --> 右子节点 后序遍历：遍历顺序 左子节点 --> 右子节点 --> 根节点 广度 / 层次遍历： 从上往下，一层一层的遍历 如果是一棵混乱的二叉树，那查找或者搜索的效率也会比较低，和一条混乱的链表没有什么区别，何必弄更加复杂的结构呢？二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。平衡二叉搜索树的任何结点的左子树和右子树高度最多相差1。平衡二叉树也称为 AVL 树。红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 [1]
红黑树是在1972年由[Rudolf Bayer](https://baike.baidu.com/item/Rudolf Bayer/3014716)发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 [2]
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 性质1. 结点是红色或黑色。 性质2. 根结点是黑色。 性质3. 所有叶子都是黑色。（叶子是NIL结点） 性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点） 性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。 正是这些特性，让红黑树在调整的时候，不像普通的平衡二叉树调整那般困难，频繁。也就是加上了条条框框，让它符合一定的标准，减少平衡过程的混乱以及频次。970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：m/2 - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：m/2 <= k <= m ；
4、所有的叶子结点都位于同一层。B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下:
(1)每个结点至多有m个子女；
(2)除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女；
(3)有k个子女的结点必有k个关键字。一般b+树的叶子节点，会用链表连接起来，方便遍历以及范围遍历。 b+树的中间节点不保存数据，每次IO查询能查到更多的索引，,是一个矮胖的树。 对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要从根节点都叶子节点。 除了上面的树，其实还有一种叫Huffman树：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。堆 大顶堆：每个节点都大于等于其子树节点（堆顶是最大值） 小顶堆：每个节点都小于等于其子树节点（堆顶是最小值） 一般情况下，我们都是用数组来表示堆，比如下面的小顶堆： i 结点的父结点 parent = floor((i-1)/2) (向下取整) i 结点的左子结点 2 * i +1 i 结点的右子结点 2 * i + 2 既然是存储数据的，那么一定会涉及到插入删除等操作，堆里面插入删除，会涉及到堆的调整，调整之后才能重新满足它的定义，这个调整的过程，叫做堆化 。 还是完全二叉树 堆中每一个节点都还小于等于其左右子节点 对于小顶堆，调整的时候是：小元素往上浮，大元素往下沉，就是不断交换的过程。图 顶点：图最基本的单元，那些节点 边：顶点之间的关联关系 相邻顶点：由边直接关联的顶点 度：一个顶点直接连接的相邻顶点的数量 权重：边的权值 一般表示图有以下几种方法： 邻接矩阵，使用二维数组表示，为1 表示联通，0表示不连通，当然如果表示路径长度的时候，可以用大于0的数表示路径长度，用-1表示不连通。 下面的图片中，0和 1，2连通，我们可以看到第 0行的第1，2列是1 ，表示连通。还有一点：顶点自身我们是标识了0，表示不连通，但是有些情况可以视为连通状态。邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。直接相关 的顶点，一般借助队列实现。而深度优先遍历则是往一个方向一直走到不能再走，有点不撞南墙不回头的意思，一般使用递归实现。一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。秦怀@观点 为了编写出一个”好“的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系，这就是”数据结构“这门学科和发展的背景。【作者简介】 ：秦怀杂货店 】作者，个人网站：http://aphysia.cn，技术之路不在一时，山高水长，纵使缓慢，驰而不息。 
游戏开发
发布于：2022-02-04 11:30
|
阅读数：361
|
评论：0
QQ好友和群
QQ空间
