Удалить все копии элемента в списке, кроме последнего вхождения
Как удалить все копии элементов в списке, кроме их последнего вхождения? Код ниже работает частично - только для одной копии элемента. Но если элемент стоит в начале или повторяется больше 2-х раз, то выдаёт разные ошибки.
Ожидаемы результат для списка 2 3 3 2 4 5 6 5 -> 3 2 4 6 5. Но при попытке выполнить получаем: Вызвано исключение: нарушение доступа для чтения. cur было 0xFFFFFFFFFFFFFFF7. на строку for (List* cur(head); cur && cur->next; cur = cur->next) {
Пример 1: Есть список 2 3 4 5 3. После выполнения станет правильным -> 2 4 5 3
Пример 2: Иной список 3 2 4 5 3. После выполнения пишет, что удалён 1 элемент, но после попытки вывода возникает ошибка Вызвано исключение: нарушение доступа для чтения. p было 0xFFFFFFFFFFFFFFFF. На строку printf("%d ", p->value);
Пример 3: Список с большим повторением 2 3 4 3 5 3. После выполнения пишет, что удалено 2 элемента, но выводится 2 4 5
Мне кажется, что ошибка в переданном head для функции Delete_copy, но как её разрешить не знаю.
struct List{
int value;
List* next;
List(int val = 0, List* p = NULL) {
value = val;
next = p;
}
};
List* Insert_first(int n, List* head){
List* q = new List(n, head);
return q;
}
List* Delete_value(int n, List* head)
{
List* p = head, * t;
if (head == NULL) { puts("LIST EMPTY!"); return NULL; }
if (head->value == n)
{
t = head;
head = head->next;
delete t;
return head;
}
while (p->next != NULL)
if (p->next->value == n)
{
t = p->next;
p->next = p->next->next;
delete t;
return head;
}
else p = p->next;
puts("NO VALUE!");
return head;
}
void Print_list(List* head){
List* p = head;
puts("\n PRINT LIST");
if (p == NULL) puts("List empty!");
else
while (p != NULL){
printf("%d ", p->value);
p = p->next;
}
}
int Delete_copy(int countRes, List * head) {
std::vector<int> v;
v.push_back(head->value);
for (List* cur(head); cur && cur->next; cur = cur->next) {
if ((std::find(v.begin(), v.end(), cur->next->value) != v.end()) && cur->next) {
head = Delete_value(cur->next->value, head);
countRes++;
Delete_copy(countRes, head);
}
else {
if (cur->next){
v.push_back(cur->next->value);
}
else {
return countRes;
}
}
}
return countRes;
}
void main()
{
int i, k, n, num;
char const * ss[] = { "\n 0-Print list"," 1-Insert first", " 2-Delete copy"," 3-EXIT" };
char c{};
List* head = NULL;
k = sizeof(ss) / sizeof(ss[0]);
for (;;){
for (i = 0; i < k; i++) puts(ss[i]);
scanf_s("%c", &c);
switch (c){
case '0': Print_list(head); break;
case '1': printf("n = "); scanf_s("%d", &num); head = Insert_first(num, head); break;
case '2': printf("Was delete %d elemens", Delete_copy(0, head)); break;
case '3': return;
}
}
}
Ответы (1 шт):
Кое-как, но нашёл такое решение. Если есть идеи по оптимизации, то буду благодарен (Можно динамически задавать массивы). Функция Delete_value из вопроса не менялась
List* Delete_copy(int countRes, List * &head) {
List* p, * q, * def;
p = head;
q = head;
def = head;
int keys[10];
int values[10];
for (int i = 0; i < 10; i++) {
keys[i] = 0;
values[i] = 0;
}
int arr_length = 0;
while (p != NULL) {
int index = 0;
for (int i = 0; i < 10; i++) {
if (keys[i] == p->value) {
values[i]++;
index = 0;
break;
}
else {
index++;
}
}
if (index == 0) {
p = p->next;
continue;
}
else {
if (arr_length < 10) {
keys[arr_length] = p->value;
values[arr_length]++;
arr_length++;
}
}
p = p->next;
}
int counter = 0;
for (int i = 0; i < 10; i++) {
if (values[i] > 1) {
for (int countCopy = 0; countCopy < values[i]-1; countCopy++) {
def = Delete_value(keys[i], def);
counter++;
}
}
}
printf("Was delete %d elemens", counter);
return def;
}
И в менюшке
case '2': head = Delete_copy(0, head); break;