Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
#1

двунаправленный список. - C++

29.05.2011, 22:49. Просмотров 1559. Ответов 26
Метки нет (Все метки)

Доброго времени суток.
Прощу помочь с заданием которое звучит так :
Построить кольцевой двунаправлений список. Значения элементов считать из файла.
Определить, есть ли в списке хотяб один элемент, который равен элементу , что идет за ним по кругу. Вывести такие элементы. Удалить из списка все элементы у которых одинаковые "соседы"(первый и последний считать соседами).

Смог реализовать сам список и загрузку из файла, но вот как сравнивать текущий и предидущим не понимаю.
Буду рад любой помощи.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include "stdafx.h"
#include "string.h"
#include "stdlib.h"
#include "conio.h"
#include "iostream"
 
using namespace std;
struct Item 
{
char data[50];        
 
Item *next;      
Item *prev;     
 
};
 
Item*head,*current, *last;
char str[50];
int n1, n2;
FILE*file;
 
void add(char* val)
{
    if(head==0)
    {
    head = new Item;
    strcpy(head->data,val);
    head->next=head;
    head->prev=head;    
    last=head;
    }else
    {
    current=new Item;
    strcpy(current->data,val);
    current->prev=last; // пред элем = конец списка
    current->next=head; // след элем = начало списка (замыкание списка 1й этап)
    last->next=current; // у текущего посл элем-та след эл = тот который только что создали
    last=current; // и этот же элемент который создали будет последним т.к добавили в конец
 
    head->prev=last; // замыкание списка (2-ой этап)
    }
}
void show()
{
    current=head;
    cout << endl << "List:" << endl;
    while(current!=head->prev)
    {
    cout << current->data << " ";
    current=current->next;
    }
    cout << endl;
 
}
int main()
{
head = NULL;
last = NULL;
do{
    system("cls");
int key;
    cout<<"1. Read list from file."<<endl;
    cout<<"2. Show list."<<endl;
    cout<<"3. Show same elements"<<endl;
    cout<<"4. Delete same elements."<<endl;
    cout<<"5. Exit."<<endl;
    cout<<"\nChoose menu item: ";
    cin>>key;
        switch(key)
        {
        case 1:{file = fopen("list.txt", "r+"); while(!feof(file))
               {fscanf(file,"%c",&str); add(str);}
               fclose(file);
                cout<<"The list is created!"<<endl; 
                system("pause");break;}
        case 2:{show();system("pause");break;}
        //case 3:{compare();system("pause");break;}
        //case 4:{del();system("pause");break;;
        case 5:{exit(1);}
        default:{cout<<"Error"<<endl;break;}
        }
    }while(1);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2011, 22:49     двунаправленный список.
Посмотрите здесь:

Двунаправленный список - C++
Вот в примере елем в список добавл в конец, а как сдел чтобы они добавл в начало ? void List_2::Insert_end_list_2(int data) { Plist...

Двунаправленный список - C++
Люди, объясните пжлст, что такое двунаправленный список?

Двунаправленный список - C++
Чемпион мира по футболу. Страна, год последней победы, число побед. Сортировка по названию. Вычисление среднего числа титулов всех...

Двунаправленный список - C++
Как в этом списке поменять ввод элементов с ручного на рандомный, помогите пожалуйста? #include &lt;iostream.h&gt; struct tochd { ...

Двунаправленный список - C++
Помогите пожалуйста удалить заданный элемент из двунаправленного списка... Напишите как это делается

Двунаправленный список - C++
Вопросы: Почему ругается при таком описании, говорит ; пропустил spis_fam * Create_first(char *); //формирование первого элемента ...

Двунаправленный список - C++
Вставка элемента в список. Удалениеэлемента из списка Сортировка списка. Поиск элемента в списке.Объединение двух списков Пересечение двух...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
30.05.2011, 01:40     двунаправленный список. #16
Тогда странно. У меня только одно теряется, последнее, как и ожидалось
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
30.05.2011, 01:52  [ТС]     двунаправленный список. #17
Действительно странно.
Без if (feof(file)) break; - теряеться последнее
С if (feof(file)) break; - теряеться 2 последних
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
30.05.2011, 01:55     двунаправленный список. #18
Цитата Сообщение от Stormfire Посмотреть сообщение
Без if (feof(file)) break; - теряеться последнее
Так ведь не терялось же раньше, когда я говорил, что должно теряться
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
30.05.2011, 02:07  [ТС]     двунаправленный список. #19
Цитата Сообщение от grizlik78 Посмотреть сообщение
Так ведь не терялось же раньше, когда я говорил, что должно теряться
Странно. Еще раз проверил:
Без if (feof(file)) break; - нету потерь, при этом последний элемент всегда выводиться в compare()
С if (feof(file)) break; - теряеться 1 последний и при первый=последний не выводит его в compare()
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
30.05.2011, 02:17     двунаправленный список. #20
Да, теперь работает так, как написано в программе. То есть надо бы исправить и show, и compare. Но я на паузу
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
30.05.2011, 12:41  [ТС]     двунаправленный список. #21
Буду ждать Вас, но не откажусь и от другой помощи!
На повестке ночи вопросы:
1)Как исправить то, что функция compare всегда выводит последний элемент списка, при этом никогда не сравнивая первый элемент.
2) Как удалять из списка элементы которые функция compare выводит?
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
30.05.2011, 18:05     двунаправленный список. #22
Итак, мой вариант compare
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int compare()
{
    if (head)
    {
        Item *cur, *prev = head;
        while ((cur = prev->next) != head){ // пока хвост не замкнется
            if (strcmp(cur->data, prev->data) == 0) // проверяем не равны ли у них значения поля дата
                cout << cur->data << endl; // если равны - выводим   
            prev = cur;
        }
        if (strcmp(cur->data, prev->data) == 0) // обработка последнего или единственного элемента
            cout << cur->data << endl;
    }
    return 0;
}
Ну а с удалением что? Там же просто ссылки перед удалением надо наладить с предыдущего на следующий и наоборот. Ну и особый случай обработать, когда на удаляемый элемент указывает head и особенно когда это единственный элемент. Ну, может через некоторое время тоже набросаю.
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
30.05.2011, 22:15  [ТС]     двунаправленный список. #23
Цитата Сообщение от grizlik78 Посмотреть сообщение
Итак, мой вариант compare
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int compare()
{
    if (head)
    {
        Item *cur, *prev = head;
        while ((cur = prev->next) != head){ // пока хвост не замкнется
            if (strcmp(cur->data, prev->data) == 0) // проверяем не равны ли у них значения поля дата
                cout << cur->data << endl; // если равны - выводим   
            prev = cur;
        }
        if (strcmp(cur->data, prev->data) == 0) // обработка последнего или единственного элемента
            cout << cur->data << endl;
    }
    return 0;
}
Ну а с удалением что? Там же просто ссылки перед удалением надо наладить с предыдущего на следующий и наоборот. Ну и особый случай обработать, когда на удаляемый элемент указывает head и особенно когда это единственный элемент. Ну, может через некоторое время тоже набросаю.
Даже так последний элемент выводиться 2жди( или 1 раз с if (feof(file)) break; в main,но в таком случае show не выводит последний элемент), при условии, что последний=первому
А вот ссылки наладить что-то совсем не выходит. битый час пробую
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
30.05.2011, 22:48     двунаправленный список. #24
Вот такие функции у меня нормально работают, вроде.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void show()
{
    current = head;
    cout << endl << "List:" << endl;
    if (head)
    {
        while (current != head->prev)
        {
            cout << current->data << " ";
            current = current->next;
        }
        cout << current->data;
    }
    cout << endl;
}
 
Item* delete_node(Item *node) // удаление узла. возвращает следующий узел
{
    if (node && node->next == node)
    {
        delete node;
        head = node = NULL;
    }
    if (head)
    {
        Item *tmp = node->next;
        if (head == node)
            head = node->next;
        node->next->prev = node->prev;
        node->prev->next = node->next;
        delete node;
        node = tmp;
    }
    return node;
}
 
int del() // удаление дублей
{
    if (head)
    {
        Item *cur, *prev = head;
        while ((cur = prev->next) != head){ // пока хвост не замкнется
            if (strcmp(cur->data, prev->data) == 0) // проверяем не равны ли у них значения поля дата
                delete_node(cur); // если равны - удаляем текущий   
            else
                prev = cur;
        }
        if (strcmp(cur->data, prev->data) == 0)
            delete_node(cur);
    }
    return 0;
}
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
30.05.2011, 22:55  [ТС]     двунаправленный список. #25
Вроде понял, как работают функции преведенные Вами. Пойду тестить.
Большое спасибо.
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
30.05.2011, 23:03     двунаправленный список. #26
Ну, в функция del() это та же compare, только повторы узлов списка не выводятся, а удаляются вызовом функции delete_node(). Ну а в ней всё просто
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Item* delete_node(Item *node) // удаление узла. возвращает следующий узел
{
    if (node && node->next == node) // выполнение условия означает, что узел только один
    {
        delete node; // удаляем его
        head = node = NULL;
    }
    if (head)
    {
        Item *tmp = node->next; // запомним следующий (на всякий случай)
        if (head == node) // если удаляемый узел — голова,
            head = node->next; // то делаем головой следующий
        node->next->prev = node->prev; // следующий связываем с предыдущим
        node->prev->next = node->next; // а предыдущий со следующим
        delete node; 
        node = tmp; // возвращать будем указатель на следующий (иногда полезно)
    }
    return node;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.05.2011, 23:11     двунаправленный список.
Еще ссылки по теме:

СД Двунаправленный список - C++
Ребят помогите пожалуйста понять что значит сделать двунаправленный список используя обьектно-ориентированное программирование. Хотяб...

Двунаправленный список - C++
Как создать двунаправленный список из целых чисел? и как заменить повторяющиеся последовательности одним числом?

двунаправленный список - C++
Двунаправленный список.Найти сумму первого и последнего элементарных.Заранее спасибо

Двунаправленный список! - C++
Не Класс! Помогите создать список (Двунаправленный хоронящий int a ) сама проблема в том что я не пойму как организовать ссылку на...

двунаправленный список - C++
Используя двунаправленный список, написать программу сложения двух длинных целых чисел. Что такое двунаправленный список понимаю, но как...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
30.05.2011, 23:11  [ТС]     двунаправленный список. #27
За коментарии еще раз спасибо!
Выручили. )
Yandex
Объявления
30.05.2011, 23:11     двунаправленный список.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru