Программа формирования линейного списка и выполнения операций над ним
Изучите приведенную программу. Протестируйте программу. Объясните полученные результаты.
#include <conio.h>
#include <stdio.h>
#include <iostream.h>
// Определяется структура. Заказываем необходимый размер
// памяти для записи информации о новом объекте.
struct node {
int inf; // Поле для записи целых чисел.
node *next; // Поле указателя для записи адресов элементов типа node.
};
void main()
{node *r, *fr = NULL, *er; // fr – указатель на головной элемент списка.
// er – указатель на последний элемент списка.
// r – указатель для формирования нового узла списка.
node *rp; int a, b; // a – переменная для записи целых чисел.
clrscr();
FILE *f;
f = fopen("t.dat","r"); // Начало формирования списка.
do // Начало цикла ввода чисел из файла.
{ fscanf(f,"%d", &a); // Ввод числа из файла.
r = new node; // Создаем новый элемент списка.
// Выделяем память для нового элемента.
r->inf = a; // Инициализируем поле inf нового элемента списка.
r->next = NULL; // Инициализируем поле указателя нового элемента
//списка.
if (fr == NULL) // Проверяем: список существует или нет. Если
// fr = NULL, то списка нет.
fr = r; // Поэтому новый элемент объявляем головным.
else // Если список существует, то
er -> next = r; // новый элемент присоединяем к списку.
er = r;
} // Новый элемент объявляем последним.
while (!feof(f)); // Конец цикла ввода чисел из файла.
fclose(f); // Конец формирования списка.
// Вывод списка на экран.
cout << "\tСформирован список:\n\n";
r = fr;
while (r != NULL) // Пока не дошли до последнего элемента списка.
{ cout << r -> inf << " "; // Вывод информации из поля inf элемента,
// адрес которого находится в указателе r.
r = r -> next; // Переход к следующему элементу списка.
// Для этого из поля next текущего элемента списка
// в указатель r пересылаем адрес на следующий элемент.
}
getch();
cout << "\n\nУдалить узел cо значением k= ";
cin >> a;
r = fr;
if (r -> inf == a)
{ cout << "\nудаляется головной узел списка\n";
fr = fr -> next; // В указатель на первый элемент пересылаем
// адрес второго элемента списка.
delete r;
}
else
{ while ((r -> inf != a) && ( r != NULL)) // Поиск элемента, который
{ // надо удалить.
rp = r; // Запоминаем адрес пройденного элемента.
r = r -> next;
} // Переходим на новый элемент.
if (r -> inf == a) // Проверяем, найден элемент или нет.
{
cout << " Удаляется узел со значением= " << r -> inf << "\n\n";
rp -> next = r -> next; // Поле указателя удаляемого элемента
// пересылаем в поле указателя элемента, который
// расположен перед удаляемым.
delete r;
cout << "\tСписок после удаления элемента: \n\n";
r = fr;
while (r != NULL) // Пока не дошли до последнего элемента списка.
{ cout << r -> inf << " "; // Вывод значения текущего элемента списка.
r = r -> next; // Переход к следующему элементу списка.
// Для этого из поля next текущего элемента списка
} // в указатель r пересылаем адрес на следующий элемент.
}
else
cout << "\n" << "Узел со значением " << a << " не найден ";
getch();
}
// Вставка нового элемента в список.
cout << "\n\nВставить в список элемент со значением b= ";
cin >> b;
cout << "\n\nЗа элементом со значением n = ";
cin >> a;
r = fr;
while ((r -> inf != a) && (r != NULL)) r = r -> next;
if (r -> inf == a)
{ rp = new node; // Выделяем память под новый элемент.
rp -> inf = b; // Заполняем поле inf нового элемента.
rp -> next = r -> next; // К новому элементу присоединяем правую часть списка.
r -> next = rp; // К левой части списка присоединяем новый элемент списка.
cout << "Cписок после вставки элемента со значением: " << b << "\n";
r = fr;
while (r != NULL)
{ cout << r -> inf << " ";
r = r -> next;
}
}
else cout << "\nЭлемент списка со значением " << a << " не найден ";
// Вставка в список нового головного элемента.
cout << "\n\nВведи значение для нового головного элемента n = ";
cin >> a;
rp = new node; // Выделяем память под новый элемент.
rp -> inf = a; // Заполняем поле inf нового элемента.
rp -> next = fr; // Новый элемент делаем первым.
fr = rp; // В указатель на первый элемент списка
// пересылаем адрес нового элемента.
cout << "\nСписок с новым головным элементом:\n";
r = fr;
while (r != NULL)
{ cout << r -> inf << " ";
r = r -> next;
}
getch();
}