Шаблон иерархической структуры данных в памяти
Назначение и область применения программного продукта: наглядное пособие при изучении механизма шаблонов в языке программирования С++. Двухуровневая структура данных, определение шаблона класса, модель компиляции. Описание пользовательского интерфейса.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 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