Задание №1

Текст задания

Необходимо описать тип данных, соответствующий предложенному представлению многочленов, а также разработать следующие функции и процедуры для работы с этими списками-многочленами:

- логическую функцию Equality(p,q), проверяющую равенство многочленов p и q;

- функцию Meaning(p, x), вычисляющую значение многочлена в целочисленной точке х;

- процедуру Add(p,q,r) вычисления суммы многочленов q и r, результат – многочлен p.

1.

Реализация программы

#include <iostream>

#include <windows.h>

#include <math.h>

#include <stdlib.h>

using namespace std; //функция стандартной библиотеки

struct spis

{

int koef; // коэффициент

int pow; // степень

spis *next; // указатель на след. элемент

};

bool Equality(spis*, spis*); // функция, проверяющая равенство многочленов

double Meaning(spis*, double); // функция, вычисляющая значение многоччлена в целочисленной точке х

void Add(spis*, spis*); // вычисление суммы многочленов

void russia(const char* rus); // функция руссифицирования

void printPxQx(spis*, spis*); // вывод многочленов на экран

void init(spis*, spis*, int, int); // инициализация

spis* headPx; // начало списка P(x)

spis* headQx;

spis* headRx;

spis* lastPtrPx; // предпоследний элемент списка

spis* lastPtrRx;

spis* lastPtrQx;

spis* Px; // список P(x)

spis* Qx;

spis* Rx;

int main()

{

int kolEl = 4; // количествоо элементов списка

int x = 0; // целочисленная точка

Px = new spis; // резервирование памяти

Qx = new spis;

init(Px, Qx, kolEl, kolEl); // вызов функции

Px = headPx; // присваивание списку P(x) адрес начала списка

Qx = headQx;

printPxQx(Px, Qx); // вывод многочленов на экран

Px = headPx; // присваивание списку адрес начала списка

Qx = headQx;

if (Equality(Px, Qx)) // если это - истина, то

russia("Многочлены равны \n");

else // если ложь, то

russia("Многочлены не равны \n");

russia("Введите значение x = ");

cin >> x; //ввод x

cout << "P(" << x << ")=" << Meaning(Px, x) << endl; //вывод Р с функцией Meaning

cout << "Q(" << x << ")=" << Meaning(Qx, x) << endl;

Add(Px, Qx); //функция, сложения многочленов

system("pause"); //команда задержки экрана

return 0;

}

bool Equality(spis* Px, spis* Qx) //функция, проверяющая равенство многочленов

{

bool equa = true; //если функция логического типа истина

while (Px->next != 0) //Проверяем не равен ли Px нулю и проверяем следующий эллемент

{

if ((Px->pow != Qx->pow) && (Px->koef != Qx->koef)) //если не равно и если истины оба условия

{

equa = false;

break; //досрочно прерывается исполн. оператора цикла, передается след. после цикла

}

Px = Px->next; // Проверить следующий эллемент

Qx = Qx->next;

}

return equa; //возвращает значение

}

double Meaning(spis* Mx, double x) // функция, вычисляющая значение многоччлена в целочисленной точке х

{

double mean = 0; //временная переменная = 0

while (Mx->next != 0) //Сравниваем не равны ли они нулю

{

mean += Mx->koef*pow(x, Mx->pow);

Mx = Mx->next;

}

return mean; //возвращает значение

}

void Add(spis* Px, spis* Qx) // вычисление суммы многочленов

{

Rx = new spis;//Результирующий список

int Arr[20][2];//Результирующий массив(временный)

//Первый элемент(Arr[i][0]) двумерного массива - степень, второй(Arr[i][1]) - коэффициент.

bool log = false; // определяет наличие в списке Qx степеней, которых нет в Px

int kolX = 0, koly = 0, k;

while ((Px->next != NULL)) // записываем данные в массив

{

//Перенос данных из списка в массив

Arr[kolX][0] = Px->pow;

Arr[kolX][1] = Px->koef;

//Определение количества перенесённых членов многочлена.

kolX++;

Px = Px->next;

}

k = 0;//Счётчик

kolX--;

koly = kolX;//Последний элемент многочлена в массиве

while ((Qx->next != 0))//записываем в массив

{

while (k < kolX)//Обход первого многочлена

{

if (Arr[k][0] == Qx->pow)//Если степени равны

{

log = true;//Ставим, что степень не уникальная

if (Qx->koef + Arr[k][1] != 0)//Если при сложении не занулится коэффициент(0*x^n)

Arr[k][1] += Qx->koef;//То складываем коэффициенты

else

{//Сдивгаем элементы многочлена на 1 влево

//(удаляем элемент с нулём, т.к. любое число умноженное на ноль равно нулю и при сложении на результат не влияет)

for (int i = k; i <= kolX; i++)

{

Arr[i][0] = Arr[i + 1][0];

Arr[i][1] = Arr[i + 1][1];

}

kolX--; //декримент х

koly--; //декримент у

}

}

k++;

}

if (!log) //лог отрицание

{

//Если степень в первом многочлене уникальная

//То заносим его на последнее место(пустое)

Arr[koly + 1][0] = Qx->pow;

Arr[koly + 1][1] = Qx->koef;

koly++; //Увеличиваем общее количество элементов в многочлене

}

k = 0;

Qx = Qx->next;//Выполняем обход со следующим элементом

log = false;

}

cout << "Px+Qx="; //вывод

for (int i = 0; i <= koly; i++)

{

//Перенос в результирующий список значений массива(не верный, т.к. каждый раз создаётся новый список)

Rx = new spis;

Rx->pow = Arr[i][0];

Rx->koef = Arr[i][1];

cout << Rx->koef << "x^" << Rx->pow << " "; //вывод коэффициента и степени

if (headRx == 0) //если начальный список = 0

headRx = Rx; //начало списка RX

}

}

void init(spis* Px, spis* Qx, int m, int n) // инициализация

{

int ArrPx[4][2] = { { 4, 7 },{ 2, 3 },{ 1, -1 },{ 0, 2 } };

int ArrQx[4][2] = { { 5, -2 },{ 3, 2 },{ 1, 1 },{ 0, -6 } };

for (int i = 0; i <= m; i++)

{

Px = new spis; // Новый элемент списка

Qx = new spis;

Px->pow = ArrPx[i][0]; // создание массива PX

Px->koef = ArrPx[i][1];

Qx->pow = ArrQx[i][0]; // создание массива QX

Qx->koef = ArrQx[i][1];

Px->next = NULL;

Qx->next = NULL;

if (headPx == 0)

{

headPx = Px; // первый эллемент списка

lastPtrPx = Px; // пред последний эллемент списка

headQx = Qx;

lastPtrQx = Qx;

}

else

{

lastPtrPx->next = Px; //иначе перейти на следующий элемент списка

lastPtrPx = Px; //прировнять Px к последнему значению списка

lastPtrQx->next = Qx;

lastPtrQx = Qx;

}

}

}

void printPxQx(spis* Px, spis* Qx) // вывод Px и Qx

{

cout << "P(x) = ";

while (Px->next != 0)

{

cout << Px->koef << "x^" << Px->pow << " ";

Px = Px->next;

}

cout << endl << "Q(x) = ";

while (Qx->next != 0)

{

cout << Qx->koef << "x^" << Qx->pow << " ";

Qx = Qx->next;

}

cout << endl;

}

void russia(const char* rus) // руссификация

{

char word[100];

CharToOemA(rus, word);

cout << word;

}

Контрольные вопросы

1. Перечислите наиболее частые случаи, когда может оказаться эффективной работа с указателями.

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

   2. Работа с динамическими типами данных.

2. Объясните, в чем различие между типизированными и не типизированными указателями.

   1. Типизированный указатель указывает на переменную определенного типа. Объявляется как type* pointer;

   2. Не типизированный указатель, указывает на некоторую область в памяти, тип которой не имеет значения. Нельзя разы именовать. Объявляется как void *

3. Объясните, почему сложение указателей не имеет смысла.

   1. Указатель хранит адрес, а не значение, следовательно,разность или сумма адресов не имеет никакой практической ценности.

4. Дайте определение абстрактному типу данных «список».

   1. Структура данных, характеризующая последовательность элементов определенного типа.