Лінійний однозв’язний список.

Скачати лекцію (.doc)

Лінійний однозвв’язний список

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

З визначення випливає, що кожен елемент списку містить поле даних (Data) (воно може мати складну структуру) і поле посилання на наступний елемент (next). Поле посилання останнього елемента повинно містити порожній покажчик (NULL).

Так як посилання лише одне (тільки на наступний елемент), то такий список є однозв’язним.

Коли говорять про лінійний список, то, як правило, мають на увазі саме однозв’язний список.

Приклад. Сформувати список, що містить цілі числа 3, 5, 1, 9.

Рішення. При роботі з динамічними структурами даних можна рекомендувати наступний порядок дій.

а) Перш за все необхідно визначити дві структури:

1. структура, яка містить характеристики даних, тобто всі ті поля з даними, які необхідні для вирішення поставленого завдання (у нашому випадку є всього одне поле цілого типу). Назвемо цю структуру Data;
2. друга структура, яка містить поле типу Data і поле – адресу наступного елемента next. Другу структуру назвемо List.

Тексти цих структур необхідно розташувати на початку програми (до main () та інших функцій). Ось можлива реалізація структур:

struct Data
{   int a;
};
struct List
{   Data d;
List *next;
};

Такий підхід дозволить надалі змінювати в широких межах структуру з власними даними, при цьому не зачіпаючи  основну структуру List.

Отже, ми описали структурний тип, за допомогою якого можна створити наш однозв’язний список. Графічно створюваний список можна зобразити так, як це показано на малюнку нижче:

б) У програмі (зазвичай у функції main ()) визначаємо покажчик на початок майбутнього списку:

List *u = NULL;

 

Поки список порожній, і покажчик  заданий  константі NULL.

в) Виконуємо початкове заповнення списку.

Створимо перший елемент:

u = new List;  // Виділяєм пам’ять під елемент списку

u->d.a = 3;    // Заповнюємо поля з даними

               // (у нашому випадку це лише одне поле)

u->next = NULL;// Вказівник на наступний елемент пустий

 

Після включення першого елемента список можна зобразити так:

Продовжимо формування списку, додаючи нові елементи в його кінець. Для зручності заведемо допоміжну змінну-покажчик, яка буде зберігати адресу останнього елемента списку:

 

List *x;

x = u; // Сейчас последний элемент списка совпадает с его началом
Таким чином, до області пам’яті можна звернутися через два покажчика.

Виділяємо місце в пам’яті для наступного елемента списку і перенаправляємо покажчик x на виділену область пам’яті:

x->next = new List;

x = x->next;

 

Потім визначаємо значення цього елементу списку:

x->d.a = 5;

x->next = NULL;

Получилась такая схема:
Цей процес продовжуємо доти, поки не буде сформований весь список.

 

Действия со сформированным списком

Сформировав начальный список, можно выполнять с ним различные действия. Настоятельно рекомендуется каждую операцию со списком оформлять в виде отдельной функции. Такой подход заметно упрощает разработку программы и возможную её дальнейшую модификацию. Понятно, что и только что рассмотренное формирование начального списка также лучше записать в виде функции.

1. Просмотр списка— осуществляется последовательно, начиная с его начала. Указатель последовательно ссылается на первый, второй, и т.д. элементы списка до тех пор, пока весь список не будет пройден. Приведём пример реализации просмотра, например, длявывода списка на экран монитора:

void Print(List *u)

{

   List *p = u;

   cout << “Spisok:” << endl;

   while(p)

   {

      cout << p->d.a << endl;

      p = p->next;

   }

}

Обратиться к функции можно так:

Print(u);

Здесь и далее в примерах u — это указатель на начало списка.

2. Поиск первого вхожденияв список элемента, соответствующего заданным требованиям:

List * Find(List *u, Data &x)

{

   List *p = u;

   while(p)

   {

      if(p->d.a == x.a) // условие для поиска

         return p;

      p = p->next;

   }

   return 0;

}

Возможный вызов функции:

List * v = Find(u, x);

где x — объект типа Data.

3. Добавление нового элемента в начало списка:

void Add_Beg(List **u, Data &x)

{

   List *t = new List;

   t->d.a = x.a;

   t->next = *u;

   *u = t;

}

Возможный вызов функции:

Add_Beg(&u, x);

где x — объект типа Data.

4. Вставка нового элемента в произвольное место спискапо какому-нибудь принципу, например, вставка в отсортированный по возрастанию список:

void Insert(List **u, Data &x)

{

   // вставка в список одного элемента перед элементом,

   // меньшим или равным данному x

   List *p = new List;

   p->d.a = x.a;

 

   if(*u == 0) // исходный список пуст – вставка в начало

   {

      p->next = 0;

      *u = p;

      return;

   }

 

   List *t = *u;

   if(t->d.a >= p->d.a) // исходный список не пуст –

                        // вставка в начало

   {

      p->next = t;

      *u = p;

      return;

   }

 

   List *t1 = t->next;

   while(t1)

   {

      if(t->d.a < p->d.a && p->d.a <= t1->d.a)

         {  // вставка в середину

         t->next = p;

         p->next = t1;

         return;

      }

      t = t1;

      t1 = t1->next;

   }

 

   t->next = p; // добавляем в конец списка

   p->next = 0;

}

Возможный вызов функции:

Insert(&u, x)

где x — объект типа Data.

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

5. Удаление элемента из линейного списка:

void Delete(List **u, Data &x)

{

   if(*u == 0) // исходный список пуст – удалять нечего!

   {

      return;

   }

   List *t = *u;

   if(t->d.a == x.a) // исходный список не пуст –

                     // удаляется начало

   {

      *u = t->next;

      delete t;

      return;

   }

   List *t1 = t->next;

   while(t1)

   {

      if(t1->d.a == x.a)

      // исходный список не пуст –

      //удаляется не первый элемент

      {

         t->next = t1->next;

         delete t1;

         return;

      }

      t = t1;

      t1 = t1->next;

   }

}

Возможный вызов функции:

Delete(&u, x);

где x — объект типа Data.

6. Удаление (очистка) всего списка

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

void Clear(List **u)

{

   // удаление (очистка) всего списка

   if(*u == 0) return;

   List *p = *u;

   List *t;

   while(p)

   {

      t = p;

      p = p->next;

      delete t;

   }

   *u = 0;

}

Возможный вызов функции:

Clear(&u);

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