1. Цель работы:
Изучение списковых структур данных и приобретение навыков разработки и отладки программ, использующих динамическую память. Исследование особенностей организации списков средствами языка С/С++.
2. Постановка задачи и текст индивидуального задания.
Представить одну из приведенных ниже таблиц в виде линейного списка L, элементами которого являются строки таблицы. Написать функции организации, добавления элемента в список, исключения элемента из списка, просмотра списка, а также одну из функций в соответствии с вариантом, приведенным ниже. Значения и количество записей в таблице студент выбирает самостоятельно. Исходные данные после организации списка должны сохраняться в файле и при повторном запуске программы считываться из файла. Количество строк таблицы не задается.
Использовать таблицу 1. Список организовать в виде стека. Дополнительно написать функцию, которая вставляет в конец стека новый элемент.
Таблица 1. Таблица по варианту
| Номер | ФИО | Год рождения | Место рождения | Пол |
Дата приёма на работу |
Оклад |
3. Теоретические сведения
В предыдущих лабораторных работах были рассмотрены задачи, в которых объем памяти, необходимый программе, был известен либо до компиляции программы, либо на этапе ввода данных. В первом случае память резервировалась с помощью операторов описания, во втором случае ― с помощью функций выделения памяти. В каждом из этих случаев выделялся непрерывный участок памяти.
Если до начала работы программы невозможно определить, сколько памяти потребуется для хранения данных, то память выделяется по мере необходимости отдельными блоками, которые связывают друг с другом при помощи указателей. Такой способ выделения памяти предполагает организацию в памяти ЭВМ динамических структур данных, поскольку их размер изменяется во время выполнения программы. Из динамических структур в программах чаще всего используются различные линейные списки, стеки, очереди, деревья. Они различаются способами связи отдельных элементов и допустимыми операциями над ними. Динамическая структура может занимать несмежные участки оперативной памяти. В процессе работы программы элементы структуры могут по мере необходимости добавляться и удаляться.
Напомним, что линейным списком называется структура данных, при которой логический порядок следования элементов задается путем ссылок, т.е. каждый элемент списка содержит указатель на следующий элемент (предыдущий элемент). Доступ к первому элементу списка выполняется с помощью специального указателя – указателя на начало (голову) списка.
Односвязным линейным списком называют список, в котором предыдущий элемент ссылается на следующий. Двусвязный линейный список – это список, в котором предыдущий элемент ссылается на следующий, а следующий – на предыдущий. Односвязный циклический список – это односвязный линейный список, в котором последний элемент ссылается на первый. Стек – это односвязный список, в котором компоненты добавляются и удаляются только со стороны вершины списка. Очередь – это односвязный список, в котором компоненты добавляются в конец списка, а удаляются со стороны вершины списка.
5. Алгоритм решения задачи:
Блок-схема 1. Главная функция
Блок-схема 2. Функция “Очистить стек”
Блок-схема 3. Функция “Вывести стек”
Блок-схема 4. Функция “Добавить элемент в конец”
Блок-схема 5. Функция “Сохранить в файл”
Блок-схема 6. Функция “Добавить элемент в начало”
Блок-схема 7. Функция “Извлечь из файла”
Блок-схема 8. Функция “Удалить элемент”
6. Текст программы
#include <iostream.h>
#include <string>
#include <windows.h>
HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
char s1[256];
void GotoXY(int X, int Y){ //Установка координат курсора ввода
COORD coord = { X, Y };
SetConsoleCursorPosition(hStdOut, coord);
}
struct Node{
string Num;
string Fio;
int God;
string Mesto;
string Pol;
string Mind;
int Oklad;
Node *Next; //Указатель на предыдущий элемент
};
struct List{
Node *Head; //Верхний элемент
List():Head(NULL){}; //Конструктор класса
void New(); //Создать стек
void Add_Start(); //Добавить элемент в начало
void Add_End(); //Добавить элемент в конец стека
void Show(); //Показать стек
void Del(); //Удалить верхний элемент
void Save();
void Open();
};
void List::New(){
Head=NULL; //Очищаем указатели
cout<<"Новый стек создан!"<<endl;
system("pause");
}
void List::Add_Start(){
Node *p=new Node; //Указатель на новый элемент
p->Next=NULL;
cout<<"Введите Номер(string): ";
cin>>p->Num;
cout<<"Введите Фио(string): ";
cin>>p->Fio;
cout<<"Введите год рождения(int): ";
cin>>p->God;
cout<<"Введите место рождения(string): ";
cin>>p->Mesto;
cout<<"Введите пол(string): ";
cin>>p->Pol;
cout<<"Дата приёма на работу(string): "; ///////////////////////////////////////////
cin>>p->Mind;
cout<<"Введите оклад(int): ";
cin>>p->Oklad;
if (Head==NULL) { //Если стек пуст
Head=p;
}
else{
p->Next=Head;
Head=p;
}
cout<<"Элемент добавлен!"<<endl;
system("pause");
}
void List::Add_End(){
Node *p=Head;
Node *new_p=new Node; //Новый элемент
new_p->Next=NULL;
cout<<"Введите Номер(string): ";
cin>>new_p->Num;
cout<<"Введите Фио(string): ";
cin>>new_p->Fio;
cout<<"Введите год рождения(int): ";
cin>>new_p->God;
cout<<"Введите место рождения(string): ";
cin>>new_p->Mesto;
cout<<"Введите пол(string): ";
cin>>new_p->Pol;
cout<<"Дата приёма на работу(string): "; ///////////////////////////////////////////
cin>>new_p->Mind;
cout<<"Введите оклад(int): ";
cin>>new_p->Oklad;
while (p->Next!=NULL){
p=p->Next;
}
p->Next=new_p;
cout<<"Элемент добавлен!"<<endl;
system("pause");
}
void List::Show(){
system("cls");
Node *p=Head;
int y=2;
if(Head==NULL){
system("cls");
cout<<"Не найдено ни одной записи!"<<endl;
system("pause");
return;
}
cout<<" Номер ФИО Год рождения Место Пол Дата Оклад "<<endl;
cout<<"-------------------------------------------------------------------------------"<<endl;
while (p!=NULL){
GotoXY(3,y);
cout<<p->Fio<<endl;
GotoXY(10,y);
cout<<p->Fio<<endl;
GotoXY(23,y);
cout<<p->God<<endl;
GotoXY(40,y);
cout<<p->Mesto<<endl;
GotoXY(51,y);
cout<<p->Pol<<endl;
GotoXY(61,y);
cout<<p->Mind<<endl;
GotoXY(72,y);
cout<<p->Oklad<<endl;
cout<<endl;
p=p->Next;
y=y++;
}
cout<<endl;
system("pause");
}
void List::Del(){
Node *p=Head;
if (Head==NULL) {
cout<<"Список итак уже пуст"<<endl;
system("pause");
return;
}
Head=p->Next;
delete p;
cout<<"Вырхний элемент удален"<<endl;
system("pause");
}
void List::Save(){
Node *p=Head; //указатель на структуру
FILE *output; // указатель на файл
if(Head==NULL){
system("cls");
cout<<"Не найдено ни одной записи!"<<endl;
return;
}
else{
output = fopen("Spisok.txt","wb" ); //создаем файл, режим записи данных
while ( p!= NULL ){
fwrite ( p, sizeof (Node), 1, output );
p = p->Next;
}}
fclose (output);
cout<<"Запись завершена"<<endl;
system("pause");
}
void List::Open(){
FILE *input; //указатель на файл
Node *p,*r;
Node *last;
r=NULL;
input = fopen ("Spisok.txt","rb" ); //открываем файл, режим чтения данных
while (!feof(input)){
last=p;
p = new Node; //выдедение памяти под считываемые данные
fread (p, sizeof(Node),1,input); //чтение из файла 1 структуры
p->Next = NULL;
if ( r != NULL )
r->Next = p;
else
Head = p;
r = p;
}
last->Next=NULL;
fclose (input);//закрытие файла
cout<<"Файл загружен"<<endl;
system("pause");
}
void Fun(){
system("cls");
cout<<"1. Новый"<<endl;
cout<<"2. Просмотреть"<<endl;
cout<<"3. Добавить в начало"<<endl;
cout<<"4. Добавить в конец"<<endl;
cout<<"5. Удалить"<<endl;
cout<<"6. Сохранить в файл"<<endl;
cout<<"7. Извлечь из файла"<<endl;
cout<<"8. Выход"<<endl<<endl;
}
List MyStack; //Пустой стек
void main(){
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
int k;
do{
Fun();
cin>>k;
switch (k) {
case 1: MyStack.New(); break;
case 2: MyStack.Show(); break;
case 3: MyStack.Add_Start(); break;
case 4: MyStack.Add_End();break;
case 5: MyStack.Del();break;
case 6: MyStack.Save();break;
case 7: MyStack.Open();break;
case 8: exit(0); break;
}
}
while(1);
system("pause");
}
7. Таблица используемых переменных.
| Переменная | Тип | Значение |
| Case 1 | char | Пункт меню |
| Case 2 | char | Пункт меню |
| Case 3 | char | Пункт меню |
| Case 4 | char | Пункт меню |
| Case 5 | char | Пункт меню |
| Case 6 | char | Пункт меню |
| Case 7 | char | Пункт меню |
| Case 8 | char | Пункт меню |
8. Результаты работы программы:
После компиляции кода, приложение имеет вид нумерованного меню. Программа предлагает ввести пользователю одну из цифр от 1 до 8. За каждой цифрой закрепляет вызываемая функция, которая совершает предопределенное действие.
На рисунке 4.1 мы видим 8 пунктов меню:
- Новый
- Просмотреть
- Добавить в начало
- Добавить в конец
- Удалить
- Сохранить в файл
- Извлечь из файла
- Выход
Рисунок 4.1 – Главное меню программы
Функция “Новый” создаёт новый стек путем очищения указателя на верхний элемент стека.
Функция “Просмотреть” ставить указатель на начало стека и, путём перемещения указателя, выводит информационную часть стека.
Функция “Добавить в начало” смещает текущую шапку на новую введенную структуру. Если шапка пустая, то введенный элемент становится шапкой.
Функция “Добавить в конец” ставит временный указатель на начало стека, и путем перемещения указателя, доходит до последнего элемента. После достижения последнего элемента, пользователь вводит поля новой структуры, после чего новая структура приклеивается к концу стека.
Функция “Удаление” удаляет верхний элемент стека. Смещая указатель шапки на позицию вперед
Функция “Сохранения в файл” ставит указатель на начало стека и пошагово записывает каждый элемент в файл.
Функция “Извлечь из файла” пошагово считывает каждый элемент структуры и формирует стек.
Функция “Выход” обрывает бесконечный цикл и выходит из программы.
Добавим несколько элементов и выведем их на экран. Продемонстрируем выполнение на рисунках 4.2–4.3.
Рисунок 4.2 – Добавление элемента в начало
Рисунок 4.3 – Вывод стека на экран
9. Выводы:
Изучили списковых структуры данных и приобрели навыки разработки и отладки программ, использующих динамическую память. Исследовали особенности организации списков средствами языка С/С++.