Министерство образования и науки Республики Казахстан
Карагандинский Государственный Технический Университет
Кафедра ИВС
Расчетно-графическая работа
Объектно-ориентированное программирование
( наименование дисциплины)
Тема: Разработка класса для работы с динамической структурой данных
Руководитель Кайбасова Д.Ж.
(ФИО преподавателя)
(оценка) (подпись)
Студент ИС-14-2
(группа)
(фамилия, инициалы)
(подпись) (дата)
Караганда 2015
Задание.
Построить класс для работы с односвязным списком. Элементы списка – слова. Создать список, содержащий некоторую последовательность слов. Заменить в списке каждое вхождение заданного слова другим (также заданным).
Содержание
Введение. 4
- Теоретическая часть. 5
1.1 Основные понятия С++. 5
1.2 Основные операторы управления. 7
2 Практическая часть. 15
2.1 Описание использованных элементов. 15
2.2 Блок-схемы алгоритмов. 17
2.3Реализация программы.. 20
Заключение. 21
Список использованной литературы.. 22
Приложение. 23
Введение
Расчетно-графическая работа включает в себя решение задачи описания класса для работы с односвязным списком, элементами которого являются слова. Программа должна создать список, содержащий некоторую последовательность слов. Заменить в списке каждое вхождение заданного слова другим (также заданным).
В работе над заданием были использованы класс, объекты, функции, конструктор и структура.
Выполнение работы осуществляется на языке С++ в среде VisualStudio 2010, которая позволяет разрабатывать консольные приложения.
Данная работа состоит из двух частей: теоретической и практической. В теоретической части рассмотрены основные понятия языка С++, такие как переменные, основные типы данных и массивы. Кроме того, описаны основные операторы управления: циклы, операторы выбора, функции, структура данных, классы, списки, объекты, конструктор и стандартная библиотека. В практической части приведена таблица основных элементов, которые использовались в классе lis tи главной функции main. Также графически изображены блок-схемы алгоритмов. Последним пунктом практической части является реализация программы, которая включает в себя рисунок, изображающий результат работы программы, и подробное описание ее действий с соответствующей реализацией в коде.
В приложении отображен листинг данной программы.
- Теоретическая часть
1.1. Основные понятияC++
C++ - это компилируемый, статически типизированный язык программирования общего назначения. Он поддерживает такие парадигмы программирования как процедурное программирование, объектно-ориентированное программирование, обобщённое программирование, обеспечивает модульность, раздельную компиляцию, обработку исключений, абстракцию данных, объявление типов (классов) объектов, виртуальные функции. Стандартная библиотека включает, в том числе, общеупотребительные контейнеры и алгоритмы. C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков. В сравнении с его предшественником — языком C, — наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования.
C++ широко используется для разработки программного обеспечения, являясь одним из самых популярных языков программирования. Область его применения включает создание операционных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а также развлекательных приложений (игр). Синтаксис C++ унаследован от языка C. Одним из принципов разработки было сохранение совместимости с C. Тем не менее, C++ не является в строгом смысле надмножеством C; множество программ, которые могут одинаково успешно транслироваться как компиляторами C, так и компиляторами C++, довольно велико, но не включает все возможные программы на C.
Структура данных
Структура данных (англ. datastructure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.Структуры данных формируются с помощью типов данных, ссылок и операций над ними в выбранном языке программирования.
Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, B-деревьяобычно подходят для создания баз данных, в то время как хеш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет-адреса компьютеров.
Переменные C++
Переменная в императивном программировании — поименованная, либо адресуемая иным способом область памяти, адрес которой можно использовать для осуществления доступа к данным. Данные, находящиеся в переменной (то есть по данному адресу памяти), называются значением этой переменной.
В других парадигмах программирования, например, в функциональной и логической, понятие переменной оказывается несколько иным. В таких языках переменная определяется как имя, с которым может быть связано значение, или даже как место (location) для хранения значения.
По зоне видимости различают локальные и глобальные переменные. Первые доступны только конкретной подпрограмме, вторые — всей программе. С распространением модульного и объектного программирования, появились ещё и общие переменные (доступные для определённых уровней иерархии подпрограмм). Область видимости иногда задаётся классом памяти.
Ограничение зоны видимости придумали как для возможности использовать одинаковые имена переменных (что разумно, когда в разных подпрограммах переменные выполняют похожую функцию), так и для защиты от ошибок, связанных с неправомерным использованием переменных (правда, для этого программист должен владеть и пользоваться соответствующей логикой при структуризации данных).
Основные типы данных в C++
Основными типами данных в языке С++ являются:
int — целочисленный тип данных.
float — тип данных с плавающей запятой.
double — тип данных с плавающей запятой двойной точности.
char — символьный тип данных.
bool — логический тип данных.
Переменные объявляют в операторе описания. Оператор описания состоит из спецификации типа и списка имён переменных, разделённых запятой. В конце обязательно должна стоять точка с запятой.
Объявление переменной имеет следующий формат:
[модификаторы] тип идентификатора [идентификатор]
Модификаторы - ключевые слова signed, unsigned, short, long.
Спецификатор типа - ключевое слово char или int, определяющее тип объявляемой переменной.
Пример:
char x;
int a, b, c;
unsigned long long y;
В данной работе использованы данные типаint .
Инкремент и декремент
Если необходимо изменить значение переменной на 1, то используют инкремент или декремент.Инкремент - операция увеличения значения, хранящегося в переменной, на 1.
i++;
Декремент - операция уменьшенния , хранящегося в переменной, на 1.
i--;
1.2. Основные операторы управления
Цикл — многократное прохождение по одному и тому же коду программы. Циклы необходимы программисту для многократного выполнения одного и того же кода, пока истинно какое-то условие. Если условие всегда истинно, то такой цикл называется бесконечным, у такого цикла нет точки выхода.
Цикл for в С+. Тело цикла будет выполняться до тех пор, пока условие будет истинно(т. е. true).
for (/*выражение1*/; /*выражение2*/; /*выражение3*/ ){
/*один оператор или блок операторов*/;
}
Выражение 1 — объявление (и) или инициализация, ранее объявленной, переменной-счетчика, которая будет отвечать за истинность условия в цикле for.
intcounter = 0;
Выражение 2 — это условие продолжения цикла for, оно проверяется на истинность.
counter< 10;
Выражение 3 изменяет значение переменной-счетчика. Без выражения 3 цикл считается бесконечным, так как изменение содержимого переменной count выполняться не будет, и если изначально условие было истинным, то цикл будет бесконечным, иначе программа даже не войдет в цикл. Выражения 1, 2, 3 отделяются друг от друга обязательными разделителями, точкой с запятой. Тело цикла обрамляется фигурными скобочками, если тело цикла состоит из одного оператора,то фигурные скобочки не нужны. Под изменением значения переменной подразумевается уменьшение или приращение значения, например:
counter++;
Один из примеров использования цикла forв данной работе
for(inti =0;i<element;i++){
double g = stck.get();
stk.get();
cout<<g<<" "; }
Операторы выбора С++.
В языке программирования С++ существует два оператора выбора:
- Оператор выбора if
- Оператор выбора switch
Операторы выбора позволяют принять программе решение, основываясь на истинности или ложности условия. Если условие истинно (т. е. равно true) значит, оператор в теле if выполняется, после чего выполняется следующий по порядку оператор. Если условие ложно (т. е. равно false) значит, оператор в теле if не выполняется (игнорируется или пропускается) и сразу же выполняется следующий по порядку оператор. Проверяемое условие может быть любым логическим выражением. Логические выражения могут быть образованы операциями равенства и отношения.
Таблица 1. Операции равенства и отношения
|
Операция в С++ |
Условие |
Смысл записанных условий в С++ |
|
== |
a == b |
a равно b |
|
!= |
a != b |
a не равно b |
|
> |
a > b |
a больше b |
|
< |
a < b |
a меньше b |
|
>= |
a >= b |
a больше или равно b |
|
<= |
a <= b |
a меньше или равно b |
В данной работе оператор switchиспользуется для выбора выполняемых действий.
Функции
Функции — это блоки кода, выполняющие определенные операции.Если требуется, функция может определять входные параметры, позволяющие вызывающим объектам передавать ей аргументы.При необходимости функция также может возвращать значение как выходное.Функции полезны для инкапсуляции основных операций в едином блоке, который может многократно использоваться. В идеальном случае имя этого блока должно четко описывать назначение функции.Следующая функция принимает от вызывающего ее объекта два целых числа и возвращает их сумму.
Пример использования функции в данной работе:
void add(int d){
element *newelement= new element;
newelement->data=d;
newelement->next=first;
first=newelement;};
Данная функция сортирует стек в порядке убывания. Тип функции void.
Классы C++
Классом называется составной тип данных, элементами которого являются функции и переменные (поля). В основу понятия класс положен тот факт, что «над объектами можно совершать различные операции». Свойства объектов описываются с помощью полей классов, а действия над объектами описываются с помощью функций, которые называются методами класса. Класс имеет имя, состоит из полей, называемых членами класса, и функций — методов класса.
После описание класса необходимо описать переменную типа class. Это описание имеет следующий формат:
class name
{private://описание закрытых членов и методов класса
protected://описание защищенных членов и методов класса
public://описание открытых членов и методов класса
В отличие от полей структуры, доступных всегда, в классах могут быть члены и методы различного уровня доступа:
- открытые, также называемые публичными, (public). Их вызов осуществляется с помощью оператора.(«точка»);
- закрытые, или приватные, (private), доступ к которым возможен только с помощью открытых методов;
- защищенные(protected) методы, являются промежуточными меж-ду private иpublic.
В данной работе использовались уровни доступа publicиprivate.
private: double *stack;
private: int last;
public: Stack(intn)
Объекты
Классы в С++ — это абстракция, описывающая методы, свойства, ещё не существующих объектов. Объекты — конкретное представление абстракции, имеющее свои свойства и
Созданные объекты на основе одного класса называются экземплярами этого класса. Эти объекты могут иметь различное поведение, свойства, но все равно будут являться объектами одного класса. В ООП существует три основных принципа построения классов:
- Инкапсуляция— это свойство, позволяющее объединить в классе и данные, и методы, работающие с ними и скрыть детали реализации от пользователя.
- Наследование— это свойство, позволяющее создать новый класс-потомок на основе уже существующего, при этом все характеристики класса родителя присваиваются классу-потомку.
- Полиморфизм— свойство классов, позволяющее использовать объекты классов с одинаковым интерфейсом без информации о типе и внутренней структуре объекта.
Конструктор C++
Конструктор — специальная функция, которая выполняет начальную инициализацию элементов данных, причём имя конструктора обязательно должно совпадать с именем класса. Важным отличием конструктора от остальных функций является то, что он не возвращает значений вообще никаких, в том числе и void. В любом классе должен быть конструктор,даже если явным образом конструктор не объявлен, то компилятор предоставляет конструктор по умолчанию, без параметров
Пример конструктора в данной работе:
public: Stack(int n){
last = 0;
stack = new double[n]; }
Стандартная библиотека.
В языке программирования C++ термин «Стандартная библиоте-ка» означает коллекцию классов и функций, написанных на базовом языке. Стандартная Библиотека поддерживает несколько основных контейнеров, функций для работы с этими контейнерами, объектов-функции, основных типов строк и потоков (включая интерактивный и файловый ввод-вывод), поддержку некоторых языковых особенностей, и часто используемые функции для выполнения таких задач, как, например, нахождение квадратного корня числа. Стандартная Библиотека языка C++ также включает в себя спецификации стандарта ISO C90 стандартной библиотеки языка Си. Функциональные особенности Стандартной Библиотеки объявляются внутри пространства имен std.
Стандартная библиотека шаблонов (STL) — подмножество стандартной библиотеки C++ и содержит контейнеры, алгоритмы, итераторы, объекты-функции и т. д.
iostream — заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++. Он включён в стандартную библиотеку C++. Название образовано от Input/OutputStream («поток ввода-вывода»). В языке C++ нет встроенной поддержки ввода-вывода, вместо этого используется библиотека функций. iostream управляет вводом-выводом. Iostream использует объекты cin, cout, cerr и clog для передачи информации в и из стандартных потоков ввода, вывода, ошибок (без буферизации) и ошибок (с буферизацией) соответственно. Являясь частью стандартной библиотеки C++, эти объекты также являются частью стандартного пространства имён — std.
stdlib.h — заголовочный файл стандартной библиотеки языка Си, который содержит в себе функции, занимающиеся выделением памяти, контроль процесса выполнения программы, преобразования типов и другие. Заголовок вполне совместим с C++ и известен в нём как cstdlib. Название «stdlib» расшифровывается как «standardlibrary» (стандартная библиотека).
В данной работе использовались стандартные библиотекиiostream,stdlib.
Свя́зный спи́сок
Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Виды связных списков:
Линейный связный список
Односвязный список
Рисунок 1 - Связный список
Разновидность связного списка — односвязный список, содержащий 3 элемента
Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.
В односвязном списке каждый элемент информации содержит ссылку на следующий элемент списка. Каждый элемент данных обычно представляет собой структуру, которая состоит из информационных полей и указателя связи. Концептуально односвязный список выглядит так, как показано на рис. 2.
| +---------+ +---------+ +---------+| данные | | данные | | данные |+---------+ +---------+ +---------+|указатель|--->|указатель|--->| 0 |+---------+ +---------+ +---------+ |
|
Рисунок 2 - Односвязный список |
Существует два основных способа построения односвязного списка. Первый способ — помещать новые элементы в конец списка[1]. Второй — вставлять элементы в определенные позиции списка, например, в порядке возрастания. От способа построения списка зависит алгоритм функции добавления элемента. Давайте начнем с более простого способа создания списка путем помещения элементов в конец.
Как правило, элементы связанного списка являются структурами, так как, помимо данных, они содержат ссылку на следующий элемент. Поэтому необходимо определить структуру, которая будет использоваться в последующих примерах. Поскольку списки рассылки обычно хранятся в связанных списках, хорошим выбором будет структура, описывающая почтовый адрес. Ееописаниепоказанониже:
struct address {char name[40];char street[40];charcity[20];char state[3];char zip[11];struct address *next; /* ссылканаследующийадрес */} info;
Приведенная ниже функция slstore() создает односвязный список путем помещения каждого очередного элемента в конец списка. В качестве параметров ей передаются указатель на структуру типа address, содержащую новую запись, и указатель на последний элемент списка. Если список пуст, указатель на последний элемент должен быть равен нулю.
voidslstore(struct address *i,struct address **last){if(!*last) *last = i; /* первыйэлементвсписке */else (*last)->next = i;i->next = NULL;*last = i;}
Несмотря на то, что созданный с помощью функции slstore() список можно отсортировать отдельной операцией уже после его создания, легче сразу создавать упорядоченный список, вставляя каждый новый элемент в нужное место в последовательности. Кроме того, если список уже отсортирован, имеет смысл поддерживать его упорядоченность, вставляя новые элементы в соответствующие позиции. Для вставки элемента таким способом требуется последовательно просматривать список до тех пор, пока не будет найдено место нового элемента, затем вставить в найденную позицию новую запись и переустановить ссылки.
В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных. На практике линейные списки обычно реализуются при помощи массивов и связных списков. Иногда термин «список» неформально используется также как синоним понятия «связный список». К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и основных операций:
- Операция, проверяющая список на пустоту.
- Три операции добавления объекта в список (в начало, конец или внутрь после любого (n-ого) элемента списка);
- Операция, вычисляющая первый (головной) элемент списка;
- Операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.
- Длина списка. Количество элементов в списке.
- Списки могут быть типизированнымиили нетипизированными. Если список типизирован, то тип его элементов задан, и все его элементы должны иметь типы, совместимые с заданным типом элементов списка. Обычно списки, реализованные при помощи массивов, типизированы.
- Список может быть сортированнымили несортированным.
- В зависимости от реализации может быть возможен произвольный доступк элементам списка.
Рисунок 3 - Двусвязный список (двунаправленный связный список)
Здесь ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно эффективно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как легко доступны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
Кольцевой связный список
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.
Рисунок 4 – Кольцевой список
Как правило, такая структура реализуется на базе линейного списка. С каждым кольцевым списком дополнительно хранится указатель на первый элемент. В этом списке ссылки на NULL не встречается.
Также существуют циклические списки с выделенным головным элементом, облегчающие полный проход через список.
В данной работе был использован односвязный список;
- Практическая часть
2.1. Описание использованных элементов
Для разработки данной программы были использованы различные переменные массивы и функции. Их описание и код приведены в таблице 2.
Таблица 2.Описание использованных элементов.
|
Classlist |
||
|
Название |
Описание |
Код |
|
Функция add() |
Имеет тип Void Добавляет элементы в список |
void add(string s){ element *newelement= new element; newelement->data=s; newelement->next=first; first=newelement; }; |
|
Функция show() |
Имеет тип Void Показывает элементы списка |
void show(){ setlocale(LC_CTYPE, "rus"); element *n=first; while(n){ cout<<n->data<<" "; n=n->next; } cout<<endl; }; |
|
Функция replace |
Имеет тип Void Меняет элементы списка на заданное слово
|
void replace(string s){ element *n=first; while(n){ n->data=s; n=n->next; } }; |
|
Функция menu() |
Имеет тип Void Меню |
void menu(){ setlocale(LC_CTYPE, "rus"); int l; string word; cout<<"Введите размер списка: "; cin>>l; cout<<endl; |
Продолжение таблицы 2.
|
|
|
for (int i=1;i<=l;i++){ cout<<"Введите "<<i<<" слово: "; cin>>word; add(word); cout<<endl; } show(); cout<<"введите слово на которое нужно заменить все слова: "; cin>>word; cout<<endl; replace(word); show(); }; }; |
|
Переменная s |
Имеет тип list Для вызова функции из класса |
int main(){ list s; s.menu(); system("pause"); return 0; } |
|
Переменная next |
Имеет тип element Хранит указатель на последний элемент списка |
struct element{ string data; element *next; }; |
2.2. Блок-схемы алгоритмов
Блок-схема реализации функции replace
|
Блок-схема реализации функции add
Блок-схема реализации функции menu
2.3. Реализация программы
Результат работы данной программы представлен на рисунке 5.
Рисунок 5 - Результат работы программы
Сначала программа запускается инициализирует перемену s которая вызывает класс и функцию меню внутри
list s;
s.menu();
system("pause");
После вызова программа запрашивает размер списка :
cout<<"Введите размер списка: ";
cin>>l;
cout<<endl;
Далее программа просит ввести слова которые мы будем заменять
for (int i=1;i<=l;i++){
cout<<"Введите "<<i<<" слово: ";
cin>>word;
add(word);
cout<<endl;
}
После программа запрашивает слово которым мы будем заменять все другие слова :
cout<<"введите слово на которое нужно заменить все слова: ";
cin>>word;
cout<<endl;
После ввода слова вызывается функция replace которая проводит замену всех слов
replace(word);
show();
Заключение
В результате выполнения данной расчетно-графической работы были выполнены все поставленные задачи. При выполнении работы был описан класс для работы с односвязным списком, созданы и использованы функции, конструктор. При тестировании программы необходимые данные вводились с клавиатуры, а динамическая структура данных постоянно хранилась в памяти.
Список литературы
- http://www.cplusplus.com
- https://ru.wikipedia.org
- Стефан Р. Дэвис. С++ Для чайников.
- Шилдт Г.С. Базовый курс С++, 3 издание, 2010 г.
- Литвиненко Н. А. Технология программирования на С++.
- Коплиен Дж. Мультипарадигменное проектирование для С++.
- Романов Е.Л. Си++. От дилетанта до профессионала.
Приложение
#include<iostream>
#include<stdlib.h>
#include<string>
using namespace std;
struct element{
string data;
element *next;
};
class list{
private:
element *first;
public:
list(){
first=NULL;}
void add(string s){
element *newelement= new element;
newelement->data=s;
newelement->next=first;
first=newelement;
};
void show(){
setlocale(LC_CTYPE, "rus");
element *n=first;
while(n){
cout<<n->data<<" ";
n=n->next;
}
cout<<endl;
};
void replace(string s){
element *n=first;
while(n){
n->data=s;
n=n->next;
}
};
void menu(){
setlocale(LC_CTYPE, "rus");
int l;
string word;
cout<<"Введите размер списка: ";
cin>>l;
cout<<endl;
for (int i=1;i<=l;i++){
cout<<"Введите "<<i<<" слово: ";
cin>>word;
add(word);
cout<<endl;
}
show();
cout<<"введите слово на которое нужно заменить все слова: ";
cin>>word;
cout<<endl;
replace(word);
show();
};
};
int main(){
list s;
s.menu();
system("pause");
return 0;
}
Скачать: