 |
Последовательный и бинарный поиск, сравнение способов организации поиска.
|
|
|
|
Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация, когда V содержит один элемент, а в В имеется не более одного такого элемента.
Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi - относительная частота использования элемента Кi в В, а Si - количество сравнений, необходимое для его поиска, то
Max{А} = max{ Si, i=1,n }; Avg{А} = Pi*Si.
Последовательный поиск предусматривает последовательный просмотр всех элементов списка В в порядке их расположения, пока не найдется элемент, равный V. Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка.
Рассмотрим пример, когда V содержит один элемент и встречается в B один раз.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace PrFind
{
public partial class frmFind: Form
{
int N = 100;
int[] A = new int[30000];
public frmFind()
{
InitializeComponent();
}
private void btnExit_Click(object sender, EventArgs e)
{
Close();
}
private void btnCreate_Click(object sender, EventArgs e)
{
Random rnd = new Random();
for (int I = 0; I < N; I++)
A[I] = rnd.Next(101) - 50;
lstMassiv.Items.Clear();
for (int I = 0; I < N; I++)
lstMassiv.Items.Add(Convert.ToString(I) + " - " + Convert.ToString(A[I]));
}
private void btnPusk_Click(object sender, EventArgs e)
{
int F = Convert.ToInt16(txtF.Text);
|
|
|
lstResult.Items.Clear();
for (int I = 0; I < N; I++)
if (A[I] == F)
lstResult.Items.Add("Номер - " + Convert.ToInt16(I));
}
}
}
Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск состоит в том, что ключ V сравнивается со средним элементом списка. Если эти значения окажутся равными, то искомый элемент найден, в противном случае поиск продолжается в одной из половин списка.
Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg бинарного поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов.
Пусть, например, во входном потоке задано 10 чисел, К1,К2,...,К10, V - элементы списка и ключ. Известно, что список упорядочен по возрастанию, и элемент V в списке имеется. Составим программу для ввода данных и осуществления бинарного поиска ключа V в списке К1,К2,...,К10.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace PrFind
{
public partial class frmFind: Form
{
int N = 100;
int[] A = new int[30000];
public frmFind()
{
InitializeComponent();
}
private void btnExit_Click(object sender, EventArgs e)
{
Close();
}
private void btnCreate_Click(object sender, EventArgs e)
{
Random rnd = new Random();
for (int I = 0; I < N; I++)
A[I] = rnd.Next(101) - 50;
for (int j = 0; j < N; j++)
{
int indmin = j;
for (int i = j + 1; i < N; i++)
if (A[i] < A[indmin]) indmin = i;
int tmp = A[j];
A[j] = A[indmin];
A[indmin] = tmp;
}
lstMassiv.Items.Clear();
for (int I = 0; I < N; I++)
lstMassiv.Items.Add(Convert.ToString(I) + " - " + Convert.ToString(A[I]));
}
private void btnPusk_Click(object sender, EventArgs e)
{
int F = Convert.ToInt16(txtF.Text);
int i=0, j=N-1,
m=(i+j)/2;
while ((A[m]!= F) && (i!= m) && (j!= m))
{
if (A[m] < F)
i = m;
else j = m;
m = (i + j) / 2;
}
if ((i!=m) && (j!=m))
lblResult.Text="Совпадение с элементом номер " + Convert.ToInt16(m);
else lblResult.Text="Такого элемента нет";
|
|
|
}
}
ДИАЛОГИ
Диалоги предназначены для выполнения стандартных задач Windows по заказу пользователя в диалоговом режиме.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.IO;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace PrDialog
{
public partial class frmDialog: Form
{
Graphics picGraf;
Pen tmpPen;
Brush tmpBrush;
public frmDialog()
{
InitializeComponent();
}
private void mnuExit_Click_1(object sender, EventArgs e)
{
Close();
}
private void mnuColor_Click(object sender, EventArgs e)
{
ColorDialog clrDialog = new ColorDialog();
if (clrDialog.ShowDialog() == DialogResult.OK)
// tmpPen = new Pen(clrDialog.Color);
tmpBrush = new SolidBrush(clrDialog.Color);
}
private void mnuPusk_Click(object sender, EventArgs e)
{
//picGraf.DrawLine(tmpPen, 0, 0, 100, 100);
picGraf.FillEllipse(tmpBrush, 0, 0, 100, 100);
}
private void frmDialog_Load(object sender, EventArgs e)
{
picGraf = picDraw.CreateGraphics();
}
private void mnuSave_Click(object sender, EventArgs e)
{
SaveFileDialog saveFileDialog1 = new SaveFileDialog();
saveFileDialog1.Filter = "JPeg Image|*.jpg|Bitmap Image|*.bmp|Gif Image|*.gif";
saveFileDialog1.Title = "Save an Image File";
saveFileDialog1.ShowDialog();
if (saveFileDialog1.FileName!= "")
{
System.IO.FileStream fs =
(System.IO.FileStream)saveFileDialog1.OpenFile();
switch (saveFileDialog1.FilterIndex)
{
case 1:
picDraw.Image.Save(fs,
System.Drawing.Imaging.ImageFormat.Jpeg);
break;
case 2:
picDraw.Image.Save(fs,
System.Drawing.Imaging.ImageFormat.Bmp);
break;
case 3:
picDraw.Image.Save(fs,
System.Drawing.Imaging.ImageFormat.Gif);
break;
}
fs.Close();
}
}
private void mnuLoad_Click(object sender, EventArgs e)
{
OpenFileDialog opnDialog = new OpenFileDialog();
opnDialog.Filter = "Picture files (*.bmp)|*.bmp";
if (opnDialog.ShowDialog() == DialogResult.OK)
{
picDraw.Image = new Bitmap(opnDialog.OpenFile());
}
}
}
}
Классы и ООП
Объектно-ориентированное программирование и проектирование построено на классах. Любую программную систему, выстроенную в объектном стиле, можно рассматривать как совокупность классов, возможно, объединенных в проекты, пространства имен, решения, как это делается при программировании в Visual Studio.Net.
Две роли классов
У класса две различные роли: модуля и типа данных. Класс - это модуль, архитектурная единица построения программной системы.
Вторая роль класса не менее важна. Класс - это тип данных, задающий реализацию некоторой абстракции данных, характерной для задачи, в интересах которой создается программная система.
Объектно-ориентированная разработка программной системы основана на стиле, называемом проектированием от данных. Проектирование системы сводится к поиску абстракций данных, подходящих для конкретной задачи. Каждая из таких абстракций реализуется в виде класса, которые и становятся модулями - архитектурными единицами построения нашей системы. В основе класса лежит абстрактный тип данных.
|
|
|
Синтаксис класса
[атрибуты][модификаторы] class имя_класса [:список_родителей]{тело_класса}В простых случаях объявление класса выглядит так:
public class Rational {тело_класса}В теле класса могут быть объявлены:
- константы;
- поля;
- конструкторы и деструкторы;
- методы;
- события;
- делегаты;
- классы (структуры, интерфейсы, перечисления).
Поля класса
Поля класса синтаксически являются обычными переменными (объектами) языка. Их описание удовлетворяет обычным правилам объявления переменных.
Доступ к полям
Каждое поле имеет модификатор доступа, принимающий одно из четырех значений: public, private, protected, internal.
| Модификатор доступа | Описание |
| public | Член доступен вне определения класса и иерархии производных классов. |
| protected | Член невидим за пределами класса, к нему могут обращаться только производные классы. |
| private | Член недоступен за пределами области видимости определяющего его класса. Поэтому доступа к этим членам нет даже у производных классов. |
| internal | Член видим только в пределах текущей единицы компиляции. Модификатор доступа internals вплане ограничения доступа является гибридом public и protected, зависимым от местоположения кода. |
Атрибутом доступа по умолчанию является атрибут private.
Методы класса
Методы класса синтаксически являются обычными процедурами и функциями языка.
Доступ к методам
Каждый метод имеет модификатор доступа, принимающий одно из четырех значений: public, private, protected, internal.
Методы-свойства
Методы, называемые свойствами (Properties), представляют специальную синтаксическую конструкцию, предназначенную для обеспечения эффективной работы со свойствами.
Пять наиболее употребительных стратегий:
- чтение, запись (Read, Write);
- чтение, запись при первом обращении (Read, Write-once);
- только чтение (Read-only);
- только запись (Write-only);
- ни чтения, ни записи (Not Read, Not Write).
Открытость свойств (атрибут public) позволяет реализовать только первую стратегию. В языке C# принято, как и в других объектных языках, свойства объявлять закрытыми, а нужную стратегию доступа организовывать через методы. Для эффективности этого процесса и введены специальные методы-свойства.
|
|
|
Пример:
Рассмотрим класс Person, у которого пять полей: fam, status, salary, age, health, характеризующих соответственно фамилию, статус, зарплату, возраст и здоровье персоны. Для каждого из этих полей может быть разумной своя стратегия доступа. Возраст доступен для чтения и записи, фамилию можно задать только один раз, статус можно только читать, зарплата недоступна для чтения, а здоровье закрыто для доступа и только специальные методы класса могут сообщать некоторую информацию о здоровье персоны. Вот как на C# можно обеспечить эти стратегии доступа к закрытым полям класса:
public class Person{ //поля (все закрыты) string fam="", status="", health=""; int age=0, salary=0; //методы - свойства /// <summary> ///стратегия: Read,Write-once (Чтение, запись при ///первом обращении) /// </summary> public string Fam { set {if (fam == "") fam = value;} get {return(fam);} } /// <summary> ///стратегия: Read-only(Только чтение) /// </summary> public string Status { get {return(status);} } /// <summary> ///стратегия: Read,Write (Чтение, запись) /// </summary> public int Age { set { age = value; if(age < 7)status ="ребенок"; else if(age <17)status ="школьник"; else if (age < 22)status = "студент"; else status = "служащий"; } get {return(age);} } /// <summary> ///стратегия: Write-only (Только запись) /// </summary> public int Salary { set {salary = value;} }}Рассмотрим теперь общий синтаксис методов-свойств. Пусть name - это закрытое свойство. Тогда для него можно определить открытый метод-свойство (функцию), возвращающую тот же тип, что и поле name. Имя метода обычно близко к имени поля (например, Name). Тело свойства содержит два метода - get и set, один из которых может быть опущен. Метод get возвращает значение закрытого поля, метод set - устанавливает значение, используя передаваемое ему значение в момент вызова, хранящееся в служебной переменной со стандартным именем value. Поскольку get и set - это обычные процедуры языка, то программно можно реализовать сколь угодно сложные стратегии доступа. В нашем примере фамилия меняется, только если ее значение равно пустой строке и это означает, что фамилия персоны ни разу еще не задавалась. Статус персоны пересчитывается автоматически при всяком изменении возраста, явно изменять его нельзя. Вот пример, показывающий, как некоторый клиент создает и работает с полями персоны:
private void btnPusk_Click(object sender, EventArgs e)
{
Person pers1 = new Person();
pers1.Fam = "Петров";
pers1.Age = 21;
pers1.Salary = 10000;
lblResult.Text=pers1.Fam + " " + pers1.Age + " " + pers1.Status;
|
|
|
pers1.Fam = "Иванов";
pers1.Age += 1;
lblResult1.Text = pers1.Fam + " " + pers1.Age + " " + pers1.Status;
}
Заметьте, клиент работает с методами-свойствами так, словно они являются настоящими полями, вызывая их как в правой, так и в левой части оператора присваивания. Заметьте также, что с каждым полем можно работать только в полном соответствии с той стратегией, которую реализует данное свойство. Попытка изменения фамилии не принесет успеха, а изменение возраста приведет и к одновременному изменению статуса.
Индексаторы
Свойства являются частным случаем метода класса с особым синтаксисом. Еще одним частным случаем является индексатор. Метод-индексатор является обобщением метода-свойства. Он обеспечивает доступ к закрытому полю, представляющему массив. Объекты класса индексируются по этому полю.
Синтаксически объявление индексатора - такое же, как и в случае свойств, но методы get и set приобретают аргументы по числу размерности массива, задающего индексы элемента, значение которого читается или обновляется. Важным ограничением является то, что у класса может быть только один индексатор и у этого индексатора стандартное имя this. Так что если среди полей класса есть несколько массивов, то индексация объектов может быть выполнена только по одному из них.
Добавим в класс Person свойство children, задающее детей персоны, сделаем это свойство закрытым, а доступ к нему обеспечит индексатор:
const int Child_Max = 20; //максимальное число детейPerson[] children = new Person[Child_Max];public int count_children=0; //число детейpublic Person this[int i] //индексатор{ get {if (i>=0 && i< count_children)return(children[i]); else return(children[0]);} set { if (i==count_children && i< Child_Max) {children[i] = value; count_children++;} }}Имя у индексатора - this, в квадратных скобках в заголовке перечисляются индексы. В методах get и set, обеспечивающих доступ к массиву children, по которому ведется индексирование, анализируется корректность задания индекса. Закрытое поле count_children, хранящее текущее число детей, доступно только для чтения благодаря добавлению соответствующего метода-свойства. Запись в это поле происходит в методе set индексатора, когда к массиву children добавляется новый элемент.
Протестируем процесс добавления детей персоны и работу индексатора:
private void btnPusk_Click(object sender, EventArgs e)
{
Person pers1 = new Person(), pers2 = new Person(), pers3 = new Person();
pers1.Fam = "Петров";
pers1.Age = 42;
pers1.Salary = 10000;
pers1[pers1.count_children] = pers2;
pers2.Fam = "Петров";
pers2.Age = 21;
pers2.Salary = 1000;
pers1[pers1.count_children] = pers3;
pers3.Fam = "Петрова";
pers3.Age = 5;
lblResult.Text=pers1.Fam + " " + pers1.Age + " " + pers1.Status;
lblResult1.Text = pers1[0].Fam + " " + pers1[0].Age + " " + pers1[0].Status;
lblResult2.Text = pers1[1].Fam + " " + pers1[1].Age + " " + pers1[1].Status;
}
Заметьте, индексатор создает из объекта как бы массив объектов, индексированный по соответствующему полю, в данном случае по полю children.
Операции
Еще одним частным случаем являются методы, задающие над объектами-классами бинарную или унарную операцию. Введение в класс таких методов позволяет строить выражения, аналогичные арифметическим и булевым выражениям с обычно применяемыми знаками операций и сохранением приоритетов операций.
Константы
В классе могут быть объявлены константы. Константы фактически являются статическими полями, доступными только для чтения, значения которых задаются при инициализации. Однако задавать модификатор static для констант не только не нужно, но и запрещено. В нашем классе Person была задана константа Child_Max, характеризующая максимальное число детей у персоны.
Конструкторы класса
Конструктор - неотъемлемый компонент класса. Конструктор представляет собой специальный метод класса, позволяющий создавать объекты класса. Одна из синтаксических особенностей этого метода в том, что его имя должно совпадать с именем класса.
Как и когда происходит создание объектов? Чаще всего, при объявлении сущности в момент ее инициализации. Давайте обратимся к нашему последнему примеру и рассмотрим создание трех объектов класса Person:
Person pers1 = new Person(), pers2 = new Person();Person pers3= new Person("Петрова");Сущности pers1, pers2 и pers3 класса Person объявляются с инициализацией, задаваемой унарной операцией new, которой в качестве аргумента передается конструктор класса Person. У класса может быть несколько конструкторов - это типичная практика, - отличающихся сигнатурой. В данном примере в первой строке вызывается конструктор без аргументов, во второй строке для сущности pers3 вызывается конструктор с одним аргументом типа string. Разберем в деталях процесс создания:
- первым делом для сущности pers создается ссылка, пока висячая, со значением null;
- затем в динамической памяти создается объект - структура данных с полями, определяемыми классом Person. Поля объекта инициализируются значениями по умолчанию: ссылочные поля - значением null, арифметические - нулями, строковые - пустой строкой. Эту работу выполняет конструктор по умолчанию, который, можно считать, всегда вызывается в начале процесса создания. Заметьте, если инициализируется переменная значимого типа, то все происходит аналогичным образом, за исключением того, что объект создается в стеке;
- если поля класса проинициализированы, как в нашем примере, то выполняется инициализация полей заданными значениями;
- если вызван конструктор с аргументами, то начинает выполняться тело этого конструктора. Как правило, при этом происходит инициализация отдельных полей класса значениями, переданными конструктору. Так, поле fam объекта pers3 получает значение "Петрова";
- На заключительном этапе ссылка связывается с созданным объектом.
Процесс создания объектов становится сложнее, когда речь идет об объектах, являющихся потомками некоторого класса. В этом случае, прежде чем создать сам объект, нужно вызвать конструктор, создающий родительский объект. Но об этом мы еще поговорим при изучении наследования. Ключевое слово new используется в языке для двух разных целей. Во-первых, это имя операции, запускающей только что описанный процесс создания объекта. Во-вторых, это модификатор класса или метода. Роль new как модификатора будет выяснена при рассмотрении наследования.
Зачем классу нужно несколько конструкторов? Дело в том, что, в зависимости от контекста и создаваемого объекта, может требоваться различная инициализация его полей. Перегрузка конструкторов и обеспечивает решение этой задачи.
Немного экзотики, связанной с конструкторами. Конструктор может быть объявлен с атрибутом private. Понятно, что в этом случае внешний пользователь не может воспользоваться им для создания объектов. Но это могут делать методы класса, создавая объекты для собственных нужд со специальной инициализацией. Пример такого конструктора будет дан позже.
В классе можно объявить статический конструктор с атрибутом static. Он вызывается автоматически - его не нужно вызывать стандартным образом. Точный момент вызова не определен, но гарантируется, что вызов произойдет до создания первого объекта класса. Такой конструктор может выполнять некоторую предварительную работу, которую нужно выполнить один раз, например, связаться с базой данных, заполнить значения статических полей класса, создать константы класса, выполнить другие подобные действия. Статический конструктор, вызываемый автоматически, не должен иметь модификаторов доступа. Вот пример объявления такого конструктора в классе Person:
static Person(){ Console.WriteLine("Выполняется статический конструктор!");}В нашей тестирующей процедуре, работающей с объектами класса Person, этот конструктор вызывается первым, и первым появляется сообщение этого конструктора.
Подводя итоги, можно отметить, что объекты создаются динамически в процессе выполнения программы - для создания объекта всегда вызывается тот или иной конструктор класса.
Деструкторы класса
Если задача создания объектов полностью возлагается на программиста, то задача удаления объектов, после того, как они стали не нужными, в Visual Studio.Net снята с программиста и возложена на соответствующий инструментарий - сборщик мусора. В классическом варианте языка C++ деструктор так же необходим классу, как и конструктор. В языке C# y класса может быть деструктор, но он не занимается удалением объектов и не вызывается нормальным образом в ходе выполнения программы. Так же, как и статический конструктор, деструктор класса, если он есть, вызывается автоматически в процессе сборки мусора. Его роль - в освобождении ресурсов, например, файлов, открытых объектом. Деструктор C# фактически является финализатором (finalizer), с которыми мы еще встретимся при обсуждении исключительных ситуаций. Приведу формальное описание деструктора класса Person:
~Person(){ //Код деструктора}Имя деструктора строится из имени класса с предшествующим ему символом ~ (тильда). Как и у статического конструктора, у деструктора не указывается модификатор доступа.
|
|
|
