Программирование

Федеральное агентство  по образованию РФ

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

Курсовая работа

По дисциплине: «Программирование»

 

 

Вариант 3.3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Группа:  АВТ-910

Студент:  Радченко О.

Преподаватель: Васюткина И.А.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Новосибирск 2011

 

1. Техническое задание

3. Шаблон иерархической  структуры данных в памяти (начальный балл 4,0)

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

Шаблон структуры  данных – односвязный список, каждый элемент которого содержит статический массив указателей на объекты. Последовательность указателей в каждом массиве ограничена NULL. При переполнении текущего массива указателей создается новый элемент списка, в который переписывается половина указателей из текущего.

2. Диаграмма вариантов использования

 

 

 

 

 

 

 

 

 

 

 

 

 

                   

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Диаграмма действий

 

1.Просмотр списка

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Вывод по номеру

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Добавление элемента по номеру

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Добавление в конец списка

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6. Удаление по номеру

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7. Загрузка списка

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8. Структурное описание разработки

 

В программе описано 3 класса. Реализация списка осуществлена при помощи шаблонного класса List и вложенного класса item. Сложный тип данных (комплексные числа) описан в классе Complex, разработана полная функциональность класса.

Класс item является элементом списка. Он содержит массив указателей на элементы типа T (размерность массива (N) передается как параметр при определении списка),  численное значение int size, которое показывает, на сколько заполнен массив указателей и указатель на следующий элемент списка item *next.

Класс List содержит указатели на первый и последний элементы списка (item *First; item *Last;). В данном классе описаны все функции, работающие непосредственно со списком такие как: вставка в список, балансировка, сортировка, сохранение/загрузка из файла, извлечение из списка, информация о текущем состоянии списка, вывод всего списка на экран и удаление списка.

 

Диаграмма классов

 

class List {             int kol; public: class item     { public: int size; T * data; item *next; } item *First; item *Last;             void Info (); void Add (T);             void Split (item*); void ShowElement (int); void DelElem (int); void DelList (); void Insert (T, int); void Sort (); void Save (char*); void Load (char*);             void Balance (); };

class Complex {  public: Complex operator +(Complex);             Complex operator - (Complex); Complex operator / (Complex); Complex operator *(Complex); Complex operator *(Complex);             Complex operator =(const Complex);             Complex operator =(const int);               bool operator > (Complex);             bool operator < (Complex);             bool operator == (Complex);             bool operator != (Complex);             bool operator == (int);             bool operator != (int);   ostream& operator << (ostream& , Complex);             istream& operator >>(istream&, Complex);     };

 

 

 

 

 

 

 

Графическое изображение иерархии, реализованной в программе:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Описание пользовательского интерфейса

 

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

 

Рассмотрим каждую операцию отдельно на примере списка, содержащего статический массив указателей на целые числа. Размер элемента списка ограничен 6-ю, при переполнении половина указателей переписывается в новый элемент.  Цифры слева от указанного действии соответствуют порядковому номеру операции в основном меню.

 

8. Добавить в конец  списка (->List.Add)

Пользователь вводит элемент (222), который добавляется в конец списка. Если списка нет, то создаётся структура с одним (введённым элементом). После выполнения операции список автоматически выводится на экран.

 

Добавим ещё несколько элементов  в список. Полученный результат представлен  ниже на рисунке.

 

 

2. Добавить по номеру (->List.Insert)

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

 

 

3. Удалить по номеру (->List.DelElem)

Удаляет элемент по введённому пользователем  номером (0)

 

 

1. Показать список (->List.ShowList)

Функция выводит в удобном виде содержимое списка (элементы списка отделяются чертой “--------“), содержимое массива указателей, логические номера содержимого. Если список не существует, то выводится сообщение «Список пуст».

 

4. Вывод по номеру (->List.ShowElement)

Выводит содержимое указанного пользователем  адреса.

 

6. Сохранение в бинарный файл (->List.Save)

           Пользователь вводит имя файла, в который происходит сохранение структуры. В случае удачного исхода операции выводится сообщение «Файл записан».

 

5. Удалить весь список (->List.DelList)

Происходит удаление списка, в случае удачного исхода операции выводится  сообщение «Список удален!».

 

7. Загрузка из бинарного файла (->List.Load)

Происходит загрузка структуры  из указанного пользователем файла, после выполнения операции выводится сообщение «Файл загружен».

 

1. Показать список (->List.ShowList)

 

Список после удаления 0-ого элемента

 

    b. Балансировка (->List.Balance)

Происходит выравнивание структур данных нижнего уровня.

 

9. Сортировка (->List.Sort)

Сортировка списка по возрастанию.

 

1. Информация о структуре (->List.Info)

 

 

 

     e. Осуществляет выход из программы.

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Функциональное  описание разработки.

 

Программа включает в себя следующие  основные функции:

 

 Добавить в конец списка (List.Add()):

Программа считывает введённую  информацию и вызывает функцию Add, которая проверяет, не является ли список пустым. В случае пустого списка создается новый элемент, и на первую позицию сохраняется только что введенное значение. Если список непустой, то введенное значение добавляется  в конец последнего элемента. Затем вызывается метод Split (item*). В теле этого метода содержится проверка на то, не является ли массив указателей переполненным. Для этого в каждом элементе списка есть переменная size. По достижении переменной size размера N, создаётся ещё один элемент списка, содержащий массив указателей, в который переписывается половина указателей из текущего.

//----------------Вставка в конец-----------------------

 

template <class T, int N>

void List<T,N>::Add(T val) {

 

 

if (First == NULL)         // если список пуст – добавляем  значение первым

{

item *q= new item;

q->next= NULL;

kol=1;

q->data[0]= val;

q->size++;

First= Last= q;

return;

}

item *q= Last;                         // иначе в конец

q->data[q->size]= val;

q->size++;

 

Split(q);  //проверка на переполнение

}

 

Добавить по номеру (List.Insert(T val, int n)):

Программа переводит введенный  логический номер (n) в индекс объекта массива указателей в соответствующем элементе списка. Таким образом получаем место вставки. Далее «раздвигаем» элементы массива указателей и вставляем значение (val) на освободившееся место. При этом идет проверка на переполнение массива указателей и если это происходит, то создается еще один элемент списка, в него переписывается половина указателей из текущего и соответствующим образом происходит переброска указателей.

//----------------Вставка по номеру---------------------

 

template <class T, int N>

void List<T,N>::Insert(T val, int n)          // вставка по номеру

{

item *q=First;

 

if (q==NULL&&n==0) {Add(val); return;}

 

while ((q!=NULL)&&(n>=q->size))

{ n=n-q->size;           

  q= q->next;}

 

int j=0;

 

q->size++;

for (j=(q->size); j>n; j--)

q->data[j] = q->data[j-1];                     // раздвижка границ

 

q->data[n]= val;

Split(q);   //проверка на переполнение

}

 

Вывод по номеру (List.ShowElement(int n)):

Также как и в функции вставки  по логическому номеру происходит его  перевод в индекс элемента в массиве  указателей. Затем на экран выводится только объект соответствующий этому номеру(n)..

 

//-------------------Вывод по номеру---------------------

template <class T, int N>

void List<T, N>::ShowElement(int n) {

item *q=new item;

q=First;

 

while ((q!=NULL)&&(n>=q->size))  //поиск  нужного элемента списка

{ n=n-q->size;

 

  q= q->next;}

 

cout<<"["<<n<<"] "<<q->data[n]<<endl;

}

 

Удалить по номеру (List.DelElem(int n)):

После нахождения соответствующего элемента с номером “n” происходит «сжатие» массива указателей относительно этого элемента. Таким образом он оказывается затертым. После удаления функция уменьшает переменную size на единицу.

 

//--------------------Удаление по номеру---------------------

template <class T, int N>

void List<T, N>::DelElem(int n) {

item *q=new item;

q=First;

 

while ((q!=NULL)&&(n>=q->size))   //поиск  нужного элемента списка

{

n=n-q->size;

q=q->next;

}

 

if (q==NULL) return;

 

for (int i=n; i<q->size; i++) 

q->data[i]=q->data[i+1];

 

//if (i==q->size-1)

 

q->size--;

}

 

Удалить весь список (List.DelList()):

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

 

//----------------Удаление списка------------------

template <class T, int N>

void List<T,N>::DelList() {

item *q=First;

while(q!=NULL) {

First=First->next;

delete q;

q=First; }

 

First=Last=0;

kol=0;

}