Понятие динамической структуры данных

Содержание

Введение. 4

Указатель. 6

1.1. Определение указателя. 6

1.2. Понятие динамической структуры данных. 9

1.3.Переменные типа "массив". Арифметические операции с указателями. 11

1.4. Динамические массивы.. 13

Контрольные вопросы.. 13

Задания для практической работы.. 14

Абстрактный тип данных. 18

Линейный однонаправленный (односвязный) список. 18

1.1. Определение односвязного списка. 18

1.2. Операции обработки списка. 21

1.3. Создание класса для работы со списком.. 21

1.4. Реализация копирования списка с помощью класса. 22

Контрольные вопросы.. 24

Задания для практической работы.. 25

Линейные двунаправленные списки. 27

1.1. Определение двунаправленного списка. 27

Контрольные вопросы.. 29

Задания для практической работы.. 29

Структуры данных стеки и очереди. 31

1.1. Определение стека, очереди. 31

1.2. Представление стека. 31

1.3. Основные операции над стеком.. 32

1.4. Реализация стека на основе статического массива. 33

1.5. Реализация стека с использованием динамической памяти. 34

1.6. Представление статической очереди. 35

1.7.Представление динамической очереди. 37

Контрольные вопросы.. 38

Задания для практической работы.. 38

Структуры данных: деревья. 40

1.1. Определение структуры: дерево. 40

1.2. Обходы деревьев. 42

1.2.1. Алгоритмы обхода в глубину. 42

1.2.2. Алгоритмы обхода в ширину. 43

1.3. Ввод дерева. 44

1.4. Разрушение дерева. 44

1.5. Представление выражений с помощью деревьев. 45

Контрольные вопросы.. 46

Задания для практической работы.. 46

Литература. 48

 Введение

 

Алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату.

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

Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, чем бит, «строительные блоки» для организации произвольных данных получаются на основе понятия «структуры данного».

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

Понятие «физическая структура данных» отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти. Рассмотрение структуры данных без учета ее представления в машинной памяти называется абстрактной или логической структурой. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той среды, в которой она должна быть отражена. Вследствие этого различия существуют процедуры, осуществляющие отображение логической структуры в физическую и, наоборот, физической структуры в логическую. Эти процедуры обеспечивают, кроме того, доступ к физическим структурам и выполнение над ними различных операций, причем каждая операция рассматривается применительно к логической или физической структуре данных. Кроме того, в зависимости от размещения физических структур, а соответственно, и доступа к ним, различают внутренние (находятся в оперативной памяти) и внешние (на внешних устройствах) структуры данных.

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

Составными называются такие структуры данных, составными частями которых являются другие структуры данных – элементарные или в свою очередь составные. Составные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.

Важный признак составной структуры данных – характер упорядоченности ее частей. По этому признаку структуры можно делить на линейные и нелинейные структуры.

Весьма важный признак структуры данных – ее изменчивость, т. е. изменение числа элементов и/или связей между составными частями структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры статические и динамические.

Рис.1. Классификация структур данных

 

В языках программирования понятие «структуры данных» тесно связано с понятием «типы данных». Любые данные, т. е. константы, переменные, значения функций или выражения, характеризуются своими типами.

Информация по каждому типу однозначно определяет:

– структуру хранения данных указанного типа, т. е. выделение памяти, представление данных в ней и метод доступа к данным;

– множество допустимых значений, которые может иметь тот или иной объект описываемого типа; – набор допустимых операций, которые применимы к объекту описываемого типа.

Далее рассматриваются структуры данных и соответствующие им типы данных. Базы данных детально изучаются в рамках отдельных дисциплин, и здесь рассматриваться не будут.

При описании элементарных типов и при конструировании составных типов использовался в язык программирования Си++.

Указатель

 

Определение указателя

 

Значением типа указатель является адрес участка памяти, выделенного для объекта конкретного типа (ссылка на объект). Связь указателя P с объектом можно изобразить следующим образом:

По указателю осуществляется обращение (доступ) к объекту.

Определение переменной типа указатель:

type *имя_указателя;

где type – обозначение типа, на который будет указывать переменная с именем (идентификатором) имя_указателя.

Символ ‘*’ - это унарная операция раскрытия ссылки (операция разыменования, операция обращения по адресу, операция доступа по адресу), но в данном контексте служит признаком типа указатель.

При определении переменной-указателя можно выполнить инициализацию:

