Динамические структуры данных 5

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

Уральский федеральный университет имени первого Президента России Б.Н. Ельцина

Кафедра вычислительных методов и уравнений математической физики

Оценка работы

Преподаватель

Динамические структуры данных

Подпись Дата Ф.И.О.

Преподаватель _ Трясцина Т. С.

Студент _ Запалацкий В. С.

Группа Р-190901

Екатеринбург 2010

СОДЕРЖАНИЕ

ВВЕДЕНИЕ……………………………………………………………………………………..3

1. ПОСТАНОВКА ЗАДАЧИ………………………………….……………………………….4

2. ТЕРЕТИЧЕСКАЯ ЧАСТЬ………………………………………………………………….5

3. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ………………………………………………………..7

4. ИНСТРУКЦИЯ ПРОГРАММИСТА………………………………………….……………8

5. МЕТОДИКА И РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ……………………………………..9

ЗАКЛЮЧЕНИЕ………………………………………………………………………………..12

ПРИЛОЖЕНИЕ. ТЕКСТ ПРОГРАММЫ…………………………………………………..13

БИБЛИОГРАФИЧЕСКИЙ СПИСОК……………………………………………………….20

введение

Данная программа была разработана для изучения динамических структур данных таких, как стек, очередь и список. Применение их для решения практических задач. Создание графического интерфейса.

На сегодняшний день существует много средств для визуального проектирования программ, наиболее известные из них: Visual Studio (последняя версия 10.0) и Borland C++ Builder. В основе этих сред программирования лежит технология визуального проектирования и событийного программирования, суть которой заключается в том, что среда разработки берет на себя большую часть работы по генерации кода программы, остав­ляя автору работу по конструированию диалоговых окон и написа­нию функций обработки событий, благодаря этому скорость разработки программ возрастает.

1. постановка задачи

Текст помощи для некоторой программы организован в виде линейного списка.Каждая компонента текста помощи содержит термин(слово) и текст,содержащий пояснения к этому термину.Количество строк текста , относящихся к одному термину состовляет от одной до пяти.Написать программу ,которая обеспечивает : Начальное формирование текста помощи; вывод пояснительного текста для заданного термина.Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе
2. теоретическая часть

Динамические структуры данных

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

В таких случаях применяют данные особои? структуры, которые представляют собои? отдельные элементы, связанные с помощью ссылок. Каждыи? элемент (узел) состоит из двух областеи? памяти: поля данных и ссылок. Ссылки – это адреса других узлов этого же типа, с которыми дан- ныи? элемент логически связан. В языке Си для организации ссылок используются переменные- указатели. При добавлении нового узла в такую структуру выделяется новыи? блок памяти и (с помощью ссылок) устанавливаются связи этого элемента с уже существующими. Для обозна- чения конечного элемента в цепи используются нулевые ссылки (NULL).

Всего существует 6 основных видов динамических структур данных :

1Стек

2Очередь

3Хэш таблица

4Список (односвязный, двусвязный, циклический)

5Дерево

6Граф

Список

Существует 3 вида списков :

1односвязный (линейный)

2двусвязный

3циклический

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

Двусвязный список.

Многие проблемы при работе с односвязным списком вызваны тем, что в них невозможно переи?ти к предыдущему элементу. Возникает естественная идея – хранить в памяти ссылку не только на следующии?, но и на предыдущии? элемент списка. Для доступа к списку используется не одна переменная-указатель, а две – ссылка на «голову» списка (Head) и на «хвост» - последнии? элемент (Tail).

Очередь

Очередь – это упорядоченныи? набор элементов, в котором добавление новых элементов до-

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

Хорошо знакомои? моделью является очередь в магазине. Очередь называют структурои? типа FIFO (First In – First Out) – первым пришел, первым ушел. На рисунке изображена очередь из 3-х элементов.

Стек

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

Стек называют структурои? типа LIFO (Last In – First Out) – последним пришел, первым ушел. Стек похож на стопку с подносами, уложенными один на другои? – чтобы достать какои?-то под- нос надо снять все подносы, которые лежат на нем, а положить новыи? поднос можно только сверху всеи? стопки. На рисунке показан стек, содержащии? 6 элементов.

В современных компьютерах стек используется для :

1размещения локальных переменных

2размещения параметров процедуры или функции

3сохранения адреса возврата (по какому адресу надо вернуться из процедуры)

4временного хранения данных, особенно при программировании на Ассемблере

5

На стек выделяется ограниченная область памяти. При каждом вызове процедуры в стек добавляются новые элементы (параметры, локальные переменные, адрес возврата). Поэтому если вложенных вызовов будет много, стек переполнится. Очень опаснои? в отношении переполнения стека является рекурсия, поскольку она как раз и предполагает вложенные вызовы однои? и тои? же процедуры или функции. При ошибке в программе рекурсия может стать бесконечнои?, кроме того, стек может переполниться, если вложенных вызовов будет слишком много.

3. инструкция пользователя

Программа выполнена как консольное приложение. В начале запускается файл практика.exe,после запуска появляется главное окно программы(Рис.1):

Рис.1. Главное окно программы

4. инструкция программиста

Исходный текст организован в одном файле практика.cpp;

Используються следующие заголовочные файлы:

windows.h – для описания структур и функция WinAPI;

iostream.h – для вывода на консоль информации о ходе работы, диагностики и сообщений об ошибки

conio.h – для использования функций ввода

Основные функции программы:

void add() – функция добавления.

void prosmotr() – функция для просмотра всего текста

void find_number_poisk(char * search)– функция поикак

void prosmotr1() – функция функция для просмотра одного термина

void print_ukazat – функция выделения указателя в меню

void bd() – функция читает базу данных с файла

void save_bd()-функция сохраняет файл в структуру

5. методика и результаты тестирование

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

Рис. 3 На рисунке представлены копируемые файлы.

Рис. 6 На рисунке представлена ошибочный ввод данных.

В результате тестирования был сделан вывод, о корректности работы разработанного программного обеспечения. Было установлено , что поставленные цели были достигнуты.

заключение

В результате проделанной работы было создано консольное Win32 приложение для по секторного копирования дискеты. Поставленная задача была реализована, также было проведено тестирование которое показало работоспособность программы. Программа является примером использования Windows API функций. За время выполнения курсового проекта были закреплены знания по программированию на языке С++ в среде Borland C++Builder 6, а также дополнительно освоены некоторые Windows API функций.

ПРИЛОЖЕНИЕ. ТЕКСТ ПРОГРАММЫ

copsector.cpp

#pragma hdrstop

#include<iostream.h>

#include<windows.h>

#include<conio.h>

//---------------------------------------------------------------------------

#pragma argsused

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

typedef char CHAR;

typedef CHAR *PCHAR;

PCHAR *buf;

DWORD dwSectPerClust =0; //количество секторов в кластере

DWORD dwBytesPerSect =0; //количество байт в секторе

DWORD dwNumbFreeClust =0;//количество свободных кластеров

DWORD dwTotalNumbOfClust =0; //общее количество кластеров

void PrintError()

{

char str[256];

LPVOID lpMsgBuf;

FormatMessage(

FORMAT_MESSAGE_ALLOCATE_BUFFER |

FORMAT_MESSAGE_FROM_SYSTEM |

FORMAT_MESSAGE_IGNORE_INSERTS,

NULL,

GetLastError(),

MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),

(LPTSTR) &lpMsgBuf,

0,

NULL

);

CharToOem((LPCSTR)lpMsgBuf, str);

cout<<str<<endl;

}

void PrintInfoDrive(LPCTSTR lpDriveName = "A:\")

{

GetDiskFreeSpace(

lpDriveName,

&dwSectPerClust,

&dwBytesPerSect,

&dwNumbFreeClust,

&dwTotalNumbOfClust

);

printf("Drive name: %sn", lpDriveName);

cout<<"SectorsPerClustre: "<< dwSectPerClust<<endl;

cout<<"BytesPerSector: "<<endl <<dwBytesPerSect<<endl;

cout<<"NumberFreeOfCluster: "<< dwNumbFreeClust<<endl; //

cout<<"TotalNumberOfCluster: "<< dwTotalNumbOfClust<<endl; //

cout<<"------------------------------------"<<endl;

DWORD dwTotalSize = dwBytesPerSect * dwNumbFreeClust;

cout<<"Free space: "<<(dwTotalSize/1024)<<" kb"<<endl;// размер свободного места в kB

}

void funMemory(){

//cout<<"Vpamat zahodit";

buf = new PCHAR[dwTotalNumbOfClust*dwSectPerClust];

for(int i=0;i<dwTotalNumbOfClust*dwSectPerClust;i++)

buf[i] = new char[dwBytesPerSect];

}

void funFree(){

for(int i=0;i<dwTotalNumbOfClust*dwSectPerClust;i++)

delete[] buf[i];

delete[] buf;

//cout<<"Udaleno udachno";

}

int ReadSector(LPCSTR lpDriveName_1) // для открытия доступа к диску А

{

OSVERSIONINFO verInfo = {0};

verInfo.dwOSVersionInfoSize = sizeof (verInfo);

GetVersionEx(&verInfo);

UINT sector;

HANDLE hDrive_1;

DWORD dw, n;

switch (verInfo.dwPlatformId)

{

case VER_PLATFORM_WIN32_NT:

hDrive_1 = CreateFile(

lpDriveName_1,

GENERIC_READ,

FILE_SHARE_READ,

NULL,

OPEN_EXISTING,

FILE_ATTRIBUTE_NORMAL,

NULL

);

if (hDrive_1 == INVALID_HANDLE_VALUE)

{

PrintError();

return 1;

}

for(sector=1;sector<dwTotalNumbOfClust*dwSectPerClust+1;sector++){

if((SetFilePointer(hDrive_1, (sector-1) * dwBytesPerSect, NULL, FILE_BEGIN))==-1){ //устанавливает позицию чтения сектора

PrintError(); //функция обработки ошибок

return 1;

};

if((ReadFile(hDrive_1, (LPVOID)buf[sector-1], dwBytesPerSect, &dw, NULL))==false){ //производит чтение сектора

PrintError();

return 1;

};

}

CloseHandle(hDrive_1);

break;

case VER_PLATFORM_WIN32_WINDOWS:

break;

default:

printf ("Error!!!n");

return 1;

}

return 0;

}

int WriteSector(LPCSTR lpDriveName_2) // для открытия доступа к диску А

{

OSVERSIONINFO verInfo = {0};

verInfo.dwOSVersionInfoSize = sizeof (verInfo);

GetVersionEx(&verInfo);

UINT sector;

HANDLE hDrive_2;

DWORD dw, n;

switch (verInfo.dwPlatformId)

{

case VER_PLATFORM_WIN32_NT:

hDrive_2 = CreateFile(

lpDriveName_2,

GENERIC_WRITE,

FILE_SHARE_WRITE,

NULL,

OPEN_EXISTING,

FILE_ATTRIBUTE_NORMAL,

NULL

);

if (hDrive_2 == INVALID_HANDLE_VALUE)

{

PrintError();

return 1;

}

for(sector=1;sector<dwTotalNumbOfClust*dwSectPerClust+1;sector++){

if((SetFilePointer(hDrive_2, (sector-1) * dwBytesPerSect, NULL, FILE_BEGIN))==-1){ //устанавливает позицию чтения сектора

PrintError(); //функция обработки ошибок

return 1;

};

if((WriteFile(hDrive_2, (LPVOID)buf[sector-1], dwBytesPerSect, &dw, NULL))==false){ //производит запись сектора

PrintError();

return 1;

};

}

CloseHandle(hDrive_2);

MessageBox(NULL,"Копирование закончено успешно","Диск А",MB_OK);

break;

case VER_PLATFORM_WIN32_WINDOWS:

break;

default:

printf ("Error!!!n");

return 1;

}

return 0;

}

int main(int argc, char* argv[])

{

char pop1[]="\\.\A:";

char pop2[]="\\.\A:";

char faf1[]="A:\";

char faf2[]="A:\";

int i=0;

clrscr();

while(1){

cout<<"nn-------------PROGRAMMA POSECTORNOGO KOPIROVANIA DISKETI------------------nn";

cout<<"nnVvedite nazvanie disketi(A ili B) otkuda kopirovat: ";

cin>>pop1[4];

if(pop1[4]=='A' || pop1[4]=='a' || pop1[4]=='B'|| pop1[4]=='b')

break;

clrscr();

cout<<"nnBukva "<<pop1[4]<<" nesootvetstvuet bukve (A ili B)";

}

while(1){

cout<<"nnVvedite nazvanie disketi(A ili B) kuda kopirovat: ";

cin>>pop2[4];

if(pop2[4]=='A' || pop2[4]=='a' || pop2[4]=='B'|| pop2[4]=='b')

break;

clrscr();

cout<<"nnBukva "<<pop2[4]<<" nesootvetstvuet bukve (A ili B)";

}

cout<<"Copiruemi disk "<<pop1[4]<<" pered kopirovaniem: n";

faf1[0]=pop1[4];

faf2[0]=pop2[4];

PrintInfoDrive(faf1);

funMemory();

i=ReadSector(pop1);

if(i){

MessageBox(NULL,"Ошибка чтения","Копироваине диска",MB_OK);

exit(1);

}

MessageBox(NULL,"Вставте следующую дискету","Копироваине диска",MB_OK);

i=WriteSector(pop2);

if(i){

MessageBox(NULL,"Ошибка записи","Копироваине диска",MB_OK);

exit(1);

}

cout<<"nnnCopia diska: "<<pop1[4]<<" v diske :"<<pop2[4]<<endl ;

funFree();

PrintInfoDrive(faf2);

getch();

return 0;

}

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Страуструп Б. Язык программирования C++. Специальное издание. Пер. с англ. – М.: ООО «Бином-Пресс», 2006 г. – 1104 с.: ил.

2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. Пер. с англ. Под редакцией А. Шеня. – М.: МЦНМО: БИНОМ. Лаборатория знаний, 2006. – 3-е изд., стереотип. – 1096 с.: 263 ил.

3.

4. MSDN Library 2005 [Электронный ресурс] – Microsoft Software Developer Network Library – опт. диск(DVD-ROM) - Загл. с этикетки диска.