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

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

Войти
Регистрация
Восстановить пароль
 
Priorzivil
0 / 0 / 0
Регистрация: 11.03.2013
Сообщений: 11
#1

Списки. Удалить каждое последующее вхождение символа если он встречался до этого. - C++

11.03.2013, 18:07. Просмотров 350. Ответов 0
Метки нет (Все метки)

Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен

Задача 7 Двусвязный список

В файле input.txt содержатся символы создать из этих символов список. Удалить каждое последующее вхождение символа если он встречался до этого.
Input:
Код
= + - ) ( + ? _ - ) трава трава
Код программы
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <fstream>
using namespace std;
 
ifstream in("input.txt");
ofstream out("output.txt");
 
class spisok
{
private:
    struct elem
    {
        char inf;
        elem *next;
        elem *prev;
        elem (char x, elem *p, elem *n):inf(x), next(p), prev(n){}
    };
    elem *head, *tail;
public:
    spisok():head(0), tail(0){};
    void push_head(char value)
    {
        head= new elem(value, head, NULL);
 
    }
    void push_tail(char value)
    {
        elem *newptr= new elem(value, NULL, tail);
        if(head==0)
            head=tail=newptr;
        else
        {
            tail->next=newptr;
        }
        tail=newptr;
    }
    void print()
    {
        //cout<<"*";
        if(head!=0)
        {
            //cout<<"$";
            elem *r=head;
            while(r!=NULL)
                {
                //cout<<"&";
                    out<<r->inf<<' ';
                    r=r->next;
                }
        }
        else out<<"empty spisok";
 
    }
    void findRemove(char i,elem *t)
        {
            elem *r=t->next;
            while(r!=NULL)
            {
                if(r->inf==i)
                    {
                        remove(r);
                    }
                else r=r->next;
 
            }
        }
    void remove (elem *&r)
        {
            if(r->prev==NULL&&r->next==NULL)
            {
                r=NULL;
                delete r;
                return;
            }
 
            if(r->prev==NULL)
            {
                elem *p=r;
                r->next->prev=NULL;
                head=r->next;
                r=head;
                delete p;
            }
            else if(r->next==NULL)
            {
                elem *t=r;
                r->prev->next=NULL;
                tail=r->next;
                r=tail;
                delete t;
 
            }
            else
            {
                elem *t=r;
                t->next->prev=r->prev;
                t->prev->next=r->next;
                //t->next=NULL;
                //t->prev=NULL;
                r=r->next;
                delete t;
 
            }
        }
    void removeAll()
        {
            for(elem *t=head; t!=NULL; t=t->next)
            {
                findRemove(t->inf,t);
            }
        }
 
};
 
int main()
{
    spisok t;
    char n;
    while(in>>n)
    {
        t.push_tail(n);
    }
    out<<"Spisok:"<<endl;
    t.print();
    t.removeAll();
    out<<endl;
    out<<"Spisok s ydaleniem"<<endl;
    t.print();
    out<<endl;
    in.close();
    out.close();
    
  system("PAUSE");
 
    return 0;
}
output:
Код
Spisok:
= + - ) ( + ? _ - ) т р а в а т р а в а 
Spisok s ydaleniem
= + - ) ( ? _ т р а в
Задача 8 Деревья 1

в файле input.txt хранится последовательность целых чисел. По входной последовательности построить дерево бинарного поиска и найти количество узлов, имеющих только одного левого потомка
Input:
Код
15 10 9 13 12 8 18
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
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
 
using namespace std;
 
class tree {
private:
 
    struct el {
        int val;
        el *l_tree;
        el *r_tree;
 
        el() {
            l_tree = 0;
            r_tree = 0;
        }
    };
 
    el *root;
 
public:
 
    tree() {root = 0;}
 
 
    void push (int x, el *&b) {
        if (!b) {
            el *t = new el;
            t->val = x;
            t->l_tree = t->r_tree = NULL;
            b = t;
        }
 
        if (b->val > x)
            push (x, b->l_tree);
        else
            if (b->val < x)
                push (x, b->r_tree);
    }
 
    void add (int x) {
        push(x, root);
    }
 
    //метод выводящий дерево в симметрическом порядке
    void print (el *r = 0) {
        if (r == 0)
            r = root;
 
        if (r->l_tree != 0)
            print (r->l_tree);
 
        cout << r->val << ' ';
 
        if (r->r_tree != 0)
            print (r->r_tree);
    }
 
    //метод ищущий ответ на задачу
    int ans (el *r = 0) {
        if (r == 0)
            r = root;
 
        int cnt = 0;
 
        if (r->l_tree != NULL) {
            cnt += ans (r->l_tree);
        }
 
        if (r->r_tree != NULL) {
            cnt += ans (r->r_tree);
        }
 
        if (r->l_tree != NULL && r->r_tree == NULL)
            ++cnt;
 
        return cnt;
    }
 
};
 
int main () {
    freopen("input.txt", "r", stdin);
    
    int x;
 
    tree derevo;
 
    while (cin >> x) {
        derevo.add(x);
    }
 
    cout << "Bin tree search:";
    derevo.print();
    cout << endl << "Answer:" << endl;
    cout << derevo.ans() << endl;
    return 0;
}
output:
Код
Bin tree search: 8 9 10 12 13 15 18
Answer: 2
Задача 9 Деревья 2
в файле input.txt хранится последовательность целых чисел. По входной последовательности построить идеально сбалансированное дерево и поменять в нем местами узлы, хранящие минимальное и максимальное значение

input:
Код
7 15 10 9 13 12 8 18
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
//сначала кол-во чисел, потом сами числа
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
 
using namespace std;
 
class tree {
private:
 
    struct el {
        int val;
        el *l_tree;
        el *r_tree;
 
        el() {
            l_tree = 0;
            r_tree = 0;
        }
    };
 
    el *root;
 
public:
 
    tree() {root = 0;}
 
 
    void push (int n, el *&b) {
        int x;
        if (n > 0) {
            b = new el;
            cin >> x;
            b->val = x;
            b->l_tree = b->r_tree = 0;
            int nl = n / 2;
            int nr = n - nl - 1;
            push(nl, b->l_tree);
            push(nr, b->r_tree);
        }
    }
 
    void add (int n) {
        push(n, root);
    }
 
    //метод выводящий дерево в симметрическом порядке
    void print (el *r = 0) {
        if (r == 0)
            r = root;
 
        if (r->l_tree != 0)
            print (r->l_tree);
 
        cout << r->val << ' ';
 
        if (r->r_tree != 0)
            print (r->r_tree);
    }
 
    //метод ищущий ответ на задачу
    void ans (el*& maxi, el*& mini, el *r) {
        if (r->val > maxi->val)
            maxi = r;
 
        if (r->val < mini->val)
            mini = r;
 
        if (r->l_tree != 0)
            ans (maxi, mini, r->l_tree);
 
        if (r->r_tree != 0)
            ans (maxi, mini, r->r_tree);
    }
 
    void change () {
        el* ma = root;
        el* mi = root;
        ans(ma, mi, root);
        swap (ma->val, mi->val);
    }
 
};
 
int main () {
    freopen("input.txt", "r", stdin);
    
    int x;
 
    tree derevo;
    //для дерева построения дерева бинарного поиска по последовательности нужно вводить только последовательность
    // а для идеальносбалансированного перед последовательностью её длину
    int n;
    cin >> n;
    derevo.add(n);
 
    cout << "Balanced tree:" << endl;
    derevo.print();
    derevo.change();
    cout << endl << "Balanced tree after:" << endl;
    derevo.print();
    return 0;
}
output:
Код
Balanced tree:
9 10 13 15 8 12 18
Balanced tree after:
9 10 13 15 18 12 8

задача 10 Граф 1
использовать представление графа в виде списков смежности
вывести на экран все вершины, не смежные с данной;
input:
Код
6
1 2 3
2 1 3 4
3 1 2 5
4 2 5
5 3 4 6
6 5
6

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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <fstream>
 
using namespace std;
 
vector<vector<int>> g;
int n;
 
int main () {
    freopen("input.txt", "r", stdin);
    cin >> n;
    g.resize(n);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        a--;
        while (cin.peek() != '\n' && cin.peek() != EOF) {
            int b;
            cin >> b;
            b--;
            g[a].push_back(b);
            g[b].push_back(a);
        }
    }
 
    // вершина из условии задачи
    int v;
    cin >> v;
    --v;
 
    cout << "Vershini ne smeznie s dannoy " << v + 1 << ":" << endl;
    for (int i = 0; i < n; i++) {
        bool f = false;
        for (int j = 0; j < g[v].size(); j++)
            if (i == g[v][j] || i == v) {
                f = true;
                break;
            }
        if (!f)
            cout << i + 1 << ' ';
    }
 
    return 0;
}
Код
Vershini ne smeznie s dannoy 6:
1 2 3 4
задача 11 Граф 2
использовать представление графа в виде списков смежности
добавить в орграф новую вершину.

Input:
Код
6
1 2 3
2 1 3 4
3 1 2 5
4 2 5
5 3 4 6
6 5
5
7 6
7 1
8 7
8 3
9 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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <fstream>
 
using namespace std;
 
vector<vector<int>> g;
int n;
 
int main () {
    freopen("input.txt", "r", stdin);
    cin >> n;
    g.resize(n);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        a--;
        while (cin.peek() != '\n' && cin.peek() != EOF) {
            int b;
            cin >> b;
            b--;
            g[a].push_back(b);
        }
    }
 
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {       
        // Дуга из v в u
        int v, u;
        cin >> v >> u;
        if (u > g.size() || v > g.size()) {
            g.push_back(vector<int>());
            n = g.size();
        }
        --u;
        --v;
        g[v].push_back(u);
    }
 
    cout << "spisok smeznosti grapha:" << endl;
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ": ";
        for (int j = 0; j < g[i].size(); j++)
            cout << g[i][j] + 1 << " ";
        cout << endl;
    }
 
    return 0;
}



output:
Код
spisok smeznosti grapha:
1: 2 3
2: 1 3 4
3: 1 2 5
4: 2 5
5: 3 4 6
6: 5
7: 6 1
8: 7 3
9: 8
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2013, 18:07
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Списки. Удалить каждое последующее вхождение символа если он встречался до этого. (C++):

Удвоить каждое вхождение символа в строке - C++
Дана строка s и c символ . Удвойте каждое вхождение символа c в строке s подскажите пожалуйста как решить. Добавлено через 10 минут ...

Удвоить каждое вхождение символа C в строку S - C++
Дана строка S и символ C. Удвоить каждое вхождение символа C в строку S. Помогите плиз написать программу с помощью функций.

Удвоить каждое вхождение символа С в строку S - C++
Дана строка S и символ С. Удвоить каждое вхождение символа С в строку S.

Дан символ C и строка S .Удвоить каждое вхождение символа С в строку S - C++
Обработка символьных массивов с помощью указателей: Дан символ C и строка S .Удвоить каждое вхождение символа С в строку S Для...

Заменить каждое вхождение <i> на <курсив>, а каждое вхождение </i> на <конец курсивах> - C++
Тэг курсива. Дан текст, в котором встречаются структуры &lt;i&gt; и &lt;/i&gt;. Заменить каждое вхождение &lt;i&gt; на &lt;курсив&gt;, а каждое вхождение &lt;/i&gt;...

Удалить из строки каждое вхождение подстроки - C++
Удалить из строки s каждое вхождение подстроки s1. На С++ Дублирование тем запрещено правилами форума (п. 3.4). Не плодите...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.03.2013, 18:07
Привет! Вот еще темы с ответами:

Как скопировать подстроку из строки до определенного символа? Или удалить, начиная с этого символа - C++
Добрый вечер. Ответ искал, но не нашёл. Предположим, есть строка: ABC|DEF Надо скопировать всё до | , т.е., в приведённом...

Из файла ввести слово и найти в нём последнее вхождение заданного символа, если он есть - C++
Из файла ввести слово и найти в нём последнее вхождение заданного символа, если он есть. Выдать соответствующее текстовое сообщение и...

В предложении удалить первое вхождение “w”, если такое есть - C++
Как можно выполнить это задание с помощью строк?? В предложении удалить первое вхождение “w”, если такое есть. Образовавшуюся “дыру”...

Удалить из списка последний отрицательный элемент, если такой есть (линейные списки) - C++
Помогите, пожалуйста. Нужно, написать программу, которая удаляет из списка последний отрицательный элемент, если такой есть.


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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