С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
1505 / 968 / 812
Регистрация: 30.04.2016
Сообщений: 3,334
1

Односвязные списки. Задача на использование быстрых и медленных указателей

14.07.2019, 18:44. Показов 546. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте, уважаемые форумчане! Придумал несложную задачу на использование быстрых и медленных указателей. Надеюсь, кому-то будет интересно. Вот код:

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
/*
Дан односвязный список, состоящий более чем из одного элемента. Начиная с головы списка начинают движение два указателя,
причем скорость второго в два раза больше, чем первого. Вывести элементы списка между двумя данными указателями, 
как только второй указатель достигнет введенной позиции (не индекса) списка. (pos > 1 и <= длины списка). 
Если таких элементов не найдено, вывести соответствующее сообщение. 
*/
 
#include <iostream>
 
    using namespace std;
 
struct List {
    int data;
    List* next;
};
 
List* head = NULL;
 
void add(int data) {
    List* temp = new List;
    temp->data = data;
    temp->next = NULL;
    if (head == NULL) {
        head = temp;
    } else {
        List* ptr = head;
        while (ptr-> next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = temp;
    }
}
 
void output(List* head, int pos) {
    List* slow = head;
    List* fast = head;
    int k = 0;
    bool flag = false;
    while (k < pos / 2) {
        slow = slow->next;
        fast = fast->next->next;
        k++;
    }
    List* curr = slow->next;
    while (curr != fast) {
        flag = true;
        cout << curr->data << " ";
        curr = curr->next;
    }
    if (!flag) {
        cout << "No any nodes found for output!\n";
    }
}
 
int main() {
    int n, val, pos;
    cout << "Enter a number of nodes (n > 1):\n";
    cout << "n = ";
    cin >> n;
    cout << "Enter some elements nodes:\n";
    for (int i = 1; i <= n; i++) {
        cin >> val;
        add(val);
    }
    cout << "Enter a position: (1 < pos <= n):\n";
    cout << "pos = ";
    cin >> pos;
    cout << "Output of the program:\n";
    output(head, pos);
    return 0;
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
14.07.2019, 18:44
Ответы с готовыми решениями:

Односвязные списки
Нужно создать односвязный список, есть код на си, хоть и кривоватый, там хоть как-то разобрался...

Односвязные списки
Помогите, никак не могу понять что делать.. Написал код самого линейного списка, а дальше завис.

Односвязные списки
Процедура для заполнения нового файла числами,скопированными из другого файла и записанными в...

Односвязные списки
не могу понять в чём ошибка. ВОт полностью программа program laba16; {$APPTYPE CONSOLE}...

3
610 / 415 / 151
Регистрация: 11.01.2019
Сообщений: 1,746
14.07.2019, 20:09 2
Это всё здОрово, но что такое "быстрые" указатели и "медленные"?
0
1505 / 968 / 812
Регистрация: 30.04.2016
Сообщений: 3,334
14.07.2019, 20:22  [ТС] 3
jugu, это когда один указатель, двигается быстрее чем другой (через один элемент, например). Такой подход позволяет решать некоторые проблемы. В частности, это поиск центрального элемента списка и задача о зайце и черепахе (см. Detecting a Loop in Singly Linked List - Tortoise & Hare). Моя следующая тема, снова на использование этого подхода для обмена первой половины списка со второй. Сейчас выкладываю.
0
610 / 415 / 151
Регистрация: 11.01.2019
Сообщений: 1,746
14.07.2019, 20:27 4
Ясно, а то я испугался, что в стандарте втихаря появились новые концепции...
0
14.07.2019, 20:27
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
14.07.2019, 20:27
Помогаю со студенческими работами здесь

Односвязные списки
Добрый день! Скажите можно ли создав два односвязных списка соединить их посредством указателя...

Односвязные списки
Доброго времени суток! Подскажите, пожалуйста где тут ошибка в коде. Заранее спасибо:rose: ...

односвязные списки
Помогите пожалуста в проге нужно в методе класа List нужно вставить елементы с первого списка в...

Односвязные списки
Задача: добавить в список 1 узлы, содержащие слова в списке 2, не совпадающие со словами списка...

односвязные списки С++
Дана последовательность символов s1 , s2 , . . . , sn ( n &gt;= 2 и заранее неизвестно)....

Односвязные списки
Вечер добрый) Сформировать список символов, оканчивающийся точкой. Заменить в списке символ “A” на...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
Telegram бот на C#
InfoMaster 08.01.2025
Разработка ботов для Telegram стала неотъемлемой частью современной экосистемы мессенджеров. C# предоставляет мощный и удобный инструментарий для создания разнообразных ботов, от простых. . .
Использование GraphQL в Go (Golang)
InfoMaster 08.01.2025
Go (Golang) является одним из наиболее популярных языков программирования, используемых для создания высокопроизводительных серверных приложений. Его архитектурные особенности и встроенные. . .
Что лучше использовать при создании класса в Java: сеттеры или конструктор?
Alexander-7 08.01.2025
Вопрос подробнее: На вопрос: «Когда одновременно создаются конструктор и сеттеры в классе – это нормально?» куратор уточнил: «Ваш класс может вообще не иметь сеттеров, а только конструктор и геттеры. . .
Как работать с GraphQL на TypeScript
InfoMaster 08.01.2025
Введение в GraphQL и TypeScript В современной разработке веб-приложений GraphQL стал мощным инструментом для создания гибких и эффективных API. В сочетании с TypeScript, эта технология. . .
Счётчик на базе сумматоров + регистров и генератора сигналов согласования.
Hrethgir 07.01.2025
Создан с целью проверки скорости асинхронной логики: ранее описанного сумматора и предополагаемых fast регистров. Регистры созданы на базе ранее описанного, предполагаемого fast триггера. То-есть. . .
Как перейти с Options API на Composition API в Vue.js
BasicMan 06.01.2025
Почему переход на Composition API актуален В мире современной веб-разработки фреймворк Vue. js продолжает эволюционировать, предлагая разработчикам все более совершенные инструменты для создания. . .
Архитектура современных процессоров
inter-admin 06.01.2025
Процессор (центральный процессор, ЦП) является основным вычислительным устройством компьютера, которое выполняет обработку данных и управляет работой всех остальных компонентов системы. Архитектура. . .
История создания реляционной модели баз данных, правила Кодда
Programming 06.01.2025
Предпосылки создания реляционной модели В конце 1960-х годов компьютерная индустрия столкнулась с серьезными проблемами в области управления данными. Существовавшие на тот момент модели данных -. . .
Полезные поделки на Arduino, которые можно сделать самому
raxper 06.01.2025
Arduino как платформа для творчества Arduino представляет собой удивительную платформу для технического творчества, которая открывает безграничные возможности для создания уникальных проектов. Эта. . .
Подборка решений задач на Python
IT_Exp 06.01.2025
Целью данной подборки является предоставление возможности ознакомиться с различными задачами и их решениями на Python, что может быть полезно как для начинающих, так и для опытных программистов. . . .
С чего начать программировать микроконтроллер­­ы
raxper 06.01.2025
Введение в мир микроконтроллеров Микроконтроллеры стали неотъемлемой частью современного мира, окружая нас повсюду: от простых бытовых приборов до сложных промышленных систем. Эти маленькие. . .
Из чего собрать игровой компьютер
inter-admin 06.01.2025
Сборка игрового компьютера требует особого внимания к выбору комплектующих и их совместимости. Правильно собранный игровой ПК не только обеспечивает комфортный геймплей в современных играх, но и. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru