Анализ и реализация общей структуры данных
иллюстрировать
- Код в этой статье относится к учебному заведению "Java Programming Ideas".
- код в текстеGithubТеперь, если вам интересно, вы можете посмотреть. Нажмите на звездочку, чтобы поощрить меня.
- Код был набран в Sublime, жалкий GBK, много китайских комментариев аннотировано, а перекодировку использовать нельзя! ! !
- Основное внимание уделяется идеям, а не реализации. Я снова рекомендую «Идеи программирования на Java».
1. Структура данных
Суть программирования заключается в обработке данных (информация существует в виде данных).В реальном программировании необходимо обрабатывать большое количество данных.Поэтому эти данные должны быть проанализированы и обработаны до фактического программирования, и связь между данные должны быть обработаны.
Между фактическими элементами данных существует сложная логическая взаимосвязь, и необходимо принять подходящую физическую структуру для хранения данных и выполнения соответствующих операций с данными на основе этого. В то же время следует также проанализировать временные и пространственные издержки этих структур данных.Этот вид знаний, который специализируется на изучении логической связи между данными в приложении, методом хранения и его операцией, называется структурой данных.
Связи, существующие между элементами данных, называются данными.логическая структураПодводя итог, можно выделить примерно следующие четыре основные логические структуры:
- Коллекция: существует только отношение «принадлежность к одной коллекции» между элементами данных.
- Линейная связь: существует связь один к одному между элементами данных.
- Древовидная структура: между элементами данных существует отношение «один ко многим».
- График или сетка. Между элементами данных существует связь «многие ко многим».
Карта мозга:
Картинка>Код>Текст,я лично это понимаю.Если вы можете использовать картинки для объяснения проблемы,не используйте код.Так же попробуйте использовать код+текст для объяснения сути проблемы.
Для одной и той же логической структуры внизу обычно находятся две физические структуры хранения:
- Последовательные структуры хранения, такие как одномерные массивы
- Непоследовательные структуры хранения, такие как цепные структуры хранения (связанные списки), хэши
Последовательная структура подходит для операций чтения (почему? Потому что есть индекс), а хранилище связанных списков подходит для операций записи (почему? Отключение, добавление узлов для завершения, базовая репликация не требуется).
Дизайн алгоритма зависит от логической структуры: реализация алгоритма зависит от структуры хранения. Дизайн объекта зависит от структуры класса, (...)
Каков результат данных? Структуру данных можно описать в трех аспектах:
- Объективные связи между элементами данных (логическая структура)
- Как данные хранятся внутри компьютера (структура хранения)
- Эффективные операции и обработка данных (алгоритм)
Связь между объектами (абстракция реальности, наследование? композиция?), где они хранятся в памяти, в куче и как? существуют в массиве? хеш-таблица? Как вы с этим справились? Добавлять, удалять, изменять, проверять, сортировать, шифровать и расшифровывать,
Stack
Для обычных линейных таблиц он действует как контейнер для данных с аналогичными результатами.
- Разделяется на механизм последовательного хранения и цепную структуру хранения
- Вставка, удаление и сортировка операций
- Если линейный список позволяет добавлять и удалять элементы на одном конце линейного списка, он превращается в: стеки и очереди. (первым пришел, последним вышел (журнал), первым пришел, первым ушел (в очереди на вокзале))
Следующие картинки взяты из Википедии (не читайте Википедию)
Простите тех, кто не поставил хоррор, от Google (не используйте 100 X)
Стек — это специальная линейная таблица, которую можно вставлять и удалять только на фиксированном конце (конце линейной таблицы).
- Один конец, который позволяет операции вставки и удаления, является вершиной стека, а другой конец, как вы уже догадались? (Нижний)
- Push: Процесс вставки элемента в стек, длина стека + 1, (нажатие маркера)
- Pop: Процесс удаления элемента, длина стека -1.(Pop запуск...)
- Первый пришел, последний вышел или последний пришел, первый вышел.
- Общие операции: инициализация, (по мере удаления кадра стека метод выполняется. Может появитьсяstackoverflow.com/),++i,i++,
- Отношения наследования в Java, стек наследует от вектора, списка (abstractList?)
нужно: Пожалуйста, напишите код для реализации класса Stack, который может реализовать функцию стека LIFO. Необходимые методы включают:
- Stack(int) создает экземпляр стека указанной глубины
- boolean push(E item) помещает объект как вершину стека, возвращает true в случае успеха и возвращает false, если стек заполнен
- E pop() удаляет объект из вершины стека и возвращает значение null, если оно пустое.
- E peek() Просматривает и возвращает объект в верхней части стека, возвращает ноль, если он пуст
- int size() возвращает текущее количество элементов в стеке
- int depth() возвращает текущую глубину стека
Злая кодировка символов, крайне удручающаяВесь приведенный ниже код относится к сети и написан на Sublime.
На основе реализации одной таблицы:
class Node<E> {
Node<E> next = null;
E data;
public Node(E data) {
this.data = data;
}
}
//采用单链表实现栈
public class MyStack<E> {
int depth; //栈的深度
public MyStack(int i) {
this.depth = i;
}
Node<E> top = null;
//将元素压入栈中
public boolean push(E data) {
if(size() < depth) {
Node<E> newNode = new Node<E>(data);
newNode.next = top;
top = newNode;
return true;
}
return false;
}
//读取栈中的头节点，不删除头节点
public E peek() {
if(top ==null) {
return null;
}
return top.data;
}
//获取栈中的头节点，并删除头节点
public E pop() {
if(top ==null) {
return null;
}
Node<E> tmp = top;
top = top.next;
return tmp.data;
}
//栈的元素个数
public int size() {
int len = 0;
Node tmeNode = top;
while(tmeNode != null) {
tmeNode = tmeNode.next;
len++;
}
return len;
}
//当前栈的深度
public int depth() {
return this.depth;
}
public static void main(String[] args) {
MyStack stack = new MyStack(2);
System.out.println(stack.push(1));
System.out.println(stack.push(2));
System.out.println(stack.push(3));
System.out.println("栈的元素个数： " +stack.size());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println("栈的元素个数： " + stack.depth());
}
}
---------------------------此代码来自《Java编程思想》----------------------------------
import java.util.LinkedList;
public class Stack<T> {
private LinkedList<T> storage = new LinkedList<T>();
public void push(T v) { storage.addFirst(v); }
public T peek() { return storage.getFirst(); }
public T pop() { return storage.removeFirst(); }
public boolean empty() { return storage.isEmpty(); }
public String toString() { return storage.toString(); }
}
Давайте взглянем на другую реализацию большого парня, она проста и понятна.
public class LinkedStack<T> {
private static class Node<U> {
U item;
Node<U> next;
Node() {
item = null;
next =null;
}
Node(U item,Node<U> next) {
this.item = item;
this.next = next;
}
boolean end() {
return item == null && next == null;
}
}
private Node<T> top = new Node<T>();
public void push(T item) {
top = new Node<T>(item,top);
}
public T pop() {
T result = top.item;
if (!top.end()) {
top = top.next;
}
return result;
}
public static void main(String[] args) {
LinkedStack<String> lss = new LinkedStack<String>();
for (String s : "Phasers on stun!".split(" ") )
lss.push(s);
String s;
while((s = lss.pop()) != null)
System.out.println(s);
}
}
输出如下：
I:\Java\note\sort\code>java LinkedStack
stun!
on
Phasers
Queue
Очередь, также специальная линейная таблица, использует фиксированный конец для вставки данных, а другой конец — для удаления данных.
- «Первым пришел – первым ушел», как стоять в очереди за билетами на вокзале! ! ! , вся команда движется вперед.
- Разделяется на последовательную структуру очереди и структуру цепной очереди
- Начиная с JDK 5, Java Collection Framework предоставляет интерфейс Queue, и классы, реализующие этот интерфейс, могут использоваться в качестве очередей, например LinkedBlockingQueue и PriorityBlockingQueue.
- Блокирующие очереди могут быть реализованы с помощью механизмов опроса и ожидания-уведомления.
Конкретная реализация очереди:
import java.util.*;
public class SimpleQueue<T> implements Iterable<T> {
private LinkedList<T> storage = new LinkedList<T>();
public void add(T t){
storage.offer(t);
}
public T get() {
return storage.poll();
}
public Iterator<T> iterator() {
return storage.iterator();
}
public static void main(String[] args) {
SimpleQueue queue = new SimpleQueue();
queue.add(8);
System.out.println(queue.get());
}
}
Давайте посмотрим, как реализовать Queue with Stack, очень хорошо, "Идеи программирования на Java"
import java.util.Stack;
public class MyQueue{
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> stackTmp = new Stack<Integer>();
//Push element X to the back of queue
public void push(int x) {
stack.push(x);
}
//Removes the element form in front of queue
public void pop() {
if (stackTmp.isEmpty()) {
while (!stack.isEmpty()) {
int tmp = stack.peek();
stackTmp.push(tmp);
stack.pop();
}
}
else {
stackTmp.pop();
}
}
//Get the front element
public int peek() {
if (!stackTmp.isEmpty()) {
int tmp = stack.peek();
stackTmp.push(tmp);
}
return stackTmp.peek();
}
//Return whether the queueis empty
public boolean empty() {
if (stackTmp.isEmpty() && stack.isEmpty()) {
return true;
}else {
return false;
}
}
public static void main(String[] args) {
MyQueue queue = new MyQueue();
queue.push(8);
System.out.println(queue.empty()); //false
}
}
Tree
Дерево также является нелинейной структурой данных, и элементы в этой структуре имеют отношения «один ко многим».
-
Широко используются деревья, особенно бинарные деревья, сортированные бинарные деревья, сбалансированные бинарные деревья и красно-черные деревья.
-
Двоичное дерево на основе обычных деревьев позволяет каждому узлу в дереве содержать не более двух дочерних узлов и строго отличать левый дочерний узел от правого дочернего узла (положение нельзя изменить). - Пройдите бинарное дерево, подумайте о глубоком чтении и сначала пройдите. (обход в прямом порядке, обход по порядку, последующий обход) и обход в ширину.
-
Дерево Хаффмана , двоичное дерево с кратчайшим взвешенным путем, полезное для поиска информации.
-
Кодирование Хаффмана, предполагая, что строка, такая как «abcabcabc», должна быть закодирована, преобразована в уникальный двоичный код, и требуется минимальная длина преобразованного двоичного кода. Дерево Хаффмана можно использовать для решения проблемы кодирования сообщений
-
Сортированное бинарное дерево: специальное бинарное дерево, которое может легко сортировать и извлекать все узлы в дереве.
Двоичное дерево, здесь принимает идею рекурсии и внутреннего класса.
public class BinaryTree {
private Node root;
//添加节点
public void add(int data) {
if (root ==null) {
root = new Node(data);
}else {
root.addNode(data);
}
}
//打印节点
public void print() {
root.printNode();
}
private class Node {
private int data;
private Node left;
private Node right;
public Node(int data) {
this.data = data;
}
public void addNode(int data) {
//核心思想就是进来先个当前节点比，如果如果小于则在左边添加，如果左边没子节点，则创建，如果有添加
if (this.data > data) {
if (this.left == null) {
this.left = new Node(data);
}else {
this.addNode(data); //这里应该是采用递归。
}
}else {
if (this.right == null) {
this.right = new Node(data);
}else {
this.right.addNode(data);
}
}
}
//中序遍历
public void printNode() {
if (this.left != null) {
this.left.printNode();
}
System.out.println(this.data + "->");
if (this.right !=null) {
this.right.printNode();
}
}
}
}
------------------------测试-----------------------------------------------
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
// 8、3、10、1、6、14、4、7、13
bt.add(8);bt.add(3);bt.add(10);
bt.add(1);bt.add(6);bt.add(14);
bt.add(4);bt.add(7);bt.add(13);
bt.print();
}
输出：
1->3->4->6->7->8->10->13->14->
LinkedList
ArrayList наполовину написан из-за искаженных символов. Я беспомощен. Он полностью меня обманывает. Идея состоит в том, чтобы судить, выходит ли он за пределы, на основе индекса, когда он включает расширение. Неважно здесь. Просто посмотрите на LinkedList.
public class MyLinkedList {
protected Node first; // 链表的第一个节点
protected Node last; // 链表的最后一个节点
private int size; // 节点的数量
// 链表中的每一个节点
public class Node {
public Node(Object ele) {
this.ele = ele;
}
Node prev; // 上一个节点对象
Node next; // 下一个节点对象
public Object ele; // 当前节点中存储的数据
}
public void addFirst(Object ele) {
Node node = new Node(ele); //需要保存的节点对象
//进来一个节点，如果为空的话，它可定时第一个，也是最后一个
if (size == 0) {
this.first = node;
this.last = node;
}else {
node.next = this.first; // 把之前第一个作为新增节点的下一个节点，(进来一个，当前的只能当老二了。)
this.first.prev = node; // 把新增节点作为之前第一个节点的上一个节点
this.first = node; // 把新增的节点作为第一个节点
}
size++;
}
//这里很重要，别忘记
public void addLast(Object ele) {
Node node = new Node(ele);
if (size == 0) {
this.first = node;
this.last = node;
}else {
this.last.next = node; // 新增节点作为之前最后一个节点的下一个节点(因为是加在后面，所以当前节点的下一个才是 新增节点)
node.prev = this.last; // 之前最后一个节点作为新增节点的上一个节点
this.last = node; // 把新增的节点作为最后一个节点
}
}
//原谅我复制了
public void remove(Object ele) {
// 找到被删除的节点
Node current = this.first;// 确定为第一个节点,从头到尾开始找
for (int i = 0; i < size; i++) {
if (!current.ele.equals(ele)) {// 当前为true !true 为false ,说明找到当前ele,输出
if (current.next == null) { // 续上: 如果false取反为true, 判断是否最后一个,
return;
}
current = current.next;
}
}
//删除节点
if(current==first){
this.first = current.next; //当前的下一个作为第一个
this.first.prev = null; //当前下一个对上一个的引用设置为null
}else if(current==last){
this.last = current.prev;
this.last.next = null;
}else{
//把删除当前节点的下一个节点作为删除节点的上一个节点的next
current.prev.next =current.next;
//把删除节点的上一个节点作为删除节点下一个节点的prev
current.next.prev = current.prev;
}
size--;
//System.out.println("current =" + current.ele);
}
public String toString() {
if (size == 0) {
return "[]";
}
StringBuilder sb = new StringBuilder(size * 2 + 1);
Node current = this.first;// 第一个节点
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(current.ele);
if (i != size - 1) {
sb.append(",");
} else {
sb.append("]");
}
current = current.next; // 获取自己的下一个节点
}
return sb.toString();
}
}
Этот двусторонний список немного сложно понять, давайте посмотрим на картинку,
Линейный связанный список:
Двусвязный список:
Иди сюда первым, гогого, возможность зарезервирована для тех, кто готов,