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

Реализуйте АТД “Список” для любого типа данных - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Даны две последовательности а1,а2,...аn и b1, b2, ... bn (m<n). В каждой из них члены различны. http://www.cyberforum.ru/cpp-beginners/thread402257.html
Даны две последовательности а1,а2,...аn и b1, b2, ... bn (m<n). В каждой из них члены различны. Верно ли, что все члены второй последовательности входят в первую последовательность входят в первую последовательность?
C++ Ругается на функцию В чём тут ошибка? #include <iostream> #include <string> const int n=3; http://www.cyberforum.ru/cpp-beginners/thread402250.html
написать программу, которая содержит текущую информацию о продажах билетов на теплоход C++
C++. написать программу, которая содержит текущую информацию о продажах билетов на теплоход. Сведения о каждой продаже содержат: • Пристань назначения; • Номер рейса • Фамилию и инициалы пассажира • Стоимость билета • Желаемая дата отплытия Программа должна решать следующие задачи: • Начальное формирование данных обо всех продажах билетов в кассе в виде списка. • Добавление продажи в...
C++ Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки.
Доброго времени суток всем! Вот такая задача, ничего не могу даже сообразить по ней, подкиньте идеи, пожалуйста (ну или код в C++ ) Дан массив А(м х м), заполненный "1" и "0". С клавиатуры вводятся координаты i,j двух точек мас-сива. Определить, существует ли путь от первой ко второй точке, состоящий из одних "0". Вывести найденный путь в удобной форме.
C++ Обращение матрицы методом Гаусса. http://www.cyberforum.ru/cpp-beginners/thread402207.html
Если кто знает, напишите пожалуйста программу обращения любой матрицы методом Гаусса.
C++ Использование массивов в Dev-c++ Написать функцию для удаления строки из двумерного массива. Оставшиеся строки должны быть расположены плотно, недостающие элементы заменяются 0. С помощью разработанных функций исключить из массива строки с номерами от А до В. подробнее

