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

Практические задания из собеседований - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ прога при компиляции ругаеться на "unit1.h" http://www.cyberforum.ru/cpp/thread308854.html
вся проблема в том,что у меня єтого файла нет,так как прога с нета качаная.можно ли его как нить востановить?? #include <vcl.h> #pragma hdrstop #include «Unit1.h» // – #pragma package...
C++ не работают условия кроме sravnenie[i].kozer==1 && sravnenie[j].kozer==1 int sravnenie_kart_v_massive_sravnenie(KARTA *kart,KARTA *sravnenie,int *nsravnenie,int *sravnenie11,int *sravnenie12,int *fsravnenie) {int n,i,j,f1=0,f2=0; n=0; for(i=*sravnenie11;i<9 &&... http://www.cyberforum.ru/cpp/thread307839.html
C++ Вывод текста через pokeb
Доброго времени суток. Столкнулся с проблемой при использование функции pokeb, выводит символы из таблицы асхи #include <conio.h> #include <string.h> #include <iostream.h> #include <ctype.h>...
вопрос по winsoc C++
WSAStartup(MAKEWORD(2,0), &wsaData); builder ругается на &wsaData, что делать?
C++ Программа шифрования http://www.cyberforum.ru/cpp/thread305362.html
Помогите написать программу для шифрования файлов с помощью симметричного алгоритма шифрования. на си или дельфи.?
C++ Vkontakte API Как в C++ пользоваться Vkontakte API? подробнее

Показать сообщение отдельно
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
10.06.2011, 17:49
2. Написать функцию, определяющую содержит ли односвязный список циклы (например, последний ссылается на второй).
Если решать в лоб - односвязный список не содержит циклов, если все указатели (которые получаются при последовательном обходе узлов списка в одну сторону) на его узлы уникальны:
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
115
116
117
118
119
120
121
#include <cstdlib>
#include <iostream>
#include <set>
#include <tuple>
 
template <class T>
struct node
{
    T value;
    node<T>* next;
    node(T, node<T>*);
};
 
template <class T>
node<T>::node(T v, node<T>* n)
    : value(v), next(n)
{
}
 
template <class T>
class singly_linked
{
    node<T>* first;
    node<T>* last;
    size_t sz;
    
public:
    singly_linked();
    singly_linked<T>& push(const T& val);
 
    // "Зацикливает" последний указатель на указатель node_no
    // (или на последний, если число указателей меньше node_no - 1)
    singly_linked<T>& make_circular(size_t node_no = 0);
 
    // Проверка на наличие циклов
    bool has_cycles() const;
 
    ~singly_linked();
};
 
template <class T>
singly_linked<T>::singly_linked()
    : first(NULL), last(NULL), sz(0)
{
}
 
template <class T>
singly_linked<T>& singly_linked<T>::push(const T& val)
{
    node<T>* new_node = new node<T>(val, NULL);
 
    if(!first)
    first = new_node;
    else
    last->next = new_node;
    last = new_node;
 
    ++sz;
    
    return *this;
}
 
template <class T>
singly_linked<T>& singly_linked<T>::make_circular(size_t node_no)
{
    node<T>* node = first;
 
    if(!node)
    throw 42;
    
    while(node->next && node_no--)
    node = node->next;
 
    last->next = node;
    
    return *this;
}
 
template <class T>
bool singly_linked<T>::has_cycles() const
{
    bool new_key;
    
    std::set<node<T>*> nodes;
 
    for(node<T>* pn = first; pn; pn = pn->next)
    {
    std::tie(std::ignore, new_key) = nodes.insert(pn);
    if(!new_key)
        return true;
    }
 
    return false;
}
 
template <class T>
singly_linked<T>::~singly_linked()
{
    while(sz--)
    {
    node<T>* del_node = first;
    first = first->next;
    delete del_node;
    del_node = NULL;
    }
}
 
 
#define CHECK(EXP) std::cout << #EXP ": " << std::boolalpha << (EXP) << std::endl
 
int main()
{
    singly_linked<int> lst;
 
    CHECK(lst.has_cycles());
    CHECK(lst.push(3).has_cycles());
    CHECK(lst.push(8).push(3).has_cycles());
    CHECK(lst.push(9).make_circular().has_cycles());
    
    return 0;
}


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