Реализация - односвязный список.
#include <iostream>using namespace std; struct Element{ // Данные char data; // Адрес следующего элемента списка Element * Next;}; // Односвязный списокclass List{ // Адрес головного элемента списка Element * Head; // Адрес головного элемента списка Element * Tail; // Количество элементов списка int Count; public: // Конструктор List(); // Деструктор ~List(); // Добавление элемента в список // (Новый элемент становится последним) void Add(char data); // Удаление элемента списка // (Удаляется головной элемент) void Del(); // Удаление всего списка void DelAll(); // Распечатка содержимого списка // (Распечатка начинается с головного элемента) void Print(); // Получение количества элементов, находящихся в списке int GetCount();}; List::List(){ // Изначально список пуст Head = Tail = NULL; Count = 0;} List::~List(){ // Вызов функции удаления DelAll();} int List::GetCount(){ // Возвращаем количество элементов return Count;} void List::Add(char data){ // создание нового элемента Element * temp = new Element; // заполнение данными temp->data = data; // следующий элемент отсутствует temp->Next = NULL; // новый элемент становится последним элементом списка // если он не первый добавленный if(Head!=NULL){ Tail->Next=temp; Tail = temp; } // новый элемент становится единственным // если он первый добавленный else{ Head=Tail=temp; }} void List::Del(){ // запоминаем адрес головного элемента Element * temp = Head; // перебрасываем голову на следующий элемент Head = Head->Next; // удаляем бывший головной элемент delete temp;} void List::DelAll(){ // Пока еще есть элементы while(Head != 0) // Удаляем элементы по одному Del();} void List::Print(){ // запоминаем адрес головного элемента Element * temp = Head; // Пока еще есть элементы while(temp != 0) { // Выводим данные cout << temp->data << " "; // Переходим на следующий элемент temp = temp->Next; } cout << "\n\n";} // Тестовый примерvoid main(){ // Создаем объект класса List List lst; // Тестовая строка char s[] = "Hello, World !!!\n"; // Выводим строку cout << s << "\n\n"; // Определяем длину строки int len = strlen(s); // Загоняем строку в список for(int i = 0; i < len; i++) lst.Add(s[i]); // Распечатываем содержимое списка lst.Print(); // Удаляем три элемента списка lst.Del(); lst.Del(); lst.Del(); //Распечатываем содержимое списка lst.Print();} |
Предыдущая
| Оглавление
| Следующая
|
Предыдущая
| Оглавление
| Следующая
|
Двусвязный список.
Вы уже знаете, что есть односвязный список и, поэтому вам будет просто понять принцип работы двусвязного списка. Отличие данной структуры от предыдущей состоит в том, что в двусвязном (или двунаправленном списке) узел состоит не из двух, а из трех частей. В третьем компоненте хранится указатель на предыдущий элемент.
//узел (звено) списка struct node { //Информационный элемент звена списка int value; // Указатель на предыдущее звено списка node *prev; // Указатель на следующее звено списка node *next; }; |
Такое построение позволяет производить движение по списку, как в прямом, так и в обратном направлении.
Рассмотрим на иллюстрациях основные действия над двусвязным списком.
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.