Միակապ ցուցակի շրջելը ռեուրսիվ եղանակով

Մի քանի օր առաջ Լիլիթն ինձ առաջարկեց գրել միակապ ցուցակը շրջելու ֆունկցիան՝ օգտագործելով ռեկուրսիվ ալգորիթմ։ Առաջին բանը, որ միտքս եկավ՝ թե ինչպես կարելի է դա ան մի այնպիսի լեզվով, որտեղ ցուցակը ներդրված տիպ է, և արդեն առկա են ցուցակի հետ գործողություններ կատարող ֆունկցիաները։ Օրինակ, 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֊ի նկատմամբ։

* * *Բայց Լիլիթն ուզում էր, որ ես սա գրեմ C++ լեզվով, որից ես շատ քիչ բան եմ հասկանում, և այդ պատճառով էլ որոշեցի գրել C լեզվով։ Սակայն այս դեպքում իրավիճակը բոլորովին այլ է․ C լեզվում չկան ո՛չ ներդրված ցուցակը, ո՛չ էլ դրա հետ աշխատող ֆունկցիաները։ Ես պետք է սկսեմ սկզբից՝ սահմանելով նախ՝ ցուցակը, ապա՝ այն շրջող ֆունկցիան։

Եվ այսպես, սահմանում եմ միակապ ցուցակի մեկ հանգույցը ներկայացնող 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) արտահայտությունները։

ՍկզբնաԱղբյուր

Միակապ ցուցակի շրջելը ռեուրսիվ եղանակով, 10.0 out of 10 based on 4 ratings

Նշագրեր: LISP, Scheme, միակապ ցուցակ, ռեկուրսիա, ցուցակ

Բաժին: C և C++, Lisp և Common Lisp, Ալգորիթմներ, Ծրագրավորում