Связанные списки в С++

[little_greg]

Всем привет. Объясните, пожалуйста, работу со списками в С++. Никак не могу разобраться со всеми этими указателями, голова уже кругом идет, в учебнике толково не объяснено, а в интернете поискал - только примеры, в которых ничего не понять. Заранее спасибо.

[Тролль]

little_greg:

Да идея списка проста, как мычание. Хотя, как говорят, черта надо искать в мелочах.

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

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

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

Вообще хорошим стилем программирования считается не писать комментарии к программе, а программу к комментариям. То есть сначала описываешь программу на русском языке в виде комментариев, а потом вставляешь в текст их переводы на C++. Но всем хочется побыстрее, поэтому комментировать, а пуще того обосновывать на бумаге свои действия, никто не любит. Я не исключение - в этом посте я написал пример программы создания списка и функций работы с ними, а комментарии, само собой, писала моя лень, поэтому их кот наплакал.

[little_greg]

Не знаю как правильно выразиться, но, объясните как сказать "по-русски" понятным языком, что тут происходит pNDS->pNext = pHead; А то никак не могу понять того, как это работает, как я понимаю эту инструкцию, получается: "присваивание pHead указателю на объект, указывающему на указатель на следующую запись в списке" - бред какой-то(

#include <cstdio>#include <cstdlib>#include <iostream>#include <string.h>using namespace std;class NameDataSet{ public:char szName[128];// указатель на следующую запись в спискеNameDataSet* pNext;};// указатель на первую запись спискаNameDataSet* pHead = 0;// добавление нового члена в списокvoid add(NameDataSet* pNDS){pNDS->pNext = pHead;// заголовок указывает на новую записьpHead = pNDS;}// чтение имениNameDataSet* getData(){// читаем имяchar nameBuffer[128];cout << "\nEnter name:";cin  >> nameBuffer;// усли "exit" - выходif ((stricmp(nameBuffer, "exit") == 0)){	return 0;}// новая запись для заполненияNameDataSet* pNDS = new NameDataSet;// заполнение поля имени и обнуление указателяstrncpy(pNDS->szName, nameBuffer, 128);pNDS->szName[127] = '\0';pNDS->pNext = 0;// возврат адреса созданного объктаreturn pNDS;}int main(int nNumberofArgs, char* pszArgs[]){cout << "Read names of students\n"	 << "Enter 'exit' for first name to exit\n";// создание объекта NameDataSetNameDataSet* pNDS;while (pNDS = getData()){	// добавление в конец списка	add(pNDS);}cout << "Entries:\n";pNDS = pHead;while(pNDS){	// вывод текущей записи	cout << pNDS->szName << "\n";	// получение следующей записи	pNDS = pNDS->pNext;}system("PAUSE");return 0; }

[Тролль]

little_greg:

Начну с того, как все это работает.

Функция getData создает новую запись, заполняет ее поле данных (строку szName) вводом с клавиатуры и возвращает в качестве результата выполнения указатель на эту запись. В функции main при вызове функции getData значение этого указателя присваивается указателю pNDS.

Итак, создана новая запись, ее поле данных заполнено, ее адрес находится в указателе pNDS.

Теперь мы вставляем новую запись в начало списка.

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

Так что нам надо сделать две вещи:

а) поместить в указатель созданной нами записи адрес бывшей первой записи списка - это делает оператор pNDS->pNext=pHead, о котором ты спрашивал (подробнее - pNDS->pNext говорит, что в записи, на которую указывает pNDS, имеется указатель с именем pNext, в который надо поместить значение указателя pHead)

б) подкорректировать указатель на первую запись списка, поместив в него адрес созданной нами новой записи, то есть pHead=pNDS.

Всё! Запись создана, в ее указатель помещен адрес старой первой записи списка, а указатель на первую запись списка переориентирован на новую запись.

Вернусь для пущей ясности к расшифровке оператора pNDS->pNext = pHead; это не "присваивание pHead указателю на объект, указывающему на указатель на следующую запись в списке", а присваивание значения, содержащегося в указателе pHead, указателю с именем pNext, находящемуся в записи, адрес которой содержится в указателе pNDS.

Операция -> берет не указатель по указателю, а указанный вторым операндом компонент объекта, на который ссылается указатель, являющийся первым операндом. C++ вообще очень любит одним обозначением операции обозначать цепочку действий.

[little_greg]

спасибо

[little_greg]

Локальные и глобальные объекты, это также как и локальные и глобальные переменные: локальные объявлены в какой-либо функции, глобальные - вне какой-либо функции. Поправьте если не прав.

[Архимаг]

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

Набрал код односвязного списка из книги Дж. Либерти, тоже не понял как работает программа. Можете объяснить для начала, какие функции возлагают на себя используемые классы: Data, Node, TailNode, InternaNode, HeadNode, LinkedList.

#include <cstdlib>#include <iostream>#include <string>using namespace std;enum {kIsSmaller, kIsLarger, kIsSame};class Data{public:	Data(int val):myValue(val){}	~Data(){}	int Compare(const Data &);	void Show() {cout << myValue << endl;}private:	int myValue;};int Data::Compare(const Data & theOtherData){if(myValue < theOtherData.myValue) return kIsSmaller;if(myValue > theOtherData.myValue) return kIsLarger;else return kIsSame;}class Node;class HeadNode;class TailNode;class InternalNode;class Node{public:	Node() {}	virtual ~Node(){}	virtual Node * Insert(Data * theData)=0;	virtual void Show()=0;};class InternalNode: public Node{  public:	 InternalNode(Data * theDat, Node * next);	 ~InternalNode() { delete myNext; delete myData;}	 virtual Node * Insert(Data * theData);	 virtual void Show() {myData->Show(); myNext->Show();}  private:	 Data * myData;	 Node * myNext;};				InternalNode::InternalNode(Data * theData, Node * next):myData(theData), myNext(next) {}Node * InternalNode::Insert(Data * theData){	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;	}class TailNode: public Node{public:	TailNode(){}   ~TailNode(){}	virtual Node * Insert(Data * theData);	virtual void Show() {}};Node * TailNode::Insert(Data* theData){InternalNode * dataNode = new InternalNode(theData, this);return dataNode;}class HeadNode: public Node{public:	HeadNode();	~HeadNode(){delete myNext;}	virtual Node * Insert(Data * theData);	virtual void Show() {myNext->Show();}private:	Node * myNext;};HeadNode::HeadNode(){ myNext=new TailNode();}Node * HeadNode::Insert(Data * theData){myNext=myNext->Insert(theData);return this;}class LinkedList{public:	LinkedList();	~LinkedList(){delete myHead;}	void Insert(Data * theData);	void ShowAll() {myHead->Show();}private:	HeadNode * myHead;};LinkedList::LinkedList(){myHead = new HeadNode;}void LinkedList::Insert(Data * pData){myHead->Insert(pData);}int main(){Data * pData;int val;LinkedList ll;for(;;){	cout << "What value? (0 to stop): ";	cin >> val;	if(!val)	break;	pData=new Data(val);	ll.Insert(pData);}ll.ShowAll();system("PAUSE");return 0;}

[Lion HC]

Data - класс, для хранения даних. Он содержиться во всех узлах списка. Кроме поля int myValue, для хранения целого числа, етот клас умеет виводить ето число на екран, сравнивать себя с другими обьектами своего класса, не у умеет правильно создаваться и удаляться.

Node - родительський класс для TailNode, InternaNode и HeadNode. Сам он ничего не умеет, но задает список общих методов, которие будут определины в дочерних классах. Ето нужно для того, чтоби обращаться к методам дочерних классов, не проверяя, и не зная наверняка, к какому из дочерних классов ви обращаетесь.

LinkedList - собственно наш список узлов.

InternaNode - внутренние узлы списка. Они могут хранить дание, печатать, добавлять.

HeadNode - начало списка. Может добавлять новый узел и печатать, имеет указатель на следуючий узел, но сам не хранит даних.

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

InternaNode, HeadNode, TailNode - абартья, но не блезницы. Каждий делает одни и те же функции по разному.

[Архимаг]

class Node{public:	Node() {}	virtual ~Node(){}	virtual Node * Insert(Data * theData)=0;	virtual void Show()=0;};

Что ознаяает следующая запись?

virtual Node * Insert(Data * theData)=0;

[Тролль]

Архимаг:

Это абстрактный (чистый виртуальный) метод. В таких вместо тела {...} указывается так называемый чистый описатель =0. Проще говоря, это означает, что мы зарезервировали на будущее заголовок метода, а описан по-настоящему он будет только в потомках этого класса.

[Архимаг]

Архимаг:

Это абстрактный (чистый виртуальный) метод. В таких вместо тела {...} указывается так называемый чистый описатель =0. Проще говоря, это означает, что мы зарезервировали на будущее заголовок метода, а описан по-настоящему он будет только в потомках этого класса.

Т.е. по сути записали портотип ?

[Тролль]

Абстрактные методы - в определенной степени аналог прототипов, но не то же самое. И прототип, и чистый виртуальный (абстрактный) метод нужны, чтобы компилятор смог построить обращение к тому, чего еще нет. Но прототип - это описание обращения к функции этого же класса, абстрактный метод - это описание обращения к виртуальной функции класса-потомка. Обрати внимание на замечание Lion HC: "Ето нужно для того, чтоби обращаться к методам дочерних классов, не проверяя, и не зная наверняка, к какому из дочерних классов ви обращаетесь."

Обращаясь к беллетристике, "армия, флот, авиация и производство оружия были целиком переданы в ведение федерального правительства. Заглядывая далеко вперед, ему передали также атомную энергию, ибо настанет день, когда мы и на Теллусе овладеем этой могучей силой. " (Ф. Карсак, "Робинзоны космоса")

Вот это и есть чистая виртуальная (абстрактная) функция.

Изменено 11 октября, 2009 пользователем Тролль

[Архимаг]

Data - класс, для хранения даних. Он содержиться во всех узлах списка. Кроме поля int myValue, для хранения целого числа, етот клас умеет виводить ето число на екран, сравнивать себя с другими обьектами своего класса, не у умеет правильно создаваться и удаляться.

Node - родительський класс для TailNode, InternaNode и HeadNode. Сам он ничего не умеет, но задает список общих методов, которие будут определины в дочерних классах. Ето нужно для того, чтоби обращаться к методам дочерних классов, не проверяя, и не зная наверняка, к какому из дочерних классов ви обращаетесь.

LinkedList - собственно наш список узлов.

InternaNode - внутренние узлы списка. Они могут хранить дание, печатать, добавлять.

HeadNode - начало списка. Может добавлять новый узел и печатать, имеет указатель на следуючий узел, но сам не хранит даних.

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

InternaNode, HeadNode, TailNode - абартья, но не блезницы. Каждий делает одни и те же функции по разному.

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

Хотел бы по-этапно уточнить.

Ну во-первых, в испольняемом блоке программы создается указатель на тип Data. Объект этого типа представляет из себя как бы единицу

данных списка ? Далее создается объект типа LinkedList, который я является списком... Запускается конструктор класса LinkedLink, который

выделяет память для объекта класса HeadNode (т.е. для головы списка). Но здесь myHead это как бы данные класса LinkedList, которые еще является объектом класса HeadNode ? И так как выделяется память под тип HeadNode, то вызывается конструктор этого класса ?

[Lion HC]

Всё правильно поняли. :)

... а в свою очередь конструктор HeadNode'а визывает консторуктор TailNode(), присваивает указатель.... и на етом завершается создание пустого списка ll

[Архимаг]

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

Смотрел в Либерти, там описывается только односвязный список, да и то не совсем понял...

[Lion HC]

В Павловской есть про всё по немножку. Думаю для понимания достаточно.

Второй учебник из етого поста.

[Архимаг]

Всё правильно поняли. :D

... а в свою очередь конструктор HeadNode'а визывает консторуктор TailNode(), присваивает указатель.... и на етом завершается создание пустого списка ll

Хорошо, эту часть я понял, спасибо за ответы. Очень хочу разобраться в доскональности в работе списков, но видно либо опыта не хватает в ООП, либо

думать плохо умею :)

Скажите пожалуйста, а вот почему некоторые функции, в частности функция Insert, возвращает значение типа Node, если сам класс Node, не содержит в себе как таковых функций и данных ?

[Lion HC]

Функция Insert, возвращает не значение типа Node, а указатель Node *.

Указатели, могут указывать на любой из объектов дочерних классов:

Node *N = new HeadNode;Node *N = new InternaNode;Node *N = new TailNode;

Тоесть, если ви наверняка не знаете, указатель на объект какого из класов (одной иерархии) придется возвращать функции, то единственний правильный виход - возвратить из этой функции указатель на базовый класс.

И если ви напишыте:

N->Insert(x);

будет визываться не Node->Insert,

а HeadNode->Insert, InternaNode->Insert, или TailNode->Insert, в зависимости от того, на объект какого класса в действительности указывает N;

Такова абстракция...

Кстати класс Node - абстрактный! И создавать объекты етого класса нельзя:

Node *N = new Node;	//ошибка

[Архимаг]

разбираю пример односвязного списка из книги Липмана "С++ для начинающих".

список прост, представлен двумя классами: List - класс списка и item_List - класс элементов списка (именования изменены...).

пытаюсь воспроизвести список в собственном представлении :)

class List{public:List(): First(NULL),Last(NULL),_size(0) {}int size() {return _size; }private:item_List *First;item_List *Last;int _size;};

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

Далее, класс элементов

class item_List{  public:   item_List(int value, item_List *item_link_to=0);  private:   int data;   item_List *Next;};

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

Не могу понять как работает конструктор этого класса...

Понятно, что он получает значение, которое необходимо присвоить переменной data и кроме этого, получает какой то адрес, вроде адрес элемента, после которого необходимо вставить новый...

Вот сам конструктор

item_List::item_List(int value, item_List *item){data=value;if(item) Next=0;else { Next=item->Next; item->Next=this; }

Что происходит с данными понятно, а вот что происходит с указателем ?

Что означает Next=item->Next; item->Next=this; ?

Я конечно имею представление, но хотелось бы уточнить :)

[Тролль]

Архимаг:

Что означает Next=item->Next; item->Next=this; ?

В поле Next созданной записи записывается адрес, на который указывала переданная в качестве параметра запись (точнее, передан был ее адрес), а в указатель переданной в качестве параметра записи записывается адрес созданной записи. Таким образом, новая запись вставлена в список после переданной в качестве параметра. Изменено 9 января, 2010 пользователем Тролль

[Архимаг]

Архимаг: В поле Next созданной записи записывается адрес, на который указывала переданная в качестве параметра запись (точнее, передан был ее адрес), а в указатель переданной в качестве параметра записи записывается адрес созданной записи. Таким образом, новая запись вставлена в список после переданной в качестве параметра.

Хм, мне кажется, либо здесь небольшая ошибка ? :)

Разве инструкции в операторе ветвления не должны быть поменяны местами ?

if(item) {Next=item->Next;  item->Next=this;}else Next=NULL;

А если мы передаем нулевой указатель, то что будет указывать на создаваемый элемент ?

[Тролль]

Архимаг:

В книгах мелких опечаток в программах всегда полно. Скорее всего тут должно было быть

if(!item) Next=0;else { Next=item->Next; item->Next=this; }

Или, как ты предлагаешь, поменять местами.

Изменено 9 января, 2010 пользователем Тролль

[Архимаг]

Все тот же пример, но уже с функциями вставки :g:

class item_List{  public:   item_List(int value, item_List *item=0);   void SetNext(item_List *first) {Next=first;}   int value () {return data;} private:   int data;   item_List *Next;};//Конструктор элемента с параметрами...item_List::item_List(int value, item_List *item){data=value;if(!item) Next=0;else { Next=item->Next; item->Next=this; }}//Класс списка...class List{public:List(): First(NULL),Last(NULL),_size(0) {}int size() {return _size; }void insert (item_List *ptr, int value);void insert_front(int value);void insert_end(int value);void printList();void bump_up_size() {++_size;}void bump_down_size() {--_size;}private:item_List *First;item_List *Last;int _size;};//Функция вставки по адресу...void List::insert(item_List *ptr, int value){if(!ptr) insert_front(value);else { bump_up_size(); new item_List(value,ptr); }}//Вставка в начало списка...void List::insert_front(int value){   cout << "write_front" << endl;item_List *ptr=new item_List(value);if(!First) First=Last=ptr;else { ptr->SetNext(First); First=ptr;} bump_up_size();}//Вставка элемента в конец списка...void List::insert_end(int value){if(!Last) Last=First=new item_List(value);else Last=new item_List(value,Last);bump_up_size();}

Далее нужна функция вывода на экран. Автор книги предлагает следующий вариант

void List::print(ostream &os){  os << "\n(" << _size << " ) (   ";item_List *ptr = First;while(ptr) {  os << ptr->value() <<  " ";  ptr = ptr->next(); }os << ")\n";}

Не понял, что здесь os, это поток ? Для чего он нужен, почему нельзя использовать стандартную конструкцию "cout <<"

Не нашел его объявление нигде в программе...

[Тролль]

Архимаг:

Можно было и использовать стандартную конструкцию с cout. Автор, видимо, хотел сделать функцию печати более универсальной, чтобы можно было при обращении к функции задавать, куда надо выводить - на экран или в какой-нибудь файл без переназначения стандартного потока вывода. А ostream - стандартный тип (класс) для вывода (сокращение от "output stream"), он есть в заголовочном файле iostream.

Изменено 10 января, 2010 пользователем Тролль