В университете дали задание сделать двухсвязный линейный список, над которым можно было бы выполнять определенные действия.
Но при этом я не понимаю, что представляет этот тип списка. И что именно должны делать те или иные операции, куда добавлять элементы и т.п.
Преподавателя увы сложно выловить. Вот само задание:
-------
Задание
Реализовать линейный двухсвязный список для хранения следующих данных:
- фамилия,
- год поступления,
-средний балл.
Обеспечить выполнение операций:
- добавление элемента в неупорядоченный список,
- удаление  элемента с заданным полем «фамилия» в неупорядоченном списке,
- сортировка списка по полю «фамилия»,
- добавление и удаление заданного элемента из упорядоченного списка  с поиском «слева» и «справа»,
- распечатка содержимого списка.
-------
То есть должен быть список, его элементы, и связи между элементами. А вот какие связи - это мне неизвестно.
Вот так я начинал делать программу (но это неправильно - нужен другой тип списка).



Поясните, пожалуйста, что от меня хотят. Либо если не сложно, как это реализовать.

Вот пример двунаправленного списка

Спасибо за ответ.
Двунаправленный - это линейный двухсвязный или другой?

Насколько я помню - двунаправленный список, это список, в котором каждый элемент имеет ссылку как на предыдущий так и на следующий элемент, соответственно можно двигаться по списку как в пряммом так и в обратном направлении...

Если воспользуетесь поиском - недавно аналогичная тема достаточно подробно разбиралась с кучей примеров... (правда не помню в этом конкретном форуме или нет), но тема настолько избитая, что поиск должен выдать огромную массу информации.

Я такое и сделал вначале. А мне сказали, что надо по-другому.
Может, кто-нибудь знает наверняка?

p.s. В поиске нашел многое, но не то...

Может тот, кто сказал по-другому и скажет как? Или хотя бы что не так?
Многие преподаватели несколько по-разному подходят к таким вопросам.

Ну не имели же они в виду двунаправленную очередь. 

Их можно отправить читать Кормена и др.

И двухсвязный список сложно понять как-то по иному   

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

Недавно лично видел, как бедолага студент делал свою минисубд в курсовике по теме "Динамическое распределение памяти".

Ну на фига в такой теме заставлять свою СУБД писать?! Человек больше провозился с файловыми операциями чем с заданием по теме...

Ок, чем отличается линейный двухсвязный от простого двухсвязного?
И в задании говорится:

- добавление элемента в неупорядоченный список,
.....
- добавление и удаление заданного элемента из упорядоченного списка  с поиском «слева» и «справа»,

То есть возможно указатели next и prev указывают не так что 1 <-> 2 <-> 3 а по-другому?
1 -> 2 -> 3 -> 4
2 <- 4 <- 1 <- 3

Кто-то писал так:


Отсюда вывод: двусвязный список является частным случаем линейного...
Ромб, он же параллелограмм...

Хотя быть может я и не прав   

Спасибо, понял. То есть код  который я написал в 1 сообщении этой темы, правильно описывает нужный тип списка?

Описывает да, на счет реализации - не смотрел, если честно.

Lesh_od
Неплохо бы проверять длину строки sn в конструкторе прежде, чем копировать иначе можешь память попортить.
Вместо strcpy(surname,"") не проще ли написать surname[0] = '\0' ?
В AddToHead нужно ещё: newvalue->prev=NULL сделать.
Также у тебя там описан неупорядоченный список, т.к. всегда добавляется к голове. В упорядоченном списке тебе следует проходить список вперёд или назад и искать ту позицию в которую нужно добавить элемент.
Кроме того, у тебя не написан деструктор к классу List!
И ещё удаления отдельного элемента из класса List у тебя нет    

Добавлено @ 16:25 
Подписался

Это сообщение отредактировал(а) Arks - 4.12.2006, 16:58

Arks, Спасибо. Да, я знаю, что над программой надо работать и работать. Сейчас займусь этим, и напишу о результатах.

Взял за основу программу человека из другого варианта, и изменил под свой вариант. Все вроде бы ничего, учитывая, что в C++ я ничего не понимаю в указателях. Но почему-то при выполнении выдается ошибка.

Для начала поправь то, на что я тебе в предыдущем посте указал. Особенно в AddToHead - это ведь ведёт к будущим ошибкам.
Касательно, нового кода в проге, могу сказать, что функцию List::DelNum лучше спрятать подальше от глаз людских и никогда не использовать   
Она во-первых, жутко медленная - список от начала и до нужного элемента проходится аж ТРИ РАЗА! Во-вторых, я так понял она должна бы удалять элемент в i-ой позиции, а похоже удаляет в i+1 -ой. Отсюда может и быть ошибка. Чтобы точно узнать, оттрасируй.
В любом случае, эту функцию следует переписать, т.к. ты сейчас работаешь со списком, будто он односвязный. У двусвязного списка перед односвязным преимущество в том, что нам не требуется проходить его когда нужно добавить (если мы знаем после/перед каким эл-м добавлять) или удалить элемент, где-то в середине. Нам достаточно знать адрес элемента для этого.
Т.е. вместо удаления по номеру, нужно написать удаление по адресу:

И ещё, когда работаешь со списками, рисуй наброски на бумаге - здорово поможет избагать ошибок.

Это сообщение отредактировал(а) Arks - 6.12.2006, 07:22

До того, как я прочитал последнее сообщение, я наладил ту программу, которая была. Потом добавил деструктор List и заменил удаление на показанное тобой. Сейчас она выглядит так:



Если все это соответствует заданию, то мне сейчас осталось:
1)- сортировка списка по полю «фамилия»,
2)- добавление и удаление заданного элемента из упорядоченного списка  с поиском «слева» и «справа»

Для сортировки, наверное, имеет смысл выбрать самую простую (пузырьковую) и написать функцию Change (Elem *one, Elem *two).
А что значит 2-ое, то есть работа с упорядоченным списком?

Добавлено @ 08:34 
Нашел в форуме такую сортировку:

Я попытался сделать хотя бы смену элементов, но она не работает. Почему- пока не разобрался, наверное я меняю копии объектов. Вот так это выглядит:








Убирал указатели (то есть swapitem(Elem a,Elem b)) - ничего не дало.

Полный текст программы:


Это сообщение отредактировал(а) lesha_od - 6.12.2006, 09:24

А вот это оччччень зря, друг! Обязательно разберись! Без них какой смысл??

Для начала советую подумать, что случится с указателем ptr после его удаления. Понял? Так вот, а ты его после этого используешь! Если не понял о чём, я можешь глянуть листинг ниже. Там новая правильная версия функции DelElem.

Когда же ты обмениваешь элементы списка между собой в сортировке, то вовсе ненужно физически их содержимое обменивать местами, достаточно просто поменять соответсвующие связи. Разбираться, что у тебя там не так с сортировкой не охото, сам немного подумай ;)
Единственное скажу, что это не лучший метод. Для не очень длинных списков (<20) эффективно будет применять сортировку вставками (InsertSort), а для длинных списков сорт. слияниями (MergeSort).

П.С.: Почитай про указатели. Да же на этом форуме (в этом разделе) кое-что есть.

Про указатели я знаю в общих чертах. Когда долго программируешь на Java, совсем не охота запутываться с ссылками\указателями на C.

Я пробовал и ссылки поменять на элементы. Но по неизвестной мне причине они не меняются местами, хоть убей. Сортировку-то я сделаю, любым способом.


Должно работать?

Неа, не должно.   Ты обмениваешь значения указателей, а не тех элементов на которые они указывают.
Тоже самое, что и в ссылках Java, там таким присваиванием ты обменяешь ссылки, а не сами объекты.
Указатели Си и ссылки Java по сути одно и тоже (попровте меня кто-нибудь, если ошибаюсь), по-крайней мере я не вижу между ними никакой разницы, кроме синтаксиса.
Т.е. тебе нужно так:

В Java ты бы делал это через клонирование.

Но это не эффективно. То что я предлагал, это изменения соответсвующих указателей a->next; a->prev; b->next; b->prev.
Итак, берёшь бумагу. Рисуешь прямоугольники-кирпичи, которые будут обозначать элементы. Рисуешь связи, и смотришь как надо изменить (рисуя эти изменения на бумаге) эти связи. Вперёд и с песней   

Arks,
твой код меняет сами элементы, но не меняет указатели на них соседних элементов... то есть функция Print() выдает то же самое и до, и после обмена.

Тогда я попробовал с указателями.... вроде бы связи правильные, но не работает из-за синтаксиса.





и плюс в эту функцию нужно добавить 

(связи с предыдущими элементами)

Но не работает.

Это сообщение отредактировал(а) lesha_od - 7.12.2006, 09:36

Проверил все рассмотренные варианты.

1) У тебя swapitem, кстати, был совершенно корректно написан ещё в этом посте.
Если ты запустишь сортировку, она должна отработать верно, если ещё где-нибудь не закосячил.
Просто, когда меняешь местами e1 и e2, ты меняешь местами именно их, а не то, что содержится в списке. Посмотри адреса в указателях, они разные. Причина в том, что ты копируешь элементы при добавлении. Если их не копировать, то всё ок:

Правда в этом случае, придётся немного изменить ф-цию main, чтобы не вылетало ошибок (ведь список удаляет свои элементы):


2)Твой вариант, как я и сказал не работает. Вот этот:


3) Мой вариант тоже не катит   
Связи портятся.

4)Вариант и изменением ссылок - самый замутный, но и самый эффективный, особенно если собираешься расширять кол-во информационных полей в будущем.
Ты в принципе понял, что я имел ввиду, но закосячил реализвацию. Вот так верно:

Ещё элементы должны следовать в правильном порядке, т.е. чтобы работало должно быть так:

Спасибо за такой подробный ответ! Я уже начинаю понимать, как эти указатели работают
Программа работает, выполняет требуемое от нее. Единственное, что не работает - если вручную запустить смену элементов, и до или после нее попытаться удалить "хвостовой" элемент с фамилией "ааа", то выдается ошибка.

Update: оказалось, сравнение строк не работает по знаку ">". Видимо, надо сравнивать по-другому.

Вот код работающей программы:


а вот строчки, которые в любом порядке убивают программу:

Попробую сейчас разобраться, почему ошибка. Наверно какой-то указатель мы таки забыли поставить на место.
P.S. А в принципе, это неважно. Программа же должна быть инкаспулированной, и работать с (e3,e2) необязательно. А в остальных случаях она работает, что отлично.

Это сообщение отредактировал(а) lesha_od - 7.12.2006, 14:36

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

то все работает нормально.
А как добавить созданный пользователем элемент? Когда я делаю так:

то программа зависает при распечатке, либо при удалении - в общм, что-то с копиями и объектами не так 

1) Разве p->surname - строка? Это всего лишь указатель на неё. Для строк есть свои функции. В том числе и для сравнения. Ты сравниваешь указатели. Кстати в DelSurname ты ведь нужную ф-цию используешь, а здесь забыл!

2)Ты память портишь, т.к. не создаёшь таким образом новый объект. Надо:

только AddToHead надо перекроить, т.к. сейчас ей параметр передаётся по ссылке, а нам надо по указателю:

Можно и не перекраивать, но имо, так даже правильнее будет.

3)
Таже рожа толька в профиль: смотри про правильный порядок   
А ещё лучше посмотри, что со связями творится в этой функции, после её вызова в отсортированном списке.
Не хочешь париться с порядком. Проверяй в его в функции.

Все отлично заработало, кроме сортировки... я к сожалению не умею нормально отлаживать. Надеюсь, преподаватель сможет помочь с ошибкой.

Как называется функция, проверяющая, является ли введенное значение числом? Скажем я пишу



И мне надо точно знать, что это число. А если не число, то выдать сообщение пользователю.

lesha_od,

i в данном случае всегда будет целым числом со знаком.
А проверять придется флаги у cin.

Вот так:

Я это кстати, где то на этом форуме нашёл.