Журнал LinuxFormat - перейти на главную

LXF137:C

Материал из Linuxformat
Версия от 09:58, 16 декабря 2011; Crazy Rebel (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Подписка на печатную версию
Весь 2015 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)
Подписка на электронную версию
Весь 2015 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)
Подшивки старых номеров журнала (печатные версии)
Весь 2014 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)
Из 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;
 }

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

Источник — «http://wiki.linuxformat.ru/wiki/index.php?title=LXF137:C&oldid=13175»
Персональные инструменты
купить
подписаться
Яндекс.Метрика