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