Главна страница

Упражнение 3 - Свързан списък

Свързан списък

Свързаният списък е структура от данни изградена от елементи, всеки от които съдържа някакви данни + информация, къде се намира следващият елемент от списъка.

В list.h е деклариран шаблонен клас List. Съдържанието на файла не е поместено в тази страница, поради големия си размер, но може да бъде свалено от тук: list.h.
Следващата програма, чрез директивата include, включва list.h в себе си и показва как може да се използва класът List.

#include <iostream>
#include <fstream>
#include "list.h"		// кавичките казват на препроцесора най-напред да търси файла list.h
				// в директорията, където е текущият файл
using namespace std;

int main() {

	List<int> l1;				// тук се вика конструкторът по подразбиране
	cout << "is empty: " << l1.isEmpty() << endl;

	cout << "insertFirst 11\n";
	l1.insertFirst(11);
	cout << "list: '";
	l1.print();
	cout << "'\n";

	cout << "insertLast 33\n";
	l1.insertLast(33);
	cout << "list: '" << l1 << "'\n";	// тук се вика операторът за извеждане

	cout << "is empty: " << l1.isEmpty() << "\n\n";

	cout << "l2(l1)\n";
	List<int> l2(l1);			// тук се вика копиращият конструктор

	cout << "l2.insertAt(2, 22)\n";
	l2.insertAt(2, 22);

	cout << "l1[1] = 0\n";
	l1[1] = 0;				// тук се вика операторът за достъп

	cout << "l2: '" << l2 << "'\n";
	cout << "l1: '" << l1 << "'\n\n";

	List<int> l3;
	cout << "l3 = l2\n";
	l3 = l2;				// тук се вика операторът за присвояване

	cout << "l3.removeFirst()\n";
	l3.removeFirst();

	cout << "l3.removeAt(2)\n";
	l3.removeAt(2);

	cout << "l3: '" << l3 << "'\n";
	cout << "l2: '" << l2 << "'\n";
	cout << "l1: '" << l1 << "'\n\n";

	cout << "l2.writeToFile(\"list\");" << endl;
	l2.writeToFile("list");

	cout << "l1.removeAll\n";
	l1.removeAll();
	cout << "l1: '" << l1 << "'\n";
	cout << "l1.isEmpty(): " << l1.isEmpty() << endl;

	cout << "l1.readFile(\"list\")\n\n";
	l1.readFile("list");

	// тук използваме итератора, за да отпечатаме списъка
	Elem<int>* p;
	l1.iteratorReset();
	while(p = l1.getNext()) cout << p->data << ' ';
	cout<< "\n";

	// ако вместо да използваме итератора напишем
	for(int i = 1; i <= 3; i++) cout << l1[i] << ' ';
	cout<< "\n";
	// обхождането на списъка ще става многократно по-бавно,
	// особено при големи списъци, защото при всяко обръщение към оператора []
	// се тръгва от началото на списъка

	ofstream f("a");
	f << l1 << " | " << l2  << " | " << l3;	// тук отново се вика операторът за извеждане
	f.close();				// но потокът е файлов

	return 0;
	// след като свърши областта на видимост, в която са декларирани обектите,
	// се викат деструкторите им и се унищожават
}

 

Вмъкване в началото.

Свързан списък Linked list

 

Вмъкване в края.

Свързан списък Linked list

 

Вмъкване на зададена позиция. Елементите от тази позиция (включително) нататък се преместват към края на списъка.

Свързан списък Linked list

 

Премахване на елемента в началото.

Свързан списък Linked list

 

Премахване на елемента в края.

Свързан списък Linked list

 

Премахване на елемента на зададената позиция.

Свързан списък Linked list

 

Спрямо структурата от данни свързан списък, методите на класа List можем да обособим като:

	конструктори:
		List(const List<T> &aList);

	трансформатори:
		void insertFirst(T aData);
		void insertLast(T aData);
		void insertAt(unsigned aPos, T aData);
		void removeFirst();
		void removeLast();
		void removeAt(unsigned aPos);
		void removeAll();
		void readFile(const char* aFileName);
		T &operator [] (unsigned aPos);
		List<T> &operator = (const List &aList);

	наблюдатели:
		bool isEmpty() const;
		void print() const;
		void writeToFile(const char* aFileName) const;
		friend ostream& operator << (ostream& os, List& aList);

	итератори:
		void iteratorReset();
		Elem<T>* getNext();
	

Мястото на оператора за достъп [] е спорно, защото той пряко не променя полетата на класа, но връща псевдоним, чрез който може да се променят.
Спорно е и мястото на print, writeToFile и операторът << тъй като те не връщат информация за класа, а предизвикват странични ефекти: отпечатване на списъка и записът му във файл.

Когато създаваме класове-шаблони за широка употреба и в тях заделяме памет динамично, е добре да ги снабдяваме с копиращ конструктор и оператор за присвояване '='. В противен случай компилаторът ще предостави автоматично такива, а те ще копират указателите към динамичната памет, вместо да направят нейно копие. Освен, че класовете ще ползват една и съща памет, те ще се опитат да я освободят 2 пъти, при своето унищожаване, което може да доведе до непредвидими последствия (за да наблюдавате това тествайте по-обстойно програмата objects_2.cpp).

За класовете, които имат конструктор по подразбиране, копиращ конструктор, деструктор и оператор за присвояване се казва, че са в канонична форма. Ако такъв клас ще се наследява, деструкторът му трябва да е виртуален.

Променлив брой вложени цикли

Имаме масива „a“ от N целочислени елемента. За всеки от тези елементи в масива „from“ е посочена начална стойност, а в масива „to“ крайна стойност. Искаме да отпечатваме съдържанието на масива „a“ за всички възможни стойности, които могат да приемат елементите му. Примерно:

	from:	3 5 1
	to:	4 7 1
	
	a:
		3 5 1
		3 6 1
		3 7 1
		4 5 1
		4 6 1
		4 7 1

Можем да постигнем това с 3 вложени цикъла:

for(a[0] = from[0]; a[0] <= to[0]; a[0]++)
	for(a[1] = from[1]; a[1] <= to[1]; a[1]++)
		for(a[2] = from[2]; a[2] <= to[2]; a[2]++)
			printArray();

Ако масивът стане с 4 елемента трябва да добавим нов цикъл.
Вместо това може да имитираме вложени цикли, примерно използвайки рекурсия. Това е направено в следната програма:

#include <iostream>
#define N 3

using namespace std;

int counter;
int a[N];
int from[N] = {3, 5, 1};
int to[N] = {4, 7, 1};

void printArray() {
	cout << ++counter << ": ";
	for(int i = 0; i < N; i++)
		cout << a[i] << ' ';
	cout << endl;
}

void f(int k) {
	if(k == N) {
		printArray();
	} else {
		for(a[k] = from[k]; a[k] <= to[k]; a[k]++)
			f(k + 1);
	}
}

int main() {
	counter = 0;

	for(a[0] = from[0]; a[0] <= to[0]; a[0]++)
		for(a[1] = from[1]; a[1] <= to[1]; a[1]++)
			for(a[2] = from[2]; a[2] <= to[2]; a[2]++)
				printArray();

	counter = 0;

	// за да тествате рекурсивния вариант коментирайте циклите по-горе и разкоментирайте долния ред
	// f(0);

	return 0;
}

Следващата схема показва дървото на рекурсията. Възлите в него са извиквания на функцията „f“, а ребрата показват стойности на „a“. Ако гледаме червените числа, тръгвайки от корена и минавайки по някой клон, като стигнем до листо сме получили едно състояние на масива.

Дърво на рекурсията

Нерекурсивен вариант дава Амерал в глава 10 от книгата си „Алгоритми и структури от данни в C++“. Сорс кодът на програмата с име NESTED1.CPP може да свалите от неговия сайт.

Главна страница