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
    23,803
    Indeed, and moved.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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, 04:45 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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