type *имя_указателя инициализатор;

Инициализатор имеет две формы записи, поэтому допустимо:

type *имя_указателя = инициализирующее_ выражение;

type *имя_указателя (инициализирующее_ выражение);

Инициализирующее_ выражение – это константное выражение, которое может быть задано указателем, уже имеющим значение или выражением, позволяющим получить адрес объекта с помощью операции & - получение адреса операнда.

 

Пример 1.1:

 

char cc = ‘f’, *p;	//Определение символьной переменной сс и //неинициализированного указателя на объект типа char
int *p1, *p2;	//Определение двух неинициализированных //указателей p1 и p2 на объекты типа int
сhar *pc = &cc;	//Инициализированный указатель на объект типа char
char *ptr (NULL);	//Нулевой указатель на объект типа char
int *mas [10];	//Массив из 10 указателей на объекты типа int
int (*point) [10];	//Указатель на массив из 10 элементов типа int
struct list *n, *pr;	//Два указателя n и pr на объекты именованного структурного //типа list. Определение типа list должно либо предшествовать //данному определению, либо находиться в пределах области //действия данного определения
struct list { char b; int *k;   } line;	//Определение переменной line структурного типа list, //один из элементов которой типа указатель на объект //типа int
int **pp = &p1;	//Указатель pp – это указатель на указатель. Он инициирован //значением адреса указателя p1 на объект целого типа. //Это допустимо, так как указатель – это тоже объект в памяти

Переменной типа указатель можно задать значение:

- присваивая ей адрес объекта с помощью операции & (тип объекта должен быть тот же, что и тип объекта, на который ссылается указатель);

- присваивая ей значение другой переменной или выражения типа указатель (типы объектов, на которые они ссылаются должны быть одинаковыми);

-   с помощью операции new.

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

- присваивание;

- получение адреса;

- сложение и вычитание;

- инкремент и декремент;

- операции отношения.

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

С помощью переменной типа указатель и операции разыменования * можно обращаться к объекту, на который она ссылается.

 

Пример 1.2 (с учетом описаний в примере 1.1):

 

int a = 10, b = 20, c = 30; int x[3][10];
ptr = pc;	//Указатели ptr и pc ссылаются на одну и ту же //переменную cc типа char
*ptr = ‘+’;	//Объект, на который указывают ptr и pc (т.е. //сс), получил новое значение
p1 = &a;	//Указатель p1 получил значение адреса целой //переменной а
p2 = &b;	//Указатель p2 – значение адреса целой / /переменной b
mas[0] = p1;	//Элемент массива mas[0] типа указатель //получил то же значение, что и указатель p1
mas[1] = &b;	//Указатель mas[1] получил значение адреса
b *mas[0] = 15;	//Переменная типа int, на которую указывают и p1 и //mas[0],//т.е. переменная a получила новое //значение
*p2 = 25;	//Переменная b получила новое значение
point = &x[0];	//Указатель point получил значение адреса нулевого //элемента массива x, т.е. адреса элемента x[0][0]
point[0] = a;	//Элементу массива с индексом 0, на который //указывает point присваивается значение /переменной a
*(point + 1) = b;	//Элементу массива, на который указывает //point + 1, т.е. элементу x[0][1] присваивается //значение b
n = &line;	//Указателю n присвоен адрес структуры line
pr = n;	//Указатели n и pr ссылаются на одну переменную
(*n).b = *ptr;	//Элементу b структуры, на которую ссылается //n, присваивается значение объекта, на который //ссылается ptr, т.е. line.b получила значение ‘+’
pr -> k = p1;	//Элементу k структуры, на которую ссылается //pr присваивается значение указателя p1, т.е. //line.k получила значение адреса целой //переменной a

 

Для пояснения смысла операций "*" и "&" рассмотрим программу 1.1.

 

Программа 1.1:

 

#include <iostream.h>

typedef int* IntPtrType;

int main()

{

IntPtrType ptr_a, ptr_b;

int num_c = 4, num_d = 7;

ptr_a = &num_c;                        /* СТРОКА 10 */

ptr_b = ptr_a;                            /* СТРОКА 11 */

cout << *ptr_a << " " << *ptr_b << "\n";

ptr_b = &num_d;                      /* СТРОКА 13 */

cout << *ptr_a << " " << *ptr_b << "\n";

*ptr_a = *ptr_b;                        /* СТРОКА 15 */

cout << *ptr_a << " " << *ptr_b << "\n";

 cout << num_c << " " << *&*&*&num_c << "\n";

return 0;

}

Программа выдает на экран следующие сообщения:

4 4

4 7

7 7

7 7

Графически состояние программы 1.1 после выполнения операторов присваивания в 10-11-й строках, 15-й и 19-й показано, соответственно, на рис. 1, 2 и 3.

 

Рис.1. Состояние программы 1.1 после выполнения 10-й и 11-й строк

 

 

Рис.1. Состояние программы 1.1 после выполнения 13-й строки

 

Рис.1. Состояние программы 1.1 после выполнения 15-й строки

 

Операции "*" и "&", в некотором смысле, являются взаимно обратными, так что выражение "*&*&*&num_c" означает то же самое, что и "num_c".

 

Динамические массивы

 

Правила создания и уничтожения динамических переменных типов "int", "char", "double" и т.п. распространяются и на динамические массивы. По отношению к массивам динамическое распределение памяти особенно полезно, поскольку иногда бывают массивы больших размеров.

Динамический массив из 10-ти целых чисел можно создать следующим образом:

int* number_ptr;

number_ptr = new int[10];

Для уничтожения динамического массива применяется оператор "delete" c квадратными скобками "[ ]":

delete[] number_ptr;

Скобки "[]" играют важную роль. Они сообщают оператору, что требуется уничтожить все элементы массива, а не только первый. Работа с динамическими массивами показана в  приведенном фрагменте программы. У  пользователя запрашивается список целых чисел, затем вычисляется и выводится на экран их среднее значение....

Пример 1.7:

...

int no_of_integers, *number_ptr;

cout << "Введите количество целых чисел в списке: ";

cin >> no_of_integers;

number_ptr = new int[no_of_integers];

if (number_ptr == NULL)

{

cout << "Извините, недостаточно памяти.\n";

exit(1);

}

cout << "Наберите " << no_of_integers;

cout << " целых чисел, разделяя их пробелами:\n";

for (int count = 0; count < no_of_integers; count++)

cin >> number_ptr[count];

cout << "Среднее значение: ";

cout << average(number_ptr, no_of_integers);

delete[] number_ptr;

... Динамические массивы, как и обычные, можно передавать в качестве параметров функций.

 

Контрольные вопросы

 

1. Что является значением типа указатель?
2. Определение указателя?
3. Как задать значение переменной типа указатель?
4. Какие операции допустимы над указателем?
5. Как с помощью переменной типа указатель и операции разыменования можно обращаться к объекту?
6. Чем характеризуется статическая структура данных?
7. Чем характеризуется динамическая структура данных?
8. Какая операция используется для создания динамической структуры?
9. Действия операции new?
10. Уничтожение динамического объекта?
11. Понятие «висячая» ссылка?
12. арифметические  операции с указателями на примере массива?
13. Правила создания и уничтожения динамического массива?

 

Задания для практической работы

Задание 1. Определить в функции main() переменные и массивы в соответствии с вариантом:

Вариант 1:                                                        

1. Одномерный символьный массив:

2. Указатель  на тип char:

3. Статический одномерный массив целых чисел:

4. Указатель на массив целых чисел:

5. Трехмерный массив целых чисел;

6. Указатель на двумерный массив целых чисел.     

Вариант 2:                                                        

1. Одномерный массив плавающих чисел;

2. Указатель на тип float;

3. Статический одномерный массив целых чисел;

4. Указатель  на массив unsigned int;

5. Трехмерный массив символов;

6. Указатель на двумерный массив символов.

Вариант 3:                                                         

1. Одномерный массив целых чисел;

2. Указатель на тип int;

3. Статический одномерный символьный массив;

4. Указатель  на массив символов;

5. Трехмерный массив плавающих чисел;

6. Указатель на двумерный массив плавающих чисел.        

Вариант 4:                                                        

1.  Одномерный символьный массив;

2. Указатель на тип char;

3. Статический одномерный массив типа double;

4. Указатель  на массив типа double;

5. Трехмерный массив целых чисел;

6. Указатель на двумерный массив целых чисел.

Вариант 5:                                                        

1. Одномерный символьный массив;

2. Указатель на тип char;

3. Статический одномерный массив длинных чисел;

4. Указатель  на массив длинных целых чисел;

5. Трехмерный массив плавающих чисел;

6. Указатель  на двумерный массив плавающих чисел.       

Вариант 6:                                                        

1.  Одномерный массив целых чисел;

2. Указатель на тип int;

3. Статический одномерный массив плавающих чисел;

4. Указатель  на массив плавающих чисел;

5. Трехмерный массив символов;

6. Указатель  на двумерный массив символов.

Вариант 7:                                                        

1. Одномерный массив длинных целых чисел;

2. Указатель на тип long int;

3. Статический одномерный массив символов;

4. Указатель на массив символов;

5. Трехмерный массив целых чисел;

6. Указатель на двумерный массив целых чисел.     

Вариант 8:                                                        

1. Одномерный массив типа double;

2. Указатель на тип double;

3. Статический одномерный массив целых чисел;

4. Указатель на массив unsigned int;

5. Трехмерный массив символов;

6. Указатель на двумерный массив символов.

Вариант 9:                                                        

1.  Одномерный массив типа float;

2. Указатель на тип float:

3. Статический одномерный массив символов:

4. Указатель  на массив символов:

5. Трехмерный массив целых чисел:

6. Указатель на двумерный массив целых чисел.     

Вариант 10:                                                      

1. Одномерный массив целых чисел;

2. Указатель на тип unsigned int;

3. Статический одномерный массив символов;

4. Указатель  на массив символов;

5. Трехмерный массив целых чисел;

6. Указатель  на двумерный массив целых чисел.

Вариант 11:                                                      

1. Одномерный символьный массив:

2. Указатель на тип char:

3. Статический одномерный массив коротких целых чисел:

4. Указатель на массив коротких целых чисел:

5. Трехмерный массив целых чисел:

6. Указатель на двумерный массив целых чисел.     

Вариант 12:                                                      

1.  Одномерный массив типа float;

2. Указатель на тип float;

3. Статический одномерный массив символов;

4. Указатель на массив символов;

5. Трехмерный массив unsigned int;

6. Указатель на двумерный массив целых чисел.

Вариант 13:                                                      

1. Одномерный массив коротких целых чисел:

2. Указатель на тип short int:

3. Статический одномерный массив символов:

4. Указатель на массив символов:

5. Трехмерный массив целых чисел:

6. Указатель на двумерный массив целых чисел.     

Вариант 14:                                                      

1.      Одномерный символьный массив;

2. Указатель на тип char;

3. Статический одномерный массив плавающих чисел;

4. Указатель  на массив плавающих чисел;

5. Трехмерный массив целых чисел;

6. Указа гель на двумерный массив целых чисел.

Вариант 15:                                                      

1.  Одномерный массив типа double;

2. Указатель на тип double:

3. Статический одномерный массив целых чисел;

4. Указатель на массив целых чисел;

5. Трехмерный массив символов;

6. Указатель на двумерный массив символов.          

Вариант 16:                                                      

1. Одномерный массив целых чисел;

2. Указатель на тип int:

3. Статический одномерный массив типа double;

4. Указатель на массив тина double:

5. Трехмерный массив символов;

6. Указатель на двумерный массив символов.

Вариант 17:                                                      

1. Одномерный символьный массив:

2. Указатель  на тип char:

3. Статический одномерный массив целых чисел:

4. Указатель на массив целых чисел:

5. Трехмерный массив целых чисел;

6. Указатель на двумерный массив целых чисел.     

Вариант 18:                                                      

1. Одномерный массив плавающих чисел;

2. Указатель на тип float;

3. Статический одномерный массив целых чисел;

4. Указатель  на массив unsigned int;

5. Трехмерный массив символов;

6. Указатель на двумерный массив символов.

Вариант 19:                                                       

1. Одномерный массив целых чисел;

2. Указатель на тип int;

3. Статический одномерный символьный массив;

4. Указатель  на массив символов;

5. Трехмерный массив плавающих чисел;

6. Указатель на двумерный массив плавающих чисел.        

Вариант 20:                                                      

1.  Одномерный символьный массив;

2. Указатель на тип char;

3. Статический одномерный массив типа double;

4. Указатель  на массив типа double;

5. Трехмерный массив целых чисел;

6. Указатель на двумерный массив целых чисел.

Вариант 21:                                                      

1. Одномерный символьный массив;

2. Указатель на тип char;

3. Статический одномерный массив длинных чисел;

4. Указатель  на массив длинных целых чисел;

5. Трехмерный массив плавающих чисел;

6. Указатель  на двумерный массив плавающих чисел.       

Вариант 22:                                                      

1.  Одномерный массив целых чисел;

2. Указатель на тип int;

3. Статический одномерный массив плавающих чисел;

4. Указатель  на массив плавающих чисел;

5. Трехмерный массив символов;

6. Указатель  на двумерный массив символов.

Вариант 23:                                                      

1. Одномерный массив беззнаковых целых чисел;

2. Указатель на тип unsigned int;

3. Статический одномерный массив символов;

4. Указатель  на массив символов;

5. Трехмерный массив целых чисел;

6. Указатель  на двумерный массив целых чисел.

Вариант 24:                                                      

1. Одномерный символьный массив:

2. Указатель на тип char:

3. Статический одномерный массив коротких целых чисел:

4. Указатель на массив коротких целых чисел:

5. Трехмерный массив целых чисел:

6. Указатель на двумерный массив целых чисел.     

Вариант 25:                                                      

1.  Одномерный массив типа float;

2. Указатель на тип float;

3. Статический одномерный массив символов;

4. Указатель на массив символов;

5. Трехмерный массив unsigned int;

6. Указатель на двумерный массив целых чисел.

 

Задание 2. В функции main() выполнить следующие действия:

1. Проверить содержимое массива №1 (с помощью цикла for и операции вывода cout<<).

2. Ввести данные в массив №1 (с помощью цикла for и операции ввода cin>>).

3. Еще раз проверить содержимое этого массива, сделать выводы.

4. Присвоить указателю №2 адрес массива №1, вывести на экран адреса массива и указателя и содержимое указателя. Сделать выводы.

5. Повторить пункт 3 для указателя, содержащего адрес массива. Сделать выводы.

6. Повторить пункты 1 - 3 для статического массива №3. Сделать выводы.

7. Используя имеющийся указатель №2, создать динамический массив и повторить для него пункты 1—3. Сделать выводы.

8. Удалить динамический массив. Используя указатель №4, создать двумерный динамический массив и повторить для него пункты 2. 3. Сделать выводы. Удалить двумерный динамический массив.

9. Вывести на экран любой из элементов трехмерного массива №5. использую операцию индексации.

10. Повторить пункт 9. используя имя массива как указатель и операцию

доступа по указателю.

11.      Присвоить указателю №6 на двумерный массив адрес трехмерного массива №5. Повторить для этого указателя пункт 10. Сделать выводы.

Текст программы следует дополнить сообщениями о вводе и выводе данных. Такие сообщениям облегчат контроль выполнения программы.

Абстрактный тип данных

 

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

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

Чтобы описать набор операций некоторого абстрактного типа данных на языке C++, требуется определить класс, в котором эти операции будут объявлены как методы класса. Такое описание определяет интерфейс взаимодействия с абстрактным типом данных. Чаще всего никакой реализации этих методов непосредственно в интерфейсе не подразумевается, поэтому можно не задавать тела соответствующих функций, оставляя их "чистыми". Это означает, что объектов описанного класса не существует, а соответствующий класс называется в C++ абстрактным классом. Такой класс будет служить базовым классом для реализации конкретных представлений (воплощений, реализаций) объектов, заданных абстрактно.

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

Операции обработки списка

Основными операциями обработки списка являются:

1) включение (вставка) в список нового элемента перед или после заданного элемента (в том числе перед первым элементом или после последнего); включению, как правило, предшествует поиск элемента после и/или перед которым происходит включение; при включении элемента перед первым в список без заглавного звена меняется заголовок списка; при включении после некоторого элемента меняется ссылочное поле у элемента, после которого происходит включение, поэтому надо определять ссылку на элемент после которого происходит включение;

2) исключение (удаление) заданного элемента из списка (в том числе удаление первого элемента или последнего); исключению, как правило, предшествует поиск, исключаемого элемента; результатом поиска должна быть ссылка на элемент предшествующий исключаемому, так как при удалении элемента из списка меняется ссылочное поле у элемента, предшествующего удаляемому; при удалении первого элемента в списке без заглавного звена меняется заголовок списка;

3) поиск заданного элемента по его значению или порядковому номеру; операция заканчивается, когда элемент найден или просмотрен весь список (если элемента нет); результат операции должен определять, есть ли элемент в списке или нет и, если есть, то возможно его адрес или значение;

4) определение числа звеньев списка;

5) упорядочение элементов списка по значению информационного поля.

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

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

Листинг 1: Определение класса IntList

файл intlist.h

 

