Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Skaarj
2 / 2 / 1
Регистрация: 28.06.2013
Сообщений: 53
#1

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

28.06.2013, 21:53. Просмотров 1712. Ответов 4
Метки нет (Все метки)

Всем привет! Прошу помощи, надо написать функцию удаления всех повторяющихся элементов из списка. Например надо получить из 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.06.2013, 21:53     Удаление повторяющихся элементов из списка
Посмотрите здесь:
Удаление из вектора повторяющихся элементов C++
Удаление повторяющихся элементов в векторе C++
Удаление из массива повторяющихся элементов C++
Удаление повторяющихся элементов в односвязном списке C++
C++ Удаление из строки повторяющихся элементов (через функцию)
C++ Сохранение строки в массив и удаление повторяющихся элементов массива
Сравнение двух векторов <string>, удаление повторяющихся элементов C++
Удаление элементов из односвязного списка списка C++
Двунаправленный список (добавление/удаление элементов в голову, просмотр списка, реализовать дублирование элементов с заданным значением) C++
C++ Удаление элементов из списка
C++ Удаление элементов из списка
Удаление элементов из списка C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
BumerangSP
4285 / 1407 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
29.06.2013, 00:38     Удаление повторяющихся элементов из списка #2
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
2 / 2 / 1
Регистрация: 28.06.2013
Сообщений: 53
29.06.2013, 18:41  [ТС]     Удаление повторяющихся элементов из списка #3
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
4285 / 1407 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
29.06.2013, 21:17     Удаление повторяющихся элементов из списка #4
Ну, можно тогда с примера: дано 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
2 / 2 / 1
Регистрация: 28.06.2013
Сообщений: 53
29.06.2013, 23:47  [ТС]     Удаление повторяющихся элементов из списка #5
Согласен, что странное сравнение - хотел сделать условие удаления элемента, который находится в начале списка(в голове). Я думаю пока можно опустить это условие, оно не критично при удаление элементов из середины. А вот в середине при удаление больше 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; 
     }
Yandex
Объявления
29.06.2013, 23:47     Удаление повторяющихся элементов из списка
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru