C++ programming Can you solve the problem that linked list part doesn\'t compile
ID: 3839198 • Letter: C
Question
C++ programming
Can you solve the problem that linked list part doesn't compile;
the array part is broken as you have 20000 elements,
and it's trying to put a number in at 20527 so it crashes.
/*
Storage Problem:
Time the creation of an array that holds two million integer random values between -10,000 and 10,000, sorted.
Print out the middle 200 values, 20 values per line.
Time the creation of a vector that holds two million integer random values between -10,000 and 10,000, sorted.
Print out the middle 200 values, 20 values per line.
Finally, time the creation of a linked list that holds two million integer random values between -10,000 and 10,000, sorted. Print out the middle 200 values, 20 values per line.
Print out the times it took to create each type of thing, labeled appropriately.
The values in each should be entered into the array / vector / linked list sorted.
*/
#include <iostream>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
//The functions to perform linked list insertion
//linked list lNode
struct node
{
int number;
node* link;
};
node* SortedMerge(node* a, node* b);
void FrontBackSplit(node* source, node** frontRef, node** backRef);
void MergeSort(node** headRef) //merge sort for linked list
{
node* head = *headRef;
node* a;
node* b;
/* Base case -- length 0 or 1 */
if ((head == NULL) || (head->link == NULL))
{
return;
}
/* Split head into 'a' and 'b' sublists */
FrontBackSplit(head, &a, &b);
/* Recursively sort the sublists */
MergeSort(&a);
MergeSort(&b);
/* answer = merge the two sorted lists together */
*headRef = SortedMerge(a, b);
}
void FrontBackSplit(node* source, node** frontRef, node** backRef)
{
node* fast;
node* slow;
if (source == NULL || source->link == NULL)
{
/* length < 2 cases */
*frontRef = source;
*backRef = NULL;
}
else
{
slow = source;
fast = source->link;
/* Advance 'fast' two nodes, and advance 'slow' one node */
while (fast != NULL)
{
fast = fast->link;
if (fast != NULL)
{
slow = slow->link;
fast = fast->link;
}
}
/* 'slow' is before the midpoint in the list, so split it in two
at that point. */
*frontRef = source;
*backRef = slow->link;
slow->link = NULL;
}
}
node* SortedMerge(node* a, node* b)
{
node* result = NULL;
/* Base cases */
if (a == NULL)
return(b);
else if (b == NULL)
return(a);
/* Pick either a or b, and recur */
if (a->number <= b->number)
{
result = a;
result->link = SortedMerge(a->link, b);
}
else
{
result = b;
result->link = SortedMerge(a, b->link);
}
return(result);
}
void push(node** head_ref, int new_data)
{
/* allocate node */
node* new_node = new node;
/* put in the data */
new_node->number = new_data;
/* link the old list off the new node */
new_node->link = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
void sortedInsert(struct lNode** pointhead, struct lNode* nodeNew)
{
struct lNode* head;
if (*pointhead == NULL || (*pointhead)->number >= nodeNew->number)
{
nodeNew->link = *pointhead;
*pointhead = nodeNew;
}
else
{
head = *pointhead;
while (head->link != NULL &&
head->link->number < nodeNew->number)
{
head = head->link;
}
nodeNew->link = head->link;
head->link = nodeNew;
}
}
node *newNode(int newRandom)
{
node* nodeNew = new node;
nodeNew->number = newRandom;
nodeNew->link = NULL;
return nodeNew;
}
void printNode(node *curNode)
{
node *vtem = curNode;
int x = 0;
while (x != 9900)
{
vtem = vtem->link;
x++;
}
int line = 0;
while (vtem != NULL && x != 10100)
{
if (line % 20 == 0)
cout << endl;
line++;
cout << vtem->number << " ";
vtem = vtem->link;
x++;
}
}
//The main
int main()
{
cout << "ARRAY" << endl;
clock_t start, end;
start = clock();
int Numb, vi, vj, vk, numArray[20000], count;
int max = 10000;
int min = -10000;
srand(time(NULL));
//change the number to 2000000
for (vi = 0; vi<2000000; vi++)
{
Numb = rand()%((max - min) + 1) + min;
Numb = rand() % 20000 - 10000;
vj = 0;
while (numArray[vj] )
{
vj = vj + 1;
}
for (vk = vi; vk>vj; vk--)
{
numArray[vk + 1] = numArray[vk];
}
numArray[vj] = Numb;
}
for (vi = 0; vi<20000; vi++)
{
Numb = rand() % ((max - min) + 1) + min;
numArray[vi] = Numb;
}
sort(numArray, numArray + 20000);
int line = 0;
for (vi = 9900; vi<10100; vi++)
{
if (line % 20 == 0)
cout << endl;
cout << numArray[vi] << " ";
line++;
}
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
cout << " For array the time taken = " << cpu_time_used << endl;
cout << "Vector";
start = clock();
vector <int> numvect(20000);
for (vi = 0; vi<2000000; vi++)
{
Numb = rand()%((max - min) + 1) + min;
Numb = rand() % 20000 - 10000;
vj = 0;
while (numvect[vj])
{
vj = vj + 1;
}
for (vk = vi - 1; vk>vj; vk--)
{
numvect[vk + 1] = numvect[vk];
}
numvect[vj] = Numb;
}
for (vi = 0; vi<20000; vi++)
{
Numb = rand() % ((max - min) + 1) + min;
numvect[vi] = Numb;
}
sort(numvect.begin(), numvect.end());
line = 0;
for (vi = 9900; vi<10100; vi++)
{
if (line % 20 == 0)
cout << endl;
cout << numvect[vi] << " ";
line++;
}
end = clock();
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
cout << " For vector the time taken = " << cpu_time_used << endl;
cout << " Linked list" << endl;
start = clock();
struct node* head = NULL;
Numb = rand()%((max - min) + 1) + min;
Numb = rand() % 20000 - 10000;
struct node *nodeNew = newNode(Numb);
for (vi = 0; vi<20000; vi++)
{
Numb = rand() % ((max - min) + 1) + min;
push(&head, Numb);
Numb = rand() % 20000 - 10000;
nodeNew = newNode(Numb);
}
MergeSort(&head);
printNode(head);
end = clock();
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
cout << " For Linked list the time taken = " << cpu_time_used << endl;
system("pause");
return 0;
Explanation / Answer
#include <iostream>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct node
{
int number;
node* link;
};
node* SortedMerge(node* a, node* b);
void FrontBackSplit(node* source, node** frontRef, node** backRef);
void MergeSort(node** headRef)
{
node* head = *headRef;
node* a;
node* b;
if ((head == NULL) || (head->link == NULL))
{
return;
}
FrontBackSplit(head, &a, &b);
MergeSort(&a);
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
void FrontBackSplit(node* source, node** frontRef, node** backRef)
{
node* fast;
node* slow;
if (source == NULL || source->link == NULL)
{
*frontRef = source;
*backRef = NULL;
}
else
{
slow = source;
fast = source->link;
while (fast != NULL)
{
fast = fast->link;
if (fast != NULL)
{
slow = slow->link;
fast = fast->link;
}
}
*frontRef = source;
*backRef = slow->link;
slow->link = NULL;
}
}
node* SortedMerge(node* a, node* b)
{
node* result = NULL;
if (a == NULL)
return(b);
else if (b == NULL)
return(a);
if (a->number <= b->number)
{
result = a;
result->link = SortedMerge(a->link, b);
}
else
{
result = b;
result->link = SortedMerge(a, b->link);
}
return(result);
}
void push(node** head_ref, int new_data)
{
node* new_node = new node;
new_node->number = new_data;
new_node->link = (*head_ref);
(*head_ref) = new_node;
}
void sortedInsert(struct lNode** pointhead, struct lNode* nodeNew)
{
struct lNode* head;
if (*pointhead == NULL || (*pointhead)->number >= nodeNew->number)
{
nodeNew->link = *pointhead;
*pointhead = nodeNew;
}
else
{
head = *pointhead;
while (head->link != NULL &&
head->link->number < nodeNew->number)
{
head = head->link;
}
nodeNew->link = head->link;
head->link = nodeNew;
}
}
node *newNode(int newRandom)
{
node* nodeNew = new node;
nodeNew->number = newRandom;
nodeNew->link = NULL;
return nodeNew;
}
void printNode(node *curNode)
{
node *vtem = curNode;
int x = 0;
while (x != 9900)
{
vtem = vtem->link;
x++;
}
int line = 0;
while (vtem != NULL && x != 10100)
{
if (line % 20 == 0)
cout << endl;
line++;
cout << vtem->number << " ";
vtem = vtem->link;
x++;
}
}
int main()
{
cout << "ARRAY" << endl;
clock_t start, end;
start = clock();
int Numb, vi, vj, vk, numArray[20000], count;
int max = 10000;
int min = -10000;
srand(time(NULL));
for (vi = 0; vi<2000000; vi++)
{
Numb = rand()%((max - min) + 1) + min;
Numb = rand() % 20000 - 10000;
vj = 0;
while (numArray[vj] )
{
vj = vj + 1;
}
for (vk = vi; vk>vj; vk--)
{
numArray[vk + 1] = numArray[vk];
}
numArray[vj] = Numb;
}
for (vi = 0; vi<20000; vi++)
{
Numb = rand() % ((max - min) + 1) + min;
numArray[vi] = Numb;
}
sort(numArray, numArray + 20000);
int line = 0;
for (vi = 9900; vi<10100; vi++)
{
if (line % 20 == 0)
cout << endl;
cout << numArray[vi] << " ";
line++;
}
end = clock();
double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
cout << " For array the time taken = " << cpu_time_used << endl;
cout << "Vector";
start = clock();
vector <int> numvect(20000);
for (vi = 0; vi<2000000; vi++)
{
Numb = rand()%((max - min) + 1) + min;
Numb = rand() % 20000 - 10000;
vj = 0;
while (numvect[vj])
{
vj = vj + 1;
}
for (vk = vi - 1; vk>vj; vk--)
{
numvect[vk + 1] = numvect[vk];
}
numvect[vj] = Numb;
}
for (vi = 0; vi<20000; vi++)
{
Numb = rand() % ((max - min) + 1) + min;
numvect[vi] = Numb;
}
sort(numvect.begin(), numvect.end());
line = 0;
for (vi = 9900; vi<10100; vi++)
{
if (line % 20 == 0)
cout << endl;
cout << numvect[vi] << " ";
line++;
}
end = clock();
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
cout << " For vector the time taken = " << cpu_time_used << endl;
cout << " Linked list" << endl;
start = clock();
struct node* head = NULL;
Numb = rand()%((max - min) + 1) + min;
Numb = rand() % 20000 - 10000;
struct node *nodeNew = newNode(Numb);
for (vi = 0; vi<20000; vi++)
{
Numb = rand() % ((max - min) + 1) + min;
push(&head, Numb);
Numb = rand() % 20000 - 10000;
nodeNew = newNode(Numb);
}
MergeSort(&head);
printNode(head);
end = clock();
cpu_time_used = ((double)(end - start))
cout << " For Linked list the time taken = " << cpu_time_used << endl;
system("pause");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.