учебное пособие. Часть1. Информатика

Удаление узла производится еще пpоще (рис. 28): k = top;

top = top->link; delete k;

Рассмотрим пример, демонстрирующий удаление различных узлов стека (это более сложный процесс): из входной последовательности чисел построить стек, удалить из стека узлы, содержащие максимальное значение (рис. 29).

// Пример pr56

#include <cstdio> using namespace std;

int main()

{

struct node

{ char info; node *link; };

node *top, *k; char w;

top = NULL;

puts ( "введите число" ); scanf ( "%c", &w ); while ( !feof ( stdin ))

{

k = new node; k->link = top; k->info = w; top = k ;

printf ( "введите число\n" ); scanf ( " %c", &w );

}

/* Вывод построенного стека*/ k=top;

while ( k != NULL )

{

printf (" %c", k->info ); k = k->link;

}

//Поиск максимального значения k = top;

int max = top->info; while (k!=NULL)

{

281

k = top;

}

else

{ //ecли максимальный не веpшина l->link = k->link;

delete k;

k = l->link;

}

else

{ //если не максимальный l = k;

k = k->link;

}

}

puts ( "Стек после удаления максимального:" ); k = top;

while ( k != NULL )

{

printf ( " %c", k->info ); k = k->link;

}

return 0;

}

Следующий пример демонстрирует добавление узлов не только в вер- шину стека, но и в произвольное место (рис. 31). Построение стека из вход- ной последовательности символов и добавление узлов c символом ':' пеpед каждым знаком '=’.

//Пример pr56

#include <cstdio> using namespace std; int main()

struct node

{

char info; node *link;

};

{

node *top, *k; char w;

top = NULL;

puts ( "введите cимвол:" ); scanf( "%c", &w );

while (!feof (stdin ))

283

{

k = new node; k->link = top; k->info = w; top = k ;

printf ( "введите число\n" ); scanf ( " %c", &w );

}

k = top;

while ( k != NULL )

{

printf ( " %c", k->info ); k = k->link;

}

//Добавление узлов фактически после знака '=' k = top;

node *newnode; /* Поиск знаков '='

while ( k != NULL )

{

if ( k->info == '=' )

{

newnode = new node;// Добавление узла newnode->link = k->link;

k->link = newnode; newnode->info = ':';

}

k = k->link;

}

puts ( "после добавления узлов" ); k = top;

while ( k != NULL )

{

printf ( " %c", k->info ); k = k->link;

}

return 0;

}

Ещё одним способом организации простейшего линейного списка яв- ляется организация типа очередь (далее очередь). Организация очередей по- хожа на схему стека, но в очереди пришедший первым обслуживается пер- вым (рис. 32), т. е. это способ организации ожидания. Часто очередь описы- вают как структуру FIFO: first in - fist out. Доступ

284

r->link = k ;//добавление узла справа r = k;

printf ( "введите число\n" ); scanf(" %d",&w);

}

//Вывод содержимого очереди k = l;

while ( k != NULL )

{

printf ( "%c", k->info ); k = k->link;

}

return 0;

}

Добавление нового узла к очереди происходит справа (используется указатель r):

node *newnode; scanf ( " %c", &w ); newnode= new node;

newnode->link = NULL; newnode->info = w;

r->link = newnode ; // Добавление узла справа r = newnode;

Исключение узла из очереди происходит слева (используется указа- тель l):

k = l;

l = l->link; delete k;

Если к операторам формирования очереди добавить ещё один опера-

тор:

r->link=l;

то получится циклический список (рис. 33). При этом любой из указате- лей l или r может быть принят за "голову" списка.

286

void llist ( node *left )

{

node *k = left; while ( k != NULL )

{

printf ( "%d \n" ,k->g ); k = k->rlink;

}

}

/*_____Функция вывода списка спpава налево_____*/ void rlist ( node *right )

{

node *k = rigth; while ( k != NULL )

{

printf ( "%d \n ", k->g );

// Создание пеpвого узла printf ( "введите число" ); scanf ( "%d", &w );

k = new node; // Выделение дин. памяти под узел k->g = w;//Заполнение полей узла

k->rlink = NULL;

k->llink = NULL; rigth = k;

q = k; // Указатель на предпоследний узел /*______Построение остальных узлов списка_______*/ printf ( "введите следующее число:" );

scanf ( "%d", &w ); while ( !feof ( stdin ))

{

k = new node; k->g = w;

k->rlink = q; //Связываем созданный узел с предыдущим q->llink = k; //Связываем предыдущий узел с созданным

289

q = k;

printf ( "введите следующее число:" ); scanf ( "%d", &w );

}

q->llink = NULL; left = q;

puts ( "Слева напpаво " ); llist ( left ); puts ( "Спpава налево" ); rlist ( right );

//Добавление после узла, содержащего положительное

//значение, узла, содержащего ноль (слева направо) node *newnode; // Указатель на новый узел

k = left;

while ( k !=NULL )

{

if ( k->g > 0 )

{

newnode = new node; newnode->g = 0; newnode->rlink = k->rlink; newnode->llink = k;

if ( k == right )

rigth = newnode;//Если добавляем после последнего else

k->rlink->llink = newnode; //Добавляем в середину k->rlink=newnode;

}

k = k->rlink;

}

puts ( "Вывод после добавления нулей" ); puts ( "Слева напpаво " ); llist ( left ); puts ( "Спpава налево" ); rlist ( rigth);

/*____________Удаление нулей_______________*/ node *l;//Указатель на предыдущий узел

l = k = left;

while ( k != NULL )

{

if ( k->g == 0 )

{

if ( k == left ) //Удаление самого левого

{

q = k;

left = k->rlink; left->llink = NULL;

290