demonhunterus
Интересующийся
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
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #1 : 24-10-2010 08:31 » |
|
Ты пишеш на С++ или на другом языке? Если на С++, так полностью используй его возможности. ООП поможет разгребсти некоторые залежи. Ну и второй вопрос, чем отличается двухсвязанный список от односвязанного. И кстати, зачем ты пытаешся закольцевать список причем в последнем элементе? У тебя получается, что при добавлении каждый элемент будет закольцован с последним. При начальной иницилизации списка не происходит иницилизации last. Следовательно при следуюшем добавлении элемента, просто произойдет крах программы. Отсюда делаем вывод, что верхний кусок кода честно скомуниздин.
|
|
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
lapulya
Молодой специалист
Offline
|
|
« Ответ #2 : 24-10-2010 09:03 » |
|
Offtopic: скоммунизжен! Плохо русский язык учил ))))))))
Поставлю в угол.
|
|
« Последнее редактирование: 24-10-2010 09:28 от Finch »
|
Записан
|
С уважением Lapulya
|
|
|
demonhunterus
Интересующийся
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
Пол:
|
|
« Ответ #4 : 24-10-2010 12:48 » |
|
demonhunterus, полагаю, что для выбора необходимо знать назначение списка и характер его использования.
|
|
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
demonhunterus
Интересующийся
Offline
|
|
« Ответ #5 : 24-10-2010 12:52 » |
|
Назначение: На основе списка,в котором содержится информация о заболеваемости сотрудников(Ф.И.О.,заболевание,длительность болезни) сформировать список сотрудников,которые перенесли одно и то же заболевание.
|
|
|
Записан
|
|
|
|
Finch
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #6 : 24-10-2010 13:12 » |
|
Давай откинем на время теорию. Займемся чуть чуть рисованием. Нарисуй на листе три квадратика. Напиши в верхнем левом углу каждого квадратика Элемент1, Элемент2 и Элемент3 соответственно для каждого квадратика Под надписью проведи черту и затем напиши next. Проведи стрелку от next квадратика с названием Элемент1 к Квадратику с названием Элемент2 ну и соответственно также для пары Элемент2 - Элемент3. Над квадратиком Элемент1 напиши first и проведи стрелку к Элемент1 и соответственно для last для своего квадратика. Вот у тебя получился односвязанный не кольцевой список. Теперь попробуй сам самостоятельно дорисовать в конец этого списка Элемент4. И опиши в топик, какие тебе нужно будет провести действия для такой вставки..
|
|
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
RXL
Технический
Администратор
Offline
Пол:
|
|
« Ответ #7 : 24-10-2010 13:14 » |
|
demonhunterus, и какой тут характер использования данных списка? Сказанное тобой пока не характеризует его.
Например: 1. Очередь (FIFO, буфер): вставка в начало, выборка в конец. Закольцовка не нужна, но будет полезен указатель на последний элемент очереди. 2. Стек: вставка и выборка с одного конца. Закольцовка не нужна. 3. Список с доступом (а также добавлением и выборкой) к началу и концу. Аналогичен FIFO. 4. Список с произвольным доступом. Закольцовка не нужна, но полезна группировка элементов или индексация, чтобы поиск был быстрее полного перебора.
|
|
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
demonhunterus
Интересующийся
Offline
|
|
« Ответ #8 : 24-10-2010 13:29 » |
|
Finch, Если я всё правильно понял,то будет примерно так: Элемент 3 последний.Значит "Элемент 3-> next = NULL; Элемент 3 = Last" Вставка Элемент 4 в конец списка: "Элемент 3->next = Элемент 4; Элемент 4 = Last". Так? RXL, Не понял этого немного...Ну,судя по тому,что вставка производится в конец списка,очередь не подходит.И удаление элемента произвольное(удаление по номеру записи в базе данных).Видимо,список с произвольным доступом - это характер моего списка.
|
|
|
Записан
|
|
|
|
Finch
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #9 : 24-10-2010 13:31 » |
|
Нет не правильно, есть логическая ошибка. Причем довольно грубая.
Кстати в односвязанном и также двухсвязанном списке нет произвольного доступа в принципе.
|
|
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
demonhunterus
Интересующийся
Offline
|
|
« Ответ #10 : 24-10-2010 13:32 » |
|
Finch, "Элемент 3 = Last; last->next=NULL","Элемент 4 = Last; last->next=NULL"?
|
|
|
Записан
|
|
|
|
Finch
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #11 : 24-10-2010 13:37 » |
|
Подсказка: В С/С++ да впрочем во всех языках, с которыми я работал левая часть выражения это элемент, кому происходит присвоение результата вычислений правой части.
|
|
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
demonhunterus
Интересующийся
Offline
|
|
« Ответ #12 : 24-10-2010 13:47 » |
|
Совсем запутался. first=db; first->next=NULL; --- так должна выглядеть первая вставка,на сколько я понял. last=db;last->next=NULL; --- вставка последующих элеметов что-то в этом роде,только вот если так написать,то будет оставаться всего лишь один последний введеный элемент списка.
|
|
|
Записан
|
|
|
|
Finch
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #13 : 24-10-2010 13:54 » |
|
Ну ладно, не буду больше мучать Ты почти дошел до истины Для первого элемента в свиске. db->next=NULL; first=db; last=db; Для последующей вставки. db->next=NULL; last->next=db; last=db;
|
|
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
demonhunterus
Интересующийся
Offline
|
|
« Ответ #14 : 24-10-2010 14:04 » |
|
db->next=NULL; first=db; last=db; -----Не совсем понял.Сначала мы указали,что ссылка текующего элемента на следующий никуда не ведет.Потом присвоили текущему элементу звание Первый и он же Последний.А наоборот не получится?Сначала присвоить первый-последний элементу текущему,а потом показать,что ссылка никуда не ведет?То же самое во втором случае.
|
|
|
Записан
|
|
|
|
Finch
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #15 : 24-10-2010 14:15 » |
|
Когда ты вставляеш в пустой список. У тебя всего один элемент. Он одновременно и первый и последний. Когда ты вставляеш в хвост списка. То last это указатель на хвост. Следовательно, элемент на который он в данный момент ссылается, должен ссылаться уже на вставляемый новый элемент, и хвост должен уже указывать на этот новый элемент.
|
|
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
demonhunterus
Интересующийся
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
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #17 : 29-10-2010 15:27 » |
|
Не заметил темы У тебя такой подход не подойдет Тебе в цикле сначало нужно найти предыдушего соседа. А потом уже удалять элемент из списка. Кстати не забывай про оператор delete, иначе твой элемент будет потерян. Для маленькой программы это ничего не значит. Но в больших программах это будет вызывать проблему. Поэтому надо сразу учитьсч подчишать за собой. У тебя возможны три варианта удаления из списка. Подумай какие Есть правда еше один вариант
|
|
« Последнее редактирование: 29-10-2010 15:29 от Finch »
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
demonhunterus
Интересующийся
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
Спокойный
Администратор
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
Интересующийся
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
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #21 : 29-10-2010 17:40 » |
|
Я поэтому и сказал, что возможны ошибки. Я лично никогда не использую i как переменную для хранения размера массива. Обычно count или size или len у меня приучены для этих целей. А i у меня всегда работает как индекс. Твой код не верен логически после оператора else.
|
|
« Последнее редактирование: 29-10-2010 17:43 от Finch »
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
demonhunterus
Интересующийся
Offline
|
|
« Ответ #22 : 29-10-2010 17:56 » |
|
Твой код не верен логически после оператора else. --- глупый вопрос,но все же...А почему?Чего-то не хватает?Или что-то лишнее?Сужу только по тому,что это дело работает,за исключением ситации,когда остаются всего 2 элемента...
|
|
|
Записан
|
|
|
|
Finch
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #23 : 29-10-2010 18:00 » |
|
demonhunterus, Ты введи список на экран, гдето на 7 элементов. Затем удали например 3 элемент и сравни список до и после удаления Поймеш о чем я говорю.
|
|
« Последнее редактирование: 29-10-2010 18:02 от Finch »
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
demonhunterus
Интересующийся
Offline
|
|
« Ответ #24 : 29-10-2010 18:04 » |
|
Вывел.Удалил.То же самое сделал с десятью элементами.Удаляет все верно. о_О И нумерует верно.
|
|
|
Записан
|
|
|
|
Finch
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #25 : 29-10-2010 18:07 » |
|
Да, нет вру. Сейчас просмотрел твой код еше раз. Тебе надо начинать с 0 а не 1 при обходе цикла. Ты же ишеш предыдуший элемент. И кстати как-то разрулить эту ситуацию. вначале.
|
|
« Последнее редактирование: 29-10-2010 18:09 от Finch »
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
demonhunterus
Интересующийся
Offline
|
|
« Ответ #26 : 29-10-2010 18:14 » |
|
Тебе надо начинать с 0 а не 1 при обходе цикла --- Так? for (i = 0; i < num-1; i++) Если да - то не работает.Удаляет вообще непонятно что и как. И кстати как-то разрулить эту ситуацию. вначале. --- вначале - это где?
|
|
|
Записан
|
|
|
|
Finch
Спокойный
Администратор
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
Интересующийся
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
Спокойный
Администратор
Offline
Пол:
Пролетал мимо
|
|
« Ответ #29 : 29-10-2010 18:38 » |
|
Для первого узла, у тебя не сушествует предыдуших узлов. Поэтому в самом начале я и написал base *db = NULL. А во втором случае я сам себя перехитрил Нужно наверно не так. t=db->next; db->next=t->next; if (t==last) last=db;
|
|
|
Записан
|
Не будите спашяго дракона. Джаффар (Коша)
|
|
|
|