Միակապ ցուցակի կարգավորումը (Insertion sort)

Վերջերս մի հարցազրույցի ժամանակ խնդիր առաջադրվեց C լեզվով իրականացնել միակապ ցուցակի (singly linked list) կարգավորման ալգորիթմը՝ անպայման ռեկուրսիայի օգտագործմամբ։ Ես ընտրեցի տեղադրումով կարգավորման (insertion sort) մեթոդը։ Ստորև ներկայացնում եմ դա։

Նախ՝ ցուցակի հանգույցի (node) սահմանումը, որտեղ բանալին double տիպի է․

typedef struct _node node;
struct _node {
    double data; /* բանալի */
    node* next;  /* կապ */
};

Հիմա տեղադրումով կարգավորման մասին։ Ալգորիթմի էությունն այն է, որ ամեն մի քայլում հերթական տարրը (իմ դեպքում՝ հանգույցը) տեղադրվում է իր ճիշտ տեղում։ Բնականաբար բուն տեղադրման գործողությունը կարևոր գործողություն է։ Սահմանում եմ insert_into() ֆունկցիան, որը տրված հանգույցը տեղադրում է տրված ցուցակի իր ճիշտ տեղում և վերադարձնում է ձևաձոխված ցուցակը։

node* insert_into( node* n, node* l )
{
    /* եթե ցուցակը դատարկ է, ապա տրված հանգույցը 
       վերադարձնել որպես կարգավորված ցուցակ */
    if( NULL == l ) {
        n->next = NULL;
        return n;
    }

    /* եթե տրված հանգույցի բանալին փոքր է տրված ցուցակի 
       առաջին հանգույցի բանալու արժեքից, ապա տրված 
       հանգույցը կցել ցուցակի սկզբից */
    if( n->data <= l->data ) {
        n->next = l;
        return n;
    }

    /* ռեկուրսիվ կանչով տրված հանգույցը տեղադրել ցոցակի 
       պոչի մեջ, ապա նախնական ցուցակի առաջին հանգույցը 
       կապել ձևափոխված պոչին */
    l->next = insert_into(n, l->next);
    return l;
}

Ցուցակը կարգավորող sort_list() ֆունկցիան պարզապես կանչում է insert_into() ֆունկցիան․

node* sort_list( node* l )
{
    /* ցուցակը դատարկ լինելու դեպքը */
    if( NULL == l )
        return NULL;

    /* ցուցակի առաջին հանգույցը տեղադրել կարգավորված 
       պոչի մեջ՝ ճիշտ տեղում */
    return insert_into(l, sort_list(l->next));
}

Այսքանը։

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

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

Tcl: Սիմվոլիկ դիֆերենցում

Մի քանի օր առաջ թերթում էի Structure and Interpretation of Computer Programs գիրքը և աչքովս ընկավ մի օրինակ, որտեղ հաշվում էր պարզագույն մաթեմատիկական արտահայտությունների դիֆերենցիալը (2.3.2 Example: Symbolic Differentiation)։ Փորձեցի այն վերարտադրել Tcl լեզվով ու ահա թե ինչ ստացվեց։

Նախապես ասեմ, որ արտահայտություները սահմանափակված են միայն գումարում, հանում, բազմապատկում և բաժանում բինար գործողություններով, իսկ դիֆերենցիալը հաշվող differentiate ֆունկցիան սպասում է, որ իր մուտքին տվելու է արտահայտության պրեֆիքսային ներկայացումն ու այն փոփոխականը, ըստ որի կատարվում է դիֆերենցումը։

Արտահայտությունների դիֆերենցիալը հաշվելու համար օգտագործվում են հետևյալ բանաձևերը.

1. \(C\) հաստատունի համար. \[\frac{dC}{dx}=0,\]
2. \(x\) փոփոխականի համար. \[\frac{dx}{dx}=1,\]
3. \(u+v\) գումարի համար. \[\frac{d(u+v)}{dx}=\frac{du}{dx}+\frac{dv}{dx},\]
4. \(u\cdot v\) արտադրյալի համար. \[\frac{d(uv)}{dx}=\frac{du}{dx}v+\frac{dv}{dx}u,\]
5. \(\frac{u}{v}\) քանորդի համար. \[\frac{d}{dx}\Big(\frac{u}{v}\Big)=\frac{\frac{du}{dx}v-\frac{dv}{dx}u}{v^2},\]

differentiate ռեկուրսիվ պրոցեդուրայում պարզապես ծրագրավորված են նշված բանաձևերը։

proc differentiate { src var } {
  set H [lindex $src 0]
  # constant 
  if [regexp {\d+} $H] {
    return 0
  }
  # variable
  if [regexp {\w[\w\d]*} $H] {
    if [string equal $H $var] {
      return 1
    } else {
      return 0
    }
  }
  # addition, subtraction
  if [regexp {(\+|\-)} $H] {
    set L [differentiate [lindex $src 1] $var]
    set R [differentiate [lindex $src 2] $var]
    return [addi $H $L $R]
  }
  # multiplication, division
  if [regexp {(\*|\/)} $H] {
    set A [lindex $src 1]
    set B [lindex $src 2]
    set L [muli "*" [differentiate $A $var] $B]
    set R [muli "*" [differentiate $B $var] $A]
    if [string equal {*} $H] {
      return [addi "+" $L $R]
    }
    return [muli "/" [addi "-" $L $R] [muli "*" $B $B]]
  }
}

Բացի դիֆերենցիալի հաշվումից այս պրոցեդուրան կատարում է նաև մի քանի պարզեցումներ՝ հաշվի առնելով, որ \(0\cdot x=0\), \(1\cdot x=x\) և \(0 + x=x\)։ Այս պարզեցումները կատարվում են addi, muli և numeq պրոցեդուրաներով։

proc numeq { n v } {
  if [regexp {^\d+$} $n] { 
    return [expr $n == $v]
  }
  return false
}

proc addi { o a b } {
  if [numeq $a 0] { return $b }
  if [numeq $b 0] { return $a }
  if {[regexp {^\d+$} $a] && [regexp {^\d+$} $b]} {
    return [expr $a $o $b]
  }
  return [list $o $a $b]
}

proc muli { o a b } {
  if {[numeq $a 0] || [numeq $b 0]} { return 0 }
  if [numeq $a 1] { return $b }
  if [numeq $b 1] { return $a }
  if {[regexp {^\d+$} $a] && [regexp {^\d+$} $b]} {
    return [expr $a $o $b]
  }
  return [list $o $a $b]
}

* * *
Սա շատ լավ է։ Կարելի է կառուցել արտահայտությունների պրեֆիքսային ներկայացման օրինակներ և համոզվել, որ differentiate պրոցեդուրան իր անելիքն անում է։ Բայց հետաքրքիր խնդիր է նաև ինֆիքսային գրառմամբ տրված արտահայտությունից պրեֆիքսային տեսքը կառուցելը։ Այդ խդիրը լուծելու համար ես գրել եմ ստանդարտ շարահյուսական անալիզատոր, որը կառուցում է տրված արտահայտության աբստրակտ քերականական ծառը Tcl լեզվի ցուցակի տեսքով, որն էլ հենց արտահայտության պրեֆիքսային ներկայացում է։ Ահա այդ կոդը.

namespace eval Parser {
  variable tokens [list]
  variable position -1
  variable current {}

  # սա կարելի է ասել, որ լեքսիկական անալիզատորն է
  proc tokenizer { src } {
    set temp [regsub -all -- {(\+|\-|\*|\/|\(|\))} $src { \1 }]
    set temp [string trim [regsub -all -- {\s+} $temp { }]]
    return [split $temp { }]
  }

  # ստուգում է հերթական սիմվոլը, և եթե այն համաատասխանում է 
  # սպասվածին, ապա փոխարինում է հաջորդով, հակառակ դեպքում 
  # գեներացնում է քերականական սխալ
  proc next { tok } {
    variable tokens
    variable current
    variable position
    if [regexp $tok $current] {
      incr position
      set current [lindex $tokens $position]
    } else {
      error "Syntax error"
    }
  }

  # վերլուծում է գումարման ու հանման գործողությունները
  proc parseExpr { } {
    variable current
    set R [parseTerm]
    while {({+} eq $current) || ({-} eq $current)} {
      set op $current
      next {[\+\-]}
      set R [list $op $R [parseTerm]]
    }
    return $R
  }

  # վերլուծում է բազմապատկման ու բաժանման գործողությունները
  proc parseTerm { } {
    variable current
    set R [parseFactor]
    while {({*} eq $current) || ({/} eq $current)} {
      set op $current
      next {[\*\/]}
      set R [list $op $R [parseFactor]]
    }
    return $R
  }

  # վերլուծում է հաստատունները, փոփոխականները և 
  # խմբավորման փակագծերը
  proc parseFactor { } {
    variable current
    set res {}
    if [regexp {[0-9]+} $current] {
      set res $current
      next {[0-9]+}
    } elseif [regexp {\w[\w\d]*} $current] {
      set res $current
      next {\w[\w\d]*}
    } elseif [string equal {(} $current] {
      next {[\(]}
      set res [parseExpr]
      next {[\)]}
    }
    return $res
  }

  # այս պրոցեդուրայից է սկսվում անալիզատորի աշխատանքը,
  # այն ստանում է արտահայտության տեքստը, վերլուծում է ու
  # վերադարձնում է նրա պրեֆիքսային ներկայացումը
  proc parse { src } {
    variable tokens
    variable position
    variable current
    set tokens [tokenizer $src]
    lappend tokens EOS
    set position -1
    set current {}
    next {}
    return [parseExpr]
  }
}

* * *
prefixToInfix պրոցեդուրան լուծում է հակառակ խնդիրը։ Այն իր արգումենտում ստանում է արտահայտության պրեֆիքսային ներկայացումը և վերադարձնում է ինֆիքսայինը։ Այս տարբերակով, իհարկե, այն արտահայտության մեջ դնում է ավելորդ փակագծեր, բայց այդ թերությունը հեշտությամբ կարելի է շտկել։

proc prefixToInfix { exp } {
  set H [lindex $exp 0]
  if [regexp {^\d+$} $H] {
    return $H
  }
  if [regexp {\w[\w\d]*} $H] {
    return $H
  }
  if [regexp {(\+|\-|\*|\/)} $H _ op] {
    set L [prefixToInfix [lindex $exp 1]]
    set R [prefixToInfix [lindex $exp 2]]
    return "($L $op $R)"
  }
}

Scheme: Չփոփոխվող բինար ծառերի մասին

Շարունակելով իմ նախորդ գրառման բինար որոնման ծառերի թեման, ուզում եմ նույն այդ օրինակով ցույց տալ, թե ինչպես կարելի է ծրագրեր գրել օգտագործելով միայն չփոփոխվող (immutable) տվյալների կառուցվածքներ։ Այս անգամ բինար որոնման ծառերի վարքը ծրագրավորել եմ Scheme լեզվով (այն Lisp ընտանիքի թերևս ամենահայտնի ներկայացուցիչն է)։ Ծառը ներկայացված է ցուցակի տեսքով, որի առաջին տարրը արմատի արժեքն է, երկրորդը՝ ձախ ենթածառն է, իսկ երրորդը՝ աջ ենթածառը։ Տերևներն իրենց աջ ու ձախ ենթածառերի փոխարեն պարունակում են #f արժեքը։ Օրինակ, 23 արժեքով տերևը ներկայանում է (23 #f #f) ցուցակով։ Իսկ ստորև բերված նկարում պատկերված ծառը․

        10
       /  \
      6    20
     / \    \
    4   8    28
            /  \
          23    30
            \
             26

ցուցակային ներկայացմամբ կունենա ահա այսպիսի տեսք․

(10 (6 (4 #f #f) (8 #f #f)) (20 #f (28 (23 #f (26 #f #f)) (30 #f #f))))

(Իհարկե կարելի է տերևները ներկայացնել կա՛մ ատոմներով, կա՛մ մեկ տարր պարունակող ցուցակներով։ Բայց ես ընտրել եմ այս ներկայացումը։)

Նախ ծառում արժեք ավելացնելու օրինակով ցույց տամ փոփոխվող (mutable) և չփոփոխվող (immutable) ծրագրավորելու տարբերությունները։ Ենթադրենք C լեզվով որպես բինար որոնման ծառի հանգույց սահմանված է _node ստրուկտուրան, իր _new_node կոնստրուկտորով.

typedef struct _node {
  int data;
  struct _node* left;
  struct _node* right;
} node;
node* _new_node( int value, node* l, node* r )
{
  node* result = (node*)malloc(sizeof(node));
  result->data = value;
  result->left = l;
  result->right = r;
  return result;
}

Այս տիպի հանգույցներով ծառում արժեք ավելացնելու համար սահմանված է _add_value ռեկուրսիվ ֆունկցիան, որն արգումենտում ստանում է ծառի արմատի ցուցիչի ցուցիչը և ավելացվող արժեքը:

void _add_value( node** tree, int value )
{
  if( *tree == NULL )
    *tree = _new_node( value, NULL, NULL );
  if( value < (*tree)->data )
    _add_value( &((*tree)->left), value );
  if( value > (*tree)->data )
    _add_value( &((*tree)->right), value );
}

Այս ֆունկցիայի համար ծառը փոփոխվող օբյեկտ է։ Այն դեպքում, երբ *tree ցուցիչի արժեքը NULL է, ստեղծվում է նոր հանգույց, և այդ նոր հանգույցի ցուցչիը վերագրվում է *tree ցուցիչին։ Քանի որ tree փոփոխականը ֆունկցիայի արգումենտում հայտարարված է struct _node** tree տեսքով, ապա փոփոխությունը կատարվում է հենց ծառի մեջ։

Չփոփոխվող տվյալներով տարբերակում նոր ստեղծված հանգույցն ավելացվում է ոչ թե ծառի մեջ, այլ տրոհվում է ծառը, ավելացվում է հանգույցը պետք եղած տեղում, ապա ստեղծվում է նոր ծառ։

node* _add_value_i( node* tree, int value )
{
  // եթե ծառը դատարկ է, ապա ստեղծել ու վերադարձնել նոր հանգույց
  if( tree == NULL )
    return _new_node( value, NULL, NULL );

  // տրոհել ծառը արմատի արժեքի, ձախ ու աջ ենթածառերի
  int d = tree->data;
  node* l = tree->left;
  node* r = tree->right;
  // ազատել հանգույցի զբաղեցրած հիշողությունը
  free(tree);
  
  // եթե տրված արժեքը փոքր է արմատի արժեքից, ապա 
  // ապա այն ավելացնել ձախ ենթածառում
  if( value < d )
    l = _add_value_i( l, value );
  // եթե տրված արժեքը մեծ է արմատի արժեքից, ապա 
  // ապա այն ավելացնել աջ ենթածառում
  else if( value > d )
    r = _add_value_i( r, value );
  // ստեղծել նոր արմատ ու վերադարձնել նրա ցուցիչը
  return _new_node( d, l, r );
}

(Պարզ է, որ եթե տրված արժեքը հավասար է արմատի արժեքին, ապա հանգույցը քանդելու կարիք չկա, այլ պետք է այն նույնությամբ վերադարձնել։)

Ծառում արժեք ավելացնող add-value պրոցեդուրայի սահմանումը Scheme լեզվով բերված է ստորև։ Այն համարյա նույնությամբ կրկնում է C լեզվով գրված տարբերակը։

(define add-value
  (lambda (tree val)
    (if tree
        (let ([d (car tree)] [l (cadr tree)] [r (caddr tree)])
          (cond
             [(< val d) (list d (add-value l val) r)]
             [(> val d) (list d l (add-value r val))]
             [else (list d l r)]))
        (list val #f #f))))

Քանի որ Scheme լեզվում ներդրված է աղբի հավաքման մեխանիզմը, այս պրոցեդուրայում կարիք չկա C լեզվի free() ֆունկցիային համարժեք գործողություններ կատարելու։

Ֆունկցիաների սահմանման համար Scheme լեզվում նախաատեսված է նաև (define (function-mane arguments) ...) գրելաձևը։ Բայց ինձ ավելի է դուր գալիս lambda արտահայտությամբ սահմանված (define function-name (lambda (arguments) ...) տարբերակը։ Հաջորդ բոլոր ֆունկցիաները սահմանելիս նույնպես օգտագործել եմ այս վերջին գրելաձևը։

Նաև սահմանեմ մի պրոցեդուրա, որը ծառի մեջ ավելացնում է ոչ միայն մեկ տրված արժեքը, այլ արժեքների ցուցակը։ Սա հնարավորություն կտա հեշտ ու ակնառու եղանակով կառուցել մեծ ծառեր։

(define add-to-tree
  (lambda (tree values)
    (if (empty? values)
        tree
        (add-to-tree (add-value tree (car values)) 
                     (cdr values)))))

Օրինակ, վերևի նկարում պատկերված ծառը կարելի է սահմանել (և սահմանածում համոզվելու համար արտածել) հետևյալ արտահայտություններով.

(define *tr* (add-to-tree #f '(10 6 20 4 8 28 23 30 26)))
(displayln *tr*)

Ծառից որևէ տրված արժեքը պարունակող հանգույցը հեռացնելու համար նույնպես կիրառված է նույն մոտեցումը՝ տրոհվում է ծառը, ապա հետ է հավաքվում, բայց արդեն առանց հեռացվող արժեքի։ Այն դեպքում, երբ ծառը դատարկ չէ, արմատը տրոհվում է d, l և r բաղադրիչների։ Երբ որոնվող արժեքը հավասար է d-ին, դիտարկվում են հետևյալ դեպքերը.

1. Եթե \(r=\varnothing \;\wedge\; l=\varnothing\), ապա վերադարձվում է #f։
2. Եթե \(r=\varnothing \;\vee\; l=\varnothing\), ապա վերադարձվում է համապատասխանաբար ձախ կամ աջ ենթածառը։
3. Եթե \(r\ne\varnothing \;\wedge\; l\ne\varnothing\), ապա հեռացվում է աջ ենթածառի ամենափոքր արժեքը պարունակող հանգույցը, իսկ նրա արժեքը գրվում է արմատի արժեքի փոխարեն։

(define remove-value
  (lambda (tree val)
    (if tree
      (let ([d (car tree)] [l (cadr tree)] [r (caddr tree)])
        (cond
          [(< val d)
           (list d (remove-value l val) r)]
          [(> val d)
           (list d l (remove-value r val))]
          [else
           (cond
             [(and (not l) (not r)) #f]
             [(and l (not r)) l]
             [(and (not l) r) r]
             [else
              (let* ([h (minimum-value r)]
                     [t (remove-value r h)])
                (list h l t))])]))
      #f)))

minimum-value պրոցեդուրան, որ օգտագործված է remove-value պրոցեդուրայում, վերադարձնում է իրեն տրված ծառի ամենափոքր արժեքը, կամ, այլ կերպ ասած, ծառի ամենաձախ հանգույցի արժեքը։

(define minimum-value 
  (lambda (tree)
    (let ([l (cadr tree)])
      (if (not l)
          (car tree)
          (minimum-value l)))))

* * * ՈՒ, պարզապես հետաքրքրության համար սահմանեմ նաև ծառի հետ կատարվող մի քանի գործողություններ։ Առաջինը թող լինի մի պրոցեդուրա, որ պարզում է տրված արժեքի առկայությունը ծառում։

(define contains-value 
  (lambda (tree val)
    (if tree
        (let ([d (car tree)])
          (cond 
            [(= val d) #t]
            [(< val d) (contains-value (cadr tree) val)]
            [(> val d) (contains-value (caddr tree) val)]))
        #f)))

Իսկ inorder-traverse պրոցեդուրան կատարում է ծառի ձախ-արմատ-աջ անցում՝ արմատի արժեքի վրա կիրառելով տրված պրոցեդուրան։

(define inorder-traverse 
  (lambda (tree func)
    (when tree
      (inorder-traverse (cadr tree) func)
      (func (car tree))
      (inorder-traverse (caddr tree) func))))

inorder-modify պրոցեդուրան տրված ծառից կառուցում ու վերադարձնում է մի նոր ծառ, որի հանգույցների արժեքները ձևափոխվել են ըստ տրված գործողության։

(define inorder-modify
  (lambda (tree func)
    (if tree
        (let* ([l (inorder-modify (cadr tree) func)]
               [d (func (car tree))]
               [r (inorder-modify (caddr tree) func)])
          (list d l r))
        #f)))

Այս պրոցեդուրայի աշխատանքի արդյունքը ցուցադրելու համար, օրինակ, տրված ծառից կառուցենք և արտածենք մի նոր ծառ, որի հանգույցների \(x\) արքժեքները փոխարինված են \((x\; \sqrt{x})\) տեսքի զույգերով։

(define *tr* (add-to-tree #f '(10 6 20 4 8 28 23 30 26)))
(displayln *tr*)
(displayln (inorder-modify *tr* (lambda (e) (list e (sqrt e)))))

Ահա նաև արդյունքը.

(10 (6 (4 #f #f) (8 #f #f)) (20 #f (28 (23 #f (26 #f #f)) (30 #f #f))))
((10 3.1622776601683795) ((6 2.449489742783178) ((4 2) #f #f) ((8 2.8284271247461903) #f #f)) ((20 4.47213595499958) #f ((28 5.291502622129181) ((23 4.795831523312719) #f ((26 5.0990195135927845) #f #f)) ((30 5.477225575051661) #f #f))))

Tcl ցուցակների հետ աշխատանքը

Ցուցակները Tcl լեզվում կառուցվում են list պրոցեդուրայով։ Այն ստանում է արգումենտների ցուցակ, հաշվարկում է դրանք և արդյունքներից կառուցվում է նոր ցուցակ։ Օրինակ,

set a [list [expr 1 + 2] 7 [expr 34 * 2]]

պրոցեդուրայի կատարումը a փոփոխականին կվերագրի {3 7 68} ցուցակը։ Հաստատուններից ցուցակ կարելի է կառուցել դրանք պարզապես թվարկելով "{" և "}" փախագծերի միջև։ Օրինակ,

set b {1 2 3 4 5}

Ցուցակի ամեն մի տարրն իր հերթին կարող է լինել ցուցակ։ Այդպիսին է օրինակ {a b c {3 4} d {5 6}} ցուցակը, որի տարրերից երկուսը ցուցակներ են։

Որևէ տողից կարելի է ցուցակ ստանալ, այն կտրտելով տրված բաժանիչով։ Օրինակ, եթե տրված է "a,b,c,d" տողը, ապա նրանից {a b c d} ցուցակը կարող ենք ստանալ ահա այսպես.

set c [split "a,b,c,d" ,]

Իսկ եթե տողում բաժանիչները մի քանիսն են, օրինակ ինչպես "a,b:c;d" տողում, ապա նույն {a b c d} ցուցակը կարելի է ստանալ split պրոցեդուրայի երկրորդ արգումենտում տալով բոլոր բաժանիչները.

set c [split "a,b,c,d" ",:;"]

split պրոցեդուրայի հակառակ գործողությունն է կատարում join պրոցեդուրան, որը տրված ցուցակի տարրերը տարրերը միացնում է իրար և ստանում տող՝ տարրի միջև ավելացնելով տրված տողը։ Օրինակ, {1 2 3 4} ցուցակից "1 + 2 + 3 + 4" տողը ստանալու համար կարող ենք գրել

set d [join {1 2 3 4} { + }]

Մի քանի ցուցակներ իրար կցելու և նոր ցուցակ ստանալու համար է նախատեսված concat պրոցեդուրան։ Օրինակ, {6 7 8 9}, {g h i j} և {"a 1" "b 2" "c 3"} ցուցակներից մի նոր ցուցակ կարող ենք ստանալ՝ կատարելով հետևյալ հրամանը.

set e [concat {6 7 8 9} {g h i j} {"a 1" "b 2" "c 3"}]

կատարման արդյունքում կստացվի {6 7 8 9 g h i j "a 1" "b 2" "c 3"} ցուցակը։

Ցուցակ կարելի է կազմել նաև տրված տարրը lrepeat պրոցեդուրայի օգնությամբ տրված քանակով կրկնելով։ Օրինակ, եթե ուզում ենք կառուցել տաս z տառերից բաղկացած ցուցակ, ապա պետք է գրել.

set u [lrepeat 10 z]

Տրված ցուցակի պոչից նոր տարր կցելու համար lappend պրոցեդուրայի առաջին արդումենտում պետք է տալ այն ցուցակը, որին ուզում ենք կցել տարրերը, իսկ հաջորդ արգումենտներով՝ կցվող տարրերը։ Օրինակ,

set a [list 1 2 3]
lappend a 4 5 6

Առաջին տողը կատարվելիս a փոփոխականի վերագրվում է {1 2 3} ցուցակը։ Հաջորդ տողը կատարելիս արդեն a-ն փոխվում է՝ ստանալով {1 2 3 4 5 6} արժեքը։ lappend պրոցեդուրան փոխում է իր առաջին արգումենտում տրված ցուցակը, բայց նաև վերադարձնում է նոր ստեղծված ցուցակը։

Ցուցակի տարրերի միջև նոր տարրեր խցկելու համար պետք է օգտագործել linsert պրոցեդուրան։ Նրա առաջին արգումենտը ցուցակն է, որում պետք է խցկել նոր տարրեր, երկրորդը ինդեքս է՝ այն տարրի ինդեքսը, որից առաջ պետք է խցկել տարրերը, հաջորդ արգումենտներով արդեն տրվում են ավելացվող տարրերը։ Օրինակ, եթե {1 2 3} ցուցակի սկզբից 8 և 9 տարրերն ավելացնելու համար ինդեքսը պետք է տալ զրո.

linsert {1 2 3} 0 8 9

Այս հրամանը կվերադարձնի {8 9 1 2 3} ցուցակը։ Իսկ {1 8 9 2 3} ցուցակը ստանալու համար պետք է գրել հետևյալը.

linsert {1 2 3} 1 8 9

Ցուցակի վերջից տարրերն ավելացնելու համար (մոտավորապես այնպես, ինչպես անում է lappend պրոցեդուրան) ինդեքսի փոխարեն պետք է տալ end բառը.

linsert {1 2 3} end 8 9

Ցուցակի տարրերը հեռացնելու կամ այլ տարրերով փոխարինելու համար է նախատեսված lreplace պրոցեդուրան։ Այն առաջին արգումենտում ստանում է ցուցակը, որի տարրերը պետք է փոխարինել, երկրորդ և երրորդ արգումենտով ստանում է փոխարինվող տարրերի միջակայքի ինդեքսները, իսկ հաջորդ արգումենտներով ստանում է այն տարրերը, որոնք պետք է տեղադրվեն հեռացվածների փոխարեն։ Օրինակ, {1 2 3 4 5 6 7} ցուցակից {1 2 a b c d 6 7} ցուցակը ստանալու համար պետք է գրել.

lreplace {1 2 3 4 5 6 7} 2 4 a b c d

Նույն այդ ցուցակի վերջին երկու տարրերը հեռացնելու համար էլ պետք է գրել.

lreplace {1 2 3 4 5 6 7} end-2 end

Ցուցակի տարրերից որևէ մեկի արժեքը մեկ այլ արժեքով փոխարինելու համար պետք է lset պրոցեդուրային տալ ցուցակը ներկայացնող փոփոխականի անունը, տարրի ինդեքսը և նոր արժեքը։ Օրինակ, եթե a փոփոխականին վերագրված է {1.2 3.4 5.6 7.8 9.0} ցուցակը, և ուզում ենք 7.8 արժեքը փոխարինել 8.7 արժեքով, ապա կարող ենք գրել.

set a {1.2 3.4 5.6 7.8 9.0}
lset a 3 8.7

lset պրոցեդուրայով կարելի է փոփոխել նաև ներդրված ցուցակների տարրերը։ Այս դեպքում ինդեքսի փոխարեն պետք է տալ ինդեքսների ցուցակ։ Օրինակ, եթե b փոփոխականին վերագրված է {{x0 1.2} {x1 3.4} {x2 5.6} {x3 7.8} {x4 9.0}} ցուցակը, և մեզ պետք է 5.6 արժեքը փոխարինել 0.0 արժեքով, ապա կարող ենք գրել.

set b {{x0 1.2} {x1 3.4} {x2 5.6} {x3 7.8} {x4 9.0}}
lset b {2 1} 0.0

Եթե պետք է ստանալ ցուցակի տրված ինդեքսով տարրը, ապա lindex պրոցեդուրային պետք է տալ ցուցակը և պահանջվող տարրի ինդեքսը։ (Եթե որևէ ինդեքս տրված չէ, ապա այս պրոցեդուրան վերադարձնում է ամբողջ ցուցակը։) Օրինակ, հետևյալ արտահայտությունը k փոփոխականին վերագրում է {x1 3.4}.

# set b {{x0 1.2} {x1 3.4} {x2 5.6} {x3 7.8} {x4 9.0}}
set k [lindex $b 1]

Եթե հարկավոր է k փոփոխականին վերագրել 3.4 արժեքը, ապա ինդեքսի փոխարեն պետք է տալ ինդեքսների ցուցակ (ինչպես lset պրոցեդուրայի դեպքում).

set k [lindex $b {1 1}]

Մի տարրի փոխարեն ցուցակի տարրերի տրված ինդեքստներով սահմանափակված հատվածը կարելի է ստանալ lrange պրոցեդուրայով։ Այն ստանում է ցուցակը, պահանջվող հատվածի սկզբի և վերջի ինդեքսները. ընդ որում, վերջին ինդեքսով որոշվող տարրը արդյուքի մեջ չի ներառվում։ Օրինակ, {a b c d e f g h} ցուցակից def բառը ստանալու համար պետք է գրել.

join [lrange {a b c d e f g h} 3 5] {}

Ցուցակում տրված շաբլոնին համապատասխանող տարրի առկայությունը որոշելու համար է նախատեսված lsearch պրոցեդուրան։ Սա վերադարձնում է որոնվող տարրի ինդեքսը, կամ -1 արժեքը՝ եթե որոնումն անհաջող է ավարտվել։ Օրինակ, ենթադրենք, թե a փոփոխականին վերագրված է {1.2 3.4 5.6 7.8 3.4 9.0} ցուցակը։ 7.8 արժեքով տարրի ինդեքսը որոշելու համար պետք է գրել.

set k [lsearch -real $a 7.8]

որտեղ -real բանալին ցույց է տալիս, որ որոնման ժամանակ արժեքները համեմատվելու են որպես իրական թվեր։ Ցուցակը 3.4 արժեքը պարունակում է երկու անգամ և այդ երկու տարրերի ինդեքսները որոշելու համար lsearch պրոցեդուրայի կանչի ժամանակ պետք է տալ -all բանալին, և այս դեպքում կստանանք ինդեքսների ցուցակ։

set k [lsearch -real -all $a 3.4]

Այժմ ենթադրենք, թե b փոփոխականի հետ կապված է {c7 b4 a0 B6 a2 c8 a1 b3 B5} ցուցակը, և ուզում ենք ստանալ այն տարրերը, որոնց սկսվում են a տառով։

puts [lsearch -ascii -all -inline -regexp $b {^a}]

Այս արտահայտության մեջ -ascii բանալին նշում է, որ ցուցակի տարրերը տողեր են, -inline բանալին ցույց է տալիս, որ պետք է վերադարձնել ոչ թե տառերը, այլ գտնված տարրերը։ -regexp բանալին ասում է, որ որոնման ժամանակ տարրերը պետք է համապատասխանեմ տրված կանոնավոր արտահայտությանը, իսկ {^a} արտահայտությունը ճանաչում է բոլոր այն տարրերը, որոնց առաջին տարրը a է։ Եթե հարկավոր է, որ որոնում կատարելիս անտեսվեն մեծատառերի ու փոքրատառերի տարբերությունները, ապա պետք է գրել նաև -nocase բանալին։

Ցուցակները կարդավորելու (sort) համար է lsort պրոցեդուրան: Օրինակ, նախորդ b ցուցակը այբբենական եղանակով կարգավորելու համար պետք է գրել.

puts [lsort -nocase -ascii $b]

Նույն ցուցակը հակառակ կարգով կարգավորելու համար հրամանին պետք է ավելացնել -decreasing բանալին։ Եթե հարկավոր է կարգավորման ժամանակ ցուցակից հեռացնել կրկնությունները, ապա պետք է տալ նաև -unique բանալին։

Ցուցակը շրջելու համար պետք է օգտագործել lreverse պրոցեդուրան: Այն ստանում է ցուցակը և վերադարձնում է մեկ այլ ցուցակ, որում նախնականի տարրերն են՝ թվարկված հակառակ հաջորդականությամբ։ llength պրոցեդուրան պարզապես վերադարձնում է տրված ցուցակի տարրերի քանակը։