Практическая работа №2 «Динамические структуры данных»

1. 
   Списки
   

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

• 
  Односвязные – каждый элемент списка имеет указатель на следующий;
  
• 
  Двусвязные – каждый элемент списка имеет указатель на следующий и на предыдущий элементы;
  
• 
  Циклические – первый и последний элементы списка ссылаются друг на друга, и цепочка представляет собой кольцо.
  

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

• 
  Информационное поле, которое в общем случае может содержать произвольное количество полей разных типов.
  
• 
  Указатель на следующий элемент списка, или пустой указатель, если следующего элемента нет.
  

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

---

2. 
   Односвязный список
   

Простейший случай – элемент списка содержит единственный указатель на следующий элемент, что позволяет двигаться по списку только в одном направлении.Для односвязного списка наиболее простыми являются операции включения и исключения элементов в начале и конце списка, соответственно они используются для моделирования таких структур данных, как стеки и очереди.Стек – это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека.По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл ‑ первый ушёл" (LIFO ‑ LastIn – FirstOut).Основные операции со стеком:‑ создание первого элемента;‑ помещение нового элемента в стек;‑ извлечение элемента из стека.Для линейного списка, представляющего стек, необходимо будет сохранять top – указатель на вершину стека.Очередь — упорядоченный набор данных (структура данных), в котором, в отличие от стека, извлечение данных происходит из начала цепочки, а добавление данных — в конец этой цепочки. Очередь также называют структурой данных, организованной по принципу FIFO (FirstIn – FirstOut).Для линейного списка, представляющего очередь, необходимо будет сохранять: pbeg – указатель на первый элемент списка, и pend – указатель на последний элемент.2.1 Формирование односвязного спискаКак правило, элементы связанного списка являются структурами, так как, помимо данных, они содержат ссылку на следующий элемент. Поэтому необходимо определить структуру:structList{intinfo;//информационная частьstructList *next;//указатель на следующий элемент списка};В приведенном примере информационная часть представляет собой одну целочисленную переменную (info), которая имеет тип int. Списки с элементами других типов описываются аналогично.Пример. Список символов (‘a’,’b’,’c’), состоит из трех элементов. Первый элемент в этом списке – ‘a’, второй – ‘b’, третий – ‘c’. Представление этого списка стеком изображается на рис. 1, очередью – на рис. 2.

---

Рис.1 – Стек из трех элементовРис. 2 – Очередь из трех элементовПри этом в программе выражение pbegозначает указатель на первое звено в цепочке; *pbegозначает само первое звено, (*pbeg).info— первый элемент списка. По-другому первыйэлемент обозначается с помощью операции доступа к члену структуры через указатель:pbeg−>info. Выражение pbeg−>next означает указатель на второе звено. Далее,*pbeg−>next — само второе звено,pbeg−>next−>info— второй элемент списка,pbeg−>next−>next — указатель на третье звено,*pbeg–>next−>next — само третье звено,pbeg−>next−>next−>info— третий элемент списка,pbeg−>next−>next−>next — пустой указатель (конец списка).Заметим, что соседние звенья цепочки располагаются в оперативной памяти произвольно относительно друг друга, в отличие от соседних компонент массива, всегда занимающих смежные участки памяти. Такое расположение звеньев облегчает операции вставки и удаления, так как нет необходимости перемещать элементы, как это было бы в случае реализации списков массивами.2.2 Добавление нового элемента в стекОпределена структура, которая будет использоваться в последующих примерах:#define STACK struct ListSTACK{ char info;STACK *next;};Функция добавления элемента в стек:

void push (STACK **top, char item) { STACK *new_item; new_item = new STACK; new_item->info = item; new_item->next = *top; *top = new_item; }

//*top – указатель на вершину стека, //item – символ, который заносится в стек; //указатель на новый элемент стека; //создаем элемент стека; //заполняем поле info; //присоединяем в конец стека новый элемент //вершиной стека становится новый элемент;

Пример. Пусть в стек, состоящий из элементов (‘a’,’b’,’c’) (элементы указаны в порядке их добавления в стек), представленный в программе переменной s, необходимо добавить новый элемент ‘d’. Для этого вызывается функция push:push(&s,’d’);На рис. 3 показано происходящее после каждого шага изменения.Рис. 3 – Добавление элемента в стек

---

2.3 Удаление элемента из стекаФункция удаления элемента из стека:

void del (STACK **top) { STACK *old_item = *top; if(*top) { *top =(*top)->next; free(old_item); } }

//*top – указатель на вершину стека //old_item – указатель на удаляемый элемент; //если стек не пуст (*top!=NULL) //переносим указатель *top на следующий элемент стека, вершиной стека становится предыдущий элемент последовательности //уничтожаем элемент old_item

Пример. Пусть из стека, состоящего из элементов (‘a’,’b’,’c’) (элементы указаны в порядке их добавления в стек), представленного в программе переменной s, необходимо удалить элемент ‘c’. Для этого вызывается функция del:del(&s);На рис. 4 показано происходящее после каждого шага изменения.

0. 
   Рис. 4 – Удаление элемента из стека
   
1. 
   2.4 Добавление нового элемента в очередь
   

Определена структура, которая будет использоваться в последующих примерах:#define QUEUE struct ListQUEUE{ char info; QUEUE *next;};

0. 
   
   
1. 
   Функция добавления элемента в очередь:
   
2. 
   
   

void insert(QUEUE **pbeg, char item) { QUEUE *current = *pbeg; QUEUE *previous = 0; QUEUE *new_node; while (current) { previous = current; current = current -> next; } new_node = new QUEUE; new_node->info = item; if (previous) { new_node->next = 0; previous->next = new_node; } else { *pbeg = new_node; (*pbeg)->next = 0; } }

//*pbeg – указатель на первый элемент очереди //current – указатель на текущий элемент очереди; указывает на первый элемент //указатель на предыдущий элемент очереди //указатель на новый элемент очереди //пока текущий элемент не равен NULL //указатель previous указывает на тот же элемент, что и указатель current //перемещение указателя current на следующий по отношению к текущиму элемент //создаем новый элемент очереди //записываем в поле info нового элемента значение переменной item //если очередь не пустая (добавляется элемент в конец очереди) //указатель на следующий элемент после нового равен нулю (т.е. элемент не существует) //следующим по отношению к последнему элементу очереди становится новый элемент //если очередь пустая (добавляется первый элемент очереди) //первым элементом очереди будет новый элемент //указатель на следующий элемент поcле первого элемента равен 0 (т.е. элемент не существует)

---

0. 
   Пример 1. Необходимо сформировать очередь, состоящую из трех элементов (‘a’,’b’,’c’), представленную в программе переменной q. Для этого используется функция insert.
   
1. 
   
   
2. 
   QUEUE *q;
   
3. 
   insert(&q,’a’);
   
4. 
   insert(&q,’b’);
   
5. 
   insert(&q,’c’);
   

0. 
   На рис. 5 показаны изменения, происходящие при добавлении первого элемента очереди, на рис. 6 – при добавлении второго элемента очереди, на рис. 7 – добавление третьего элемента очереди.
   
1. 
   
   
2. 
   Рис. 5 – Добавление первого элемента очереди
   

Рис. 6 – Добавление второго элемента очереди

0. 
   
   
1. 
   Рис. 7 – Добавление третьего элемента очереди
   
2. 
   
   
3. 
   Пример 2. Пусть в очередь, состоящую из трех элементов (‘a’,’b’,’c’), представленную в программе переменной q, необходимо добавить элемент ‘d’ после элемента ‘b’. В этом случае необходимо добавить элемент в середину очереди.
   
4. 
   
   
5. 
   Функция добавления элемента в середину очереди:
   
6. 
   
   

   void insert_mid(QUEUE **pbeg, char item) { QUEUE *current; QUEUE *new_node; current = *pbeg; while(current->info!=’b’) { current = current->next; } new_node = new QUEUE; new_node->info = item; new_node->next = current->next; current->next = new_node; }

   //*pbeg – указатель на первый элемент очереди //текущий элемент очереди //новый элемент очереди //просмотр очереди начинаем с первого элемента //пока поле info текущего элемента не содержит символ ‘b’ //указатель current перемещается на следующий элемент очереди //создаем новый элемент очереди //в поле info нового элемента заносится значение ‘d’ //следующим элементом по отношению к новому становится следующий по отношению к текущему элемент //следующим по отношению к текущему элементу становится новый элемент

7. 
   
   

На рис. 8 показано происходящее после каждого шага изменения.Рис. 8 – Добавление элемента в середину очереди2.5 Удаление элемента из очереди Функция удаления элемента из очереди аналогична функции удаления из стека:

---

Смотрите также файлы

• aзacтaн Pecпyбликacы Білім жнe ылым миниcтpлігі Aбaй aтындaы aзa лтты пeдaгoгикaлы yнивepcитeті Филoлoгия жнe кптілді білім бepy инcтитyты.docx

• Ответ (2)Гипотеза самозарождения предполагала рождение живого из неживого. (3)Р. Гук и Л. Пастер не были приверженцами гипотезы самозарождения (4)Креационизм рассматривает жизнь как результат божественного творения. Задание 2.docx

• aзacтaн Pecпyбликacы Білім жнe ылым миниcтpлігі Aбaй aтындaы aзa лтты пeдaгoгикaлы yнивepcитeті Филoлoгия жнe кптілді білім бepy инcтитyты.docx

• Дисциплина Русский язык и культура речи Практическое занятие 3 Обучающийся Казакова Вера Михайловна Преподаватель Пинаева Ирина Юрьевна Задание Расставьте ударения в словах. В затруднительных случаях обращайтесь к словарям.doc

• Курсовая работа по дисциплине Организация и проведение всех видов охоты.docx