Связанные структуры

Связанные структуры

Если программа должна работать с фиксированным числом экземпляров одного типа структуры, то объявляется массив структур.

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

Рассмотрим линейные связанные структуры.

Все элементы связанных структур представляют собой 

  последовательность элементов, связанных в цепь посредством

  указателей.

2) ОП для элементов выделяется и освобождается динамическая

  (new – delete или  malloc – free )

последовательность элементов имеет вершину и хвост.

К линейным связанным структурам относятся стеки, очереди, списки, и т. д., включение и исключение элементов в которых происходит по-разному:

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

Стек

новый элемент  вершина стека  хвост стека

  … 

  0

  s-указатель на вершину до включения

  stnew ->next= s 

  s = stnew  - указатель на вершину после включения

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

Стек – это организация данных,  в которой элемент поступивший в стек последним извлекается первым.

Рассмотрим функции

включения нового элемента исключения элемента считывание данных вершины стека

//Функция дополнения стека:

#include <iostream. h>

#include <conio. h>

struct stack { int data ; stack * next ; }

stack * beg;  // указатель на вершину стека – глобальный

//-------------------------------------------------------------------------------

//Функция дополнения стека:

void dop ( stack*&s, int dat )  // cссылка на указатель для передачи

  //  адреса  вершины стека и 

  // данные для нового элемента

/*адрес вершины стека будет  меняться в функции дополнения, поэтому указатель на вершину-глобальная переменная будет передаваться в функцию по ссылке, в нее и будут записываться все изменения адреса вершины*/

{ stack * stnew;  // указатель на новый элемент стека

  stnew = new ( stack) ;  // выделение памяти под новый элемент

  stnew -> data = dat;  // размещение информации в новый элемент

  stnew->next=s;        //“указывает” на бывшую вершину стека 

  s = stnew;  // указатель на вершину –это указатель на новый элемент

  }  //новый элемент стал вершиной стека.

//---------------------------------------------------------------------------------

//Функция дополнения стека с клавиатуры:

void dop1 ( stack*&s ) 

{ stack * stnew; 

  stnew = new ( stack) ;

  cout<<”\n Введите данные  data = “;

  cin>>stnew -> data; 

  stnew->next=s;        

  s = stnew  ; 

  } 

//-----------------------------------------------------------------------------

//Функция удаления элемента. Возвращает данное удаляемого эл. :

int  ud  ( stack *&s  )  //ссылка указатель  на вершину

{  stack * fr = s  // удаляемый элемент – является вершиной стека

  //  указатель на него – это указатель на вершину

  int k =0;

  if (s)  { k= fr ->data ;  //информацию помещаем в переменную k

  s = fr -> next;  // указателю на вершину присваеваем адрес

  // следующего элемента

  delete fr; }  // освобождаем память

  return k;  // функция возвращает информацию

}

//-----------------------------------------------------------------------------------

//Функция чтения из вершины стека.

//Т. к. значение указателя  на вершину стека  не изменяется в функции //чтения, формальным параметром может быть сам указатель на //вершину

int cht ( stack *s )

{ if (s)  return (s -> data ); }

//-----------------------------------------------------------------

//Рекурсивная функция выводит все содержимое стека

int cht1 ( stack *s )

{ if (s = = NULL)

  {cout<<”\nСтек опустел”; return;}

  cout<<”\n data = “ <<s->data;

  cht1(s->next);

} 

//---------------------------------------------------------------------------

void main ( )

{clrscr();

stack*beg1;

for ( int i=1 ; i < =10 ; i++)

dop ( beg, i );

beg1=beg;

for ( int i=0 ; i < 10 ; i++)

{cout<<cht(beg1); beg1=beg1->next;}

//cht1(beg);

cout<<’\n’<<ud(beg);

cht1(beg);

}

Очередь

Очередь – это связанная структура данных, в которой добавлять элементы можно только в конец (хвост) очереди, а удалять и читать можно только элементы с начала (вершины) очереди.

  первый элемент  последний 

  очереди  элемент 

  …  0

  s начало  конец 

  новый

  элемент

//------------------------------------------------------------------------------------------------

// Функция добавления элемента в конец очереди

#include <iostream. h> 

struct qu {  int data ;  qu* next ; };

void dop ( qu *& s,  int dat) // ссылка на указатель на начало

  //  очереди

  { qu * p = s,  //тек. указатель устанавливаем на начало очереди

  *q = 0,  // всп. yказатель на NULL

  *nst=  new ( qu) ; // выделили память для нового элемента

  nst -> data = dat ; 

  nst->next=NULL; // это последний элемент очереди

  while ( p)  // пока указатель не достигнет нулевого значения

{ q=p ;  p= p ->next ; };  //продвигаемся по очереди к концу

if (q)  q -> next= nst ;  // последний ненулевой элемент должен 

  //  указывать на новый элемент 

  else s = nst;  // новый элемент первый в очереди

}

//------------------------------------------------------------------------------

// Функция удаления элемента из очереди, возвращает удаляемую //информацию. Удаление производится из вершины очереди

int ud ( qu*& s)

{  int k=0;

  qu* fr = s  //  указатель на начало очереди

  if(s)

{ k = s -> data ; s = s -> next ; delete fr;}

  return k; }

//----------------------------------------------------------------------------------

// Функция чтения элемента из начала очереди

  int cht ( qu*s )

  { if(s) return s ->data ; }

//-------------------------------------------------------------------------

// Функция чтения элементов очереди рекурсивная

int cht1 ( qu*s )

  { if(s==NULL) {cout<<”\nэлементов нет”; return;}

  cout<<”\n data = “<< s->data;

  cht1(s->next);

  }

////-------------------------------------------------------------------------

// Функция чтения элементов очереди итерационная

int cht2 ( qu*s )

  {qu* list=s;

if(list==NULL) cout<<”\nэлементов нет”;

else while(list)

  {cout<<”\n data = “<< list->data;

  list=list->next;}

  }

qu * s1;  // объявлен указатель на очередь глобальный

//------------------------------------------------------------------------------

void main ( )

