Crazy Rebel: викификация, оформление, иллюстрация

Crazy Rebel — Fri, 16 Dec 2011 06:58:10 GMT

викификация, оформление, иллюстрация

Новая статья

: '''Из ''C'' в ''C#''''' Преобразуем код с указателями, не меняя логики работы программы [[Категория:Учебники]]

==''C->C#'': Как дважды два==

: Работа с памятью и указателями в управляемых и неуправляемых языках имеет некоторые отличия, которые нужно учитывать. '''Андрей Кузьменко''' покажет, как аккуратно адаптировать использующий их код.

Информационные технологии развиваются чрезвычайно динамично. Постоянно появляются новые процессоры, операционные системы, средства разработки и прикладные программы. И если на заре становления операционной системы Linux главным языком программирования для неё был ''C'' (именно на нём написано ядро), то теперь выбор гораздо шире. Вам нужно объектно-ориентированное программирование и переносимый графический интерфейс? Связка ''С++'' и ''Qt'' к вашим услугам. Хотите максимально полно использовать современные возможности: многопоточность, обработку исключений, автоматическое управление памятью, поддержку баз данных, XML-описания? Присмотритесь к платформе ''Mono''. А может случиться так, что вам потребуется переписать некоторый код с неуправляемого языка (''C/С++'') на управляемый язык ''С#''. Все знают, что основным отличием управляемых языков от неуправляемых является подход к работе с указателями. И на этом уроке мы рассмотрим вопрос адаптации программ, написанных на языках ''C'' и ''С++'', для платформы ''Mono'', а именно: поработаем с кодом, в котором активно используются двойные указатели.

===Делай раз===

{{Врезка|Содержание=[[Изображение:LXF137_80_1.jpg|300px|Рис. 1]] Рис. 1. Так выглядит однонаправленный линейный связный список.|Ширина=300px}}

Указатель в языке ''C'' может представлять собой как адрес одной переменной, так и адрес начала области памяти для массива. Таким образом, объявление '''int **data''' можно трактовать четырьмя способами:
# Указатель на одиночный указатель на переменную типа '''int'''.
# Указатель на одиночный указатель на массив типа '''int'''.
# Указатель на массив, содержащий указатели на одиночные переменные типа '''int'''.
# Указатель на массив, содержащий указатели на массивы переменных типа '''int'''.

Наибольший интерес для нас будут представлять варианты номер 1 и 2.

Мы начнём с использования двойного указателя в списке параметров функции. Эта ситуация постоянно возникает при анализе программ, написанных на языке ''C''. Для иллюстрации мы будем использовать код, который позволяет работать со связными списками.

Список – это структура данных, которая состоит из узлов, каждый из которых содержит как некоторые данные, так и одну или две ссылки на следующее и/или предыдущее поле. Мы будем работать с линейным однонаправленным списком (рис. 1), в котором можно передвигаться только в направлении конца списка, а получить адрес предшествующего узла из текущего напрямую нельзя.

На языке ''C'' эта структура данных описывается так:

<source lang=c>
typedef struct Node
{
int value;
struct Node *next;
} Node;
</source>

Наш список будет содержать целочисленные значения, хотя тип данных может быть абсолютно любым. Для объявления в программе «головы» списка достаточно написать

Node *head = NULL;

Теперь любые операции со списком будут осуществляться посредством адресации через указатель '''head'''.

Рассмотрим добавление данных в конец списка:

<source lang=c>
void insert(Node **head, int x)
{
if(head == NULL) return;
if(*head == NULL) *head=make_Node(x, NULL);
else insert(&((*head)->next), x);
}
</source>

Функция начинает свою работу с «головы» списка. Если указатель '''head''' имеет значение '''NULL''', то вызывается функция '''make_Node()''', которая выделяет память под узел списка и выполняет инициализацию его полей. В противном случае будет выполнен переход по ссылке '''next''' текущего узла, и описанная выше последовательность действий будет рекурсивно повторяться до тех пор, пока не обнаружится последний элемент списка, после которого будут вставлены новые данные.

Вот и двойной указатель! А, собственно, почему здесь используется именно указатель на указатель? Дело в том, что, будучи параметром функции, сам указатель передаётся по значению; таким образом, в теле функции можно изменять данные, адресуемые посредством указателя, но нельзя изменить его самого с сохранением нового значения. В самом деле, если мы хотим вставить данные в пустой список, то после выделения памяти и связывания её с указателем '''head''' мы рассчитываем, что по возвращении из функции '''insert()''' указатель '''head''' будет отличен от '''NULL'''. Однако, если он передаётся по значению, наши ожидания не оправдаются. Чтобы преодолеть данное ограничение, указатель и передаётся не по значению, а по ссылке, через указатель на указатель. В этом случае мы можем как манипулировать данными, связанными с указателем '''head''', так и изменять сам указатель.

После выполнения программы

<source lang=c>
int main(void)
{
Node *head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
insert(&head, 50);
print_list(head);
kill_list(head);
return (0);
}
</source>

===Молоток и напильник===

Как же нужно действовать в случае, если нам необходимо переписать код, аналогичный вышеприведённому (двойной указатель используется как параметр функции), для платформы ''Mono''? Допустим, у нас есть класс '''Node''' (узел списка) и класс '''List''' (связный список), который в качестве поля данных имеет указатель на заглавный элемент. Конструктор, присваивающий указателю '''head''' значение '''null''', создаст пустой список, после чего пользователь объекта класса '''List''' может применять доступный ему интерфейс. Функция '''insert()''', описанная выше, осуществляет вставку нового целочисленного значения в конец списка, принимая на входе два параметра: голову списка и целочисленное значение. Поскольку голова списка является внутренним элементом класса List, то интерфейсный метод для вставки в конец списка может быть, например, таким:

public void insert_last(int x);

Пользователь просто сообщает, какое целочисленное значение он хочет вставить в список. В теле метода '''insert_last()''' вызывается некоторая функция, которая является переработанным вариантом '''insert()'''. По сути, происходит прямой транслирующий реинжиниринг существующего кода, когда фрагмент старого кода вносится в новую среду, подвергаясь некоторым «косметическим изменениям», но при этом не меняется сама логика работы исходной программы. Мы именно адаптируем имеющийся у нас гарантированно работающий код, а не переписываем его «с нуля». Вся «содержательная начинка» программы остаётся «старой», и это ключевой момент всей работы. Таким образом, наша задача сводится к написанию внутреннего метода класса '''List''', который на входе, как и функция '''insert()''', принимает два параметра и вызывается из интерфейсной функции-обёртки '''insert_last()'''. Вопрос в том, на что и как поменять конструкцию «указатель на указатель».

Первый способ – своего рода «лобовая атака». Язык программирования ''C#'' допускает передачу параметра функции по ссылке и предоставляет для этого зарезервированные служебные слова '''out''' и '''ref'''. Тогда аналогом функции '''insert()''' станет код:

<source lang=csharp>
private void insert_ref(ref Node start, int x)
{
if (start == null) start = new Node(x, start);
else insert_ref(ref start.next, x);
}
</source>

Интерфейс пользователя:

<source lang=csharp>
public void insert_to_end(int x)
{
insert_ref(ref head, x);
}
</source>

Ключевое слово '''out''' похоже на '''ref''', за исключением того, что '''ref''' требует инициализации переменной перед ее передачей. Как правило, '''out''' используется для того, чтобы возвратить какое-либо значение, а '''ref''' позволяет вызываемым методам изменять объект, на который указывает ссылка.

Второй способ – это преобразование двойного указателя в пару одинарных указателей «входной параметр + возвращаемое значение»:

<source lang=csharp>
private Node insert_return(Node start, int x)
{
if(start == null) start = new Node(x, start);
else start.next = insert_return(start.next, x);
return start;
}
</source>

Интерфейс пользователя:

<source lang=csharp>
public void insert_last(int x)
{
head = insert_return(head, x);
}
</source>

Третий способ – использование класса-обёртки:

<source lang=csharp>
class NodePtr
{
internal Node item;
internal NodePtr(Node n) { item = n; }
}

Аналог функции '''insert()''':

<source lang=csharp>
private void insert_wrapper(NodePtr t, int x)
{
Node start = t.item;
if(start == null)
{
start = new Node(x, start);
t.item = start;
}
else
{
NodePtr sn = new NodePtr(start.next);
insert_wrapper(sn, x);
start.next = sn.item;
}
}
</source>

Интерфейс пользователя:

<source lang=csharp>
public void insert_tail(int x)
{
NodePtr np = new NodePtr(head);
insert_wrapper(np, x);
head = np.item;
}
</source>

Четвертый способ основан на эмуляции двойного указателя через массив:

<source lang=csharp>
private void insert_mas(Node [] mas, int x)
{
if(mas[0] == null)
{
mas[0] = new Node(x, null);
}
else
{
Node [] arr = {mas[0].next};
insert_mas(arr, x);
mas[0].next = arr[0];
}
}
</source>

Интерфейс пользователя:

<source lang=csharp>
public void insert_back(int x)
{
Node [] mas = {head};
insert_mas(mas, x);
head = mas[0];
}
</source>

Из предложенных четырёх способов каждый может выбрать себе по вкусу!

Читатель может спросить: а зачем рассматривать столько дополнительных вариантов, когда язык ''C#'' изначально позволяет передавать параметры функции по ссылке, используя ключевые слова '''ref''' и '''out'''? Не происходит ли тут «изобретение велосипеда»?

Я согласен с тем, что использование типовых средств, определённых стандартом, в подавляющем большинстве случаев предпочтительнее, чем применение «самопала». И если в данной конкретной ситуации передача параметра по ссылке изначально заложена в возможности языка, то использование класса-обёртки «просто из принципа» выглядит, мягко говоря, странным. В конце концов, что-либо создаётся именно с той целью, чтобы этим пользовались, а вовсе не для того, чтобы старательно исследовать варианты, как это можно сделать другим способом. Однако у меня есть некоторые замечания по данному вопросу, которыми я готов поделиться с уважаемыми читателями.

Во-первых, разбор любой ситуации с точки зрения «А как это сделать иначе?» повышает общий профессиональный уровень, позволяет лучше узнать и понять используемый инструментарий, развивает гибкость мышления.

Во-вторых, при работе с чужим кодом и столкновении с некоторым нестандартным на первый взгляд решением, вместо растерянности или раздражения у вас будет понимание того, что решение само по себе вполне стандартное, а вот насколько оно уместно (эффективно) в данном конкретном случае и можно ли сделать лучше, это уже другой вопрос.

В-третьих, жизнь показывает, что далеко не всё, что записано в стандартах и спецификациях, всегда беспрекословно и безошибочно реализуется на практике, а наличие альтернативного решения – это очень важно и ценно.

В-четвёртых, чем более общими и широко распространёнными средствами написан код, тем проще его повторно использовать на большем количестве платформ без дополнительной доработки.

Закончить я хочу тем, что никто не знает, что ждёт нас в будущем. Может быть, пройдёт ещё несколько лет, и появится некий «наследник» ''Mono'', который будет ориентирован на встроенные системы, многопоточность, функциональное программирование, но не будет иметь передачи параметра функции по ссылке. И что тогда делать? Вспомним Microsoft: ''Visual Basic'' и ''Visual Basic .NET'' – это разные языки программирования…

===Делай два===

{{Врезка|Содержание=[[Изображение:LXF137_81_1.jpg|150px|Рис. 2]] Рис. 2. Простейший пример дерева поиска.|Ширина=150px}}

Следующим шагом рассмотрим ситуацию, когда конструкция «указатель на указатель» используется вне контекста параметров функции, а именно – в коде логики программы. В качестве интересного и поучительного примера возьмем реализацию алгоритма вставки данных в корень бинарного дерева поиска, которая будет «переведена» с языка ''С++'' на ''C#''.

Бинарное дерево '''Т''' является либо пустым, либо состоит из элемента, называемого корнем, и двух составляющих бинарных деревьев '''left_tree(Т)''' и '''right_tree(Т)''', называемых левым поддеревом и правым поддеревом '''Т'''.

Бинарное дерево поиска '''Т''' – это бинарное дерево, такое, что '''Т''' либо пусто, либо
* Каждый элемент в дереве '''left_tree(Т)''' меньше корневого элемента дерева '''Т'''.
* Каждый элемент в дереве '''right_tree(Т)''' больше корневого элемента дерева '''Т'''.
* И дерево '''left_tree(Т)''', и дерево '''right_tree(Т)''' являются бинарными деревьями поиска.

Графически это определение представлено на рис. 2. На языке ''С#'' узел дерева может быть описан следующим образом:

<source lang=csharp>
class Node
{
internal int value;
internal Node left;
internal Node right;
}

Алгоритм вставки данных в листья бинарного дерева общеизвестен: начиная с корня, мы сравниваем вставляемый элемент с текущим и, в зависимости от результатов, осуществляем переход по левой или правой ветви до тех пор, пока не спустимся к листу дерева, после чего и осуществляем вставку.

Однако для бинарного дерева поиска существует способ добавления данных в корень дерева. Алгоритм гораздо менее известен, чем вставка листа, но в ряде случаев он может быть полезен. Вот его реализация на ''С++'':

<source lang=cpp>
void insertRoot(int data)
{
Node *current = root;
root = new Node(data, NULL, NULL);
Node **small_node = &(root->left);
Node **big_node = &(root->right);
while(current != NULL)
{
if(current->value < data)
{
*small_node = current;
small_node = &(current->right);
current = current->right;
}
else
{
*big_node = current;
big_node = &(current->left);
current = current->left;
}
}
*small_node = NULL;
*big_node = NULL;
}
</source>

Двойные указатели уже тут как тут! Начнём с ними разбираться. А чтобы теория усваивалась легче, обратимся к графической интерпретации работы функции '''insertRoot()''':
Исходное дерево представлено на рис. 3, а оно же после вставки элемента «32» в корень дерева – на рис. 4.

{{Врезка|Содержание=[[Изображение:LXF137_82_1.jpg|300px|Рис. 3]] Рис. 3. Исходное дерево поиска '''T'''.

[[Изображение:LXF137_83_1.jpg|300px|Рис. 4]] Рис. 4. Элемент «32» вставлен в корень дерева '''T'''.|Ширина=300px}}

При добавлении в корень нового узла может получиться так, что в левой части исходного дерева окажутся узлы со значениями большими, чем значение нового корня, а в правой части дерева могут быть узлы со значениями меньшими, чем значение нового корня. Следовательно, в процессе работы нужно переносить такие узлы на «правильную» сторону, чтобы после вставки нового корня сохранялась корректная структура бинарного дерева поиска. Отсюда следует, что работа осуществляется с двумя параметрами: ЧТО перемещать и КУДА перемещать. У одних узлов могут появиться новые потомки, а у других – пропадут существующие. Таким образом, местом присоединения-отсоединения становятся поля '''left''' и '''right''' узлов дерева.

Первым узлом, чьи поля могут быть изменены, будет новый корень. Изначально его поля '''left''' и '''right''' равны '''null'''. С какой стороны будет присоединяться к новому корню старый? Если значение узла меньше значения нового корня, то присоединять будем слева, иначе – справа. В контексте данного алгоритма условимся, что узел с меньшим значением присоединяется в позицию «меньше», а иначе – в позицию «больше». Строки

Node **small_node = &(root->left);
Node **big_node = &(root->right);

указывают, что стартовыми значениями позиций «меньше» и «больше» являются адреса указателей '''left''' и '''right''' нового корня.

В цикле '''while''' мы обходим «старое» дерево от корня к листьям в поисках узлов, которые нужно «перевесить» на «правильную» сторону. Если значение узла меньше значения нового корня, то данный узел присоединяется в позицию «меньше». Так как все узлы левого поддерева данного узла будут меньше, чем он сам, то новой позицией «меньше» следует сделать поле '''right''' данного узла, поскольку на следующих шагах алгоритма именно сюда можно будет присоединить узел из правой части дерева, который будет иметь значение меньшее, чем у нового корня, но большее, чем значение того узла, чьё поле '''right''' стало позицией «меньше».

После этого осуществляется переход

current = current->right;

по исходному дереву с целью поиска там узлов для присоединения в позицию «меньше».

Если же значение узла больше значения нового корня, то данный узел присоединяется в позицию «больше», его поле '''left''' становится новой позицией «больше», а переход в дереве осуществляется по '''left'''-ссылке с целью дальнейшего поиска узлов для присоединения в позицию «больше».

Поскольку из-за «перевешивания» узлов структура исходного дерева может сильно меняться, то после обхода всего дерева выполняются строки

*small_node = NULL;
*big_node = NULL;

Это защищает нас от случая, когда физически потомок узла уже отсоединён и присоединён на новое место, но у его родителя ещё осталась на него ссылка.

Зачем здесь используются двойные указатели? Дело в том, что позиции «меньше» и «больше» могут быть как '''left'''-, так и '''right'''-ссылками узлов, а использование указателя на указатель позволяет нивелировать этот факт: узел просто ставится в некоторую правильную позицию, и не важно, «лево» это или «право». Это предоставляет нам дополнительный уровень абстракции и позволяет компактно записать код.

===Трудности перевода===

Как же переложить эту логику на язык ''C#''? Разберемся по пунктам.
* Нам нужны два обычных указателя на узлы дерева для обозначения позиций «меньше» и «больше», начальное значение которых – узел, являющийся новым корнем.
* Нужны две переменные, обозначающие «положение в пространстве» для позиций «меньше» и «больше».
* Будем считать, что «меньше» изначально находится слева, а «больше» – справа.
* В цикле обхода дерева текущий узел вставляется в позицию «меньше» или «больше» с использованием информации о том, с какой стороны находятся позиции «меньше» и «больше».

Таким образом, вместо использования адресов полей '''left''' и '''right''' для задания позиций «меньше» и «больше» используется указатель на узел и информация о том, с какой стороной нужно работать.

В результате получаем:

{{Врезка|Заголовок=Скорая помощь|Содержание=Вообще говоря, в ''C#'' есть указатели – только их использование допустимо лишь в небезопасных секциях кода. Поищите в документации по слову '''unsafe''', чтобы узнать все детали.|Ширина=200px}}

<source lang=csharp>
public void insertRoot(int data)
{
int LEFT = 1;
int RIGHT = 2;
Node current = root;
root = new Node(data, null, null);
Node small_node = root;
Node big_node = root;

int small_side = LEFT;
int big_side = RIGHT;
while(current != null)
{
if(current.value < data)
{
if(small_side == LEFT) small_node.left = current;
else small_node.right = current;
small_node = current;
small_side = RIGHT;
current = current.right;
}
else
{
if(big_side == LEFT) big_node.left = current;
else big_node.right = current;
big_node = current;
big_side = LEFT;
current = current.left;
}
}
if(small_side == LEFT) small_node.left = null;
else small_node.right = null;
if(big_side == RIGHT) big_node.right = null;
else big_node.left = null;
}
</source>

На этом всё. Желаю успешной работы!

LXF137:C - История изменений

Crazy Rebel: викификация, оформление, иллюстрация