मैं एक लिंक की गई सूची में एक नोड को हटाने के लिए एक फ़ंक्शन लिखने की कोशिश कर रहा हूं, सिर को एक डबल पॉइंटर और नोड को हटाने के लिए एक पॉइंटर दिया गया है। (हटाए जाने वाला नोड टेल नोड नहीं होगा) मैंने यही कोशिश की है: -

public: 
    int value; 
    Node* next; 
};
 
/* 
headPtr is a reference to the head node(i.e. pointer to pointer) and
deleteNodePtr is the node which is to be deleted. You can see the Node definition above.
It is guaranteed that deleteNodePtr will not point to the last element.
*/ 
void deleteNode(Node** headPtr, Node* deleteNodePtr) {

     
    Node* current;  
    current=*headPtr;
    if (*headPtr==deleteNodePtr){
        *headPtr=deleteNodePtr->next;
        //delete current;
        return;
        
    }
    else {
        Node* prev = current;
        while(current->next!=deleteNodePtr){
            prev = current;
            current=current->next;
        }
        prev->next =current->next;
        //delete current;
        return;
    }
    return;

}
0
aryan kolapkar 18 फरवरी 2021, 18:52

2 जवाब

सबसे बढ़िया उत्तर

मैं कई चीजें देख सकता हूं:

1 - आपकी स्थिति में आप जाँच नहीं कर रहे हैं कि करंट मान्य है:

while(current->next!=deleteNodePtr){
            prev = current;
            current=current->next;
        }

2- शायद अब आपके साथ क्या हो रहा है: deleteNodePtr सूची में दूसरे तत्व की ओर इशारा करता है, इसलिए आप कभी भी while लूप में प्रवेश नहीं करते हैं जिसका अर्थ है prev == current जिसका अर्थ है कि आप current->next = current->next असाइन कर रहे हैं।

इसके लिए एक समाधान होगा:

void deleteNode(Node** headPtr, Node* deleteNodePtr) {


    Node* current;
    current = *headPtr;
    if (current == deleteNodePtr) {
        current = deleteNodePtr->next;
        delete current;
    }
    else {
        Node* prev = current;
        current = current->next;
        while (current!= nullptr && current != deleteNodePtr) {
            prev = current;
            current = current->next;
        }

        if(current!=nullptr)
        {
            prev->next = current->next;
            delete current;
        }
    }
    return;

}

3- आप कभी भी जांच नहीं करते हैं कि क्या headPtr मान्य है, यह नहीं हो सकता।

4- यह एक कोड समस्या के बजाय स्टाइलिश चीज़ में एक सुझाव है, इसलिए यदि आप इस दृष्टिकोण को साझा नहीं करते हैं, तो आप इसे स्वतंत्र रूप से अनदेखा कर सकते हैं। शुरुआत में आप करंट को *headPtr असाइन करते हैं, लेकिन आगे के उपयोग के लिए करंट का उपयोग करने के बजाय, आप headPtr का उपयोग करते हैं। इसके बजाय यह बहुत स्पष्ट होगा, यदि आप हमेशा करंट का उपयोग करते हैं:

मूल:

 Node* current;  
    current=*headPtr;
    if (*headPtr==deleteNodePtr){
        *headPtr=deleteNodePtr->next;
        //delete current;
        return;
        
    }

सुझाव:

 Node* current;  
    current=*headPtr;
    if (current==deleteNodePtr){
        current=deleteNodePtr->next;
        //delete current;
        return;    
    }
0
Aleix Rius 18 फरवरी 2021, 19:19

यह सी ++ में लिखी गई सी-स्टाइल लिंक्ड सूची होने के लिए पहली बार ब्लश पर दिखाई देता है। निश्चित रूप से कहना मुश्किल है क्योंकि हमारे पास आपके कोड की एक बड़ी तस्वीर नहीं है। एक C++ लिंक्ड सूची कम से कम इन कार्यों को एक वर्ग में रखेगी, न कि वैश्विक Node.

नोड वह है जिसे कार्यान्वयन विवरण कहा जाता है। यह हमें सूची लिखने में मदद करता है, लेकिन सूची वर्ग के उपयोगकर्ताओं को अपने स्वयं के नोड्स घोषित करने में सक्षम नहीं होना चाहिए, और न ही उन्हें पता होना चाहिए कि नोड्स मौजूद हैं। उम्मीद है कि आपकी कक्षा का उपयोग करने वाले लोग इस डिलीट फंक्शन को स्पष्ट रूप से नहीं बुला रहे हैं।

आपकी सूची वर्ग के उपयोगकर्ता उन्हें इटरेटर उपलब्ध कराना पसंद कर सकते हैं/चाहिए (निर्भर करता है)। यदि आपके कंटेनरों के लिए इटरेटर लिखने वाले कुछ भी उन्हें लूप के लिए रेंज-आधारित के साथ उपयोग करने की अनुमति देंगे। चूंकि आपकी लिंक की गई सूची एकल रूप से जुड़ी हुई प्रतीत होती है, इसलिए आपके पुनरावर्तक केवल आगे बढ़ सकते हैं। मैंने अपनी कक्षा को एक पुनरावर्तक के साथ भी लिखा था क्योंकि मुझे लगता है कि यह ज्यादातर मामलों में होमवर्क सबमिशन कॉपी/पेस्ट करने से रोकने में मदद करेगा।

अब आपके फंक्शन पर। मेरी टिप्पणी के अनुसार, सिर को डबल पॉइंटर के रूप में पास करने का कोई मतलब नहीं है। एक बार आप इसे डबल पॉइंटर के रूप में उपयोग नहीं करते हैं; आप हमेशा इसे डी-रेफरेंस करते हैं। तो बीच के आदमी को काट दें और इसे गेट-गो से एक नोड पॉइंटर पास करें।

एक ऐसा मामला है जिसके न होने की गारंटी है, और वह यह है कि deleteNodePtr कभी भी अंतिम नोड नहीं होगा। यह बुरा लगता है। लोग अंतिम नोड को हटाना चाह सकते हैं, लेकिन उन्हें अनुमति है और कोई औचित्य नहीं दिया गया है।

खाली सूची पर हटाने के प्रयास को पकड़ने के लिए कोई कोड नहीं है।

आपका विशिष्ट मुद्दा यहाँ झूठ लगता है:

while(current->next!=deleteNodePtr){
    prev = current;
    current=current->next;
}

आप लूप से बाहर तब निकलते हैं जब current->next हटाए जाने वाला नोड है, न कि current। आप अंत में गलत नोड (current, जो deleteNodePtr से पहले 1 है) को हटा देते हैं, और इससे समस्याएँ उत्पन्न होने की संभावना है। उदाहरण के लिए, यदि दूसरा नोड हटाया जाना है, तो आप अपना सिर हटा देते हैं, और इससे सामान टूट जाता है। मुझे लगता है कि ->next को आपकी बूलियन स्थिति से हटाने से समस्या ठीक हो जाएगी। मैं आपका अधिक कोड देखे बिना एक गहरा समाधान प्रदान नहीं कर सकता।

=== वैकल्पिक पठन ===
सी ++ वर्ग के रूप में लिखी गई एक बेहद अलग-अलग लिंक की गई सूची यहां दी गई है। आप इस कोड को यहां चला सकते हैं: https://godbolt.org/z/7jnvje
या इसे स्वयं संकलित करें।

#include <iostream>

// A simple linked list for integers
class List {
public:
  List() = default;
  ~List();
  // List(const List& other);  // Copy ctor needed for Rule of 5
  // List(List&& other) noexcept;  // Move ctor needed for Rule of 5
  void push_back(int val);

  class iterator;

  iterator begin();
  iterator end();

  iterator find(int val);
  void erase(iterator it);

  void clear();
  // friend void swap(List& lhs, List& rhs);  // Not Rule of 5; aids Rule of 5
  // List& operator=(List other);  // Assignment operator needed for Rule of 5
  /*
   * Quick note on Rule of 5 functions.
   * If your class deals with heap-allocated resources, certain functions become
   * required. The only one I included was the destructor. The signature of my
   * assignment operator is different than you might see, but the reason is
   * it's written to take advantage of the copy/swap idiom.
   * https://stackoverflow.com/a/3279550/6119582
   */
private:
  // Data
  struct Node {
    int value = 0;
    Node *next = nullptr;

    Node(int val) : value(val) {}
  };

  Node *m_head = nullptr;
  Node *m_tail = nullptr;

  // Functions
  Node *find_node(int val);
};

class List::iterator {
public:
  iterator(Node *loc) : location(loc) {}
  iterator &operator++();
  int operator*();
  bool operator==(const List::iterator &rhs);
  bool operator!=(const List::iterator &rhs);

private:
  Node *location;
};

// List Implementation
List::~List() { clear(); }

void List::push_back(int val) {
  if (m_tail) {
    m_tail->next = new Node(val);
    m_tail = m_tail->next;
    return;
  }

  m_head = new Node(val);
  m_tail = m_head;

  return;
}

List::iterator List::begin() { return iterator(m_head); }

List::iterator List::end() { return iterator(nullptr); }

List::iterator List::find(int val) { return iterator(find_node(val)); }

void List::erase(iterator it) {
  // Emtpy list or end()
  if (!m_head || it == end())
    return;

  Node *toDelete = find_node(*it);

  // Deleting head
  if (toDelete == m_head) {
    m_head = m_head->next;
    delete toDelete;

    return;
  }

  // Deleting tail
  if (toDelete == m_tail) {
    Node *walker = m_head;
    while (walker->next != m_tail) {
      walker = walker->next;
    }
    m_tail = walker;
    delete m_tail->next;
    m_tail->next = nullptr;

    return;
  }

  // Delete any middle node; by moving value until it is the tail, then
  // deleting the tail
  while (toDelete->next) {
    toDelete->value = toDelete->next->value;
    if (toDelete->next == m_tail) {
      m_tail = toDelete;
    }
    toDelete = toDelete->next;
  }
  delete toDelete;
  m_tail->next = nullptr;
}

void List::clear() {
  while (m_head) {
    Node *tmp = m_head;
    m_head = m_head->next;
    delete tmp;
  }
  m_tail = nullptr;
}

List::Node *List::find_node(int val) {
  if (!m_head) {
    return nullptr;
  }

  Node *walker = m_head;
  while (walker && walker->value != val) {
    walker = walker->next;
  }

  return walker;
}

// List iterator implementation
List::iterator &List::iterator::operator++() {
  location = location->next;

  return *this;
}

int List::iterator::operator*() { return location->value; }

bool List::iterator::operator==(const List::iterator &rhs) {
  return location == rhs.location;
}

bool List::iterator::operator!=(const List::iterator &rhs) {
  return !(*this == rhs);
}

// Free function
// NOTE: Should take list by const reference, but I didn't add the necessary
// code for that. I'm not passing by value because I also left out Rule of 5
// code that is otherwise required.
// NOTE 2: Could also be templatized and made more generic to print any
// container, but that's outside the scope of this answer.
void print(List &list) {
  for (auto i : list) {
    std::cout << i << ' ';
  }
  std::cout << '\n';
}

int main() {
  List list;

  for (int i = 1; i <= 10; ++i) {
    list.push_back(i);
  }

  print(list);
  list.erase(list.find(1));
  print(list);
  list.erase(list.find(10));
  print(list);
  list.erase(list.find(6));
  print(list);

  auto it = list.begin();
  for (int i = 0; i < 3; ++i) {
    ++it;
  }
  list.erase(it);
  print(list);

  list.erase(list.find(25));  // Bogus value; could throw if so desired
  print(list);
}

डबल-लिंक्ड सूची के साथ मिटाना काफी आसान बना दिया गया है, लेकिन हमारे पास एक नहीं है। माई इरेज़ फंक्शन कुछ जाँच करता है और सिर और पूंछ की स्थितियों को व्यक्तिगत रूप से संभालता है। सूची के बीच में किसी भी नोड के लिए, मैं विशेष रूप से उस नोड को हटाने की जहमत नहीं उठाता। इसके बजाय मैं जो करता हूं वह सूची की पूंछ में हटाए जाने वाले मान को घुमाता है, और फिर पूंछ को हटा देता है।

मेरी टिप्पणियां कुछ ऐसी चीजों का संकेत देती हैं जिन्हें छोड़ दिया गया था। मैंने किसी भी फ़ंक्शन को const के रूप में चिह्नित नहीं किया। मेरा पुनरावर्तक ForwardIterator की सभी आवश्यकताओं को पूरा नहीं करता है। लोग शायद मेरे द्वारा छोड़ी गई अन्य चीजें ढूंढ सकते हैं। मेरे पास इसके दो कारण हैं। मुख्य रूप से यह त्वरित और गंदा कोड है, और मैं कॉपी/पेस्ट समाधान का प्रलोभन प्रदान नहीं करना पसंद करता हूं।

यह अच्छा होगा यदि सभी सी ++ प्रशिक्षक वास्तव में सी ++ पढ़ाएंगे, हालांकि। लिंक्ड सूची के इस रूप को अब C++ कक्षा में नहीं पढ़ाया जाना चाहिए।

0
sweenish 18 फरवरी 2021, 21:17