{

  for (int i=1 ; i<=20 ; i++)

  dop ( s1 , i );

  cout << cth (s1 ); 

  cout << ud(s1);

cout << cth (s1 ); 

cht1(s1);  // cht2(s1); }

Список

Список – это соединение элементов в порядке убывания или возрастания ключевого признака –одного из элементов структур.

Рассмотрим следующие функции:

добавление элемента в список; удаление элемента с заданным значением поискового признака; поиск и вывод заданного элемента; чтение и вывод всех элементов; уничтожение списка путем освобождения ОП

Информация связанного списка – не данные типа int,  а некая сложная структура пусть - библиотечная  карта книги.

  вершина  хвост

  списка  списка

s

  …  0

  новый  новый  новый

  элемент

ФУНКЦИИ  СПИСКА

#include <string. h>

#include<stdio. h>

#include<iostream. h>

#include<conio. h>

int count ;  // внешняя переменная для нумерации структур в списке

// определение структурного типа:

struct spisoc{

char*name;  // название книги

char*author;  // имя  автора

int year;  // год издания

spisoc* next;  // указатель на следующую структуру в списке

};

// определение массива структур для дополнения с инициализацией

spisoc stm[]=

{ { "Turbo Pascal-7" , "", 1999 },

  { "Turbo C++" , "", 1991 },

  { "C-C++", " " , 1998 } };

spisoc *s;  // определение внешнего указателя на вершину списка, он

  // по умолчанию инициирован нулем (NULL)

// Функция вывода на экран данных структуры - параметра

void print(spisoc st)

{

//static int count =0;

cout<<"\n"<<++count<<". "<<st. name<<", " <<st. author<<", " <<st. year;

}

// Функция вывода без нумерации

void print1(spisoc st)

{ cout<<st. name<<", " <<st. author<<", " <<st. year;

}

// Функция дополнения структурой, передаваемой как параметр

void dop (spisoc*&s, spisoc*st)

{

spisoc*list = s, // текущий указатель инициируется указателем  на

  //вершину

*pr=0,  // вспомогательный указатель инициируется 0

*stnew=new(spisoc);  // выделяется память на новую структуру

  // типа  spisoc

*stnew=*st;  // копируются данные в новую структуру

// Организуем цикл продвижения по списку пока не  достигнем или  // нулевого указателя или пока не найдем такую структуру в списке,  // в которой поле названия должно по алфавиту стоять после поля  // названия вводимой структуры

while(list && (strcmp(list->name, st->name)<=0))

{ pr=list; list=list->next;}; // pr присваиваем значение указателя на

  // текущую структуры, а текущему

  //указателю list присваиваем значение

  //указателя на следующую структуру list->next

stnew->next=list;  //производим подключение справа: новую

  // запись помещаем перед  list

// организуем подключение слева

if(pr==0) s=stnew;  // если не только list но и pr равен нулю, это

  // значит, что список пуст и поэтому вершину

  //надо установить на новый элемент

else pr->next=stnew; // подключение слева

}

// Функция дополнения с клавиатуры

void dop1 (spisoc*&s)

{ spisoc*list,*pr ;

char c;

do

{  // тело цикла

clrscr();

cout<<"Для ввода данных нажмите любую клавишу и Esc –“

“если ввод производить не надо \n ";

c=getch();

// если символ отличен от символа Esc

if(c!=27){

list = s;  // устанавливаем текущий указатель на вершину списка

pr=0;  // устанавливаем вспомогательный указатель на 0

spisoc*stnew=new(spisoc);  // выделяем память на новую структуру

cout<<"Введите данные структуры\n"

<<"Название:" ;stnew->name=new char[50];  //выделяем память

cin. getline(stnew->name,90);  // вводим строку - название

cout<<"Автор:" ;stnew->author=new char[50];

cin. getline(stnew->author,90);

cout<<"Год издания:";cin>>stnew->year;  // вводим число - год

cin. ignore(80,'\n');  // игнорируем пробелы и извлекаем  Enter

// структура введена долее аналогично предыдущей функции

while(list && (strcmp(list->name, stnew->name)<=0))

{ pr=list; list=list->next;};

stnew->next=list;

if(pr==0) s=stnew;

else pr->next=stnew;

}

else clrscr();  // в противном случае, если символ равен Esc – очистка

}  // завершение тела цикла

while(c!=27);  // пока символ отличен от Esc повторяем тело цикла

}

//Функция чтения списка, использующая цикл для продвижения по //списку

void cht(spisoc*s)

{ cout<<"\n\nСтруктуры списка :";

count=0;  //  устанавливаем нумерацию структур на 0

spisoc*list=s;  // установка текущего указателя на вершину

if(list==0) cout<<"\nСписок пуст";

else

while(list)  // пока list отличен от нуля

{

print( *list);  // выводим структуру

list=list->next;  // переходим к следующей структуре

}  // тело цикла while

  count=0;  // опять нумерация структур - внешняя переменная

  //устанавливается на ноль

}

// Функция чтения списка, использующая рекурсию

void cht1(spisoc*s)

{

if(s!=0) 

{ print( *s);  // выводим структуру вершины

if ( s-> next!=0) // если  указатель на следующую структуру не нулевой

cht1( s->next);  // вызываем функцию, в которую в качестве вершины

  // передаем следующую структуру

  }

else cout<< “Список пуст” ;

}

//Функция поиска структуры первой попавшейся в списке, у которой //поле - год издания совпадает с параметром

void poisk (spisoc*s, int year)

{ spisoc*list=s;  // установка текущего указателя на вершину

if(list==0) cout<<"\nСписок пуст";

else {

while (list && list->year!=year) //пока не достигнем ноль или  не

  // найдем структуру, у которой совпадает поле с параметром

list=list->next;  // продвигаемся по списку

//если цикл завершился, при достижении нуля, нужной структуры нет в

// списке, в противном случае выводим эту структуру

if(list==0) cout<<"Элемент не найден";

else {cout<<"\n\n Результат поиска :";print1 (*list);}

}

}

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

void poisk1 (spisoc*s, int year)

{

  cout<<"\n\nРезультат поиска :";

  int k=0;  // счетчик структур в списке, у которых совпадает поле

  spisoc*list=s;  // устанавливаем текущий указатель на вершину

if(list==0) cout<<"\nСписок пуст";  //если он ни на что не указывает

else

{  // в противном случае

while (list)  // организуем цикл до конца списка

  {  //если есть совпадение,  выводим структуру

  if( list->year==year) {cout<<"\n"<<++k<<". "; print1 (*list);}

  list=list->next; // переходим к следующей структуре

  }

// просмотрели все структуры и, если k осталось равным 0

if(k==0) cout<<"Элемент не найден ";

}

}

//Функция удаления одной первой попавшейся структуры, у

//которой значение поля – год издания совпало со значением //параметра функции

void ud(spisoc*&s, int year)

{ spisoc*list=s,  // устанавливаем текущий указатель на вершину списка

*pr=0;  // вспомогательный указатель равен нулю

// организуем цикл продвижения по списку

while(list && list->year!=year) //пока не достигнем ноль или  не

  // найдем структуру, у которой совпадает поле с параметром

{  pr=list;  //  pr присваиваем значение текущего указатель

list=list->next;  //текущий указатель прикрепляем к следующей

  //структуре

  }

if(list==0) cout<<"Элемент не найден"; // если цикл прервался по

  //достижению конца списка

else

{  // альтернативная ветвь

cout<<"\n\n“Удаление :";print1(*list);  // в противном случае

  //выводится удаляемая структура

// удаляем структуру из списка

  if(pr==0)  // если найденная структура – первая в списке

  s=list->next; // вершину устанавливаем на следующую за ней

  // структуру

  //в противном случае – если не первая, предыдущая структура

  // напрямую связывается со следующей от list

  else pr->next=list->next;

  delete(list);  // память, отведенная для list освобождается

  }  // конец альтернативной ветви

}

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

void ud1 (spisoc*&s, int year)

{

static int k=0;  // счетчик нужных структур

  spisoc*list=s,  //текущий указатель устанавливается на вершину списка

*pr=0;  // вспомогательный на NULL

// организуем цикл продвижения по списку

while(list && list->year!=year) //пока не достигнем ноль или  не

  // найдем структуру, у которой совпадает поле с параметром

{pr=list; list=list->next;}  // продвигаемся по списку

//если мы достигли конца списка( list = =0), не найдя ни одной //структуры (k= = 0)

if((list==0)&&(k==0)) cout<<"\nЭлемент не найден";

else  // в противном случае – альтернативная ветвь

if(list!=0)  // если цикл завершился потому, что нашлась структура для

  //удаления

{

cout<<"\n"<<++k<<". ";print1(*list); // выводим структуру с номером

//удаляем структуру также  как в предыдущей функции

if(pr==0)

s=list->next;

else pr->next=list->next;

delete(list);

ud1(s, year);// опять вызываем функцию, в которую передаем вершину //уже измененного списка для поиска и удаления других нужных //структур

}  // конец альтернативной ветви

}

//Функция уничтожения списка

void osv (spisoc*&s)

{spisoc*list=s, // текущий указатель устанавливается на вершину списка

*pr=0;  // вспомогательный на NULL

while(list)  // пока не достигнем конца списка

{

  pr=list;  // текущий указатель запоминаем в pr

  list=list->next;  // текущий указатель прикрепляем к следующей

  //структуре списка

delete(pr);  // предыдущую структуру затираем – освобождаем

  // память, выделенную структуре

}

s=0;  // указатель на вершину получает значение NULL

}

void main()

{

for(int i=0;i<3; i++)

dop(s, stm+i);

dop1(s);

cht(s);

poisk1(s,1998);

cout<<"\n\nУдаление:";

ud1(s,1991);

cout<<"\n\nСтруктуры списка :";

cht1(s);

osv(s);

cht(s);  }

Пример двусвязанного линейного списка: