C++ Suggested point values are marked in parentheses. In all questions that invo

Question

C++

Suggested point values are marked in parentheses. In all questions that involve writing methods, be sure to think of whether method arguments and return values should be references to const data, whether or not the method should be const, etc.

(4) Write a code fragment that will insert newNode at the rear of a non-empty list.

(4) Write a code fragment that will insert newNode into the list after the node pointed to by current.

(4) Write a recursive method that will return the size of the list. The method should take a pointer to an Node<T> and return an int. When the method is initially called, it will be passed the list's head pointer.

(4) Write a non-recursive method that will return the size of the list. The method should take no arguments and return an int.

(2) Declare a pointer to a function that returns a bool and takes two double arguments.

(4) Rewrite the contents of the following array once the array has been partitioned by the quicksort partition code used on Assignment 8.

Explanation / Answer

(4) Write a code fragment that will insert newNode at the rear of a non-empty list.

(4) Write a code fragment that will insert newNode into the list after the node pointed to by current.

(4) Write a recursive method that will return the size of the list. The method should take a pointer to an Node<T> and return an int. When the method is initially called, it will be passed the list's head pointer.

(4) Write a non-recursive method that will return the size of the list. The method should take no arguments and return an int.

Ans: code pasted below:

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

class LL{
Node *head;
Node *curr;
public:
void insert_newnode_atend(Node* n){
Node *temp = head;
while(temp->next != nullptr) temp = temp->next;
temp->next = n;
n->next = nullptr;
}
void insert_newnode_aftercurr(Node* n){
Node *temp = curr->next;
temp->next = n;
n->next = temp;
}
int get_size(){
int lsize = 0;
Node *temp = head;
while(temp->next != nullptr){
temp = temp->next;
lsize++;
}
return lsize;
}
int get_size_recursive(Node* n, int running_size){
if (n->next == nullptr) return running_size;
return get_size_recursive(n->next, ++running_size);
}
};

int main(){
//bool (*foofunction)(double a, double b);
return 0;
}

(2) Declare a pointer to a function that returns a bool and takes two double arguments.

Ans: bool (*foofunction)(double a, double b);

(4) Rewrite the contents of the following array once the array has been partitioned by the quicksort partition code used on Assignment 8.

Ans:

In the first call to partition function for this array above, Array would be re written as

26 10 18 28 67 54 41 30.

Chech the code below:

/* C implementation QuickSort */
#include<stdio.h>

/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n ");
}

// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
printArray(arr, 8);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

// Driver program to test above functions
int main()
{
int arr[] = {26,10, 67, 30, 18, 54, 41, 28};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: n");
printArray(arr, n);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.