Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Only need help with the Header file These two files need a main() to run their functions insertionSort() and mergeSortWrapper(). Then all three C files
Only need help with the Header file
These two files need a main() to run their functions insertionSort() and mergeSortWrapper(). Then all three C files need a header file to inform them of what the others have that they need, including Node.h which defines the data-structure. Please finish both the main.c and headers.
- For headers.h, not everything needs to be shared.
- main() needs insertionSort() and mergeSortWrapper()
- Both insertionSort() and mergeSortWrapper() need print().
headers.h
#include#include #include "Node.h" // WHAT CODE GOES HERE
Node.h
struct Node { int value_; struct Node* nextPtr_; };
main.c
#include "headers.h" #define TEXT_LEN 256 #define NUM_NUMBERS (2*65536) int numNumbers = NUM_NUMBERS; // PURPOSE: To create and return the address of the first node of a linked // list of 'length' struct Node instances, each with a randomly-generated // integer in its 'value_' member variable. struct Node* createList (int length ) { if (length == 0) { return(NULL); } struct Node* startPtr = (struct Node*)malloc(sizeof(struct Node)); struct Node* endPtr = startPtr; startPtr->value_ = rand() % 4096; startPtr->nextPtr_ = NULL; for (length--; length > 0; length--) { endPtr->nextPtr_ = (struct Node*)malloc(sizeof(struct Node)); endPtr->nextPtr_->value_ = rand() % 4096; endPtr->nextPtr_->nextPtr_ = NULL; endPtr = endPtr->nextPtr_; } return(startPtr); } // PURPOSE: To print integer values in the linked list pointed to by // 'nodePtr'. No return value. void print (const struct Node* nodePtr ) { // I've already written this print function } // PURPOSE: To 'free()' the 'struct Node' instances of the linked list // pointed to by 'nodePtr'. No return value. void freeList (struct Node* nodePtr ) { struct Node* nextPtr; for ( ; nodePtr != NULL; nodePtr = nextPtr) { nextPtr = nodePtr->nextPtr_; free(nodePtr); } } // PURPOSE: To run this program. Ignores command line arguments. Returns // 'EXIT_SUCCESS' to OS. int main () { int choice; struct Node* nodePtr = createList(numNumbers); print(nodePtr); do { char text[TEXT_LEN]; printf ("How do you want to sort %d numbers? " "(1) Insertion sort " "(2) Merge sort " "Your choice (1 or 2)? ", NUM_NUMBERS ); fgets(text,TEXT_LEN,stdin); choice = strtol(text,NULL,10); } while ( (choice < 1) || (choice > 2) ); switch (choice) { case 1 : nodePtr = insertionSort(nodePtr); break; case 2 : nodePtr = mergeSortWrapper(nodePtr); break; } freeList(nodePtr); return(EXIT_SUCCESS); }
insertionSort.c
#include "headers.h" // PURPOSE: To sort the linked-list of nodes pointed to by 'nodePtr' using // the insertion sort algorithm. Returns the first node of the sorted // list. struct Node* insertionSort (struct Node* nodePtr ) { struct Node* startPtr = NULL; struct Node* endPtr = NULL; struct Node* lowestPtr; struct Node* lowestPrevPtr; while (nodePtr != NULL) { struct Node* prevPtr; struct Node* run; lowestPrevPtr = NULL; lowestPtr = nodePtr; for (prevPtr = nodePtr, run = nodePtr->nextPtr_; run != NULL; prevPtr = run, run = run->nextPtr_ ) { if (lowestPtr->value_ > run->value_) { lowestPtr = run; lowestPrevPtr = prevPtr; } } if (lowestPrevPtr == NULL) { if (startPtr == NULL) { startPtr = endPtr = lowestPtr; } else { endPtr->nextPtr_ = lowestPtr; endPtr = endPtr->nextPtr_; } nodePtr = nodePtr->nextPtr_; endPtr->nextPtr_ = NULL; } else { if (startPtr == NULL) { startPtr = endPtr = lowestPtr; } else { endPtr->nextPtr_ = lowestPtr; endPtr = endPtr->nextPtr_; } lowestPrevPtr->nextPtr_ = lowestPtr->nextPtr_; endPtr->nextPtr_ = NULL; } } print(startPtr); return(startPtr); }
mergeSort.c
#include "headers.h" // PURPOSE: To sort the linked-list of nodes pointed to by 'nodePtr' using // the merge sort algorithm. Returns the first node of the sorted list. struct Node* mergeSort (struct Node* nodePtr ) { if ( (nodePtr == NULL) || (nodePtr->nextPtr_ == NULL) ) { return(nodePtr); } struct Node* run; struct Node* run2; struct Node* lastPtr = NULL; for ( run = run2 = nodePtr; (run2 != NULL) && (run2->nextPtr_ != NULL); lastPtr = run, run = run->nextPtr_, run2 = run2->nextPtr_->nextPtr_ ); lastPtr->nextPtr_ = NULL; run2 = mergeSort(run); run = mergeSort(nodePtr); nodePtr = NULL; lastPtr = NULL; while ( (run != NULL) && (run2 != NULL) ) { if (run->value_ < run2->value_) { if (nodePtr == NULL) { nodePtr = lastPtr = run; } else { lastPtr = lastPtr->nextPtr_ = run; } run = run->nextPtr_; } else { if (nodePtr == NULL) { nodePtr = lastPtr = run2; } else { lastPtr = lastPtr->nextPtr_ = run2; } run2 = run2->nextPtr_; } } if (run == NULL) { if (lastPtr == NULL) { nodePtr = run2; } else { lastPtr->nextPtr_ = run2; } } else { if (lastPtr == NULL) { nodePtr = run; } else { lastPtr->nextPtr_ = run; } } return(nodePtr); } struct Node* mergeSortWrapper(struct Node* nodePtr ) { nodePtr = mergeSort(nodePtr); print(nodePtr); return(nodePtr); }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started