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

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); }

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

Дата добавления: 2015-07-26