/* Sandra N. Kardaras-Flick LINKED LISTS 03/18/05 With the use of rand()%101, a program which generates 25 random integers from 0 to 100 in order, and creates a linked list out of them. The program should calculate the sum, and the average, of the elements. */ #include #include #include /*Global Declarations */ /* define a new type KEY_TYPE as a synonym for int */ typedef int KEY_TYPE; /* This is a structure to hold the data in the list ; we can define it */ /* however we want. In this case since KEY_TYPE is defined as an int */ /* the DATA struct just contains an int */ /* each DATA struct stores one data item to be stored in the list */ typedef struct { KEY_TYPE key; /* Other data could go here */ } DATA; /* This structure contains one DATA item, and a pointer to the next NODE */ /* Each NODE points to the next one in the list. The last NODE has a */ /* NULL pointer for its link to indicate that it is the end of the list */ typedef struct nodeTag { DATA data; struct nodeTag *link; } NODE; /*Prototype Declarations */ void printList (NODE * pList); void printSumAndAvg (NODE * pList); void freeList (NODE * pList); int main (void) { /*Local Definitions */ int num; NODE *pList = NULL; /* pointer to start of the list */ NODE *pNew; /* pointer to use when creating a new node */ NODE *pRear = NULL; /* pointer to end of the list */ int i; /* loop counter */ /* --- GENERATE 25 Random INTS 1-100 AND PUT THEM IN LINKED LIST --- */ /* This is pretty much the exact same code as above; the only difference */ /* is that we generate random ints rather than getting them from the */ /* keyboard -- adding them to the list is exactly the same as above */ /* Insert first node into linked list */ /* EXPLANATION OF RAND () It is normal for rand () to always generate the same random numbers, but an oddity of how rand() works. Rand () is designed to always give the same 'psuedorandom' numbers unless you 'seed' it with a random seed. This is done with the srand() function -- if you add this line: srand ( time(NULL) ); in your main() method, somewhere at the start of your program, you'll get a different sequence every time -- you only need to call this once in your program, before the first time you call rand(). This takes the current time in milliseconds and seeds the random number generator with it so it will be different every time you run the program. You may have to #include at the top with the other includes, for this to compile. It seems odd but it turns out it is useful sometimes for debugging and testing to be able to get the same sequence of random numbers as you did last time. */ freeList(pList); /* free the memory we malloc'd for the Nodes */ pList = NULL; /* set the list to be empty again */ srand ( time(NULL) ); /* seed rand with a random seed to avoid pseudorandom number generation. Takes current time in milliseconds. */ for (i=0; i < 25; i++) /* we'll loop 25 times */ { /* create a NODE by calling malloc to get the memory */ /* store a pointer to the new NODE in the pointer variable pNew */ pNew = (NODE *) malloc (sizeof (NODE)); /* if pNew is NULL that means the malloc failed */ if (!pNew) { printf ("\aCan not allocate node.\n"); return 100; } /* if */ /* set num to a random number between 0 and 100 */ num = rand() % 101; /* store the int num in the key field of the DATA struct */ pNew->data.key = num; /* set the pNew link to NULL since it will be added at the end */ /* of the list -- there will be no node after it */ pNew->link = NULL; /* pList is a pointer to the start of the list. If it is NULL that */ /* means we just allocated the first node, so we'll set pList to */ /* point to our new node. We'll also set pRear to point to it since*/ /* at this point there will only be one node in the list */ if (pList == NULL) /* first node */ pList = pRear = pNew; else /* other nodes */ { /* this is not the first node. So we add it onto the end of the */ /* list by setting the current last Node's link to point to */ /* the new node. The current last node (end of the list) is */ /* pointed to by pRear */ pRear->link = pNew; /* now the new Node is the new end of the list so we set pRear */ /* to point to it */ pRear = pNew; } /* else */ } /* while */ /* we have generated a linked list of 25 random ints */ printf("\n\nLinked list of 25 random ints from 0-100 generated.\n\n"); /* print it out */ printList (pList); /* print sum and average */ printSumAndAvg(pList); return 0; }/* main */ /*================== printList ===================== Traverse and print the keys from a linked list Pre: pList is a valid linked list Post: Keys of list have been printed */ void printList (NODE *pList) { /*Local Definitions */ /* pWalker is a pointer to a NODE. We will start it off pointing at the */ /* first NODE and print that node's data. THen we will change it to */ /* point to the node pointed to by the first Node's link pointer and */ /* print that. For each Node in the list, we will print the node's data */ /* and then move up one link in the list by setting pWalker to that */ /* node's link pointer */ NODE *pWalker; int lineCount = 0; /*Statements */ pWalker = pList; /* start at the first node in the list */ printf ("\nList contains:\n"); while (pWalker) /* stop when pWalker = NULL; there's no more list then */ { if (++lineCount > 10) /* for spacing - add a new line after every 10 ints */ { lineCount = 1; printf ("\n"); } /* if */ /* print the int stored in the Node pointed to by pWalker */ printf ("%d => ", pWalker->data.key); /* move pWalker to point to the next node in the list */ pWalker = pWalker->link; } /* while */ printf ("\n\n"); return; }/* printList */ /* print the sum and average of all the ints in this list */ /* just like in printList we'll walk the list but instead */ /* printing the int for each node we'll add it to our sum */ void printSumAndAvg (NODE *pList) { NODE *pWalker; /* pointer to the next node in the list */ int sum; /* total of all the ints in the list */ int count; /* number of ints in the list */ float avg; /* average */ pWalker = pList; /* start at the first node in the list */ sum = 0; /* start the sum at 0 */ count = 0; /* ditto for count */ while (pWalker) /* stop when pWalker = NULL; there's no more list then */ { /* add this node's int to the sum and add one to count*/ sum += pWalker->data.key; count++; /* move pWalker to point to the next node in the list */ pWalker = pWalker->link; } /* while */ /* compute the average */ avg = (float) sum / count; /* print the sum and average */ printf("Sum = %d Average = %.2f\n", sum, avg); return; }/* printSumAndAvg */ /* free the memory of this list */ /* just like in printList we'll walk the list - but here we'll call free() */ /* for each Node to free it's memory */ void freeList (NODE *pList) { NODE *pWalker; /* pointer to the next node in the list */ NODE *link; /* pointer to save the link to following NODE */ pWalker = pList; /* start at the first node in the list */ while (pWalker) /* stop when pWalker = NULL; there's no more list then */ { /* save the pointer to the next Node -- since we're freeing the */ /* memory of this one we won't be able to use its link pointer */ link = pWalker->link; /* free the node pointed to by pWalker */ free(pWalker); /* move pWalker to point to the next node in the list */ pWalker = link; } /* while */ return; }/* freeList */