[C++] Удаление элемента из кольцевого однонаправленого списка. - Общие вопросы C/C++

CortesGames · 02.03.2017, 22:21

Нужно удалить все элементы 'p ' перед элементами 'a' из кольцевого однонаправленого списка.
И есть вот такой код:

Код:

#include <iostream>

struct NODE {
    int value;
    struct NODE * prev;
    struct NODE * next;
};

struct DbCircleList {
    size_t size;
    struct NODE * head;
};

void addNode(DbCircleList * list, int elem) {
    NODE * newElem = new NODE;
    newElem->value = elem;
    if (list->size == 0) {
        list->head = newElem;
        list->head->next = list->head;
        list->head->prev = list->head;
    }else {
        newElem->next = list->head;
        newElem->prev = list->head->prev;
        list->head->prev->next = newElem;
        list->head->prev = newElem;
    }
    ++list->size;
}
void printList(DbCircleList * list) {
    NODE * tmp = list->head;
    std::cout << "List values: " << std::endl;
    for (int i = 0; i < list->size; ++i) {
        std::cout << "Value: " << tmp->value << std::endl;
        tmp = tmp->next;
    }
}
void removeNodes(DbCircleList * list) {
    NODE * tmp = list->head;
    for (int i = 0; i < list->size; ++i) {
        if (tmp->value == 8) {
            NODE * toDel = new NODE;
            toDel = tmp->next;
            tmp->next = tmp->next->next;
            tmp->next->prev = tmp;
            delete toDel;
            --list->size;
        }
        tmp = tmp->next;
    }
}
int main(){
    DbCircleList * list = new DbCircleList;
    list->size = 0;
    list->head = NULL;
    for (int i = 0; i < 10; ++i) {
        int v;
        std::cin >> v;
        addNode(list, v);
    }
    printList(list);
    removeNodes(list);
    printList(list);
    delete list;
    return 0;
}

Но этот код не подходит так как он для двунаправленого списка и удаляет все элементы перед которыми стоит элемент с числом 8. Надо переделать этот код так чтобы он подходил под задание. Но из-за недостатка системы образования нам толком не обяснили как он работает. Просьба обяснить как он работает или помочь переделать. Буду премного благодарен.

CortesGames · 07.03.2017, 16:53

Up theme

New man · 07.03.2017, 17:43

Цитата:

Сообщение от CortesGames

++list->size;

Код нерабочий, выкидывайте.

Загуглите реализацию двусвязного связка, примеров в Интернете море.

CortesGames · 08.03.2017, 17:15

Цитата:

Сообщение от New man

Код нерабочий, выкидывайте.

Загуглите реализацию двусвязного связка, примеров в Интернете море.

Мне нужен односвязный кольцевой список, я не могу найти примеров, можно ссылку пожалуйста.

ura_111 · 08.03.2017, 19:46

Вот например (тебе надо только до комментария: "///////Сама программа///////", а остальной код я оставил, чтобы ты мог посмотреть как манипулировать с узлами списка. Эта программа чужая) :

Код:

struct list
{
	int key;
	list* next;
};

#include <conio.h>
#include <stdio.h>

int main()
{
	list *head = new list;	head->key = 0;
	list *h1 = new list;	h1->key = 1;  head->next = h1;	
	list *h2 = new list;	h2->key = 2;    h1->next = h2;
	list *h3 = new list;	h3->key = 3;	h2->next = h3;
	list *h4 = new list;	h4->key = 4;	h3->next = h4;
	list *h5 = new list;	h5->key = 5;	h4->next = h5;
	list *h6 = new list;	h6->key = 6;	h5->next = h6;
	                                        h6->next = NULL;
	// Вывод на экран первоначального массива
	list *vuvod;
	vuvod = head;
	while (vuvod)
	{
		printf("%d ", vuvod->key);
		vuvod = vuvod->next;
	}
	printf("\n");

	//////////////////Сама программа/////////////////////////////
	int num = 3;	
	list *p, *first, *END;
	p = head;	
	int count = 0;
	while (count != num) // Сдвигаем голову
	{
		END = p;
		if (p->next == NULL)
		{
			p = head;
			count++;
			continue;
		}
		p = p->next;		
		count++;
	}	
	if (END->next != NULL)
	{
		END->next = NULL;
		while (p != NULL)
		{
			first = p;
			p = p->next;
			first->next = head;
			head = first;
		}
	}
	/////////////////////////////////////////////////////////

	// Вывод на экран результата
	vuvod = head;
	while (vuvod)
	{
		printf("%d ", vuvod->key);
		vuvod = vuvod->next;
	}
	scanf("%d", &num); // чтобы консоль быстро не закрывалась
	return 0;
}

А чтобы доделать этот код до кольцевого списка (нужно применить идею):

0.jpg

p.s.: твоя задача - проследить по коду (сопоставляй с фотографией) где формируются список, как он выглядит и что нужно переделать в коде, чтобы он превратился в кольцевой...
Для начала просто ("в ручную") создай кольцевой список (как в примере показано); и только после этого, переходи к написанию своей программы.

CortesGames · 08.03.2017, 20:20

Я так и сделал, сначала написал программу для кольцевого списка и только потом начал выполнять задачу. Но почему-то оно удаляет "а" перед "р", а не "р" перед "а".
Вот код:

Код:

#include <stdio.h>
#include <stdlib.h>

struct node{
    char data;
    struct node *next;
}*START=NULL;

void insertData(char);
void displayData(void);
void removeData(void);

int main(void){
    int ch;
    char let;
    do{
        printf("\n1. Add element");
        printf("\n2. Display list");
        printf("\n3. Delete all 'p' before 'a'");
        printf("\n4. Exit");
        printf("\nYour choice: ");
        scanf("%d",&ch);
        switch(ch){
            case 1:
                    printf("Enter any letter: ");
                    scanf("%s",&let);
                    insertData(let);
                    break;
            case 2:
                    displayData();
                    break;
            case 3:
                    removeData();
                    displayData();
                    break;
            case 4:
                    exit(0);
            default:
                    printf("Invalid Choice");
        }
        printf("------------------------------------------------------------------------------------------------\n");
    }while(1);
    return 1;
}

void insertData(char let){
    struct node *q,*temp;
    if(START==NULL){
        START=(struct node*)malloc(sizeof(struct node));
        START->data=let;
        START->next=START;
    }else{
        q=START;
        while(q->next!=START){
            q=q->next;
        }
        temp=(struct node*)malloc(sizeof(struct node));
        temp->data=let;
        temp->next=START;
        q->next=temp;
    }
}

void displayData(void){
    struct node *q=START;
    printf("List:\t");
    do{
        printf("%c\t",q->data);
        q=q->next;
    }while(q!=START);
    printf("\n");
}

void removeData(void){
    struct node *q=START;
    do{
        if(q->next->data=='p' && q->next->next->data=='a'){
            q=q->next->next;
            free(q->next);
        }
        q=q->next;
    }while(q!=START);
}

ura_111 · 08.03.2017, 22:16

А ну, протестируй (при разных количествах узлов и в разных комбинациях а/р):

Код:

#include <stdio.h>

struct list
{
	char key;
	list* next;
};

int main()
{
	list *head = new list;	head->key = 'a';
	list *h1 = new list;	h1->key = 'a';  head->next = h1;
	list *h2 = new list;	h2->key = 'p';    h1->next = h2;
	list *h3 = new list;	h3->key = 'a';	  h2->next = h3;
	list *h4 = new list;	h4->key = 'p';	  h3->next = h4;
	list *h5 = new list;	h5->key = 'a';	  h4->next = h5;
	list *h6 = new list;	h6->key = 'p';	  h5->next = h6;
	list *h7 = new list;	h7->key = 'p';	  h6->next = h7;
	list *h8 = new list;	h8->key = 'a';	  h7->next = h8;
	list *h9 = new list;	h9->key = 'p';	  h8->next = h9;
	list *h10 = new list;  h10->key = 'a';	  h9->next = h10;
	h10->next = head;

	// Вывод на экран первоначального массива
	list *vuvod;
	vuvod = head;
	while (vuvod->next != head)
	{
		printf("%c ", vuvod->key);
		vuvod = vuvod->next;
	}
	printf("%c ", vuvod->key);
	printf("\n");
	////////////////////Сама программа/////////////////////////////
	list *one = head;
	list *two = one->next;
	list *fre = two->next;
	while (two->next != head)
	{
		if (two->key == 'p' && fre->key == 'a')
		{
			one->next = fre;
			two = fre;
			fre = fre->next;
		}
		else
		{
			one = one->next;
			two = two->next;
			fre = fre->next;
		}
	}
	/////////////////////////////////////////////////
	vuvod = head;
	while (vuvod->next != head)
	{
		printf("%c ", vuvod->key);
		vuvod = vuvod->next;
	}
	printf("%c ", vuvod->key);
	printf("\n");

	int num;
	scanf("%d", &num); // чтобы консоль быстро не закрывалась
	return 0;
}

CortesGames · 09.03.2017, 22:58

Цитата:

Сообщение от ura_111

А ну, протестируй (при разных количествах узлов и в разных комбинациях а/р):

Код:

#include <stdio.h>

struct list
{
	char key;
	list* next;
};

int main()
{
	list *head = new list;	head->key = 'a';
	list *h1 = new list;	h1->key = 'a';  head->next = h1;
	list *h2 = new list;	h2->key = 'p';    h1->next = h2;
	list *h3 = new list;	h3->key = 'a';	  h2->next = h3;
	list *h4 = new list;	h4->key = 'p';	  h3->next = h4;
	list *h5 = new list;	h5->key = 'a';	  h4->next = h5;
	list *h6 = new list;	h6->key = 'p';	  h5->next = h6;
	list *h7 = new list;	h7->key = 'p';	  h6->next = h7;
	list *h8 = new list;	h8->key = 'a';	  h7->next = h8;
	list *h9 = new list;	h9->key = 'p';	  h8->next = h9;
	list *h10 = new list;  h10->key = 'a';	  h9->next = h10;
	h10->next = head;

	// Вывод на экран первоначального массива
	list *vuvod;
	vuvod = head;
	while (vuvod->next != head)
	{
		printf("%c ", vuvod->key);
		vuvod = vuvod->next;
	}
	printf("%c ", vuvod->key);
	printf("\n");
	////////////////////Сама программа/////////////////////////////
	list *one = head;
	list *two = one->next;
	list *fre = two->next;
	while (two->next != head)
	{
		if (two->key == 'p' && fre->key == 'a')
		{
			one->next = fre;
			two = fre;
			fre = fre->next;
		}
		else
		{
			one = one->next;
			two = two->next;
			fre = fre->next;
		}
	}
	/////////////////////////////////////////////////
	vuvod = head;
	while (vuvod->next != head)
	{
		printf("%c ", vuvod->key);
		vuvod = vuvod->next;
	}
	printf("%c ", vuvod->key);
	printf("\n");

	int num;
	scanf("%d", &num); // чтобы консоль быстро не закрывалась
	return 0;
}

Не работает если первый узел p а второй а. Во всех остальных работает.

ura_111 · 10.03.2017, 09:53

А это (протестируй):

Код:

#include <stdio.h>

struct list
{
	char key;
	list* next;
};

int main()
{
	list *head = new list;	head->key = 'p';
	list *h1 = new list;	h1->key = 'a';  head->next = h1;
	list *h2 = new list;	h2->key = 'p';    h1->next = h2;
	list *h3 = new list;	h3->key = 'a';	  h2->next = h3;
	list *h4 = new list;	h4->key = 'p';	  h3->next = h4;
	list *h5 = new list;	h5->key = 'a';	  h4->next = h5;
	list *h6 = new list;	h6->key = 'p';	  h5->next = h6;
	list *h7 = new list;	h7->key = 'p';	  h6->next = h7;
	list *h8 = new list;	h8->key = 'a';	  h7->next = h8;
	list *h9 = new list;	h9->key = 'p';	  h8->next = h9;
	list *h10 = new list;  h10->key = 'p';	  h9->next = h10;
	h10->next = head;
	
	int vuvod;
	int n = 10; // количество узлов

	// Вывод на экран первоначального массива
	vuvod = 0;
	while (vuvod < n)
	{
		printf("%c ", head->key);
		head = head->next;
		vuvod++;
	}
	printf("%c ", head->key);
	printf("\n");
	////////////////////Сама программа/////////////////////////////
	list *one = head;
	list *two = one->next;
	list *fre = two->next;
	head = one->next;	
	int kol = n;
	bool flag = false;
	vuvod = 0;
	while (vuvod < kol)
	{
		if (two->key == 'p' && fre->key == 'a')
		{
			one->next = fre;
			two = one->next;
			fre = two->next;
			n--;
			if (vuvod == 0)
				flag = true;
		}
		else
		{
			one = one->next;
			two = two->next;
			fre = fre->next;
		}
		vuvod++;
	}
	if (two->key == 'p' && fre->key == 'a' && flag == false)
	{
		one->next = fre;
		head = head;
	}
	else
		head = fre;
	///////////////////////////////////////////////////
	vuvod = 0;
	while (head < head->next)
	{
		printf("%c ", head->key);
		head = head->next;
		vuvod++;
	}
	printf("%c ", head->key);
	printf("\n");

	int num;
	scanf("%d", &num); // чтобы консоль быстро не закрывалась
	return 0;
}

CortesGames · 10.03.2017, 23:00

Можешь пожалуйста обяснить что в ней происходит?Я просто не совсем понимаю эту систему с флагом, и почему у тебя head это не первый а второй элемент?

07.03.2017, 16:53	#2
CortesGames Пользователь Регистрация: 23.10.2016 Сообщений: 86	Up theme Насылаю баги по фотографии преимущественно себе

10.03.2017, 23:00	#10
CortesGames Пользователь Регистрация: 23.10.2016 Сообщений: 86	Можешь пожалуйста обяснить что в ней происходит?Я просто не совсем понимаю эту систему с флагом, и почему у тебя head это не первый а второй элемент? Насылаю баги по фотографии преимущественно себе

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
c++ удаление элемента списка	NinjaNoob	Помощь студентам	1	28.01.2013 04:01
Сортировка однонаправленого списка вставками.	gvilon	Паскаль, Turbo Pascal, PascalABC.NET	0	08.11.2011 23:39
Удаление элемента из списка	bpystep	Помощь студентам	4	09.07.2010 14:55
Удаление элемента из списка	Ghost_gg	Паскаль, Turbo Pascal, PascalABC.NET	2	30.05.2010 20:43
Удаление последнего элемента из списка и реверс этого списка.	Goose	Общие вопросы C/C++	8	16.05.2010 16:12