Виж пълна версия : Помощ по информатика
SyncMstr
03.06.07 г., 15:24
Здравейте! Молбата ми е да помогнете със задача по информатика, че ми е голяма мъка :(
Ето и условието:
Даден е свързан списък. Напишете функция, която обръща елементите на списъка.
Благодаря предварително на всички отзовали се! :wink: :)
#include <list>
int main()
{
std::list<int> list;
// ...
list.reverse();
}:o
artanis
03.06.07 г., 15:53
Защо ли си мисля, че не са имали предвид STL ...
Иначе, SyncMstr, защо не седнеш да почетеш малко. Те домашните не ги дават, щото не знаят как става, а за да се научиш ТИ...
Защо ли си мисля, че не са имали предвид STL ...
Хвърлях боб. Юнакът не е казал дори за какъв език става дума. Мога и на APL (http://en.wikipedia.org/wiki/APL_%28programming_language%29) да му го напиша (обаче няма).
SyncMstr
03.06.07 г., 16:01
Благодаря много. Аз и аз се сетих за stl, но ни изискват да напишем ние функцията не да използваме наготово. :)
За С++ става въпрос :)
При двойно-свързан списък алгоритъмът за обръщане е елементарен. Трябва да направиш две неща - да размениш begin и end указателите, и за всеки елемент да размениш previous и next указателите.
anrieff
03.06.07 г., 16:40
Покрай СЕП-а, Логическото Програмиране и другите рекурсивно-тачещи гадости ми идва наум следното много елегантно решение за едносвързан списък...
List reverse(List l) {
if (l.empty()) return l;
ListElement le = l.extractFirstElement();
List temp = reverse(l);
temp.addToBack(le);
return temp;
}
Остава само да се напишат класа List с голямата 4-ка, отделно методите extractFirstElement, addToBack и empty и си готов :ghi:
List reverse(List l) {
if (l.empty()) return l;
ListElement le = l.extractFirstElement();
List temp = reverse(l);
temp.addToBack(le);
return temp;
}
Доста неефективно решение. Сложността му е квадратична - копираш целия списък при всяко рекурсивно извикване. Точно от теб очаквам повече :)
Е сега, anrieff е забравил едно & и вече ще го изядеш :p
Иначе в случая и простата итерация си е екстра... Виж ако не трябва да ползва допълнителна памет става по-интересно :)
Е сега, anrieff е забравил едно & и вече ще го изядеш :p
Не е само &-то :) При връщането на стойността също има копиране (освен ако компилатора не приложи NRVO, на което не може да се разчита при сложни структури).
Ето как горе-долу бих го направил аз в рекурсивен вариант:
template <class T>
struct ListNode
{
T data;
ListNode<T> *next;
};
template <class T>
ListNode<T> *reverse(ListNode<T> *node, ListNode<T> *previous)
{
if (!node) return previous;
ListNode<T> *first = reverse(node->next, node);
node->next = previous;
return first;
}
За да обърнем списъка, викаме reverse() с първи параметър началото на списъка, и втори параметър NULL.
anrieff
04.06.07 г., 00:27
Pesho, на тези училищни задачи никога не искат добра сложност. Мен ме кефи само колко е елегантно, не друго..
А за сложността, имаше един много весел случай, на един приятел бяха дали да напише "най-къс път в граф между два върха". Аз му я написах, като представих графа с матрица на съседство и приложихме обикновена Дийкстра (О(N^2)) сложност. Писаха му 2. Искали да се напише с пълно изчерпване (О(N!))... :bow:
artanis
04.06.07 г., 02:58
lol, къде се е случило това?
anrieff
04.06.07 г., 11:58
ПМГ Стара Загора, разбира се, не при Mr. PF. - по онова време нямаше други свестни даскали по Информатика (сиреч, останалите бяха бивши даскали по Математика, гдето една реална програма не са написали и преподават 1:1 от учебника... а защо в учебника са решили, че пълното изчерпване е по-добро решение от Дийкстрата, остава една голяма тайна за мен).
Всъщност, да живее елегантността, ето и линейно решение:
List reverse(List l) {
List temp;
while (! l.empty()) {
ListElement le = l.extractFirstElement();
temp.addToFront(le);
}
return temp;
}
...по онова време нямаше други свестни даскали по Информатика (сиреч, останалите бяха бивши даскали по Математика, гдето една реална програма не са написали и преподават 1:1 от учебника...
Повярвай ми, сега не е много по-различно... :rolleyes:
Авторски права на vBulletin