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

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

а) подсчитать количество вхождений заданного символа в каждую строку текста. Вхождение задавать номером строки и номером позиции в строке;

б) найти все вхождения (см. пункт 1.а) заданного символа в текст;

в) найти первое вхождение (см. пункт 1.а) каждой десятичной цифры в текст;

г) найти первое вхождение (см. пункт 1.а) гласных латинских букв в текст;

д) подсчитать количество вхождений четных (нечетных) десятичных цифр в каждую строку текста;

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

ж) удалить все вхождения заданного символа из текста;

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

и) если в строке текста содержится заданный символ, то переместить его на место первого символа в этой строке;

к) если в строке текста содержится заданный символ, то переместить его на место последнего символа в этой строке.

2.Даны действительные числа x1, x2,..., xn (n >= 2 и заранее неизвестно). Получить последовательность (x1 – xn), (x2 – xn),..., (xn-1 – xn).

3.Дана последовательность действительных чисел a1, a2,..., an (n >= 2 и заранее неизвестно). Если последовательность упорядочена по неубыванию, то оставить ее без изменения, иначе получить последовательность an, an-1,..., a1.

4.Для заданных полиномов Pn(x) и Qn(x) найти полином R - сумму полиномов P и Q. Каждый полином представить в виде списка:

Причем в список   

а) включать,     

б) не включать и коэффициенты равные нулю.

Считать, что входные данные не содержат равных нулю коэффициентов.

5. Дана последовательность символов s1, s2,..., sn (n >= 2 и заранее неизвестно). Получить те символы, принадлежащие последовательности, которые входят в нее по одному разу.

6. Дана последовательность символов s1, s2,..., sn (n >= 2 и заранее неизвестно). Получить последовательность символов, содержащую только последние вхождения каждого символа в строку с сохранением их исходного взаимного порядка.

7. Дана последовательность символов s1, s2,.... Известно, что s1 отличен от точки и, что среди s2, s3,... имеется хотя бы одна точка. Пусть s1, s2,..., sn - символы, предшествующие первой точке. Получить последовательность s1, s3,..., sn, если n нечетно и последовательность s2, s4,..., sn, если n четно.

8. Написать программу, которая удаляет из списка М второй элемент, если такой есть.

9. Написать программу, которая удаляет из списка М N-ый элемент, если такой есть. N задает пользователь.

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

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

12. Написать программу, которая удаляет из списка М первый отрицательный элемент, если такой есть.

13. Написать программу, которая удаляет из списка М все отрицательные элементы.

14. Написать программу, которая формирует список М, включив в него по одному разу элементы, которые входят хотя бы в один из списков М1 и М2.

15. Написать программу, которая формирует список М, включив в него по одному разу элементы, которые входят одновременно в оба списка М1 и М2.

16. Написать программу, которая формирует список М, включив в него по одному разу элементы, которые входят в список М1, но не входят в список М2.

17.  Написать программу, которая меняет местами первый и второй элементы непустого списка. Если элементы не найдены, то выдать на экран соответствующие сообщение.

18. Написать программу, которая меняет местами первый и пятый элементы непустого списка. Если элементы не найдены, то выдать на экран соответствующие сообщение.

19. Написать программу, которая меняет местами первый и последний элементы непустого списка. Если элементы не найдены, то выдать на экран соответствующие сообщение.

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

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

22. Написать программу, которая проверяет на равенство списки М1 и М2.

23. Написать программу, которая определяет, входит ли список М1 в список М2. Предполагается, что списки существуют.

24. Написать программу, которая копирует в конец непустого списка М его первый элемент. Если элементы не найдены, то выдать на экран соответствующие сообщение.

25. Написать программу, которая копирует в начало непустого списка М его последний элемент. Если элементы не найдены, то выдать на экран соответствующие сообщение.

26. Написать программу, которая копирует в список М за каждым вхождением заданного элемента все элемента списка М1.

27. Написать программу, которая объединяет два упорядоченных по неубыванию списка М1 и М2 в один упорядоченный по неубыванию список, построив новый список М.

28. Написать программу, которая объединяет два упорядоченных по неубыванию списка М1 и М2 в один упорядоченный по неубыванию список, сменив соответствующим образом ссылки в М1 и М2.

29. Написать программу, которая проверяет, упорядочены ли элементы списка по алфавиту.