site logo
  • Կայքի մասին
  • Ծրագրավորում
  • Ժեշտ
  • Անվտանգություն
  • Հարց ու Պատասխան (ՀուՊ)
Հունվար 30, 2013  |  By armenbadal In

Չփոփոխվող տվյալների կառուցվածքների մասին

Շարունակելով իմ նախորդ գրառման բինար որոնման ծառերի թեման, ուզում եմ նույն այդ օրինակով ցույց տալ, թե ինչպես կարելի է ծրագրեր գրել օգտագործելով միայն չփոփոխվող (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 = nil և l = nil, ապա վերադարձվում է #f։
  2. Եթե r <> nil կամ l <> nil, ապա վերադարձվում է համապատասխանաբար ձախ կամ աջ ենթածառը։
  3. Եթե r <> nil և l <> nil, ապա հեռացվում է աջ ենթածառի ամենափոքր արժեքը պարունակող հանգույցը, իսկ նրա արժեքը գրվում է արմատի արժեքի փոխարեն։
(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))))

Սկզբնաղբյուրը։ http://armenbadal.blogspot.com/2013/01/scheme.html

Չփոփոխվող տվյալների կառուցվածքների մասին, 10.0 out of 10 based on 10 ratings
binary search tree C++ lambda LISP Lisp և Common Lisp Scheme Ալգորիթմներ բինար որոնման ծառ Ծրագրավորում Ուսումնական նյութեր Վերլուծություն ցուցակ ցուցիչ
Previous StoryԻնչպես ներբեռնել ամբողջ կայքը
Next StoryԵրջանկության մեխանիկան, կամ օֆֆիսային մուտիլովկաներ

Comments: no replies

Join in: leave your comment Cancel Reply

(will not be shared)

Որոնում

Նշագրեր

*Nix-եր (18) android (17) C++ (19) C և C++ (27) Excel (10) html (10) Network Administration (16) System Administration (28) Windows 7 (14) Ալգորիթմներ (15) Անվտանգություն (29) ԳՆՈՒ/Լինուքս (16) Թեյնիկներին (57) Ժեշտ (44) Լակոնիկ (21) Լինուքս/Յունիքս հրամաններ (29) Լուսանկարչություն և մշակում (15) Խելախոսներ (19) Ծրագրավորման լեզուներ (16) Ծրագրավորում (64) Ծրագրեր (48) Հայականացում (28) Հումոր (11) Ուսումնական նյութեր (34) Սոցցանցային Հմտություններ (19) Վեբ (25) Վերլուծություն (10) Վորդպրես (21) ՏՏ և փիլիսոփայություն (21) Տվյալների բազաներ (12) Օպերացիոն համակարգեր (27) Օֆիսային ծրագրեր (22) անդրոիդ (16) բաշ (10) ինտերնետ (11) խելախոսներ (13) համացանց (15) հայատառ (10) հայերեն (11) հայերեն ստեղնաշար (11) հայկական սոֆթ (11) ստեղնաշար (10) սքրիփթ (14) վինդոուս (12) տեսանյութ (23)
Copyright ©2017 ThemeFuse. All Rights Reserved