5. Примеры связных списков
Класс связного списка [3] является довольно популярным базовым классом, на котором построено множество других классов. Рассмотрим реализацию класса списка.
//********************************//
// Программа для обработки объектов//
// классов "список", "двусвязный //
// список", "закольцованный список" //
//-------------------------------------------------//
// Автор: Каширин Д.И. //
//------------------------------------------//
// Версия: 07.12.02 v. 1.01.2 //
//
//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream.h>
#include <alloc.h>
#include <conio.h>
#define IMAX 4
class List{ // Класс "Список"
protected:
float Value; // Значение эл-та списка
List *Next; // @ след. эл-та списка
public:
void AddElList(char);
void OutpList(char);
void DelElList(int);
void AddElList(float, char);
void CreateList();
List(const char *Ident) // Конструктор класса
{
cout << "Lead the value of the first "; //Запрос на ввод
// значения
cout << "element of list "<<Ident<< ;
cin >> Value; // Чтение первого эл-та
Next = NULL; // 1-й эл-т ссылается на NULL
}
List() // Конструктор без параметров
{
Value = 0; // Чтение значения нов. эл-та
Next = NULL; // Нов. эл-т ссыл-ся на NULL
}
~List(); // Деструктор класса
};
//--------------------------------//
// Деструктор класса List //
//--------------------------------//
List::~List()
{
List *CurrEl, // Текущий эл-т списка
*TNext; // Следующий эл-т
CurrEl = this; // Первый эл-т - Объект
while ((CurrEl->Next!= NULL) &&
(CurrEl->Next!= this)){
TNext = CurrEl->Next; // Сохраним адрес след. эл-та
free(CurrEl);
CurrEl = TNext; // След. эл-т сделать текущим
};
free(CurrEl); // Удалить последний эл-т
cout << "Object deleted" << ;
getch();
}
//*****************************************************//
// Функция добавления элемента в конец односвязного списка //
//*****************************************************//
void List::AddElList(char R)
{
List *CurrEl, // Текущий эл-т списка
*NewEl = new List; // Новый эл-т списка
// Выдел-е памяти под нов. эл-т
CurrEl = this; // Текущий эл-т - Объект
List* KeyWord;
KeyWord = R ? this: NULL;
while (CurrEl->Next!= KeyWord){ // Переход в конец списка
CurrEl = CurrEl->Next;
}
cout << "Lead the value of new element of list ";
cin >> NewEl->Value; // Ввод знач-я нового эл-та
NewEl->Next = KeyWord; // Новый эл-т ссылается на NULL
CurrEl->Next = NewEl; // Новый эл-т - в конец списка
}
//----------------------------------------------------------------//
// Функция вывода на экран односвязного списка //
//----------------------------------------------------------------//
void List::OutpList(char R)
{
int Count = 1; // Счетчик эл-тов списка
List *CurrEl; // Текущий эл-т списка
CurrEl = this; // Текущий эл-т - Объект
void* KeyWord;
KeyWord = R ? this: NULL;
while (CurrEl!= KeyWord){
cout << Count << "-th element of list = "; // Вывод эл-та списка
cout << CurrEl->Value << ;
CurrEl = CurrEl->Next;
Count++;
}
}
//-----------------------------------------------------//
// Функция удаления i-го элемента списка //
//-----------------------------------------------------//
void List::DelElList(int i)
{
int Count = 1; // Счетчик эл-тов списка
List *CurrEl, // Текущий эл-т списка
*PrevEl; // Предыдущий эл-т
CurrEl = this; // Текущий эл-т - Объект
while (Count < i){ // Преход к i-му эл-ту
PrevEl = CurrEl; // Сохранение пред. эл-та
CurrEl = CurrEl->Next;
Count++;
}
PrevEl->Next = CurrEl->Next; // Пред. эл-т ссыл-ся на след.
free(CurrEl);
}
//--------------------------------------------------------------//
// Функция добавления элемента в конец списка //
// с заданием элемента из программы //
//--------------------------------------------------------------//
void List::AddElList(float Val, char R)
{
List *CurrEl,
*NewEl = new List;
CurrEl = this; // Текущий эл-т - Объект
List* KeyWord;
KeyWord = R ? this: NULL;
while (CurrEl->Next!= KeyWord){ // Переход в конец списка
CurrEl = CurrEl->Next;
}
CurrEl->Next = NewEl; // Новый эл-т - в конец списка
NewEl->Value = Val; // Ввод знач-я нового эл-та
NewEl->Next = KeyWord; // Новый эл-т ссылается на NULL
}
//----------------------------------------------------------------//
// Функция создания списка (ввод первого эл-та //
// списка, созд. конструктором без параметров) //
//-----------------------------------------------------------------//
void List::CreateList()
{
List *CurrEl;
char ch;
int Ok = 0;
CurrEl = this; // Текущий эл-т - Объект
do
if ((Value == 0)||(Ok == 1)){
cout << "Lead the value of the first "; //Запрос на ввод
// значения
cout << "element of new list "<< ;
cin >> CurrEl->Value;
break;
}
else{
cout << "This List already exists.";
cout << "Do you want to delete it?(Y/N)";
cin >> ch;
if ((ch == N)||(ch == n))
break;
else
if ((ch == Y)||(ch == y))
Ok = 1;
else
cout << "Input Error";
}
while (1);
}
//---------------------------------------------------------------------------
//-------------------------------------//
// Производный класс: //
// двусвязный список //
//-------------------------------------//
class DLList: public List{
List *Prev; // Адрес пред. эл-та списка
public:
DLList(): List(){
Prev = NULL;
}
void AddElList();
void DelElList(int);
void AddElList(float);
};
//------------------------------------------------------------------------------//
// Функция добавления элемента в конец двусвязного списка //
//------------------------------------------------------------------------------//
void DLList::AddElList()
{
DLList *CurrEl, // Текущий эл-т списка
*NewEl = new DLList; // Новый эл-т списка
// Выдел-е памяти под нов. эл-т
CurrEl = this; // Текущий эл-т - Объект
while (CurrEl->Next!= NULL){ // Переход в конец списка
CurrEl = (DLList*) CurrEl->Next;
}
cout << "Lead the value of new element of list ";
cin >> NewEl->Value; // Ввод знач-я нового эл-та
NewEl->Next = NULL; // Новый эл-т ссылается на NULL
CurrEl->Next = NewEl; // Новый эл-т - в конец списка
NewEl->Prev = CurrEl; // Новый эл-т ссыл-ся на пред.
}
//----------------------------------------------------------------------//
// Функция удаления i-го элемента двусвязного списка //
//----------------------------------------------------------------------//
void DLList::DelElList(int i)
{
int Count = 1; // Счетчик эл-тов списка
DLList *CurrEl, // Текущий эл-т списка
*PrevEl; // Предыдущий эл-т
CurrEl = this; // Текущий эл-т - Объект
while (Count < i){ // Преход к i-му эл-ту
PrevEl = CurrEl; // Сохранение пред. эл-та
CurrEl = (DLList*) CurrEl->Next;
Count++;
}
PrevEl->Next = (DLList*) CurrEl->Next; // Пред. эл-т
// ссыл-ся на след.
PrevEl = (DLList*) PrevEl->Next;
PrevEl->Prev = CurrEl->Prev; // След. эл-т ссыл-ся на пред.
free(CurrEl);
}
//------------------------------------------------------------------//
// Функция добавления элемента в конец списка //
// (двусвязного) с заданием элемента из программы //
//------------------------------------------------------------------//
void DLList::AddElList(float Val)
{
DLList *CurrEl,
*NewEl = new DLList;
CurrEl = this; // Текущий эл-т - Объект
while (CurrEl->Next!= NULL){ // Переход в конец списка
CurrEl = (DLList*) CurrEl->Next;
}
CurrEl->Next = NewEl; // Новый эл-т - в конец списка
NewEl->Value = Val; // Ввод знач-я нового эл-та
NewEl->Next = NULL; // Новый эл-т ссылается на NULL
}
//---------------------------------------------------------------------------
//---------------------------------------//
// Производный класс: //
// закольцованный список //
//---------------------------------------//
class RLList: public List{
public:
RLList(){
Value = 0;
Next = this;
}
};
//---------------------------------------------------------------------------
// Главная функция программы тестирует работоспособность
// Класса “Список”
int main(int argc, char **argv)
{
List TestL;
int Number;
char ch = Y; // Вспомогательная перем-я
char Key = , *PKey;
// Приветствие
cout << "Hellow! You have ran the program of";
cout << " processing Lists just now." << ;
cout << "First part:" << ;
cout << "Please, enter you choose:" << ;
PKey = &Key;
// Главное меню
do{
cout << " 1 - New List" << ;
cout << " 2 - Adding Element to List" << ;
cout << " 3 - Deleting Element of List" << ;
cout << " 4 - Output List to screen" << ;
cout << " 5 - Exit" << ;
Key = getch();
switch (Key){
case 1: TestL.CreateList(); break;
case 2: TestL.AddElList(0); break;
case 3: cout << "Enter the number of element";
cout << " you want to delete" << ;
cin >> Number;
TestL.DelElList(Number); break;
case 4: TestL.OutpList(0); break;
case 5: break;
default: cout << "Input Error";
}
fread(PKey,1,1,stdin);
if (Key == 5)
break;
clrscr();
}
while (1);
clrscr();
cout << "Second part:" << ;
List L1("L1"); // Объект - список
do{
if ((ch == Y)||(ch == y))
L1.AddElList(0); // Добавление эл-та
else
cout << "Input error" << ; // Нажата не та клавиша
cout << "Do you want to add one"; // Запрос на ввод след. эл-та
cout << " more element?(Y/N)" << ;
cin >> ch;
if ((ch == N)||(ch == n))
break; // Выход из цикла
}
while (1); // Бесконечный цикл
L1.AddElList(12, 0);
L1.OutpList(0); // Вывод сп-ка на экран
getch();
clrscr();
cout << "Third part:" << ;
List L2;
int i;
L2.CreateList();
for(i = 0; i <= IMAX; i++){
L2.AddElList((float) i+1, 0);
}
L2.OutpList(0); // Вывод сп-ка на экран
getch();
return 0;
}
//---------------------------------------------------------------------------
В приведенном примере определяется базовый класс односвязного списка List в соответствии с концепцией полны класса содержащий все основные функции работы со списками:
void AddElList(char) - добавление элемента,
void OutpList(char) - вывод содержимого мписка на экран,
void DelElList(int) - удаление элемента,
void CreateList() - первоначальное создание списка.
Как следует из теста программы, класс двусвязного списка DLList является производным классом от List. Такая реализация целесообразна вследствие того, что большинство методов односвязного списка полностью по программному коду совпадают с методами двусвязного, хотя обработка двусвязного списка должна быть дополнена рассмотрением обратных ссылок на элементы. Аналогичным образом реализуется и класс закольцованного списка RLList, по тем же соображениям являющийся производным от класса List.
Спецификатор доступа protected позволяет расширить область видимости полей-данных класса List так, чтобы их можно было использовать в классах, производных от класса List - DLList и RLList. Функции-члены класса List описаны с использованием спецификатора protected, что позволяет использовать их имена как при определении производных классов, так и во всех остальных функциях программы. Ссылка на предыдущий элемент списка в описании класса DLList по умолчанию описана как privat, поскольку данный класс не является базовым для других классов.
Для всех классов, описанных в данном примере, используется один и тот же деструктор. Он наследуется производными классами как обычная функция-член, и следовательно будет работать правильно с любыми их объектами, несмотря на различия по числу и размеру полей.
Функция main() в примере предназначена лишь для проверки работоспособности определенных в программе классов и поэтому содержит описание необходимого объекта и меню для его тестирования. При желании число объектов в основной части программы можно пополнить.
- Прядок вызова конструкторов в производных классах
- Производные классы: полиморфная функция
- 29) Конструкторы и деструкторы производных классов.
- R.10 Производные классы
- 3.4.3 Объявление производных классов
- Базовые и производные классы
- 4.1. Производные классы
- Предотвращение переопределения виртуальных членов производными классами
- Объявление производных классов