Был рассмотрен вопрос о важности структур данных и о том, как они влияют на эффективность алгоритмов. Выбор правильного представления данных служит ключом к удачному программированию и может в большей степени сказываться на производительности программы, чем детали используемого алгоритма. Для определения того, как структуры данных влияют на производительность программ, нужно рассмотреть, как можно строго проанализировать различные операции, выполняемые структурами данных. Вряд ли когда-нибудь появится общая теория выбора структур данных.
Стоит добавить, что совокупность структур данных и операций их обработки составляет модель данных, которая является ядром любой базы данных. Модель данных представляет собой множество структур данных, ограничений целостности и операций манипулирования данными. С помощью модели данных могут быть представлены объекты предметной области и взаимосвязи между ними. База данных основывается на использовании иерархической, сетевой или реляционной модели, на комбинации этих моделей или на некотором их подмножестве.
- Могилев А. В., Пак Н. И., Хеннер Е. К., Информатика, М., «Академия», 2004.
- Симонович С.В., Информатика: Базовый курс, СПб: Питер, 2007.
- Информатика: Учебник / Под общ. ред. А.Н. Данчула. - М.: И 74 Изд-во РАГС, 2004. - 528 с.
- Т. Пратт, М. Зелковиц. Языки программирования: разработка и реализация = Terrence W. Pratt, Marvin V. Zelkowitz. Programming Languages: Design and Implementation. - 4-е издание. - Питер, 2002. - 688 с. - (Классика Computer Science). - 4000 экз. - ISBN 5-318-00189-0.
- Каймин В.А. Информатика: Учебник. - М.: ИНФРА-М,2000. - 232 с. - (Серия «Высшее образование»).
- Т.А. Павловская С/С++. Программирование на языке высокого уровня. Спб. Питер – 2005.
- Гук М.Ю. Процессоры Intel от 8086 до Pentium II. СПб.: Питер, 1997.
- Нортон П., Соухэ Д. Язык ассемблера для IBM PC. М.: Компьютер, 1992.
- Высокие интеллектуальные технологии образования и науки: Материалы Х Международной научно-методической конференции. 28 февраля - 1 марта 2003 года. Санкт-Петербург. - СПб.: Изд-во СПбГПУ, 2003.– 420 с.
- Новые информационные технологии: Учеб. Пособие /Под ред. В.П. Дьяконова; Смол. гос. пед. ун-т. - Смоленск. 2003. - Ч. 3: Основы математики и математическое моделирование /~В.П. Дьяконов, И.В. Абраменкова, А.А. Пеньков. - 192 с.: ил.
- Дьяконов В. П. Компьютерная математика. Теория и практика. /В. П. Дьяконов. - М.: Нолидж, 2001.
- Говорухин В. Н., Цибулин В. Г. Компьютер в математическом исследовании. \ Учебный курс. - СПб.: Питер, 2001.
- Айламазян А. К., Информатика и теория развития. - М.: Наука, 1992.
- Информатика и образование, \N5 - 1999.
- Грэхем Р., Кнут Д., Паташник О. Конкретная информатика. - М.: Мир, 1988.
|
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
|
#include "stdafx.h"
#include <iostream>
using namespace std;
const int N=5; //размер дека
struct Deque
{
int data[N]; //массив данных
int last; //указатель на конец
};
void Creation(Deque *D) //создание дека
{ D->last=0; }
bool Full(Deque *D) //проверка дека на пустоту
{
if (D->last==0) return true;
else return false;
}
void AddL(Deque *D) //добавление элемента в начало
{
if (D->last==N)
{ cout<<"\nДек заполнен\n\n"; return; }
int value;
cout<<"\nЗначение > "; cin>>value;
for (int i=D->last; i>0; i--)
D->data[i]=D->data[i-1];
D->data[0]=value;
D->last++;
cout<<endl<<"Элемент добавлен\n\n";
}
void AddR(Deque *D) //добавление элемента в конец
{
if (D->last==N)
{ cout<<"\nДек заполнен\n\n"; return; }
int value;
cout<<"\nЗначение > "; cin>>value;
D->data[D->last++]=value;
cout<<endl<<"Элемент добавлен\n\n";
}
void DeleteL(Deque *D) //удаление первого элемента
{
for (int i=0; i<D->last; i++) //смещение элементов
D->data[i]=D->data[i+1]; D->last--;
}
void DeleteR(Deque *D) //удаление последнего элемента
{ D->last--; }
int OutputL(Deque *D) //вывод первого элемента
{ return D->data[0]; }
int OutputR(Deque *D) //вывод последнего элемента
{ return D->data[D->last-1]; }
int Size(Deque *D) //размер дека
{ return D->last; }
//******************************************
int main() //главная функция
{
setlocale(LC_ALL,"Rus");
Deque D;
Creation(&D);
char number;
do
{
cout<<"1. Добавить элемент в начало"<<endl;
cout<<"2. Добавить элемент в конец"<<endl;
cout<<"3. Удалить первый элемент"<<endl;
cout<<"4. Удалить последний элемент"<<endl;
cout<<"5. Вывести первый элемент"<<endl;
cout<<"6. Вывести последний элемент"<<endl;
cout<<"7. Узнать размер дека"<<endl;
cout<<"0. Выйти\n\n";
cout<<"Номер команды > "; cin>>number;
switch (number)
{
case '1': AddL(&D);
break;
//-----------------------------------------------
case '2': AddR(&D);
break;
//-----------------------------------------------
case '3':
if (Full(&D)) cout<<endl<<"Дек пуст\n\n";
else
{
DeleteL(&D);
cout<<endl<<"Элемент удален из дека\n\n";
} break;
//-----------------------------------------------
case '4':
if (Full(&D)) cout<<endl<<"Дек пуст\n\n";
else
{
DeleteR(&D);
cout<<endl<<"Элемент удален\n\n";
} break;
//-----------------------------------------------
case '5':
if (Full(&D)) cout<<endl<<"Дек пуст\n\n";
else cout<<"\nПервый элемент: "<<OutputL(&D)<<"\n\n";
break;
//-----------------------------------------------
case '6':
if (Full(&D)) cout<<endl<<"Дек пуст\n\n";
else cout<<"\nПоследний элемент: "<<OutputR(&D)<<"\n\n";
break;
//-----------------------------------------------
case '7':
if (Full(&D)) cout<<endl<<"Дек пуст\n\n";
else cout<<"\nРазмер дека: "<<Size(&D)<<"\n\n";
break;
//-----------------------------------------------
case '0': break;
default: cout<<endl<<"Команда не определена\n\n";
break;
}
} while(number!='0');
system("pause");
}
|
Приложение 2. Программная реализация дека на основе массива(вариант2):
|
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
|
#include "stdafx.h"
#include <iostream>
#include <deque>
using namespace std;
int main() //главная функция
{
setlocale(LC_ALL,"Rus");
deque<int> D; //создание дека D размером 5
deque<int>::iterator out;
int value;
char number;
do
{
cout<<"1. Добавить элемент в начало"<<endl;
cout<<"2. Добавить элемент в конец"<<endl;
cout<<"3. Удалить первый элемент"<<endl;
cout<<"4. Удалить последний элемент"<<endl;
cout<<"5. Вывести первый элемент"<<endl;
cout<<"6. Вывести последний элемент"<<endl;
cout<<"7. Узнать размер дека"<<endl;
cout<<"0. Выйти\n\n";
cout<<"Номер команды > "; cin>>number;
switch (number)
{
case '1':
cout<<"\nЗначение > "; cin>>value;
D.push_front(value);
cout<<endl<<"Элемент добавлен\n\n";
break;
//-----------------------------------------------
case '2':
cout<<"\nЗначение > "; cin>>value;
D.push_back(value);
cout<<endl<<"Элемент добавлен\n\n";
break;
//-----------------------------------------------
case '3': if (D.empty()) cout<<"\nДек пуст\n\n";
else
{
D.erase(D.begin());
cout<<endl<<"Элемент удален\n\n";
} break;
//-----------------------------------------------
case '4': if (D.empty()) cout<<"\nДек пуст\n\n";
else
{
D.erase(D.end()-1);
cout<<endl<<"Элемент удален\n\n";
} break;
//-----------------------------------------------
case '5':
if (D.empty()) cout<<endl<<"Дек пуст\n\n";
else
{
out=D.begin();
cout<<"\nПервый элемент: "<<*out<<"\n\n";
} break;
//-----------------------------------------------
case '6': if (D.empty()) cout<<"\nДек пуст\n\n";
else
{
out=D.end()-1;
cout<<"\nПоследний элемент: "<<*out<<"\n\n";
} break;
//-----------------------------------------------
case '7':
if (D.empty()) cout<<endl<<"Дек пуст\n\n";
else cout<<"\nРазмер дека: "<<D.size()<<"\n\n";
break;
//-----------------------------------------------
case '0': break;
default: cout<<endl<<"Команда не определена\n\n";
break;
}
} while(number!='0');
system("pause");
}
|
Приложение 3. Реализация очереди с помощью массива
|
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
|
#include "stdafx.h"
#include <iostream>
using namespace std;
const int N=4; //размер очереди
struct Queue
{
int data[N]; //массив данных
int last; //указатель на начало
};
void Creation(Queue *Q) //создание очереди
{ Q->last=0; }
bool Full(Queue *Q) //проверка очереди на пустоту
{
if (Q->last==0) return true;
else return false;
}
void Add(Queue *Q) //добавление элемента
{
if (Q->last==N)
{ cout<<"\nОчередь заполнена\n\n"; return; }
int value;
cout<<"\nЗначение > "; cin>>value;
Q->data[Q->last++]=value;
cout<<endl<<"Элемент добавлен в очередь\n\n";
}
void Delete(Queue *Q) //удаление элемента
{
for (int i=0; i<Q->last && i<N; i++) //смещение элементов
Q->data[i]=Q->data[i+1]; Q->last--;
}
int Top(Queue *Q) //вывод начального элемента
{ return Q->data[0]; }
int Size(Queue *Q) //размер очереди
{ return Q->last; }
void main() //главная функция
{
setlocale(LC_ALL,"Rus");
Queue Q;
Creation(&Q);
char number;
do
{
cout<<"1. Добавить элемент"<<endl;
cout<<"2. Удалить элемент"<<endl;
cout<<"3. Вывести верхний элемент"<<endl;
cout<<"4. Узнать размер очереди"<<endl;
cout<<"0. Выйти\n\n";
cout<<"Номер команды > "; cin>>number;
switch (number)
{
case '1': Add(&Q);
break;
//-----------------------------------------------
case '2':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else
{
Delete(&Q);
cout<<endl<<"Элемент удален из очереди\n\n";
} break;
//-----------------------------------------------
case '3':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else cout<<"\nНачальный элемент: "<<Top(&Q)<<"\n\n";
break;
//-----------------------------------------------
case '4':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else cout<<"\nРазмер очереди: "<<Size(&Q)<<"\n\n";
break;
//-----------------------------------------------
case '0': break;
default: cout<<endl<<"Команда не определена\n\n";
break;
}
} while(number!='0');
system("pause");
}
|
Приложение 4. Интерфейс очереди, основанной на базе циклического массива
|
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
|
#include "stdafx.h"
#include <iostream>
using namespace std;
const int N=6; //размер очереди
struct Queue
{
int data[N]; //массив данных
int first; //указатель на начало
int last; //указатель на конец
};
void Creation(Queue *Q) //создание очереди
{ Q->first=Q->last=1; }
bool Full(Queue *Q) //проверка очереди на пустоту
{
if (Q->last==Q->first) return true;
else return false;
}
void Add(Queue *Q) //добавление элемента
{
int value;
cout<<"\nЗначение > "; cin>>value;
if ((Q->last%(N-1))+1==Q->first)
cout<<"\nОчередь заполнена\n\n";
else
{
Q->data[Q->last]=value;
Q->last=(Q->last%(N-1))+1;
cout<<endl<<"Элемент добавлен в очередь\n\n";
}
}
void Delete(Queue *Q) //удаление элемента
{
Q->first=(Q->first%(N-1))+1;
cout<<endl<<"Элемент удален из очереди\n\n";
}
int Top(Queue *Q) //вывод начального элемента
{ return Q->data[Q->first]; }
int Size(Queue *Q) //размер очереди
{
if (Q->first>Q->last) return (N-1)-(Q->first-Q->last);
else return Q->last-Q->first;
}
void main() //главная функция
{
setlocale(LC_ALL,"Rus");
Queue Q;
Creation(&Q);
char number;
do
{
cout<<"1. Добавить элемент"<<endl;
cout<<"2. Удалить элемент"<<endl;
cout<<"3. Вывести верхний элемент"<<endl;
cout<<"4. Узнать размер очереди"<<endl;
cout<<"0. Выйти\n\n";
cout<<"Номер команды > "; cin>>number;
switch (number)
{
case '1': Add(&Q);
break;
//-----------------------------------------------
case '2':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else Delete(&Q);
break;
//-----------------------------------------------
case '3':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else cout<<"\nНачальный элемент: "<<Top(&Q)<<"\n\n";
break;
//-----------------------------------------------
case '4':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else cout<<"\nРазмер очереди: "<<Size(&Q)<<"\n\n";
break;
//-----------------------------------------------
case '0': break;
default: cout<<endl<<"Команда не определена\n\n";
break;
}
} while(number!='0');
system("pause");
}
|
Приложение5. Следующее консольное приложение обслуживает очередь, каждый элемент которой – целое число.
|
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
|
#include "stdafx.h"
#include <iostream>
using namespace std;
struct Node //описание узла списка
{
int data; //информационное поле
Node *next; //указатель на следующий элемент
};
struct Queue //описание очереди
{
int size; //счетчик размера очереди
Node *first; //указатель на начало очереди
Node *last; //указатель на конец очереди
};
void Creation(Queue *Q) //создание очереди
{
Q->first=new Node;
Q->first->next=NULL;
Q->last=Q->first;
Q->size=0;
}
bool Full(Queue *Q) //проверка очереди на пустоту
{
if (Q->first==Q->last) return true;
else return false;
}
int Top(Queue *Q) //вывод начального элемента
{ return Q->first->next->data; }
void Add(Queue *Q) //добавление элемента
{
int value;
cout<<"\nЗначение > "; cin>>value;
Q->last->next=new Node;
Q->last=Q->last->next;
Q->last->data=value; //добавление элемента в конец
Q->last->next=NULL; //обнуление указателя на следующий элемент
Q->size++;
cout<<"\nЭлемент добавлен\n\n";
}
void Delete(Queue *Q) //удаление элемента
{
Q->first=Q->first->next; //смещение указателя
Q->size--;
cout<<"\nЭлемент удален\n\n";
}
int Size(Queue *Q) //размер очереди
{ return Q->size; }
void main() //главная функция
{
setlocale(LC_ALL,"Rus");
Queue Q;
Creation(&Q);
char number;
do
{
cout<<"1. Добавить элемент"<<endl;
cout<<"2. Удалить элемент"<<endl;
cout<<"3. Вывести верхний элемент"<<endl;
cout<<"4. Узнать размер очереди"<<endl;
cout<<"0. Выйти\n\n";
cout<<"Номер команды > "; cin>>number;
switch (number)
{
case '1': Add(&Q);
break;
//-----------------------------------------------
case '2':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else Delete(&Q);
break;
//-----------------------------------------------
case '3':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else { cout<<"\nНачальный элемент: "<<Top(&Q)<<"\n\n"; }
break;
//-----------------------------------------------
case '4':
if (Full(&Q)) cout<<endl<<"Очередь пуста\n\n";
else cout<<"\nРазмер очереди: "<<Size(&Q)<<"\n\n";
break;
//-----------------------------------------------
case '0': break;
default: cout<<endl<<"Команда не определена\n\n";
break;
}
} while(number!='0');
system("pause");
}
|