linked list ,, Help me

[AbEeR Q8]

Hello ;

I need a help in my home work , I have to write the program that prints the number of clock ticks it took the program to sort the data

the main part is already given , I have to wright the functions

this is my program ::

#include<iostream>
using namespace std;
struct Cell{
       int data;
       Cell* next;
       Cell(int d,Cell *n=0){
            data=d;
            next=n;
            }
       };

// print all elements in linked-list p
void print(Cell *p){
    if(p!=0){
        cout<<p->data<<" , ";
        print(p->next);
        }
    }

// deletes all cells in linked-list p   
void dispose(Cell *p){
     while(p!=0){
           Cell *h=p->next;
           delete []p;
           p=h;
           }
     }

//returns the number of elements in p that are sorted non-descendingly
int countSorted2 (Cell *p,Cell *h){
     if( (h->next != 0) && ( h->next->data > h->next->next->data) )
        return 0+countSorted2 (p,h->next);
      else
          return 1+countSorted2 (p,h->next);
      }
int countSorted (Cell *p){
     return countSorted2 (p,p);
     }

//Inserts data into the sorted list L
void insert2(Cell *& L,Cell *& h ,int data){
     if( (h->next!=0) && (h->data > h->next->data) )
        insert2 (L,h->next,data);
      else
          h->next=new Cell(data,0);
      }   
void insert(Cell* &L, const int data){
     insert2(L,L,data);
     }
     
//Builds a linked-list of the N numbers in A , the order of elements is not important
Cell *build2 (int A[],int k,int N){
      if( N == 0) return 0;
      else 
          return new Cell (A[k] , build2(A, k+1, N-1));
          }
Cell * build(int A[], int N){
       return build2 (A,0,N) ;
       }
       

// Splits the list L into two equal sublists p and q ,  the order of elements is not important

void split(Cell *L, Cell*& p,Cell * &q){
     
    // I need a help here in how to write this function
     
     }

//Merges the lists p and q into a single sorted list , Both p and q are already sorted 
Cell *merge(Cell*p , Cell*q){
     Cell *h;
     if (p->data < q->data){
         h->data=p->data;
         return merge(p->next,q);
         }
     else{
          h->data=q->data;
          return merge(p,q->next);
          }
     h=h->next;
     return h;
     }


// this fourth functions are given also
Cell *msort(Cell *L){
      if ((L==0) || (L->next == 0)) return L;
      else {
            Cell *p, *q ;
            split(L,p,q) ;
            return merge(msort(p),msort(q)) ;
            }
      }

Cell* merge_sort(int A[], int N) { 
      return msort(build(A,N)) ; 
      }

Cell* insertion_sort(int A[], int N){
      Cell *L = 0 ;
      while (N-- > 0){
            insert(L,A[N]) ;
            }
      return L ;
      }

void random(int A[], const int N) {
     srand(time(0)) ;
     for (int k = 0 ; k < N ; k++) A[k] = rand() % (2*N) - N ;
     }

int main(int argc, char** argv){
    if (argc != 3){
        cout << "Error: Need exactly two arguments: Sort-type & size" << endl ;
        return -1 ;
        }
    char type = *argv[1]  ;
    int N = atoi(argv[2]) ;
    int* data = new int[N] ;
    random(data,N) ;
    
    clock_t T0 = clock() ;
    Cell* A = (type=='I' || type = 'i') ? insertion_sort(data,N)
                                        : merge_sort(data,N) ;
    clock_t T1 = clock() ;
    if (countSorted(A) != N)
        cout << "logical error in sorting routine!" << endl ;
    else
        cout << type << " " << N << " " << (T1-T0) << endl ; 
    if (N < 50) print(A) ;
    dispose(A) ;*/
    delete [] data ;
    
cout<<"\n\n";
system("pause");
return 0;
}

thanks;

[raptr_dflo]

So which functions do you need to write? They all look "written" to me....

Accessing the system clock may be dependent on what operating system you're running on (Windows, Linux, other), and what APIs you have available. If you're running in Windows, try searching http://msdn.microsoft.com/ . It's often hard to filter out the results that -aren't- relevant, but eventually you should be able to find what you're looking for.

For future reference, we really don't need to see your entire working source code for this kind of question. Something as simple as the following would suffice, assuming I've understood your question:

void doSomething()
{
    cout << "blah!" << endl;
}

int main(int argc, char *argv[])
{
    clock_t startTime = clock();
    for (int i=0;  i < 1000000;  i++)
        doSomething();
    clock_t endTime = clock();
    cout << "took " << (endTime - startTime) << " ticks" << endl;
    return 0;
}

Speaking of understanding your question, please learn how to articulate your questions more clearly, such as "I need to determine the execution time of a piece of code; how would I implement the clock() function in this code sample? Is there a system function that returns relevant timing information? Perhaps a CPU instruction counter, or elapsed real or virtual run-time? I'm running Windows 7, in case that matters."

[AbEeR Q8]

void split(Cell *L, Cell*& p,Cell * &q){
 
    // I need a help here in how to write this function
 
     }

I'm running Windows 7
in this home work the ( main ) is already given so I can't change any things on it .
all what I need is to write the functions and I stopped in split function , I didn't know how to write it .
I thought add counter function to use it in split function

int count(Cell *L){
    if(L==0)
       return 0;
    else
       return 1+count(L->next);
    }

[raptr_dflo]

I'm sorry, I completely misunderstood your original post. If I now understand correctly, you're requesting help implementing recursive functions that perform certain tasks on linked lists. Specifically one that splits list L into two equal-length lists P and Q.

There are a variety of ways to go about this. You could use counting to:
1) determine which of P or Q is currently shorter (and thus should be added to next)
2) determine whether the length of L is even or odd (so you know which new list to add to next)
3) try to figure out where to split L so that P can point to the first half and Q can point to the second half (but this isn't recursive, only your count() function is)
4) and probably others!

But, given idea #2 above, can you think of a way to do the same thing (alternating between P and Q) without counting the number of elements in L?

[AbEeR Q8]

I'm solved the program Know and it's work
but there is ( error ) in sorting routine
so I have error in one of these functions ,

build or split or merge

I don't know what is the error exactly
can you help me , please .

#include<iostream>
using namespace std;
struct Cell{
       int data;
       Cell* next;
       Cell(int d,Cell *n=0){
            data=d;
            next=n;
            }
       };
       
// Prints all elements in linked-list p
void print(Cell *p){
    if(p != 0){
       cout<<p->data<<" , ";
       print(p->next);
       }
    }

// Deletes all cells in linked-list p     
void dispose(Cell *p){
     while(p != 0){
           Cell *h=p->next;
           delete []p;
           p=h;
           }
     }
     
// Returns the number of elements in p that are sorted non-descendingly     
int countSorted2 (Cell *p,Cell *h){
    if (p == NULL)
        return 0;
    else if( (h->next != 0) && (h->data > h->next->data) )
         return 0 + countSorted2(p,h->next);
    else
        return 1 + countSorted2(p,h->next);
    }
int countSorted (Cell *p){
    return countSorted2(p,p);
    }
    
// Inserts data into the sorted list L  
void insert(Cell* &L, const int data){
     Cell *h=L;
     if (h == NULL)
         h = new Cell(data,NULL);
     else if (data > h->data)
          h = new Cell (data,h->next);
     else {
           while ( (h->next != NULL) && (data > h->next->data) )
                  h=h->next;
           h->next = new Cell (data,h->next);
           }
     }
     
// Builds a linked-list of the N numbers in A , 
// the order of elements is not important
Cell * build(int A[], int N){
      if(N == 0) 
         return NULL;
      else 
          return new Cell (A[N-1] , build(A, N-1));
       }

