Шаблон иерархической структуры данных в памяти

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

Брянский государственный технический университет

Кафедра «Информатика и программное обеспечение»

Пояснительная записка к курсовой работе

по дисциплине «Объектно-ориентированное программирование»

Шаблон иерархической структуры данных в памяти

Выполнил:

студ. гр. 11-ПРИ

Самоделко А.С.

Руководитель:

доц. каф. ИиПО

Израилев В.Я.

Брянск 2012



Оглавление

программирование массив сортировка элемент

1. Задание для курсовой работы

2. История ООП

3. Основные приемы, используемые в работе

Заключение



1. Задание для курсовой работы

Для заданной двухуровневой структуры данных, содержащей указатели на объекты (или сами объекты) - параметры шаблона, разработать полный набор операций (добавление, включение и извлечение по логическому номеру, сортировка, включение с сохранением порядка, загрузка и сохранение строк в текстовом файле, балансировка - выравнивание размерностей структур данных нижнего уровня). Предполагается, что операции сравнения хранимых объектов переопределены стандартным образом (в виде операций <,> и т.д.). Программа должна использовать шаблонный класс с объектами - строками и реализовать указанные выше действия над текстом любого объема, загружаемого из файла.

Основное задание:

Шаблон структуры данных - массив указателей на заголовки списков. Элемент списка содержит указатель на строку. (При включении последним предусмотреть ограничение длины текущего списка и переход к следующему).

2. История ООП

На заре появления вычислительных машин программирование, как область знания, находилось в зачаточном состоянии. Первые программы создавались посредством переключателей на панели компьютера. Очевидно, что такой способ подходил только для небольших программ. Затем программы стали писать на языке машинных команд, а изобретение ассемблера позволило писать уже сравнительно длинные программы. Следующий шаг был сделан в 1950 году, когда был создан первый язык программирования высокого уровня Фортран.

Теперь программисты могли создавать программы длиной до нескольких тысяч строк длиной. Однако язык программирования, легко понимаемый в простых программах, когда дело касалось больших программ, становился нечитаемым (и неуправляемым). Избавление от таких неструктурированных программ пришло после изобретения в 1960 году языков структурного программирования (Алгол, Паскаль и С). Структурное программирование подразумевает точно обозначенные управляющие структуры, программные блоки отсутствие (или минимальное использование) операторов GOTO, автономные подпрограммы, в которых поддерживается рекурсия и локальные переменные. С появлением структурного программирования появилась возможность разбиения программы на составляющие ее элементы. Теперь уже один программист был в состоянии создать и поддерживать программу в несколько десятков тысяч строк диной.

Хотя структурное программирование и принесло выдающиеся результаты, даже оно оказалось несостоятельным, когда программа достигала определенной длины. Чтобы писать более сложную программу, необходим был новый подход к программированию. В итоге были разработаны принципы объектно-ориентированного программирования, которое аккумулировало лучшие идеи, воплощенные в структурном программировании, в сочетании с мощными новыми концепциями, позволяющими оптимально организовать ваши программы. ООП позволяет разложить проблему на связанные между собой задачи. Каждая проблема становится самостоятельным объектом, содержащим свои собственные коды и данные, которые относятся к этому объекту. В этом случае исходная задача в целом упрощается, и программист получает возможность оперировать с гораздо большими по объему программами.

3. Основные приемы, используемые в работе

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Ниже будут представлены листинги кода основных функций программы, с пояснениями.

Шаблон класса

С помощью классов, легко сгруппировывать информацию об объекте воедино. Класс содержит в себе член-данные и член-функции.

template <class T>

class Array

{

public:

Array();

Array(int size, int MaxSize);

~Array();

void AddElem();

void AddElem(int position);

void DelElem(int position);

void SortALL();

void ShowAll();

private:

ListElem<T> **Arr;

bool IsListFull(int index);

void Change(T a[], T first, T second);

T FindMax(T a[], int max);

void Sort(T b[], int max);

int MaxCount; //Максимальная длина списка

int CurSize; //Текущий размер односвязного списка

int ArrSize; //Размер массива указателей

int pointer; //Указатель на вставку элемента

};

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

Структура элемента списка

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



template <class T>

struct ListElem

{

T *objects;

int countObj; //Количество объектов

ListElem<T> *pNext;

};

Функция простого добавления элемента в список

Данная функция добавляет элемент на первое свободное место в списке. Так же, если нам не хватает массива указателей, она память под ещё одну ячейку и, записывает элемент в неё.

template <class T>

void Array<T>::AddElem()

{

if (CurSize==MaxCount)

{

pointer++;

CurSize=0;

}

if (pointer==ArrSize)

{

Arr[pointer]=new ListElem<T>;

Arr[pointer]=NULL;

ArrSize++;

}

int count=0;

cout<<"Enter count of elements=";

cin>>count;

if (count<=0)

{

cout<<"Non of elements"<<endl;

return;

}

ListElem<T> *NewElem = new ListElem<T>;

NewElem->countObj=count;

NewElem->objects=new T[count];

for (int i = 0; i < count; i++)

{

cout<<"Enter element=";

cin>>NewElem->objects[i];

}

ListElem<T> *cur = Arr[pointer];

if (cur==NULL)

{

Arr[pointer]=NewElem;

NewElem->pNext=NULL;

}

else

{

while(cur->pNext!=NULL)

cur=cur->pNext;

cur->pNext=NewElem;

NewElem->pNext=NULL;

}

CurSize++;

}



Функция сортировки элементов

Сортируются массивы внутри списков, по возрастанию. Для этого были написаны несколько закрытых методов класса. Первая функция Change меняет элементы местами, функция FindMax ищет в массиве максимальный элемент, а функция Sort сортирует переданный в неё массив.

void Array<T>::Change(T a[], T first, T second)

{

if (first == second)

return;

T i;

i = a[second];

a[second] = a[first];

a[first] = i;

}

template <class T>

T Array<T>::FindMax(T a[], int max)

{

T imax = 0;

for (int i = 0; i <= max; i++)

{

if (a[imax] < a[i])

imax = i;

}

return imax;

}

template <class T>

void Array<T>::Sort(T b[], int max)

{

int i1;

for (int i = max - 1; i > 0; i--)

{

i1 = FindMax(b, i);

Change(b, i, i1);

}

}

template <class T>

void Array<T>::SortALL()

{

ListElem<T> *cur=0;

for (int i = 0; i<ArrSize; i++)

{

cur = Arr[i];

while(cur!=NULL)

{

Sort(cur->objects,cur->countObj);

cur=cur->pNext;

}

}

}

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

template <class T>

void Array<T>::ShowAll()

{

ListElem<T> *cur=0;

ListElem<T> *pcur=0;

for (int i = 0; i<ArrSize; i++)

{

cout<<" <<< Next Pointer-> >>> \n";

cur = Arr[i];

pcur = Arr[i];

while(cur!=NULL)

{

cout<<"Elem=";

for(int j=0; j<cur->countObj; j++)

{

cout<<cur->objects[j]<<" ";

}

cout<<"\n <<< Next list-> >>> \n";

cur=cur->pNext;

}

cout<<endl;

cout<<endl;

cout<<endl;

cout<<endl;

}

}

Функция добавления элемента по позиции

Элемент добавляется в указанную пользователем позицию, т.к. нумерация списков считается сквозной. Если позиция, которую указал пользователь слишком большая, то элемент просто добавляется в конец уже имеющегося списка.

template <class T>

void Array<T>::AddElem(int position)

{

int index = 0;

while (position>MaxCount)

{

index++;

position-=MaxCount;

}

ListElem<T>*pcur=Arr[index];

if (pcur==NULL)

{

int count=0;

cout<<"Enter count of elements=";

cin>>count;

if (count<=0)

{

cout<<"Non of elements"<<endl;

return;

}

ListElem<T> *NewElem = new ListElem<T>;

NewElem->countObj=count;

NewElem->objects=new T[count];

for (int i = 0; i < count; i++)

{

cout<<"Enter element=";

cin>>NewElem->objects[i];

}

Arr[index]=NewElem;

NewElem->pNext=NULL;

CurSize++;

return;

}

if (index>=ArrSize)

{

AddElem();

return;

}

if (IsListFull(index))

{

if(index==MaxCount)

{

ListElem<T> *pcur=0;

for(pcur;pcur->pNext!=NULL;pcur=pcur->pNext);

int count=0;

cout<<"Enter count of elements=";

cin>>count;

if (count<=0)

{

cout<<"Non of elements"<<endl;

return;

}

ListElem<T> *NewElem = new ListElem<T>;

NewElem->countObj=count;

NewElem->objects=new T[count];

for (int i = 0; i < count; i++)

{

cout<<"Enter element=";

cin>>NewElem->objects[i];

}

pcur->pNext=NewElem;

NewElem->pNext=NULL;

CurSize++;

return;

}

}

if (position==1)

{

int count=0;

cout<<"Enter count of elements=";

cin>>count;

if (count<=0)

{

cout<<"Non of elements"<<endl;

return;

}

ListElem<T> *NewElem = new ListElem<T>;

NewElem->countObj=count;

NewElem->objects=new T[count];

for (int i = 0; i < count; i++)

{

cout<<"Enter element=";

cin>>NewElem->objects[i];

}

ListElem<T> *cur=Arr[index];

NewElem->pNext=cur->pNext;

Arr[index]=NewElem;

CurSize++;

return;

}

else

{

int count=0;

cout<<"Enter count of elements=";

cin>>count;

if (count<=0)

{

cout<<"Non of elements"<<endl;

return;

}

ListElem<T> *NewElem = new ListElem<T>;

NewElem->countObj=count;

NewElem->objects=new T[count];

for (int i = 0; i < count; i++)

{

cout<<"Enter element=";

cin>>NewElem->objects[i];

}

ListElem<T>*cur=Arr[index];

ListElem<T>*pcur=Arr[index];

count=0;

for(cur,pcur;cur!=NULL && count<position-2;)

{

count++;

cur=cur->pNext;

pcur=pcur->pNext;

}

if (cur==NULL)

{

pcur->pNext=NewElem;

CurSize++;

return;

}

else

{

NewElem->pNext=cur->pNext;

pcur->pNext=NewElem;

CurSize++;

return;

}

}

}

Функция удаления элемента с заданной позиции

В данной функции пользователь вводит позицию, с которой он хочет удалить элемент.

template <class T>

void Array<T>::DelElem(int position)

{

int ALL = MaxCount*ArrSize;

if (position>ALL || position<0)

{

cout<<"Нет элемента в этой позиции"<<endl;

system("pause");

return;

}

int index = 0;

while (position>MaxCount)

{

index++;

position-=MaxCount;

}

if (IsListFull(index) && position==MaxCount)

{

int curr=0;

ListElem<T> *cur=Arr[index];

if (cur->pNext!=NULL)

{

cur=cur->pNext;

}

ListElem<T> *pcur=0;

for (cur, pcur=Arr[index]; cur->pNext!=NULL;)

{

curr++;

cur=cur->pNext;

pcur=pcur->pNext;

}

if (cur->pNext==NULL)

{

delete []cur->objects;

delete cur;

pcur->pNext=NULL;

CurSize--;

}

}

else if (IsListFull(index) && position<MaxCount)

{

ListElem<T>*pcur=0;

ListElem<T>*cur=0;

ListElem<T>*temp=0;

int p=0;

pcur=cur=Arr[index];

for(cur;p!=position-1;p++)

cur=cur->pNext;

p=0;

for(pcur;p!=position-2;p++)

pcur=pcur->pNext;

temp=cur;

pcur->pNext=cur->pNext;

temp->pNext=NULL;

delete []temp->objects;

delete temp;

CurSize--;

}

else if (position==1)

{

ListElem<T>*cur=Arr[index];

ListElem<T>*pcur=Arr[index];

ListElem<T>*temp=Arr[index];

temp=temp->pNext;

pcur->pNext=cur->pNext->pNext;

temp->pNext=NULL;

delete []temp->objects;

delete temp;

CurSize--;

}

else

{

ListElem<T>*cur=Arr[index];

ListElem<T>*pcur=Arr[index];

int count=0;

for (cur=cur->pNext, pcur; count<position; count++)

{

if (cur==NULL)

cur=Arr[index++];

if (pcur==NULL)

pcur=Arr[index];

cur=cur->pNext;

pcur=pcur->pNext;

}

if (cur->pNext!=NULL)

{

temp=cur;

pcur->pNext=cur->pNext;

temp->pNext=NULL;

delete []temp->objects;

delete temp;

CurSize--;

}

}

}

Реализация выполненной работы

Создадим изначально список с 2 ячейками массива указателей и, максимальной длиной списков 3. Добавим 8 элементов, чтобы гарантировано было переполнение массива. Пользователь вводит количество элементов и заполняет массив нужными ему элементами. В самом простом случае элементами будут числа от 1 до 9.



Рис. 1. Добавление элементов

И, видим, что всё корректно заполнилось, и выделилась новая ячейка памяти, для записи ещё трех элементов. Далее элементы выводятся на экран.

Рис. 2. Вывод полученного списка

Далее, усложним задачу, чтобы показать функцию сортировки элементов списка. Введем 9 элементов, но в каждом массиве будет разное количество данных. Первоначально неотсортированные данные показаны на следующем рисунке.



Рис. 3. Ввод элементов для сортировки

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

Рис. 4. Вывод отсортированных элементов списка



Далее протестируем функцию удаления элементов из нашего списка. Введем стандартный простой список, от 1 до 6 и удалим 2 элемента. В результате получился вот этот список.

Рис. 5. Удаление элементов из списка

И, наконец, функция добавления элементов в произвольное место в списке. Опять зададим список, но теперь добавим в него элементы по позициям. Вводим в консоль элементы, как обычно, с 1 до 6. Но, с помощью функций добавления в текущую позицию, пусть у нас должен будет вывестись список «1, 3, 2, 4, 6, 5».

Рис. 6. Нарушение упорядоченности



Как и следовало ожидать, последовательность нарушилась, поскольку, во время добавления элементов, использовались функции обычной вставки, вперемешку с функциями вставки в конкретную позицию. В данном случае, в позиции 1, но это незаметно, а вот добавление элементов 3 и 6 в соответственные позиции 2 и 5, уже видимо нарушает порядок.



Заключение

Итак, после выполнения курсовой работы, были закреплены основные приемы ООП. Приведенный пример программы позволил разобраться с алгоритмом разработки данного задания. А подробная наглядная демонстрация позволяет довольно быстро разобраться с программой.

Размещено на Allbest.ru