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

[demonhunterus]

Доброго времени суток, ув. форумчане.
Прошу вашей помощи в решении одной задачи.
Необходимо программу, обрабатывающую двусвязные списки, настроить для работы с односвязными списками.
Листинг программы:

Код:

#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;
}

Мои попытки перевести хотя бы функцицию ввода не увенчались никакими успехами.

Код:

  if (first == NULL) 
  { first=db;
    first->next=NULL;
    
  }
  else              
  {
   db->next=last->next;
   last->next=db;
  };
}

Ткните носом, как это дело хоть примерно должно выглядеть

[Finch]

Ты пишеш на С++ или на другом языке? Если на С++, так полностью используй его возможности. ООП поможет разгребсти некоторые залежи.
Ну и второй вопрос, чем отличается двухсвязанный список от односвязанного. И кстати, зачем ты пытаешся закольцевать список причем в последнем элементе? У тебя получается, что при добавлении каждый элемент будет закольцован с последним. При начальной иницилизации списка не происходит иницилизации last. Следовательно при следуюшем добавлении элемента, просто произойдет крах программы. Отсюда делаем вывод, что верхний кусок кода честно скомуниздин.

[lapulya]

Offtopic:

скоммунизжен! Плохо русский язык учил ))))))))

Поставлю в угол.

[demonhunterus]

Finch, C++.Да,код я всего лишь переделал под свое задание,а сами реализации ф-ций добавления,удаления оставил без изменений.
По поводу

Ну и второй вопрос, чем отличается двухсвязанный список от односвязанного. И кстати, зачем ты пытаешся закольцевать список причем в последнем элементе? У тебя получается, что при добавлении каждый элемент будет закольцован с последним. При начальной иницилизации списка не происходит иницилизации last. Следовательно при следуюшем добавлении элемента, просто произойдет крах программы

:нашел 3 соглашения,на основе которых можно реализовать односвязный список:
1)Список циклический,никогда не бывает пустым:

первая вставка: 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-указатель завершающего узла

инициализация: 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-указатель завершающего узла

инициализация: 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)

Что в этом есть t,а что x для верхнего кода - так и не разобрался.Попытался что-то намудрить на основе второго соглашения - не получилось.(Я так понял,что base *first = NULL; --- это то же самое,что head=0.t и x - не могу понять что.t-это db или x-это db.И если t-это db,то что есть x.Вот в чем,собственно,проблема)
По поводу использовать все возможности - в приницпе эту прогу нужно было делать через шаблон класса List.Но,к сожалению,от преподавателя,ведущего практику,ничего узнать нового нельзя,на лекции теория,в итоге,чтоб остаться на стипендии приходится выкрчиваться как только можно.

[RXL]

demonhunterus, полагаю, что для выбора необходимо знать назначение списка и характер его использования.

[demonhunterus]

Назначение: На основе списка,в котором содержится информация о заболеваемости сотрудников(Ф.И.О.,заболевание,длительность болезни) сформировать список сотрудников,которые перенесли одно и то же заболевание.

[Finch]

Давай откинем на время теорию. Займемся чуть чуть рисованием. Нарисуй на листе три квадратика. Напиши в верхнем левом углу каждого квадратика Элемент1, Элемент2 и Элемент3 соответственно для каждого квадратика
Под надписью проведи черту и затем напиши next. Проведи стрелку от next квадратика с названием Элемент1 к Квадратику с названием Элемент2 ну и соответственно также для пары Элемент2 - Элемент3. Над квадратиком Элемент1 напиши first и проведи стрелку к Элемент1 и соответственно для last для своего квадратика.
Вот у тебя получился односвязанный не кольцевой список. Теперь попробуй сам самостоятельно дорисовать в конец этого списка Элемент4. И опиши в топик,  какие тебе нужно будет провести действия для такой вставки..

[RXL]

demonhunterus, и какой тут характер использования данных списка? Сказанное тобой пока не характеризует его.

Например:
1. Очередь (FIFO, буфер): вставка в начало, выборка в конец. Закольцовка не нужна, но будет полезен указатель на последний элемент очереди.
2. Стек: вставка и выборка с одного конца. Закольцовка не нужна.
3. Список с доступом (а также добавлением и выборкой) к началу и концу. Аналогичен FIFO.
4. Список с произвольным доступом. Закольцовка не нужна, но полезна группировка элементов или индексация, чтобы поиск был быстрее полного перебора.

[demonhunterus]

Finch, Если я всё правильно понял,то будет примерно так:
Элемент 3 последний.Значит "Элемент 3-> next = NULL; Элемент 3 = Last"
Вставка Элемент 4 в конец списка: "Элемент 3->next = Элемент 4; Элемент 4 = Last".
Так?
RXL, Не понял этого немного...Ну,судя по тому,что вставка производится в конец списка,очередь не подходит.И удаление элемента произвольное(удаление по номеру записи в базе данных).Видимо,список с произвольным доступом - это характер моего списка.

[Finch]

Нет не правильно, есть логическая ошибка. Причем довольно грубая.

Кстати  в односвязанном и также двухсвязанном списке нет произвольного доступа в принципе.

[demonhunterus]

Finch, "Элемент 3 = Last; last->next=NULL","Элемент 4 = Last; last->next=NULL"?

[Finch]

Подсказка: В С/С++ да впрочем во всех языках, с которыми я работал левая часть выражения это элемент, кому происходит присвоение результата вычислений правой части.

[demonhunterus]

Совсем запутался.
first=db; first->next=NULL; --- так должна выглядеть первая вставка,на сколько я понял.
last=db;last->next=NULL; --- вставка последующих элеметов что-то в этом роде,только вот если так написать,то будет оставаться всего лишь один последний введеный элемент списка.

[Finch]

Ну ладно, не буду больше мучать Ты почти дошел до истины
Для первого элемента в свиске.
db->next=NULL;
first=db;
last=db;
Для последующей вставки.
db->next=NULL;
last->next=db;
last=db;

[demonhunterus]

db->next=NULL;
first=db;
last=db;
-----Не совсем понял.Сначала мы указали,что ссылка текующего элемента на следующий никуда не ведет.Потом присвоили текущему элементу звание Первый и он же Последний.А наоборот не получится?Сначала присвоить первый-последний элементу текущему,а потом показать,что ссылка никуда не ведет?То же самое во втором случае.

[Finch]

Когда ты вставляеш в пустой список. У тебя всего один элемент. Он одновременно и первый и последний.
Когда ты вставляеш в хвост списка. То last это указатель на хвост. Следовательно, элемент на который он в данный момент ссылается, должен ссылаться уже на вставляемый новый элемент, и хвост должен уже указывать на этот новый элемент.

[demonhunterus]

Всё.Со вставкой разобрался.Благодарю.Теперь попробую сам разобраться с удалением(методом квадратиков)

Добавлено через 23 часа, 32 минуты и 10 секунд:
Мои попытки разобраться с удалением,увы,не увенчались успехом.
На сколько я понял,если мы удаляем первый элемент списка,то это будет выглядеть так:
first=first->next.
А что делать,если удаляем последний элемент?
В двусвязном списке это будет иметь вид:
last=last->prev, но в односвязном списке нет указателя prev....И как указать без него на предыдущий элемент?
И что делать если удаляем элемент из середины списка(т.е. db=db->next (случая db=db->prev,я так понимаю,у нас для односвязного списка не будет))?
(Выводы сделаны на основе когда,приведенного ниже,для двусвязного списка)

Код:

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;
  };
}

Добавлено через 4 дня, 1 час, 12 минут и 2 секунды:
Up =(

[Finch]

Не заметил темы У тебя такой подход не подойдет Тебе в цикле сначало нужно найти предыдушего соседа. А потом уже удалять элемент из списка. Кстати не забывай про оператор delete, иначе твой элемент будет потерян. Для маленькой программы это ничего не значит. Но в больших программах это будет вызывать проблему. Поэтому надо сразу учитьсч подчишать за собой.

У тебя возможны три варианта удаления из списка. Подумай какие Есть правда еше один вариант

[demonhunterus]

cout << "Введите номер удаляемой записи ";
  cin >> num;
  if (num < 1 || num > i) return;

  base *db = first;
  // находим указатель на удаляемую структуру
  for (i = 1; i < num; i++)
  {
    db = db->next;
  }

В этом цикле,я так понял,нужно,чтобы был найден предыдущий сосед?Или не тут копать?

Кстати не забывай про оператор delete, иначе твой элемент будет потерян. Для маленькой программы это ничего не значит. Но в больших программах это будет вызывать проблему. Поэтому надо сразу учитьсч подчишать за собой.

Т.е. примерно так?

if (db)
  {
    if (db == first) first = first->next;
    delete db;
  };

Варианты - это строчки типа "if (db == first) first = first->next;" или сам цикл+if?

Добавлено через 48 минут и 29 секунд:
Как-то так?

base *db = first, *t;
  for (i = 1; i < num-1; i++)
  {
    db = db->next;
  }
  if(i==1){
      first=db->next;
      delete db;
      }
  else{
     t=db->next;
     db->next=t->next;
     delete t;
  }
 }

