 |
Описание организации структур данных
|
|
|
|
Для реализации стека, очереди и дека созданы структуры steck,qucue и дек имеющие следующие поля.
В стеке:
1) поле а – информационное поле;
2) поле pred – поле указатель на предыдущий элемент.
В очереди:
1) поле а – информационное поле;
2) поле next – поле указатель на следующий элемент.
В деке:
1) поле а – информационное поле;
2) поле pred – поле указатель на предыдущий элемент;
3) поле next – поле указатель на следующий элемент.
Структура р является текущим элементом. Структура top головным элементом.
Описание алгоритма
Создание стека:
1) Создаем головной элемент;
2) Создаем текущий элемент поле указатель, которого указывает на головной элемент;
3) Текущий элемент становится головным.
Добавление элемента в начало:
1) Осуществляем переход в начало стека;
2) Поле указатель первого элемента заносим адрес добавляемого элемента;
Добавление элемента в конец:
1) Поле указатель добавляемого элемента заносим адрес головы стека.
Добавление элемента середину:
1) Осуществляем переход в середину;
2) Поле указатель добавляемого элемента заносим адрес первого элемента;
3) Поле указатель третьего элемента заносим адрес добавляемого элемента.
Удаление первого элемента:
1) Переходим в начало стека;
2) Поле указатель второго элемента заносим 0;
3) Удаляем элемент.
Удаление последнего элемента:
1) Предыдущий элемент становится головным;
2) Удаляем элемент.
Удаление элемента из середины:
1) Осуществляем, переходим в середину;
2) Поле указатель следующего элемента заносим адрес, хранящийся в поле указателя удаляемого элемента;
3) Удаляем элемент.
Формальное описание входных и выходных данных
Входными данными являются:
|
|
|
1) Размер стека;
2) Элементы стека;
3) Добавляемый элемент;
4) Удаляемый элемент.
Выходными данными являются:
1) Содержимое стека.
Аналогично для очереди и дека.
Описание диалога
При запуске программы создается стек и появляется окно, в которой перечислены операции над стеком. (Рис.1)
Потом выбираем нужный нам пункт к примеру, я выбрал 1 и нажимаем Enter. И сразу внизу появляется запись «введите элемент» водим элемент который мы хотим занести в стек. (рис.2)
Выбираем 2 пункт «Удалить элемент». Рис.3
Выбираем 4 пункт «Поиск элемента в стеке». Если веденный пользователем элемент присутствует в стеке, выводится сообщение о нахождении. Рис.4
Аналогично для очереди и дека.
Описание процедур и функций
В программе были использованы функции, хранящиеся в заголовочных файлах. Список заголовочных файлов из стандартной библиотеки C++, используемых в программе (в описании приведены функции, использующиеся в данной программе):
· iostream – в ней реализована поддержка для файлового ввода/вывода данных встроенных типов. Операции ввода/вывода выполняются с помощью классов istream (потоковый ввод) и ostream (потоковый вывод). Третий класс, iostream, является производным от них и поддерживает двунаправленный ввод/вывод.
Так же были написаны собственные функции для реализации алгоритмов сжатия:
1. void vivod() – вывод стека;
2. void addToTop() – добавление элемента в начало;
3. void addToPos() – добавление элемента в указанную позицию;
4. void delet() – удаление элемента;
5. void poisk() – поиск элемента в стеке.
Результаты
Рис.1
Рис.2
Рис.3
Рис.4
ЗАКЛЮЧЕНИЕ
Развитие вычислительной техники и программирования сопровождалось эволюцией представлений о роли данных, взглядов на их организацию. В большинстве случаев одним из доминирующих свойств компьютеров является способность хранить огромные объемы информации, к которым можно просто обратиться. Информация, подлежащая обработке, в некотором смысле представляет абстракцию некоторого фрагмента реального мира. Мы говорим о данных как об абстрактном представлении реальности, поскольку некоторые свойства и характеристики реальных объектов при этом игнорируются (как несущественные для данной задачи).
|
|
|
В данной курсовой работе было рассмотрено стековый способ организации данных, организация данных очередью и деком. Также были рассмотрены создание стека, очереди и дека. Добавление элемента, удаление элемента, поиск элемента. Данные способы организации данных в основном применятся в различных алгоритмах(поиск в глубину, полный перебор).
Приложение 1
#include <iostream>
#include <conio.h>
using namespace std;
struct stack
{
int a;
stack *pred;
};
void postr(stack *&top, int size)
{
int x;
for (int i = 1; i <= size; i++)
{
if (top == NULL)
{
top = new stack;
cout << "Введите значение:";
cin >> x;
top->a = x;
top->pred = NULL;
}
else
{
stack *p = new stack;
std::cout << "Введите значение след. элемента:";
std::cin >> x;
p->a = x;
p->pred = top;
top = p;
}
}
}
void vivod(stack *top, int size)
{
stack *p = top;
cout << "stack:";
while (p!= NULL){
cout << p->a;
p = p->pred;
}
cout << endl;
}
void addToTop(stack *&top, int &size)
{
size = size + 1;
stack *p = new stack;
int dz;
cout << "\nДобавить элемент в начало:";
cin >> dz;
p->a = dz;
p->pred = top;
top = p;
}
void addToPos(stack *&top, int size){
stack *p = top;
stack* newElem = new stack;
int pos;
cout << "На какую позицию вы хотите вставить элемент?" << endl;
cin >> pos;
if ((pos - size) > 1){ //Если пользователь введет позицию, больше чем размер стека
pos = size + 1;
}
if (pos == 1){
addToTop(top, size);
return;
}
cout << "Введите значение 'a' элемента:";
cin >> newElem->a;
for (int i = 1; i <= pos - 2; i++){
p = p->pred;
}
newElem->pred = p->pred;
p->pred = newElem;
}
void delet(stack *&top, int size)
{
stack *p = top;
cout << "\nудалить элемент из позиции: ";
int delPos;
cin >> delPos;
if (delPos < 1 || delPos > size){ //Если будет введена недопустимая позиция
cout << "Недопустимая позиция. Выход из функции..." << endl;
return;
}
if (delPos == 1){
cout << "Удаляем голову..." << endl;
top = top->pred;
delete p;
return;
}
for (int i = 1; i <= delPos - 2; i++){
p = p->pred;
}
stack *boof = p->pred;
p->pred = boof->pred;
delete boof;
}
void poisk(stack *&top, stack *&p)
{
std::cout << "\nВедите искомое значение:";
int b;
std::cin >> b;
|
|
|
p = top;
while (p)
{
if (p->a == b)
{
std::cout << "\nДанный элемен присуствует в стеке"<<std::endl;
break;
}
p = p->pred;
}
if (p == NULL)
{
std::cout << "\nЭлемент ненайден" << std::endl;
}
}
int main()
{
setlocale(LC_ALL, "Russian");
int size;
cout << "Стек состоит из:" <<endl;
std::cin >> size;
stack *top = NULL;
stack*p = NULL;
postr(top, size);
system("cls");
vivod(top, size);
char number;
do
{
cout << "1. Добавить элемент" << endl;
cout << "2. Удалить элемент" << endl;
cout << "3. Добавить элемент в начало " << endl;
cout << "4. поиск элемента в очереди " << endl;
cout << "0. Выйти" << endl;
cout << "Номер команды > "; cin >> number;
switch (number)
{
case '1': addToPos(top, size);
vivod(top, size);
break;
case '2': delet(top, size);
vivod(top, size);
break;
case '3': addToTop(top, size);
vivod(top, size);
break;
case'4': poisk(top,p);
case'0': break;
default: cout << endl << "Команда не определена\n\n";
break;
}
} while (number!= '0');
//_getch();
return 0;
}
Приложение 2
#include<iostream>
#include<conio.h>
#include<Windows.h>
using namespace std;
struct qucue
{
int a;
qucue *next;
};
void postr(qucue *&top, int size)
{
int x;
qucue *tail = NULL;
for (int i = 1; i <= size; i++)
if (top == NULL)
{
top = new qucue;
std::cout << "Ведите главный элемент:";
std::cin >> x;
top->a = x;
top->next = NULL;
tail = top;
}
else
{
qucue *p = new qucue;
std::cout << "Ведите значение:";
std::cin >> x;
p->a = x;
p->next = NULL;
tail->next = p;
tail = p;
}
}
void vivod(qucue *&top,int &size)
{
qucue *p = top;
cout << "qucue:";
for (int i = 1; i <=size; i++)
{
std::cout << p->a;
p = p->next;
}
cout << std::endl;
}
void addToTop(qucue *&top, int &size)
{
size = size + 1;
qucue*p = new qucue;
int dz;
std::cout << "\nДобавить элемент в начало:";
std::cin >> dz;
p->a = dz;
p->next = top;
top = p;
}
void addToPos(qucue *&tail,qucue *&top, int &size){
qucue *p = top;
qucue* newElem = new qucue;
int pos;
std::cout << "На какую позицию вы хотите вставить элемент?" << std::endl;
std::cin >> pos;
if ((pos - size) > 1){ //Если пользователь введет позицию, больше чем размер
pos = size + 1;
}
if (pos == 1){
tail->next = p;
tail = p;
return;
}
std::cout << "Введите значение 'a' элемента:";
std::cin >> newElem->a;
for (int i = 1; i <= pos - 2; i++){
p = p->next;
}
newElem->next = p->next;
p->next = newElem;
}
void delet(qucue *&top, int &size)
{
qucue *p = top;
|
|
|
std::cout << "\nудалить элемент из позиции: ";
int delPos;
std::cin >> delPos;
if (delPos < 1 || delPos > size){ //Если будет введена недопустимая позиция
std::cout << "Недопустимая позиция. Выход из функции..." << std::endl;
return;
}
if (delPos == 1){
std::cout << "Удаляем голову..." << std::endl;
top = top->next;
delete p;
size = size - 1;
return;
}
for (int i = 1; i <= delPos - 2; i++){
p = p->next;
}
qucue *boof = p->next;
p->next = boof->next;
delete boof;
size = size - 1;
}
void poisk(qucue *&top, qucue *&p)
{
std::cout << "\nВедите искомое значение:";
int b;
std::cin >> b;
p = top;
while (p)
{
if (p->a == b)
{
std::cout << "\nДанный элемен присуствует в очереди";
break;
}
p = p->next;
}
if (p == NULL)
{
std::cout << "\nЭлемент ненайден";
}
}
int main()
{
setlocale(LC_ALL, "Russian");
int size;
std::cout << "Очередь состоит из:";
std::cin >> size;
qucue *tail = NULL;
qucue *top = NULL;
qucue *p = NULL;
postr(top, size);
system("cls");
vivod(top, size);
char number;
do
{
cout << "1. Добавить элемент" << endl;
cout << "2. Удалить элемент" << endl;
cout << "3. Добавить элемент в начало " << endl;
cout << "4. поиск элемента в очереди " << endl;
cout << "0. Выйти" << endl;
cout << "Номер команды > "; cin >> number;
switch (number)
{
case '1': addToPos(tail, top, size);
vivod(top, size);
break;
case '2': delet(top, size);
vivod(top, size);
break;
case '3': addToTop(top, size);
vivod(top, size);
break;
case'4': poisk(top, p);
case'0': break;
default: cout << endl << "Команда не определена\n\n";
break;
}
} while (number!= '0');
//_getch();
return 0;
}
Приложение 3
#include <iostream>
#include <conio.h>
using namespace std;
struct decue
{
int a;
decue *pred;
decue *next;
};
void postr(decue *&tail, decue *&top, int size)
{
int x;
for (int i = 1; i <= size; i++)
if (top == NULL)
{
top = new decue;
top->pred = NULL;
top->next = NULL;
std::cout << "Vedite pervoe znachenie:";
std::cin >> x;
top->a = x;
tail = top; //На данном этапе и хвост и голова указывают на один и тот же элемент
}
else
{
decue *p = new decue;
cout << "Vedite znachenie:";
cin >> x;
p->a = x;
tail->pred = p;
p->pred = NULL;
p->next = tail;
tail = p;
}
}
void vivod(decue *&top, int size)
{
decue *p = top;
cout << "deque:";
while (p!= NULL){
cout << " " << p->a;
p = p->pred;
}
}
void add(decue *&top, int &size)
{
decue *p = new decue;
int dz;
cout << "\nдобавить число в начало:";
cin >> dz;
size = size + 1;
p->a = dz;
p->pred = top;
p->next = NULL;
top->next = p;
top = p;
}
void addToPos(decue *&tail, decue *&top, int &size){
decue *p = top;
decue* newElem = new decue;
int pos;
std::cout << "\nНа какую позицию вы хотите вставить элемент?" << std::endl;
std::cin >> pos;
if ((pos - size) > 1){ //Если пользователь введет позицию, больше чем размер
pos = size + 1;
}
if (pos == 1){
add(top, size);
return;
}
std::cout << "Введите значение 'a' элемента:";
std::cin >> newElem->a;
for (int i = 1; i <= pos - 2; i++){
p = p->pred;
}
newElem->pred = p->pred;
newElem->next = p->next;
p->pred = newElem;
}
void delet(decue *&top, int &size)
{
decue*p = top;
|
|
|
std::cout << "\nудалить элемент из позиции: ";
int delPos;
std::cin >> delPos;
if (delPos < 1 || delPos > size){ //Если будет введена недопустимая позиция
std::cout << "Недопустимая позиция. Выход из функции..." << std::endl;
return;
}
if (delPos == 1){
std::cout << "Удаляем голову..." << std::endl;
top = top->next;
delete p;
size = size - 1;
return;
}
for (int i = 1; i <= delPos - 2; i++){
p = p->pred;
}
decue *boof = p->pred;
p->pred = boof->pred;
p->next = boof->next;
delete boof;
size = size - 1;
}
int main()
{
setlocale(LC_ALL, "Russian");
decue *top = NULL;
decue *tail = NULL; //Хвост
int size;//размер
cout << "Сколько элементов в деке:";
cin >> size;
postr(tail, top, size);
system("cls");
vivod(top, size);
cout << endl;
char number;
do
{
cout << "1. Добавить элемент" << endl;
cout << "2. Удалить элемент" << endl;
cout << "3. Добавить элемент в начало " << endl;
cout << "0. Выйти" << endl;
cout << "Номер команды > "; cin >> number;
switch (number)
{
case '1': addToPos(tail, top, size);
vivod(top, size);
cout << endl;
break;
case '2': delet(top, size);
vivod(top, size);
cout << endl;
break;
case '3': add(top, size);
vivod(top, size);
break;
case'0': break;
default: cout << endl << "Команда не определена\n\n";
break;
}
} while (number!= '0');
return 0;}
Список литературы
1. Айламазян А. К., Информатика и теория развития. - М.: Наука, 1992.
2. Говорухин В. Н., Цибулин В. Г. Компьютер в математическом исследовании. \ Учебный курс. - СПб.: Питер, 2001.
3. Гук М.Ю. Процессоры Intel от 8086 до Pentium II. СПб.: Питер, 1997
5. Данчула А. Н. Информатика Издательство РАГС, 2004- 528
6. Дьяконов В. П. Компьютерная математика. Теория и практика. /В. П. Дьяконов. - М. 2001.
7.Зелковиц М. Языки программирования: разработка и реализация
8. Каймин В.А. Информатика: Учебник. - М.: ИНФРА-М,2000. - 232 с. - (Серия «Высшее образование»).
9. Могилев А. В., Пак Н. И., Хеннер Е. К., Информатика, М., «Академия», 2004.
10. Нортон П., Соухэ Д. Язык ассемблера для IBM PC. М.: Компьютер, 1992.
11. Павловская Т. А. С/С++. Программирование на языке высокого уровня. Питер - 2005.
|
|
|
