PDA

View Full Version : Задача със свързани списъци на C



Fena
06-14-2007, 19:19
Здравейте, имам една задача за свързани списъци която ме мъчи. Ето я:


Дадени са указатели Х и T към възли от кръгов списък; напишете кодов фрагмент, който премества възела, следващ Т, към позиция, следваща възела, който следва Х в списъка.

Не искам да ми пишете самата програма, но ако има някои с идеи покрай алгоритъма й, ще се радвам да ги сподели с мен :roll: Нещо не ги чаткам много тези свързани списъци :?

06-15-2007, 22:28
Здравейте, имам една задача за свързани списъци която ме мъчи. Ето я:


Дадени са указатели Х и T към възли от кръгов списък; напишете кодов фрагмент, който премества възела, следващ Т, към позиция, следваща възела, който следва Х в списъка.

Не искам да ми пишете самата програма, но ако има някои с идеи покрай алгоритъма й, ще се радвам да ги сподели с мен :roll: Нещо не ги чаткам много тези свързани списъци :?
може би нещо такова


// List.h
// Dev C++

template <typename Object>
class List
{ private:
class Node
{ public:
Object info;
Node* next;
Node(const Object x = Object())
: info(x), next(NULL) { }
};

typedef Node* NodePtr;

NodePtr first, last;

public:
List(){ first = last = NULL; }

List(const List & L)
{ first = last = NULL;
NodePtr p=L.first;
while(p!=NULL)
{ push_back(p->info);
p = p->next;
}
}

List& operator=(const List &L)
{ if(this != &L)
{ clear();
NodePtr p=L.first;
while(p!=NULL)
{ push_back(p->info);
p = p->next;
}
}
return *this;
}

~List() { clear(); }

bool empty() const
{ return first==NULL; }



void push_front(const Object & x)
{ NodePtr p = new Node(x);
if(first==NULL) first = last = p;
else
{ p->next = first;
first = p;
}
}

void push_back(const Object & x)
{ NodePtr p = new Node(x);
if(first==NULL) first = last = p;
else last = last->next = p;
}

Object & front()
{ if(first!=NULL) return first->info; }

Object & back()
{ if(last!=NULL) return last->info; }

void pop_front()
{ if(first!=NULL)
{ first = first->next;
if(first==NULL) last=NULL;
}
}

void pop_back()
{ if(first==NULL) return;
if(first==last)
{ pop_front(); return; }

NodePtr p=first;
NodePtr q=p->next;;
while(q!=last)
{ p = q; q = p->next; }
delete last;
last = p;
last->next = NULL;
}

void clear()
{ while(first!=NULL) pop_front(); }

/* тук са останалите методи които са ти необходими
например метод за сортиране, за сливане на списъци, от и към файл и т.н.
. . .
. . .
*/

void MoveNode(NodePtr, NodePtr);
};

// --------------------------------------

template <typename Object>
void List<Object>::MoveNode(NodePtr T, NodePtr X)
{
NodePtr p = T->next;
NodePtr q = X->next;

T = p->next;
X->next = p;
p->next = q;
}
не съм го тествал този код, но когато се поосвободя ще седна да го дообмисля. Преди време си правих собствени реализации на почти всички основни структури от данни, но скоро не съм се занимавал.
Тъй като не е упоменат език, реших да използвам C++ като това е част от реализацията на едносвързан списък. Разгледай метода MoveNode(NodePtr T, NodePtr X) мисля, че това ти трябва, останалото е бонус O:)

Успех!