LXF137:C

Материал из Linuxformat.

Из C в C# Пре­об­ра­зу­ем код с ука­за­те­ля­ми, не ме­няя ло­ги­ки ра­бо­ты про­грам­мы

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

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

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

Де­лай раз

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

1. Ука­за­тель на оди­ноч­ный ука­за­тель на пе­ре­мен­ную ти­па int.
2. Ука­за­тель на оди­ноч­ный ука­за­тель на мас­сив ти­па int.
3. Ука­за­тель на мас­сив, со­дер­жа­щий ука­за­те­ли на оди­ноч­ные пе­ре­мен­ные ти­па int.
4. Ука­за­тель на мас­сив, со­дер­жа­щий ука­за­те­ли на мас­си­вы пе­ре­мен­ных ти­па int.

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

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

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

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

typedef struct Node
 {
 	 int value;
 	 struct Node *next;
 } Node;

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

Node *head = NULL;

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

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

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

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

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

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

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);
 }

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

Как же нуж­но дей­ство­вать в слу­чае, ес­ли нам необ­хо­ди­мо пе­репи­сать код, ана­ло­гич­ный вы­ше­при­ве­дён­но­му (двой­ной ука­за­тель ис­поль­зу­ет­ся как па­ра­метр функ­ции), для плат­фор­мы 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() станет код:

private void insert_ref(ref Node start, int x)
 {
 	 if (start == null) start = new Node(x, start);
 	 else insert_ref(ref start.next, x);
 }

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

public void insert_to_end(int x)
 {
 	 insert_ref(ref head, x);
 }

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

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

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;
 }

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

public void insert_last(int x)
 {
 	 head = insert_return(head, x);
 }

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

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;
 	 }
 }

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

public void insert_tail(int x)
 {
 	 NodePtr np = new NodePtr(head);
 	 insert_wrapper(np, x);
 	 head = np.item;
 }

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

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];
 	 }
 }

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

public void insert_back(int x)
 {
 	 Node [] mas = {head};
 	 insert_mas(mas, x);
 	 head = mas[0];
 }

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

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

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

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

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

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

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

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

Де­лай два

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

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

Би­нар­ное де­ре­во по­иска Т – это би­нар­ное де­ре­во, та­кое, что Т ли­бо пусто, ли­бо

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

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

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;
 }

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

При до­бав­лении в ко­рень но­во­го уз­ла мо­жет по­лу­чить­ся так, что в ле­вой части ис­ход­но­го де­ре­ва ока­жут­ся уз­лы со зна­чения­ми боль­ши­ми, чем зна­чение но­во­го кор­ня, а в пра­вой части де­ре­ва мо­гут быть уз­лы со зна­чения­ми мень­ши­ми, чем зна­чение но­во­го кор­ня. Сле­до­ва­тель­но, в про­цес­се ра­бо­ты нуж­но пе­ре­но­сить та­кие уз­лы на «пра­виль­ную» сто­ро­ну, что­бы по­сле встав­ки но­во­го кор­ня со­хра­ня­лась кор­рект­ная струк­ту­ра би­нар­но­го де­ре­ва по­иска. От­сю­да сле­ду­ет, что ра­бо­та осу­ще­ств­ля­ет­ся с дву­мя па­ра­мет­ра­ми: ЧТО пе­ре­ме­щать и КУДА пе­ре­ме­щать. У одних уз­лов мо­гут поя­вить­ся но­вые по­том­ки, а у дру­гих – про­па­дут су­ще­ствую­щие. Та­ким об­ра­зом, ме­стом при­сое­динения-от­со­единения ста­но­вят­ся по­ля 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 для за­дания по­зи­ций «мень­ше» и «боль­ше» ис­поль­зу­ет­ся ука­за­тель на узел и ин­фор­ма­ция о том, с ка­кой сто­ро­ной нуж­но ра­бо­тать.

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

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;
 }

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