| 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; удаляет символ перевода строки.
|
|
При работе со списком используются операции косвенного обращения по указателю к структуре или к ее элементу - "." или "->".
Пример односвязного списка и операции над ним.