Пиши Дома Нужные Работы

Обратная связь

Динамические структуры. Односвязанный список

Рассмотрим реализацию простого связанного списка

Список поддерживает следующие операции:

· Вставка элемента в начале списка

· Удаление элемента в начале списка

· Перебор списка для вывода содержимого

 

Класс Link- предназначен для хранения данных. Класс описывает узел списка

Полное определение класса Link выглядит так:

import java.io.*;

 

////////////////////////////////////////////////////////////////

class Link

{

public int iData; // data item (key)

public double dData; // data item

public Link next; // next link in list

// -------------------------------------------------------------

public Link(int id, double dd) // constructor

{

iData = id; // initialize data

dData = dd; // (‘next’ is automatically

} // set to null)

// -------------------------------------------------------------

public void displayLink() // display ourself

{

System.out.print(“{“ + iData + “, “ + dData + “} “);

}

} // end class Link

////////////////////////////////////////////////////////////////

 

В классе LinkList описаны методы для работы со списком:

 

class LinkList

{//указатель на 1 элемент

private Link first; // ref to first link on list

// -------------------------------------------------------------

public LinkList() // constructor

{

first = null; // no items on list yet

}

// -------------------------------------------------------------

//проверка. Является ли список пустым

public boolean isEmpty() // true if list is empty

{

return (first==null);

}

// -------------------------------------------------------------

// insert at start of list

// вставить в начало списка

public void insertFirst(int id, double dd)

{ // make new link

Link newLink = new Link(id, dd);

newLink.next = first; // newLink --> old first

first = newLink; // first --> newLink

}

// -------------------------------------------------------------

public Link deleteFirst() // delete first item

{ // (assumes list not empty)

Link temp = first; // save reference to link

first = first.next; // delete it: first-->old next

return temp; // return deleted link

}

// -------------------------------------------------------------

public void displayList()

{

System.out.print(“List (first-->last): “);

Link current = first; // start at beginning of list

while(current != null) // until end of list,

{

current.displayLink(); // print data

current = current.next; // move to next link



}

System.out.println(“”);

}

// -------------------------------------------------------------

} // end class LinkList

////////////////////////////////////////////////////////////////

Основная программа

 

class LinkListApp

{

public static void main(String[] args)

{

LinkList theList = new LinkList(); // make new list

theList.insertFirst(22, 2.99); // insert four items

theList.insertFirst(44, 4.99);

theList.insertFirst(66, 6.99);

theList.insertFirst(88, 8.99);

theList.displayList(); // display list

while( !theList.isEmpty() ) // until it’s empty,

{

Link aLink = theList.deleteFirst(); // delete link

System.out.print(“Deleted “); // display it

aLink.displayLink();

System.out.println(“”);

}

theList.displayList(); // display list

} // end main()

} // end class LinkListApp

////////////////////////////////////////////////////////////////

 

Следующий пример программы добавляет методы :

· метод для поиска в связанном списке элемента с указанным значением ключа ;

· метод удаление элемента с указанным значением ключа.

class LinkList

{

private Link first; // ref to first link on list

// -------------------------------------------------------------

public LinkList() // constructor

{

first = null; // no links on list yet

}

// -------------------------------------------------------------

public void insertFirst(int id, double dd)

{ // make new link

Link newLink = new Link(id, dd);

newLink.next = first; // it points to old first link

first = newLink; // now first points to this

}

// -------------------------------------------------------------

Public Link find(int key) // find link with given key

{ // (assumes non-empty list)

Link current = first; // start at ‘first’

while(current.iData != key) // while no match,

{

if(current.next == null) // if end of list,

return null; // didn’t find it

else // not end of list,

current = current.next; // go to next link

}

return current; // found it

}

// -------------------------------------------------------------

Public Link delete(int key) // delete link with given key

{ // (assumes non-empty list)

Link current = first; // search for link

Link previous = first;

while(current.iData != key)

{

if(current.next == null)

return null; // didn’t find it

else

{

previous = current; // go to next link

current = current.next;

}

} // found it

if(current == first) // if first link,

first = first.next; // change first

else // otherwise,

previous.next = current.next; // bypass it

return current;

}

// -------------------------------------------------------------

public void displayList() // display the list

{

System.out.print(“List (first-->last): “);

Link current = first; // start at beginning of list

while(current != null) // until end of list,

{

current.displayLink(); // print data

current = current.next; // move to next link

}

System.out.println(“”);

}

// -------------------------------------------------------------

} // end class LinkList

 


Лабораторна робота № 3

Тема: «Рекурсія . Задача пошуку. Лінійний та бінарний пошук»

 

Мета роботи

Отримання практичних навичок програмування задач лінійного пошуку у масиві та бінарне дерево пошуку. Вивчення властивості бінарного дерева пошуку. Отримання практичних навичок находження наступного та попереднього елементів бінарного дерева пошуку. Вивчення рекурсивні алгоритми вставки, пошуку та видалення у бінарному дереві пошуку.

 

Завдання до лабораторної роботи

Побудувати бінарне дерево пошуку. І виконати операції :

- вставка і видалення елементів;

- пошук елемента по ключу;

- пошук мінімального елементу;

- пошук максимального елементу.

 

Методичні вказівки

 

Лабораторна робота спирається на знання й уміння, отримані при вивченні наступних тем лекційного курсу:

- Алгоритми лінійного та бінарного пошуку.

- Пошук у бінарних деревах.

- Рекурсія. Особливості рекурсивних програм.

Тому під час підготовки до лабораторної роботи рекомендується повторити зазначені розділи дисципліни.

Наведемо нижче декілька важливих визначень, які слід пам’ятати під час виконання лабораторної роботи та перелік важливих методів, що дозволяють полегшити обробку дерева і можуть бути використані при створенні програми лабораторної роботи.

У алгоритмах пошуку нас цікавить процес перегляду списку у пошуках деякого конкретного елементу, що називається цільовим.

Алгоритм лінійного пошуку послідовно переглядає по одному елементу списку, починаючи з першого, до тих пір, поки не знайде цільовий елемент. Очевидно, що чим далі в списку знаходиться конкретне значення ключа, тим більше часу піде на його пошук. Це слід пам'ятати при аналізі алгоритму.

У алгоритмі послідовного пошуку два найгірші випадки. У першому випадку цільовий елемент стоїть в списку останнім. У другому його зовсім немає в списку. Припустимо, що усі ключові значення в списку унікальні, і тому якщо збіг стався в останньому записі, то усі попередні порівняння були невдалими. Проте алгоритм проробляє усі ці порівняння доки не дійде до останнього елементу. В результаті буде виконано порівнянь, де – число елементів в списку.

Бінарне дерево пошуку– структура даних, яка підтримує багато операцій з динамічними множинами, включаючи пошук елементу, мінімального і максимального значення, попереднього і подальшого елементу, вставку і видалення.

Основні операції у бінарному дереві пошуку виконуються за час, пропорційний його висоті. Для повного бінарного дерева з вузлами ці операції виконуються за час у найгіршому випадку. Математичне очікування висоти побудованого випадковим чином бінарного дерева дорівнює , так що усі основні операції над динамічною множиною в такому дереві виконуються в середньому за час .

Бінарне дерево пошуку може бути представлене за допомогою зв'язаної структури даних, в якій кожен вузол є об'єктом Node. На додаток до полів ключа і супутніх даних, кожен вузол містить поля leftChild, rightChild, які вказують на лівий, правий дочірні вузли . Якщо дочірній вузол відсутній, відповідне поле містить значення . Єдиний вузол, вказівник root– це кореневий вузол дерева.

 

class Node

{

public int iData; // data item (key)

public double dData; // data item

public Node leftChild; // this node’s left child

public Node rightChild; // this node’s right child

public void displayNode() // display ourself

{

System.out.print('{');

System.out.print(iData);

System.out.print(", ");

System.out.print(dData);

System.out.print("} ");

}

} // end class Node

 

Ключі у бінарному дереві пошуку зберігаються особливим чином, щоб у будь-який момент задовольняти наступній властивості бінарного дерева пошуку: якщо – вузол бінарного дерева пошуку, а вузол знаходиться в лівому піддереві , то . Якщо вузол знаходиться в правому піддереві , то .

Вставка елементу. Алгоритм вставки елементу починає свою роботу в корені дерева і проходить по низхідному шляху, переміщаючись вліво або управо залежно від результату порівняння ключів, до тих пір, поки не наштовхнеться на незайняту позицію лівого або правого спадкоємця елементу.

 

public void insert(int id, double dd)

{

Node newNode = new Node(); // make new node

newNode.iData = id; // insert data

newNode.dData = dd;

if(root==null) // no node in root

root = newNode;

else // root occupied

{

Node current = root; // start at root

Node parent;

while(true) // (exits internally)

{

parent = current;

if(id < current.iData) // go left?

{

current = current.leftChild;

if(current == null) // if end of the line,

{ // insert on left

parent.leftChild = newNode;

return;

}

} //

else // or go right?

{

current = current.rightChild;

if(current == null) // if end of the line

{ // insert on right

parent.rightChild = newNode;

return;

}

} // end else go right

} // end while

} // end else not root

} //

 

Пошук. Для пошуку вузла із заданим ключем у бінарному дереві пошуку використовується наступний алгоритм: для кожного вузла на шляху вниз, його ключ порівнюється з шуканим ключем . Якщо ключі однакові, пошук завершується. Якщо менше , пошук триває в лівому піддереві ; якщо більше – то пошук переходить в праве піддерево. Відвідані при рекурсивному пошуку вузли утворюють низхідний шлях від кореня дерева, так що час роботи цього алгоритму рівний , де – висота дерева.

 

public Node find(int key) // find node with given key