[Finch]

Хоть и против правил форума. Вот тебе готовое решение. Я его не отлаживал. Так что могут быть ошибки.

Код:

void DeleteItem (void)
{
  // выводим список всех структур
  int i = List ();
  int num;

  cout << "Введите номер удаляемой записи ";
  cin >> num;
  if (num < 1 || num > i) return;

  base *db = first;
  // находим указатель на удаляемую структуру
 
 base *prev=NULL;
 int i=1;
 while ((i != num) && (db)) {
 	prev=db;
 	db=db->next;
 	i++;
 }
 if (db) {
 	if (prev) prev->next = db->next;
 	else first=db->next;
 	if (db == last) last=prev;
 	delete db;
 }
}

[demonhunterus]

Что-то не работает.

Код:

int i=1;

---ругается на эту строку.Мол,выше уже присвоили i значение

Код:

int i = List ();

.Если строчку 1=1 удалить,то: при попытке удалить последний элемент удаляется предпоследний,при попытке удалить первый элемент ничего не удаляется,при попытке удалить любой элемент(кроме последнего) также ничего не происходит.

Код:

base *db = first, *t;
  for (i = 1; i < num-1; i++)
  {
    db = db->next;
  }
  if(i==1){
      first=db->next;
      delete db;
      }
  else{
     t=db->next;
     db->next=t->next;
     delete t;
  }
 }

--- в этой реализации,которую я написал выше,работает все,кроме одного:
когда остается 2 элемента - первый и последний,и мы попытаемся удалить последний - удалится первый А так всё было бы красиво...

[Finch]

Я поэтому и сказал, что возможны ошибки. Я лично никогда не использую i как переменную для хранения размера массива. Обычно count или size или len   у меня приучены для этих целей. А i у меня всегда работает как индекс. Твой код не верен логически после оператора else.

[demonhunterus]

Твой код не верен логически после оператора else.

--- глупый вопрос,но все же...А почему?Чего-то не хватает?Или что-то лишнее?Сужу только по тому,что это дело работает,за исключением ситации,когда остаются всего 2 элемента...

[Finch]

demonhunterus,  Ты введи список на экран, гдето на 7 элементов. Затем удали например 3 элемент и сравни список до и после удаления Поймеш о чем я говорю.

[demonhunterus]

Вывел.Удалил.То же самое сделал с десятью элементами.Удаляет все верно. о_О И нумерует верно.

[Finch]

Да, нет вру. Сейчас просмотрел твой код еше раз. Тебе надо начинать с 0 а не 1 при обходе цикла. Ты же ишеш предыдуший элемент. И кстати как-то разрулить эту ситуацию. вначале.

[demonhunterus]

Тебе надо начинать с 0 а не 1 при обходе цикла

--- Так?

Код:

for (i = 0; i < num-1; i++)

Если да - то не работает.Удаляет вообще непонятно что и как.

И кстати как-то разрулить эту ситуацию. вначале.

--- вначале - это где?

[Finch]

Код:

base *db = NULL, *t;
  for (i = 0; i < num-1; i++)
  {
    if (db) db = db->next;
    else db=first;
  }
  if(db){
     t=db->next;
     if (t) db->next=t->next;
     else last=db;
     delete t;
      }
  else{
  	  db=first;
      first=db->next;
      if (db == last) last=first;
      delete db;
  }
 }

Добавлено через 33 секунды:
Подправил код.

[demonhunterus]

Хух...Не думал,что всё будет так сложно.
Только вот не совсем понял смысл...

Код:

{
    if (db) db = db->next;
    else db=first;
  }

--- если в цикле натыкаемся на узел,то переходим на следующий,в противном случае переходим на первый7Так что ли?

Код:

if(db){
     t=db->next;
     if (t) db->next=t->next;
     else last=db;

--- и вот тут то же самое.Не совсем понимаю.Если натыкаемся на узел,то присваеваем t значение db->next.Если натыкамся на t,то ... Так?

[Finch]

Для первого узла, у тебя не сушествует предыдуших узлов. Поэтому в самом начале я и написал base *db = NULL.
А во втором случае я сам себя перехитрил Нужно наверно не так.

Код:

    t=db->next;
     db->next=t->next;
     if (t==last) last=db;