Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Вставка узла в список по индексу

Автор: knut 16.1.2007, 11:03

Добрый день.
У меня такой вопрос.
Как вставить узел в список по индексу?

Код


void Add_Node(int position,cList value, cList *node){//???}

Автор: _hunter 16.1.2007, 11:16

нихт не понял. вставить куда? что это за функция? проблема в чем?

Автор: Daevaorn 16.1.2007, 11:17

Пробегать от начала списка и считать элементы, когда встретишь нужный номер - вставляй новый

Автор: knut 16.1.2007, 11:23

Цитата

нихт не понял. вставить куда?

вставить надо в список.

Автор: zkv 16.1.2007, 11:25

по крайней мере надо знать что такое cList

Автор: knut 16.1.2007, 11:31

Цитата

по крайней мере надо знать что такое cList

не понял а что это значит?

Автор: zkv 16.1.2007, 11:36

Цитата(knut @ 16.1.2007, 11:31

)

не понял а что это значит?

объявление класса cList надо, ты показал, что тебе нужна функция

Цитата(knut @ 16.1.2007, 11:03

)

void Add_Node(int position,cList value, cList *node){//???}

но чтобы ее реализовать, надо знать что из себя представляет cList

Автор: _hunter 16.1.2007, 11:38

Цитата(knut @ 16.1.2007, 11:23

)

вставить надо в список.

что это за список (его организация)

Цитата(knut @ 16.1.2007, 11:31

)

не понял а что это значит?

это значит что нужно знать что такое cList (судя по названию это самоклепный класс). так же это значит что кроме автора класса (и возможно справки) этого никто не знает: например в моем самоклепном классе bList вставка узла по индексу осуществляется функцией Delete(void).
и я так и не понял проблемы: функцию для втавки ты знаеш, ее параметры тоже. что мешает ее использовать?

Автор: knut 16.1.2007, 11:52

Код


class cList
{
public:
    typedef struct Node
    {
        int val;
        Node *prev;
        Node *next;
    }*NODE;
private:
    Node head,tail;
public:
    cList();
    ~clist();
public:
    void Add_Begin(cList var);
    void Add_End(cList var);
    void Add(int position,cList var);
};

Add_Begin(cList var) and Add_End(cList var) писать не буду (не кого не удевлю я этим) а вот теперь как собственно реализовать Add(int position,cList var)
т.е вставка в список по индексу

Автор: _hunter 16.1.2007, 12:35

ааа... т.е. тебя алгоритм интересует? -- так бы сразу и говорил...
делается это очень легко -- проходиш последовательно по всем елементам (начиная с первого) и увеличиваеш счетчик. когда он == индексу (или индексу+-1 (зависит от реализации)) делаеш:
-- запоминаеш куда-нить следующий елемент
-- перекидываеш его (текущего елемента) *next на вставляемый елемент
-- вставляемому ставиш *prev на текущий елемент
-- запомненому "следующему" ставиш *prev на вставляемый елемент
-- вставляемому елементу ставиш *next на запомненый "следующий"
все...

Автор: knut 18.1.2007, 15:46

что за проблемма не пойму делаю так вдоди все должно работать smile

Код


void cList::Add_By_Index(int ipos, int var){

    cList::ndd *root = head;
    while (root->next != NULL || ipos != index){        
        root = root->next;
        index++;
    }
    if(root->next){
    cList::ndd* Add_object = new cList::ndd; 
    Add_object = var;
    temp = root;
    root->next->prev = Add_object;
    Add_object->prev = temp->prev;
    Add_object->next = temp;
    index++;
    }
    else{
        Add_End(int var); 
    }

Автор: zkv 18.1.2007, 16:57

а index это что такое, где сбрасывается, и зачем в конце увеличивается?

что то страшное здесь происходит

Цитата(knut @ 18.1.2007, 15:46

)

   root->next->prev = Add_object;
    Add_object->prev = temp->prev;
    Add_object->next = temp;

что типа этого должно быть наверное:

Код


Add_object->next = temp->next;
Add_object->prev = temp;
temp->next->prev = Add_object;
temp->next = Add_object;

Автор: knut 18.1.2007, 18:52

zkv, а что не так в коде?

Автор: zkv 18.1.2007, 20:01

Цитата(knut @ 18.1.2007, 18:52

)

zkv, а что не так в коде?

ну давайте посмотрим,
судя по этой строчке:
root->next->prev = Add_object;
я понял, что вы хотите вставить Add_object в список после root
объект с адресом root условно назовем A, Add_object - B, а root->next - С. требуется выстроить их в цепочку A-B-C.

Что имеем сейчас (состояние объектов на 11 строке вашего кода):

Цитата(Состояние 1)

A.next указывает на C
A.prev указывает куда то куда и надо, менять не нужно

B.next указывает в никуда
B.prev указывает в никуда

C.next указывает куда то куда и надо, менять не нужно
C.prev указывает на A

после строки root->next->prev = Add_object; (root->next соответствует C, помните мы договорились smile

те C.prev теперь указывает на Add_object, те на B) описываем состояние:

Цитата(Состояние 2)

далее строка Add_object->prev = temp->prev; Так, здесь была моя ладья smile

,
temp == root (судя по 11 строке вашего кода) что в свою очередь соответствует A,
Add_object соответствует B получаем:

Цитата(Состояние 3)

A.next указывает на C
A.prev указывает куда то куда и надо, менять не нужно

B.next указывает в никуда
B.prev указывает туда куда должен указывать A.prev

C.next указывает куда то куда и надо, менять не нужно
C.prev указывает на B

ну и завершаем выстраивание строкой Add_object->next = temp; те B.next указывает на A. Смотрим:

Цитата(Состояние 4)

A.next указывает на C
A.prev указывает куда то куда и надо, менять не нужно

B.next указывает на A
B.prev указывает туда куда должен указывать A.prev

C.next указывает куда то куда и надо, менять не нужно
C.prev указывает на B

а хотелось бы получить:

Цитата(Желаемый результат)

A.next указывает на B
A.prev указывает куда то куда и надо, менять не нужно

B.next указывает на C
B.prev указывает на A

C.next указывает куда то куда и надо, менять не нужно
C.prev указывает на B

Видите разницу, приведенный мною код я уж не буду комментировать, посмотрите сами, что происходит.
Удачи!