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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.90
Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 51
#1

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

16.11.2011, 18:08. Просмотров 3010. Ответов 13
Метки нет (Все метки)

Здравствуйте! Нужно реализовать кольцевую однонаправленную очередь. С простой очередью разобрался, но точную информацию про "кольцевую однонаправленную" найти не могу.
Поразмыслив логически, пришел к выводу что кольцевая однонаправленная очередь, это очередь фиксированного размера, 'head' которого двигается по кругу? А если добавить элемент, то добавляется он на место того элемента, что стоит перед 'head'? Что делать с элементами, которые удаляют?
Дайте пожалуйста точное объяснение, можно с реализацией
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.11.2011, 18:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Кольцевая однонаправленная очередь (C++):

однонаправленная очередь - C++
Проблема следующая,это одноноправленная очередь. 1)Создую очередь,удалаю элементы,все хорошо,НО тут же хочу создать заново...

Создать на базе класса с реализацией очереди клас потомок — кольцевая очередь - C++
Доброго времени суток. Я хотел создать на базе класса с реализацией очереди клас потомок - кольцевая очередь. Исходник: #include...

Игра "Однорукий бандит". Кольцевая очередь. Двусвязный список - C++
Здраствуйте. Задание: "Создать игру "Однорукий бандит". При нажатии кнопки Enter происходит "вращение" трех барабанов (количество...

Сформировать очередь по файлу целых чисел. Промоделировать очередь в супермаркете - C++
Сформировать очередь по файлу целых чисел. Промоделировать очередь в супермаркете. В каждый момент времени происходит одно из событий:...

Очередь (сделать очередь, чтобы добавляло, удаляло, читало. Не STL.) - C++
Помогите пожалуйста написать очередь. Есть Температура double и ее тип int ну и нужно сделать очередь, чтобы добавляло, удаляло, читало....

Задача на очередь (вывод сообщения, что очередь пуста) - C++
Доброго дня! Есть задачка на очередь, которая работает нормально, только надо добавить код, чтобы выводил сообщение, что очередь пуста.....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Сыроежка
Заблокирован
16.11.2011, 18:17 #2
Цитата Сообщение от Klendathu Посмотреть сообщение
Здравствуйте! Нужно реализовать кольцевую однонаправленную очередь. С простой очередью разобрался, но точную информацию про "кольцевую однонаправленную" найти не могу.
Поразмыслив логически, пришел к выводу что кольцевая однонаправленная очередь, это очередь фиксированного размера, 'head' которого двигается по кругу? А если добавить элемент, то добавляется он на место того элемента, что стоит перед 'head'? Что делать с элементами, которые удаляют?
Дайте пожалуйста точное объяснение, можно с реализацией
То, что вы описали, есть стек, то есть принцип, первым пришел, первым ушел. А в очереди элементы добавляются в хвост, а не в начало очереди.
0
Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 51
16.11.2011, 18:21  [ТС] #3
А как определить конец очереди, если у нас кольцо?
0
Serejke_qq
150 / 108 / 9
Регистрация: 06.07.2011
Сообщений: 224
Завершенные тесты: 2
16.11.2011, 18:23 #4
в кольцевой , как таковой конца очереди нет.. Есть текущий элемент =))..
0
Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 51
16.11.2011, 18:24  [ТС] #5
Куда добавлять новый элемент? И куда девать удаляемый? Не могу понять)
0
Сыроежка
Заблокирован
16.11.2011, 18:41 #6
Цитата Сообщение от Klendathu Посмотреть сообщение
А как определить конец очереди, если у нас кольцо?
Вам нужно хранить два указателя: на начало очереди и на конец очереди
0
alkagolik
Заблокирован
16.11.2011, 19:12 #7
А.В. Ахо, Д.Э. Хокпрофт, Д.Д. Ульман "Структуры данных и алгоритмы" 2000
стр 61 - 66
1
easybudda
Модератор
Эксперт CЭксперт С++
9625 / 5573 / 947
Регистрация: 25.07.2009
Сообщений: 10,708
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);
}
2
Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 51
21.11.2011, 22:22  [ТС] #9
Мне непонятны эти символы стрелок и malloc... Можно на С++ упрощенный вариант??
0
alkagolik
Заблокирован
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;
1
easybudda
Модератор
Эксперт CЭксперт С++
9625 / 5573 / 947
Регистрация: 25.07.2009
Сообщений: 10,708
21.11.2011, 23:42 #11
Цитата Сообщение от Klendathu Посмотреть сообщение
Мне непонятны эти символы стрелок и malloc... Можно на С++ упрощенный вариант??
Может всё-таки учебник почитаете? А то ведь если на С++ по чесноку всё делать - проще точно не будет. Будут заморочки с классами, исключениями, функциями-друзьями для потокового ввода/вывода... Так, что, простой вариант уже был...
1
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
22.11.2011, 10:51 #12
Klendathu, ну и, дополняя easybudda, без указателей (с которыми связаны "стрелочки") и динамического выделения памяти (с которым в данном случае связан malloc) вы тут никак не обойдётесь.
2
Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 51
22.11.2011, 20:31  [ТС] #13
С указателями не дружу))) Ну, спасибо) А если через вектор? Можно ведь без указателей обойтись...)
А почему вы делаете на С, а не С++?
0
easybudda
Модератор
Эксперт CЭксперт С++
9625 / 5573 / 947
Регистрация: 25.07.2009
Сообщений: 10,708
22.11.2011, 23:23 #14
Цитата Сообщение от Klendathu Посмотреть сообщение
А если через вектор?
Как Вы себе это представляете? Думаете - с итераторами проще будет? Да и замыкать в кольцо его самому прийдётся. То есть - писать свой класс, внутри которого контейнером тот же vector использовать. Хотя здесь больше список подошёл бы. В любом случае морока.

Цитата Сообщение от Klendathu Посмотреть сообщение
А почему вы делаете на С, а не С++?
Мне сам по себе язык С нравится. С++ уже громоздкий и неуклюжий какой-то... Одна радость - стандартная библиотека велосипедов.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.11.2011, 23:23
Привет! Вот еще темы с ответами:

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

Создать очередь. Добавить элемент в очередь. Удалить элемент из очереди - C++
Нужно создать очередь. Добавить элемент в очередь. Удалить элемент из очереди. Вот моё &quot;творение&quot;. int main() { int...

Очередь - C++
В чем проблема? не хочет запускаться код? Ошибки следующие: #include &lt;iostream&gt; #include &lt;queue&gt; using namespace std; ...

Очередь - C++
Описать структуру с именем TRAIN, содержащую следующие поля: - название пункта назначения - номер поезда - время отправления ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.11.2011, 23:23
Ответ Создать тему
Опции темы

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