Добрый день.Столкнулся с такого вот рода проблемой: необходимо переделать код программы,обрабатывающей двусвязный список,для работы с односвязными списками.Как ни пытался - ничего толком не получилось.Сам листинг программы:
Нашел ещё примеры нескольких соглашений,на основе которых можно описывать односвязный список,но как применить к этой программе - не знаю...
1)Список циклический,никогда не бывает пустым:
2)Ведущий указатель,null-указатель завершающего узла
3)Фиктивный ведущий узел,null-указатель завершающего узла
Буду благодарен за любую помощь.
C++:
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
struct base {
char fio [30]; // ФИО сотрудника
char bolezn [50]; // Название болезни
int dlit; // Длительность болезни
base *prev; // Указатель на предыдущую запись
base *next; // Указатель на следующую запись
};
base *first = NULL; // Указатель на начало списка
base *last = NULL; // Указатель на конец списка
int List (void);
void AddItem (void)
{
base *db;
// создаем новую структуру
db = new base;
// заполняем её
cout << "Введите фамилию сотрудника: ";
cin >> db->fio;
cout << "Введите название болезни: ";
cin >> db->bolezn;
cout << "Введите длительность болезни: ";
cin >> db->dlit;
// добавляем в список
if (last != NULL) // если список уже существует
{
db->prev = last;
db->next = NULL;
last->next = db;
last = db;
}
else // если список ещё не создан
{
db->prev = NULL;
db->next = NULL;
first = db;
last = db;
};
}
void DeleteItem (void)
{
// выводим список всех структур
int i = List ();
int num;
cout << "Введите номер удаляемой записи ";
cin >> num;
if (num < 1 || num > i) return;
base *db = first;
// находим указатель на удаляемую структуру
for (i = 1; i < num; i++)
{
db = db->next;
}
// удаляем её
if (db)
{
if (db->prev) db->prev->next = db->next;
if (db->next) db->next->prev = db->prev;
if (db == first) first = first->next;
if (db == last) last = last->prev;
delete db;
};
}
void Input (void)
{
bool enough = false;
do
{
AddItem (); // заполняем очередную структуру
cout << "Продолжить ввод информации? (y/n)" << endl;
if (getch () == 'n') enough = true;
}
while (!enough);
}
void Find (void)
{
base *db = first;
char name[20]=" ";
int i=0;
cout<<"Введите название болезни :";
cin>>name;
cout << "Результаты поиска:" << endl;
while (db)
{
if (!strcmp(db->bolezn,name)) // проверяем запись
{
cout << db->fio << " "
<< db->bolezn << " "
<< db->dlit << endl;
i++;
}
db = db->next; // переходим к следующей записи
}
if (i==0)cout<<"Поиск не дал результата";
}
int List (void)
{
base *db = first;
int i = 0;
cout << endl << "В списке содержатся:" << endl;
while (db)
{
i++;
cout << i << ". " << db->fio << " " << db->bolezn << " " << db->dlit << endl;
db = db->next;
}
return i;
}
int Menu (void)
{
char ch = 0;
// Выводим список возможных вариантов выбора
cout << "Ваш выбор:" << endl;
cout << "1. Сформировать список" << endl;
cout << "2. Печать списка" << endl;
cout << "3. Добавить в список" << endl;
cout << "4. Удалить из списка" << endl;
cout << "5. Поиск в списке" << endl;
cout << "6. Выход" << endl;
// ожидаем нажатия правильной клавиши
while (ch < '1' || ch > '6')
{
ch = getch ();
}
// осуществляем выбор согласно набраной клавише
switch (ch)
{
case '1': Input (); break;
case '2': List (); break;
case '3': AddItem (); break;
case '4': DeleteItem (); break;
case '5': Find (); break;
case '6': return 0;
};
return 1;
}
int main (void)
{
while (Menu ()); // цикл,пока пользователь не выбрал Выход
return 0;
}1)Список циклический,никогда не бывает пустым:
C++:
первая вставка: head->next = head;
вставка t после x: t->next=x->next; x->next=t;
удаление после x: x->next=x->next->next
цикл обхода: t=head;
do {... t=t>next;}
while (t!=head);
проверка на наличие лишь одного элемента: if (head->next==head)
C++:
инициализация: head=0;
вставка t после x: if (x==0) {head=t; head->next=0;}
else {t->next=x->next;x->next=t;}
Удаление после x: t=x->next; x->next=t->next;
цикл обхода: for (t=head;t!=0;t=t->next)
Проверка на пустоту: if (head=0)
C++:
инициализация: head=new node;
head->next=0;
вставка t после x: t->next=x->next;x->next=t;
удаление после x: t=x->next;x->next=t->next
цикл обхода: for(t=head->next;t!=0;t=t->next)
проверка на пустоту: if(head->next=0)