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

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

14.07.2019, 18:44. Показов 538. Ответов 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
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.07.2019, 20:27
Помогаю со студенческими работами здесь

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

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru