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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
29.05.2011, 22:49     двунаправленный список. #1
Доброго времени суток.
Прощу помочь с заданием которое звучит так :
Построить кольцевой двунаправлений список. Значения элементов считать из файла.
Определить, есть ли в списке хотяб один элемент, который равен элементу , что идет за ним по кругу. Вывести такие элементы. Удалить из списка все элементы у которых одинаковые "соседы"(первый и последний считать соседами).

Смог реализовать сам список и загрузку из файла, но вот как сравнивать текущий и предидущим не понимаю.
Буду рад любой помощи.
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++ Двунаправленный список
Двунаправленный список C++
C++ Двунаправленный список!
Двунаправленный список C++
C++ двунаправленный список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
30.05.2011, 12:41  [ТС]     двунаправленный список. #21
Буду ждать Вас, но не откажусь и от другой помощи!
На повестке ночи вопросы:
1)Как исправить то, что функция compare всегда выводит последний элемент списка, при этом никогда не сравнивая первый элемент.
2) Как удалять из списка элементы которые функция compare выводит?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
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
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
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
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
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++ Двунаправленный список

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

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

Текущее время: 02:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru