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

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C++] Круговой список -> 2 линейных списка 
:(
    Опции темы
Master_
Дата 31.5.2009, 09:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
Цитата
Написать программу, в которой после создания кругового списка, элементы которого вводятся из файла,   происходит обращение к подпрограмме процедуре разбивания кругового списка на два линейных списка.  Данные полученных линейных списков вывести  в текстовый файл.

Как этот круговой список создавать то? Вообще без понятия...

Может у кого есть опыт?

Код

struct student {
    char name[20];
    int  born;
    student *next;
};

?
PM   Вверх
zim22
Дата 31.5.2009, 10:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69
Цитата(Master_ @  31.5.2009,  09:41 Найти цитируемый пост)
Как этот круговой список создавать то? Вообще без понятия...

круговой == кольцевой.
список, в котором последний элемент указывает на первый.
Код

struct node {
int value;
node *next;
node(int v, node *n = 0) : value(v), next(n) { }
};
typedef node *link;

link t = new node(1);
t->next = t; // зациклили первый элемент

link x = t;
for (int i = 2; i < 10; i++)
  x = x->next = new node(i, t); // заполнили кольцевой список


Это сообщение отредактировал(а) zim22 - 31.5.2009, 10:08


--------------------
C++ FAQ Lite
PM MAIL   Вверх
Master_
Дата 31.5.2009, 10:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
А можно поподробнее объяснить?

Код

node(int v, node *n = 0) : value(v), next(n) { }

Ставит значение текущее или слудеющее?
Не совсем понятно: node *n = 0 и new node(i, t);
PM   Вверх
zim22
Дата 31.5.2009, 10:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69
Цитата(Master_ @  31.5.2009,  10:25 Найти цитируемый пост)
А можно поподробнее объяснить?

node *n = 0 - по умолчанию поле next будет равно нулю. если же мы его указываем явно, как в случае  new node(i, t);, то поле next будет равно t.
чтобы лучше понять - возьмите листик, ручку и нарисуйте элементы списка и их взаимодействие.




--------------------
C++ FAQ Lite
PM MAIL   Вверх
Master_
Дата 31.5.2009, 12:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
Понятно...
Только вот не понимаю еще: в каком виде хранить списки в файле? Просто значение на строку? 

А чтобы сделать кольцевой список, после прочтения первого создавать новый список, подобно
Код

если первый элемент из файла{
link t = new node(1);
t->next = t; // зациклили первый элемент
link x = t;
}
иначе
x = x->next = new node(i, t);

Так?

Это сообщение отредактировал(а) Master_ - 31.5.2009, 12:41
PM   Вверх
zim22
Дата 31.5.2009, 12:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69
Цитата(Master_ @  31.5.2009,  12:39 Найти цитируемый пост)
Так?

 smile 
Цитата(Master_ @  31.5.2009,  12:39 Найти цитируемый пост)
Только вот не понимаю еще: в каком виде хранить списки в файле? Просто значение на строку? 

Цитата(Master_ @  31.5.2009,  09:41 Найти цитируемый пост)
Данные полученных линейных списков вывести  в текстовый файл.

вам нужно вывести значения, содержащиеся в списках. формат вывода: любой.



--------------------
C++ FAQ Lite
PM MAIL   Вверх
Master_
Дата 31.5.2009, 13:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
Такая проблема, все время попадает в первое условие (см ниже в ф=ии read_file), то есть постоянно заполняется первый элемент (головной).
Код

struct node {
    int value;
    node *next;
    node(int v=0, node *n = 0) : value(v), next(n) { }
};
typedef node* link;
link head;

void read_file();

int main()
{
    read_file();
    /*
        link head = new node(1);
            head->next = head; // зациклили первый элемент
            link x = head;
            for (int i = 2; i < 10; i++)
                x = x->next = new node(i, head); // заполнили кольцевой список*/        
    return 0;
}
void read_file()
{
    link x;
    ifstream fin("list.txt");
    if ( fin.is_open() )
        while ( !fin.eof() )
        {
            if ( !head )//вот сюда
            { 
                link head = new node;
                fin >> head->value;
                head->next = head; // зациклили первый элемент
                link x = head;
                cout << "head: " << head->value;
            }
            else
            {
                x->next=new node;
                x = x->next;
                fin >> x->value;
                cout << "X: " << x->value << endl;
            }
            
        }
    else cout << "Не удалось открыть файл" << endl;
}
PM   Вверх
zim22
Дата 31.5.2009, 14:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69
Цитата(Master_ @  31.5.2009,  13:48 Найти цитируемый пост)
Такая проблема, все время попадает в первое условие

Код

if ( !head )//вот сюда
{ 
    head = new node;
    fin >> head->value;
    head->next = head; // зациклили первый элемент
    x = head;
    cout << "head: " << head->value;
}



--------------------
C++ FAQ Lite
PM MAIL   Вверх
Master_
Дата 31.5.2009, 14:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
Да уж.. А как же его разделять на два линейных?

Пополам чтоли делить?
PM   Вверх
zim22
Дата 31.5.2009, 14:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69
Цитата(Master_ @  31.5.2009,  14:30 Найти цитируемый пост)
Да уж.. А как же его разделять на два линейных?Пополам чтоли делить?

пополам, или по заданному алгоритму деления. например: все чётные элементы в первый список, все нечётные - во второй.




--------------------
C++ FAQ Lite
PM MAIL   Вверх
Master_
Дата 31.5.2009, 14:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
Например пополам.
Как сделать?
Считаем количество элементов и делим пополам, а потом перемещаем? В новые списки?

И еще, что-то недопонял, как обходить созданный кольцевой список без зацикливаний 1 раз?

Это сообщение отредактировал(а) Master_ - 31.5.2009, 14:40
PM   Вверх
zim22
Дата 31.5.2009, 14:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69
Цитата(Master_ @  31.5.2009,  14:39 Найти цитируемый пост)
И еще, что-то недопонял, как обходить созданный кольцевой список без зацикливаний 1 раз?

храните указатель на начало списка. и если поле next следующий элемент станет равно head - значит список закончился.


--------------------
C++ FAQ Lite
PM MAIL   Вверх
Master_
Дата 31.5.2009, 15:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
Понятно, что примерно такое: 
Код

    x = head;
    while ( x->next != head )
    {
        cout << x->value << ", ";
        x = x->next;
    }

Он то до от начала до конца проходит, и в конце дебагер выдает ошибку, на последнем элементе..
Надо по другому, но как - додуматься не могу..
PM   Вверх
zim22
Дата 31.5.2009, 15:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69
Цитата(Master_ @  31.5.2009,  15:16 Найти цитируемый пост)
Надо по другому, но как - додуматься не могу..

Код

for (link p = t; p->next != t; p = p->next)
  std::cout << p->value << std::endl;

это является продолжением моего кода: http://forum.vingrad.ru/index.php?showtopi...t&p=1883230


--------------------
C++ FAQ Lite
PM MAIL   Вверх
Master_
Дата 31.5.2009, 16:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
Нашел у себя ошибку. При чтении из файла не дописал в конец x->next = head;
Код

            else
            {
                x->next=new node;
                x = x->next;
                fin >> x->value;
                cout << "X: " << x->value << endl;
            }
            x->next = head;

Теперь работает 
Код

for (link p = t; p->next != t; p = p->next)
  std::cout << p->value << std::endl;
Вместо p->next!=t полагаю надо писать p!=t, т.к. последний элемент не будет выводится.

Осталось только разделить список на два линейных. Подкините идейку? smile
PM   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




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


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

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