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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
№1
2 / 2 / 0
Регистрация: 15.03.2011
Сообщений: 19
#1

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

08.12.2011, 18:48. Просмотров 1252. Ответов 2
Метки нет (Все метки)

Помогите решить задачку.
1. Реализуйте АТД “Список” для любого типа данных и его операторы (INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, FIRST, PRINTLIST), используя массив.
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
122
123
#include <iostream>
using namespace std;
 
typedef int T;
 
struct elem
{
    T val;
    elem* prev;
    elem* next;
};
 
class list{
private:
    static const int def_size = 4;
    T* values;
    int count, val_size;
    void expand(int);
public: 
    list();
    ~list();
    list(const list&);
    list& operator=(const list&);
    T* BEGIN() const {return values;}
    T* END() const {return values+count;};
    T NEXT(int i) const {return *(values+i+1);}
    T PREVIOUS(int i) const {return *(values+i-1);}
    void INSERT(T value, int position);
    int FIND(T value) const; 
    int SIZE() const {return count;}
    void CLEAR();
    void DELETE(int position);
    int operator[](int i) const {return values[i];};
friend  ostream& operator<< (ostream& os, const list& l); 
};
list::list(){
    count = 0;
    val_size = def_size;
    values = new T[val_size];
}
list::list(const list& l){
    count = l.count;
    val_size = l.val_size;
    values = new T[val_size];
    for(int i=0; i< count; i++)
        values[i] = l.values[i];
}
list& list::operator=(const list& l){
    if(&l == this) return *this;
    delete[] values;
    count = l.count;
    val_size = l.val_size;
    values = new T[val_size];
    for(int i=0; i< count; i++)
        values[i] = l.values[i];
    return *this;
}
void list::expand(int increment){
    val_size += increment;
    T* newmas = new T[val_size];
    for(int i=0; i< count; i++)
        newmas[i] = values[i];
    delete[] values;
    values = newmas;
}
void list::CLEAR(){ // очистить
    count = 0;
    val_size = def_size;
    delete[] values;
    values = new T[val_size];
}
void list::INSERT(T value, int position){ // вставить в список новый элемент
    if(count >= val_size-1) expand(5);
    for(int i=count; i>= position; i--){
        values[i+1] = values[i];
    }
    values[position] = value;
    count ++;
}
void list::DELETE(int position){ // удалить этот элемент
    for(int i= position; i< count; i++)
        values[i] = values[i+1];
    count --;
}
int list::FIND(T value) const{ // найти элемент со значением value
    for(int i=0; i< count; i++)
        if(values[i] == value) return i;
    return -1;
}
list::~list(){
    delete[] values;
}
ostream& operator << (ostream& os, const list& l) {
    if(l.count == 0)return os << "empty list\r\n";
    for (int i = 0; i < l.count; i++)
        cout << l.values[i] << "  ";
    return os << "\r\n";
}
int main() {
    list l;
    cout << l;
    l.INSERT(10, 0);
    cout << l;
    l.INSERT(21, 1);
    cout << l;
    l.INSERT(55, l.FIND(10));
    cout << l;
    l.INSERT(57, 2);
    list m;
    m = l;
    cout << m;
    cout << l;
    cout << l.NEXT(l.FIND(55)) << endl;
    cout << l.PREVIOUS(l.FIND(21)) << endl;
    cout << l.PREVIOUS(l.SIZE()) << endl;
    cout << l.SIZE() << endl;
    cout << *l.BEGIN() << endl << *(l.END()-1) << endl;
    l.DELETE(l.FIND(21));
    cout << l;
    l.CLEAR();
    m.CLEAR();
    cout << l;
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2011, 18:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Реализуйте АТД “Список” для любого типа данных (C++):

Согласно заданию реализовать класс абстрактного типа данных (далее АТД) как динамический массив. Для этого определение класса должно иметь следующие - C++
1. Согласно заданию реализовать класс абстрактного типа данных (далее АТД) как динамический массив. Для этого определение класса должно...

АТД "Однонаправленный список" с элементами типа char - C++
помогите пожалуйста) АТД − однонаправленный список с элементами типа char. Дополнительно перегрузить следующие операции: + –...

Разработать абстрактный тип данных (АТД) «Двусвязный циклический список» - C++
Разработать абстрактный тип данных (АТД) «Двусвязный циклический список». АТД должен обеспечивать выполнение следующих операций: ...

Шифрование любого типа данных - C++
Всем привет у меня вопрос по теории. Написал консольное приложение которое изначально как я предполагал будет способно зашифровать текст...

Создать класс "Список объектов любого типа" - C++
Создайте класс, который способен запоминать список объектов не заданного типа класса (для любого класса). Помогите кто знает (Нужен код,...

Создать класс "Список объектов любого типа" - C++
Создайте класс, который способен запоминать список объектов не заданного типа класса (для любого класса). #include &lt;iostream&gt; ...

2
№1
2 / 2 / 0
Регистрация: 15.03.2011
Сообщений: 19
12.12.2011, 23:50  [ТС] #2
Что, никто не знает?
1
JerryJackson
50 / 6 / 1
Регистрация: 15.07.2010
Сообщений: 112
12.12.2011, 23:56 #3
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;
}
 Комментарий модератора 
Используйте теги форматирования кода!
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2011, 23:56
Привет! Вот еще темы с ответами:

Разработайте и реализуйте абстрактный тип данных для представления треугольника - C++
Разработайте и реализуйте абстрактный тип данных для представления треугольника. Данные этого типа должны включать в себя стороны...

Написать шаблонную функцию, для обработки матриц любого типа - C++
Написать ф-цию по матрицам,превратить в шаблон с тем,чтобы ф-ция обрабатывала матрицу любого типа.

АТД-однонаправленный список - C++
доброй ночи =) .......я человек не смыслящий в этом атд классе, нуждаюсь в вашой помощи.......вот мне попалось такое задание ...

АТД список. Сравнение элементов - C++
Здравствуйте!! Тут возникла такая проблема! Подскажите пожалуйста каким образом можно сравнить элементы списка в цикле!!! В...


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

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

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