Лабораторная работа № 6. Динамические структуры данных. Списки
Список представляет собой линейную последовательность переменных, каждая из которых связана указателями со своими соседями. Списки бывают односвязные (каждый элемент имеет указатель на следующий); двусвязные (каждый элемент имеет указатель на следующий и на предыдущий); двусвязные циклические (первый и последний элементы ссылаются друг на друга).
| Задание
| Краткие теоретические сведения
| | 1. Изучить работу с односвязным списком, выполнив программу, представленную в правой части. Написать условие задачи.
| 
При работе со списком используются операции косвенного обращения по указателю к структуре " -> " или операции принадлежности "."
| | 2. Изучить работу с двусвязным списком, выполнив программу, представленную в правой части.
Написать условие задачи и комментарии к операторам.
|
| #include < iostream>
using namespace std;
extern struct list a, b, c;
struct list
{ int vv;
list*next;
list*prev;
} a = {9, & b, NULL}, b = {5, & c, & a},
c = {1, NULL, & b}, *px = & a;
int A[10] = {345, 435, 56, 54, 456, 345, 6, 456, 567, 45};
list *insert(list *ph, int x)
{ list *pn, *p; pn = new list;
pn-> next = pn-> prev = NULL;
pn-> vv = x;
if(ph == NULL) ph = pn;
else
{ for(p = ph; p-> next! = NULL; p = p-> next);
p-> next = pn; pn-> prev = p;
}
return ph;
}
| void scan(list*p)
{
for(; p! = NULL; p = p -> next)
cout < < p -> vv < < " ";
cout < < endl;
}
int main()
{ px = NULL;
int i, m, k;
for(m = 0; m < 10; m++)
{ for(i = 1, k = 0; i < 10; i++)
if(A[i] > A[k]) k = i;
px = insert(px, A[k]);
A[k] = -1;
}
px = insert(px, 6);
scan(px);
return 0;
}
|
| | 3. В правой части записана программа, которая формирует двусвязный список для хранения информации, содержащей адреса людей (имя, улицу и город).
Информация может быть записана в файл и загружена из файла.
Написать комментарии к программе.
| #include < iostream>
#include < fstream>
using namespace std;
struct Adr
{ char name[30];
char street[40];
char city[20];
struct Adr *next;
struct Adr *prev;
};
struct Adr *head; struct Adr *last;
int Menu(void)
{ char s[80]; int c; cout< < endl;
cout< < " 1. Ввод имени" < < endl;
cout< < " 2. Удаление имени" < < endl;
cout< < " 3. Вывод на экран" < < endl;
cout< < " 4. Поиск" < < endl;
cout< < " 5. Сохранить в файл" < < endl;
cout< < " 6. Загрузить из файла" < < endl;
cout< < " 7. Выход" < < endl; cout< < endl;
do
{ cout< < " Ваш выбор: "; gets(s); cout< < endl;
c = atoi(s);
} while(c < 0 || c > 7);
return c;
}
void Sozdat(Adr *i, Adr **head, Adr **last)
{ struct Adr *old, *p;
if(*last == NULL)
{ i-> next = NULL; i-> prev = NULL;
*last = i; *head = i; return;
}
p = *head; old = NULL;
while(p)
{ if(strcmp(p-> name, i-> name) < 0)
{ old = p;
p = p-> next;
}
else
{ if(p-> prev)
{ p-> prev-> next = i; i-> next = p;
i-> prev = p-> prev; p-> prev = i;
return;
}
i-> next = p; i-> prev = NULL;
p-> prev = i; *head = i;
return;
}
}
old-> next = i; i-> next = NULL;
i-> prev = old; *last = i;
}
void Vvod(char *prompt, char *s, int count)
{ char p[255];
do
{ cout< < (prompt); fgets(p, 254, stdin);
if(strlen(p) > count)
cout< < (" Слишком длинная строка" ); //длина строки
} while(strlen(p) > count);
p[strlen(p)-1] = 0; strcpy(s, p);
}
void VvodSp(void)// Ввод строки
{ struct Adr *t; int i;
t = new (struct Adr);
if(! t) { cout< < (" Нет свободной памяти" ); return; }
Vvod(" Введите имя: ", t-> name, 30);
Vvod(" Введите улицу: ", t-> street, 40);
Vvod(" Введите город: ", t-> city, 20);
Sozdat(t, & head, & last);
}
void VyvodSp(void)//Вывод списка на экран
{ struct Adr *t; t = head;
while(t)
{ cout< < t-> name< < ' ' < < t-> street < < ' ' < < t-> city< < endl;
t = t-> next;
}
cout< < " " < < endl;
}
void Poisk(void)// Поиск имени в списке
{ char name[40]; struct Adr *t; t = head;
cout< < " Введите имя: "; gets(name);
while(t)
{ if(! strcmp(name, t-> name)) break; t = t-> next; }
if(! t) cout< < " Имя не найдено" < < endl;
else cout < < t-> name < < ' ' < < t-> street < < ' ' < < t-> city< < endl;
}
void Udalit( Adr **head, Adr **last)// Удаление имени из списка
{ struct Adr *t; char name[40]; t = *head;
cout< < " Введите имя: "; gets(name);
while(t)
{ if(! strcmp(name, t-> name)) break; t = t-> next; }
if(t)
{ if(*head == t)
{ *head = t-> next;
if(*head) (*head)-> prev = NULL;
else *last = NULL;
}
else
{ t-> prev-> next = t-> next;
if(t! = *last) t-> next-> prev = t-> prev;
else *last = t-> prev;
} delete t;
}
}
void Zapisat(void)//Запись в файл
{ struct Adr *t; FILE *fp;
fp = fopen(" mlist", " wb" );
if(! fp) { cout< < " Файл не открывается" < < endl; exit(1); }
cout< < " Сохранение в файл" < < endl;
t = head;
while(t)
{ fwrite(t, sizeof(struct Adr), 1, fp); t = t-> next; }
fclose(fp);
}
void Schitat() //Считывание из файла
{ struct Adr *t; FILE *fp;
fp = fopen(" mlist", " rb" );
if(! fp) { cout< < " Файл не открывается" < < endl; exit(1); }
while(head)
{ last = head-> next; delete head; head = last; }
head = last = NULL;
cout< < " Загрузка из файла" < < endl;
while(! feof(fp))
{ t = new (struct Adr);
if(! t) { cout< < " Нет свободной памяти" < < endl; return; }
if(1! = fread(t, sizeof(struct Adr), 1, fp)) break;
Sozdat(t, & head, & last);
}
fclose(fp);
}
int main(void)
{ setlocale (LC_CTYPE, " Rus" );
head = last = NULL;
for(;; )
{ switch(Menu())
{ case 1: VvodSp(); break;
case 2: Udalit(& head, & last); break;
case 3: VyvodSp(); break;
case 4: Poisk(); break;
case 5: Zapisat(); break;
case 6: Schitat(); break;
case 7: exit(0);
}
}
return 0;
}
| 4. Дополнить проект п. 3 разработав функции в соответствии со своим вариантом из таблицы, представленной ниже. Запись в файл и считывание информации из файла осуществить с помощью операторов языка С++.
| № варианта
| Задание для выполнения
| | 1, 3
| DeleteDouble() – функция удаления повторяющихся (имеющих одинаковые поля или одно из полей) элементов.
| | 2, 4
| DeleteKFirst(int k) – функция удаления К первых элементов списка.
| | 5, 7
| DeleteEveryМ (int m) – функция удаления каждого М-ого элемента списка.
| | 6, 8
| DeleteKLast(int k) – функция удаления К последних элементов списка.
| | 9, 11
| DeleteList – функция удаления всего списка.
| | 10, 12
| FindMin – функция поиска минимального элемента списка по одному из выбранных полей.
| | 13, 15
| FindMax – функция поиска максимального элемента списка по одному из выбранных полей.
| | 14, 16
| CountList – функция подсчета числа элементов списка.
|
В начало практикума
Популярное:
|
