Двусвязный в односвязный список

  • Автор темы Demonhunterus1
  • Дата начала
D

Demonhunterus1

#1
Добрый день.Столкнулся с такого вот рода проблемой: необходимо переделать код программы,обрабатывающей двусвязный список,для работы с односвязными списками.Как ни пытался - ничего толком не получилось.Сам листинг программы:
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)
2)Ведущий указатель,null-указатель завершающего узла
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)
3)Фиктивный ведущий узел,null-указатель завершающего узла
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)
Буду благодарен за любую помощь.
 
D

Demonhunterus1

#2
Попытался что-то типа такого сделать,по второму соглашению для ввода,но после ввода 2х элементов - вылет програмы.
C++:
 if (first == NULL) 
{ first=db;
first->next=NULL;

}
else			 
{
db->next=last->next;
last->next=db;
};
}
 

DarkKnight

Well-known member
01.08.2010
653
0
#3
Код твой почти не правил, просто немного адаптировал
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;
base *lastdel = NULL;
// находим указатель на удаляемую структуру
for (i = 1; i < num; i++)
{	
lastdel = db;
db = db->next;
}

// удаляем её
if (db)
{
if (db->next) //Удаление внутри списка
{
if (db == first) //Удаление первого элемента
{
first = db->next;
} 
else //Если элемент не первый
{
lastdel->next = db->next;
}
}
else //Удаление в конце списка либо единственного элемента
{
if (db == first) //Удаление первого элемента
{
first = NULL;
last = NULL;
} 		
else
{
lastdel->next = NULL;
last = lastdel;
}
}

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)
{
setlocale(LC_ALL,"Russian");	

while (Menu ()); // цикл,пока пользователь не выбрал Выход
return 0;
}