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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 07.06.2014
Размер файла 2,3 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Рис 14. Результат добавления с сохранением порядка.

6) Проверка 7-го пункта балансировка.

Рис 15. Результат балансировки

Как и требовалось в произошло разрежение нашего списка - каждый узел заполнен на половину.

7) Пункт меню 8, запись списка в файл. Запись списка будет произведена в файл который будет находиться в той же папке что и исполняемый файл самой программы, имя файла для записи будет запрошено непосредственно перед записью (Рис 16). Запишем наш список в файл (outfile.txt).

Рис 17. Ввод имени файла для вывода.

Текстовй файл получившийся в результате вывода (Рис 18).

Рис 18. Содержимое файла вывода.

Пункт меню 9 был проверен в самом начале раздела.

ЗАКЛЮЧЕНИЕ

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1) Джесс Либерти. «Освой самостоятельно С++ за 21 день» третье издание. Изд. Вильямс.

2) Павловская Т.А. «С/С++ Программирование на языке высокого уровня» Изд. БХВ-Петербург. 2010г.

3) Романов Е.Л. «Практикум по программированию на С++» Изд. БХВ-Петербург. 2004г.

4) Подбельский В.В. «Язык СИ++» Изд. Москва «финансы и статистика». 2005г.

5) Бьерн Страуструп «Язык программирования С++ специальное издание» Изд. Москва Бином-Пресс 2007г.

6) http://cpp.com.ru/lippman/

7) http://ru.wikipedia.org/wiki/Шаблоны_C%2B%2B

ТЕКСТЫ ПРОГРАММНЫХ МОДУЛЕЙ (ПРИЛОЖЕНИЕ)

Программа включает 8 файлов:

kursach.cpp,

StringMy.h, StartMenu.h, reborncin.h, CyDoublewayList.h,

StringMy.cpp, StartMenu.cpp, reborncin.cpp.

Файл kursach.cpp

#include "stdafx.h"

#include <iostream>

#include <Windows.h>

#include "CyDoublewayList.h"

#include "StringMy.h"

#include "StartMenu.h"

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL,"RUS");

setlocale(LC_NUMERIC,"ENG");

StartMenu Menu;

Menu.StartProgramm();

std::cout << std::endl;

system("pause");

return 0;

}

Файл StringMy.h

#pragma once

#include <iostream>

#include <fstream>

#include <string>

#include <sstream>

#include "reborncin.h"

//const int STRLEN = 80; // длина строки

class StringMy

{

public:

StringMy(void);

~StringMy(void);

StringMy(const StringMy& rhs); //конструктор-копировщик

int leng(); // возвращает длину строки

bool operator>(StringMy& rhs);

bool operator<(StringMy& rhs);

bool operator==(StringMy& rhs);

StringMy& operator=(StringMy& rhs); // перегрузка оператора присваивания

friend std::istream& operator>>(std::istream& in_flow, StringMy& rhs); // перегрузка оператора ввода с клавиатуры

friend std::ostream& operator<<(std::ostream& out_flow, StringMy& rhs); // перегрузка оператора вывода на экран

friend std::ifstream& operator>>(std::ifstream& infiles, StringMy& rhs); // перегрузка оператора ввода из файла

friend std::ofstream& operator<<(std::ofstream& outfile, StringMy& rhs); //перегрузка оператора вывода в файл

private:

char *stroka;

};

Файл StringMy.cpp

#include "stdafx.h"

#include "StringMy.h"

const int DLINA = 250;

StringMy::StringMy(void)

:stroka(NULL)

{

}

StringMy::~StringMy(void)

{

if(stroka != NULL)delete[] stroka;

}

StringMy::StringMy(const StringMy& rhs){ //конструктор-копировщик

stroka = new char[DLINA];

for(int i=0; i<DLINA; ++i){

stroka[i] = rhs.stroka[i];

}

}

StringMy& StringMy::operator=(StringMy& rhs){ // перегрузка оператора присвоения

this->~StringMy();

stroka = new char[DLINA];

for(int i=0; i<DLINA; ++i){

stroka[i] = rhs.stroka[i];

}

return *this;

}

int StringMy::leng(){ // возвращает длину строки

if(stroka == NULL) return -1;

int lng = 0;

for(int i = 0; i < DLINA; ++i){

if(stroka[i] == '\0'){

lng = i;

return lng;

}

}

std::cerr << "\nerror... no zero in stroka\n";

return -1; // если так и не встретил \0

}

std::istream& operator>>(std::istream& in_flow, StringMy& rhs){

if(rhs.stroka != NULL)delete[] rhs.stroka;

rhs.stroka = new char[DLINA];

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

// очистка ввода

std::cin.clear();

std::cin.ignore(std::cin.rdbuf()->in_avail());

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

std::cin.getline(rhs.stroka,DLINA-1,'\n');

return in_flow;

}

std::ostream& operator<<(std::ostream& out_flow, StringMy& rhs){

if(rhs.stroka == NULL)return out_flow;

std::cout << rhs.stroka;

return out_flow;

}

bool StringMy::operator>(StringMy& rhs){ // > сравнение по длине

if( this->leng() > rhs.leng() )return true;

return false;

}

bool StringMy::operator<(StringMy& rhs){ // < сравнение по длине

if( this->leng() < rhs.leng() )return true;

return false;

}

bool StringMy::operator==(StringMy& rhs){ // == сравнение по длине

if( this->leng() == rhs.leng() )return true;

return false;

}

std::ofstream& operator<<(std::ofstream& outfile, StringMy& rhs){

outfile << rhs.stroka << '\n';

return outfile;

}

std::ifstream& operator>>(std::ifstream& infile, StringMy& rhs){

//infile.getline(rhs.stroka,DLINA,'\n');

std::string buf;

std::getline(infile,buf); // читаем из файла в буфер строку

int i = 0;

/*int sss = ;

sss+2;*/

rhs.stroka = new char[buf.size()+1]; // +1 для завершающего нуля

while(buf[i]){

rhs.stroka[i] = buf[i]; // из буфера в нашу новую строку

i++;

}

//rhs.stroka[i] = '\n';

//i++;

rhs.stroka[i] = '\0';// завершающий ноль

return infile;

}

Файл StartMenu.h

#pragma once

#include "CyDoublewayList.h"

#include "StringMy.h"

class StartMenu //конкретизированный вариант меню - для простоты

{

public:

StartMenu(void);

virtual~StartMenu(void);

void StartProgramm();

private:

CyDoublewayList<StringMy> * p;

};

Файл StartMenu.cpp

#include "stdafx.h"

#include "StartMenu.h"

#include "reborncin.h"

const int STARTPUNKT = 0; //

const int ENDPUNKT = 9; // максимальный пункт меню

const int LENG_PATHFILENEME = 255;

StartMenu::StartMenu(void)

:p(NULL)

{

p = newCyDoublewayList<StringMy>;

}

StartMenu::~StartMenu(void)

{

}

void StartMenu::StartProgramm(){

int choice = 0;

do{

do{

std::cout << "\n************* Демонстрационная программа ***********\n";

std::cout << "\n********************** Меню **********************\n";

std::cout << "\n1. Ввести на экран содержимое списка";

std::cout << "\n2. Добавить запись";

std::cout << "\n3. Включение по логическому номеру";

std::cout << "\n4. Извлечение по логическому номеру";

std::cout << "\n5. Включение с сохранением порядка";

std::cout << "\n6. Сортировка";

std::cout << "\n7. Балансировка";

std::cout << "\n8. Запись списка в файл";

std::cout << "\n9. Чтение списка из файла";

std::cout << "\n\n\n-------------------------------------------------";

std::cout << "\n0. Выход из программы";

std::cout << "\n****************************************************\n";

std::cin >> choice;

reborncin();

if(choice < STARTPUNKT || choice > ENDPUNKT)std::cout << "\nНеверный ввод, такого пункта нет!";

}while (choice < STARTPUNKT || choice > ENDPUNKT); // крутимся в меню пока не будет выбран какой нибудь пункт из меню

switch(choice){

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

{case 0:

break;

}

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

{case 1: //Ввести на экран содержимое списка

p->Show();

std::cout << std::endl;

system("pause");

break;

}

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

{case 2: //Добавить запись

p->AddRecord(p->GetHead());

break;

}

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

{case 3: //Включение по логическому номеру

int numer = -1;

std::cout << "\nВведите номер строки для включения: ";

std::cin >> numer;

std::cout << std::endl;

p->AddLogNumRecord(numer);

break;

}

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

{case 4: //Извлечение по логическому номеру

int numer = -1;

std::cout << "\nВведите номер строки для извлечения: ";

std::cin >> numer;

std::cout << std::endl;

p->GetLogNumRecord(numer);

break;

}

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

{case 5: //Включение с сохранением порядка

p->AddOrderNumRecord();

break;

}

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

{case 6: //Сортировка

p->Sorting();

break;

}

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

{case 7: //Балансировка

p->Balancing();

break;

}

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

{case 8: //Запись списка в файл

std::cout << "\nВведите полное имя файла: ";

char *pathfilename = new char[LENG_PATHFILENEME];

std::cin >> pathfilename;

p->SaveInTxtfile(pathfilename);

delete[] pathfilename;

break;

}

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

{case 9: //Чтение списка из файла

std::cout << "\nВведите полное имя файла: ";

char *pathfilename = new char[LENG_PATHFILENEME];

std::cin >> pathfilename;

p->LoadOfTxtfile(pathfilename);

delete[] pathfilename;

break;

}

}//end of switch

}while(choice != 0); // выход из программы

}//emd of StartProgramm()

Файл reborncin.h

void reborncin();

Файл reborncin.cpp

#include "stdafx.h"

#include "reborncin.h"

#include <iostream>

void reborncin(){

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

if(!std::cin){// очистка ввода

std::cin.clear();

std::cin.ignore(std::cin.rdbuf()->in_avail());

}

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

}

Файл CyDoublewayList.h

#pragma once

#include <iostream>

#include "StringMy.h"

//typedef CyDoublewayList<StringMy> CDWLSM;

const int NODEARRLEN = 4; // количество элементов в массиве (ОБЯЗАТЕЛЬНО должно быть чётным, иначе не будет работать Born2newNodes() )

const int MAXINDEXARR = NODEARRLEN - 1;

enum ERRCODE {SUCESS, FAIL};

//================================================================================================

template<class T>

class CyDoublewayList

{

public:

struct node

{

node *next;

node *prev;

int instd; // количество вставленных в массив элементов

T *arr[NODEARRLEN];// указатель на массив указателей на T (StringMy строк в нашем случае)

};

CyDoublewayList(void):head(NULL),tail(NULL),lsize(0){}; // конструктор по умолчанию

CyDoublewayList(int size); // создаёт список с заданным количеством пустых узлов

~CyDoublewayList(void); // деструктор

//добавить алгоритмы:

//1.добавление

//2.включение и извлечение по логическому номеру

//3.сортировка

//4.включение с сохранением порядка

//5.загрузка и сохранение строк в бинарном файле

//6.балансировка - выравнивание размерностей структур данных нижнего уровня

//*********************** нельзя сделать снаружи ( из за node* ) ***********************************

node* AddNode(int count = 1){// возвращает указатель на первый добавленный

// узел (чтобы с него начать заполнение при необходимости)

int cnt = count; // требование шаблона

if(head == NULL){

head = new node;

for(int i = 0; i<NODEARRLEN ; ++i)head->arr[i] = NULL;

head->instd = 0;

tail = head; // первый он же последний

head->next = tail;

head->prev = tail;

tail->next = head;

tail->prev = head;

++lsize; //наращиваем количество узлов

--cnt;

if(cnt == 0) return head; // возвращает указатель на первый добавленный узел (чтобы с него начать заполнение при необходимости)

}else{

node* p = tail; //запоминаем место с которого начинается добавление новых узлов

while(cnt != 0){

tail->next = new node;

tail->next->prev = tail; //указатель prev нового узла ссылается на последний в очереди

tail = tail->next; //теперь вновь созданный - последний

tail->next = head; //замыкаем в кольцо

for(int i = 0; i<NODEARRLEN ; ++i)tail->arr[i] = NULL;

tail->instd = 0;

++lsize;//наращиваем количество узлов

--cnt;

}//end of while

p = p->next;

return p; //возвращает указатель на первый добавленный узел (чтобы с него начать заполнение при необходимости)

// БЫЛО

// [head]-[*]-...-[*]-[tail]

// СТАЛО

// [head]-[*]-...-[*]-[здесь был tail]-[p]-[*]-...-[*]-[tail]

}

}//end of node* AddNode(int count = 1)

node* GetLogNode(int num){ // возвращает указатель на узел в котром находится num-запись

//нумерация узлов начинается с 1

//---------- вычисляем номара узла и индекса в нём ---------

int nodenum = num/NODEARRLEN;

int arrindex = num%NODEARRLEN;

if(num >= NODEARRLEN && arrindex == 0){

arrindex = MAXINDEXARR;

}else{

nodenum++;

arrindex--;

}

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

if(nodenum > lsize){

std::cerr << "\nОШИБКА такого узла нет\n";

return NULL;

}

node* tmp = head;

for(int i=1; i<nodenum ;i++) tmp = tmp->next;

return tmp;

}

void GetLogNumRecord(int num){ // выводит на экран запись по логическому номеру

//нумерация узлов начинается с 1

//---------- вычисляем номара узла и индекса в нём ---------

int nodenum = num/NODEARRLEN;

int arrindex = num%NODEARRLEN;

if(num >= NODEARRLEN && arrindex == 0){

arrindex = MAXINDEXARR;

}else{

nodenum++;

arrindex--;

}

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

if(nodenum > lsize){

std::cerr << "\nзаписи с таким номером не существует\n";

return;

}

node* tmp = head;

for(int i=1; i<nodenum ;i++)tmp = tmp->next;

if(tmp->arr[arrindex] != NULL){

std::cout << *tmp->arr[arrindex];

}else{

std::cerr << "\nпо указанному номеру нет данных\n";

}

return;

/*

node* tmp = GetLogNode(num);

if(tmp == NULL){

std::cerr << "\nзаписи с таким номером не существует\n";

return;

}

*/

}

//??????????????????????????????????????????????????????????????????????????????

void AddRecord(node* inserted = NULL){ // добавление записи с клавиатуры

node* tmp = NULL; // временный указатель

if(inserted == NULL){

tmp = AddNode();

}else{

tmp = inserted;

}

if(tmp->instd == NODEARRLEN){ // если в узле нет свободных мест

AddRecord(Born2newNodes(tmp)); // рекурсивный вызов самой себя после

// микробалансировки и добавления 2-х новых узлов

}else{

for(int i=0; i<NODEARRLEN ; ++i){ // ищем в узле свободное место под вставку нового элемента <T>

if(tmp->arr[i] == NULL){// если нашли

tmp->arr[i] = new T; // выделяем память под новый элемент

std::cout << "\nВвод: ";

std::cin >> *tmp->arr[i]; // вводим с клавиатуры

tmp->instd++; // увеличиваем счётчик заполненных мест в узле на 1

break;

}

}//end for

}//end else

}

node* GetHead(){

return head;

}

//************************************************************************************************

void Show();

void AddLogNumRecord(int num);

int Leng();

void Sorting();

void Balancing();

void SaveInTxtfile(const char* pathfilename);

void LoadOfTxtfile(const char* pathfilename);

void AddOrderNumRecord();

/*

void SwapCell(StringMy* raz, StringMy* dva){// Конкретезированный вариант свапа (концепция трёх стаканов)

StringMy *tmp = new StringMy;

*tmp = *raz;

*raz = *dva;

*dva = *tmp;

delete tmp;

}

*/

//****************************

private:

//************* закрытые функции **************************************************

void CreateTmpList(node*& phead, node*& ptail, int sz);

void SwapCell(T* raz, T* dva);

node* Born2newNodes(node* full){ // разбивает заполненный узел на два полузаполненных (создаёт 2-а пустых)

// и возвращает указатель на второй созданный (пустой)

node* cpynd = AddNode(2);

int cnt_full = NODEARRLEN/2;

int cnt_copy = 0;

while(cnt_full < NODEARRLEN){

cpynd->arr[cnt_copy] = full->arr[cnt_full]; //копируем адреса в новый узел из заполненного

full->arr[cnt_full] = NULL; // освобождаем место в заполненном

cpynd->instd++; // количество в новом - растёт

full->instd--; // количество в заполненном - уменьшается

++cnt_full; // следующие две пары

++cnt_copy;

}

return cpynd->next;

}

//********************** закрытые переменные ***********************************************

node *head;

node *tail;

int lsize;

//******************************************************************************************

};

//================================================================================================

template<class T>

CyDoublewayList<T>::CyDoublewayList(int size) // создаёт список с заданным количеством пустых узлов

:head(NULL),

tail(NULL),

lsize(size)

{

if(size == 0)return;

int tmpsz = size;

head = new node;

for(int i = 0; i<NODEARRLEN ; ++i)head->arr[i] = NULL;

head->instd = 0;

--tmpsz;

if(tmpsz == 0){ // если больше нет элементов

tail = head; // первый он же последний

head->next = tail;

head->prev = tail;

tail->next = head;

tail->prev = head;

}else{

node *tmp = head; // запоминаем указатель на первый

while(tmpsz !=0){

head->next = new node;

for(int i = 0; i<NODEARRLEN ; ++i)head->next->arr[i] = NULL;

head->next->instd = 0;

head->next->prev = head; // указатель на предыдущий

head = head->next;

--tmpsz;

}

tail = head; // последний созданный - теперь хвост

head = tmp; // запомненный ранее первый - теперь голова

tail->next = head;

head->prev = tail;

}

}

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

template<class T>

CyDoublewayList<T>::~CyDoublewayList(void){ // ------------Деструктор------------

if(head == NULL)return; // если нет ниодного узла в списке

if(head != NULL && head == tail){ // если есть один единственный элемент

delete head;

return;

}

node *tmp = NULL;

while(tmp != tail){

tmp = head->next;

delete head; // освобождение памяти по указателю

head = tmp;

}

delete tail; // освобождение памяти по последнему указателю в списке

}

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

template<class T>

void CyDoublewayList<T>::Show(){

if(head == NULL)return;

int nodenum = 1;

node *tmp = head;

do{

std::cout << "\n------ " << nodenum << " ------\n";

for(int i = 0; i<NODEARRLEN; ++i){

if(tmp->arr[i] != NULL)std::cout << "\n[" << i << "]: "<< *tmp->arr[i];

else std::cout << "\n[" << i << "]: ";

}

++nodenum;

tmp = tmp->next; // переходим к следующему

}while(tmp != head);

}

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

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

template<class T>

void CyDoublewayList<T>::AddLogNumRecord(int num){ //включение записи по логическому номеру

//нумерация узлов начинается с 1

//---------- вычисляем номара узла и индекса в нём ---------

int nodenum = num/NODEARRLEN;

int arrindex = num%NODEARRLEN;

if(num >= NODEARRLEN && arrindex == 0){

arrindex = MAXINDEXARR;

}else{

nodenum++;

arrindex--;

}

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

if(nodenum > lsize){

std::cerr << "\nвключение невозможно, сначала нужно увеличить размер списка\n";

return;

}

node* tmp = head;

for(int i=1; i<nodenum ;i++) tmp = tmp->next;// пролистываем список до нужного узла

/*

node* tmp = GetLogNode(num);

if(tmp == NULL){

std::cerr << "\nвключение невозможно, сначала нужно увеличмть размер списка\n";

return;

}

*/

if(tmp->arr[arrindex] != NULL) delete tmp->arr[arrindex]; // если место занято - освободить

//сделать здесь функцию переноса данных для освобождения места

tmp->arr[arrindex] = new T;

std::cout << "\nВвод: ";

std::cin >> *tmp->arr[arrindex];

tmp->instd++;

//std::cout << "\nnodenum = " << nodenum;

//std::cout << "\narrindex = " << arrindex;

}

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

template<class T>

int CyDoublewayList<T>::Leng(){

return sizeof(T);

}

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

template<class T>

void CyDoublewayList<T>::SwapCell(T* raz, T* dva){//концепция трёх стаканов

T *tmp = new T;

*tmp = *raz;

*raz = *dva;

*dva = *tmp;

delete tmp;

}

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

template<class T>

void CyDoublewayList<T>::Sorting(){

if(head == NULL)std::cerr << "\nнечего сортировать\n";

int lst = 0, pos = 0;

//StringMy* index_min;

T* index_min;

index_min = NULL;

int colvo = lsize*NODEARRLEN;

node* tmp = tail;

int fullcellcounter = 0;//счётчик для насчитывания непустых ячеек при первом проходе по листу

int fullcellnum = 0; //общее количество непустых ячеек в листе (вычисляется при первом проходе)

int abscellnum = 0; //абсолютный логический номер ячейки во всём листе

int prohodnum = 1; //счётчик походов по листу

int prednum = -1;//абсолютный логический номер ячейки сравниваемой со всеми на предыдущем проходе по листу

int proidenonum = 0;//количество пройденых (сравнённых со всем листом) заполненых данными ячеек

/*

for(int i=0;i<lsize;i++){//цикл обхода списка

tmp = tmp->next;

for(int j=0;j<NODEARRLEN;j++){//цикл обхода узла (массива arr[NODEARRLEN])

if(tmp->arr[j] == NULL)continue;

if(index_min == NULL)index_min = tmp->arr[j]; //находим первую непустую ячейку и запоминаем адрес

if( index_min->leng() > tmp->arr[j]->leng() ){

SwapCell(index_min,tmp->arr[j]);

restand++;

}

}

if(restand>0 && i == (lsize-1)){

i = 0;

restand = 0;

tmp = tail;

}

}//end of цикл обхода

*/

for(int i=0;i<lsize;i++){//цикл обхода списка

tmp = tmp->next;

for(int j=0;j<NODEARRLEN;j++){//цикл обхода узла (массива arr[NODEARRLEN])

abscellnum++;//абсолютный номер текущей ячейки

if(tmp->arr[j] == NULL)continue;

if(prohodnum == 1)fullcellcounter++;//количество непустых ячеек

if(index_min == NULL){//находим первую/очередную непустую ячейку и запоминаем адрес

if(abscellnum <= prednum)continue;//????

std::cout << "\nследующий непросмотренный...\n"; //для отладки

prednum = abscellnum;

proidenonum++;

index_min = tmp->arr[j];

}

//if( index_min->leng() > tmp->arr[j]->leng() ){

if( *index_min > *tmp->arr[j] ){

std::cout << "\nSwapCell()\n"; //для отладки

SwapCell(index_min,tmp->arr[j]);//меняем местами (строки, записи, элементы)

}

}

if( (i == (lsize-1)) ){//перезарядка для нового прохода по листу, либо выход

std::cout << "\nend of list, if(), called... \n";//для отладки

if(prohodnum == 1)fullcellnum = fullcellcounter; // запоминаем насчитанные заполненные ячейки

if(proidenonum == fullcellnum)break;

prohodnum++; // номер прохода по массиву

abscellnum = 0;

i = -1;

tmp = tail;

index_min = NULL;

}

std::cout << "\nend iteration i = " << i << std::endl;//для отладки

}//end of цикл обхода

}

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

template<class T>

void CyDoublewayList<T>::Balancing(){

int fullcellcounter = 0;//счётчик для насчитывания непустых ячеек при проходе по листу

node* tmp = tail;

//*********************************** 1 подщчитываем количество непустых ячеек *******************************

for(int i=0;i<lsize;i++){//цикл обхода списка

tmp = tmp->next;

for(int j=0;j<NODEARRLEN;j++){//цикл обхода узла (массива arr[NODEARRLEN])

if(tmp->arr[j] == NULL)continue;

fullcellcounter++;//количество непустых ячеек

}

}

//******************************* 2 вычисляем количество необходимых узлов для нового листа ********************

const int half = NODEARRLEN/2;

int nd = 0; // количество необходимых узлов для переноса

if(fullcellcounter < half){

nd = 1;

}else{//-----------------

if(fullcellcounter <= NODEARRLEN && fullcellcounter > half){

nd = 2;

}else{//-------------------

if(fullcellcounter%half){

nd = fullcellcounter/half + 1;

}else{//-------------------

nd = fullcellcounter/half;

}

}

}

std::cout << "\nКол-во занятых ячеек в листе: " << fullcellcounter <<

"\nможно разбить на " << nd << " узлов\n";

//*********************************************** 3 создаём новый список ****************************************

node *newhead = NULL;

node *newtail = NULL;

CreateTmpList(newhead,newtail,nd);

/*

newhead->arr[2] = new T;

std::cout << "\nВведи значение: ";

std::cin >> *newhead->arr[2];

std::cout << "\nЗначение: " << *newhead->arr[2];

*/

//************************** 4 переносим записи из старого в новый с компактным размещением *****************

node *newtmp = newtail;

tmp = tail;

bool swapped = false;

while(fullcellcounter){//пока есть неперенесённые ячейки

newtmp = newtmp->next;

for(int m = 0; m<half ;m++){//цикл записи в новый узел половины значений

for(int k=0; k<lsize ;k++){//цикл обхода несбалансированного списка и поиск ячеек с записями

tmp = tmp->next;

for(int j=0;j<NODEARRLEN;j++){ //цикл обхода узла (массива arr[NODEARRLEN])

if( tmp->arr[j] == NULL )continue; // пропускаем пустые и уже перенесённые

newtmp->arr[m] = new T;

*newtmp->arr[m] = *tmp->arr[j];//перенос

newtmp->instd++;

delete tmp->arr[j];//освобождение памяти в старом листе

tmp->arr[j] = NULL; // избавиться от дополнительных проверок

swapped = true; // признак переноса

--fullcellcounter;//количество неперенесённых уменьшается

break;// прерываем цикл j<NODEARRLEN для перещёлкивания m++ (заполнения следующей ячейки)

}

if(swapped){ // если был перенос

swapped = false;// сбрасываем признак переноса

tmp = tail; // начать просмотр оригинальнго списка с начала

break; //выходим из цикла k<lsize для перещёлкивания m++ (заполнения следующей ячейки)

}

}

}//end of m<half

}//end of while

//*************************** 5 освобождаем память от старого листа и переносим указатели головы и хвоста ****************

CyDoublewayList::~CyDoublewayList();

head = newhead;

tail = newtail;

lsize = nd;

newhead = newtail = NULL;

//************************************************************************************************************************

//************************************************************************************************************************

}//end of func Balancing()

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

template<class T>

void CyDoublewayList<T>::CreateTmpList(node*& phead, node*& ptail , int sz){

node *nwhead = NULL;

node *nwtail = NULL;

node *nwtmp = NULL;

int tmpsz = sz;

nwhead = new node;

for(int i = 0; i<NODEARRLEN ; ++i)nwhead->arr[i] = NULL;

nwhead->instd = 0;

--tmpsz;

if(tmpsz == 0){ // если больше нет элементов

nwtail = nwhead; // первый он же последний

nwhead->next = nwtail;

nwhead->prev = nwtail;

nwtail->next = nwhead;

nwtail->prev = nwhead;

}else{

node *nwtmp = nwhead; // запоминаем указатель на первый

while(tmpsz !=0){

nwhead->next = new node;

for(int i = 0; i<NODEARRLEN ; ++i)nwhead->next->arr[i] = NULL;

nwhead->next->instd = 0;

nwhead->next->prev = nwhead; // указатель на предыдущий

nwhead = nwhead->next;

--tmpsz;

}

nwtail = nwhead; // последний созданный - теперь хвост

nwhead = nwtmp; // запомненный ранее первый - теперь голова

nwtail->next = nwhead;

nwhead->prev = nwtail;

}

phead = nwhead;

ptail = nwtail;

}

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

template<class T>

void CyDoublewayList<T>::SaveInTxtfile(const char* pathfilename){

std::ofstream ofile(pathfilename);

if(!ofile){

std::cerr << "\nОшибка создания файла!\n";

return;

}

node *tmp = tail;

for(int i=0; i<lsize ;i++){ // обход списка

tmp = tmp->next;

for(int j=0; j<NODEARRLEN ;j++){// обход очередного узла

if(tmp->arr[j] == NULL)continue; //пустые пропускаем

ofile << *tmp->arr[j]; //запись в файл

}

}

ofile.close();// не забываем закрыть файл

}

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

template<class T>

void CyDoublewayList<T>::LoadOfTxtfile(const char* pathfilename){

std::ifstream infile(pathfilename);

if(!infile){

std::cerr << "\nОшибка открытия файла!\n";

return;

}

node* tmp = NULL;

const int half = NODEARRLEN/2;

T* etalon = new T;

while(!infile.eof()){ //пока не достигнут конец файла

tmp = AddNode(); //

for(int j=0;j<NODEARRLEN;j++){

if(infile.peek() == EOF) break; //если чтение обрвается не на конце массива не создавать новых T

tmp->arr[j] = new T;

infile >> *tmp->arr[j];

tmp->instd++;

}

}

}

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

template<class T>

void CyDoublewayList<T>::AddOrderNumRecord(){

char choice = 'n';

std::cout << "\nСписок будет отсортирован.[y/n]?: ";

reborncin();

std::cin >> choice;

if(choice != 'y')return;

Sorting();

Balancing();

T* record = new T; // место в памяти под добавляемую запись

reborncin();

std::cout << "\nВвод: ";

std::cin >> *record;

node* tmp = tail;

const int half = NODEARRLEN/2;

for(int i = 0; i<lsize; i++){

tmp = tmp->next;

for(int j=0;j<NODEARRLEN;j++){

if(tmp->arr[j] == NULL)continue;

if(*tmp->arr[j] > *record){

for(int t = 0, z=0; t<=((half-1)-j) ; t++,z++){//цикл преноса

tmp->arr[half+z] = tmp->arr[j+t];

tmp->arr[j+t] = NULL;

}

tmp->arr[j] = record;

return;

}

}

}

}

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

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


Подобные документы

  • Проектирование структуры и архитектуры программного продукта. Реализация программы конвертера файлов баз данных. Описание пользовательского интерфейса. Выбор порядка конвертации dbf файлов. Создание и исполнение шаблонов. Расчет себестоимости продукта.

    дипломная работа [2,2 M], добавлен 21.06.2013

  • Понятия шаблонов функции и класса, правила описания на языке С++. Разработка и отлаживание в среде программирования программ, содержащих шаблоны функций и классов. Шаблон функции square, возвращающей квадрат переменной. Создание шаблона класса массива.

    лабораторная работа [162,6 K], добавлен 25.05.2013

  • Понятие шаблона проектирования или паттерна в разработке программного обеспечения. Изменение поведения системы (базы данных) с помощью порождающего шаблона программирования - абстрактной фабрики. Программирование базы данных и управление ею на языке С+.

    курсовая работа [124,8 K], добавлен 30.04.2011

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

    курсовая работа [1,6 M], добавлен 18.01.2012

  • Требование к структуре данных в базе, описание ее вида, содержание объектов. Используемые форматы данных. Алгоритмы и их особенности. Функциональное описание разработки. Описание пользовательского интерфейса. Контрольные примеры, временные характеристики.

    курсовая работа [1,5 M], добавлен 06.04.2016

  • Разработка шаблона для работы с двоичным файлом, в котором хранится структура данных (двоичное дерево объектов). Представление двоичного дерева в файле. Вставка объекта в дерево, его удаление. Алгоритм сжатия файла. Описание пользовательского интерфейса.

    курсовая работа [1,1 M], добавлен 26.01.2013

  • Разработка программного продукта на языке программирования Turbo C. Назначение и область применения программы. Установка и запуск программы. Наиболее важные функции приложения с руководством по их использованию. Возможные проблемы и пути их устранения.

    курсовая работа [1,2 M], добавлен 11.09.2012

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

    дипломная работа [3,1 M], добавлен 19.01.2017

  • Основные типичные системы управления базами данных. Способы описания взаимодействий между объектами и атрибутами. Структурная и управляющая части иерархической модели базы данных. Представление связей, операции над данными в иерархической модели.

    реферат [30,5 K], добавлен 22.02.2011

  • Разработка программного продукта - базы данных "Экскурсия" в интегрированной среде программирования C++ Builder 6. Определение порядка просмотра данных базы, их редактирования и удаления. Особенности руководства пользователя и общего интерфейса программы.

    курсовая работа [2,4 M], добавлен 03.11.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.