Премини към съдържанието
SeatFR

Помощ за двусвързан списък-пръстен

Препоръчан отговор


Играта е "Броеница". N деца застават в кръг и получават номера от 1 до N. Като се започне от дете 1 по часовниковата стрелка (всяко нечетно броене) или обратно на часовниковата (за всяко четно броене) се отброяват M деца. Дете с номер M излиза и започва ново броене от следващото дете. Продължава докато остане 1 дете.

 

Играта работи идеално с движение в едната посока, но това с броенето в две посоки ме озадачава. Прилагам кода, в който съм добавил функция за инвертиране на списъка след всяко броене (т.е. да не променям посоката на броене, а само да инвертирам данните), но не се получава.

#include <iostream>
using namespace std;
void add(int n);
void invert();
struct elem
{
	int key; elem *next; elem *prev;
} *start = NULL;

int main()
{
	int i, n, m;
	cout << "Zadaite broq na decata N: ";
	cin >> n;
	for (i = n; i>0; i--)
		add(i);
	elem *p = start;
	while (p->next != NULL)
		p = p->next;
	p->next = start;
	cout << "\nVuvedete cqlo polojitelno chislo M: ";
	cin >> m;
	p = start;
	elem *q = start;
	do
	{
		for (i = 1; i < m; i++)
		{
			q = p;
			p = p->next;
		}
		q->next = p->next;
		cout << "\nIzkluchva se nomer " << p->key;
		delete (p);
		p = q->next;
		invert();
	} while (p != p->next);
	cout << "\nNomerut na poslednoto dete e: " << p->key;
	cout << endl;
	return 0;
}
void add(int n)
{
	elem *p = start;
	start = new elem;
	start->key = n;
	start->next = p;
	start->prev = NULL;
	if (p)
		p->prev = start;
}
void invert()
{
	elem *p = start, *q;
	while (p)
	{
		q = p->next;
		p->next = p->prev;
		p->prev = q;
		if (q == NULL)
			start = p;
		p = q;
	}
}

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Не разбирам какво сложно има в обратната посока. Просто се използва prev вместо next. Забелязвам че когато изтриваш не променяш prev на елемента, който е следвал изтрития.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

+1, освен това може да се случи да трябва да се изтрие първия елемет - тогава start трябва да се премести на следващия.

#include <iostream>
using namespace std;
 
struct elem
{
    int key; 
    elem *next; 
    elem *prev;
}  *start = NULL;
 
void add(int n)
{
    elem *p = start;
    start = new elem;
    start->key = n;
    start->next = p;
    if (p) p->prev = start;
}
 
void del(elem *p) 
{
     p->prev->next=p->next;
     p->next->prev=p->prev;
     cout << "\nIzkluchva se nomer " << p->key;
     delete(p);
}
 
int main()
{
    int n, m;
    cout << "Zadaite broq na decata N: ";
    cin >> n;
    for (int i = n; i>0; i--) add(i);
    elem *p = start;
    while (p->next != NULL) p = p->next;
    p->next = start;
    start->prev=p;
    
    cout << "\nVuvedete cqlo polojitelno chislo M: ";
    cin >> m;
    do
    {   
        p=start;
        for (int i = 1; i < m; i++) p=p->next;
        start=p->next; del(p);

        if (start==start->next) break;

        p=start;
        for (int i = 1; i < m; i++) p=p->prev;
        start=p->prev; del(p);

    } while (start != start->next);
    cout << "\nNomerut na poslednoto dete e: " << start->key;
    cout << endl;
    return 0;
}

Редактирано от ined (преглед на промените)
  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Извинявам се, че ви занимавах. Програмата я бях писал като ined и си работеше така, но бях допуснал грешка в алгоритъма си и си мислех, че работи грешно, а тя си е работила правилно. Благодаря ви за помощта! :)

Редактирано от SeatFR (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Регистрирайте се или влезете в профила си за да коментирате

Трябва да имате регистрация за да може да коментирате това

Регистрирайте се

Създайте нова регистрация в нашия форум. Лесно е!

Нова регистрация

Вход

Имате регистрация? Влезте от тук.

Вход

×

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите условия за ползване.