Работа со структурами данных: программирование списков на языке C /C++

КУРСОВАЯ РАБОТА

Работа со структурами данных: программирование списков на языке C /C++

Ишимбай 2012

СОДЕРЖАНИЕ

Введение

1 Постановка задачи

1.1 Общая характеристика задачи

1.2 Динамические двусвязные списки

2              Разработка алгоритма задачи

2.1 Описание данных, используемых для решения задачи

2.2 Описание схемы программы

3 Кодирование программы

3.1 Описание структуры разрабатываемого пакета

4 Тестирование программы

4.1 Внешний вид программы

4.2 Работа программы

Заключение

Список используемой литературы:

Приложение А (Динамический двунаправленный список)

Введение

Язык Си, созданный Денисом Ритчи в начале 70-х годов в Bell Laboratory американской корпорации AT&T, является одним из универсальных языков программирования. Язык Си считается языком системного программирования, хотя он удобен и для написания прикладных программ. Среди преимуществ языка Си следует отметить переносимость программ на компьютеры различной архитектуры и из одной операционной системы в другую, лаконичность записи алгоритмов, логическую стройность программ, а также возможность получить программный код, сравнимый по скорости выполнения с программами, написанными на языке ассемблера. Последнее связано с тем, что хотя Си является языком высокого уровня, имеющим полный набор конструкций структурного программирования, он также обладает набором низкоуровневых средств, обеспечивающих доступ к аппаратным средствам компьютера. С 1989 года язык Си регламентируется стандартом Американского института национальных стандартов ANSI С. В настоящее время, кроме стандарта ANSI C разработан международный стандарт ISO C (International Standard Organization C).

В течение многих лет стандартом C де-факто была версия, поставляемая для операционной системы UNIX System V. Растущая популярность компьютеров привела к созданию множества приложений для C.

C часто называют языком среднего уровня. Это определение означает, что он объединяет элементы языков высокого уровня с функциональностью ассемблера.

Известно, какое значение приобретает сегодня объектно-ориентированное программирование, учитывая возрастающие требования к качеству, надежности и пользовательскому интерфейсу приложений. Сложность и объем программ все время растут. В свете этого объектно-ориентированные языки, и прежде всего C++, становятся едва ли не единственным средством решения встающих перед программистом задач.

1 Постановка задачи

1.1 Общая характеристика задачи

Разработать программу на языке C++ для обработки данных типа структура с именем AVTOTICKET, содержащей поля: номер билета, маршрут, время продажи (час минута), цена билета. Хранение данных организовать в виде двухсвязного динамического списка.

Обеспечить выполнение следующих операций:

      Создание нового списка;

      Удаление списка;

      Вывод на экран всех элементов списка;

      Добавление и удаление элементов из списка;

      Поиск в списке по заданному ключу;

      Выборка из списка билетов, проданных с 7 до  вечера.

Интерфейс работы программы организовать в виде меню.

1.2 Динамические двусвязные списки

Очень часто, при разработке приложений, оперирующих с большим количеством входных данных, возникает вопрос об их хранении во время выполнения программы. Данный тип решает вопрос хранения данных. Главным из них, является его фиксированный размер. Это свойство не поддается изменению даже у динамически созданных массивов, что довольно часто заставляет программистов, использующих исключительно их, выделять память "с запасом". Ну а во-первых, даже "запас" ограничен, и никто не может дать гарантии, что и его будет достаточно, а во-вторых, наоборот, "запаса" может хватить настолько, что немалая часть отведенной программе памяти будет занята понапрасну.

Данную проблему решает другой тип хранения данных - связанный список динамических переменных - динамический список. Компоненты добавляются и удаляются во время выполнения программы, и их количество зависит исключительно от размера доступной памяти. Если в случае с массивом, в любой момент можно получить доступ к любому компоненту, то в случае со списком, в один момент времени доступны максимум 3 компонента (это зависит от способа представления списка в программе).

Для демонстрации реализации работы с динамическим списком, решим задачу:

"В текстовом файле находятся идентификаторы переменных и их числовые значения (например: x 15 abc 12.098 z -1.23). Перенести их в динамический список, для которого реализовать следующие операции: поиск идентификатора в списке; изменение значения указанного идентификатора; удаление идентификатора из списка, добавление в список нового идентификатора с заданным значением.

Создается консольный проект, и пишется довольно стандартный код - организовываем файловый ввод. Для чтения из файла используем метод 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 мы описываются типы, необходимые для работы со списком, во втором описываются функции для работы с ним. Теперь приступим непосредственно к описанию списка, т.к. в программе мы уже вплотную подошли к его заполнению.

Описание динамического списка

Динамический список представляет из себя некоторое количество компонентов (узлов), содержащих непосредственно информационную часть (число, строка или более сложные типы данных), а также ссылку на следующий компонент (возможно, что узел содержит 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);

Операции с компонентами списка

Ну, перед тем, как проводить какие-то операции с компонентами, их необходимо добавить в список, чем мы сейчас и займемся. Прежде всего, нам необходимо создать новый компонент и заполнить его информационную часть. Так как мы будем помещать его в конец списка, то ссылочная часть узла будет иметь значение 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. В качестве параметров, по ссылке передадим адрес компонента, а также новое значение изменяемого поля. Ну и в одну строчку все изменим. Вот как просто это выглядит: