Как сделать односвязный список в узле дерева
29.12.2013, 15:51. Показов 814. Ответов 1
Ребят подскажите, пожалуйста, как сделать односвязный список в узле дерева?
Нужно написать программу учета нарушений ПДД. Для каждого а/м нужно хранить в базе список нарушений. Для каждого нарушения фиксируется дата, время, вид нарушения и размер штрафа. При оплате всех штрафов а/м удаляется из базы. Ключом узла д/б номер а/м.
код списка:
list.h
| 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
| #ifndef LIST_H
#define LIST_H
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct LIST
{
char date[15];
char time[15];
char narushenie[50];
float price;
struct LIST *next;
};
typedef struct LIST LIST;
class CL_LIST
{
private:
LIST *first, *cur;
int GoToPrev(); //переход в предыдущий элемент
void GoToFirst(); //перейти в начало списка
int IsEnd(); //конец списка ?
int Move(); //движение вправо по списку
int IsEmpty(); //пустой ли список ?
public:
CL_LIST(); //конструктор
void AddFirst(char *_date, char *_time, char *_narushenie, float _price); //добавление первого элемента
void AddAfloCur(char *_date, char *_time, char *_narushenie, float _price); //добавление после текущего
int GetElem(); //возвращает текущий элемент
void DeleteFirst(); //удаление первого элемента
int DeleteCur(); //удаление текущего
int Print(); //печать списка
int DeleteKey(char *_date, char *_time); //удаление по ключу
};
#endif |
|
list.cpp
| 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
| #include "list.h"
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
CL_LIST::CL_LIST() { first = NULL; cur = NULL;}
int CL_LIST::IsEmpty() { return first == NULL; }
void CL_LIST::AddFirst(char *_date, char *_time, char *_narushenie, float _price)
{
LIST *tmp = new struct LIST;
strcpy(tmp->date, _date);
strcpy(tmp->time, _time);
strcpy(tmp->narushenie, _narushenie);
tmp->price = _price;
tmp->next = first;
first = cur = tmp;
}
void CL_LIST::AddAfloCur(char *_date, char *_time, char *_narushenie, float _price)
{
if(IsEmpty(){
AddFirst(_date, _time, _narushenie, _price);
return;
}
LIST *tmp = new struct LIST;
strcpy(tmp->date, _date);
strcpy(tmp->time, _time);
strcpy(tmp->narushenie, _narushenie);
tmp->price = _price;
tmp->next = cur->next;
cur->next = tmp;
cur = tmp;
}
int CL_LIST::IsEnd() { return cur->next == NULL; }
void CL_LIST::GoToFirst() { cur = first; }
int CL_LIST::GetElem() { return cur->data; }
int CL_LIST::Move()
{
if(IsEnd()) return 1;
cur = cur->next;
return 0;
}
int CL_LIST::GoToPrev()
{
if(IsEmpty()) return 1;
if(cur == first) return 2;
LIST *tmp = cur;
GoToFirst();
while(cur->next != tmp) Move();
return 0;
}
void CL_LIST::DeleteFirst()
{
if(IsEmpty()) { printf("pustoi spisok\n"); return; }
LIST *tmp = first->next;
delete first;
first = tmp;
}
int CL_LIST::DeleteCur()
{
if(IsEmpty()) return 1;
if(cur == first)
{
DeleteFirst();
return 0;
}
else
{
LIST *tmp = new struct LIST;
tmp = cur;
GoToPrev();
cur->next = tmp->next;
delete tmp;
}
return 0;
}
int CL_LIST::Print()
{
if(IsEmpty()) return 1;
GoToFirst();
cout << "Список нарушений:" << endl
<< "Дата Время Вид нарушения Штраф" << endl
<< cur->date << cur->time << cur->narushenie << cur->price << endl;
while(!IsEnd()){
Move();
cout << cur->date << cur->time << cur->narushenie << cur->price << endl;
}
return 0;
}
int CL_LIST::DeleteKey(char *_date, char *_time)
{
if(IsEmpty(f))
return 1;
GoToFirst();
if(strcmp(first->date, _date) == 0 && strcmp(first->time, _time) == 0)
DeleteFirst();
while(!IsEnd())
{
Move();
if(strcmp(cur->date, _date) == 0 && strcmp(cur->time, _time) == 0)
{
DeleteCur();
return 0;
}
}
return 0;
} |
|
Дерево:
| 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
| #ifndef TREE_H
#define TREE_H
#include <stdio.h>
#include <stdlib.h>
class tree
{
private:
int info; //Информационная часть
tree *left;
tree *right;
public:
tree *root;
tree() {root = NULL;}
void stree(tree *r, tree *previous, int info); //Добавление элемента в дерево
tree *dtree(tree *r, int key);
void preorder(tree *r);
void inorder(tree *r);
void postorder(tree *r);
void print_tree(tree *r, int L);
tree *seach_tree(tree *r, int key);
};
#endif |
|
| 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
| #include "tree.h"
// добавление элементов в дерево
void tree:: stree( tree *r, tree *previous, int info) //Аргументы: Указатель на корень, Указатель на предыдущий узел, инфомационная часть
{
if(r==NULL) {
r=new tree;
if (r==NULL) { printf("Heдocтaтoчнo пaмяти\n"); return;}
r->left=NULL;
r->right=NULL;
r->info=info;
if (root==NULL) root=r; //пepвый элeмeнт
else
{
if (info < previous->info) previous->left=r;
else previous->right=r;
}
return;
}
if (info < r->info) stree(r->left, r, info);
else stree(r->right, r, info);
}
// печать
void tree::print_tree(tree *r, int L)
{
int i;
if(r==NULL) return;
print_tree(r->right, L+1);
printf ("\n");
for(i=0;i<L;i++) printf("\t");
printf("%d \n",r->info);
print_tree(r->left, L+1);
}
// последовательный обход дерева
void tree::inorder (tree *r)
{
if(r==NULL) return;
inorder(r->left);
if(r->info) printf("\t%d",r->info);
inorder(r->right);
}
// обход дерева нисходящий
void tree:: preorder(tree *r)
{
if(r==NULL) return;
if(r->info) printf("\t%d",r->info);
preorder(r->left);
preorder(r->right);
}
// обход дерева восходящий
void tree::postorder(tree *r)
{
if(r==NULL) return;
postorder(r->left) ;
postorder(r->right);
if(r->info) printf("\t%d",r->info);
}
// поиск по дереву
tree* tree::seach_tree(tree *r, int key)
{
if(r==NULL) return r; // пустое дерево
while(r->info!=key) {
if (key < r->info) r=r->left;
else r=r->right;
if (r==NULL) break;
}
return r;
}
tree* tree::dtree(tree *r, int key)
{
tree *p, *p2;
if(r == NULL) return r; // элемент нe найден
if (r->info==key) { // delete root
//this means an empty tree
if (r->left==r->right){
free(r);
if (r==root) root = NULL;
return NULL;
}
else if (r->left==NULL) {
p = r->right; free(r) ;
if (r==root) root = p;
return p;
}
else if (r->right==NULL) {
p = r->left;
free(r) ;
if (r==root) root = p;
return p;
}
else
{
p2 = r;
p = r->right;
while(p->left) {p2 = p; p = p->left; }
p->left = r->left;
if(p2 != r)
{
p2->left = p->right;
p->right = r->right;
}
free(r);
if (r == root) root = p;
return p;
}
}
if (r->info<key) r->right = dtree(r->right, key);
else r->left = dtree(r->left,key);
return r;
} |
|
Пробовал через наследование, что-то не получилось.... Подскажите плз, как в узле сделать список
0
|
(
