Удаление повторяющихся элементов из списка

@Skaarj · Регистрация: 28.06.2013

Студворк — интернет-сервис помощи студентам

Всем привет! Прошу помощи, надо написать функцию удаления всех повторяющихся элементов из списка. Например надо получить из a b g c d a b c e f -> g d e f.
Я попытался сначала сделать эту функцию из функции которая удаляет только повторяющиеся, то есть из a b g c d a b c e f -> a b g c d e f, но не получилось и решил сделать через ещё один цикл..показалось что так проще. Cажусь на p-ый элемент и сравниваю с t-ым, пока не находится пара тождественно равных, затем беру значение этого p и присваиваю к некоторой переменной d. И затем делаю ещё один цикл который пробегает от головы до конца сравнивая все элементы с d и удаляя те, что равны d.

Проблема только в том что при удаление больше 4 элементов программа где то подвисает в цикле, не могу понять в чём ошибка и почему только 4 удаления. И ещё списки вида a b ... b обрабатывает в тот же список только первый элемент заменяет 0, но тут я наверное разберусь. Не знаю правильный ли я путь выбрал.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
list *Del_Same(list *head, int &d)
{
     list *p=head, *t, *q, *u;
     
     while(p!=NULL)
     {            t=p;
                  while(t->next!=NULL)
                  {
                              if(p->value==t->next->value)
                              {
                              d=p->value;
                              u=head;
                                      if(head==NULL) { puts("list empty"); return NULL;}
                                      if(head->value==d){head=head->next; delete u; return head;}
                                      
                                      while(u->next!=NULL)
                                      {
                                                          if(u->next->value==d)
                                                          {
                                                          q=u->next;
                                                          u->next=u->next->next;
                                                          delete q;
                                                          }
                                      else u=u->next;                  
                                      }
                               } 
                               else t=t->next;
                  } 
     p=p->next; 
     }
     return head;
}

@BumerangSP · 29.06.2013, 00:38

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
pList* deleteDublicate(pList *&first)
    {
        pList *bufI = 0;
        bool firstWasChanged = false;
        for (pList *i = first; i; i = i->next)
        {
            if (firstWasChanged)
            {
                i = first;
                firstWasChanged = false;
            }
            bool isDublicate = false;
            pList *bufJ = first;
            for (pList *j = first; j; j = j->next)
            {
                if (i->data == j->data && i != j)
                {
                    bufJ->next = j->next;
                    delete j;
                    j = bufJ;
                    isDublicate = true;
                }
                bufJ = j;
            }
            if (isDublicate)
            {
                if (i == first)
                {
                    bufI = i->next;
                    delete i;
                    i = bufI;
                    first = i;
                    if (!i) return 0; 
                    firstWasChanged = true;
                }
                else
                {
                    bufI->next = i->next;
                    delete i;
                    i = bufI;
                }
            }
            bufI = i;
        }
        return first;
    }

Вот пример, на котором тестил:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
 
struct pList
{
    char data;
    pList *next;
};
 
class List
{
    pList *first;
public:
    List(): first() {}
    void add(char x)
    {
        if(!first)
        {
            first = new pList;
            first->data = x;
            first->next = 0;
        }
        else
        {
            pList *curr = new pList;
            curr->data = x;
            curr->next = first;
            first = curr;
        }
    }
    void show()
    {
        pList *curr = first;
        while (curr)
        {
            std::cout << curr->data << ' ';
            curr = curr->next;
        }
        std::cout << '\n';
    }
    void deleteDublicate()
    {
        pList *bufI = 0;
        bool firstWasChanged = false;
        for (pList *i = first; i; i = i->next)
        {
            if (firstWasChanged)
            {
                i = first;
                firstWasChanged = false;
            }
            bool isDublicate = false;
            pList *bufJ = first;
            for (pList *j = first; j; j = j->next)
            {
                if (i->data == j->data && i != j)
                {
                    bufJ->next = j->next;
                    delete j;
                    j = bufJ;
                    isDublicate = true;
                }
                bufJ = j;
            }
            if (isDublicate)
            {
                if (i == first)
                {
                    bufI = i->next;
                    delete i;
                    i = bufI;
                    first = i;
                    if (!i) return; 
                    firstWasChanged = true;
                }
                else
                {
                    bufI->next = i->next;
                    delete i;
                    i = bufI;
                }
            }
            bufI = i;
        }
    }
    ~List()
    {
        pList *curr = first;
        while (first)
        {
            curr = first->next;
            delete first;
            first = curr;
        }
        first = 0;
    }
};
 
