Шаг 1 - Связанные списки или массив без размера

Программы обычно оперируют с табличной информацией. В большинстве случаев это не просто куча чисел. В таблицах присутствуют важные структурные отношения . Эти отношения видны из вопросов. Кто первый? Кто последний? Кто впереди? Кто сзади?

Для начала введем несколько терминов. Списки состоят из элементов. Каждый элемент состоит из полей.

Расмотрим пример списка карт. У нас будут поля TAG - признак перевернута или нет. SUIT - масть. RANG - ранг. NEXT - следующая карта.

class CField
{
public:
	CField();
	int TAG;
	int SUIT;
	int RANG;
	CField* Next;
};

Адрес структуры (указатель) обычно указывает на первый байт структуры. CFiled* test. test это переменная, в которой будет находиться адрес структуры типа CField.

Конструктор

CField::CField()
{
	Next=NULL;
}

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

1_1.gif (974 b)

Попробуем создать программу для демонстрации связей.

#include "iostream.h"
#include "afx.h"

class CField
{
public:
	CField();
	int TAG;
	int SUIT;
	int RANG;
	CField* Next;
};

CField::CField()
{
	Next=NULL;
}

void main()
{
	CField *top;
	top=new CField();			// Создать первуюь карту
	top->TAG=1;			// Установит свойство
	top->Next=new CField();		// Создать 2 карту
	CField *step1=top->Next;		// Взять 2 карту
	step1->Next=new CField();		// Создать 3 карту
	step1->TAG=0;			// Установить свойтво
	CField *step2=step1->Next;		// Взять 3 карту
	step2->TAG=1;			// Установить свойство

	// _______________ Начало подсчета карт

	CField* temp;			// Указатель на временный обьект
	int count=0;			// Счетчик карт
	temp=top;				// Временный обьект равен первому
	while (temp)			// Пока есть карты
	{	
		count++;			// Подсчитать карту
		cout << temp->TAG << endl;	// вывести ранг на экран
		temp=temp->Next;		// взять следующую
	}
	cout << count << endl;		// вывести количестов карт

	//______________ Конец подсчета карт
}

Идея понятна. В классе есть указатель на другой класс и по указателю мы по ним ходим.

Что здесь хорошего? Первое массив не имеет размера, т.е. размер ограничен памятью компьютера. При программировании под Win 32, ограничения вообще нет. То есть есть конечно, но память линейная и плавно из оперативной переходит на диск в виде вертуальной :-).

Естесвенно что данный пример далек от совершества, но это же не последний шаг.


Следующий Шаг | Оглавление
Автор Каев Артем.