Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.75/55: Рейтинг темы: голосов - 55, средняя оценка - 4.75
 Аватар для Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 53

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

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

Студворк — интернет-сервис помощи студентам
Здравствуйте! Нужно реализовать кольцевую однонаправленную очередь. С простой очередью разобрался, но точную информацию про "кольцевую однонаправленную" найти не могу.
Поразмыслив логически, пришел к выводу что кольцевая однонаправленная очередь, это очередь фиксированного размера, 'head' которого двигается по кругу? А если добавить элемент, то добавляется он на место того элемента, что стоит перед 'head'? Что делать с элементами, которые удаляют?
Дайте пожалуйста точное объяснение, можно с реализацией
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
16.11.2011, 18:08
Ответы с готовыми решениями:

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

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

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

13
Заблокирован
16.11.2011, 18:17
Цитата Сообщение от Klendathu Посмотреть сообщение
Здравствуйте! Нужно реализовать кольцевую однонаправленную очередь. С простой очередью разобрался, но точную информацию про "кольцевую однонаправленную" найти не могу.
Поразмыслив логически, пришел к выводу что кольцевая однонаправленная очередь, это очередь фиксированного размера, 'head' которого двигается по кругу? А если добавить элемент, то добавляется он на место того элемента, что стоит перед 'head'? Что делать с элементами, которые удаляют?
Дайте пожалуйста точное объяснение, можно с реализацией
То, что вы описали, есть стек, то есть принцип, первым пришел, первым ушел. А в очереди элементы добавляются в хвост, а не в начало очереди.
0
 Аватар для Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 53
16.11.2011, 18:21  [ТС]
А как определить конец очереди, если у нас кольцо?
0
 Аватар для Serejke_qq
199 / 142 / 57
Регистрация: 06.07.2011
Сообщений: 300
16.11.2011, 18:23
в кольцевой , как таковой конца очереди нет.. Есть текущий элемент =))..
0
 Аватар для Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 53
16.11.2011, 18:24  [ТС]
Куда добавлять новый элемент? И куда девать удаляемый? Не могу понять)
0
Заблокирован
16.11.2011, 18:41
Цитата Сообщение от Klendathu Посмотреть сообщение
А как определить конец очереди, если у нас кольцо?
Вам нужно хранить два указателя: на начало очереди и на конец очереди
0
 Аватар для alkagolik
1599 / 622 / 113
Регистрация: 15.07.2011
Сообщений: 3,548
16.11.2011, 19:12
А.В. Ахо, Д.Э. Хокпрофт, Д.Д. Ульман "Структуры данных и алгоритмы" 2000
стр 61 - 66
1
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,973
17.11.2011, 02:23
Цитата Сообщение от Сыроежка Посмотреть сообщение
Вам нужно хранить два указателя: на начало очереди и на конец очереди
Да и одного хватит...
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
Сообщений: 53
21.11.2011, 22:22  [ТС]
Мне непонятны эти символы стрелок и malloc... Можно на С++ упрощенный вариант??
0
 Аватар для alkagolik
1599 / 622 / 113
Регистрация: 15.07.2011
Сообщений: 3,548
21.11.2011, 23:12
Цитата Сообщение от 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
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,973
21.11.2011, 23:42
Цитата Сообщение от Klendathu Посмотреть сообщение
Мне непонятны эти символы стрелок и malloc... Можно на С++ упрощенный вариант??
Может всё-таки учебник почитаете? А то ведь если на С++ по чесноку всё делать - проще точно не будет. Будут заморочки с классами, исключениями, функциями-друзьями для потокового ввода/вывода... Так, что, простой вариант уже был...
1
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
22.11.2011, 10:51
Klendathu, ну и, дополняя easybudda, без указателей (с которыми связаны "стрелочки") и динамического выделения памяти (с которым в данном случае связан malloc) вы тут никак не обойдётесь.
2
 Аватар для Klendathu
6 / 6 / 0
Регистрация: 10.11.2011
Сообщений: 53
22.11.2011, 20:31  [ТС]
С указателями не дружу))) Ну, спасибо) А если через вектор? Можно ведь без указателей обойтись...)
А почему вы делаете на С, а не С++?
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,973
22.11.2011, 23:23
Цитата Сообщение от Klendathu Посмотреть сообщение
А если через вектор?
Как Вы себе это представляете? Думаете - с итераторами проще будет? Да и замыкать в кольцо его самому прийдётся. То есть - писать свой класс, внутри которого контейнером тот же vector использовать. Хотя здесь больше список подошёл бы. В любом случае морока.

Цитата Сообщение от Klendathu Посмотреть сообщение
А почему вы делаете на С, а не С++?
Мне сам по себе язык С нравится. С++ уже громоздкий и неуклюжий какой-то... Одна радость - стандартная библиотека велосипедов.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
22.11.2011, 23:23
Помогаю со студенческими работами здесь

кольцевая очередь
очередь в виде кольцевого массива. Если в очередь поступает положительное число, то её размер увеличивается на 1, если отрицательное - не...

Динамическая кольцевая очередь
Изучаю Java по книге Шилдта. Там есть задание создание кольцевого варианта динамической очереди. Я уже не знаю, как еще ее можно сделать,...

Кольцевая очередь на основе массива
pos - указывает на след элемент после головы start - начало Как проверять очередь на пустоту и заполненность? получается когда pos =...

Кольцевой буфер(Кольцевая очередь)
Задали написать на Java кольцевой буффер. Только вот толкового описания строения и механизма работы этой структуры данных я никак не смог...

кольцевая дорога
Люд добрый, помоги пожалуйста с задачей, надо срочно её решить. Ссылка: Удалена ссылка на сторонний форум. заранее преочень благодарен).


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru