Не могу понять почему программа работает некорректно (односвязные списки)

@Sergeev Fedor · Регистрация: 22.01.2016

Построить однонаправленный список чисел. Затем исключить из него все повторы чисел, оставить каждое число в списке в единственном экземпляре. Напечатать список до и после преобразования.

C++

#include <iostream>
#include <conio.h>
using namespace std;
struct List
{
    int k;
    List *next;
};
void Init(List **begin)
{
    *begin = new List;
    int mas[]={1,2,1,3,3,1,4};
    (*begin)->k=mas[0];
    (*begin)->next=NULL;
    List *end = *begin;
    for (int i=1; i<=6; i++)
    {
        end->next = new List;
        end = end->next;
        end->k=mas[i];
        end->next=NULL;
    }
}
void Print(List *b)
{
    List *print = b;
    while(print)
    {
        cout << print->k << " ";
        print = print->next;
    }
    cout << "NULL\n";
}
void Delete(List *begin)
{
    if (begin==NULL)
    {
        return;
    }
    List *t = begin;
    while(t)
    {
        List *t1 = t->next;
        if (t->k==t1->k)
        {
            t->next=t1->next;
            delete t1;
            t=t->next;
        }
    }
}
int main()
{
    List *begin=NULL;
    Init(&begin);
    Print(begin);
    Delete(begin);
    Print(begin);
    getch();
    return 0;
}

После запуска программы в консоль не выводится преобразованный список. В чем может заключаться проблема?

@GoldenId · 01.06.2017, 23:55

Что будет, если в функции

C++

1	void Delete(List *begin);

со входа будет

C++

1	t->k!=t1->k

?

@Sergeev Fedor · 02.06.2017, 00:18 **[ТС]**

Как я понял стоит добавить

C++

         else
        {
            t=t->next;
        }

? Но от этого ситуация, к сожалению, не изменилась
Исправил вот так:

C++

#include <iostream>
#include <conio.h>
using namespace std;
struct List
{
    int k;
    List *next;
};
void Init(List **begin)
{
    *begin = new List;
    int mas[]={1,2,1,3,3,1,4};
    (*begin)->k=mas[0];
    (*begin)->next=NULL;
    List *end = *begin;
    for (int i=1; i<=6; i++)
    {
        end->next = new List;
        end = end->next;
        end->k=mas[i];
        end->next=NULL;
    }
}
void Print(List *b)
{
    List *print = b;
    while(print)
    {
        cout << print->k << " ";
        print = print->next;
    }
    cout << "NULL\n";
}
void Delete(List **begin)
{
    if (*begin==NULL)
    {
        return;
    }
    List *t = *begin;
    while(t)
    {
        List *t1 = t->next;
        if (t->k==t1->k)
        {
            t->next=t1->next;
            delete t1;
            t=t->next;
        }
        else
        {
            t=t->next;
        }
    }
}
int main()
{
    List *begin=NULL;
    Init(&begin);
    Print(begin);
    Delete(&begin);
    Print(begin);
    getch();
    return 0;
}

Добавлено через 14 минут
GoldenId, в чём ещё может быть проблема? Указатели стоят правильно?

@GoldenId · 02.06.2017, 00:25

У вас один цикл.. одновложенный. Такой цикл не справляется с удалением дубликатов, которое в лучшем случае имеет временную сложность
$https://www.cyberforum.ru/cgi-bin/latex.cgi?O\left(n\cdot log\left(n \right) \right)$
, а если делать в лоб, то и
$https://www.cyberforum.ru/cgi-bin/latex.cgi?O\left( {n}^{2} \right)$
Вам нужен двувложенный цикл (цикл внутри цикла).

MrGluck · 02.06.2017, 00:38

Комментарий модератора

Sergeev Fedor, запрещено дублировать темы

@Sergeev Fedor · 02.06.2017, 00:45 **[ТС]**

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

@GoldenId · 02.06.2017, 00:58

Как бы Вы делали, если бы это был массив, а удалением считалась бы замена на какое-то заранее предопределённое (в дальнейшем не обрабатываемое) значение?

@GoldenId 142 / 143 / 64 Регистрация: 11.11.2010 Сообщений: 864 Записей в блоге: 10
	02.06.2017, 00:25	4
	У вас один цикл.. одновложенный. Такой цикл не справляется с удалением дубликатов, которое в лучшем случае имеет временную сложность $https://www.cyberforum.ru/cgi-bin/latex.cgi?O\left(n\cdot log\left(n \right) \right)$ , а если делать в лоб, то и $https://www.cyberforum.ru/cgi-bin/latex.cgi?O\left( {n}^{2} \right)$ Вам нужен двувложенный цикл (цикл внутри цикла). 0

@Sergeev Fedor 6 / 5 / 1 Регистрация: 22.01.2016 Сообщений: 100
	02.06.2017, 00:45 [ТС]	6
	GoldenId, да, согласен с вами. Если одинаковых чисел будет больше двух, то программа должна удалить только одну лишнюю, а остальные останутся (например 1 1 2 1 3 4 -> 1 2 1 3 4). Но на данный момент программа не работает даже для удаления одного элемента из числа нескольких дубликатов. А именно не выводит на экран получившийся (преобразованный) список. Выводит только исходный 0

@GoldenId 142 / 143 / 64 Регистрация: 11.11.2010 Сообщений: 864 Записей в блоге: 10
	02.06.2017, 00:58	7
	Как бы Вы делали, если бы это был массив, а удалением считалась бы замена на какое-то заранее предопределённое (в дальнейшем не обрабатываемое) значение? 0

Опции темы