• Списки



• Стеки



• Очереди



• Деревья

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

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

Если для обработки таких данных не использовать внешнюю память (файлы), то разумно расположить их в динамической памяти. Во-первых, динамическая память позволяет хранить больший объем информации, чем статическая. А во-вторых, в динамической памяти эти числа можно организовать в связанный список, который не требует предварительного указания количества чисел, подобно массиву. Что же такое "связанный список"? Схематически он выглядит так:

Согласно определению, список располагается в динамически распределяемой памяти, в статической памяти хранится лишь указатель на заглавное звено. Структура, в отличие от массива, является действительно динамической: звенья создаются и удаляются по мере необходимости, в процессе выполнения программы.

Для объявления списка сделано исключение: указатель на звено списка объявляется раньше, чем само звено. В общем виде объявление выглядит так.

		struct Zveno
		   {
		     BT Inf;
		     Zveno *Next; 
		   };

Здесь BT — некоторый базовый тип элементов списка.

Если указатель ссылается только на следующее звено списка (как показано на рисунке и в объявленной выше структуре), то такой список называют однонаправленным, если на следующее и предыдущее звенья — двунаправленным списком. Если указатель в последнем звене установлен не в NULL, а ссылается на заглавное звено списка, то такой список называется кольцевым. Кольцевыми могут быть и однонаправленные, и двунаправленные списки.

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

Выделим типовые операции над списками:

• добавление звена в начало списка;
• удаление звена из начала списка;
• добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан);
• удаление звена из произвольного места списка, отличного от начала (например, после звена, указатель на которое задан);
• проверка, пуст ли список;
• очистка списка;
• печать списка.

Реализуем выделенный набор операций в виде библиотеки. Подключив эту библиотеку, можно решить большинство типовых задач на обработку списка. Пусть список объявлен так, как было описано выше. Первые четыре действия сначала реализуем отдельно, снабдив их иллюстрациями.

1. Добавление звена в начало списка

{Процедура добавления звена в начало списка; в x содержится добавляемая информация} Zveno *V_Nachalo(Zveno *First, BT X) { Zveno *Vsp; Vsp = (Zveno *) malloc(sizeof(Zveno)); Vsp->Inf=X; Vsp->Next=First; First=Vsp; return First; }

2. Удаление звена из начала списка

{Процедура удаления звена из начала списка; в x содержится информация из удалённого звена} Zveno *Iz_Nachala(Zveno *First) { Zveno *Vsp; Vsp=First->Next; free(First); return Vsp; }

3. Добавление звена в произвольное место списка, отличное от начала (после звена, указатель на которое задан)

{Процедура добавления звена в список после звена, на которое ссылается указатель Pred; в x содержится информация для добавления} Zveno *V_Spisok(Zveno *Pred, BT X) { Zveno *Vsp; Vsp = (Zveno *) malloc(sizeof(Zveno)); Vsp->Inf=X; Vsp->Next=Pred->Next; Pred->Next=Vsp; return Vsp; }

4. Удаление звена из произвольного места списка, отличного от начала (после звена, указатель на которое задан)

{Процедура удаления звена из списка после звена, на которое ссылается указатель Pred; в x содержится информация из удалённого звена} BT Iz_Spiska(Zveno *Pred) { BT X; Zveno *Vsp; Vsp=Pred->Next; Pred->Next=Pred->Next->Next; X=Vsp->Inf; free(Vsp); return X; }

Приведём полный текст библиотеки "SPIS.H".

#include < iostream.h >
#include < conio.h >
#include < stdlib.h >
#include < time.h >
typedef  long  BT;
struct Zveno{            
BT Inf;            
Zveno *Next; };

Zveno *V_Nachalo(Zveno *First, BT X)
{	Zveno *Vsp;        
Vsp = (Zveno *) malloc(sizeof(Zveno));        
Vsp->Inf=X; 
Vsp->Next=First; 
First=Vsp;	
return First;}

Zveno *Iz_Nachala(Zveno *First)
{	Zveno *Vsp;	
Vsp=First->Next;	
free(First);	
return Vsp;}

Zveno *V_Spisok(Zveno *Pred, BT X)
{	Zveno *Vsp;        
Vsp = (Zveno *) malloc(sizeof(Zveno));        
Vsp->Inf=X;        
Vsp->Next=Pred->Next;        
Pred->Next=Vsp;        
return Vsp;}

BT Iz_Spiska(Zveno *Pred)
{	BT X;	Zveno *Vsp;        
Vsp=Pred->Next;        
Pred->Next=Pred->Next->Next;	
X=Vsp->Inf;	free(Vsp);	
return X;}

void Print(Zveno *First)
{	Zveno *Vsp;	
Vsp=First;	
while (Vsp)           
  {cout << Vsp->Inf << ' '; 
   Vsp=Vsp->Next;}	
cout << "\n";}

int Pust(Zveno *First)
{		return !First;}

Zveno *Ochistka(Zveno *First)
{        
  while (!Pust(First)) 
   First=Iz_Nachala(First);	
   return First;}

Пример. Составить программу, которая на основе заданного списка формирует два других, помещая в первый из них положительные, а во второй — отрицательные элементы исходного списка.

При реализации алгоритма будем использовать подпрограммы разработанного модуля. Это существенно облегчает решение задачи.

 #include "SPIS.H"

void main()
{Zveno *S1, *S2, *S3, *V1, *V2, *V3;
 BT a; int i, n;
 clrscr();
 randomize();
 S1=NULL;
 // создаём первый элемент
 a=-100+random(201);
 S1=V_Nachalo(S1, a);
 n=1+random(20);
 // формируем список произвольной длины и выводим на печать
 V1=S1;
 for (i=2; i<=n; i++)
 {
    a=-100+random(201);
    V1=V_Spisok(V1, a);
 }
 Print(S1);
 V1 = S1;  S2 = NULL; S3 = NULL;
    while (V1)
	{if (V1->Inf > 0)
	      if (!S2)
		 {S2=V_Nachalo(S2, V1->Inf); V2 = S2;}
	      else {V_Spisok(V2, V1->Inf); V2 = V2->Next;};
	 if (V1->Inf < 0)
	     if (!S3)
		{S3=V_Nachalo(S3, V1->Inf); V3 = S3;}
	     else {V_Spisok(V3, V1->Inf); V3 = V3->Next;};
	 V1= V1->Next;}
  cout << "Результирующий список из положительных элементов: \n";
  Print(S2);
  cout << "Результирующий список из отрицательных элементов: \n";
  Print(S3);
  S1=Ochistka(S1); S2=Ochistka(S2); S3=Ochistka(S3);
}