Home c++ Single-connected list, removal of item, C++

Single-connected list, removal of item, C++

Author

Date

Category

Good afternoon. There is this item removal code from the list

void del (int n) // n - position of the removed item
{
  // Mass - Objects that are stored in the list
  Mass * Temp = Head, * Helping = Temp;
  if ((temp! = NULL) & amp; & amp; (n & lt; = size) & amp; & amp; (n & gt; = 0)) // If this number lies something and this item inside the list
  {
    for (int i = 0; i & lt; n; i ++)
    {
      Helping = Temp; // previous TEMP value
      TEMP = TEMP- & GT; Next;
    }
    if (temp == head) // if an item that needs to be deleted first
    {
      Helping = Temp;
      TEMP = TEMP- & GT; Next;
      Head = Temp;
      COUT & LT; & LT; "Deleted element:" & lt; & lt; * Helping;
      FREE (Helping);
      Size--; // Reduce the size of the list
      Return;
    }
    else // Otherwise, if he is in the middle or end
    {
      // 0 1 2 3 4
      // Entered, for example, 2. Ie Helping = 1, temp = 2;
      FREE (TEMP);
      Size--;
      // 0 1 .. 3 4
      Helping- & gt; Next = Helping- & gt; next- & gt; next;
      // i.e. Now 1 indicates not 2, but by 3.
    }
  }

The beginning is worked out well, i.e. He removes the first element, but for some reason other elements does not work. I think about this for the second day, the head is boiling.
I imagine the algorithm so:

  1. Remove the
  2. element

  3. shift the remaining list items (left to remote or right?)

or even do so
1. Remove the

element

  1. We go through the entire list until we stumble upon a remote (null)
  2. throw a link from the item before remote to the element after the remote (bypassing the remote item itself)
  3. repeat item clause 3 will not be zero items. Considering that we do not consider the end of the list.

Thank you so much for your help! He opened a lot of new things for himself in working with pointers. Special thanks

@michaelpak for the direction of directions to which it is worth digging and specifying a specific error and a detailed explanation,

@mike for the ensuing for the use of an irrational algorithm

@alexolut for suggesting the difference in between Ned Delete and Malloc Free

@vlad from Moscow for a detailed solution of the problem and a cool idea of ​​using an unsigned type variable (and did in the end).

I am very grateful to you, thank you very much!


Answer 1, Authority 100%

In principle, you are written all correctly except for two moments.

first is the number of the removed item cannot be equal to Size . Size Always per unit more than the number of the last existing item, since the numbering of elements you begin with 0.

so instead of the condition

if ((temp! = null) & amp; & amp; (n & lt; = size) & amp; & amp; N & GT; = 0)) // If something is lies with this item inside the list

You should write

if ((temp! = null) & amp; & amp; (n & lt; size) & amp; & amp; (n & gt; = 0)) // If something is lies with this item inside the list
             ^^^^^^^^

You would facilitate your life if the variable size had an unsigned whole type. In this case, it would not be necessary to verify that n & gt; = 0 . You could Size declare as having a type unsigned int or, as usual, size_t .

Second – you are trying to contact the already remote element in the offer

helping- & gt; next = helping- & gt; next- & gt; next;

followed first to set the value of the Next field, but only then delete item.

Taking into account the said function may look like this

void del (int n) // n - position of the removed item
{
  if ((HEAD! = NULL) & amp; & amp; (n & lt; size) & amp; & amp; (n & gt; = 0)) // If this number lies something and this item inside the list
  {
    // Mass - Objects that are stored in the list
    Mass * Temp = Head, * Helping = Head;
    for (int i = 0; i & lt; n; i ++)
    {
      Helping = Temp; // previous TEMP value
      TEMP = TEMP- & GT; Next;
    }
    if (temp == head) // if an item that needs to be deleted first
    {
      Head = Temp- & gt; next;
    }
    ELSE.
    {
      Helping- & gt; Next = Temp- & gt; next;
    }
    COUT & LT; & LT; "Deleted element:" & lt; & lt; * TEMP;
    FREE (TEMP);
    Size--; // Reduce the size of the list
  }
}

Answer 2, Authority 700%

Lists are worse than arrays by the fact that in the lists you cannot contact the item immediately: for this you need to walk through the previous elements. Therefore, the removal process is as follows:

  1. reach the element, link next which indicates the removed item;
  2. Assign the link next Released element link of the previous item;
  3. Remove the item;
  4. profit!

Thus, from such a picture:

+ ------ + + ------ + + ------ +
      | Data | | Data | | Data |
  \ / / \ - & gt; + ------ + + ------ + + ------ +
      | | --- & gt; | | --- & gt; | 0 |
      + ------ + + ------ + + ------ +

It turns out this:

+ ------ + + ------ + + ------ +
      | Data | | Removen | | Data |
  \ / / \ - & gt; + ------ + + ------ + + ------ +
      | | | 0 | .- & gt; | 0 |
      + ------ + + ------ + | + ------ +.
         \ ______________ |

You have the problem is that you first remove the item, and then try to find a link to the next, that is, helping- & gt; Next- & gt; Next After removal no longer indicates 3 – Element. Try first to work with pointers, and only then delete item.


Answer 3, Authority 500%

2 times run around the chain – this is a bust. Better, moving along a chain, remember the previous element.

mass * temp = head, * prev = null;
int i = 0;
While (Temp & amp; & amp; i & lt; n)
 {
 I ++;
 PREV = TEMP; // remember the previous one in the chain
 TEMP = TEMP- & GT; Next;
 }
if (! temp) // item not found
 {
 Return;
 }
if (Head == TEMP)
 {
 Head = Temp- & gt; next;
 } ELSE.
 {
 If (prev) Prev- & gt; Next = Temp- & gt; Next;
 }
COUT & LT; & LT; "Deleted element:" & lt; & lt; * TEMP;
Size--;
FREE (TEMP);

Programmers, Start Your Engines!

Why spend time searching for the correct question and then entering your answer when you can find it in a second? That's what CompuTicket is all about! Here you'll find thousands of questions and answers from hundreds of computer languages.

Recent questions