Указатели и списки

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Лабораторная работа

Указатели и списки



Задание

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

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

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

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



1. Реализация программы (полностью весь код с комментариями)

программа многочлен указатель

using System;

using System. Collections. Generic;

using System. Linq;

using System. Text;

using System. Threading. Tasks;

namespace SiAOD_LR1

{

public class Item

{

public int Number {get; set;}

public int Power {get; set;}

public Item Next {get; set;}

public Item Back {get; set;}

}

}

using System;

using System. Collections. Generic;

using System. Linq;

using System. Text;

using System. Threading. Tasks;

namespace SiAOD_LR1

{

public class MyList

{

public Item List {get; set;}

public MyList() {List = new Item();}

 // добавление нового члена

public void Add (int number, int power)

{

ReverseEnd();

Item local = new Item()

{

Number = number,

Power = power,

Back = List

};

List. Next = local;

List = local;

}

 // упрощение выражения

public void Simplify()

{

 // индексаторы нужны для того что бы пропуска

 // проверяемый элемент при сравнии

int index = 0;

bool isEnd = false, delete = false;

Item item = new Item();

 // пока основной не кончился сверяю его с локальным

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

while (! isEnd)

{

ReverseBegin();

index++;

 // проходим в глуь списка по индексу

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

{

if (List. Next!= null)

List = List. Next;

else

isEnd = true;

}

 // записываем в предыдущий перебираемый элемент

 // получившуюся сумму

List. Back. Number += item. Number;

 // счётчик для вложенного цикла

 // стартовый индекс

int localIndex = index;

item = new Item()

{

Number = 0,

Power = List. Power

};

while (! IsEnd())

{

localIndex++;

List = List. Next;

if (List. Power == item. Power && index!= localIndex)

{

item. Number += List. Number;

 // удаление записанного члена многочлена

Item local = List = List. Back;

try

{

local. Next = List. Next. Next;

List. Next. Back = local;

List = local;

localIndex -;

}

catch

{

 // создание буферного элемента списка

 // для корректного извлечения последнего

List = local;

List. Next = new Item()

{

Back = List

};

List = List. Next;

delete = true;

break;

}

}

}

}

 // удаление буферного элемента списка (последнего)

if (delete)

{

DeleteEnd();

}

ReverseBegin();

}



 // удаление последнего

public void DeleteEnd()

{

ReverseEnd();

List = List. Back;

List. Next = null;

}

 // являемся ли мы в начале списка

public bool IsBegin()

{

return List. Back == null && List. Next!= null;

}

 // являемся ли мы в конце списка

public bool IsEnd()

{

return List. Next == null;

}

 // функция для перехода к началу списка

public void ReverseBegin()

{

while (List. Back!= null)

{

List = List. Back;

}

if (List. Back!= null && List. Next!= null)

List = List. Next;

}

 // функция для перехода к концу списка

public void ReverseEnd()

{

while (List. Next!= null)

{

List = List. Next;

}

}

public string GetPolynomial()

{

ReverseBegin();

string result = «»;

while (List. Next!= null)

{

List = List. Next;

result += GenerateMember (List. Number, List. Power);

}

result += GenerateMember (List. Number, List. Power);

return result;

}

public string GenerateMember (int number, int power)

{

return number. ToString() + «+(X^» + power. ToString() +»)»;

}

}

}

using System;

using System. Collections. Generic;

using System. Linq;

using System. Text;

using System. Threading. Tasks;

namespace SiAOD_LR1

{

public class Program

{

static void Main (string[] args)

{

var x = Math. Pow (0, 2);

MyList first = new MyList(), second = new MyList(), third = new MyList();

Random rnd = new Random();

first. Add (1, 2);

first. Add (3, 3);

first. Add (1, 1);

first. Add (1, 1);

first. Add (3, 3);

second. Add (1, 2);

second. Add (2, 3);

second. Add (1, 3);

second. Add (2, 1);

second. Add (3, 3);

Add (ref third, first, second);

Console. WriteLine («p {0}», third. GetPolynomial());

Console. WriteLine («Meaning {0}», Meaning (first, 5));

Console. WriteLine («Equality {0}», Equality (first, second));



Console. ReadKey();

}

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

static public void Add (ref MyList p, MyList q, MyList r)

{

p. ReverseEnd();

q. ReverseBegin();

p. List. Next = q. List. Next;

p. ReverseEnd();

r. ReverseBegin();

p. List. Next = r. List. Next;

p. List. Next. Back = p. List;

p. Simplify();

}

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

static public bool Equality (MyList p, MyList q)

{

p. Simplify();

q. Simplify();

while (! p. IsEnd())

{

p. List = p. List. Next;

q. ReverseBegin();

while (! q. IsEnd())

{

q. List = q. List. Next;

if (q. List. Number == p. List. Number && q. List. Power == p. List. Power)

{

Delete (ref p);

Delete (ref q);

break;

}

}

}

return Comparison (p, q);

}

static private bool Comparison (MyList p, MyList q)

{

bool result = true;

p. ReverseBegin();

q. ReverseBegin();

while (! p. IsEnd())

{

if (p. List!= q. List)

{

result = false;

}

p. List = p. List. Next;

q. List = q. List. Next;

}

return result;

}



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

static public double Meaning (MyList p, int x)

{

double result = 0;

p. ReverseBegin();

while (! p. IsEnd())

{

p. List = p. List. Next;

result += p. List. Number * Math. Pow (x, p. List. Power);

}

return result;

}

static private void Delete (ref MyList index)

{

Item local = index. List = index. List. Back;

try

{

local. Next = index. List. Next. Next;

index. List. Next. Back = local;

index. List = local;

}

catch {}

}

}

}



2. Скрин программы, в котором отражены все результаты работы программы

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

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

Редактирование нескольких передаваемых значений в методе.

Метод для замены значений двух переменных местами.

Доступ к объекту формы по ссылке для его редактирования. (Неявное использование указателей).

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

Типизированные указатели можно использовать только с перемен­ными конкретного типа, в то время как нетипизированные указатели могут указы­вать на любые данные.

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

Пример: На проводах категории 5e (интернетовых) очень часто пишут «указатель», т.е. число, которое каждый метр увеличивается. Вот есть у нас сколько-то метров такого провода. В начале написана метка 185m, через ровно 1 метр будет метка 186m и так далее. Мы знаем, что на другом конце метка 211m.

Вычтем указатели 211-185 = 26. Получается у нас всего 26 метров такого провода. Вычитание указателей на практике используется для того, чтобы узнать сколько между этими указателями «места», или в нашем случае провода. И важно одно свойство - со скольких бы мы не начинали отсчёт, всё равно получим 26 метров. Существование меток вне диапазона, например 10m или 500m нам не важно.

Теперь сложим: 211+185 = 396. Полученое число не несёт ни какой смысловой нагрузки. Причём оно указывает на метку, которой не существует (катушки обычно по 305 метров) https://ru.stackoverflow.com/questions/284850/почему-нельзя-складывать-указатели

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

Список - это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности. Экземпляры значений, находящихся в списке, называются элементами списка (англ. item, entry либо element); если значение встречается несколько раз, каждое вхождение считается отдельным элементом.

Размещено на Allbest.ru