adding numbers to list without predefined variables
I took a look through my previous post and learned how to add the add data to the list (but only when i have the variables predefined).
What i mean by predifined is when i have made head, first,second,third and tail nodes to store them. My question is how would i create a list without the nodes predifined? Also, to get a little more specific, without using an STL, list, stack, vector, Only by using pointers. (the STL and others are a little advanced for me at the moment)
here is what i have started. My question is with the insert() function.
Code:
#include<iostream>
using namespace std;
/* 1. Write a working program.
2. This program will insert and retrieve
3. You have to define the linked list and the nodes.
4. The linked list will be sorted, you will have to remember this when doing inserts.
5. The problem defines what the insert and retrieve function headers will return and what will be passed in as parameters.
6. When writing the insert and retrieve, remember that this is recursive.
*/
struct node
{
int data;
node *next;
};
node *head = new node;
// insert a number into the pointer based sorted linked list of integers
// insert numbers into list until 0 is entered
// sorts the list
void insert()
{
node *tmp = new node;
do
{
node *tmp1=new node;
cout << "Enter the numbers to be inserted (0 to end) : " ;
cin >> tmp->data;
tmp->next=head;
head->next=new node;
}while (tmp->data !=0);
}
// Retrieve the numbers based on the sorted list
// you enter the numbers to be retrieved
// 0 to end the function
// and display the position of each in
int retrieval(int *ptr, int item)
{
// return items position or -1 if item is not in list
}
int main() {
insert();
system("pause");
return 0;
}
How do you recover the list
I seem to run into the most problems with lack of clear instructions from books.
I am trying to recover what was or i think being placed into a linked list. I know the concepts of linked list now, but with numbers not having a variable assigned to it, how are the numbers being traversed. I'd rather if someone would be so kind to post a really easy example of how to make one with just a head pointer and traverse it with a temporary pointer.
I have code from previous posts but i dont get too far.
getting the sorting function to repeat until sorted
I took some time to try to understand linked list. I split up the functions to do separate things. But now whatever i do, i cannot get m sorting function to sort correctly. can anyone see how to repeat it until its sorted?
Code:
#include <iostream>
using namespace std;
/* Recursive functions
insertion
retrieval
pointer based sorted linked list of integers
also if 0 is entered it keeps inserting until 0 is entered.
*/
struct node
{
int item;
node *next;
};
// takes in the head pointer
// item to be inserted
//building the list here
void insertion(node *&HeadPtr, int NumberToInsert) {
HeadPtr->item=NumberToInsert;
HeadPtr->next=new node;
node *tmp=HeadPtr;
tmp->next=new node;
do {
cout << "Please input the number to insert: 0 to quit ";
cin >> NumberToInsert;
tmp->item=NumberToInsert;
if (tmp->item==0)
{
tmp->next=NULL;
} //end if
else
{
tmp->next=new node;
tmp=tmp->next;
} // end else
}while (NumberToInsert!=0); //end do -while
} //end insertion
int traverser(node *&HeadPtr) {
node *tmp2=HeadPtr;
// traverse the list
while (tmp2!=NULL)
{
cout << tmp2->item << " ";
tmp2=tmp2->next;
} // end while
cout << "\n";
} // end traverser
int sort(node *&HeadPtr)
{
node *tmp=HeadPtr;
node *tmp3=tmp;
int temp;
while (tmp3->item!=0)
{
if (tmp3->item < tmp3->next->item)
{
tmp3=tmp3->next;
}
if (tmp->item = 0) //unsure
{
}
else
{
temp=tmp3->item;
tmp3->item=tmp3->next->item;
tmp3->next->item=temp;
tmp3=tmp3->next;
}
} // end while
} // end sort
int main() {
int number=-1;
node *HeadPtr=new node;
insertion(HeadPtr, number);
traverser(HeadPtr);
sort(HeadPtr);
traverser(HeadPtr);
system("pause");
return 0;
}
Recusively inserting to list
I am trying to insert numbers into this linked list recursively, but the only way that works is if the inserted number is less than the head. Can anyone exlain how i can fix my error?
Code:
#include <iostream>
using namespace std;
struct node
{
int number;
node *next;
};
class List
{
public:
List();
~List();
node *Head();
node *createnode(int);
void insert(node *, int);
void traverse(node *);
void retrieve(node *, int);
private:
node *TheHead;
};
List::List()
{
TheHead = NULL;
}
node *List::Head()
{
return TheHead;
}
List::~List() {} //Destructor
node *List::createnode(int NumberToInsert)
{
node *NewOne = new node;
NewOne ->number = NumberToInsert;
NewOne ->next = NULL;
return NewOne;
}
void List::insert(node *pInsertedHead, int ANumber)
{
node *tmp = new node; // creates a new node for the new number(ANumber) to be inserted into
tmp = createnode(ANumber); // ANumber is inserted into the new node tmp
if (TheHead ==NULL || TheHead ->number >=ANumber)
{
tmp->next = TheHead;
TheHead =tmp;
}
else
{
if(pInsertedHead !=NULL && pInsertedHead->number <= ANumber)
{
insert(pInsertedHead->next, ANumber);
}
}
}
void List ::traverse(node *CurPtr)
{
node *current = CurPtr;
while (current !=NULL)
{
cout << current ->number << " ";
current = current ->next;
}
cout << "\n";
}
void List::retrieve(node *pPointer, int XNumber) //performs retrieve on a sorted list
{
node *tmp = pPointer;
int position=0;
while (tmp != NULL && tmp->number != XNumber)
{
tmp=tmp->next;
position++;
}
if (tmp == NULL )
{
cout << XNumber << " is not in the list " << endl;
}
else if (tmp->number = XNumber )
{
cout << XNumber << " is located in position " << position << endl;
}
else
{
cout << " this is 0 " << endl;
}
}
int main()
{
List s;
s.Head();
int TheNumber=-1;
int RetrievedNumber = -1;
while (TheNumber != 0)
{
cout << "Please enter in a number: enter 0 to quit: " ;
cin >> TheNumber;
s.insert(s.Head() , TheNumber);
}
s.traverse(s.Head());
while (RetrievedNumber !=0)
{
cout << "Please enter the number to be retrieved , 0 to quit: " ;
cin >> RetrievedNumber ;
s.retrieve(s.Head(), RetrievedNumber);
}
system("pause");
return 0;
}