Sorting a linked list

This is a discussion on Sorting a linked list within the C++ Programming forums, part of the General Programming Boards category; Hi All, My task: For example, existed 2 elements of linkedlist with seven numbers: 1 3 5 7 23 24 ...

  1. #1
    Registered User qtwo's Avatar
    Join Date
    Dec 2009
    Posts
    1

    Sorting a linked list

    Hi All,

    My task:

    For example, existed 2 elements of linkedlist with seven numbers:
    • 1 3 5 7
    • 23 24 30

    inserting "6" and now we must have 3 elements of linkedlist:
    • 1 3
    • 5 6 7
    • 23 24 30


    inserting "10" and 3 elements of linkedlist:
    • 1 3
    • 5 6 7 10
    • 23 24 30



    So now I have this code
    Code:
    #include <iostream>
     
    struct nodes
    {
            
            void sort();
            void push(int value);
            void pop(int* value);
            void show();
            bool is_full();
            
            int* array;
            nodes* prior;
            
            nodes(){array = new int [4];top = 0;}
            ~nodes(){delete[] array;}
            int top; 
    };
    //============================================================
    struct linked_lists
    {
     
                    void show(); 
                    void add(int value);
                                    
                    linked_lists(){tail = NULL;}
                    ~linked_lists();
                    nodes* tail;            
    };
     
    //============================================================
    int main()
    {
    	time_t t;
    	srand((unsigned) time(&t));
    
            linked_lists *a = new linked_lists();
     
            a->show();
            system("pause");
    
    		for(int i=0;i<8;i++) 
    		{
    			a->add(rand() %50 + 0);
                            a->show();
                            system("pause");
    		}
        
            
            system("cls");
            a->show();       
            system("pause");
            delete a;
            system("pause");
            return 0;
    }
     
    //============================================================
    void nodes::push(int value)
    {
            if (top>9) return; 
            array[top++]=value;
    }
     
    void nodes::pop(int* out)
    {
            if (!top) return; 
            
            *out = array[--top];
    }
     
    void nodes::show()
    {
            for(int i=0;i<top;i++) std::cout<<"  "<<array[i];
    }
     
    void nodes::sort()                                     
    { 
            int tmp, i, j;
            for ( i=0; i < top; i++)
            {  
                tmp = array[i];   
            for ( j=i-1; j>=0 && array[j] > tmp; j--)
                    array[j+1] = array[j];
            array[j+1] = tmp;
            }
    }
    bool nodes::is_full()
    {
            return (top==4);
    }
     
     
    // =====================================================================
    void linked_lists::add(int value)
    {
            if (tail==NULL) { tail = new nodes(); tail->prior=NULL;}
     
     
            if(!tail->is_full())
            {
                    tail->push(value);
                    tail->sort();
            }
            else 
     
            {
                    nodes* node = new nodes();
                    node->prior = tail;
                    
                    int tmp;
                    for(int i=1;i<=2;i++)
                    {
                            tail->pop(&tmp);
                            node->push(tmp);
                    }
                    tail->pop(&tmp);
                    if(value<tmp) {tail->push(value);node->push(tmp);}
                    else {tail->push(tmp);node->push(value);}
                 
                
                    
                    tail = node;
                    tail->sorting();
    		tail->prior->sorting();
                    
            }
            
    }
     
     
    void linked_lists::show()
    {
            if(tail==NULL) {std::cout<<"\n linked-list is empty now..\n\n";return;}
            nodes* ip = tail;
            while (true)
            {
                    std::cout<<ip;
                    ip->show();
                    std::cout<<"\n";
                    if(ip->prior==NULL)     break;
                    ip=ip->prior;
            }
     
    }
     
    linked_lists::~linked_lists()
    {
            if(tail==NULL) {std::cout<<"\nmemory is free!!\n";return;}
            
            nodes* ip = tail;
            while (ip->prior!=NULL)
            {
                    tail = ip;
                    ip=ip->prior;
                    delete tail;
            }
            delete ip;
            std::cout<<"\n memory is free!!!";      
            }
     
     
    //======================================================================
    And result of this is not correct, for example:
    • 14 37 46 47
    • 16 35
    • 3 26


    Thanks in advance!

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    You should be posting to the C++ forum.

    C++ Programming
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,303
    Indeed, and moved.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Circularly-Doubly Linked List implementation
    By BlackOps in forum C Programming
    Replies: 4
    Last Post: 07-19-2009, 05:45 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 09:04 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 11:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21