Компоненты связанных списков
Связанный список состоит из блоков. Класс самого блока пока остается абстрактным.
сейчас рассмотрим лишь функциональное назначение блоков в списке.
Список будет иметь три компонента:головной блок, хвостовой блок, и любое количество
внутренних блоков. Фактическим хранилищем данных в списке будут внутренние блоки.
Обратите внимание, данные и список-совершенно разные вещи. Теоретически в списке
можно хранить любой тип данных. Но не из них состоит список, а из блоков,
которые могут быть связаны вместе и содержать любой тип данных.
Основной программе ничего не известно о блоках, она работает со списком
в целом. Список тоже делает не слишком много, он просто предоставляет блоки.
Посмотрите программу которая подробнейшим образом демонстрирует работу
со связанным списком.
// ***********************************************
// FILE: Listing 13.13
//
// PURPOSE: Demonstrate ilinked list
// NOTES:
//
// COPYRIGHT: Copyright (C) 1998 Liberty Associates, Inc.
// All Rights Reserved
//
// Demonstrates an object-oriented approach to
// linked lists. The list delegates to the node.
// The node is an abstract data type. Three types of
// nodes are used, head nodes, tail nodes and internal
// nodes. Only the internal nodes hold data.
//
// The Data class is created to serve as an object to
// hold in the linked list.
//
// ***********************************************
#include <iostream>
using namespace std;
enum
{
kIsSmaller, kIsLarger, kIsSame};
//Класс Data для размещения в связанном списке
//Любой класс в связанном списке должен обладать
//двумя функциями:
//Show() -отображает значение
//Compare()-возвращает относительную позицию
//элемента в списке
-/-/-/-1.
class
Data
{
public:
Data(int val):myValue(val)
{}
~Data()
{}
int Compare(const Data &);
void Show()
{
cout << myValue << endl; }
private:
int myValue;
};
-/-/-/-2.
//Функция Compare() используется , чтобы определить
//относительное положение объекта в списке
int Data::Compare(const Data & theOtherData)
{
if (myValue < theOtherData.myValue)
return kIsSmaller;
if (myValue > theOtherData.myValue)
return kIsLarger;
else
return kIsSame;
}
// forward declarations объявления:
class Node;
class HeadNode;
class TailNode;
class InternalNode;
-/-/-/-3.
// ADT -представление объекта блока в списке
// Каждый производный класс должен переопределить
// функции Insert() и Show()
class
Node
//базовый класс
{
public:
Node()
{}
virtual ~Node()
{}
virtual Node * Insert(Data * theData)=0;
virtual void Show() = 0;
private:
};
-/-/-/-4.
//Этот блок на действительно будет содержать объект
//в данном случае объект имеет тип Data
//более общий случай будет продемонстрирован
//при рассмотрении шаблонов
class
InternalNode:
public Node
{
public:
InternalNode(Data * theData, Node * next);
~InternalNode()
{
delete myNext;
delete myData; }
virtual Node * Insert(Data * theData);
// delegate!
virtual void Show()
{
myData->Show();
myNext->Show(); }
private:
Data * myData; // the data itself
Node * myNext; // points to next node in the linked list
};
-/-/-/-5.
// конструктор лишь инициализирует значения защищенных переменных
InternalNode::InternalNode(Data * theData, Node * next):
myData(theData), myNext(next)
{
}
-/-/-/-6.
//Суть списка:
//при поступлении в список нового объекта
//он передается в блок, который
//и будет добавлен в список
Node * InternalNode::Insert(Data * theData)
{
// is the new guy bigger or smaller than me?
int result = myData->Compare(*theData);
switch(result)
{
// по соглашению если он такой же как я то идет первым
case kIsSame: //придется пропустить новые данные
case kIsLarger: // впереди себя
{
InternalNode * dataNode = new InternalNode(theData, this);
return dataNode;
}
//он больше меня, поэтому пошел он к следующему
//блоку и пусть ОН его обработает
case kIsSmaller:
myNext = myNext->Insert(theData);
return this;
}
return this; // успокоить MSC
}
-/-/-/-7.
//хвостовой блок списка-не больше чем сторож
class
TailNode
: public Node
{
public:
131 TailNode()
{}
~TailNode()
{}
virtual Node * Insert(Data * theData);
virtual void Show()
{
}
private:
};
-/-/-/-8.
//Если данные дошли до меня, то их следует
//поставить впереди меня, поскольку я ХВОСТ
//списка и ничего не должно быть вставлено
//после меня
Node * TailNode::Insert(Data * theData)
{
InternalNode * dataNode = new InternalNode(theData, this);
return dataNode;//возвращен адрес вновь созданного блока InternalNode
}
-/-/-/-9.
//Головной блок не содержит ни каких данных
//он только указывает на начало списка
class
HeadNode
: public Node
{
public:
HeadNode();
~HeadNode()
{
delete myNext; }
virtual Node * Insert(Data * theData);
virtual void Show()
{
myNext->Show(); }
private:
Node * myNext;
};
-/-/-/-10.
//Хвост списка создается точно так же
//как и голова
163 HeadNode::HeadNode()
{
myNext = new TailNode;
}
-/-/-/-11.
//Ничто не может находиться перед головным блоком
//поэтому данные передаются следующему блоку
170:Node * HeadNode::Insert(Data * theData)
{
myNext = myNext->Insert(theData);
return this;
}
-/-/-/-12.
//Я только раздаю данные
//но сам не делаю ничего
class
LinkedList
{
public:
LinkedList();
~LinkedList()
{
delete myHead; }
void Insert(Data * theData);
void ShowAll()
{
myHead->Show(); }
private:
HeadNode * myHead;
};
-/-/-/-13.
//При рождении я создаю головной блок списка
//Он создает хвост списка
//Так что пустой список указывает на голову,
//которая указывает на хвост,
//и между ними ничего нет
LinkedList::LinkedList()
{
myHead = new HeadNode;
}
-/-/-/-14.
// Передать, передать, передать
void LinkedList::Insert(Data * pData)
{
200 myHead->Insert(pData);
}
* * * * * * * * * * *
* * * * * * * * * * *
// test driver program
int main()
{
Data * pData;
int val;
LinkedList ll;
// ask the user to produce some values
// put them in the list
212: for (;;)
{
cout << "What value? (0 to stop): ";
cin >> val;
if (!val)
break;
pData = new Data(val);
ll.Insert(pData);
}
// now walk the list and show the data
ll.ShowAll();
return 0; // ll falls out of scope and is destroyed!
}
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Результат:
What value? (0 to stop): 9
What value? (0 to stop): 3
What value? (0 to stop): 5
What value? (0 to stop): 4
What value? (0 to stop): 7
What value? (0 to stop): 13
What value? (0 to stop): 0
3
4
5
7
9
13
Анализ:
-.-.-.- 1.
В первую очередь следует обратить внимание на перечисление enum,
которое содержит три постоянных значения.
enum
{
Каждый сохраняемый в списке объект должен иметь метод Compare() ,
возвращающий значение именно этого типа.
-.-.-.- 2.
Исключительно для иллюстрации работы со списком в строках 30-39
был создан класс Data,
int Compare(const Data &);
private:
int myValue;
class Data
{
Data(int val):myValue(val)
{}
~Data()
{}
void Show()
{
метод Compare() которого реализован в строках 41-51.
//Метод Compare() используется , чтобы определить относительное
//положение объекта в списке
int Data::Compare(const Data & theOtherData)
{
return kIsSmaller;
if (myValue > theOtherData.myValue)
return kIsLarger;
else
return kIsSame;
Объект Data содержит значение int myValue , которое можно сравнить с
аналогичным значением другого объекта Data при помощи
функции-члена Compare().
Объект Data так же содержит функцию Show(), которая отображает значение
объекта на экране.
void Show()
{
Объект Data инициализируется при помощи конструктора
Data(int val):myValue(val)
{}
-.-.-.-3.
Кроме этого в программе есть следующие классы:
class Node;
// forward declarations объявления:
class HeadNode;
class TailNode;
class InternalNode;
Класс Node является базовым для остальных трех классов
// Каждый производный класс должен переопределить
// функции Insert() и Show()
class Node //базовый класс
{
Node()
{}
virtual ~Node()
{}
virtual Node * Insert(Data * theData)=0;
virtual void Show() = 0;
private:
Как видим функция Insert()
virtual Node * Insert(Data * theData)=0;
возвращает указатель на тип Node и в качестве аргумента ей тоже
передается указатель на тип Data.(То есть другими словами ей
передается в качестве аргумента адрес на объект класса Data,
а возвращает она адрес на объект класса Node.)
-.-.-.-4.
Кроме того в программе создан класс LinkedList(связный список) строка 177
//Я только раздаю данные
//но сам не делаю ничего
class LinkedList
{
LinkedList();
~LinkedList()
{
void Insert(Data * theData);
void ShowAll()
{
private:
185 HeadNode * myHead;
Как видим здесь есть закрытый член -указатель на тип HeadNode (головной блок списка)
private:
185 HeadNode * myHead;//указатель на тип HeadNode.
//объект HeadNode здесь еще не создан.
-.-.-.-.- 4.
Простейший способ понять работу связного списка-использовать его на практике.
Посмотрим главную программу main() :
в строке 206 объявлен указатель на объект класса Data.
206: Data * pData;
Далее В строке 208 -создан объект класса LinkedList
локальный связанный список ll(LinkedList-связанный список).
208: LinkedList ll;//создан объект ll класса LinkedList-
//- локальный связанный список
При создании объекта связанного списка, вызывается его конструктор.
(реализован в строке 192)
Единственной задачей конструктора является создание объекта HeadNode
(головной блок) и присвоение адреса этого объекта указателю на головной блок.
Этот указатель был объявлен в классе LinkedList (строка 185)
а следовательно это будет одновременно и указатель на связанный список,
private:
Итак конструктор для LinkedList ll:
//При рождении я создаю блок заголовка списка
192 LinkedList::LinkedList() //конструктор создает голову списка
class LinkedList
{
185 HeadNode * myHead; //объявлен указатель на тип HeadNode (головной блок)
//Он создает блок хвоста списка
//Так что пустой список указывает на голову,
//которая указывает на хвост,
//и между ними ничего нет
{
Получается что конструктор привязывает ранее объявленный указатель
к головному блоку, то есть теперь указатель указывает на головной блок,
который создан в динамической памяти последовательностью
таких инструкций:
private:
185 HeadNode * myHead; //указатель на тип это в объявлении класса LinkedList
myHead = new HeadNode; //переопределение указателя на головной блок,
// созданный в динамической памяти .
// эта инструкция в конструкторе
Итак головной блок -объект HeadNode класса HeadNode создан в динамической памяти
и указатель myHead указывает на него!
-.-.-.- 5.
Итак при создании объекта класса LinkedList вызывается его
конструктор, который создает объект HeadNode, при создании этого
объекта (HeadNode) вызывается его собственный конструктор
который создает объект TailNode -хвостовой блок
Итак в программе как мы знаем объявлен класс HeadNode:
//Головной блок не содержит ни каких данных
//он только указывает на начало списка
class HeadNode : public Node
{
HeadNode();
~HeadNode()
{
virtual Node * Insert(Data * theData);
virtual void Show()
{
private:
Node * myNext;
Как видим в классе HeadNode объявлен указатель на тип Node
private:
Node * myNext;//указатель на тип Node
Создание объекта HeadNode класса HeadNode вызывает одноименный
конструктор HeadNode(), показанный в строках 163-166,
который в свою очередь создает объект TailNode(хвостовой блок)
класса NailNode и присваивает его адрес указателю MyNext(мой следующий)
Этот указатель был объявлен в классе HeadNode .
Итак конструктор для объекта HeadNode:
//Хвост списка создается точно так же
//как и голова
163 HeadNode::HeadNode() //конструктор создает хвост списка
{
Получается что конструктор HeadNode создает хвостовой блок (TailNode) и
помещает его в динамическую память
последовательностью таких инструкций:
private:
Node * myNext; //указатель на тип Node это в объявлении класса HeadNode
myNext = new TailNode;// переопределение указателя на объект
// TailNode (хвостовой блок) созданный в динамической
// памяти. Это в конструкторе HeadNode
Итак хвостовой блок-объект TailNode класса TailNode создан!
-.-.-.-.-6.
Создание хвостового блока-объекта TailNode класса TailNode вызывает одноименный
конструктор TailNode(), показанный в строке 131.
Он является стандартным и ничего не делает.
class TailNode : public Node
{
131 TailNode()
{
}//конструктор который ничего не делает!
. . .
Вот так легко и просто создается связанный список.
Сначала в стеке создается сам список,
208: LinkedList ll;//создан объект ll класса LinkedList-
//- локальный связанный список
Внутри этого списка объявлен указатель на тип HeadNode (головной блок)
Затем когда автоматически вызывается конструктор этого объекта,
этот конструктор создает головной блок и переопределяет на него
этот указатель.Таким образом указатель теперь указывает и на
созданный головной блок и следовательно одновременно на сам
связанный список.
Внутри головного блока объявлен указатель на тип TailNode(хвостовой блок).
При создании головного блока автоматически вызывается его конструктор
который создает хвостовой блок и переопределяет этот указатель
на вновь созданный хвостовой блок.
Как мы видим создан список который указывает на созданный головной блок,
который указывает на созданный хвостовой блок, который никуда не указывает.
Его конструктор ничего не делает -он пустой, а указателя на что-либо
хвостовой блок не имеет .
Головной и хвостовой блоки созданы в динамической памяти.
Все это делается автоматически при объявлении нами объекта класса LinkedList.
* * * * * * * * * * * * * *
* * * * * * * * * * * * * *
В строке 212 начинается бесконечный цикл.
212: for (;;)
{
cin >> val;
if (!val)
break;
218: pData = new Data(val);//создан объект класса Data
ll.Insert(pData);//функция Insert() вставляет объект Data в
Пользователю предлагается ввести значение, которое будет добавлено
в связанный список. Пользователь может ввести очень много значений,
пока не будет введено число 0.
Опять мы видим создание объектов в динамической памяти:
Data * pData; //объявлен указатель на тип Data (в начале главной програмы)
pData = new Data(val);//создан объкт класса Data в динамич.памяти
С каждой итерацией в динамической памяти будет создан новый объект
Data на который указывает указатель pData.
Итак если введенное значение отличается от 0, то в строке 218
создается новый объект класса Data
218: pData = new Data(val);
а в строке 219 он вводится в связанный список
при помощи вызова функции-члена класса LinkedList - Insert()
219: ll.Insert(pData);//вызов функции Insert() объектом ll
* * * * * * * * * * * * * *
Предположим пользователь ввел число 15,
Это число будет присвоено переменной val и будет вставлено в качестве аргумента
для инициализации вновь созданного объекта типа Data в динамической памяти,
на этот объект будет указывать указатель pData, далее объект ll класса LinkedList
вызовет функцию-член класса LinkedList- Insert()
219: ll.Insert(pData);//вызов функции Insert() объектом ll
она определена в строке 198
198: void LinkedList::Insert(Data * pData)
// Передать, передать, передать
{
В качестве аргумента в этой функции используется указатель на только
что созданный объект класса Data.
Как видим Функция Insert(), которая является функцией-членом класса
LinkedList, вызывает посредством указателя myHead другую функцию Insert()
которая является функцией-членом класса HeadNode.
Напомним что указатель myHead указывает на объект HeadNode. Мы видим что
и в этой функции в качесве аргумента использован указатель на вновь
созданный объект класса Data.
связанный список немедленно передает ответственность за вставку
объекта своему головному блоку, который вызывает
свою функцию -член Insert() она определена в строке 170:
//Ничто не может находиться перед головным блоком
//поэтому данные передаются следующему блоку
Node * HeadNode::Insert(Data * theData)
{
return this;
Эта функция-член класса HeadNode - Insert() как видим
при помощи указателя myNext, а указатель myNext в настоящий момент
указывает на объект TailNode (хвостовой блок),
следовательно будет вызвана функция-член именно объекта этого класса.
Итак вызывается функция Insert(), которая является функцией_членом
класса TailNode .
И в этой третьей вызванной функции Insert() аргументом является
указатель на вновь созданный объект класса Data.
Эта функция определена в строке 142
142: Node * TailNode::Insert(Data * theData)
//Если данные дошли до меня, то их следует
//поставить впереди меня, поскольку я ХВОСТ
//списка и ничего не должно быть вставлено
//после меня
{
return dataNode;
Эта вызванная функция знает что переданный ей объект следует поставить
непосредственно перед объектом TailNode (хвостовым блоком).
(Как она знает это?)
Она знает это потому что, внутри функции TailNode::Insert() создается новый
блок класса InternalNode и следовательно будет вызван конструктор этого
класса. И именно конструктор инициализирует вновь созданный объект так,
что поместит введенное пользователем значение внутрь в переменную и указатель,
который также присутствует в объектах этого класса, переадресует
на хвостовой блок списка, то есть фактически постави вновь созданный
объект как раз впереди хвостового блока. Что и должна была сделать
эта функция.
И мы видим как функция в строке 144 создает новый объект класса
InternalNode (внутренний блок) , передает ему данные и указатель на себя.
(адрес объекта TailNode)
Это приведет к вызову конструктора объекта InternalNode,
этот конструктор определен в строке 90
90: InternalNode::InternalNode(Data * theData, Node * next):
// конструктор лишь инициализирует значения myData и myNext
myData(theData), myNext(next)
{
Как видим конструктор InternalNode просто инициализирует свой
указатель класса Data адресом объекта Data, переданного ему,
а свой указатель myNext - адресом того блока, который передал
ему этот объект. В данном случае это будет хвостовой объект списка
(помните, именно хвостовой блок списка передал его в указателе
this).
Таким образом если теперь указатель myNext этого вновь созданного
блока указывает на хвостовой блок, то тем самым значит что вновь
созданный блок стоит перед хвостовым блоком связного списка.
Теперь когда новый внутренний блок InternalNode создан, и его адрес
присвоен указателю dataNode в строке 144,
142: Node * TailNode::Insert(Data * theData)
{
return dataNode;//возвращен адрес вновь созданного блока InternalNode
сам этот адрес возвращается при помощи функции TailNode::Insert() стр 142,
и инструкции
return dataNode;
--/-/-/-/-/-/-/-/-/-/-
Вернемся к функции HeadNode::Insert(), когда адрес InternalNode
присваивается указателю myNext объекта HeadNode. (в строке 172)
//Ничто не может находиться перед головным блоком
//поэтому данные передаются следующему блоку
Node * HeadNode::Insert(Data * theData)
{
return this;
Теперь, поскольку указателю myNext в головном блоке присвоен
адрес вновь созданного блока, то головной блок будет указывать уже не
на хвост списка, а на вновь созданный блок InternalNode.
-/-/-/-/-/-/-/-/-/-/-
В заключение адрес HeadNode возвращается связанному списку
в строке 200, дальнейшая передача прекращается , поскольку
связанный список уже "знает" адрес головного блока.
// Передать, передать, передать
198: void LinkedList::Insert(Data * pData)
{
Теперь по прежнему указатель myHead объекта ll класса LinkedList
указывает на головной блок. Поскольку функция HeadNode::Insert() вернула
адрес головного блока.
-/-/-/-/-/-/-/-
Зачем же возвращать адрес, если он не используется?
Функция Insert() объявлена в базовом классе Node ,
и возвращение его значения (адреса) необходимо
в других производных классах. Поэтому если не принять значение
возвращаемое функцией HeadNode::Insert() , то произойдет ошибка
компиляции. Во избежании этого необходимо позволить связанному
списку принять значение, возвращаемое объектом HeadNode,
и просто не использовать его.
-/-/-/-/-/-/-/-/-
Итак что же произошло? Данные были вставлены в список.
Список передал их головному блоку. Головной блок вслепую передал
их по адресу в своем указателе, а в первом случае он указывал
на хвост списка. Хвост списка немедленно создал новый внутренний
блок, инициализировав его так, чтобы он указывал на хвост списка,
тем самым поставив новый блок перед собой.
Затем хвостовой блок списка возвратил адрес нового блока голове,
тем самым указатель myNext головного блока стал указывать
на новый блок.
Все! Конец! Данные находятся в списке в нужном месте!
* * * * * * * * * * * * * * *
* * * * * * * * * * * * * * *
После вставки первого блока. управление программой возвращается
к стр 214. И пользователя снова запрашивают о новом значении.
212: for (;;)
{
cin >> val;
if (!val)
break;
218: pData = new Data(val);
219 ll.Insert(pData);
Предположим что введено значение 3. Это приведет к созданию,
и включению в список нового объекта класса Data (стр 218, 219).
И вновь в стр 200 список передает данные своему головному блоку
HeadNode.
// Передать, передать, передать
void LinkedList::Insert(Data * pData)
{
Метод HeadNode::Insert() в свою очередь передает новое
значение по адресу в указателе myNext,
//Ничто не может находиться перед головным блоком
//поэтому данные передаются следующему блоку
Node * HeadNode::Insert(Data * theData)
{
return this;
который указывает теперь на блок, содержащий объект Data,
значением которого является 15.
Это приводит к вызову метода InternalNode::Insert() в стр 99.
99 Node * InternalNode::Insert(Data * theData)
// новичок больше или меньше меня?
switch(result)
// по соглашению если он такой же как я то идет первым
//Суть списка:
//при поступлении в список нового объекта
//он передается в блок, который
//и будет добавлен в список
{
103 int result = myData->Compare(*theData);
{
case kIsSame: //придется пропустить новые данные
case kIsLarger: // впереди себя
{
return dataNode;
//он больше меня, поэтому пошел он к следующему
//блоку и пусть ОН его обработает
case kIsSmaller:
myNext = myNext->Insert(theData);
return this;
return this; // успокоить MSC
В стр 103 InternalNode использует свой указатель myData
для обращения к методу Compare() своего объекта класса Data
(значением которого является 15). Это позволяет сравнить его
с вновь переданным объектом класса Data (значением которого
является 3). Это приводит к вызову метода Compare(),
представленному в стр 43.
//Функция Compare() используется , чтобы определить
//относительное положение объекта в списке
int Data::Compare(const Data & theOtherData)
{
return kIsSmaller;
if (myValue > theOtherData.myValue)
return kIsLarger;
else
return kIsSame;
Сравниваются два значения, и поскольку myValue равно 15, а
theotherData.myValue -3, возвращается значение kIsLarger (если
больше). Это приведет к переходу процесса выполнения программы
к стр 112.
Для нового объекта Data создается новый блок InternalNode.
case kIsLarger: // впереди себя
{
return dataNode;
Новый блок указывает на текущий блок InternalNode, а новый
адрес InternalNode , возвращенный методом InternalNode::Insert(),
передается HeadNode. Теперь головной блок указывает на только что
вновь образованный блок.
Таким образом новый блок, значение объекта которого меньше значения
объекта текущего блока, вставляется в список перед текущим блоком
и список теперь выглядит так.(страница 411).
Головной -> Новый -> Текущий -> Хвостовой
блок блок блок блок
-/-/-/-/-/-/-/-/-/-/-/-/-/-/-
В третий раз пользователь добавляет значение 8. Оно больше 3, но
меньше 15, поэтому должно быть вставлено между двумя существующими
блоками. Процесс протекает аналогично предыдущему, за исключением
того, что при сравнении с объектом, содержащим значение 3, вместо
kIsLarger будет возвращено kIsSmaller (означающее, что объект
содержащий значение 3, меньше чем новый объект содержащий значение
8).
Это приведет к вызову метода InternalNode::Insert в стр119.
Вместо создания и вставки нового блока, InternalNode лишь передаст
новые данные в метод Insert объекта, адрес которого содержит
указатель myNext . В данном случае будет вызван метод InsertNode
того блока InternalNode, значение объекта Data которого равно 15.
И вновь выполняется сравнение, в результате которого создается
новый блок InternalNode. Указатель нового InternalNode содержит
адрес того блока InternalNode, значением объекта Data которого
является 15 и адрес которого будет передан обратно тому блоку
InternalNode, значение объекта Data которого является 3 (стр 119).
Главным результатом всех этих действий является то, что новый
блок вставлен в список в соответствующем месте.
Можно код этой прогграммы запустить в отладчике и с его помощью
понаблюдать как все эти методы вызывают друг друга.
Вверх
Процедурное программирование, которое было широко распространено
Вверх
Использование собственного класса массива вместо стандартного встроенного
-коллекция(Collection) -элементы упорядочены и отсортированы в определенном
-набор(set)-ни один из элементов не повторяется.
-словарь(dictionary)-набор соответствующих друг-другу пар элементов,
-разреженный массив(sparse array) -разрешены индексы любой величины,
-мешок(bag) -неупорядоченный набор элементов, добавлять и обращаться
Перегрузкой оператора индексирования [] , можно предбразовать связный
Вверх
Массив это набор строго фиксированных однотипных элементов.
Имя массива представляет собой постоянный указатель на первый его
Назад |
Начало урока |
Вверх |
Вперед
Чему вы научились?
до изобретения классов, отошло далеко на второй план. В процедурном
программировании основным методом было бы -исследование данных и вызов
соответствующих функций.
ООП подразумевает что каждый объект имеет четкие и узко-специализированные
обязанности.
Связанный список осуществляет поддержку головного блока. Головной блок
передает новые данные по адресу, содержащемуся в его указателе, не придавая
значения тому, куда именно он указывает.
Хвостовой блок создает и добавляет новый внутренний блок всякий раз, когда
получает данные. Он умеет делать только одно-если пришли данные , то их
следует поставить в список перед собой.
Внутренние блоки немного сложней:они требуют, чтобы их объект сравнил себя
с новым объектом. В зависимости от результата, новый объкт будет либо добавлен
перед существующим, либо передан следующему блоку.
Обратите вниманеи, что внутренние блоки в сравнении не участвуют, оно
выполняется самим объектом. Все, что должен уметь внутренний блок-потребовать
у объектов сравнения и ожидать один из трех возможных результатов.
Получив положительный ответ он вставляет блок в список перед собой,
в противном случае посылает его по адресу.
Итак кто же несет ответственность? В хорошо разработанной ООП программе-
никто! Каждый объект хорошо делает свое маленькое дело, а в результате
получается хорошая программа.
Классы массивов
массива дает множество преимуществ.
Во первых можно предотвратить возможность записи данных за пределы массива.
Во вторых можно создать такой класс массива, размер которого изменяется
динамически:при создании он будет размером в один элемент, а по мере
добавления новых, приобретает необходимый размер.
Элементы массива можно автоматически сортировать или выстраивать в необходимом
порядке. Кроме того такой подход позволяет создать целый ряд специальных
типов массивов. Наиболее популярными из них являются:
порядке.
в котором значение одного из них можно получить по значению другого.
но память занимают только те значения, содержащиеся в массиве,
к которым можно в произвольном порядке.
список в коллкцию. Исключив дублирование элементов, можно преобразовать
связный список в набор. Если каждый объект списка имеет пару значений,
то его можно использовать при создании словаря или разреженного массива.
Резюме.
Массивы не проверяют свой размер, поэтому вполне возможна ситуация,
когда элемент записывается за пределы области памяти, выделенной для
массива. Обычно это приводит к катастрофе. Массивы начинаются с 0.
Обычной ошибкой является попытка записи элемента номер n в массив
из n элементов.
Массивы могут быть одно или много мерными. В любом случае элементы
массива могут быть инициализированы при создании, не смотря на то,
содержит ли он встроенные типы(такие как int) или объекты класса,
располагающего стандартным конструктором.
Массивы и их содержание могут быть размещены как в динамической памяти,
так и в стеке. При удалении массивов, размещенных в динамической памяти,
не забывайте использовать квадратные скобки в операторе delete[].
элемент. Указатели и массивы используют арифметические операции над
указателями для поиска необходимого элемента массива.
Для тех наборов , размер который изначально не известен, можно создать
связанные списки. Из связанных списков можно создать множество
более сложных структур данных.
Строки-это разновидность массива символов. Язык С++ обладает специальными
средствами для работы с символьными масивами, включая возможность
инициализировать их с помощью строки заключенной в парные кавычки.
Содержание