{

Node current = root; // start at root

while(current.iData != key)

{

if(key < current.iData)

current = current.leftChild;

else // or go right?

current = current.rightChild;

if(current == null)

return null; }

return current;

} // end find()

 

Видалення елементу. Алгоритм видалення вузла працює по-різному, залежно від того – чи є у елемента, що видаляється, дочірні вузли:

- Якщо у вузла, що видаляється, немає дочірніх елементів, то ми просто змінюємо його батьківський вузол, замінюючи в ньому вказівник на елемент, що видаляється, значенням .

- Якщо у вузла, що видаляється, тільки один дочірній елемент, то ми видаляємо вузол, зв'язуючи батьківський елемент і дочірній елемент вузла, що видаляється.

- Якщо у вузла, що видаляється, два дочірні елементи, то знаходимо вузол, що йде за ним, у якого немає лівого дочірнього вузла, прибираємо його з позиції, де він знаходився раніше, шляхом створення нового зв'язку між його батьком і нащадком, і замінюємо ним вузол, що видаляється.

Час роботи алгоритму видалення у всіх трьох випадках, для бінарного дерева пошуку заввишки складає .

 

public boolean delete(int key) // delete node with given key

{

Node current = root;

Node parent = root;

boolean isLeftChild = true;

while(current.iData != key) // search for node

{

parent = current;

if(key < current.iData) // go left?

{

isLeftChild = true;

current = current.leftChild;

}

else // or go right?

{

isLeftChild = false;

current = current.rightChild;

}

if(current == null) // end of the line,

return false; // didn’t find it

} // end while

if(current.leftChild==null &&

current.rightChild==null)

{

if(current == root) // if root,

root = null; // tree is empty

else if(isLeftChild)

parent.leftChild = null; // disconnect

else // from parent

parent.rightChild = null;

}

else if(current.rightChild==null)

if(current == root)

root = current.leftChild;

else if(isLeftChild)

parent.leftChild = current.leftChild;

else

parent.rightChild = current.leftChild;

else if(current.leftChild==null)

if(current == root)

root = current.rightChild;

else if(isLeftChild)

parent.leftChild = current.rightChild;

else

parent.rightChild = current.rightChild;

else {

Node successor = getSuccessor(current);

// connect parent of current to successor instead

if(current == root)

root = successor;

else if(isLeftChild)

parent.leftChild = successor;

else

parent.rightChild = successor;

successor.leftChild = current.leftChild;

} // end else two children

return true;

} // end delete

Код програми представлений в додатку А.

 

Контрольні питання

1. Що таке пошук?

2. Що називаються ключем пошуку?

3. Які відомі методи пошуку?

4. Який алгоритм пошуку є найбільш ефективним?

5. Чим відрізняються пошук в масиві від пошуку в списку?

6. У чому полягаю метод лінійного пошуку?

7. Що представляю собоя двійкове дерево?

8. У чому полягає вставка вузла в дерево?

9. У чому полягає видалення вузла з дерева?

10. Які особливості видалення елемента з деревовидної структури даних?

11. У чому полягає пошук в дереві?

12. Що таке «проходження дерева»? Які можливі варіанти проходження дерева?

Варіанти завдань

 

Вставка Пошук Видалення
41, 71, 25, 24, 60, 68, 26, 4, 77, 12, 52, 62, 21, 31, 30 68, 12, 30, min 41, 25, 60
47, 40, 22, 61, 95, 9, 93, 39, 43, 38, 59, 25, 60, 71, 32 38, 60, 32 , max 47, 22, 61
46, 26, 2, 79, 76, 99, 41, 37, 51, 6, 97, 35, 93, 10, 21 97, 10, 35, min 46, 99, 26
48, 52, 15, 54, 79, 56, 46, 73, 65, 94, 9, 85, 7, 33, 8 73, 85, 8, max 48,79, 15
41, 27, 44, 13, 17, 37, 65, 33, 40, 84, 59, 69, 7, 60, 67 69, 33, 60, min 41, 65, 27
53, 13, 66, 55, 63, 24, 77, 82, 44, 40, 18, 86, 15, 68, 30 82, 40, 30, max 53, 66, 13
81, 42, 57, 87, 25, 52, 6, 32, 91 42, 91, 25, min 42, 91, 25, 81
44, 50, 11, 49, 23, 15, 87, 1, 27 11, 44, 49, max 11, 44, 49, 50
58, 78, 23, 47, 4, 80, 44, 56, 93 58, 23, 80, min 58, 23, 80, 4
54, 29, 97, 37, 55, 4, 34, 96, 98 29, 54, 37, max 29, 54, 37, 98
62, 81, 34, 4, 82, 41, 79, 96, 84 81, 34, 62, min 81, 34, 62, 96
56, 23, 36, 22, 87, 44, 25, 73, 11 23, 56, 36, max 23, 56, 36

 






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2021 pdnr.ru Все права принадлежат авторам размещенных материалов.