4970

Сравнение однонаправленного и двунаправленного списка

Реферат

Информатика, кибернетика и программирование

Списки Список – линейная структура, каждый элемент которой содержит адрес соседних элементов. Различают однонаправленные и двунаправленные списки. В однонаправленном списке каждый элемент содержит адрес следующего элемента. В двунаправленном сп...

Русский

2012-11-30

65.03 KB

22 чел.

Списки

Список – линейная структура, каждый элемент которой содержит адрес соседних элементов. Различают однонаправленные и двунаправленные списки.

В однонаправленном списке каждый элемент содержит адрес следующего элемента. В двунаправленном списке каждый элемент содержит адреса предыдущего и последующего элементов.

Однонаправленный список

Рассмотрим более подробно однонаправленный список.

Каждый элемент списка состоит из содержательной части и служебной части.

Содержательная часть имеет в своем составе элементы данных, которые характеризуют свойства элемента списка.

Служебная часть содержит указатель, в котором хранится адрес следующего элемента списка.

Сравнение однонаправленного и двунаправленного списка

С одной стороны, однонаправленный список проще, чем двунаправленный. С другой стороны, элементы однонаправленного списка не содержат адресов предыдущих элементов, что позволяет просматривать список только в одном направлении.

Сравнение списка и массива указателей

Принцип упорядочения элементов в списке принципиально отличается от принципа упорядочения элементов в массиве указателей.

В массиве указателей каждому указателю на элемент соответствует свой номер. Для перемещения по массиву указателей используется целочисленная переменная счетчик. Для включения нового элемента массива необходимо перемещать все элементы после места включения. К элементам массива указателей можно получать доступ по номеру.

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

Описание списка на языке Си++

Для описания списка на языке Си++ необходимо описать два класса:

класс элемента списка и класс списка.

 В классе элемента списка должны находиться переменные для описания свойств объектов класса и указатель на следующий элемент.

В классе самого списка должны находиться указатель на начало списка и число элементов

Рассмотрим пример разработки класса списка людей.

Вначале необходимо создать класс Человек PersonElem.

Затем следует создать класс PeopleList


 

А также другие работы, которые могут Вас заинтересовать

68967. Масиви об’єктів, покажчики на об’єкти 55 KB
  В мові C++ масиви можуть складатися з об’єктів. З синтаксичної очки зору оголошення масиву об’єктів нічим не відрізняється від оголошення масиву вбудованого типу. Приклад програми, в якій використовується масив, який складається з трьох елементів.
68968. ПРОГНОЗУВАННЯ І ТАКТИКА ВЕДЕННЯ ВАГІТНОСТІ ТА ПОЛОГІВ ПІСЛЯ КЕСАРЕВА РОЗТИНУ 176 KB
  Рандомізовані, контрольовані дослідження проведені Британською королівською колегією акушерів-гінекологів, переконливо довели, що плановий КР в порівнянні з плановими вагінальними пологами достовірно збільшує ризик гістеректомії
68969. Перевантаження операторів. Дружні операторні функції 31.5 KB
  Перевантаження операторів за допомогою дружніх функцій Створення операторної функціїчлена З перевантаженням функцій тісно зв’язаний механізм перевантаження операторів. Операторні функції створюються за допомогою ключового слова opertor.
68971. Віртуальні функції. Абстрактні класи 54 KB
  Кожне перевизначення віртуальної функції в похідному класі реалізує операції властиві лише даному класу. Покажчики на об’єкти базового класу можна використовувати для посилання на об’єкти похідних класів. Якщо покажчик на об’єкт базового класу встановлюється на об’єкт...
68972. Файли. Робота з файлами. Файловий ввід-вивід 58 KB
  Не дивлячись на те що система введення-виведення мови C++ в цілому є єдиним механізмом, система файлового введення-виведення має свої особливості. Частково це пояснюється тим, що на практиці найчастіше використовуються файли на жорсткому диску, можливості яких значно відрізняються від всіх інших пристроїв.
68973. Сортування масивів 30.5 KB
  Стан об’єкту цілком і повністю визначається станом елементів масиву. Для роботи з об’єктом можна використовувати інтерфейс що містить наступний набір операцій: розміщення масиву динамічної пам’яті ініціалізація масиву проглядання вивід значень елементів масиву сортування масиву різними способами...
68974. Алфавіт, ідентифікатори, службові слова 103 KB
  До специфікаторів типів відносяться: chr символьний; double дійсний з подвійною точністю з плаваючою крапкою; enum перелічуваний тип перелік визначення цілочисельних констант для кожної з яких вводяться ім’я і значення; floаt дійсний з плаваючою крапкою; int цілий; long цілий збільшеної довжини...