50456

Объектно-ориентированное программирование. Методические указания

Книга

Информатика, кибернетика и программирование

Возвращаемое значение - объект FormattedString который содержит копию nCount символов, начиная с индекса 0. Возвращаемый объект CString может быть пустым. Параметры nCount - количество символов, подлежащих копированию.

Русский

2014-01-24

298.5 KB

14 чел.

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ

Факультет прикладной математики

Кафедра специализированных компьютерных систем

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНЫМ РАБОТАМ

по курсу

“Объектно-ориентированное программирование”

часть II.

Киев 2011


СОДЕРЖАНИЕ

ЛАБОРАТОРНАЯ РАБОТА № 1.

ЛАБОРАТОРНАЯ РАБОТА №. 2.

ЛАБОРАТОРНАЯ РАБОТА №. 3.

ЛАБОРАТОРНАЯ РАБОТА №. 4.

Классификатор текстов с использованием N-grams.


WARNING: Start early: these labs require quite some work.  Do not discuss solution approaches with others or share code. All code must be written by yourself. Do not use components from the web or from your friends. Explanations such as “Я разобрался” or “Мне помогали” ARE NOT accepted.

ЛАБОРАТОРНАЯ РАБОТА №1.

Теоретические сведения можно найти в лекциях №№ 11 – 13.

Задание на работу.

Вариант 1.

Сконструировать класс MultiString для определения одномерных векторов строк со следующим интерфейсом:

/*!

* file: MultiString.h

* MultiString class definition

* written: 01/05/2011

* Copyright (c) 2011 by Yu.Zorin

*/

#pragma once

class MultiString{

public:

 //constructors destructor

MultiString();

MultiString(int );

MultiString(const MultiString & );

~MultiString();

 //methods

MultiString & operator=(const MultiString &ms){};

 char * operator[] (int nIndex) const;

MultiString & operator+=(const MultiString &);

 void MergeMultiStringExclusive(const MultiString &);

 char *Find(const char *pszSub ) const;

 int GetLength( ) const;

 bool IsEmpty()const{ return str_nmb == 0;};

 void Empty();

 void SetAt( int nIndex, const char* str );

 void PrintStr(int nIndex) const;

private:

 //forbidden copy constructor

 MultString ( const MultString & ms){};

 

 //attributes

 char **buf;//pointer to vector

 int str_len;// string length

 int str_nmb;//strings number

};

Mетоды.

MultString ( ) – создает пустой вектор.

