ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
Федеральное государственное бюджетное образовательное
учреждение высшего образования
«САНКТ-ПЕТЕРБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ
им. проф. М. А. БОНЧ-БРУЕВИЧА»
Кафедра программирования и вычислительной техники
Дисциплина «Алгоритмы и структуры данных»
Лабораторная работа №3
по теме «Список»
Выполнил студент
ак. группы ИКПИ-63
Котельников Г.А.
Санкт-Петербург, 2018
Постановка задачи: На основе односвязного списка разработать процедуру сложения больших чисел.
Обьясненение задачи:
Списком называется такая линейная структура, элементами которой служат записи с одним и тем же форматом, связанные друг с другом с помощью указателей, хранащихся в самих элементах.
По числу указателей списки подразделяются на: односвязные, двусвязные и многосвязные.
Односвязные списки, на основе которых построена данная лабораторная работа, имеют как минимум два поля: содержательное поле и поле с адресом
следующего элемента.
Двусвязные и двунаправленные списки дополнительно содержат поле с адресом предыдущего элемента. В этом случае они также как и односвязные списки являются линейными динамическими структурами. В элементе двусвязного, но недвунаправленного списка могут содержатся ссылки на два других произвольных элемента. В этом случае списки образуют уже нелинейную структуру. На основе таких списков можно построить и бинарное дерево-типичную нелинейную динамическую структуру. Ссылки в этой структуре будут указывать на два элемента, находящиеся на более низком иерархическом уровне.
Многосвязные списки содержат адреса многих злементов. Частным случаем многосвязного списка является граф. Многосвязные списки также как и деревья являются основой нелинейных динамических структур.
Решение задачи реализовано на языке C++. Был написан отдельный модуль списка, реализующий все его операции.
Программный код:
main.cpp
#include
#include
typedef std::string T_num_s;
//typedef std::list T_num_c;
void del_leading_zero(T_num_s& a) {
while(a.size() > 1 && a[0] == '0') {
a.erase(0, 1);
}
}
bool less_for_big_int(T_num_s a, T_num_s b) {
del_leading_zero(a);
del_leading_zero(b);
return a.size() == b.size() ? a < b : a.size() < b.size();
}
void reduce_big_int(T_num_s& minuend, const T_num_s& subtrahend) {
for(T_num_s::size_type cur_pos = 0; cur_pos < subtrahend.size(); ++cur_pos) {
T_num_s::size_type minuend_cur_pos = minuend.size() - 1 - cur_pos;
T_num_s::size_type subtrahend_cur_pos = subtrahend.size() - 1 - cur_pos;
char& cur_minuend_dig_ref = minuend [minuend_cur_pos];
const char& cur_subtrahend_dig_ref = subtrahend [subtrahend_cur_pos];
if(cur_minuend_dig_ref >= cur_subtrahend_dig_ref) {
cur_minuend_dig_ref -= cur_subtrahend_dig_ref - '0';
} else {
(cur_minuend_dig_ref -= cur_subtrahend_dig_ref - '0') += 10;
for(int i = 1; ; ++i) {
if(minuend[minuend_cur_pos - i] == '0') {
minuend[minuend_cur_pos - i] = '9';
} else {
--minuend[minuend_cur_pos - i];
break;
}
}
}
del_leading_zero(minuend);
}
del_leading_zero(minuend);
}
void inc_big_int(T_num_s& a) {
for(T_num_s::size_type cur_pos = a.size() - 1;; --cur_pos) {
if(a[cur_pos] < '9') {
++a[cur_pos];
return;
}
else {
a[cur_pos] = '0';
if(cur_pos == 0)
{
a.insert(0, "1");
return;
}
}
}
}
T_num_s div_big_int(const T_num_s& a, const T_num_s& b) {
if(b == "0") {
return "division into zero";
}
T_num_s res = "0";
T_num_s minuend = a;
T_num_s subtrahend = b;
while(subtrahend.size() < minuend.size()) {
subtrahend += '0';
}
for(;;) {
while(!less_for_big_int(minuend, subtrahend)) {
reduce_big_int(minuend, subtrahend);
inc_big_int(res);
}
if(subtrahend.size() <= b.size()) {
break;
}
subtrahend.erase(subtrahend.size() - 1);
res += '0';
del_leading_zero(res);
}
return res;
}
int main() {
std::cout << "a = ";
T_num_s a;
std::cin >> a;
del_leading_zero(a);
std::cout << "b = ";
T_num_s b;
std::cin >> b;
del_leading_zero(b);
std::cout << "a / b = "
<< div_big_int(a, b)
<< std::endl
<< std::endl
<< std::endl;
}
list.h
template
class List_t;
template
class Iterator_t {
friend List_t;
public:
Iterator_t(double val = 0.0, Iterator_t* n = nullptr, Iterator_t* p = nullptr);
Iterator_t(Iterator_t& other);
T value;
Iterator_t next();
Iterator_t prev();
const Iterator_t next() const;
const Iterator_t prev() const;
//protected:
Iterator_t* _next;
Iterator_t* _prev;
};
template
class List_t {
friend Iterator_t;
public:
List_t();
List_t(int size, T*arr);
List_t(const List_t& other);
List_t();
T& operator[](int index);
T& operator[](int index) const;
List_t operator()(int index, int length);
List_t operator()(int index, int length) const;
void push_back(T value);
void push_back(const List_t& other);
void push_front(T value);
void push_front(const List_t& other);
void push_at(T value, int index);
void push_at(const List_t& other, int index);
void change_at(T value, int index);
void change_at(const List_t& other, int index);
void remove(T value);
void remove(const List_t& other);
void include(T value);
void include(const List_t& other);
void unify();
Iterator_t iterator_front();
Iterator_t iterator_back();
Iterator_t iteraior_at(int index);
const Iterator_t iterator_front() const;
const Iterator_t iterator_back() const;
const Iterator_t iteraior_at(int index) const;
T back() const;
List_t back(int lenght) const;
T front() const;
List_t front(int lenght) const;
T at(int index);
T at(int index) const;
List_t at(int index, int lenght);
List_t at(int index, int lenght) const;
T pop_back();
void pop_back(int lenght);
T pop_front();
void pop_front(int lenght);
T pop_at(int index);
void pop_at(int index, int lenght);
int search_front(T value) const;
int search_front(T value, int start) const;
int search_back(T value) const;
int search_back(T value, int start) const;
int count(T value) const;
int count(const List_t& other) const;
bool contains(T value) const;
bool contains(const List_t& other) const;
void sort(bool assending);
List_t& operator=(const List_t&other);
bool operator==(const List_t&other) const;
bool operator!=(const List_t&other) const;
T* to_array() const;
int length() const;
void clear();
template
friend std::ostream& operator<<(std::ostream& o, List_t list);
//protected:
Iterator_t *first = nullptr, *cur = nullptr, *last = nullptr;
int len = 0, cur_pos = 0;
void go_to(int index);
inline void rm(Iterator_t* it);
Iterator_t* go_to_c(int index, Iterator_t* it = nullptr, int pos = 0) const;
inline int dist(int a, int b) const;
void init(T val);
T del();
void mergesort(Iterator_t*& start, Iterator_t*& end, int size, bool assend);
void merge(Iterator_t*& left, Iterator_t*& right, bool assend);
}; |
Скачать 16.01 Kb.