ZuoTi.Pro
Question

Trying to figure out what needs to be in the headers.h file. I have written the...

Trying to figure out what needs to be in the headers.h file. I have written the print function.

Qualities in header file

  • main() needs insertionSort() and mergeSortWrapper()
  • Both insertionSort() and mergeSortWrapper() need print().

  1. Please copy-and-paste the following files (0 Points):

    insertionSort.c

    /*--------------------------------------------------------------------------*
 *----                                                                  ----*
 *----          insertionSort.c                                         ----*
 *----                                                                  ----*
 *----      This file defines a function that implements insertion      ----*
 *----  sort on a linked-list of integers.                              ----*
 *----                                                                  ----*
 *----  ----    ----    ----    ----    ----    ----    ----    ----    ----*
 *----                                                                  ----*
 *----   ----*
 *----                                                                  ----*
 *--------------------------------------------------------------------------*/

#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

    /*--------------------------------------------------------------------------*
 *----                                                                  ----*
 *----          mergeSort.c                                             ----*
 *----                                                                  ----*
 *----      This file defines a function that implements merge-sort on  ----*
 *----  a linked-list of integers.                                      ----*
 *----                                                                  ----*
 *----  ----    ----    ----    ----    ----    ----    ----    ----    ----*
 *----                                                                  ----*
 *----   ----*
 *----                                                                  ----*
 *--------------------------------------------------------------------------*/

#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);
}

  2. C programming (20 Points):

    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.h

    • Please make print() print the whole linked list.
    • For headers.h, not everything needs to be shared.
      • main() needs insertionSort() and mergeSortWrapper()
      • Both insertionSort() and mergeSortWrapper() need print().
      Otherwise, it is best not to share too much, kind of like keeping methods and members private in C++ and Java.

    headers.h

    /*--------------------------------------------------------------------------*
 *----                                                                  ----*
 *----          headers.h                                               ----*
 *----                                                                  ----*
 *----      This file declares common headers used through-out the      ----*
 *----  the singly-linked list sorting program.                         ----*
 *----                                                                  ----*
 *----  ----    ----    ----    ----    ----    ----    ----    ----    ----*
 *----                                                                  ----*
 *----  Version 1a              2020 January 5          Joseph Phillips ----*
 *----                                                                  ----*
 *--------------------------------------------------------------------------*/

#include        
#include        
#include        "Node.h"

//  YOUR CODE HERE
WHAT GOES HERE

    Node.h

    /*--------------------------------------------------------------------------*
 *----                                                                  ----*
 *----          Node.h                                                  ----*
 *----                                                                  ----*
 *----      This file declares the struct that stores an integer and    ----*
 *----  a next-pointer to implement a node in a singly-linked list.     ----*
 *----                                                                  ----*
 *----  ----    ----    ----    ----    ----    ----    ----    ----    ----*
 *----                                                                  ----*
 *----  Version 1a              2020 January 5          Joseph Phillips ----*
 *----                                                                  ----*
 *--------------------------------------------------------------------------*/

struct  Node
{
  int           value_;
  struct Node*  nextPtr_;
};

    main.c

    /*--------------------------------------------------------------------------*
 *----                                                                  ----*
 *----          main.c                                                  ----*
 *----                                                                  ----*
 *----      This file defines the main functions for a program that     ----*
 *----  sorts a linked list of randomly-generated integers.             ----*
 *----                                                                  ----*
 *----  ----    ----    ----    ----    ----    ----    ----    ----    ----*
 *----                                                                  ----*
 *----   ----*
 *----                                                                  ----*
 *--------------------------------------------------------------------------*/

#include        "headers.h"

#define         TEXT_LEN        256
#define         NUM_NUMBERS     (2*65536)

const 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 code
}


//  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?\n"
         "(1) Insertion sort\n"
         "(2) Merge sort\n"
         "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);
}
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

header.h contains all the header files your code needs.

Here are some header files your code needs:

#include <stdio.h> // for printf(), sizeof(), fgets()

#include <stdlib.h> // for rand(), malloc(), free(), strtol()

#include "Node.h"

#include "insertionSort.c" // these two header files are needed by the main function for various functions

#include "mergeSort.c"

Hope this helps.

Please rate the answer if you like it.

Do leave a comment.An suggestion/query is much appreciated.

