Развернуть однонаправленный список

@Акелла · Регистрация: 10.05.2009

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

т.е. как я понял либо уже у текущего списка ссылки "развернуть" наоборот, либо создать такой же и скопировать в него значения первого с конца.

проблема вот в чем. теоретически я понимаю все. и про списки знаю. практически - не работал еще с ними ни разу.

мне готовая прога не нужна, просто кто то может накидать что то похожее на работающее с функциями построения списка и добавления в него элементов.

предположим что его структура проста:

C++

struct list
{
   int i;
   struct list *next;
} info;

@Deiron · 11.06.2009, 02:03

C++

//базовый класс узла
class Node
{
    public:
        Node(){};
        virtual ~Node(){};
        virtual Node * Insert (int& iVal)=0;
        virtual void Show()=0;
    private:
} ;
//внутренний узел
class InternalNode: public Node
{
    public:
        InternalNode(int iVal,Node* n);
        ~InternalNode() {delete next;delete data;};
        virtual Node * Insert (int& iVal);
        virtual void Show(){cout<<*data<<endl; next->Show();};
    private:
        int* data;
        Node * next;
};
InternalNode::InternalNode (int iVal,Node* n)
{
    data = new int;
    *data = iVal;
    next=n;
} 
//посылаем элемент дальше, пока он не наткнется на TailNode
Node* InternalNode::Insert (int& iVal)
{
    next=next->Insert(iVal);
    return this;
}
//"концевой" элемент. Не пускает дальше себя
class TailNode:public Node
{
    public:
        TailNode(){};
        ~TailNode(){};
        virtual Node* Insert(int& iVal);
        virtual void Show() {};
    private:
};
Node* TailNode:: Insert(int& iVal)
{
    Node* temp;
    temp = new InternalNode (iVal,this);
    return temp;
}
//головной элемент. При добавлении элемента посылает его дальше по списку.
class HeadNode:public Node
{
    public:
        HeadNode();
        ~HeadNode() {delete next;};
        virtual Node * Insert (int& iVal);
        virtual void Show() {next->Show();};
    private:
        Node* next;
};
HeadNode::HeadNode()
{
    next=new TailNode;
}
Node* HeadNode::Insert(int& iVal)
{
    next= next->Insert(iVal);
    return this;
}
//сам список
class ListFwd 
{
    public:
        ListFwd();
        ~ListFwd() {delete head;};
        void Insert (int iVal);
        void ShowAll() {head->Show();};
    private:
        HeadNode* head;
};
ListFwd::ListFwd()
{
    head=new HeadNode;
}
void ListFwd::Insert(int iVal)
{
    head->Insert(iVal);
}

Вот полностью работающий однонаправленный список.
Есть два пути решения твоей задачи. 1: "отгрызать" по одному элементу в новый список. 2. создать двунаправленный список, в который запихать все элементы однонаправленного, а затем, просматривая двунаправленный список с конца пихаем его эл-ты в однонаправленный список.

@Gravity · 11.06.2009, 02:16

Можно проще - всего лишь перенаправить ссылки.

C

List *reverse(List *lp)
{
    List *cur, *prev, *tmp;
 
    prev = NULL;
    for(cur = lp; cur != NULL; prev = cur, cur = tmp) {
        tmp = cur->next;
        cur->next = prev;
    }
    return prev;
}

Опции темы