помогите начинающему в с ++

вобщем есть такое задание:
Создать класс для реализации односвязного списка. В списке новые узлы добавляются в любое место из списка и удаляются также из любого места. Класс должен содержать методы добавления узлов в начало, в конец списка и перед заданным, удаление узла из начала, конца и перед заданным, а также просмотр списка.

для добавления в конец списка и удаления из начала списка я сделал следующие функции:

#include "snode.h"
void SOrder::Add(int inf)
{
SNode *r,*nn;
// создание нового узла
nn=new SNode;
nn->info=inf;
// Поиск последнего узла

if(head)
{
r=head;
while(r->next) r=r->next;
// добавление нового узла в конец очереди
r->next=nn;
}
else
head=nn;
}
// реализация метода Del()
void SOrder::Del()
{
SNode *r;
if(head) // если очередь не пустая
{
// запоминаем бывшую вершину
r=head;
// Определение новой вершины
head=r->next;
//удаление бывшей вершины
delete r;
}
}
_______________
snode.h

#include <iostream.h>

class SNode
{
public:
// info - информационная часть узла
int info;
// next указатель на следующий узел в очереди
SNode *next;
//Конструктор
SNode(){ info=0; next=0;}
};

class SOrder
{
// head - указатель на начало очереди
SNode *head;
public:
//Конструктор
SOrder(){head=0;}
//Добавление нового узла c информационной часть inf
void Add(int inf);
// Удаление узла из начала очереди
void Del();
// деструктор удаляет все узлы
~SOrder() { while(head) Del(); }
};

-----------------------------------------
а вот как мне теперь реализовать
методы добавления узлов в начало и перед заданным, удаление узла из конца и перед заданным?

перед заданным:

void SOrder::AddBefore(int inf,int order) //order - порядковый номер каким ставить
{
SNode *r,*nn;
// создание нового узла
nn=new SNode;
nn->info=inf;
// Поиск последнего узла
 
if(head)
{
r=head;
while(r->next && order){
   r=r->next;
   order--;
 }
//save связи
nn->next=r->next;
// добавление нового узла в конец очереди
r->next=nn;
}
else
head=nn;
}

Добавлено в 12.02.04, 08:11:
да, порядковый номер начинается с 0

Добавлено в 12.02.04, 08:16:

 
void SOrder::DelBefore(int order) //order - порядковый номер
{
SNode *nn;
if(head)
{
r=head;
while(r->next && order){
   nn=r;
   r=r->next;
   order--;
 }
//save связи
nn->next=r->next;
delete r;
}
}  

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

 
struct ListNode
{
ListNode* m_Next;
int m_Info;
};
 
class List
{
public:
List() : m_Head(NULL), m_Tail(NULL) {;}
~List() {Clear();}
private:
ListNode* m_Head;
ListNode* m_Tail;
};

Вообще говоря, все варианты операций добавления и удаления можно свести к одному - добавление/удаления перед заданным элементом. При этом предпологается, что элемент задан указателем. Договоримся, что если в качестве указателя задан NULL - то добавляем в хвост списка. На примере операции добавления элемента:

 
class List
{
public:
//...
//...
void AddItem(ListNode* beforeNode, int item)
{
ListNode* node = new ListNode;
node->m_Info = item;
node->m_Next = beforeNode;
// Обрабатываем вариант, если список пуст
if (m_Tail == NULL)
{
   m_Head = m_Tail = node;
   node->m_Next = NULL;
   return;
}
// Добавляем в хвост
if (beforeNode == NULL)
{
   m_Tail->m_Next = node;
   m_Tail = node;
   return;
}
// Добавляем в голову
if (beforeNode == m_Head)
{
   m_Head = node;
   return;
}
// Добавляем в середину
// Вообще говоря, для односвязного списка эта операция будет занимать линейное время
ListNode* pred = FindPred(beforeNode);
// Случай, если заданный узел не принадлежит этому списку
if (pred == NULL)
   return;
 
pred->m_Next = node;
return;
}
void AddAtTail(int item) {AddItem(NULL, item);}
void AddAtHead(int item) {AddItem(m_Head, item);}
//...
};

Операции удаления делаются аналогичным образом. Только нужно следить за тем, чтобы аккуратно расцеплять список.
Как явствует из приведенного примера - операции добавления/удаления в середину односвязного списка занимают линейное время. Но иначе (AFAIK) не сделаешь.

Lavrik, в общем случае понятия "список" и "индексирование" не совместимы. Т. е. для списка обычно не определяется операция индексации по той простой причине, что работает она линейное время. Таким образом, в операциях со списком лучше использовать указатели на узлы (итераторы), нежели индексы.

Сообщение отредактировано: Flex_Ferrum - 12.02.04, 08:31

Flex_Ferrum,
тогда может быть еще и придется делать методы ВПЕРЕД, НАЗАД по списку, чтобы потом указатели то передавать на вставку\удаление, иначе где юзер возьмет адрес узла который он допустим хочет удалить?

Цитата

Lavrik, 12.02.04, 12:54
тогда может быть еще и придется делать методы ВПЕРЕД, НАЗАД по списку, чтобы потом указатели то передавать на вставку\удаление, иначе где юзер возьмет адрес узла который он допустим хочет удалить?

Может и придется. А еще - метод, выполняющий поиск заданного элемента в списке. Кстати, для данного случая потребуется только метод "ВПЕРЕД", т. к. список односвязный.

всем спасибо за ответы - пойду переваривать ))

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

процедура добавления требует небольших корректировок, и вообще полезно возвращать указатель на добавленный эл.

// Добавляем в голову
if (beforeNode == m_Head)
{
  if( m_Head )node->m_Next = m_Head->m_Next; // надо не потерять цепочку
 
   m_Head = node;
   return node;
}

Цитата Lavrik @ 12.02.04, 11:08

if(head)
{
r=head;
while(r->next && order){
r=r->next;
order--;
}

а для чего order-- ?

Цитата

Sazabis, 12.02.04, 15:14
if( m_Head )node->m_Next = m_Head->m_Next; // надо не потерять цепочку

Ты уверен? ИМХО, ты таким образом "потеряешь" текущий головной элемент.

Цитата

Guest, 12.02.04, 15:23
а для чего order-- ?

когда order станет = 0 while кончится.
также когда r->next будет = NULL

Цитата

Flex_Ferrum, 12.02.04, 15:24
Цитата
Sazabis, 12.02.04, 15:14
if( m_Head )node->m_Next = m_Head->m_Next; // надо не потерять цепочку

Ты уверен? ИМХО, ты таким образом "потеряешь" текущий головной элемент.

(node = 0x500)

Head = 0x100
Head->m_next = 0x200
Head->m_next->m_next = 0x300

при записи

  m_Head = node;
  return;

Head = 0x500
Head->m_next = NULL (если в конструкторе ListNode next обнуляется, если нет то вообще неизвестно куда)

при записи

if( m_Head )node->m_Next = m_Head

->m_Next лишний написал!!

node->next = 0x100
Head = 0x100
Head->next = 0x200

теперь уже можно

  m_Head = node;
  

m_Head = 0x500
m_Head->m_next = 0x100
m_Head->m_next->m_next = 0x200

Сообщение отредактировано: Sazabis - 12.02.04, 12:38

Теперь смотри, что у меня было написано:

Цитата

Flex_Ferrum, 12.02.04, 11:26
void AddItem(ListNode* beforeNode, int item)
{
ListNode* node = new ListNode;
node->m_Info = item;
node->m_Next = beforeNode;

//...
//...

// Добавляем в голову
if (beforeNode == m_Head)
{
m_Head = node;
return;
}

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