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

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

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

Автор: Notreg 24.11.2007, 10:09

Поиск юзал ниче конкретного.

Мне, значит, требуется оформить структуру данных ввиде динамического списка.
Я не догоняю чем будет отличаться обычная структура struct от динамического списка(в смысле по оформлению), в этом вся проблема. Компилятор borland c 3.1

Автор: bsa 24.11.2007, 11:40

Цитата(Notreg @ 24.11.2007, 10:09)

Сначала объясни, что ты понимаешь под динамическим списком.
Есть динамический массив - массив, количество элементов которого неизвестно на этапе компиляции (в общем случае) и может меняться во время выполнения программы. Преимущества - константное время доступа к любому элементу.
Есть односвязный список - это список, доступ к каждому элементу которого осуществляется перебором всех предыдущих элементов. Преимущества - постоянная скорость добавления/удаления элементов.
Есть двусвязный список - отличается от односвязного тем, что перебор можно осуществлять не только сначала, но и с конца списка (каждый элемент содержит указатель не предыдущий и последующий).

Так который тебе нужен?

Автор: Notreg 24.11.2007, 12:01

односвязный, явно односвязный

Автор: bsa 24.11.2007, 13:23

тогда тебе нужно написать класс контейнер элемента (в данном случае типа int):

Код

struct Container
{
       int m_data;
       Container *m_next;
};

Затем тебе надо написать для этого контейнера управляющий класс (который знает где находится первый элемент и предоставляет возможность работы с элементами - итерацию, поиск, доступ и пр.)
Почитай http://www.sgi.com/tech/stl/Slist.html - оно тебе немного подскажет куда двигаться.

Автор: Notreg 24.11.2007, 18:28

а тупо через указатели никак не замутить??

Автор: bsa 24.11.2007, 19:18

Цитата(Notreg @ 24.11.2007, 18:28)

а тупо через указатели никак не замутить??

Что значит "тупо через указатели"? Тебе нужно хранить сами данные и ссылку на следующий объект - тупее не придумаешь!

Автор: Notreg 25.11.2007, 12:03

Код


struct Container
{
       int m_data;
       Container *m_next;
};

Где здесь хранятся данные и где здесь следующий объект??

Автор: bsa 25.11.2007, 12:18

У тебя с английским очень плохо?
m_data - это сами данные (в частности для примера типа int)
m_next - это указатель на следующий элемент контейнера.

Автор: Notreg 25.11.2007, 12:26

Напиши терь как мне забить этот список мож тогда пойму

Автор: bsa 25.11.2007, 12:31

Из того, что я уже написал вполне можно догадаться о способе заполнения списка - достаточно знать азы C++ (даже азов Си достаточно).

Судя по всему, ты хочешь получить готовое решение. Это тогда в раздел http://forum.vingrad.ru/forum/Vingrad-help-center.html

Автор: Notreg 25.11.2007, 15:43

Зачем мне готовое достаточно просто логику понять, я не могу догнать где начинается динамический список, и как им управлять. В той информации которую ты дал есть все если знаешь. Мож знаешь где написано то что ты говоришь

Автор: bsa 25.11.2007, 16:58

Я тебе дал описание контейнера - "обертки" над данными (элемент списка, если хочешь). Список - это набор таких взаимосвязанных контейнеров. Соответственно, список будет выглядеть в виде одного единственного указателя (если у тебя язык С++, то еще можно методы присобачить) на первый контейнер, если он есть, или на 0 в противном случае. Когда тебе надо добавить элемент в список, ты выделяешь память под еще один контейнер, присваиваешь его полю m_next значение 0, а полю m_next последнего элемента списка (если он есть, конечно, иначе указателю на первый элемент списка) указатель на только что созданный контейнер...

Автор: Notreg 25.11.2007, 19:45

Автор: JackYF 25.11.2007, 19:50

Notreg, тебе уже его выдали несколько постов назад.

Автор: intel 25.11.2007, 22:51

Код


#include<iostream>

    class Data {
        private:
            int number;
            Data *next;
        public:
            Data(int);
            Data *GetNext();
            void SetNext(Data*);
            void ShowNumber();
    };
    Data::Data(int n) {
        number = n;
        next = NULL;
    }
    void Data::ShowNumber() {
        std::cout<<number<<std::endl;
        return;
    }
    Data* Data::GetNext() {
        return ( next );
    }
    void Data::SetNext(Data *n) {
        next = n;
        return;
    }
//-----------------------------------------------
    class LinkedList {
        private:
            Data *head;
            Data *last;
        public:
            LinkedList();
            void Insert(Data*);
            void ShowAllElements();
    };
    LinkedList::LinkedList() {
        head = NULL;
        last = NULL;
    }
    void LinkedList::Insert(Data* d) {
        if( head == NULL ) {
            head = d;
            last = d;
        }
        else {
            last->SetNext(d);
            last = d;
        }
        return;
    }
    void LinkedList::ShowAllElements() {
        if( head != NULL ) {
            Data *tmp = head;
            while( tmp != NULL ) {
                tmp->ShowNumber();
                tmp = tmp->GetNext();
            }
        }
        return;
    }

int main()
{
    LinkedList *list = new LinkedList();

    Data *d1 = new Data(10);
    Data *d2 = new Data(20);
    Data *d3 = new Data(30);

    list->Insert(d1);
    list->Insert(d2);
    list->Insert(d3);

    list->ShowAllElements();

    getchar();

    return 0;
}

...всё элементарно smile

Автор: Notreg 2.12.2007, 19:20

Код


Я тебе дал описание контейнера - "обертки" над данными (элемент списка, если хочешь). Список - это набор таких взаимосвязанных контейнеров. Соответственно, список будет выглядеть в виде одного единственного указателя (если у тебя язык С++, то еще можно методы присобачить) на первый контейнер, если он есть, или на 0 в противном случае. Когда тебе надо добавить элемент в список, ты выделяешь память под еще один контейнер, присваиваешь его полю m_next значение 0, а полю m_next последнего элемента списка (если он есть, конечно, иначе указателю на первый элемент списка) указатель на только что созданный контейнер...

Можно ли поменять в таком варианте первый и последний элемент, используя поля связи?? Если можно черкани пару строчек кода!!

Автор: bsa 3.12.2007, 13:50

А в чем проблема? Находишь первый и предпоследний элементы списка. После этого у последнего элемента (предпоследний->next) в поле next подставляет значение поля next первого, в поле next предпоследнего подставляешь указатель на первый элемент, поле next бывшего уже первого обнуляешь.