class IntList {

/* Класс ListItem представляет элемент списка, связанный со следующим с помощью указателя, содержащегося в поле next */

struct ListItem

{

int item;               // значение элемента списка

Listltem *next;      // указатель на следующий элемент списка

 

// Конструктор для создания нового элемента

ListItem(int i, Listltem *n = NULL) { item = i; next = n; }

};

int count;                  // счетчик числа элементов

ListItem *first;      // первый элемент списка

ListItem *last;       // последний элемент списка

 

public:

 

// Конструктор по умолчанию - создание пустого списка

IntLis() { count = 0; first = last = NULL; }

 

// Конструктор копирования - создание копии имеющегося списка

IntList(const IntList & src);

 

// Деструктор списка

~IntLis();

 

// Доступ к первому элементу списка

int head() const { return first->item; }

int & head() { return first->item; }

 

// Доступ к последнему элементу списка

int tail() const { return last->item; }

int & tail() { return last->item; }

 

// Добавить один элемент в начало списка

void addFirst(int item);

 

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

void addLast(int item);

 

// Добавить элементы другого списка в конец этого

void addLast(const IntList & src);

 

// Удалить первый элемент

int removeFirst();

 

// количество элементов списка

int getCount() { return count; }

}; // Конец определения класса IntList

Файл intlist. cpp

#include "intlist.h"

// Реализация конструктора копирования

IntList::IntList(const IntList & src) {

count = 0;

first = last = NULL;

addLast(src); // добавляет список src в конец списка this

}

 

// Реализация деструктора

IntList::~IntList()

{

ListItem *current = NULL; // указатель на элемент, подлежащий удалению

ListItem *next = first;       // указатель на следующий элемент

while (next)                         // пока есть еще элементы в списке

{ current = next;

next = next->next;              // переход к следующему элементу

delete current;                     // освобождение памяти

}

}

 

// Добавление одного элемента в начало списка

void IntList::addFirst(int item)

{

ListItem *newItem = new ListItem(item, first);

// создаем новый элемент и присоединяем его к началу списка

 

if (first == NULL) {

// если список был пуст - новый элемент будет и первым, и последним

last = newItem;

}

first = newItem;

count++;                            // число элементов списка увеличилось.

}

 

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

void IntList:raddLast(int item) {

// создаем новый элемент списка

ListItem *newItem = new ListItem(item);

if (last == NULL) {

// список был пуст - новый элемент будет и первым, и последним

first = newItem;

} else {

// новый элемент присоединяется к последнему элементу списка

last->next = newItem;

}

last = newltem;

count++;                            // число элементов списка увеличилось.

}

 

// Добавление элементов заданного списка в конец определяемого

void IntList::addLast(const IntList & src) {

for (ListItem *cur = src.first; cur; cur = cur->next)

addLast(cur->item);           // используем добавление одного элемента

}

// Удаление первого элемента из списка

int IntList::remove() {

int res = first->item;           // содержимое первого элемента

first = first->next;              // второй элемент становится первым

count--;                                    // число элементов списка уменьшилось

return res;                 // удаленный элемент возвращается в качестве результата

}

 

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

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

 

 

Рис.5. Удаление элемента из середины списка

Добавьте самостоятельно в класс IntList недостающие операции.

Контрольные вопросы

 

1. Дайте определение динамической структуре список.

2. Сколько элементов может содержать список? Как заканчивается список?

3. Сколько полей может содержать элемент списка? От чего зависит количество полей? Приведите примеры.

4. Какого типа могут быть поля элементов списка? Приведите примеры.

5. Обязательно ли применять процедуру освобождения памяти, занятой элементом, когда мы избавляемся от этого элемента в списке? Каким образом это влияет на работу программы?

6. Можно ли ссылку одного элемента направить сразу на два или больше других элемента? Как необходимо поменять тип указателя, чтобы решить эту проблему?

7. Может ли элемент списка быть такого типа, чтобы содержать несколько полей типа указателя? Если – да, то приведите пример для чего это может быть нужно.

8. Можно ли последовательно "связать" два списка разного типа и почему?

9. Можно ли одновременно работать с несколькими списками сразу?

10.  Как Вы считаете, на что нужно обращать особое внимание при работе со списками?

Задания для практической работы

1.Задан текст, состоящий из строк, разделенных пробелом и оканчивающийся точкой. Написать подпрограмму поиска заданного элемента в списке. Используя эту подпрограмму:

а) подсчитать к