Միակապ ցուցակի կարգավորումը (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));
}

Այսքանը։

Python: Կապակցված ցուցակներ (I)

Որպես Python ծրագրավորման լեզվով գրված առաջին ընդգրկուն օրինակ ուզում եմ ներկայացնել կապակցված ցուցակները՝ նրանց ներքին կառուցվածքով և նրանց հետ կատարվող գործողությունների տիպիկ բազմությամբ։ Սկսեմ միակապ ցուցակներից, որոնց ամեն մի հանգույցը պարունակում է ինֆորմացիոն դաշտ և ցուցիչ իրեն հաջորդող հանգույցին։ Մոդելավորենք այդ հանգույցը Python լեզվով սահմանված Node դասով։ Այդ դասի data դաշտը նախատեսված է տվյալների համար, իսկ link դաշտը ցուցիչ է մեկ այլ հանգույցի։ Դասի դաշտերն արժեքավորող __init__ մեթոդը ստանում է հանգույցի data դաշտում գրվելիք տվյալը։

class Node:
  data = 0
  link = None

  def __init__(self, val):
    self.data = val

Node դասի Print մեթոդը արտածում է data դաշտի արժեքը, ապա, եթե link ցուցիչը տարբեր է None արժեքից՝ ցույց է տալիս մեկ այլ հանգույցի, ապա արտածում է ստորակետ սիմվոլը։

  def Print(self):
    c = ', ' if self.link != None else ''
    print(self.data, end=c)

Միակապ հանգույցներով կապակցված ցուցակը սահմանված է որպես List դաս։ Այդ դասի միակ head դաշտը ցույց է տալիս ցուցակի առաջին հանգույցին։

class List:
  data = None

Եթե head==None, ապա ցուցակը դատարկ է։ Այս վերջին փաստը ծրագրավորված է Empty մեթոդով։

  def Empty(self):
    return None == self.head

Ցուցակի պարունակությունն արտածելու համար սահմանված է Print մեթոդը։ Այն արտածում է «[» նիշը, անցում է կատարում ցուցակի հանգույցներով և ամեն մի հանգույցն արտածում է Node դասի Print մեթոդով, ապա վերջում արտածում է «]» նիշը։

  def Print(self):
    print('[', end='')
    temp = self.head
    while temp != None:
      temp.Print()
      temp = temp.link
    print(']')

Ցուցակի սկզբում նոր տարր (նոր հանգույց) ավելացնելու գործողությունը հասարակ է։ Պետք է ստեղծել նոր հանգույց, նրա link ցուցիչը կապել ցուցակի սկիզբը ցույց տվող head ցուցիչին, ապա head ցուցիչը տեղափոխել նոր ավելացրած հանգույցի վրա։

  def AddFront(self, val):
    nd = Node(val)
    nd.link = self.head
    self.head = nd

Քիչ ավելի շատ գործողություններ է պահանջվում նոր տարրը ցուցակի վերջում ավելացնելու համար։ Ստեղծվում է նոր հանգույց՝ տրված պարունակությամբ։ Եթե ցուցակը դատարկ է՝ head==None, ապա head ցուցիչը կապվում է նոր ստեղծված հանգույցին։ Եթե ցուցակը դատարկ չէ, ապա որևէ ժամանակավոր ցուցիչով որոշվում է ցուցակի վերջին հանգույցը և այդ վերջին հանգույցի link ցուցիչը կապվում է նոր հանգույցին։

  def AddBack(self, val):
    nd = Node(val)
    if self.head == None:
      self.head = nd
    else:
      tail = self.head
      while tail.link != None:
        tail = tail.link
      tail.link = nd

Ցուցակի սկզբից հանգույց հեռացնելու համար head ցուցիչը տեղափոխվում է առաջինին հաջորդող հանգույցի վրա (այն կարող է բացակայել, եթե ցուցակը պարունակում է միայն մեկ հանգույց), և վերադարձվում է հին առաջին (նախորդ) հանգույցի պարունակությունը։ Քանի որ Python-ը աղբի ավտոմատ հավաքման մեխանիզմով լեզու է, կարիք չկա բացահայտ կերպով ազատել հեռացված հանգույցի զբաղեցրած հիշողությունը։

  def RemoveFront(self):
    if self.head == None:
      return None
    t = self.head
    self.head = t.link
    t.link = None
    return t.data

Ցուցակի վերջից հանգույց հեռացնելու համար էլի պետք է մի քանի գործողություն ավել անել։ Նախ, եթե ցուցակը դատարկ է, ապա ոչինչ անել պետք չէ։ Եթե ցուցակը պարունակում է միայն մեկ տարր, ապա head ցուցիչին վերագրվում է None և վերադարձվում է այդ միակ հանգույցի պարունակությունը։ Եթե ցուցակում մեկից ավելի հանգույցներ են, ապա որևէ ժամանակավոր ցուցիչով որոնվում է նախավերջին հանգույցը։ Այդ նախավերջին հանգույցի link ցուցիչին վերագրվում է None, և վերադարձվում է վերջին հանգույցի պարունակությունը։

  def RemoveBack(self):
    if self.head == None:
      return None
    if self.head.link == None:
      val = self.head.data
      self.head = None
      return val
    else:
      tail = self.head
      while tail.link.link != None:
        tail = tail.link
      val = tail.link.data
      tail.link = None
      return val

Ցունցակում տրված արժեքով հանգույցը որոնելու համար Search մեթոդում մի ժամանակավոր ցուցիչ նախ կապվում է ցուցակի առաջին հանգույցին, ապա ցիկլով այն տեղաշարժվում է դեպի ցուցակի վերջը։ Ցիկլն ավարտվում է, երբ կա՛մ ժամանակավոր ցուցիչը հասել է ցուցակի վերջին, կա՛մ ցույց է տալիս մի հանգույցի, որի data դաշտը պարունակում է որոնվող արժեքը։

  def Search(self, val):
    temp = self.head
    while temp != None and temp.data != val:
      temp = temp.link
    return temp

Ցուցակում տարրեր կարելի է ավելացնոլ ոչ միայն սկզբից կամ վերջից, այլ նաև որևէ հանգույցից առաջ կամ հետո։ InsertAfter մեթոդը ստանում է մի արժեք և ցուցակի մի որևէ հանգույց, ապա տրված արժեքով մի նոր հանգույց է ավելացնում ցուցակի տրված հանգույցից հետո։

  def InsertAfter(self, val, node):
    nd = Node(val)
    nd.link = node.link
    node.link = nd

Իսկ InsertBefore մեթոդը տրված արժեքով նոր հանգույց է ավելացնում ցուցակի տրվախ հանգույցից առաջ։

  def InsertBefore(self, val, node):
    self.InsertAfter(val, node)
    node.link.data, node.data = node.data, node.link.data

Համապատասխանաբար RemoveAfter և RemoveBefore մեթոդները հեռացնում են ցուցակի տրվաց հանգույցին հաջորդող ու նախորդող հանգույցները՝ վերադարձնելով հեռացված հանգույցի պարունակությունը։

  def RemoveAfter(self, node):
    if node.link == None:
      return None
    t = node.link
    node.link = t.link
    t.link = None
    return t.data

  def RemoveBefore(self, node):
    if self.head == node:
      return None
    temp = self.head
    while temp.link != node:
      temp = temp.link
    val = temp.data
    temp.data = node.data
    self.RemoveAfter(temp)
    return val

Եվ վերջապես, մի հետաքրքիր գործողություն ևս։ Reverse մեթոդը շրջում է կապակցված ցուցակը։ Ահա այդ պարզ ալգորիթմը։

  def Reverse(self):
    a = self.head
    b = None
    while a != None:
      c = a.link
      a.link = b
      b = a
      a = c
    self.head = b