主页 / 问题 / 1258543
Accepted
artem_tmm
Asked:2022-03-20 23:27:37 +0800 CST2022-03-20 23:27:37 +0800 CST

从单链表中删除元素

  • 772

任务：只保留列表中最后出现的相同元素。

struct List // Создание нового типа данных
{
    int value; // информационная часть
    List* next; // служебная часть
    List(int val = 0, List* p = NULL) // конструктор
    {
        value = val;
        next = p;
    }
};


List* head = NULL;


// Включение элемента в конец списка
List* Add_last(int n, List* head)
{
    List* q = new List(n), *p = head;
    if (head == NULL) return q;
    while (p->next != NULL)
        p = p->next;
    p->next = q;
    return head;
}


// Печать содержимого списка
void Print_list(List* head)
{
    List* p = head;
    puts("\n PRINT LIST");
    if (p == NULL) puts("Список пуст!");
    else
        while (p != NULL)
        {
            printf("%d ", p->value);
            p = p->next;
        }
}


List* remove(List * head) 
{
    List * j, *i = head , *t;
    int count = 0;

    while (i != NULL) // внешний цикл, обход списка
    { 
        for (j = i; j != NULL; j = j->next) // считаю количество одинаковых элементов
            if (j->value == i->value) count++; 

        j = i; // возвращаем указатель в начало


       while (count > 1)
        {
            if (i->value == j->value)
            {
                t = j;
                j = j->next;
                delete t;

                count--;
            }
            else j = j->next;
        }

        i = i->next;

        count = 0;
    }

    return head;
}


int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);

    List* head = NULL;
 
    head = Add_last(1, head);
    head = Add_last(2, head);
    head = Add_last(1, head);
    head = Add_last(1, head);
    head = Add_last(4, head);

    Print_list(head);

    head = remove(head);

    printf("");

    Print_list(head);

    return 0;
}

程序在删除功能运行后停止运行

PS 列表是单链接的，所以我只能往一个方向移动。

c++

1 个回答

  1. Best Answer

    从单链表中删除元素的算法的复杂性在于，必须将指针更改为下一个元素，即要删除的元素之前的元素。如果我们删除列表中的第一个，我们需要更改指向列表的指针。

    我提出了一种不同的算法来解决您的问题。

    首先，让我们创建一个临时的翻转列表，通过将一个元素（仅更改指针，不删除旧指针并创建新指针）从一个列表移动到另一个列表来构建。因此，每个元素的最后一次重复将成为新列表中的第一个。

    此外，我们将从临时列表移动到结果列表中，只有那些重复项不在结果列表中的元素。

    我们还将构建这个结果列表倒置，即 我们会得到想要的结果，即 仅包含最后出现的相同元素的初始列表。

    List *remove (List *head)
{
  List *tmp = 0, *t;

  while ((t = head)) { // reverse the list
    head = t->next;

    t->next = tmp;
    tmp = t;
  }

  while ((t = tmp)) { // build result as reverse list
    tmp = t->next;

    // search t in result
    int found = 0;
    for (List *p = head; p; p = p->next)
      if (t->value == p->value) {
        found = 1;
        break;
      }
    if (found)
      delete t;
    else {
      t->next = head;
      head = t;
    }
  }
    
  return head;
}

    有什么不清楚的，在评论中提问。

    • 1

相关问题