Смоделированная односвязанная таблица
Линейная таблица:
Линейные таблицы (также называемые последовательными таблицами) являются наиболее простыми и наиболее часто используемыми структурами данных.
Взаимосвязь между элементами данных в линейной таблице представляет собой взаимосвязь один к одному, то есть за исключением первого и последнего элементов данных, другие элементы данных подключены к концу.
Логическая структура линейных таблиц проста, которую легко реализовать и эксплуатировать.
В практических приложениях линейные таблицы используются в виде специальных линейных таблиц, таких как стеки, очереди и строки.
Основные характеристики линейной структуры:
1. В коллекции должен быть уникальный «первый элемент»;
2. В коллекции должен быть уникальный «последний элемент»;
3. За исключением последнего элемента, есть уникальный преемник (последний пункт);
4. За исключением первого элемента, есть уникальный передний привод (передний кусок).
Связанный список: связанный список
Связанный список-это непрерывная и не последовательная структура хранения на физическом хранении. Логический порядок элементов данных заключается в том, что каждый элемент данных, реализованный через порядок ссылки указателя в связанном списке, содержится в «точке ссылки».
Ссылка является объектом класса, и этот тип можно назвать ссылкой. В связанном списке есть много аналогичных ссылок, и каждая ссылка содержит поле, в следующем ссылке, ссылка на следующую ссылку.
Сам объект связанного списка содержит ссылку на первый узел ссылки. (Если в первую очередь его нельзя найти)
Связанный список не может непосредственно получить доступ к элементам данных напрямую, таким как массив (с использованием подписок), но должен быть расположен с взаимосвязи между данными, то есть доступа к следующей ссылке, на которую ссылается узлом ссылки, а затем следующим, пока доступ к необходимым данным не будет доступно, а временная сложность вставки и удаления необходимых данных в голове не станет O (1), потому что только ссылка, указывающая на то, чтобы определить, и все, что определяет. Эти операции требуют среднего поиска половины узлов в связанном списке, с эффективностью O (n).
Один связанный список:
Линейная таблица представлена «последовательности узлов» и называется линейным связанным списком (один связанный список)
Это структура данных доступа к цепочке с использованием набора единиц хранения с произвольными адресами для хранения элементов данных в линейной таблице. (Этот набор ячеек памяти может быть либо непрерывной, либо прерывистой)
Структура узла ссылки:
Данные поля данных, которые хранят значения узлов; Поле указателя (цепное поле), которое хранит ссылку на узл.
Связанный список связывает N -узлы линейной таблицы вместе в своем логическом порядке через домен ссылки каждого узла.
Связанный список с одним полем ссылки на узел называется одним списком ссылок. В одном направлении есть только ссылки на последующие узелки.
/*** Одиночный список: метод вставки заголовка и первый выход* Левая сторона связанного списка называется цепной головкой, а правая сторона называется цепной хвостом. * Метод вставки заголовка для создания одного связанного списка получен путем просмотра правого конца связанного списка в качестве фиксированного, а связанный список продолжает расширяться влево. * Первое, что происходит из метода вставки заголовка, - это хвостовой узел * @author Stone */ public Class SingleLinkedList <T> {Private Link <T> First; // Первый узел public singleLinkedList () {} public boolean isempty () {return first == null; } public void insertFirst (t data) {// вставить в голову цепной ссылки <t> newLink = new Link <T> (data); newlink.next = первое; // Следующий из нового узла указывает на предыдущий узел First = newlink; } public Link <T> deleteFirst () {// Удалить ссылку заголовка цепи <T> temp = First; First = First.Next; // Измените первый узел, чтобы вернуть температуру; } public Link <t> find (t t) {link <t> find = first; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} return find; } public Link <T> delete (t t) {if (isempty ()) {return null; } else {if (first.data.equals (t)) {link <t> temp = first; First = First.Next; // изменить первый узел на следующий узел возврата; }} Link <t> p = First; Ссылка <T> Q = первое; while (! p.data.equals (t)) {if (p.next == null) {// подписаться на конец цепи, но не найденный возврат null; } else {q = p; p = p.next; }} Q.next = p.next; возврат P; } public void DisplayList () {// Transip System.out.println ("list (first-> last):"); Ссылка <T> current = First; while (current! = null) {current.displaylink (); current = current.next; }} public void displayListerSe () {// обратная связь пересечения <T> p = первое, q = first.next, t; while (q! = null) {// Указатель изменен, порядок прохождения данных обратно t = q.next; // no3 if (p == Сначала) {// Когда это исходный заголовок, .next головы должно быть пустым p.next = null; } Q.next = p; // no3 -> no1 pointer обратный p = q; // старт - это обратный Q = t; // NO3 Start} // В IF в цикле выше, First.Next пуст, и когда Q является нулевым и не выполняет цикл, P является исходным наибольшим элементом данных. После инверсии P назначается First = P; DisplayList (); } class link <t> {// точка ссылки t data; // Ссылка поля данных <T> Далее; // Последующий указатель, цепочка узла Link (t Data) {this.data = data; } void displayLink () {System.out.println ("Данные" + data.tostring ()); }} public static void main (string [] args) {singleLinkedList <integer> list = new SingLeLinkedList <Integer> (); list.insertfirst (33); list.insertfirst (78); list.insertfirst (24); list.insertfirst (22); list.insertfirst (56); list.displaylist (); list.deletefirst (); list.displaylist (); System.out.println ("find:" + list.find (56)); System.out.println ("find:" + list.find (33)); System.out.println ("DELETE FIEND:" + list.delete (99)); System.out.println ("DELETE FIEND:" + list.delete (24)); list.displaylist (); System.out.println ("--- Реверс ----"); list.displaylistreverse (); }}Печать
Список (первый-> последний): данные равны 56 Данные 22. Данные 24 Данные 78 Данные-33 список (первое-> последнее): Данные 22 Данные 24 Данные 78 Данные-33 Найти: NULL FID: LINKED_LIST.SingLinkedList $ Найдите: linked_list.singlelinkedlistlistdlink@17dfafd1 (первое-> последнее): данные 22.
Один связанный список: метод вставки хвостовой вставки, обратно в первый раз - если левый конец связанного списка исправлен, связанный список продолжает расширяться вправо, этот метод установления связанного списка называется методом вставки хвоста.
При создании связанного списка с методом вставки хвоста установлен указатель головы, поэтому необходимо настроить указатель хвоста, чтобы расширить справа от связанного списка.
Первое, что происходит из метода вставки хвоста, - это головкий узел.
открытый класс SingLeLinkedList2 <T> {частная ссылка <T> Head; // Первый узел public singleLinkedList2 () {} public boolean isempty () {return head == null; } public void insertlast (t data) {// вставить ссылку <t> newlink = new Link <T> (data); if (head! = null) {link <t> nextp = head.next; if (nextp == null) {head.next = newlink; } else {link <t> задний = null; while (nextp! = null) {buld = nextp; nextp = nextp.next; } BERT.NEXT = NEWLINK; }} else {head = newlink; }} public link <t> deletelast () {// Удалить хвост цепной ссылки <t> p = head; Ссылка <T> Q = HEAD; while (p.next! = null) {// Следующий узел P не пуст, Q равен текущему P (то есть Q - это предыдущий, а P - следующий). Когда петля заканчивается, Q равен предпоследому концу цепи Q = P; p = p.next; } // Удалить Q.next = null; возврат P; } public link <T> find (t t) {link <t> find = head; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} return find; } public Link <T> delete (t t) {if (isempty ()) {return null; } else {if (head.data.equals (t)) {link <t> temp = head; Head = Head.next; // Измените первый узел, чтобы вернуть температуру; }} Link <t> p = Head; Ссылка <T> Q = HEAD; while (! p.data.equals (t)) {if (p.next == null) {// означает, что возврат нуль не был найден в конце цепи; } else {q = p; p = p.next; }} Q.next = p.next; возврат P; } public void displaylist () {// Travel System.out.println ("list (head-> last):"); Ссылка <T> current = Head; while (current! = null) {current.displaylink (); current = current.next; }} public void DisplayListerSe () {// обратная связь пересечения <T> p = head, q = head.next, t; while (q! = null) {// Указатель изменен, и порядок обновления данных обратно t = q.next; // no3 if (p == head) {// Когда это исходный заголовок, .next головы должно быть пустым p.next = null; } Q.next = p; // no3 -> no1 pointer обратный p = q; // старт - это обратный Q = t; // no3 start} // В IF в цикле выше, Head.Next пуст, когда Q является нулевым и не выполняет цикл, P - исходный большинство элементов данных. После инверсии P назначается головке = P; DisplayList (); } class link <t> {// точка ссылки t data; // Ссылка домена данных <T> Далее; // Последовательный указатель, цепочка узлов Link (t Data) {this.data = data; } void displayLink () {System.out.println ("Данные" + data.tostring ()); }} public static void main (string [] args) {singleLinkedList2 <Integer> list = new SingleLinkedList2 <Integer> (); list.insertlast (33); list.insertlast (78); list.insertlast (24); list.insertlast (22); list.insertlast (56); list.displaylist (); list.deletelast (); list.displaylist (); System.out.println ("find:" + list.find (56)); System.out.println ("find:" + list.find (33)); System.out.println ("DELETE FIEND:" + list.delete (99)); System.out.println ("Удалить находить:" + list.delete (78)); list.displaylist (); System.out.println ("---- Обратный -----"); list.displaylistreverse (); }}Печать
Список (Head-> Last): Данные равны 33 Данные 78 Данные 24 Данные-22 Данные-56 Список (Head-> Last): данные равны 33 Данные 78 Данные-24 Данные 22 Найти: nul Найти: linked_list.singlelinkedlist2dlink@17dfafd1 (Head-> Last): данные равны 33 Данные 24.
Моделируйте двойной связанный список для реализации стека и очередей с связанными списками
Связанный список с двойным знаком:
Двойной связанный список очень похож на традиционный список связанного списка. У него добавлен только новый атрибут - то есть ссылка на последнюю ссылку сзади.
Таким образом, вставка в конце цепи станет очень легким. Просто измените следующую часть задней части на недавно добавленный узел, без зацикливания на поиск последнего узла, так что есть вставка и вставка
При удалении заголовка цепи вам нужно изменить точку отсчета; При удалении цепного хвоста вам нужно опустошить следующий узел предпоследнего узла.
Нет ссылок, поэтому для прочтения операции требуется цикл
/ *** Двойной связанный список* @author Stone*/ public class TwoEndPointList <T> {Private Link <T> Head; // Первый узел частной ссылки <t> задняя часть; // хвост public twoEndpointlist () {} public t peekhead () {if (head! = null) {return head.data; } return null; } public boolean isempty () {return head == null; } public void insertFirst (t data) {// вставить в голову цепной ссылки <t> newLink = new Link <T> (data); newlink.next = Head; // Следующее из нового узла указывает на предыдущий узел Head = NewLink; } public void insertlast (t data) {// вставить ссылку <t> newlink = new Link <T> (data); if (head == null) {upt = null; } if (bull! = null) {bul.next = newlink; } else {head = newlink; Head.next = задний; } buld = newlink; // в следующий раз, когда вы вставите, вставьте с задней части} public t deletehead () {// Удалить заголовок цепи if (isempty ()) return null; Ссылка <T> temp = Head; Head = Head.next; // Измените первый узел на следующий узел if (head == null) {<span style = "Белое пространство: pre"> </span> worm = head; } return temp.data; } public t Найти (t t) {if (isempty ()) {return null; } Link <t> find = head; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} if (find == null) {return null; } return find.data; } public t удалить (t t) {if (isempty ()) {return null; } else {if (head.data.equals (t)) {link <t> temp = head; Head = Head.next; // Измените первый узел на следующий узел return temp.data; }} Link <t> p = Head; Ссылка <T> Q = HEAD; while (! p.data.equals (t)) {if (p.next == null) {// Укажите, что возврат нуль не был найден в конце цепи; } else {q = p; p = p.next; }} Q.next = p.next; вернуть P.Data; } public void displaylist () {// Travel System.out.println ("list (head-> last):"); Ссылка <T> current = Head; while (current! = null) {current.displaylink (); current = current.next; }} public void displayListerse () {// обратный обход if (isempty ()) {return; } Link <t> p = head, q = head.next, t; while (q! = null) {// Указатель изменен, и порядок обновления данных обратно t = q.next; // no3 if (p == head) {// Когда это исходная голова, .next головы должно быть пустым p.next = null; } Q.next = p; // no3 -> no1 pointer обратный p = q; // старт - это обратный Q = t; // NO3 Start} // В IF в цикле выше, Head.Next пуст, а когда Q является нулевым и не выполняет цикл, P - исходный большинство элементов данных. После инверсии P назначается головке = P; DisplayList (); } class link <t> {// link node t data; // Ссылка домена данных <T> Далее; // Последовательный указатель, цепочка узлов Link (t Data) {this.data = data; } void displayLink () {System.out.println ("Данные" + data.tostring ()); }} public static void main (string [] args) {TwoEndPointList <Integer> list = new TwoEndPointList <Integer> (); list.insertlast (1); list.insertfirst (2); list.insertlast (3); list.insertfirst (4); list.insertlast (5); list.displaylist (); list.deletehead (); list.displaylist (); System.out.println ("find:" + list.find (6)); System.out.println ("find:" + list.find (3)); System.out.println ("DELETE FIEND:" + list.delete (6)); System.out.println ("DELETE FIEND:" + list.delete (5)); list.displaylist (); System.out.println ("--- Реверс ----"); list.displaylistreverse (); }}Печать
Список (Head-> Last): данные равны 4 Данные: 2 Данные: 1 Данные-3 Данные-это 5 списка (Head-> Last): Данные равны 2 Данные: 1 Данные-3 Данные-5 Найти: NULL Найдите: 3 Удалить Найдите: NULL Удалить. Найдите: 5 Список (Head-> Последние): Данные 2 Данные 1 Данные 3 --- Обратные.
Используйте связанные списки для реализации стека, и используйте отдельный список связанного списка перед его вставкой.
Этот класс использует двойной связанный список для реализации:
открытый класс LinkStack <T> {private TwoEndPointList <T> DATAS; public linkstack () {datas = new TwoEndPointList <t> (); } // Поместите в стек public void push (t data) {datas.insertfirst (data); } // выпустить стек public t pop () {return datas.deletehead (); } // Проверьте верхнюю часть стека public t peek () {return data.peekhead (); } // Является ли стек пустым общедоступным логическим iSempty () {return data.isempty (); } public static void main (string [] args) {linkstack <Integer> Stack = new Linkstack <integer> (); for (int i = 0; i <5; i ++) {Stack.push (i); } for (int i = 0; i <5; i ++) {integer peek = stack.peek (); System.out.println ("peek:" + peek); } for (int i = 0; i <6; i ++) {integer pop = stack.pop (); System.out.println ("pop:" + pop); } System.out.println ("----"); for (int i = 5; i> 0; i--) {Stack.push (i); } for (int i = 5; i> 0; i--) {integer peek = stack.peek (); System.out.println ("peek:" + peek); } for (int i = 5; i> 0; i--) {integer pop = Stack.pop (); System.out.println ("pop:" + pop); }}}Печать
PEEK: 4 PEEK: 4 PEEK: 4 PEEK: 4 PEEK: 4 PEEK: 4 POP: 4 POP: 3 POP: 2 POP: 1 POP: 1 POP: 0 POP: NULL --- PEEK: 1 PEEK: 1 PEEK: 1 PEEK: 1 POP: 1 POP: 1 POP: 2 POP: 4 POP: 5
Связанная очередь реализации списка реализована с использованием двойного связанного списка:
открытый класс linkqueue <t> {private twoendpointlist <t> list; public linkqueue () {list = new TwoEndPointList <T> (); } // Вставить хвост очереди public void insert (t data) {list.insertlast (data); } // Удалить голову команды public t remove () {return list.deletehead (); } // Посмотреть главу команды Public t Peek () {return List.peekhead (); } public boolean isempty () {return list.isempty (); } public static void main (string [] args) {linkqueue <Integer> queue = new Linkqueue <Integer> (); for (int i = 1; i <5; i ++) {queue.insert (i); } for (int i = 1; i <5; i ++) {integer peek = queue.peek (); System.out.println ("peek:" + peek); } for (int i = 1; i <5; i ++) {integer remove = queue.remove (); System.out.println ("удалить:" + remove); } System.out.println ("----"); for (int i = 5; i> 0; i--) {queue.insert (i); } for (int i = 5; i> 0; i--) {integer peek = queue.peek (); System.out.println ("peek2:" + peek); } for (int i = 5; i> 0; i--) {integer remove = queue.remove (); System.out.println ("удалить:" + remove); }}}Печать
PEEK: 1 PEEK: 1 PEEK: 1 PEEK: 1 PEEK: 1 Снимите: 1 Снимите: 2 Снимите: 3 Снимите: 4 --- Peek2: 5 Peek2: 5 Peek2: 5 Peek2: 5 Peek2: 5 Снимите: 5 Снимите: 4 Снимите: 3 Удалите: 2 Удалите: 1