c++ lista cykliczna - dodawanie elementów i porządkowanie ich

0

Witam. Muszę napisać listę cykliczną, w której stworzę funkcję dodającą do listy element na odpowiednią pozycję (lista ma być uporządkowana rosnąco według wartości zmiennej info). Chodzi o funkcję add_node - pomyślałem, że najlepiej będzie stworzyć wskaźniki na czoło (p1) i następny element (p2) i w while'u porównywać kolejne elementy z nowym i przechodzić do następnych, a po dojściu na właściwe miejsce wsadzać nowy element między te dwa. Niestety funkcja działa tylko przy dodawaniu elementów o wartościach mniejszych od elementu o największej wartości w liście. Przy dodawaniu elementu o wartości większej od największego elementu w liście program się zawiesza. Nie bardzo wiem, co robię źle:

 
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

struct node
{
    int info;
    struct node *next;
}*head;

class circular_llist
{
    public:
        void create_node(int value);
        void add_node(int value);
        void display_list();
        circular_llist()
        {
            head = NULL;
        }
};

void circular_llist::create_node(int value)
{
    struct node *nowy;
    nowy = new(struct node);
    nowy->info = value;
    if (head == NULL)
    {
        head = nowy;
        nowy->next = head;
    }
    else
    {
        nowy->next = head->next;
        head->next = nowy;
        head = nowy;
    }
}

void circular_llist::add_node(int value)
{
    if (head == NULL)
    {
        cout<<"First Create the list."<<endl;
        return;
    }
    struct node *nowy, *p1, *p2;
    nowy = new(struct node);
    nowy->info = value;

    p2=head;
    p1=head->next;
    while(nowy->info > p1->info)
        {
            p2 = p2->next;
            p1 = p1->next;
        }
        p2->next = nowy;
        nowy->next = p1;
}
void circular_llist::display_list()
{
    struct node *s;
    if (head == NULL)
    {
        cout<<"List is empty"<<endl;
        return;
    }
    s = head->next;
    cout<<"Circular Link List: "<<endl;
    while (s != head)
    {
        cout<<s->info<<"->";
        s = s->next;
    }
    cout<<s->info<<endl<<endl;

}

int main()
{
    int choice, element;
    circular_llist cl;
    while (1)
    {
        cout<<"1.Create node"<<endl;
        cout<<"2.Add node"<<endl;
        cout<<"3.Display"<<endl;
        cout<<"9.Quit"<<endl;
        cout<<"Enter your choice : ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter the element: ";
            cin>>element;
            cl.create_node(element);
            cout<<endl;
            break;
        case 2:
            cout<<"Enter the element: ";
            cin>>element;
            cl.add_node(element);
            cout<<endl;
            break;
        case 3:
            cl.display_list();
            break;
        case 9:
            exit(1);
            break;
        default:
            cout<<"Wrong choice"<<endl;
        }
    }
    return 0;
}

1
  1. przenieś definicje node do wnętrza definicji circular_llist. Teraz masz koszmarek w postaci globalnego wskaźnika head.
  2. nie musisz przed każdym node pisać słówko struct. Piszesz w C++ a nie C.
  3. zawiesza Ci się, bo pętla cały czas się kręci, brak jej ograniczenia przeszukiwania od head do head.

Jakoś tak to powinno wyglądać:

class circular_list
{
    struct node 
	{
		int info;
		node* next;
    };
	
	node* head;
	node* tail;

public:
    
    void add_node(int value)
	{
		node *nowy, *p1, *p2;
	 
		nowy = new node;
		nowy->info = value;
	 
		if (head == nullptr)
		{
			head = tail = nowy;
			head->next = head;
			return;
		}    
	 
		p1 = nullptr;
		p2 = head;
	 
		while(p2->info < nowy->info )
		{
			p1 = p2;
			p2 = p2->next;
	 
			if(p2 == tail) break;
		}
	 
		if(p1 == nullptr)
		{
			head = nowy;
			nowy->next = p2;
			tail->next = head;
		}
		else 
		{
			p1->next = nowy;
			nowy->next = p2;
			if(p2 == head) tail = nowy;
		}
	}
	
	
    circular_list() 
	: head(nullptr), tail (nullptr)
    { }
	
	
	...

};

pisane z palca, więc coś może nie działać.

1 użytkowników online, w tym zalogowanych: 0, gości: 1