Программирование линейных списков

№90-1,

технические науки

В статье рассматривает создание односвязного списка, добавление, удаление, поиск элемента по ключу. Приведенные в работе программы протестированы в среде Borland C++ 5.02. Программы предназначены для начинающих программистов студентов и школьников.

Похожие материалы

С++ — один из самых распространенных языков программирования [1, 2]. Он широко используется студентами при выполнении выпускных квалификационных и курсовых работ. С++ с успехом применяется при выполнении численных расчетов по научным задачам [3, 4].

Любая программа для компьютера предназначена для обработки данных. Данные бывают статические и динамические. В статье рассматривает создание односвязного списка, добавление, удаление, поиск элемента по ключу. Приведенные в работе программы протестированы в среде Borland C++ 5.02. Программы предназначены для начинающих программистов студентов и школьников. Они могут быть использованы при выполнении лабораторных, контрольных и курсовых работ.

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

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

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

struct <имя_типа_структуры> {<имя_типа> <имя_поля>;<имя_типа_структуры> *<имя_поля_указателя>;};

Первое поле структуры — поле данных, а второе поле — указатель.

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

struct spisok{char fam[200]; // поле данныхchar name[200]; // поле данныхchar fname[200]; // поле данных     nt year; // поле данныхspisok *next; / поле указатель на следующий элемент};

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

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

Над односвязнымb списками можно выполнять следующие операции:

  • начальное формирование списка (создание первого элемента);
  • добавление элемента в конец списка;
  • чтение элемента с заданным ключом;
  • вставка элемента в заданное место списка (до или после элемента с заданным ключом);
  • удаление элемента с заданным ключом;
  • упорядочивание списка по ключу.

Рассмотрим каждую операцию отдельно на примере создания динамической структуры данных для хранения списка группы студентов (ф.и.о., дата рождения (день, месяц, год)).

Начальное формирование списка.

#include <iostream.h>#include <conio.h>#include <string.h>#include <stdio.h>// описание типа структураstruct spisok{          char fam[200];          unsigned int d,m,y;spisok *next; };int main () {spisok *first=new spisok;//указатель first всегда будет указывать на 1-й элемент спискаcout<<"Введите ф.и.о. \n"; gets(first ->fam);cout<<"Введите дату рождения в виде: 17 8 2006 ";cin>> first ->d>> first ->m>> first ->y;first ->next=0;getch(); return 0; }

Добавление элемента в конец списка.

spisok *t,*z;// описываем дополнительные указателиt=first;while(t->next!=0)t=t->next;// находим конец спискаz=new spisok;cout<<"Введите ф.и.о. \n"; gets(z ->fam);cout<<"Введите дату рождения в виде: 7 8 2006  ";cin>> z->d>> z->m>> z->y;z->next=0;// ввели новый элемент// указатель z указывает на новый элементt->next=z;// указателю последнего элемента присваиваем адрес нового элемента// выводим элементы списка на экранt=first;int j=1;while(t!=0){cout<<j++<<". "<<t->fam<<", "<<t->d<<"."<<t->m<<"."<<t->y<<endl;t=t->next; }

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

Пусть ключом является год рождения.

unsigned int key;cout<<"Введите год рождения для поиска\n";cin>>key;t=first;cout<<"Данные о тех, которые родились в "<<key<< " году \n";while(t->next!=0){if (key==t->y) {cout<<t->fam<<", "<<t->d<<"."<<t->m<<"."<<t->y<<endl;}t=t->next;}

Удаление элемента с заданным ключом. Удаление элемента из списка зависит от того, где находится элемент: в начале списка, в середине или в конце. Для удаления элемента из списка введем фамилию имя отчество.

cout<<"исходный список \n";t=first;j=1;while(t!=0){cout<<j++<<". "<<t->fam<<", "<<t->d<<"."<<t->m<<"."<<t->y<<endl;t=t->next; }// Выводим исходный списокchar key_fam[20];cout<<"Введите ф.и.о. для удаления \n";gets(key_fam);while (strcmp(key_fam,first->fam)==0){first=first->next;}// удаление первого элемента списка, если ф.и.о. совпадаетt=first; z=t;while(t!=0){if (strcmp(key_fam,t->fam)==0){z->next=t->next;}else{z=t;}t=t->next;}cout<<"список после удаления элемента \n";t=first;j=1;while(t!=0){cout<<j++<<". "<<t->fam<<", "<<t->d<<"."<<t->m<<"."<<t->y<<endl;t=t->next; }

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

Список литературы

  1. Подбельский В.В. Язык С++: Учебное пособие – 5 изд. – М: Финансы и статистика, 2004. – 560 c.
  2. Шилдт Г. С++: базовый курс. 3-е издание. – М.: Издательский дом "Вильямс". 2010. – 624 с.
  3. Хусаинов И.Г. Тепловые процессы при акустическом воздействии на насыщенную жидкостью пористую среду // Вестник Башкирского университета. 2013. Т. 18. № 2. С. 350-353.
  4. Хусаинова Г.Я. Нестационарная фильтрация вязкопластичной жидкости в пласте // Автоматизация. Современные технологии. 2018. Т. 72. № 4. – С. 147-149.