2015-04-12
367
Если до начала работы с данными невозможно определить, сколько памяти потребуется для хранения, память выделяется по мере необходимости отдельными блоками, связанными друг с другом с помощью указателей. Такой способ организации данных называется динамическими данными, поскольку их размер изменяется во время выполнения программы. Динамические данные могут занимать несмежные участки оперативной памяти.
Элемент динамического данного, часто называемый узлом, представляет собой структуру, содержащую по крайней мере два поля: для хранения данных (информационная часть узла) и для указателей (адресная часть узла). Полей данных и указателей может быть несколько. Поля данных могут быть любого типа. Описание простейшего элемента (узла) выглядит следующим образом:
struct Node
{ Data d; // информационная часть узла
// тип данных Data должен быть определен ранее
Node *next; // адресная часть узла
};
Самый простой способ связать элементы – сделать так, чтобы каждый элемент содержал адрес следующего. Такие динамические данные называются односвязным списком.
|
|
|
Над списками можно выполнять следующие операции:
· добавление элемента в конец списка;
· удаление элемента из списка;
· начальное формирование списка;
· просмотр (вывод) списка.
Пример:
По результатам сессии в деканате имеется список (таблица) задолжников, т.е. студентов, имеющих неудовлетворительные оценки по экзаменам, зачетам, курсовым проектам и работам. Каждая строка содержит информацию об одном студенте. Таблица содержит n строк. Требуется написать программу, которая печатает перечень групп, имеющих задолжников с указанием их количества в группе.
Список представляет собой таблицу
| № | Фамилия и инициалы | Курс | Группа |
| Иванов А.А. | ИСТ – 101 | ||
| Сидоров Б.Б. | АСУ – 120 | ||
| . | … | … | … |
# include <iostream.h>
# include <fstream.h>
# include <string.h>
# include <iomanip.h>
# include <stdlib.h>
# include <conio.h>
struct student
{
char name[30];
int kurs;
char gr[7];
};
struct group
{
char gr[7];
int ng;
};
struct node1 // узлы первого списка
{
student s; // информационная часть узла первого списка
node1*next; // адресная часть узла первого списка
};
struct node2 // узлы второго списка
{
group g; // информационная часть узла второго списка
node2*next; // адресная часть второго узла
};
class spisok // класс списка структур
{
private:
node1*beg1, *end1; //указатели на начало и конец 1-го списка
int n; //количество элементов в первом списке
node2 *beg2, *end2; //указатели на начало и конец 2-го списка
int k; //количество элементов во втором списке
node1*findname (student t); //функция для нахождения узла 1-го списка
public:
spisok() {m=k=0; beg1=end1=beg2=end2=NULL;} //конструктор
~spisok(); //деструктор
|
|
|
void inputstudentfile(); // ввод из файла первого списка
void outputstudent(); // вывод на экран первого списка
void addstudent(); // добавление элемента в первый список
void deletestudent(); // удаление элемента из первого списка
void perechgroup(); //формирование второго списка (перечня групп)
void outputgroup(); // вывод на экран второго списка
void outputgroupfile(); // вывод в файл второго списка
};
// Определение деструктора
spisok::~spisok ()
{
node1 *p1; // указатель на узлы первого списка
node2 *p2; // указатель на узлы второго списка
if (beg1!=NULL) // первый список не пустой
{ // надо вернуть память, занимаемую им
while (beg1!=NULL)
{
p1=beg1;
beg1=beg1->next; // узел удален из списка
delete p1; // освобождена память, занимаемая узлом
}
end1=NULL;
n=0;}
if (beg2!=NULL) // второй список не пустой
{ // надо вернуть память, занимаемую им
while (beg2!=NULL)
{
p2=beg2;
beg2=beg2->next; // узел удален из списка
delete p2; // освобождена память, занимаемая узлом
}
end2=NULL;
k=0;
}}
// Нахождение узла первого списка по заданной фамилии и группе
node1 *spisok:: findname (student tt)
{
node1 *p;
p=beg1;
while (p!=NULL)
{
if(strcmp(tt.name, p->s.name)==0 && strcmp(tt.gr, p->s.gr)==0) break;
// узел найден
p=p->next;
}
return NULL; // узел не найден
}
// Ввод 1-ого списка (исходной таблицы задолжников) из файла
void spisok:: inputstudentfile()
{
ifstream fin;
char file[10];
char iniz[7]; // рабочая переменная для инициалов
node1 *p1, *p; // указатели на узлы первого списка
node2 *p2; // указатель на узлы второго списка
// очистка рабочих областей (1-ого и 2-ого списков)
if (beg1!=NULL) // первый список не пустой
{ // надо вернуть память, занимаемую им
while (beg1!=NULL)
{
p1=beg1;
beg1=beg1->next; // узел удален из списка
delete p1; // освобождена память, занимаемая узлом
}
end1=NULL;
n=0;
}
if (beg2!=NULL) // второй список не пустой
{ // надо вернуть память, занимаемую им
while (beg2!=NULL)
{
p2=beg2;
beg2=beg2->next; // узел удален из списка
delete p2; // освобождена память, занимаемая узлом
}
end2=NULL;
k=0;}
// ввод 1-ого списка (таблицы задолжников) из файла
cout << ”Имя файла:”;
cin >> file;
fin.open(file);
if(fin==NULL) {cout<<”Файл не открыт.\n”; exit(1);}
p= new node1; // выделение памяти для 1-ого узла
if(p==NULL) { cout<<”Нет динамической памяти.”; getch(); exit(1);}
fin >> p->s.name >> iniz >> p->s.kurs >> p->s.gr;
strcat(p->s.name, “ “); // добавление инициалов через
strcat(p->s.name, iniz); // пробел к фамилии
p->next=NULL;
while(fin.good())
{// Добавление нового узла в список
if (beg1==NULL) beg1==p; else end1->next=p;
end1=p;
n++;
// Формирование нового узла
p= new node1;
if(p==NULL){cout<<”Нет динамической памяти.”;getch();exit(1);}
fin >> p->s.name >> iniz >> p->s.kurs >> p->s.gr;
strcat(p->s.name, “ “); // добавление инициалов через
strcat(p->s.name, iniz); // пробел к фамилии
p->next=NULL;
}
delete p; // удаление последнего несформированного узла
fin.close();}
// Вывод 1-го списка (таблицы задолжников) на экран
void spisok:: outputgroupstudent()
{
node1 *p;
cout << ” Исходный список структур. \n”;
cout<< “Фамилия и инициалы Курс Группа \n”;
for(p=beg1; p!=NULL; p=p->next)
cout << setw(16)<< p->s.name << setw(7)<< p->s.kurs << setw(8) << p->s.gr << endl;
}
// Добавление записи в 1-ый список (таблицу задолжников)
void spisok:: addstudent()
{
node1 *p; // указатель для нового узла
char iniz[7]; // рабочая переменная для инициалов
// выделение памяти для нового узла
p= new node1;
if(p==NULL) { cout<<”Нет динамической памяти.”; getch(); exit(1);}
// ввод информации о добавляемом и формирование нового узла
cout << “Введите фамилию: ”;
cin >> p->s.name >> iniz;
strcat(p->s.name, “ “); // добавление инициалов через
strcat(p->s.name, iniz); // пробел к фамилии
cout << “Курс: ”;
cin >> p->s.kurs;
cout << “Группа: ”;
cin >> p->s.gr;
p->next=NULL;
// добавление нового узла в список
if (beg1==NULL) beg1==p; else end1->next=p;
end1=p;
n++;}
// Удаление узла из первого списка
void spisok:: deletestudent()
{
node1 *p, *p0;
student t; // рабочая переменная для информации об удаляемом
char iniz[7]; // рабочая переменная для инициалов
// ввод фамилии и группы удаляемого
cout << “Введите фамилию: ”;
cin >> t.name >> iniz;
strcat(t.name, “ “); // добавление инициалов через
strcat(t.name, iniz); // пробел к фамилии
|
|
|
cout << “Группа: ”;
cin >> t.gr;
p0=findname(t);
if (p0==NULL) {cout<<t.name<” не найден. \n“; getch(); return;}
if (p0==beg1) //найденный узел является первым в списке
{
beg1=beg1->next; // удаление узла из списка
if (p0==end1) end1==NULL; // найденный узел последний в списке
}
else
{// поиск предшествующего узла
p=beg1;
while (p->next!=p0)
p=p->next;
p->next=p0->next; // удаление узла из списка
if (p0==end1) end1=p; // найденный узел последний в списке
}
n--;
delete p0;}
// Формирование второго списка (перечня групп)
void spisok:: perechengroup()
{
int fl;
node1 *p1 // указатель на узлы первого списка
node2 *p2, *p; // указатели на узлы второго списка
// очистка рабочей области (2-ого списка)
if (beg2!=NULL) // второй список не пустой
{ // надо вернуть память, занимаемую им
while (beg2!=NULL)
{
p2=beg2;
beg2=beg2->next; // узел удален из списка
delete p2; // освобождена память, занимаемая узлом}
end2=NULL;
k=0;}
// формирование второго списка
for(p1=beg1; p1!=NULL; p1=p1->next)
{
fl=1;
for(p2=beg2; p2!=NULL; p2=p2->next)
{
if (strcmp (p1->s.gr, p2->g.gr)==0)
{fl=0; p2->g.ng++; break;}}
if (fl==1)
{
p=new node2;
if (p==NULL) {cout<<”Нет памяти”; getch(); exit(1);}
p->next=NULL;
strcpy (p->g.gr, p1->s.gr);
p->g.ng=1;
// Добавление нового узла во второй список
if (beg2==NULL) beg2==p; else end2->next=p;
end2=p;
k++;}}}
// Вывод 2-го списка (перечня групп, имеющих задолжников) на экран
void spisok:: outputgroup()
{
node2 *p;
cout << ” Перечень групп, имеющих задолжников. \n”;
cout<< “ Группа Кол-во \n”;
for(p=beg2; p!=NULL; p=p->next)
cout << setw(8)<< p->g.gr << setw(8)<< p->g.ng << << endl; }
// Вывод 2-го списка (перечня групп, имеющих задолжников) в файл
void spisok:: outputgroupfile()
{
оfstream fout;
char file[10];
node2 *p;
cout << ”Имя файла:”;
cin >> file;
fout.open(file);
if(!fout.good()) {cout<<”Файл не открыт.\n”; exit(1);}
for(p=beg2; p!=NULL; p=p->next)
fout << setw(8)<< p->g.gr << setw(8)<< p->g.ng << << endl;
fout.close();}
// Текст основной программы:
void main()
{
spisok a; // Объект класса spisok
int j;
while (1)
{
clrscr();
cout << “1. Ввод таблицы из файла. \n”;
cout << “2. Вывод таблицы на экран. \n”;
cout << “3. Добавление записи в таблицу. \n”;
cout << “4. Удаление записи из таблицы. \n”;
cout << “5. Формирование перечня групп. \n”;
cout << “6. Вывод перечня групп на экран. \n”;
cout << “7. Вывод перечня групп в файл. \n”;
|
|
|
cout << “8. Выход из программы. \n”;
cout << “\n Ваш выбор (1-8):”;
cin >> j;
switch(j)
{
case 1: a.inputstudentfile(); break;
case 2: a.outputstudent(); getch(); break;
case 3: a.addstudent(); break;
case 4: a.deletestudent(); break;
case 5: a.perechengroup(); break;
case 6: a.outputgroup(); getch(); break;
case 7: a.outputgroupfile(); break;
case 8: cout << “Завершение рабоы.”; getch(); return;
default: cout << “ Ошибка в выборе пункта меню. Повторите.”; getch();}}}
Задания для лабораторной работы:
Варианты заданий соответствуют заданиям лабораторной работы № 31-32. Для их решения необходимо использовать классы списка структур, предусмотрев выполнение операций добавления и удаления записей в исходном массиве. Для демонстрации методов класса требуется реализовать программу меню.
Контрольные вопросы:
1. Для чего необходимы динамические данные?
2. Что такое список?
3. Какие списки сущестуют?
4. Какие операции можно выполнять над списками? Привести примеры.
5. Назовите основные принципы объектно-ориентированного программирования.
