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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
№1
2 / 2 / 0
Регистрация: 15.03.2011
Сообщений: 19
08.12.2011, 18:48     Реализуйте АТД “Список” для любого типа данных #1
Помогите решить задачку.
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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2011, 18:48     Реализуйте АТД “Список” для любого типа данных
Посмотрите здесь:

C++ АТД-однонаправленный список
АТД список. Сравнение элементов C++
АТД список. Объединение списков. C++
C++ Атд список. Удалить одинаковые элементы.
C++ Шифрование любого типа данных
C++ Разработайте и реализуйте абстрактный тип данных для представления треугольника
АТД "Однонаправленный список" с элементами типа char C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
№1
2 / 2 / 0
Регистрация: 15.03.2011
Сообщений: 19
12.12.2011, 23:50  [ТС]     Реализуйте АТД “Список” для любого типа данных #2
Что, никто не знает?
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;
}
 Комментарий модератора 
Используйте теги форматирования кода!
Yandex
Объявления
12.12.2011, 23:56     Реализуйте АТД “Список” для любого типа данных
Ответ Создать тему
Опции темы

Текущее время: 13:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru