Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2  Все   Вниз
  Печать  
Автор Тема: Из двусвязного в односвязный список  (Прочитано 31724 раз)
0 Пользователей и 1 Гость смотрят эту тему.
demonhunterus
Интересующийся

ua
Offline Offline

« : 24-10-2010 08:19 » 

Доброго времени суток, ув. форумчане.
Прошу вашей помощи в решении одной задачи.
Необходимо программу, обрабатывающую двусвязные списки, настроить для работы с односвязными списками.
Листинг программы:
Код:
#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;
  };
}
Ткните носом, как это дело хоть примерно должно выглядеть
« Последнее редактирование: 01-11-2010 09:59 от Sel » Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #1 : 24-10-2010 08:31 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
lapulya
Молодой специалист

ru
Offline Offline

« Ответ #2 : 24-10-2010 09:03 » 

Offtopic:

скоммунизжен! Плохо русский язык учил ))))))))
Поставлю в угол.
« Последнее редактирование: 24-10-2010 09:28 от Finch » Записан

С уважением Lapulya
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #3 : 24-10-2010 11:01 » 

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
Технический
Администратор

Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 24-10-2010 12:48 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #5 : 24-10-2010 12:52 » 

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

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #6 : 24-10-2010 13:12 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
RXL
Технический
Администратор

Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 24-10-2010 13:14 » 

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

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #8 : 24-10-2010 13:29 » 

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

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #9 : 24-10-2010 13:31 » 

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

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

Не будите спашяго дракона.
             Джаффар (Коша)
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #10 : 24-10-2010 13:32 » 

Finch, "Элемент 3 = Last; last->next=NULL","Элемент 4 = Last; last->next=NULL"?
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #11 : 24-10-2010 13:37 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #12 : 24-10-2010 13:47 » 

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

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #13 : 24-10-2010 13:54 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #14 : 24-10-2010 14:04 » 

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

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #15 : 24-10-2010 14:15 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #16 : 24-10-2010 14:37 » 

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

Добавлено через 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 =(
« Последнее редактирование: 29-10-2010 15:21 от demonhunterus » Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #17 : 29-10-2010 15:27 » 

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

У тебя возможны три варианта удаления из списка. Подумай какие Улыбаюсь Есть правда еше один вариант Улыбаюсь
« Последнее редактирование: 29-10-2010 15:29 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #18 : 29-10-2010 15:46 » 

Цитата
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;
  }
 }
« Последнее редактирование: 29-10-2010 16:35 от demonhunterus » Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #19 : 29-10-2010 16:52 » 

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

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
Интересующийся

ua
Offline Offline

« Ответ #20 : 29-10-2010 17:34 » 

Что-то не работает.
Код:
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
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #21 : 29-10-2010 17:40 » 

Я поэтому и сказал, что возможны ошибки. Я лично никогда не использую i как переменную для хранения размера массива. Обычно count или size или len  Улыбаюсь у меня приучены для этих целей. А i у меня всегда работает как индекс. Твой код не верен логически после оператора else.
« Последнее редактирование: 29-10-2010 17:43 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #22 : 29-10-2010 17:56 » 

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

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #23 : 29-10-2010 18:00 » 

demonhunterus,  Ты введи список на экран, гдето на 7 элементов. Затем удали например 3 элемент и сравни список до и после удаления Улыбаюсь Поймеш о чем я говорю.
« Последнее редактирование: 29-10-2010 18:02 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #24 : 29-10-2010 18:04 » 

Вывел.Удалил.То же самое сделал с десятью элементами.Удаляет все верно. о_О И нумерует верно.
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #25 : 29-10-2010 18:07 » new

Да, нет вру. Сейчас просмотрел твой код еше раз. Тебе надо начинать с 0 а не 1 при обходе цикла. Ты же ишеш предыдуший элемент. И кстати как-то разрулить эту ситуацию. вначале.
« Последнее редактирование: 29-10-2010 18:09 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #26 : 29-10-2010 18:14 » 

Цитата
Тебе надо начинать с 0 а не 1 при обходе цикла
--- Так?
Код:
for (i = 0; i < num-1; i++)
Если да - то не работает.Удаляет вообще непонятно что и как.
Цитата
И кстати как-то разрулить эту ситуацию. вначале.
--- вначале - это где?
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #27 : 29-10-2010 18:20 » 

Код:
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 секунды:
Подправил код.
« Последнее редактирование: 29-10-2010 18:24 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
demonhunterus
Интересующийся

ua
Offline Offline

« Ответ #28 : 29-10-2010 18:31 » 

Хух...Не думал,что всё будет так сложно.
Только вот не совсем понял смысл...
Код:
{
    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
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #29 : 29-10-2010 18:38 » 

Для первого узла, у тебя не сушествует предыдуших узлов. Поэтому в самом начале я и написал base *db = NULL.
А во втором случае я сам себя перехитрил Улыбаюсь Нужно наверно не так.
Код:
    t=db->next;
     db->next=t->next;
     if (t==last) last=db;
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Страниц: [1] 2  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines