Файл: Алгоритмы сортировки данных (Структура и типы данных).pdf

ВУЗ: Не указан

Категория: Курсовая работа

Дисциплина: Не указана

Добавлен: 26.05.2023

Просмотров: 89

Скачиваний: 3

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Удаление элемента

Функция DeleteList для удаления элемента использует его адрес:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int DeleteList(int position)
{
if (head==NULL) { cout<<"\nСписок пуст\n\n"; return 0; }
if (head==head->next) //если это последний элемент в списке
{
delete head; //удаление элемента
head=NULL;
}
else
{
DoubleList *a=head;
for (int i=position; i>1; i--) a=a->next;
if (a==head) head=a->next;
a->prev->next=a->next; //удаление элемента
a->next->prev=a->prev;
delete a;
}
cout<<"\nЭлемент удален...\n\n";
}

Если список пуст, то выводится сообщение, извещающее об этом, и функция возвращается в место вызова.

Вывод списка

Функция PrintList выводит на экран все элементы списка:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void PrintList()
{
if (head==NULL) cout<<"Список пуст\n";
else
{
DoubleList *a=head;
cout<<"\nЭлементы списка: ";
do
{
cout<<a->data<<" ";
a=a->next;
} while(a!=head); cout<<"\n\n";
}
}

Вывести список можно и посредством цикла, то есть итеративно.

Теперь соединим эти три функции в одной программе. Если в качестве языка использовался бы Pascal, то для функционирования программы (в нашем случае интерфейса двусвязного списка) пришлось, помимо функций (процедур), написать основной блок программы (begin…end), из которого вызывались бы подпрограммы. В C++ этим блоком является функция main. Программа, реализующая простой интерфейс двусвязного списка (Приложение 8).

 От программы требуется, чтобы она выполнялась до тех пор, пока не выполнен выход из цикла do функции main (для выхода из него пользователь должен ввести 0). По этой причине в конце функции main не был описан оператор, тормозящий программу.

Заключение

Структуры данных – это абстрактные структуры или классы, которые используются для организации данных и предоставляют различные операции над этими данными.

В данной работе были описаны структуры данных всех классов памяти ЭВМ: простых, статических, полустатических, динамических и нелинейных, а также, информация о возможных операциях над всеми перечисленными структурами. С помощью операций можно организовывать поиск, сортировку и редактирование данных. Способы анализа эффективности использования структур данных важны для подсчета времени исполнения различных операций структур данных и являются полезным инструментом при выборе той или иной структуры данных для конкретной программистской задачи.


Был рассмотрен вопрос о важности структур данных и о том, как они влияют на эффективность алгоритмов. Выбор правильного представления данных служит ключом к удачному программированию и может в большей степени сказываться на производительности программы, чем детали используемого алгоритма. Для определения того, как структуры данных влияют на производительность программ, нужно рассмотреть, как можно строго проанализировать различные операции, выполняемые структурами данных. Вряд ли когда-нибудь появится общая теория выбора структур данных. 

Стоит добавить, что совокупность структур данных и операций их обработки составляет модель данных, которая является ядром любой базы данных. Модель данных представляет собой множество структур данных, ограничений целостности и операций манипулирования данными. С помощью модели данных могут быть представлены объекты предметной области и взаимосвязи между ними. База данных основывается на использовании иерархической, сетевой или реляционной модели, на комбинации этих моделей или на некотором их подмножестве. 

Список использованной литературы

  1. Могилев А. В., Пак Н. И., Хеннер Е. К., Информатика, М., «Академия», 2004.
  2. Симонович С.В., Информатика: Базовый курс, СПб: Питер, 2007.
  3. Информатика: Учебник / Под общ. ред. А.Н. Данчула. - М.: И 74 Изд-во РАГС, 2004. - 528 с.
  4. Т. Пратт, М. Зелковиц. Языки программирования: разработка и реализация = Terrence W. Pratt, Marvin V. Zelkowitz. Programming Languages: Design and Implementation. - 4-е издание. - Питер, 2002. - 688 с. - (Классика Computer Science). - 4000 экз. - ISBN 5-318-00189-0.
  5. Каймин В.А. Информатика: Учебник. - М.: ИНФРА-М,2000. - 232 с. - (Серия «Высшее образование»).
  6. Т.А. Павловская С/С++. Программирование на языке высокого уровня. Спб. Питер – 2005.
  7. Гук М.Ю. Процессоры Intel от 8086 до Pentium II. СПб.: Питер, 1997.
  8. Нортон П., Соухэ Д. Язык ассемблера для IBM PC. М.: Компьютер, 1992.
  9. Высокие интеллектуальные технологии образования и науки: Материалы Х Международной научно-методической конференции. 28 февраля - 1 марта 2003 года. Санкт-Петербург. - СПб.: Изд-во СПбГПУ, 2003.– 420 с.
  10. Новые информационные технологии: Учеб. Пособие /Под ред. В.П. Дьяконова; Смол. гос. пед. ун-т. - Смоленск. 2003. - Ч. 3: Основы математики и математическое моделирование /~В.П. Дьяконов, И.В. Абраменкова, А.А. Пеньков. - 192 с.: ил.
  11. Дьяконов В. П. Компьютерная математика. Теория и практика. /В. П. Дьяконов. - М.: Нолидж, 2001.
  12. Говорухин В. Н., Цибулин В. Г. Компьютер в математическом исследовании. \ Учебный курс. - СПб.: Питер, 2001.
  13. Айламазян А. К., Информатика и теория развития. - М.: Наука, 1992.
  14. Информатика и образование, \N5 - 1999.
  15. Грэхем Р., Кнут Д., Паташник О. Конкретная информатика. - М.: Мир, 1988.

Приложение .

Приложение 1. Программная реализация дека на основе массива:

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");
}