የጭንቅላት ጠቋሚ ያለ ኖድ ከተገናኘው ዝርዝር ይሰርዙ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ GE የጤና MAQ
የተገናኘ-ዝርዝር ቴክኒካዊ አጻጻፍ

የችግሩ መግለጫ

ችግሩ “ጭንቅላት ከሌለው ጠቋሚ ያለ ኖድ ከተያያዘው ዝርዝር ይሰርዙ” የሚለው ችግር ከአንዳንድ አንጓዎች ጋር የተገናኘ ዝርዝር እንዳለዎት ይገልጻል ፡፡ አሁን መስቀለኛ መንገድ መሰረዝ ይፈልጋሉ ግን የወላጅ መስቀለኛ መንገድ አድራሻ የለዎትም ፡፡ ስለዚህ ይህንን መስቀለኛ መንገድ ይሰርዙ ፡፡

ለምሳሌ

የጭንቅላት ጠቋሚ ያለ ኖድ ከተገናኘው ዝርዝር ይሰርዙ

2->3->4->5->6->7
Node to be deleted: 4
2->3->5->6->7

ማብራሪያ-መስቀለኛውን ከእሴት ጋር ለመሰረዝ ስለፈለግን 4. ከተገናኘው ዝርዝር ውስጥ አስወግደነው በውጤቱ ውስጥ ከተጠቀሰው ዝርዝር ጋር ቀርተናል ፡፡

ያለ ራስ ጠቋሚ መስቀለኛ መንገድን ለመሰረዝ አቀራረብ

የተገናኘ ዝርዝር በአንድ ድርድር ላይ ትልቅ ጥቅም ያለው መስመራዊ የውሂብ መዋቅር ሲሆን በመጠን ሊለያይ ይችላል ፡፡ በተገናኘ ዝርዝር ውስጥ አንድ አካል ማከል ከፈለጉ በ O (1) ጊዜ ውስጥ ማከል ይችላሉ። በመጀመሪያ ኤለመንቱን እየገቡ መሆኑን ከግምት በማስገባት ፡፡ ነገር ግን በተለመደው ድርድር ውስጥ ተመሳሳይ ነገር ማድረግ ቢኖርብዎት። ይህንን ለማድረግ O (N) ጊዜ ያስከፍልዎታል። ስለሆነም በእውነተኛ ዓለም መተግበሪያዎች ውስጥ የተገናኘ ዝርዝርን በአንድ ድርድር ላይ መጠቀሙ ጥሩ ነው። እና የተገናኘው ዝርዝር መረጃውን እንደ ተጣባቂ ቁራጭ ስለማያስቀምጥ እነዚህን ሁሉ ያገኛል ፡፡ እያንዳንዱን ንጥረ ነገር በተወሰነ የዘፈቀደ ቦታ ላይ ያከማቻል። ግን ከዚያ እንዴት ስርዓትን ይጠብቃል? የዚህ ጥያቄ መልስ ፣ የተገናኘው ዝርዝር የጠቋሚውን አጠቃቀም ይወስዳል ፡፡ እያንዳንዱ መስቀለኛ መንገድ በተገናኘው ዝርዝር ውስጥ ወደ ሌላ መስቀለኛ መንገድ ይጠቁማል እናም በዚህ መንገድ ብዙ ስሌቶችን የሚፈልግ አንድ ነጠላ ክራንች መለወጥ የለብንም ፡፡

የጭንቅላት ጠቋሚ ከተሰጠ

አሁን ችግሩ ይጠይቀናል መስቀለኛ መንገድ ሰርዝ. በአጠቃላይ የመስቀለኛ ክፍል አድራሻ ተሰጥቶናል እና በተገናኘው ዝርዝር ውስጥ የሚቀጥለውን መስቀለኛ ክፍል መሰረዝ ይጠበቅብናል ፡፡ ግን እዚህ እኛ አድራሻችን የተሰጠ መስቀለኛ መሰረዝ ይጠበቅብናል ፡፡ ይህንን ችግር ለመፍታት አንዱ መንገድ በመጀመሪያ የተገናኘውን ዝርዝር በሙሉ መሻገር ነው ፡፡ ከዚያ የእያንዳንዱን መስቀለኛ ክፍል ወላጅ ያከማቹ እና እንደ ግብዓት በሚሰጥ መስቀለኛ ክፍል ላይ ሲሆኑ ቀለበቱን ይሰብሩ ፡፡ በመጨረሻ በዚህ መንገድ የመስቀያው ወላጅ አለን ፡፡ ስለዚህ አሁን ችግሩ የወላጅ አድራሻ በተሰጠው በተገናኘው ዝርዝር ውስጥ በቀላሉ ወደ አንድ መስቀለኛ መሰረዝ ተለውጧል ፡፡ ግን ይህንን ማድረጉ የኦ (ኤን) ክወናዎችን ያስከፍለናል ፡፡ ግን ይህ መንገድ የጭንቅላት ጠቋሚ ሲኖርዎት ብቻ ሊያገለግል ይችላል ፡፡

መፍትሔ

ለችግሩ አቀራረብ “አንድ መስቀለኛ መንገድ ከተያያዘው ዝርዝር ያለ ራስ ጠቋሚ ይሰርዙ” የሚጠፋው የመስቀለኛ ክፍል እና የቀጣዩ መስቀለኛ መንገድ መረጃን ለመቀያየር ይሆናል ፡፡ በተገናኘው ዝርዝር ውስጥ ያለው እያንዳንዱ መስቀለኛ መንገድ የትኛው መስቀለኛ መንገድ ቀጣዩ ነው ፡፡ ስለዚህ ይህ ክዋኔ O (1) የጊዜ ውስብስብነት ብቻ አለው ፡፡ አሁን ውሂቡ ሲቀያየር. አሁንም ችግሩ የወላጅ አድራሻ ወደ ተሰጠው መስቀለኛ ክፍል መሰረዝ ቀይረናል ፡፡ ስለዚህ አሁን ችግሩን መፍታት ለእኛ የቀለለን ነው ፡፡ ግን የመጨረሻውን መስቀለኛ መንገድ መሰረዝ ሲኖርብን አንድ የጠርዝ ጉዳይ አለ ግን ያንን መሰረዝ አንችልም ፡፡ ምክንያቱም ቀጣዩ መስቀለኛ መንገድ የለም።

ኮድ

ያለ ራስ ጠቋሚ መስቀለኛ መንገድን ለመሰረዝ የ C ++ ኮድ

#include <bits/stdc++.h>
using namespace std;

struct node{
  int data;
  node* next;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

void deletedNode(node* &head, node* toBeDeleted){
  if(toBeDeleted == NULL)
    return;
  else{
    if(toBeDeleted->next == NULL){
      cout<<"Last node can't be freed";
    }
    // store or swap but ( the data of current node will be deleted)
    toBeDeleted->data = toBeDeleted->next->data;
    toBeDeleted->next = toBeDeleted->next->next;
  }
}

int main(){
  // create a linked list
  node* head = new node();
  head = create(2);
  head->next = create(3);
  node* toBeDeleted = create(4);
  head->next->next = toBeDeleted;
  head->next->next->next = create(5);
  head->next->next->next->next = create(6);
  head->next->next->next->next->next = create(7);

  cout<<"Old Linked List: ";
  node* tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
  deletedNode(head, toBeDeleted);

  cout<<endl<<"New Linked List: ";
  tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
}
Old Linked List: 2 3 4 5 6 7
New Linked List: 2 3 5 6 7

ያለ ራስ ጠቋሚ መስቀለኛ መንገድን ለመሰረዝ የጃቫ ኮድ

import java.util.*;
class node{
  int data;
  node next;
}
 
class Main{
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.next = null;
    return tmp;
  }
 
  static node deletedNode(node head, node toBeDeleted){
    if(toBeDeleted == null)
      return null;
    else{
      if(toBeDeleted.next == null){
        System.out.print("Last node can't be freed");
        return null;
      }
      // store or swap but ( the data of current node will be deleted)
      toBeDeleted.data = toBeDeleted.next.data;
      toBeDeleted.next = toBeDeleted.next.next;
      return head;
    }
  }
 
  public static void main(String[] args){
    // create a linked list
    node head = new node();
    head = create(2);
    head.next = create(3);
    node toBeDeleted = create(4);
    head.next.next = toBeDeleted;
    head.next.next.next = create(5);
    head.next.next.next.next = create(6);
    head.next.next.next.next.next = create(7);
 
    System.out.print("Old Linked List: ");
    node tmp = head;
    while(tmp != null){
      System.out.print(tmp.data+" ");
      tmp = tmp.next;
    }
    head = deletedNode(head, toBeDeleted);
 
    System.out.print("\n"+"New Linked List: ");
    tmp = head;
    while(tmp!=null){
      System.out.print(tmp.data+" ");
      tmp = tmp.next;
    }
  }
}
Old Linked List: 2 3 4 5 6 7 
New Linked List: 2 3 5 6 7

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (1) ፣ ምክንያቱም መለዋወጥ በቋሚ ጊዜ ሊወርድ ይችላል። እና ከዚያ እኛ እንደገና የቋሚ ጊዜ አሠራር የሆነውን አንዳንድ ጠቋሚዎችን እንለውጣለን።

የቦታ ውስብስብነት

ኦ (1) ፣ ምክንያቱም የተጠቀምናቸው ተለዋዋጮች በተገናኘው ዝርዝር ውስጥ ባሉ የአንጓዎች ብዛት ላይ የተመኩ አይደሉም ፡፡ ስለዚህ የቦታ ውስብስብነትም እንዲሁ ቋሚ ነው።