// Return the number of elements       
int count(Cell *L){
    if (L == NULL)
        return 0;
    else
        return 1 + count(L->next);
    }

// Splits the list L into two equal sublists p and q ,  
// the order of elements is not important
void split(Cell *L, Cell*& p,Cell * &q){
     Cell *h=L;
     p=L;
     int x=1;
     while( (count(L)/2) != x){
           h=h->next;
           p->next=new Cell(h->data,NULL);
           x++;
           }
     q=h->next;
     }

// Merges the lists p and q into a single sorted list ,
// Both p and q are already sorted 
Cell *merge( Cell*p ,  Cell*q) {     
      Cell * h=NULL;   
      if(p->data < q->data){       
         h=p;         
         Cell *prev=NULL;          
         Cell * temp=NULL,*qnext=NULL;         
         while(p && q){             
               if (p->data < q->data){ 
                   prev=p;                 
                   p=p->next;              
                   }             
               else{                 
                   temp=prev->next;                 
                   prev->next=q;                 
                   qnext=q->next;                 
                   q->next=temp;                 
                   q=qnext;                 
                   prev=prev->next;
                   }
               } 
         }  
      return h; 
      } 

// Given /function      
Cell *msort(Cell *L){
      if ((L == 0) || (L->next == 0)) 
          return L;
      else {
            Cell *p, *q ;
            split(L,p,q) ;
            return merge( msort(p) , msort(q) ) ;
            }
      }

// Given /function
Cell* merge_sort(int A[], int N) { 
      return msort( build(A,N) ) ; 
      }

// Given /function
Cell* insertion_sort(int A[], int N){
      Cell *L = 0 ;
      while (N-- > 0){
            insert(L,A[N]) ;
            }
      return L ;
      }

// Given /function
void random(int A[], const int N) {
     srand(time(0)) ;
     for (int k = 0 ; k < N ; k++) 
          A[k] = rand() % (2*N) - N ;
     }

// Given Main
int main(int argc, char** argv){
    if (argc != 3){
        cout << "Error: Need exactly two arguments: Sort-type & size\n\n" ;
        system("pause");
        return -1 ;
        }
    char type = *argv[1]  ;
    int N = atoi(argv[2]) ;
    int* data = new int[N] ;
    random(data,N) ;
    
    clock_t T0 = clock() ;
    Cell* A = (type=='I' || type == 'i') ? insertion_sort(data,N)
                                         : merge_sort(data,N) ;
     
    clock_t T1 = clock() ;
    if (countSorted(A) != N)
        cout << "logical error in sorting routine!" << endl ;
    else
        cout << type << " " << N << " " << (T1-T0) << endl ; 
        
    if (N < 50) print(A) ;
    dispose(A) ;
    delete [] data ;
    
cout << "\n\n";
system("pause");
return 0;
}

[raptr_dflo]

The way to determine which function is failing, is to split them out into separate steps, and print the results. You already have a recursive print() function, so call build(A, N) and call print() on the list it returns. If that looks OK, then call split(L, p, q), and call print() on p, and again on q. If that looks OK, then the problem is probably merge(). This is a -very- standard debugging technique, and works just as well for expert programmers as it does for beginners.

Your build() function looks OK, though since you have it embedded in your merge_sort() function, you are determining the amount of time it takes to build the linked list, along with the amount of time to sort it (using merge_sort). You may want to build the list first, and then pass the list into the sort-method of your choice, so you're timing just the sort....

Then, your split() function looks broken to me. Why are you allocating new cells in there? You should just be determining how to make two lists out of one. I said previously that there are several ways to do it. Pick a method that makes sense to you, then draw on paper how it should work: draw a short linked-list as boxes connected by arrows, with a number in each box. What has to change about that picture for there to be two linked lists instead of one? How do you code that change?

Also, don't call count(L) inside the expression for your while() loop, or you're re-computing the same length over and over. Compute it once and save the value, and then re-use that value in your while() loop.