I really need help for this lab. First, I wonder if my definition about *head, *
ID: 3571505 • Letter: I
Question
I really need help for this lab. First, I wonder if my definition about *head, *add, *add->next, *insert are correct or not. And I relly stuck at insertionsort function.
#include<iostream>
using namespace std;
/*
Purpose of these pointers:
add: pointer that move though the list
head: is used to point to the first item in the list
add->next: pointer that pointer to the next current pointer
insert: is used to insert a node in the list.
*/
class NumberList
{
private:
struct ListNode
{
double value;
struct ListNode *next;
};
ListNode *head;
public:
NumberList()
{
head = new ListNode;
head->value = 0;
head->next = NULL;
}
void appendNode(double);
void InsertionSort();
void displayList() const;
};
void NumberList::appendNode(double num)
{
ListNode *newNode;
ListNode *nodePtr;
newNode = new ListNode;
newNode->value = num;
newNode->next = nullptr;
if (!head)
head = newNode;
else
{
nodePtr = head;
while (nodePtr->next)
nodePtr = nodePtr->next;
nodePtr->next = newNode;
}
}
void NumberList::displayList() const
{
ListNode *nodePtr;
nodePtr = head;
while (nodePtr)
{
cout << nodePtr->value << endl;
nodePtr = nodePtr->next;
}
}
void NumberList::InsertionSort()
{
NumberList temp;
ListNode *add; //nodeptr
ListNode *addNext; //nextnode
ListNode *insert;
add = head->next; //The first node to be sorted is the one after the head node (which has the value 0)
while (!add)
{
// Replace this comment with one line of code to assign a value to addNext
//Replace this comment with one line of code to assign a value to insert
while ( /*stop when you are at the end of the temp list*/)
{
if (/* use the > operator to determine when to break out of this inner while loop*/)
{
break;
}
// Replace this comment with one line of code to assign a value to insert
}
// Replace this comment with one line of code to assign a value to add->next
// Replace this comment with one line of code to assign a value to insert->next
// Replace this comment with one line of code to assign a value to add
}
delete head;
// Replace this comment with one line of code to assign a value to head
temp.head = NULL;
}
int main()
{
NumberList example;
example.appendNode(5);
example.appendNode(2);
example.appendNode(4);
example.appendNode(7);
example.appendNode(3);
example.appendNode(1);
example.appendNode(6);
cout << "In original order: " << endl;
example.displayList();
cout << " In sorted order: " << endl;
example.InsertionSort();
example.displayList();
system("pause");
return 0;
}
Explanation / Answer
#include<iostream>
struct ListN {
int val;
ListN *next;
ListN(int x) : val(x), next(NULL) {}
};
ListN * Add(ListN *head, int d)
{
ListN *temp = new ListN(d);
temp->next = head;
return temp;
}
void Print(ListN *head)
{
while( head )
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
ListN * SortedInsert(ListN * head, ListN *newNode )
{
if( head == NULL || head->val >= newNode->val)
{
newNode->next = head;
head = newNode;
return head;
}
ListN *ptr = head;
ListN *prev = NULL;
while ( ptr != NULL && ptr->val < newNode->val )
{
prev = ptr;
ptr = ptr->next;
}
newNode->next = ptr;
prev->next = newNode;
return head;
}
ListN* InsertionSort(ListN *head)
{
if( !head || !head->next )
return head;
ListN * ptr = head->next;
ListN * result = head;
result->next = NULL;
while ( ptr )
{
ListN *temp = ptr;
ptr = ptr->next;
result = SortedInsert(result,temp);
}
return result;
}
int main()
{
ListN *head = new ListN(9);
head = Add(head,3);
head = Add(head,5);
head = Add(head,1);
head = Add(head,6);
head = Add(head,4);
head = Add(head,2);
head = InsertionSort(head);
Print(head);
return 0;
}
#include<iostream>
struct ListN {
int val;
ListN *next;
ListN(int x) : val(x), next(NULL) {}
};
ListN * Add(ListN *head, int d)
{
ListN *temp = new ListN(d);
temp->next = head;
return temp;
}
void Print(ListN *head)
{
while( head )
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
ListN * SortedInsert(ListN * head, ListN *newNode )
{
if( head == NULL || head->val >= newNode->val)
{
newNode->next = head;
head = newNode;
return head;
}
ListN *ptr = head;
ListN *prev = NULL;
while ( ptr != NULL && ptr->val < newNode->val )
{
prev = ptr;
ptr = ptr->next;
}
newNode->next = ptr;
prev->next = newNode;
return head;
}
ListN* InsertionSort(ListN *head)
{
if( !head || !head->next )
return head;
ListN * ptr = head->next;
ListN * result = head;
result->next = NULL;
while ( ptr )
{
ListN *temp = ptr;
ptr = ptr->next;
result = SortedInsert(result,temp);
}
return result;
}
int main()
{
ListN *head = new ListN(9);
head = Add(head,3);
head = Add(head,5);
head = Add(head,1);
head = Add(head,6);
head = Add(head,4);
head = Add(head,2);
head = InsertionSort(head);
Print(head);
return 0;
}