0 0
Add a comment
Know the answer?
Add Answer to:
Trying to figure out what needs to be in the headers.h file. I have written the...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • #include <iostream> using namespace std; struct ListNode { float value; ListNode *next; }; ...

    #include <iostream> using namespace std; struct ListNode { float value; ListNode *next; }; ListNode *head; class LinkedList { public: int insertNode(float num); void deleteNode(float num); void destroyList(); void displayList(); LinkedList(void) {head = NULL;} ~LinkedList(void) {destroyList();} }; int LinkedList::insertNode(float num) { struct ListNode *newNode, *nodePtr = head, *prevNodePtr = NULL; newNode = new ListNode; if(newNode == NULL) { cout << "Error allocating memory for new list member!\n"; return 1; } newNode->value = num; newNode->next = NULL; if(head==NULL) { cout << "List...

  • Programming in C: I am trying to modify this linked list to be doubly linked list....

    Programming in C: I am trying to modify this linked list to be doubly linked list. I’m also trying to add a print in reverse function. I’m really struggling with how to change the insert function to doubly link the nodes without effecting the alphabetical sorting mechanism. Example of desired output: Enter your choice: 1 to insert an element into the list. 2 to delete an element from the list. 3 to end. ? 1 Enter a character: a The...

  • In Java You may add any classes or methods to the following as you see fit in order to complete t...

    In Java You may add any classes or methods to the following as you see fit in order to complete the given tasks. Modify the LinkedList (or DoubleLinkedList) class and add a method append. append should take another LinkedList (DoubleLinkedList) as input and append that list to the end of this list. The append method should work by doing a few "arrow" adjustments on the boxes and it should not loop through the input list to add elements one at...

  • can someone please double check my code here are the requirements please help me fulfill the...

    can someone please double check my code here are the requirements please help me fulfill the requirements Using the material in the textbook (NumberList) as a sample, design your own dynamic linked list class (using pointers) to hold a series of capital letters. The class should have the following member functions: append, insert (at a specific position, return -1 if that position doesn't exist), delete (at a specific position, return -1 if that position doesn't exist), print, reverse (which rearranges...

  • Am Specification For this assignment, you will write a multi-file C program to define, implement ...

    Must be written and C, and compile with MinGW. Thank you! am Specification For this assignment, you will write a multi-file C program to define, implement and use a dynamic linked lists. Please refer to Lab 07 for the definition of a basic linked list. In this assignment you will need to use the basic ideas of a node and of a linked list of nodes to implement a suit of functions which can be used to create and maintain...

  • My question is pretty simple, I just want to know how to call my operator== function...

    My question is pretty simple, I just want to know how to call my operator== function in Stack.cpp using a list function. Here is what I meant. This is my Stack.h file: class Stack { public:    /**constructors and destructors*/    Stack();    Stack(const Stack &S);    ~Stack();    void pop();    void push(int data);    bool operator==(const Stack &S); [ .......] private:    List<int> stack; }; Here is my List.h file: template<class listitem> class List { private:    struct...

  • Linkedlist implementation in C++ The below code I have written is almost done, I only need...

    Linkedlist implementation in C++ The below code I have written is almost done, I only need help to write the definition for delete_last() functio​n. ​ Language C++ // LinkedList.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <string> #include <iostream> using namespace std; struct Node { int dataItem;//Our link list stores integers Node *next;//this is a Node pointer that will be areference to next node in the list }; class LinkedList { private: Node *first;...

  • Using C, I need help debugging this program. I have a few error messages that I'm...

    Using C, I need help debugging this program. I have a few error messages that I'm not sure how to fix. Here is the code I have: /* * C Program to Print a Linked List in Reverse Order */ #include <stdio.h> #include <stdlib.h> struct node { int num; struct node *next; }; int main() { struct node *p = NULL; struct node_occur *head = NULL; int n; printf("Enter data into the list\n"); create(&p); printf("Displaying the nodes in the list:\n");...

  • Requirements: Finish all the functions which have been declared inside the hpp file. Details: st...

    Requirements: Finish all the functions which have been declared inside the hpp file. Details: string toString(void) const Return a visible list using '->' to show the linked relation which is a string like: 1->2->3->4->5->NULL void insert(int position, const int& data) Add an element at the given position: example0: 1->3->4->5->NULL instert(1, 2); 1->2->3->4->5->NULL example1: NULL insert(0, 1) 1->NULL void list::erase(int position) Erase the element at the given position 1->2->3->4->5->NULL erase(0) 2->3->4->5->NULL //main.cpp #include <iostream> #include <string> #include "SimpleList.hpp" using std::cin; using...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT