Thread: linked list problem

Okay well let me first post the dam code

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 10

struct data{
       int num;
       struct data *nextPtr;
       };

typedef struct data dataNode;
typedef dataNode *DataNodePtr;

void rando ( DataNodePtr *, int );
void printlist( DataNodePtr );

int main(void)
{
 int number, cnt =0;
 DataNodePtr startPtr = NULL;

 srand(time(NULL));

 while ( ++cnt != 25 ){
       number = 1 + rand() %100;
       rando( &startPtr, number );
       }
 printlist( startPtr );

 puts(" ");


      system("PAUSE");
      return 0;
}
void rando ( DataNodePtr *sPtr, int number )
{
 DataNodePtr newPtr, currentPtr, prevoiusPtr;

 newPtr = malloc ( sizeof( dataNode));

 if ( newPtr != NULL){
    newPtr -> num = number;
    newPtr -> nextPtr = NULL;

    prevoiusPtr = NULL;
    currentPtr = *sPtr;

    while ( currentPtr != NULL && number > currentPtr -> num ){
          prevoiusPtr = currentPtr;
          currentPtr = currentPtr -> nextPtr;
    }

    if ( prevoiusPtr == NULL ){
       newPtr -> nextPtr = *sPtr;
       *sPtr = newPtr;
    }
    else{
         prevoiusPtr -> nextPtr = newPtr;
         newPtr -> nextPtr = currentPtr;
    }
 }
 else
     printf( "No memory to store integer %d", number );
}

void printlist( DataNodePtr currentPtr )
{

 int sum=0;

 if ( currentPtr == NULL )
    printf( "List is empty" );
 else{
      while ( currentPtr != NULL ){
            printf( "%d ", currentPtr -> num);
            sum += currentPtr -> num;
            currentPtr = currentPtr -> nextPtr;

      }
      printf( "\n\nThe sum is %d", sum );
      printf("\nThe average is %f", (float)sum/25 );
 }
}

Okay first thing is if i dont put a newline escape sequence in scanf it wont get the charaters typed properly why ???. Like if i dont use the newline escape sequence and if i press a its gonna take in a and a black why???

Okay the main question is this my book says write a programm that creats a link list of 10 characters , then creats a copy of the list in reverse order..

Okay so the copy should be a linked list ??? or in a array ??? I am a bit confused

Cheers

A list is just a container. So it's really a good exercise to try both ways (though I'm sure the book is referring to a list). An even more interesting challenge would be to use both at once like this:

Assume that you have to work with singly-linked lists (no previous pointer). Thus, to copy one in reverse would be quite difficult just using another list. How could you solve the problem using an array?

Originally posted by Sebastiani

Assume that you have to work with singly-linked lists (no previous pointer). Thus, to copy one in reverse would be quite difficult just using another list. How could you solve the problem using an array?

Well since i know there will be 10 characters entered i would simply do this

Code:

char ch[10];

           while ( currentPtr != NULL ){
                    ch[counterVar] = currentPtr->ch;
                    currentPtr = currentPtr -> nextPtr;
           }

Something similar u know what i am trying to do but i dont think that what they want i guess they want me to creat another linklist and store the ones that was prevoisly done ...i guess ...well i will try it but thanks for the reply

i guess if do linked-list with node method shoule be better than array based techique

a Okay first thing is if i dont put a newline escape sequence in scanf it wont get the charaters typed properly why ???. Like if i dont use the newline escape sequence and if i press a its gonna take in a and a black why???

bOkay the main question is this my book says write a programm that creats a link list of 10 characters , then creats a copy of the list in reverse order..

Okay so the copy should be a linked list ??? or in a array ??? I am a bit confused

a: Scanf leaves the \n in the buffer. You should use a function to clear the buffer after you call scanf. Something like:

while(fgetc(stdin)!='\n');

Add that line of code, or make a wrapper for it:

#define fflushstdin while(fgetc(stdin)!='\n')

Then in your code you do:

fflushstdin;

Some of you will find the humor in this...

b: I believe they expect you to make a linked list in reverse order. This is incredibly easy. Here's an easy way:

Code:

void revlist( Node *list, Node *reved )
{
    Node *n = NULL;
    if( list != NULL )
    {
        revlist( list->next, reved );
        n = newNode( list->data );
        append( n, reved );
    }
}

Pass it the list to reverse, and a node to append to. Write your own 'newNode' function, and your own 'append' function.

Basicly this function just goes to the very end of the list, and when it gets there, it takes that data, and appends it to the new list. Then that function call returns, and the previous one appends that data.

Recursion is quite entertaining. Naturally you'll not want to use this on a circular list...

Quzah.

That is a very elegant solution Quzah. Nice work.

>Instead of spawing new thread, I tought of continuing the same old thread.
[very dry]I'm thrilled that you decided to resurrect a two year old thread.[/very dry]

>but I did not get what is he trying to do?
Reverse a list by building a new one using the tail return of the recursion.

>Any idea.
Why bother when it's easier and more clear to do it iteratively?

Code:

#include <stdio.h>
#include <stdlib.h>

struct node {
  int data;
  struct node *next;
};

struct node *reverse ( struct node *head )
{
  struct node *save;
  struct node *new_list = NULL;

  while ( head != NULL ) {
    save = head->next;
    head->next = new_list;
    new_list = head;
    head = save;
  }

  return new_list;
}

int main ( void )
{
  struct node *head = 0;
  struct node *save;
  int i;

  for ( i = 0; i < 10; i++ ) {
    struct node *n = malloc ( sizeof *n );

    if ( n == NULL )
      break;

    n->data = i;
    n->next = head;
    head = n;
  }

  head = reverse ( head );

  while ( head != NULL ) {
    save = head->next;
    printf ( "%d\n", head->data );
    free ( head );
    head = save;
  }

  return 0;
}