Динамические структуры в C++

  • 30 авг. 2010 г.
  • 1106 Слова
ГОУ ВПО
Российский Государственный Университет
инновационных технологий и предпринимательства
Пензенский филиал

Кафедра «Информационных систем»

Курсовая работа
по дисциплине:

“Технология программирования”

Тема: “Динамические структуры в C++”

Выполнил: студент гр.07И1 Наумов С.Ю.Проверил: : к.ф.-м.н. доц., Горюнов Ю.Ю.

Пенза 2009.
Постановка задачи
Задание. Создать программу для выполнения следующих действий над линейными списками с целочисленными данными:
• создание списка;
• дополнение списка;
• вывод элементов списка на экран;
• увеличение на два каждого элемента списка;
• запись элементов списка в файле;
•чтение списка из файла.
• Вариант 14.Удалить из списка каждый третий элемент.
Дополнительные требования к программе:
1. программа должна содержать меню для выбора нужного действия;
2. программа должна состоять из двух модулей:
1) в главном модуле (файл с расширением cpp) должны находится меню и обращения к функциям, которые выполняют действия над списками;
2) объявленияфункций должны находится в заголовочном файле (файл с расширением h).

Теоретическая часть

Динамические структуры данных

Динамические структуры данных используются в тех случаях, когда основной составляющей обработки данных является их удаление и/или вставка.
Рассмотренные выше динамические массивы являются динамическими структурами лишь отчасти.
Наиболее распространённым видом динамическойструктуры данных является список. Списком называется совокупность элементов типа структура, одно или более полей которой имеет тип указатель на элемент списка.

Виды наиболее часто используемых списков
• Линейный (односвязный, однонаправленный) список или цепь – одно поле типа указатель на элемент списка:

• Кольцевой список – последний элемент линейного списка содержит указатель на первыйэлемент списка:

• Двунаправленный (двухсвязный) список – два поля типа указатель, один из которых указывает на следующий элемент списка, а второй, например, на предыдущий.

Бинарное дерево – у элементов списка два поля типа указатель, один на левое, а второй на правое поддерево:

Напомним, что стрелка означает "указывает на" или "содержит адрес".

Основные операции над списками

1.Объявление типа элементов списка.
2. Создание списка.
3. Добавление элемента в список.
4. Удаление элемента из списка.
5. Обход списка.
Указанные действия над списками рассмотрим на примере линейного списка, элементы которого имеют тип структура, одно поле которой имеет тип int и в нём будут храниться данные, а другое – тип указатель.

Объявление типа элементов линейного списка

struct Elem// Графическая иллюстрация
{ int Data;
Elem *Next;
};

Создание линейного списка

Elem *Create(int d)
{ Elem *pl = new Elem;
pl -> Data = d;
pl -> Next = (;
return pl; }
Примечания.
• Если переменная (pl) объявлена типа указатель на структуру (Elem), то для обращения к её полям необходимо использовать операцию стрелка "->".
• d означает аргумент функции, значениекоторого присваивается полю Data.
• 0 в поле Next является признаком конца линейного списка.

Вставка элемента в начало линейного списка

// Первый аргумент у функции InsFirst имеет тип указатель на первый элемент списка, в начало которого вставляем элемент со значением поля Data равным d.
Elem *InsFirst(Elem *pl, int d)
{ Elem *p = new Elem;
p->Data = d;
p->Next = pl;
pl = p;
returnpl;
}
Примечание. Функцию InsFirst можно использовать и для создания списка:
Elem * p = 0; p = InsFirst(p, d);
причём перед обращением к функции InsFirst с целью создания списка операция присваивания p = 0 обязательна.

Обход линейного списка

void ShowList(Elem *pl) // Аргумент указывает на первый элемент списка.
{ while(pl) // Пока pl ( 0, (пока не...
tracking img