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

Кольцевая однонаправленная очередь - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.90
Klendathu
 Аватар для Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 51
16.11.2011, 18:08     Кольцевая однонаправленная очередь #1
Здравствуйте! Нужно реализовать кольцевую однонаправленную очередь. С простой очередью разобрался, но точную информацию про "кольцевую однонаправленную" найти не могу.
Поразмыслив логически, пришел к выводу что кольцевая однонаправленная очередь, это очередь фиксированного размера, 'head' которого двигается по кругу? А если добавить элемент, то добавляется он на место того элемента, что стоит перед 'head'? Что делать с элементами, которые удаляют?
Дайте пожалуйста точное объяснение, можно с реализацией
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Сыроежка
Заблокирован
16.11.2011, 18:17     Кольцевая однонаправленная очередь #2
Цитата Сообщение от Klendathu Посмотреть сообщение
Здравствуйте! Нужно реализовать кольцевую однонаправленную очередь. С простой очередью разобрался, но точную информацию про "кольцевую однонаправленную" найти не могу.
Поразмыслив логически, пришел к выводу что кольцевая однонаправленная очередь, это очередь фиксированного размера, 'head' которого двигается по кругу? А если добавить элемент, то добавляется он на место того элемента, что стоит перед 'head'? Что делать с элементами, которые удаляют?
Дайте пожалуйста точное объяснение, можно с реализацией
То, что вы описали, есть стек, то есть принцип, первым пришел, первым ушел. А в очереди элементы добавляются в хвост, а не в начало очереди.
Klendathu
 Аватар для Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 51
16.11.2011, 18:21  [ТС]     Кольцевая однонаправленная очередь #3
А как определить конец очереди, если у нас кольцо?
Serejke_qq
 Аватар для Serejke_qq
150 / 108 / 9
Регистрация: 06.07.2011
Сообщений: 224
Завершенные тесты: 2
16.11.2011, 18:23     Кольцевая однонаправленная очередь #4
в кольцевой , как таковой конца очереди нет.. Есть текущий элемент =))..
Klendathu
 Аватар для Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 51
16.11.2011, 18:24  [ТС]     Кольцевая однонаправленная очередь #5
Куда добавлять новый элемент? И куда девать удаляемый? Не могу понять)
Сыроежка
Заблокирован
16.11.2011, 18:41     Кольцевая однонаправленная очередь #6
Цитата Сообщение от Klendathu Посмотреть сообщение
А как определить конец очереди, если у нас кольцо?
Вам нужно хранить два указателя: на начало очереди и на конец очереди
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
16.11.2011, 19:12     Кольцевая однонаправленная очередь #7
А.В. Ахо, Д.Э. Хокпрофт, Д.Д. Ульман "Структуры данных и алгоритмы" 2000
стр 61 - 66
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
17.11.2011, 02:23     Кольцевая однонаправленная очередь #8
Цитата Сообщение от Сыроежка Посмотреть сообщение
Вам нужно хранить два указателя: на начало очереди и на конец очереди
Да и одного хватит...
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <stdlib.h>
 
typedef struct NODE {
    int value;
    struct NODE * next;
} node_t;
 
int add_node(node_t ** ring, int value){
    node_t * node;
    
    if ( ! ( node = malloc(sizeof(node_t)) ) )
        return -1;
    
    node->value = value;
 
    if ( *ring == NULL )
        *ring = node;
    else 
        node->next = (*ring)->next;
    (*ring)->next = node;
    *ring = (*ring)->next;
    
    return 0;
}
 
int remove_node(node_t ** ring){
    if ( *ring == NULL )
        return -1;
    
    else if ( (*ring)->next == *ring ) {
        free(*ring);
        *ring = NULL;
        return 1;
    }
    
    else {
        node_t * prev = (*ring)->next;
        while ( prev->next != *ring )
            prev = prev->next;
        prev->next = (*ring)->next;
        free(*ring);
        *ring = prev;
    }
    
    return 0;
}
 
int menu(void){
    int ret;
    
    printf("\n1 - add node\n2 - show current\n3 - shift right\n4 - remove current\n0 - exit\n\n> ");
    return ( scanf("%d", &ret) == 1 ) ? ret : -1;
}
 
int main(void){
    node_t * ring = NULL;
    int ret;
    
    while ( ret = menu() ){
        switch ( ret ) {
            case 1 :
                {
                    int value;
                    printf("Value: ");
                    if ( scanf("%d", &value) != 1 ){
                        fprintf(stderr, "Wrong input!\n");
                        exit(1);
                    }
                    if ( add_node(&ring, value) ){
                        fprintf(stderr, "Memory error!\n");
                        exit(1);
                    }
                    printf("New node added. Now current value is %d\n", ring->value);
                }
                break;
            case 2 : 
                if ( ring == NULL )
                    printf("No values.\n");
                else
                    printf("Current value is %d\n", ring->value);
                break;
            case 3 :
                if ( ring == NULL )
                    printf("No values!\n");
                else {
                    ring = ring->next;
                    printf("Ring shifted. Now current value is %d\n", ring->value);
                }
                break;
            case 4 :
                {
                    int r = remove_node(&ring);
                    if ( r == -1 )
                        printf("Nothing to remove.\n");
                    else if ( r == 1 )
                        printf("Last node was removed.\n");
                    else 
                        printf("Node removed. Now current value is %d\n", ring->value);
                }
                break;
            default :
                fprintf(stderr, "Wrong choice!\n");
                break;
        }
    }
        
    while ( ! remove_node(&ring) )
        ;
        
    printf("Good bye!\n");
    
    exit(0);
}
Klendathu
 Аватар для Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 51
21.11.2011, 22:22  [ТС]     Кольцевая однонаправленная очередь #9
Мне непонятны эти символы стрелок и malloc... Можно на С++ упрощенный вариант??
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
21.11.2011, 23:12     Кольцевая однонаправленная очередь #10
Цитата Сообщение от Klendathu Посмотреть сообщение
Мне непонятны эти символы стрелок и malloc... Можно на С++ упрощенный вариант??
"стрелка" - разыменовывание (или разыменование) указателя. Эквивалентно следующей записи
C
1
2
3
4
5
6
7
8
9
10
struct x
{
    int y;
}
 
struct x *point;
point = malloc(sizeof(struct x)); //гуглим "функция malloc"
/*следующие строки эквивалентны*/
(*point).y = 15;
point->y = 15;
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
21.11.2011, 23:42     Кольцевая однонаправленная очередь #11
Цитата Сообщение от Klendathu Посмотреть сообщение
Мне непонятны эти символы стрелок и malloc... Можно на С++ упрощенный вариант??
Может всё-таки учебник почитаете? А то ведь если на С++ по чесноку всё делать - проще точно не будет. Будут заморочки с классами, исключениями, функциями-друзьями для потокового ввода/вывода... Так, что, простой вариант уже был...
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
22.11.2011, 10:51     Кольцевая однонаправленная очередь #12
Klendathu, ну и, дополняя easybudda, без указателей (с которыми связаны "стрелочки") и динамического выделения памяти (с которым в данном случае связан malloc) вы тут никак не обойдётесь.
Klendathu
 Аватар для Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 51
22.11.2011, 20:31  [ТС]     Кольцевая однонаправленная очередь #13
С указателями не дружу))) Ну, спасибо) А если через вектор? Можно ведь без указателей обойтись...)
А почему вы делаете на С, а не С++?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.11.2011, 23:23     Кольцевая однонаправленная очередь
Еще ссылки по теме:

Очередь, теория. Очередь на шести стеках C++
C++ Игра "Однорукий бандит". Кольцевая очередь. Двусвязный список

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

Или воспользуйтесь поиском по форуму:
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
22.11.2011, 23:23     Кольцевая однонаправленная очередь #14
Цитата Сообщение от Klendathu Посмотреть сообщение
А если через вектор?
Как Вы себе это представляете? Думаете - с итераторами проще будет? Да и замыкать в кольцо его самому прийдётся. То есть - писать свой класс, внутри которого контейнером тот же vector использовать. Хотя здесь больше список подошёл бы. В любом случае морока.

Цитата Сообщение от Klendathu Посмотреть сообщение
А почему вы делаете на С, а не С++?
Мне сам по себе язык С нравится. С++ уже громоздкий и неуклюжий какой-то... Одна радость - стандартная библиотека велосипедов.
Yandex
Объявления
22.11.2011, 23:23     Кольцевая однонаправленная очередь
Ответ Создать тему
Опции темы

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