int main()
 
{
    List list;
    list.add('c');
    list.add('B');
    list.add('A');
    list.add('a');
    list.add('a');
    list.add('c');
    list.deleteDublicate();
    list.show();
}

@Skaarj · 29.06.2013, 18:41 **[ТС]**

2BumerangSP, спасибо! Идея вроде как понятна, но не думаю что у меня получится реализовать

И у меня компилятор ругается на эту строчку.

C++
1
if (!i) return 0;

Да и хочется узнать, что не так у меня. Скидываю целиком всю программу. Работает только до 4х удалений..может быть дело в компиляторе?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <conio.h> 
 
struct list
{int value;
list* next;
list* prev;
list* number;
};
 
void Print_list (list*h)
{
    puts("\nList now:");
    while(h!=NULL)
    {
        printf("%d ",h->value);
        h=h->next;
    }
}
 
 
list *Ins_First(list*first, int n)
{
 
    list*q=new list;
    q->value=n;
    if(first==NULL)     q->next=NULL;
    q->next=first;
    return q;
};
 
list*Creat_List ()
{
    list*head=NULL;
    int num;
    puts ("Enter nambers (end = 0):");
    while (1)
    {
        scanf("%d",&num);
        if (num==0)return head;
        head=Ins_First(head,num);
    }
}
 
list *Del_Same(list *head, int &d)
{
     if(head==NULL) { puts("list empty"); return NULL;}     
     list *p=head, *t, *q, *u;
     int i=0;
     while(p!=NULL)
     {            t=p;
                  while(t->next!=NULL)
                  {              
                              if(p->value==t->next->value)
                              {
                              d=t->next->value;
                              u=head;
                              if(u->value==d){u=head; head=head->next; delete u;}  
                                      while(u->next!=NULL)
                                      {
                                                          if(u->next->value==d)
                                                          {
                                                          q=u->next;
                                                          u->next=u->next->next;
                                                          delete q;
                                                          }
                                      else u=u->next;    
                                      }    
                              } 
                              else t=t->next;
                  }
     p=p->next; 
     }
     return head;
}
 
int main()
{
    int d;
    list*head;
    puts ("Rabota so spiskom");
    head=Creat_List();
    Print_list(head);
    Del_Same (head, d);
    Print_list(head);
 
    getch();
 
}

@BumerangSP · 29.06.2013, 21:17

Ну, можно тогда с примера: дано 1231.
Этот кусок Вашего кода вначале удаляет последнюю единицу.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
if(p->value == t->next->value)
            {
                d=t->next->value; // запоминаем указатель на эту 1
                u=head; // запоминаем указатель на голову, т.е. на ту же 1
                if(u->value==d) // странное сравнение, но пока совпадает
                { 
                    u=head;  // зачем-то опять запоминаем указатель на 
                                                     // голову, хотя сделали это выше
                    head=head->next; // переходим на след., то есть в данном примере на 3
                    delete u; // удаляем узел, содержащий единицу
                }  
                while(u->next!=NULL) // u теперь ни на что не указывает <- ошибка
                {
                    if(u->next->value==d) // error
                    {
                        q=u->next; // ит.д.
                        u->next=u->next->next;
                        delete q;
                    }
                    else 
                        u=u->next;    
                }    
            }

@Skaarj · 29.06.2013, 23:47 **[ТС]**

Согласен, что странное сравнение - хотел сделать условие удаления элемента, который находится в начале списка(в голове). Я думаю пока можно опустить это условие, оно не критично при удаление элементов из середины. А вот в середине при удаление больше 4 элементов программа виснет В списке 5 2 1 4 2 1 3 2 1 не виснет после 6 удалений, а в 5 2 1 4 2 1 2 1 виснет.

вот кусок кода без проверки элемента в голове списка.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
     while(p!=NULL)
     {            t=p;
                  while(t->next!=NULL)
                  {              
                              if(p->value==t->next->value)
                              {
                              d=t->next->value;
                              u=head;
                                      while(u->next!=NULL)
                                      {
                                                          if(u->next->value==d)
                                                          {
                                                          q=u->next;
                                                          u->next=u->next->next;
                                                          delete q;
                                                          }
                                      else u=u->next;    
                                      }    
                              } 
                              else t=t->next;
                  }
     p=p->next; 
     }

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .