CodeNet / Приложения / Алгоритмы / Структуры данных
Динамический список, его реализация и применение [C++]
18 марта 2009 года
1. Введение
Очень часто, при разработке приложений, оперирующих с большим количеством входных данных, возникает вопрос об их хранении во время выполнения программы. Приводить все из них не имеет смысла, остановлюсь лишь на массивах. Несомненно, данный тип решает вопрос хранения данных, однако, очевидно, что он не лишен недостатков. Главным из них, несомненно, является его фиксированный размер. Это свойство не поддается изменению даже у динамически созданных массивов, что довольно часто заставляет программистов, использующих исключительно их, выделять память "с запасом". Ну а во-первых, даже "запас" ограничен, и никто не может дать гарантии, что и его будет достаточно, а во-вторых, наоборот, "запаса" может хватить настолько, что немалая часть отведенной программе памяти будет занята понапрасну.
Данную проблему решает другой тип хранения данных, которому и посвящена эта статья - связанный список динамических переменных, или проще - динамический список. Компоненты добавляются и удаляются во время выполнения программы, и их количество зависит исключительно от размера доступной памяти. Однако, за это преимущество приходится расплачиваться недостатком - если в случае с массивом, мы в любой момент получаем доступ к любому компоненту, то в случае со списком, в один момент времени нам доступны максимум 3 компонента (это зависит от способа представления списка в программе). В большинстве случаев, это очень даже приемлемая цена ...
В статье на примере решения несложной задачи, я попытаюсь продемонстрировать работу с динамическими списками, реализую основные операции над ним и его компонентами. Статья рассчитана на программистов С\C++, хорошо знакомых с синтаксисом языка, типами данных, имеющих представление и опыт применения указателей. Я программирую в VS 2008, однако в данном случае, IDE не имеет особого значения.
2. Постановка задачи
Для демонстрации реализации работы с динамическим списком, решим задачу:
"В текстовом файле находятся идентификаторы переменных и их числовые значения (например: x 15 abc 12.098 z -1.23). Перенести их в динамический список, для которого реализовать следующие операции: поиск идентификатора в списке; изменение значения указанного идентификатора; удаление идентификатора из списка, добавление в список нового идентификатора с заданным значением. По окончании сеанса работы список идентификаторов и их значений переносится обратно в файл"
Задача позволит нам научиться реализовывать все основные операции над динамическим списком - создание списка, добавление и удаление компонентов (узлов) списка, поиск по компонентам списка. Для решения понадобятся знания о файловом вводе-выводе, указателях, а также структурированных типах данных. Я не буду создавать никакой оболочки для этой задачи, хотя она была бы кстати, так как имеется целый спектр возможных операций. Однако это не является моей основной задачей в рамках этой статьи. Я лишь реализую все операции в виде отдельных функций и для пробы обращусь к ним по разу :
3. Решение
3.1. Стандартное начало
Приступим к решению. Создаем консольный проект, и пишем довольно стандартный код - организовываем файловый ввод. Для чтения из файла используем метод getline(), где в качестве третьего параметра указываем пробел, являющийся разделителем в нашем файле.
#include <fstream>
#include <iostream>
#include <cstdlib>
//TODO: Описание списка
//TODO: Операции со списком
using namespace std;
int main()
{
char* fileName = new char[50];
char* buf_name = new char[20];
char* buf_value = new char [10];
cout << "Enter name of file -> ";
cin >> fileName;
ifstream* inp = new ifstream(fileName);
if (!inp->good())
{
cout << "File opening error!\n";
system("PAUSE");
return 0;
}
while (!inp->eof())
{
inp->getline(buf_name, 20, ' ');
inp->getline(buf_value, 10, ' ');
Кажется, тут все ясно и ничего не требует особого внимания. В первом разделе TODO мы опишем типы, необходимые для работы со списком, во втором у нас будут функции для работы с ним. Теперь приступим непосредственно к описанию списка, т.к. в программе мы уже вплотную подошли к его заполнению.
3.2. Описание динамического списка
Для начала, вспомним (или впервые узнаем)), что динамический список представляет из себя некоторое количество компонентов (узлов), содержащих непосредственно информационную часть (число, строка или более сложные типы данных), а также ссылку на следующий компонент (возможно, что узел содержит 2 ссылки: на следующий и на предыдущий, в таком случае, список называется двусвязным). Таким образом, получаем следующую структуру, описывающую компонент списка для нашей задачи:
struct comp {
char name[20]; // Имя переменной
char value[10]; // Значение переменной
comp* next; //Ссылка на следущий элемент списка
};
Сам же список представляет из себя совокупность его узлов и задается обычно одной или двумя ссылками, на первый элемент и последний. Нередко, хватает и одной из этих ссылок, но в нашем случае удобнее будет использовать обе. Итак, получаем структуру, описывающую наш список:
struct dyn_list {
comp* head; // Первый элемент (голова) списка
comp* tail; // Последний элемент (хвост) списка
};
Несложно понять, что значит создать пустой список. Фактически делать ничего не нужно, разве что присвоить ссылке на первый элемент списка (head) значение NULL. Оформим это как функцию, параллельно создав еще одну, проверяющую по этому условию, пуст ли список.
// Создание пустого списка
void constr_list(dyn_list &l)
{
l.head = NULL;
}
// Проверка списка на пустоту
bool chk_empty(dyn_list l)
{
return (l.head==NULL);
}
Видим, что все просто. Конечно, тип, описывающий список можно было оформи как класс, а функцию, создающую его сделать конструктором данного класса, но я оставлю это вам в качестве домашнего задания :. Теперь в функции main() описываем переменную типа dyn_list и создаем пустой список. Затем переходим к следующему пункту.
dyn_list vars; // Динамический список constr_list(vars);
3.3 Операции с компонентами списка
Ну, перед тем, как проводить какие-то операции с компонентами, их необходимо добавить в список, чем мы сейчас и займемся. Прежде всего, нам необходимо создать новый компонент и заполнить его информационную часть. Так как мы будем помещать его в конец списка, то ссылочная часть узла будет иметь значение NULL. Теперь давайте поймем, что должно происходить со ссылками head и tail при этой операции. Здесь рассматриваются 2 случая - наш список пуст или в нем есть хотя бы один компонент. Если пуст, то и head и tail будут указывать на только что созданный компонент. Если же узлы в списке присутствуют, очевидно, что сначала нужно последний узел связать с добавляемым (для этого ссылочной части компонента, на который указывает tail, присвоить адрес того, который хотим добавить), а затем "передвинуть" tail. Вот как просто все это выглядит на С++:
// Включение в список нового компонента
void comp_in(dyn_list &l, char* n, char* v)
{
comp* c = new comp();
strcpy_s(c->name, 20, n);
strcpy_s(c->value, 10, v);
c->next = NULL;
if (chk_empty(l))
l.head = c;
else
l.tail->next = c;
l.tail = c;
}
Теперь займемся поиском компонента. Искать будет по имени переменной, по желанию вы можете искать и по значению. В качестве аргументов, функции поиска передаем сам список и искомый текст. Возвращать наша функция будет адрес найденного узла или NULL, если ничего не найдено. Искать начнем с компонента, на который указывает head и, двигаясь вперед, сравнивать имя текущей переменной с искомым. В функции поиска мы можем не боясь, передвигать ссылку head, так как передаем ее не по ссылке.
// Поиск компонента в списке по имени
comp* search(dyn_list l, char *n)
{
while (l.head != NULL)
{
if (!strcmp(l.head->name,n))
return l.head;
l.head = l.head->next;
}
return l.head;
}
А сейчас удалим компонент. В качестве аргумента, передаем по ссылке список, а также ссылку на компонент, который собираемся удалить. В самой же функции рассматриваем 2 случая. Первый случай простой: если компонент является первым (то есть на него указывает head), то достаточно лишь переместить ссылку на первый элемент вперед. В противном случае, нам понадобится рабочая переменная-узел, которую мы будем использовать для движения по списку. Двигаться будем до тех пор, пока следующий за текущим узел не будет тем, который мы собираемся удалить. Ну а после этого, "перепрыгиваем" удаляемый компонент, присваивая ссылочной части предшествующего удаляемому компоненту адрес следующего за удаляемым. Все эти слова умещаются буквально в несколько строк исходного кода:
// Удаление компонента из списка
void comp_del(dyn_list &l, comp* c)
{
if (c == l.head)
{
l.head = c->next;
return;
}
comp* r = new comp();
r = l.head;
while (r->next != c)
r = r->next;
r->next = c->next;
delete c;
}
Последняя и самая простая операция - это изменение значения информационной части узла. Менять будем поле value. В качестве параметров, по ссылке передадим адрес компонента, а также новое значение изменяемого поля. Ну и в одну строчку все изменим. Вот как просто это выглядит:
// Изменение значения компонента
void comp_edit(comp &c, char* v)
{
strcpy_s(c.value, 10, v);
}
С операциями закончили, теперь осталось дописать программу.
3.4. Тестируем функции и завершаем программу
Ну, тут все просто, в цикле нам осталось лишь обратиться к функции добавления компонента в список. После цикла, тестируем остальные наши функции и выводим весь список в файл. Привожу здесь весь код функции main()
int main()
{
char* fileName = new char[50];
char* buf_name = new char[20];
char* buf_value = new char [10];
dyn_list vars; // Динамический список
cout << "Enter name of file -> ";
cin >> fileName;
ifstream* inp = new ifstream(fileName);
if (!inp->good())
{
cout << "File opening error!\n";
system("PAUSE");
return 0;
}
constr_list(vars);
while (!inp->eof())
{
inp->getline(buf_name, 20, ' ');
inp->getline(buf_value, 10, ' ');
comp_in(vars, buf_name, buf_value);
}
inp->close();
comp* p = new comp();
p = search(vars, "z");
if (p)
comp_del(vars, p);
p = search(vars, "abc");
if (p)
comp_edit(*p, "2");
ofstream* out = new ofstream(fileName);
while (vars.head != NULL)
{
out->write(vars.head->name, strlen(vars.head->name));
out->write(" ",1);
out->write(vars.head->value, strlen(vars.head->value));
out->write(" ",1);
vars.head = vars.head->next;
}
out->close();
system("PAUSE");
return 0;
}
Задача решена :
4. Выводы
Несмотря на то, что кому-то могла показаться сложной работа с динамическим списком, на деле все оказывается не только довольно просто, но еще и удобно - компоненты создаются и удаляются динамически, размерность списка ограничивается лишь доступной памятью, после того, как компонент больше не используется, память можно сразу же высвободить для других узлов.
В любом случае, использовать связанные списки в своих программах или нет, придется решать вам, надеюсь, моя статья хоть немного поможет вам в этом. Спасибо за внимание.
Оставить комментарий
Комментарии
http://sources.codenet.ru/download/5277/TLK_3_10_d8_src.html
Динамический список объектов (классов С++) с зачатками возможности совмещать разнотипные объекты в одном списке.
Функции сохранения в памяти в упакованном виде для пересылки по сети, сохранения на диске и в реестре.
а реально вектора и списки есть стандартные, а если нужны возможности поиска, то множества или мапы.
Описание связанного списка есть в любой книге по структурам данных...
Автор говорит о "программистах хорошо знакомых с С\С++". Программист С++ будет использовать std::list и std::vector, а не велосипед клепать. Программистам С не знакомы классы потокового ввода-вывода С++. Много чего еще сказать можно.
Для чего писалась статья?