Показать сообщение отдельно
JerryJackson
50 / 6 / 1
Регистрация: 15.07.2010
Сообщений: 112
12.12.2011, 23:56     Реализуйте АТД “Список” для любого типа данных
1) База дерева бинарного поиска

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
137
138
139
140
#include<iostream>
 #include <windows.h>
 using namespace std;
 
 template <class T,class I> class node
 {
 private:
 T x; //ключ
 I info;//информация
 node* LL; //left link
 node* RL; //right link
 public:
 node(){x=0;LL=0;RL=0;};
 ~node()
 {
 if (LL) LL->~node();
 if (RL) RL->~node();
 if (LL) {delete LL; LL=0;}
 if (RL) {delete RL; RL=0;}
 }
 void putx(T new_x,I new_info){this -> x=new_x;this -> info=new_info;}
 void null_leftlink(){this -> LL=0;}
 void null_rightlink(){this -> RL=0;}
 void add(T new_x, I new_info)
 {
 if (LL&&(new_x < x)) LL->add(new_x,new_info);
 if (RL&&(new_x > x)) RL->add(new_x,new_info);
 
 if (!LL&&(new_x < x))
 {
 node* N=new node;
 N->x=new_x;
 N->info=new_info;
 N->LL=0;
 N->RL=0;
 LL=N;
 }
 if (!RL&&(new_x > x))
 {
 node* N=new node;
 N->x=new_x;
 N->info=new_info;
 N->LL=0;
 N->RL=0;
 RL=N;
 }
 }
 void print(int tab)
 {
 if (RL) RL-> print(tab + 1);
 for(int i=1;i!=tab;i++)cout << " "; cout <<this->x << "-"<< this->info << endl;
 if(LL) LL->print(tab + 1);
 }
 void del_all()
 {
 if (LL) LL->del_all();
 if (RL) RL->del_all();
 if (LL) {delete LL; LL=0;}
 if (RL) {delete RL; RL=0;}
 }
 void del(T x_to_del)
 {
 if (LL) LL->del();
 if (RL) RL->del();
 }
 I get(T getx)
 {
 if (getx==x) return info;
 if (LL&&(getx < x)) return LL->get(getx);
 if (RL&&(getx > x)) return RL->get(getx);
 }
 };
 
 template <class T,class I> class tree
 {
 private:
 node <T,I>* link;
 public:
 tree(){link=0;};
 ~tree(){if (link)link->~node<T,I>();delete link; link=0;};
 void add(T new_x,I new_info)
 {
 if (link) link->add(new_x,new_info);
 else
 {
 node<T,I>* N=new node<T,I>;
 N->putx(new_x,new_info);
 N->null_leftlink();
 N->null_rightlink();
 link=N;
 }
 };
 void print(){if(link)link->print(1);else cout << "No tree existing\n";}
 void del_all(){if(link) link->del_all(); delete link; link=0;}
 void del(int x){if (link)link->del(x);};
 I get(T x){if (link) return link->get(x);else cout << "No elements existing\n";}
 };
 
 int main()
 {
 system("cls");//clear screen
 tree <int,char> *T=new tree <int,char>; // создание дерева
 //menu
 int choos = 0;
 const int exit = 6;
 while (choos != exit)
 {
 cout << "This is a 'tree'\n\n"
 "There is a menu for you to choos:\n"
 " 1-add;\n"
 " 2-use destructor;\n"
 " 3-print;\n"
 " 4-delete all;\n"
 " 5-get element;\n"
 " 6-exit;\n"
 "enter-> "; cin >> choos; system("cls");
 switch (choos){
 case 1: {
 int key; //ключ.
 char val; //значение
 cout << "enter key: "; cin >> key;
 cout << "enter int value: "; cin >> val;
 T->add(key,val);
 break;
 }
 case 2: T->~tree(); break;
 case 3: T->print(); break;
 case 4: T->del_all(); break;
 case 5:{
 cout << "what is key of element? ";
 int key=0;
 cin >> key;
 cout << "there it is: " << T->get(key) << endl;
 break;}
 default: if (choos!=exit)cout << "wrong int value " << choos << endl;
 }
 }
 delete T; //удаление дерева, используется деструктор.
 return 0;
 }
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
#include <iostream>
 
using namespace std;
 
template <class Item>
class ST
{
    private:
        typedef node *link;
        link heads;
        int N;
        int M;
        struct node
        {
            Item item;
            node *l, *r;
            node (Item x) { item = x; l = 0; r = 0; }
        };
    public:
        ST(int maxN)
        {
            N = 0;
            M = maxN / 5;
            heads = new link[M];
            for (int i = 0; i < M; i++)
            heads[i] = 0;
        }
        Item search(Key v)
        {
            return searchR(heads[hash(v, M)], v);
        }
        void insert(Item item)
        {
            int i = hash(item.key(), M);
            heads[i] = new node(item, heads[i]); N++;
        }
}
 
int main()
{
  ST<int,int> obj(5);
    for(int i=0; i<=15; i++){
    myq.st[i] = rand()% 10;
    cout<<" "<<obj.st[i];} cout<<"\n\n";
    obj.hash(8,5);
    obj.search(7);
    for(int y=0; y<=5; y++){
    cout<<" "<<obj.st[y];}    cout<<" "<<objst[y];}
 
    return 0;
}
3) Хеширование методом линейного зондирования

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
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
template <class Item, class Key>class ST
{
public:
Item *st;
int N, M;
Item nul1Item;
 
ST(int maxN)
{
 N = 0; M = 2*maxN;
 st = new Item[M] ;
 for (int i = 0; i < M; i++)
 st[i] = nul1Item;
}
 
int count() const { return N; }
 
void insert(Item item)
 { int i = hash (item.key (), M) ;
   while (!st[i].null()) i = (i+1)% M;
   st[i] = item; N++;
}
 
Item search (Key v)
 { int i = hash(v, M) ;
   while (!st[i])
    if (v = st[i]) return st[i] ;
    else i = (i+1) % M;
   return nul1Item;
}
 
int hash(Key v, int M)
 {return (int) M*(v-5)/(10-5);}
 
};
 
 
int main()
{
    ST<int,int> myq(15);
    cout<<"ishodnij masiv ->\n\n";
    for(int i=0; i<=15; i++){
    myq.st[i] = rand()% 10;
    cout<<" "<<myq.st[i];} cout<<"\n\n";
    myq.hash(8,15);
    myq.search(7);
    for(int y=0; y<=15; y++){
    cout<<" "<<myq.st[y];}
    return 0;
}
Добавлено через 1 минуту
1) АТД «Стек» реализованный на базе массива.

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
#include <iostream>
 
using namespace std;
 
template<class Item>class Stack
{
    private:
        Item *s;
        int maxN;
        int N;
    public:
        Stack(int maxN) { s = new Item[maxN]; N = 0; }
        ~Stack() { delete [] s; }
        int empty() const { return N == 0; }
        void push(Item item);// { s[N++] = item; }
        Item pop(); //{ return s[--N]; }
        class UnderFlow{}; // Исключени: если стек переполнен
        class OverFlow{}; // Исключение: если стек пустой
};
 
template<class Item>void Stack<Item>::push(Item item)
{
    if (N == maxN) throw OverFlow();
    s[N] = item;
    N = N + 1;
}
 
template<class Item>Item Stack<Item>::pop()
{
    if(N == 0) throw UnderFlow();
    N = N - 1;
    return s[N];
}
 
int main()
{
    Stack<char>sc(2);
    sc.push('a');
    sc.push('b');
    sc.push('c');
    cout << sc.pop() << endl;
    cout << sc.pop() << endl;
    cout << sc.pop() << endl;
 
    return 0;
}
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
#include <iostream>
 
using namespace std;
 
template<class Item>
class Stack
{
    private:
        struct node
        {
            Item item;
            node* next;
            node(Item x, node* t) { item = x; next = t; }
        };
        typedef node *link;
        link head;
    public:
        Stack(int) { head = 0; }
        int empty() const { return head == 0; }
        void push(Item x) { head = new node(x, head); }
        Item pop() { Item v = head->item; link t = head->next;
        delete head; head = t; return v; }
};
 
int main()
{
    Stack<char>obj(5);
    
    obj.push('a');
    obj.push('b');
    obj.push('c');
    
    cout << obj.pop() << endl;
    cout << obj.pop() << endl;
    cout << obj.pop() << endl;
 
   return 0;
}
3)АТД «Очередь» на базе массива.

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
#include <iostream>
 
using namespace std;
 
template<class Item> class Queue
{
    private:
        Item *q;
        int N, head, tail;
    public:
        Queue(int maxN) { q = new Item[maxN + 1];
        N = maxN + 1; head = N; tail = 0; }
        int empty() const { return head % N == tail; }
        void put(Item item) { q[tail++] = item; tail = tail % N; }
        Item get() { head = head % N; return q[head++];}
};
 
int main()
{
    Queue<char>obj(5);
    obj.put('a');
    obj.put('b');
    obj.put('c');
    cout << obj.get() << endl;
    cout << obj.get() << endl;
    cout << obj.get() << endl;
 
    return 0;
}
4) АТД «Очередь» на базе связного списка.

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
#include <iostream>
using namespace std;
template<class Item> class Queue
{
    private:
        struct node
        {
            Item item;
            node* next;
            node(Item x)
            {
                item = x; next = 0;
            }
        };
        typedef node* link;
        link head, tail;
    public:
        Queue(int) { head = 0; }
        int empty() const { return head == 0; }
        void put(Item x) { link t = tail; tail = new node(x);
        if(head == 0) head = tail; else t->next = tail; }
        Item get() { Item v = head->item; link t = head->next;
        delete head; head = t; return v; }
};
int main()
{
      Queue<char>obj(5);
    obj.put('a');
    obj.put('b');
    obj.put('c');
    cout << obj.get() << endl;
    cout << obj.get() << endl;
    cout << obj.get() << endl;
    return 0;
}
 Комментарий модератора 
Используйте теги форматирования кода!
 
Текущее время: 22:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru