Մի քանի օր առաջ Լիլիթն ինձ առաջարկեց գրել միակապ ցուցակը շրջելու ֆունկցիան՝ օգտագործելով ռեկուրսիվ ալգորիթմ։ Առաջին բանը, որ միտքս եկավ՝ թե ինչպես կարելի է դա ան մի այնպիսի լեզվով, որտեղ ցուցակը ներդրված տիպ է, և արդեն առկա են ցուցակի հետ գործողություններ կատարող ֆունկցիաները։ Օրինակ, Scheme լեզվով գրված պրոցեդուրան կարող է ունենալ այսպիսի տեսք․
(define (reverse-it li) (define (reverse-it-rec l r) (if (null? l) r (reverse-it-rec (cdr l) (cons (car l) r)))) (reverse-it-rec li '()))
Այստեղ reverse-it
պրոցեդուրայի մարմնում սահմանված է վերջին կանչի ռեկուրսիա (tail recursive) ունեցող reverse-it-rec
պրոցոդուրան, որում էլ հենց կտարվում է տրված ցուցակի շրջելը։ reverse-it-rec
֊ն ուն երկու պարամետր՝ ցուցակի չշրջված մասը և արդեն շրջված մասը։ Պարզ է, որ reverse-it
֊ում նրան կանչելիս առաջին արգումենտը պետք է լինի շրջվելիք ցուցակը, իսկ երկրորդը՝ դարարկ ցուցակ։ Եթե l
֊ը դատարկ է, ապա համարվում է, որ r
-ը արդեն շրջված ցուցակն է, և այն վերադարձվում է որպես արդյունք։ Հակառակ դեպքում l
֊ի առաջին տարրը կցվում է r
-ի սկզբից, և reverse-it-rec
ի ռեկուրսիվ կանչը կիրառվում է l
֊ի պոչի և այդ նոր r
֊ի նկատմամբ։
Եվ այսպես, սահմանում եմ միակապ ցուցակի մեկ հանգույցը ներկայացնող node
ստրուկտուրան։ Այն ունի երկու երկու դաշտ՝ մեկը ինֆորմացիայի համար, մյուսը՝ հաջորդ հանգույցին կապելու։ Պարզության համար ինֆորմացիայի տիպն ընտրել եմ double
։
strcut node { double data; struct node* next; };
Հանգույցներ կառուցելու համար ինձ պետ է նաև create_node
ֆունկցիան, այն ստանում է double
թիվ և վերադարձնում է այդ թիվը պարունակող նոր ստեղծված հանգույցի ցուցիչը։
struct node* create_node( double d ) { struct node res = malloc(sizeof(struct node)); res->data = d; res->next = NULL; return res; }
Աշխատանիքի միջանկյալ ու վերջնական արդյունքները տեսնելու համար պետք է գալու նաև ցուցակն արտածող print_list
ֆունկցիան։ Դա էլ սահմանեմ․
void print_list_rec( struct node* list ) { if( list == NULL ) return; printf("%lf ", list->data); print_list_rec( list->next ); } void print_list( struct node* list ) { printf("{ "); print_list_rec( list ); printf("}\n"); }
Հիմա ամենահետաքրքիր պահն է։ Ես հանմանում եմ reverse_it
և reverse_it_rec
ֆունկցիաները՝ փորձելով վերարտադրել վերը բերված Scheme պրոցեդուրայի վարքը։
struct node* reverse_it_rec( struct node* l, struct node* r ) { if( l == NULL ) /* երբ ցուցակը դատարկ է */ return r; /* արդյունքը կապված է r ցուցիչին */ struct node* h = l; /* h֊ը ցուցակի գլուխն է */ l = l->next; ․ /* l֊ը հիմա ցուցակի պոչն է, դեռ չշրջված */ հ->next = r; /* սկզբնական l֊ի առաջին տարրը կապել r֊ին */ reverse_it_rec( l, h ); }
Դե իսկ reverse_it
ֆունկցաին պարզապես կանչելու է reverse_it_rec
֊ը՝ առաջին արգումենտում տալով շրջվելիք ցուցակը, իսկ երկրորդում՝ NULL
։
struct node* revers_it( struct node* list ) { return reverse_it_rec( list, NULL ); }
Այսքանը։ Հիմա կարող եմ վերը ներկայացված կոդը գրել ֆայլի մեջ, կցել stdio.h
և stdlib.h
ֆայլերը, օրինակ պատրաստել main
ֆունկցիայում և տեսնել, թե ինչպես է աշխատում իմ գրած ֆունկցիան։
Օրինակը շատ պարզ է․ կառուցում եմ ցուցակի հինգ հանգույցներ՝ օգտագործելով create_node
ֆունկցիան, ապա դրանք իրար եմ կապում next
ցուցիչի օգնությամբ։
struct node* n0 = create_node(1); struct node* n1 = create_node(2); n0->next = n1; struct node* n2 = create_node(3); n1->next = n2; struct node* n3 = create_node(4); n2->next = n3; struct node* n4 = create_node(5); n3->next = n4;
Ցուցակը տպում եմ, որպեսզի տեսնեմ տարրերի սկզբնական հաջորդականությունը։ Այնուհետև այն շրջում եմ reverse_it
ֆուկցիայի օգնությամբ, և նորից տպում եմ ստացված ցուցակը։
print_list(n0); struct node* rl = reverse_list(n0); print_list(rl);
Ահա արդյունքը․
{ 1.000000 2.000000 3.000000 4.000000 5.000000 } { 5.000000 4.000000 3.000000 2.000000 1.000000 }
Տեսնելու համար, թե ինչ տեսք ունեն l
և r
ցուցակները ռեկուրսիայի ամեն մի կանչի ժամանակ, կարելի է reverse_it_rec
ֆունկցիայի սկզբում ավելացնել print_list(l)
և print_list(r)
արտահայտությունները։
Comments: no replies