Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [C++] Круговой список -> 2 линейных списка


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

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

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

Код

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

?

Автор: zim22 31.5.2009, 10:08
Цитата(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); // заполнили кольцевой список

Автор: Master_ 31.5.2009, 10:25
А можно поподробнее объяснить?

Код

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

Ставит значение текущее или слудеющее?
Не совсем понятно: node *n = 0 и new node(i, t);

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

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

Автор: Master_ 31.5.2009, 12:39
Понятно...
Только вот не понимаю еще: в каком виде хранить списки в файле? Просто значение на строку? 

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

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

Так?

Автор: zim22 31.5.2009, 12:51
Цитата(Master_ @  31.5.2009,  12:39 Найти цитируемый пост)
Так?

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

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

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

Автор: Master_ 31.5.2009, 13:48
Такая проблема, все время попадает в первое условие (см ниже в ф=ии 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;
}

Автор: zim22 31.5.2009, 14:10
Цитата(Master_ @  31.5.2009,  13:48 Найти цитируемый пост)
Такая проблема, все время попадает в первое условие

Код

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

Автор: Master_ 31.5.2009, 14:30
Да уж.. А как же его разделять на два линейных?

Пополам чтоли делить?

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

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

Автор: Master_ 31.5.2009, 14:39
Например пополам.
Как сделать?
Считаем количество элементов и делим пополам, а потом перемещаем? В новые списки?

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

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

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

Автор: Master_ 31.5.2009, 15:16
Понятно, что примерно такое: 
Код

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

Он то до от начала до конца проходит, и в конце дебагер выдает ошибку, на последнем элементе..
Надо по другому, но как - додуматься не могу..

Автор: zim22 31.5.2009, 15:39
Цитата(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?showtopic=261438&view=findpost&p=1883230

Автор: Master_ 31.5.2009, 16:03
Нашел у себя ошибку. При чтении из файла не дописал в конец 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

Автор: zim22 31.5.2009, 17:05
Цитата(Master_ @  31.5.2009,  16:03 Найти цитируемый пост)
Подкините идейку?

первую половину списка в один список новый вставьте
вторую половину списка в другой новый список вставьте

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)