Thursday, December 27, 2012

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

No comments:

Post a Comment