MultString ( const MultString & ) – конструктор копирoвания.
MultString(
MultStrings(int n )создает вектор из n пустых строк.

char * operator[] (int nIndex) cons – возвращает указатель на КОПИЮ строки с индексом indx.

MultString & operator+=(const MultString &src) – выполняет построчную конкатенацию вектора, с которым вызван этот оператор и вектора src.

MultString MergeMultStringExcl(const MultString &src) - выполняет слияние двух векторов с исключением повторяющихся элементов и возвращает результирующий объект.

int Find( const char *pszSub ) const – возвращает индекс pszSub в векторе.

int GetLength( ) const – возврщает длину вектора.

bool IsEmpty()const – возвращает true, если вектор пуст.

void Empty() – очищает вектор.

void SetAt( int nIndex, const char* str ) – замещает в векторе строку с индексом nIndex на строку str.

void PrintStr(int nIndex) const – выводит на консоль строку с индексом nIndex.

Вариант 2.

Сконструировать класс FormattedString для эффективной работы со строками со следующим интерфейсом:

/*!

* file: FormattedString.h

* MultiString class definition

* written: 01/05/2011

* Copyright (c) 2011 by Yu.Zorin

*/

#pragma once

class FormattedString{

//constructors /destructor

FormattedString();

FormattedString(const char *src);

FormattedString(const FormattedString &);

~FormattedString();

//methods

int GetLength( ) const;

 bool IsEmpty() const;

 void Empty();

void SetAt( int nIndex, char ch );

FormattedString & operator=(const FormattedString &);

FormattedString & operator+=(const FormattedString &);

 int A2Int() const;

char* Int2Str(int )const;

void Print() const;

 CString Mid( int nFirst, int nCount ) const;

CString Left( int nCount ) const;

CString Right( int nCount ) const;

private:

//attributes

char *str;// buffer

int len;//string length

};

Mетоды.

FormattedString() – создает пустую строку.

FormattedString(const char *src) – создает строку на основе стадартной С-строки.

FormattedString(const FormattedString  & ) – конструктор копирования.

int  GetLength( ) const – возврщает длину строки.

bool IsEmpty()const – возвращает true, если строка пуста.

void Empty() – очищает строку.

void SetAt( int nIndex, char ch ) – замещает символ с индексом nIndex на символ ch.

FormattedString & operator=(const FormattedString &) – перегруженый оператор присваивания.

FormattedString & operator+=(const FormattedString &src) – выполняет конкатенацию строки, с котoрой вызван оператор и строки src.

int AtoInt() const – выполняет преобразование строки в целое по тем же правилам, что и библиотечная функция atoi.

void IntToStr(int val) – замещает содержмое строки на представление значения val в десятичной системе счисления.

void Print() const - выводит на консоль содержимое строки.

FormattedString Mid( int nFirst, int nCount ) const;
Возвращаемое значение - объект CString, который содержит копию символов из указанного диапазона. Возвращаемый объект FormattedString может быть пустым.

Параметры

nFirst  - индек  (zero-based) первого символа из копируемого диапазона.

nCount – количество символов, подлежащих копированию. Если параметр опущен, копируются все символы до конца строки.

FormattedString Left( int nCount ) const;

Возвращаемое значение - объект FormattedString который содержит копию nCount символов, начиная с индекса 0. Возвращаемый объект CString может быть пустым.

Параметры

nCount  -  количество символов, подлежащих копированию.

Примечание. Если nCount превышает длину строки, копируется вся строка.

 

FormattedString Right( int nCount ) const;
Возвращаемое значение - объект FormattedString который содержит копию nCount символов, начиная с последнего.  Возвращаемый объект FormattedString может быть пустым.

Параметры

nCount  -  количество символов, подлежащих копированию.

Примечание. Если nCount превышает длину строки, копируется вся строка.

Вариант 3.

Сконструировать класс Matrix  реализующий тип данных «квадратная вещественная матрица»  со следующим интерфейсом:

интерфейсом:

/*!

* file: Matrix.h

* MultiString class definition

* written: 01/06/2011

* Copyright (c) 2011 by Yu.Zorin

*/

#pragma once

class Matrix{

public:

//constructors / destructor

Matrix();

Matrix(const double *src, int sz);

Matrix(const Matrix &);

~Matrix();

//methods

Matrix & operator=(const Matrix &);

Matrix & operator+=(const Matrix &);

Matrix & operator*=(const Matrix &);

bool operator==(const Matrix &);

double * operator[] (int indx) const;

void SetCol(const double * , int );

void SetRow(const double *, int);

bool MakeUpperRight();

double KNorm();

void Print();

private:

//atributes

double *koeffs;//buffer

int dim;//matrix dimention

};

Mетоды.

Matrix() – создает пустую матрицу.

Matrix(const double *src, int sz) – сoздает матрицу  размерности sz из вещественного вектора src длины sz * sz.

Matrix(const Matrix &) – конструктор копирования.

Matrix & operator=(const Matrix &) – перегруженный оператор присваивания.

Matrix & operator+=(const Matrix &) – присваивание со сложением двух матриц.

Matrix & operator*=(const Matrix &) – присваивание с умноженимем двух матриц.

bool operator==(const Matrix &) – перегруженный оператор сравнения.

double * operator[] (int indx) const – возвращает указатель на КОПИЮ строки матрицы с индексом indx.

void SetCol(const double * src, int nColNmb) – замещает строку nColNmb матрицы значениями вектора src.

void SetRow(const double * src, int nRowNmb) - – замещает столбец nRowNmb матрицы значениями вектора src.

bool MakeUpperRight() – преобразует матрицу к верхнему треугольному виду (см. Примечане 1), возвращает при true успешном преобразовании и false – в противном случае.

bool IsUnit() - возвращает при true, если матрица единичная и false – в противном случае.

double KNorm() – вычисляет К-норму матрицы (см. Примечане 2).

Примечание 1. Верхней треугольной матрицей называется матрица вида

  1 Х Х Х

  0 1 Х Х

  0 0 1 Х

  0 0 0 1

Преобразование матрицы выполнять с использованием метода исключения Гаусса. Идея метода состоит в следующем.

Пусть имеется матрица вида.

                                                 (3.1)

                                

Верхний индекс указывает номер этапа преобразования матрицы.

Пусть  (главный элемент 1-й строки). Разделив 1-ю строку (3.1) на , получим

  (3.2)

где  (j = 2,3,4). Если тепер 1-ю строку (3.2) последовательно умножать на  и вычитать ее из 2-й и 3-й строк, коэффициенты при  в 2-х последних уравнениях станут равными 0. В результате получим

    (3.3)

,

где  (i = 2,3; j = 2,3,4).

Пусть    0. Тогда, разделив на него 2-е уравнение (3.3), получим

     

                                                                 (3.4)

                 

где ,  .  Если теперь 2-е уравнение  (3.4) последовательно умножать на  и  и вычитать его из 2-го и 3-го уравнений, получим

 

                     

                           (3.5)

                      ,

где  , ,.

Наконец, если  , то разделив на него 3-е уравнение (3.5),  получим

                             

                             (3.6)

                         ,

где (j = 3,4).

Примечание 2. Если на каком либо из этапов преобразования опорный элемент  оказывается равным нулю, следует завершить преобразование и вернуть false, иначе вернуть true.

К-норма матрицы вычисляется по следующей формуле

,

где - элементы матрицы.

Результаты работы оформить в виде проекта С++-программы, включающей следующие файлы:

1. Файлы объявления классов.

2. Файлы определения классов. 

3. Файл тест-драйва.

Имена файлов и проектов должны быть содержательными.

Номер варианта определяет ЗАЧЕТНОЙ КНИЖКИ, взятый по модулю 3:

00 – вариант 1

01 – вариант 2

10 – вариант 3

ЛАБОРАТОРНАЯ РАБОТА №2.

Теоретические сведения можно найти в лекциях №№ 21-23.

Задание на работу.

  1.  В зависимости от варианта реализовать класс CStudent, CTranslate или File.

/*!

* file: Student.h

* CStudent class declaration

* written: 01/02/2011

* Copyright (c) 2011 by Yu.Zorin

*/

#pragma once

class CStudent{

public:

//default constructor

CStudent();

 

//copy constructor

CStudent(const CStudent &);

//destructor

~CStudent();

 

 void SetInfo( char *_fName, char *_lName, int _id);

 void SetGrades(int *, int);

 float AverageGrade()const;

//overloaded assignment

CStudent & operator=(const CStudent &);

 bool operator<(const CStudent &)const;

 void SetId(int _id);

 int GetId()const;

 void PrintEssentials()const;

private:

 int id;//student’s id

 char *fName;//first name

 char *lName;//last name

 int *grades;//grades

 unsigned int grades_nmb;//number of grades

};

Методы

 void SetInfo( char *_fName, char *_lName, int _id);

Параметры

_fName - first name

 _lName - last name

_id – student’s id

 void SetGrades(int *grds, int n);

 Параметры

 grds  – вектор оценок

 n  - число оценок

float AverageGrade()const;

Возвращает среднее арифм. оценок

bool operator<(const CStudent &)const;

Сравнение id по неубыванию.

void PrintEssentials()const;

Вывод на консоль

id

  fName

  lName

  среднее арифм. оценок

/*!

* file: Translate.h

* CTranslate class declaration

* written: 01/03/2011

* Copyright (c) 2011 by Yu.Zorin

*/

#pragma once

class CTranslate{

public:

//default constructor

CTranslate();

//copy constructor

CTranslate(const CTranslate &);

//destructor

~CTranslate();

//overloaded assignment

CTranslate & operator=(const CTranslate &);

 bool operator<(const CTranslate &);

 void MakePair(char *, char *);

 void Print()const;

 char *GetEng()const;

 char *GetIta()const;

private:

 char *eng;//English word

 char *ita;//Italian word

};

Методы

 bool operator<(const CTranslate &);

Сравнивает английские слова в лексикографическом порядке

 void MakePair(char *en, char *ita);

Заносит анг. и итал. слова в соотв. поля

 void Print()const;

Вывод на консоль

eng

ita

либо сообщение об их отсутствии

char *GetEng()const;

char *GetIta()const;

Возвращают указатель на eng/ita соответственно.

/*!

* file: File.h

* File class declaration

* written: 01/05/2011

* Copyright (c) 2011 by Yu.Zorin

*/

#pragma once

class File{

public:

//default constructor

File();

//copy constructor

File(const File &);

//destructor

~File();

 void SetDetails(const char *, int);

 void SetKeywords(const char*);

//overloaded assignment

File & operator=(const File &);

 bool operator<(const File &)const;

 int GetSize()const{ return size;};

void SetSize( int );

 void Print()const;

private:

 char *name;//file name

 int size;//file length

 char *keywords;//set of keywords

 int keywords_nmb;//keywords number

};

Методы

void SetDetails(const char *, int);

Инициализирует поля name и size соответственно.

void SetKeywords(const char *kw);

Инициализирует поле keywords и подсчитывает число ключевых слов keywords_nmb. Ключевые слова в kw разделены “;”

“programming;in;C++;is;easy”

void SetSize( int );

Устанавливает длину файла size.

int GetSize()const;

Возвращает длину файла size.

void Print()const;

Вывод на консоль

name

size

keywords

keywords_nmb

  1.  В зависимости от варианта ревлизовать следующие функции
  2.  Для класса File

void ListAll( const container_type<File> &);

Вывести на консоль содержимое контейнера

void AddKeyword(container_type <File> &, char *);

Добавить в файлы ключевое слово

void DelKeyword(container_type <File> &, char *kwrd);

Удалить из файлов ключевое слово kwrd.

void DelKeywordByLen(container_type <File> &, int len);

Удалить из файлов ключевые слова, длины больше len.

void SortBySize(container_type <File> &);

Отсортировать элементы контейнера в лексикографическом порядке имен файлов.

void SortByKeywordsNumber(container_type <File> &);

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

  1.  Для класса CStudent 

void ListAll(container_type <CStudent> );

Вывести на консоль содержимое контейнера

void SortByGrades(container_type <CStudent> &);

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

void DeleteById(container_type <CStudent> &, int id);

Удалить элемент контенера с заданным id.

CStudent BestAverage(container_type <CStudent> );

Вернуть элемент контенера с лучшей средней оценкой.

void DeleteAll(container_type <CStudent> &);

Удалить все элементы контенера.

  1.  Для класса CTranslate

void ListAll(const container_type<CTranslate> &);

Вывести на консоль содержимое контейнера

void DelByEng(container_type <CTranslate> &, const char *en);

Удалить из контенера все элементы, у которых поле eng равно en.

void DelByIta(container_type <CTranslate> &, const char *it);

Удалить из контенера все элементы, у которых поле ita равно it.

void SortByEng(container_type <CTranslate> &);

Отсортировать элементы контейнера в лексикографическом порядке английских слов.

void SortByIta(container_type <CTranslate> &);

Отсортировать элементы контейнера в лексикографическом порядке итальянских слов.

void TranslateEng(const container_type <CTranslate> &, const char *en);

Вывести на консоль все итальянскиe эквиваленты en.

void TranslateIta(const container_type <CTranslate> &, const char *ita);

Вывести на консоль все английские эквиваленты ita.

Тип контейнера (container_type) определяется вариантом.

Выбор варианта выполняется следующим образом. Номер ЗАЧЕТНОЙ КНИЖКИ берется по модулю 6 плюс 1.

Вариант 1 – класс File, тип контейнера vector

Вариант 2 – класс File, тип контейнера list

Вариант 3 – класс CStudent, тип контейнера vector

Вариант 4 – класс CStudent, тип контейнера list

Вариант 5 – класс CTranslate, тип контейнера vector

Вариант 6 – класс CTranslate, тип контейнера list

Первоначально контейнеры заполняются из csv –файла.

Для класса File строка csv –файла имеет вид

 <file_name;file_size;keywords_list>, e.g.

“testfile.dat;128;programming;in;C++;is;easy

Для класса CTranslate строка csv –файла имеет вид

 <eng_word;ita_word; . . . eng_word;ita_word >, e.g.

"nice;bella;moon;luna"

Для класса CStudent строка csv –файла имеет вид

<id;fname;lname;grades_nmb;grades_list>, e.g.

<1;Bill;Gates;3;2;3;3>

Результаты работы оформить в виде проекта С++-программы, включающей три файла:

1. Header-файла, содержащего объявлениe класса, например,  <Translate.h>.

2. Файла с определениями функций, например,  < Translatepp>.

3. Файла тест-драйва, демонстрирующего работоспособность всех функций, например      

<Dictionary.cpp>.

Dictionaries

"The quick brown fox jumps over the lazy dog" is an English-language pangram (Greek: pan gramma, "every letter"), that is, a phrase that contains all of the letters of the alphabet.

English – Italian

lazy  pigro

 indolente

 svogliato

quick  rapido

 pronto

 spedito

brown  marrone

 bruno

 

dog  cane

fox  volpe

jump  saltare

 rincarare

 trasalire

 

Italian – English

pigro  lazy

 sluggish

 slack

pronto ready

 prompt

 quick

 apt

marrone brown

 maroon

 

trasalire leap

 hop

 bound

ЛАБОРАТОРНАЯ РАБОТА №3.

Теоретические сведения можно найти в лекциях №№ 7, 8, 11, 12..

Задание на работу.

Спроектировать классы узел дерева CTreeNode и двоичное дерево CBinTree и использовать их для написания программы в соответсвии с вариантом.

Вариант 1.

Двоичное дерево (CBinTree) содержит текущую информацию о книгах в библиотеке. Дерево отсортироровано по инвентарным номерам.

Сведения о книгах  (CtreeNode) содержат:

инвентарный номер – m_BookId;

фамилию автора – m_Author;

название – m_Title;

год издания – m_Year;

количество экземпляров данной книги в библиотеке – m_Quantity.

Программа должна обеспечивать:

начальное формирование данных о всех книгах в библиотеке в виде двоичного дерева; исходные данные читаются из csv-файла, каждая сторока которого содержит запись вида

m_BookId; m_Author; m_Title; m_Year; m_Quantity

добавление данных о книгах, вновь поступающих в библиотеку;

удаление данных о списываемых книгах (по инвентарному номеру);

по имени автора выдаются сведения о наличии всех его книг в библиотеке.

по наименованию  выдаются сведения о наличии книги в библиотеке.

Программа должна обеспечивать диалог с помощью меню.

Вариант 2.  Двоичное дерево (CBinTree) содержит текущую информацию о заявках на авиабилеты.. Дерево отсортироровано по фамилиям пассажиров.

Каждая заявка (CTreeNode) содержит:

пункт назначения – m_Destination;

номер рейса – m_Flight;

фамилию пассажира – m_PassengerName;

дату вылета – m_FlightDate.

Программа должна обеспечивать:

начальное формирование данных о заявках на авиабилеты в виде двоичного дерева; исходные данные читаются из csv-файла, каждая строка которого содержит запись вида

m_Destination;m_Flight;m_PassengerName;m_FlightDate

добавление и удаления заявок;

по заданному номеру рейса и дате вылета вывод всех заявок с их последующим удалением;

вывод всех заявок.

Вариант 3.

Двоичное дерево (CBinTree) представляет собой автоматизированную информационная систему на железнодорожном вокзале и содержит сведения об отправлении поездов.  Дерево отсортировано по номерам поездов.

Для каждого поезда (CTreeNode) указывается:

номер поезда – m_TrainNumber;

станция назначения – m_Destination;

время отправления – m_DepartureTime.

Программа должна обеспечивать:

начальное формирование данных информационной системы в виде двоичного дерева; исходные данные читаются из csv-файла, каждая строка которого содержит запись вида

m_TrainNumber;m_DEstination;m_DepartureTime

производит вывод всего списка;

по номеру поезда выводит все данные об этом поезде;

по названию станции назначения выводит данные обо всех поездах, следующих до этой станции.

по номеру поезда удаляет сведения о маршруте;

Вариант 4.

Англо-итальянский словарь (CBinTree) построен как двоичное дерево (см.  словарь  в Лаб. №2).

Каждая компонента (CTreeNode) содержит английское слово, соответствующее ему итальянское слово и номер страницы, на которой находится слово.

Программа должна обеспечивать:

первоначальное формирование дерева согласно латинскому алфавиту; исходные данные читаются из csv-файла, каждая строка которого содержит запись вида

m_EngWord;m_ItaWord;m_Page

вывод всего словаря;

по английскому слову выводит его итальянский эквивалент;

по номеру страницы выводит слова, расположенные на ней;

удаляет запись по английскому слову.

Программа должна обеспечивать диалог с помощью меню.

Результаты работы оформить в виде проекта С++-программы, включающей следующие файлы:

1. Файлы объявления классов - <TreeNode.h>  и <BinTree.h>.

2. Файлы определения классов -   <TreeNode.cpp>  и <BinTree.cpp>.

3. Файл тест-драйва, например,  <Dictionary.cpp>.

Номер варианта определяет номер зачетной книжки, взятый по модулю 4.

Вариант с бонусом. Двоичное дерево реализовать как параметризованный класс, например, вида

template<class T>

class BinTree{

 struct Node{

 T value;

 Node * left;

 Node * right;

 Node(T dat);

 void SetValue( T & val );

 ~Node();

 void Print();

};

public:

BinTree():root(NULL){};

 void add_item(T *itm);

 void Print();

 template<class _Pr3>

 void find_item(_Pr3 _Pred){

 //. . .

};

 template<class _Pr3>

 void remove_if(_Pr3 _Pred);

private:

Node *root;

// . . .

};

В соответствии с вариантом определить СTreeNode и функциональные объекты, необходимые для реализации варианта.

ЛАБОРАТОРНАЯ РАБОТА №4.

Теоретические сведения можно найти в лекциях №№ 21 – 23.

Задание на работу.

Спроектировать параметризованный класс однонаправленный список List со следующим интерфейсом

 template <class T>

class List{

 

 struct ListNode{

 T data;

 ListNode * next;

 ListNode(){

  next = NULL;

 }

 ListNode( T dat ){

  data = dat;

 }

 void Print(){

  cout<<data;

 }

};

 

public:

 typedef ListNode node_type;

 typedef _iterator<node_type> iterator;

 //constructors / destructors

List();

~List();

 

 //methods

iterator begin();//Returns an iterator addressing the first element

iterator end();//Returns an iterator that addresses the location

  //succeeding the last element

 

 void clear();//Erases all the elements of a list.

 bool empty();//Tests if a list is empty.

iterator find(const node_type & val);//Returns an iterator to the

// first element in a list that

//match a specified value.

 void pop_front();//Deletes the element at the beginning of a list.

 void push_front( const node_type val);//Adds an element to the beginning

 //of a list.

 void remove(const node_type val);//Erases first element in a list that

  //match a specified value.

 

 int size();//Returns the number of elements in a list.

 void splice( iterator _Where, List<T>& _Right);//Removes element from the

//target list and inserts it in first

      // position of the argument list.

 void Print();//Dumps list into the screen

private:

node_type *head;

iterator *first, *last;

};

Mетоды.

 List() – создает пустой список.

List<int> l;

void push_front( const node_type val) – вставляет элемент в начло списка 

l.push_front( 10 );

iterator begin() – возвращает итератор, адресующий первый элемент списка

iterator end()– возвращает итератор, адресующий позицию за пследним элементом

   списка

List<int>::iterator it;

for(it = l.begin(); it = l.end; it++)

//do something

 

void load(const char *filename) – инициализирует список из csv-file

 

void clear()- удаляет все элементы списка

bool empty() – возвращает true в случае пустого списка

iterator find(const node_type & val) – возращает итератор на первый элемент с

  заданным значением val

void pop_front() – удаляет первый элемент списка

void remove(const node_type val); – удаляет первый элемент списка с

заданным значением val

int size() – возвращает длину списка

void splice( iterator _Where, List<T>& _Right) – удаляет элемент из списка, с котормы вызывается метод, в позиции _Where и вставляет его в начало списка  _Right

void Print() – выводит содержимое списка на экран

Для перемещения по списку использовать следующий параметризованный итератор

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

*file: Iterator.h

*purpose: template class used to traverse through the List container

*author: Yu.Zorin

*written: 13/03/2008

*last modified:

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

#pragma once

template <typename T>

class _iterator

{

private:

 T* ptr;

public:

 typedef T value_type;

 typedef _iterator<T> it_type;

_iterator() {ptr = 0;}

_iterator(T* _ptr) {ptr = _ptr;}

T& operator *();

 void operator++();

 //dummy operator to keep compiler quiet

 void operator++(int);

 bool     operator==(const it_type& _iter) const;

 bool     operator!=(const it_type& _iter) const;

 bool empty(){ return ptr == NULL;}

};

template <typename T>

T& _iterator<T>::operator *()

{

 return *ptr;

}

template <typename T>

void _iterator<T>::operator ++()

{

ptr = ptr->next;

}

template <typename T>

void _iterator<T>::operator ++(int)

{

ptr = ptr->next;

}

template <typename T>

bool _iterator<T>::operator ==(const it_type &_iter) const

{

 return (ptr == _iter.ptr);

}

template <typename T>

bool _iterator<T>::operator !=(const it_type &_iter) const

{

 return !(*this == _iter);

}

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

Вариант 1.

class Bus

{

public:

/*

methods

*/

 friend ostream& operator<<(ostream& stream, Bus &obj);

private:

 char *driver;

 char *bus_number;

 char *route_number;

};

Сведения об автобусе содержат:

Номер автобуса - bus_number ;

Имя водителя - driver;

Номер маршрута - route_number.

Методы класса Bus должны обеспечить возможность создания и обработки списка List<Bus>.

Сведения об автобусах хранятся в двух списках типа List<Bus>. Первый список - данные о всех автобусах в парке (инициализируется из csv-файла). Второй список – автобусы, находящиеся на маршруте.

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

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

Вариант 2.

class File{

public:

/*

methods

*/

 friend ostream& operator<<(ostream& stream, File &obj);

private:

 char *_filename;

 char *_creation_date;

 int _size;

};

Сведения о файле содержат:

имя файла - _filename;

дата создания - _creation_date;

размер файла - _size .

Методы класса File должны обеспечить возможность создания и обработки списка

List<File>.

Сведения о файлах хранятся в двух списках типа List<File>. Первый список - данные о всех файлах данного каталога (инициализируется из файла). Второй список – файлы, удаленные из каталога.

При удалении файла из каталога, он переносится из первого списка во второй с помощью функции splice.

При восстановлении файла, он переносится из второго списка в первый с помощью функции splice.

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

Вариант 3.

class References{

public:

public:

/*

methods

*/

 friend ostream& operator<<(ostream& stream, References &obj);

private:

 char *word;

 int *pages;//pages numbers

 int _size;//number of pages

};

 

Сведения о слове содержат:

слово - word;

номера страниц, на которых оно встречается - pages;

число  страниц, на которых оно встречается - _size.

Методы класса References должны обеспечить возможность создания и обработки списка

ссылок List<References>.

Сведения о ссылках хранятся в двух списках типа List<References>. Первый список - данные о всех ссылках книги (инициализируется из файла). Второй список – удаленные ссылки. Количество страниц книги не превышает 300.

При удалении ссылки, она переносится из первого списка во второй с помощью функции splice.  

При восстановлении ссылки, она переносится из второго списка в первый с помощью функции splice.

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

Результаты работы оформить в виде проекта С++-программы, включающей следующие файлы:

1. Файлы объявления классов - <List.h> , <Iterator.h> и <Bus.h>, <File.h> <References.h> в зависимости от варианта.

2. Файлы определения классов -   <Bus.cpp>, <File.cpp>, <References.cpp> в зависимости от варианта.

3. Файл тест-драйва, например,  <Test.cpp>.

Номер варианта определяет номер зачетной книжки, взятый по модулю 3.

Классификатор текстов с использованием N-grams.

N-Grams

N-gram - это N-character срез более длинной строки. N-gram дополняется символами “_” для индикации начала (конца) слова.

Например, слово “TEXT” включает следующие N-grams:

bi-grams: _T, TE, EX, XT, T_

tri-grams: _TE, TEX, EXT, XT_, T_ _

quad-grams: _TEX, TEXT, EXT_, XT_ _, T_ _ _

В общем случае, строка длины k, дополненая символами подчеркивания, содерхит k +1 bi-grams, k+1 tri-grams, k+1 quad-grams и т.д..

Генерирование профилей (Profiles) частот  N-Gram.

Процедура “Generate Profile” на рис.1 считывает входной текст и подсчитывает количество вхождений всех N-grams. Для этого необходимо:

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

Для каждого слова сгенерировать N-grams  для N от 2 до 5 (включая символы подчеркивания).

Разместить N-grams слова в хэш-таблице увеличивая число вхождений.

Таблица должна быть отсортирована в порядке убывания числа вхождений.

Процедура классификации.

Классификация (рис. 1) включает следующие этапы.

1. Обучение (левая ветвь алгоритма на рис. 1).

Взять тексты, представляющие собой образцы категорий.

Сгенерировать профили частот  N-grams для каждого из текстов.

2. Распознавание.

Сгенерировать профиль частот  N-grams распознаваемого текста.

Вычислить меры расстояния (distance measure) профилем частот распознаваемого текста и профилями частот  образцов категорий.

Выбрать категорию с наименьшей мерой расстояния.

Figure 1. Dataflow For N-Gram-Based Text Categorization

Меры расстояний вычисляются по схеме Out-Of-Place (рис. 2).

Figure 2. Calculating The Out-Of-Place Measure Between Two Profiles

Величина max зависит от длины профилей частот  и подбирается экспериментально. Например max = 5 * len, где len – длина профиля частот распознаваемого текста.

Задание на работу.

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

 /* N-grams frequencies profile */

 typedef map<string,unsigned long> frequency_map;

 class TextClassifier {

 public:   

  

/* Name of classification defaults to 'Unknown.' */   

   TextClassifier();

   

/*Param classification - name of the classification (e.g., "Spam").    */

   TextClassifier(const string classification);

   

/* returns the map N-grams and their frequencies.     */

   frequency_map freqs() { return my_freqs; }

   

/* returns the name of the classifier.*/

   string classification() { return my_classification; }

   

/*Param classification - name of the classifier.*/

   void setClassification(string& classification) {my_classification = classification;}

/*learns the frequencies of N-grams in a corpus.*/

   void TextClassifier::learn(istream& in);

/*dumps the frequencies of N-grams in a corpus.

File structure is as follows:

* lines which start with c - comments

* line which starts with s - classification

* lines with N-grams start with n  and contain

* N-gram and its quantity separated with space or tab*/

   void TextClassifier::dumpProfile(ostream& out);

/*learns the frequencies of N-grams from a file created by.

* dumpProfile() function */

   void TextClassifier::learnFromDump(istream& in);

/*returns distance measure between 2 TextClassifiers*/

   long int TextClassifier::score(const TextClassifier &);

 . . .

private:

   /*! internal frequency map */

   frequency_map my_freqs;

   /*! internal name of classifer */

   string _classification;

   

 };

Пример использования.

int main(){

const int n = 3;

char *categories[n] = {“spam”,

  “programming”,

  “finance”};

TextClassifier classifiers[n];

string catfound;

int i;

 

for(i = 0; i < n; i++){

classifiers[i].setClassification(categories[i]);

string file_name = categories[i] + “.txt”;

ifstream in( file_name );

 classifiers[i].learn( in );

}

TextClassifier minscore = classifiers[0];

TextClassifier text2classify();

string file_name = “toclassfy.txt”;

ifstream in( file_name );

text2classify.learn( in );

 

for(i = 1; i < n; i++){

 if(text2classify.score(classifiers[i]) <

text2classify.score(minscore) )

minscore = classifiers[i];

 }

catfound = minscore.classification();

. . .

return 0;

}

Результаты работы оформить в виде проекта С++-программы, включающей следующие файлы:

1. Файл объявления класса TextClassifier.h.

2. Файл определения класса  TextClassifier.cpp.

3. Файл тест-драйва, например,  <Test.cpp>.

Тестирование провести на текстах длиной от 3K до 10K bytes.


 

А также другие работы, которые могут Вас заинтересовать

35644. Творческий проект «Тигр». В технике холодный батик 246.84 KB
  Что означает слово батик. Влияние батика на новое поколение. На уроках технологии я научилась рисовать батиком.
35645. Бижутерия. Творческий проект 64.68 KB
  Бисер - (от араб. бусра – фальшивый жемчуг) - мелкие разноцветные стеклянные бусины с отверстиями, употребляемые главным образом для вышивания (на предметах быта, женской одежде и т. д.). Бисер плотно вошел в нашу жизнь, заявив о себе в разных сферах жизни человека. Бисер можно использовать как элемент декора интерьера, как эксклюзивное украшение, для некоторых людей бисер является неотъемлемой частью их жизни. Маленькие разноцветные шарики с отверстиями несут в себе магическую силу притяжения. И столкнувшись один раз с бисером, вы оказываетесь под его влиянием.
35648. Пошив фартука. Творческий проект 468.57 KB
  Техническая последовательность Сначала мы сняли мерки потом начертили части фартука размером 1к4 в тетради в настоящую величину специальными булавками прикрепили на ткань. Скоро мы сшили карманы и низ фартука.
35649. Вязаная сумочка под различные мелочи 800.13 KB
  Затраты на изделие=стоимость ниток стоимость Крючка Стоимость всей пряжи:60 рублей. Стоимость крючка:10 рублей.