Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Динамические списки, Структура данных ввиде динамосписка 
:(
    Опции темы
Notreg
Дата 24.11.2007, 10:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 10.1.2007

Репутация: нет
Всего: нет



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

Мне, значит, требуется оформить структуру данных ввиде динамического списка.
Я не догоняю чем будет отличаться обычная структура struct от динамического списка(в смысле по оформлению), в этом вся проблема. Компилятор borland c 3.1
--------------------
Надежна лишь смерть, жизнь - нет.
PM MAIL   Вверх
bsa
Дата 24.11.2007, 11:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196



Цитата(Notreg @ 24.11.2007,  10:09)
Поиск юзал ниче конкретного.

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

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

Так который тебе нужен?
PM   Вверх
Notreg
Дата 24.11.2007, 12:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 10.1.2007

Репутация: нет
Всего: нет



односвязный, явно односвязный
--------------------
Надежна лишь смерть, жизнь - нет.
PM MAIL   Вверх
bsa
Дата 24.11.2007, 13:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196



тогда тебе нужно написать класс контейнер элемента (в данном случае типа int):
Код
struct Container
{
       int m_data;
       Container *m_next;
};
Затем тебе надо написать для этого контейнера управляющий класс (который знает где находится первый элемент и предоставляет возможность работы с элементами - итерацию, поиск, доступ и пр.)
Почитай описание slist в STL - оно тебе немного подскажет куда двигаться.
PM   Вверх
Notreg
Дата 24.11.2007, 18:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 10.1.2007

Репутация: нет
Всего: нет



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

--------------------
Надежна лишь смерть, жизнь - нет.
PM MAIL   Вверх
bsa
Дата 24.11.2007, 19:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196



Цитата(Notreg @ 24.11.2007,  18:28)
а тупо через указатели никак не замутить??

Что значит "тупо через указатели"? Тебе нужно хранить сами данные и ссылку на следующий объект - тупее не придумаешь!
PM   Вверх
Notreg
Дата 25.11.2007, 12:03 (ссылка)    | (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 10.1.2007

Репутация: нет
Всего: нет



Код

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


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

Это сообщение отредактировал(а) Notreg - 25.11.2007, 12:21
--------------------
Надежна лишь смерть, жизнь - нет.
PM MAIL   Вверх
bsa
Дата 25.11.2007, 12:18 (ссылка) |   (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196



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

PM   Вверх
Notreg
Дата 25.11.2007, 12:26 (ссылка)    | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 10.1.2007

Репутация: нет
Всего: нет



Напиши терь как мне забить этот список мож тогда пойму
--------------------
Надежна лишь смерть, жизнь - нет.
PM MAIL   Вверх
bsa
Дата 25.11.2007, 12:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196



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

Судя по всему, ты хочешь получить готовое решение. Это тогда в раздел Центр помощи
PM   Вверх
Notreg
Дата 25.11.2007, 15:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 10.1.2007

Репутация: нет
Всего: нет



Зачем мне готовое достаточно просто логику понять, я не могу догнать где начинается динамический список, и как им управлять. В той информации которую ты дал есть все если знаешь. Мож знаешь где написано то что ты говоришь 
--------------------
Надежна лишь смерть, жизнь - нет.
PM MAIL   Вверх
bsa
Дата 25.11.2007, 16:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196



Я тебе дал описание контейнера - "обертки" над данными (элемент списка, если хочешь). Список - это набор таких взаимосвязанных контейнеров. Соответственно, список будет выглядеть в виде одного единственного указателя (если у тебя язык С++, то еще можно методы присобачить) на первый контейнер, если он есть, или на 0 в противном случае. Когда тебе надо добавить элемент в список, ты выделяешь память под еще один контейнер, присваиваешь его полю m_next значение 0, а полю m_next последнего элемента списка (если он есть, конечно, иначе указателю на первый элемент списка) указатель на только что созданный контейнер...
PM   Вверх
Notreg
Дата 25.11.2007, 19:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 10.1.2007

Репутация: нет
Всего: нет



 smile 
--------------------
Надежна лишь смерть, жизнь - нет.
PM MAIL   Вверх
JackYF
Дата 25.11.2007, 19:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


полуавантюрист
****


Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162



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


--------------------
Пожаловаться на меня как модератора можно здесь.
PM MAIL Jabber   Вверх
intel
Дата 25.11.2007, 22:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 46
Регистрация: 5.7.2007

Репутация: нет
Всего: нет



Код

#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 
PM MAIL   Вверх
Notreg
Дата 2.12.2007, 19:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 124
Регистрация: 10.1.2007

Репутация: нет
Всего: нет



Код

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


Можно ли поменять в таком варианте первый и последний элемент, используя поля связи?? Если можно черкани пару строчек кода!!
--------------------
Надежна лишь смерть, жизнь - нет.
PM MAIL   Вверх
bsa
Дата 3.12.2007, 13:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196



А в чем проблема? Находишь первый и предпоследний элементы списка. После этого у последнего элемента (предпоследний->next) в поле next подставляет значение поля next первого, в поле next предпоследнего подставляешь указатель на первый элемент, поле next бывшего уже первого обнуляешь.
PM   Вверх
Страницы: (2) [Все] 1 2 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »


 




[ Время генерации скрипта: 0.0562 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.