Лабораторная работа № 8. Динамические структуры данных. Списки

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

Задание	Краткие теоретические сведения
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; } Функция atoi() преобразует строку в целое число. Функция strcmp(s1, s2) возвращает 0, если s1=s2. Результат <0, если s1<s2 и результат положителен, если s1>s2. Функция strcpy(s, p) копирует содержимое s в p. Оператор p[strlen(p)-1] = 0; удаляет символ перевода строки.

4. Дополнить проект п. 3 разработав функции в соответствии со своим вариантом из таблицы, представленной ниже.

В начало практикума