Hello, can I get some help in creating these two functions for single linked lis
ID: 3739761 • Letter: H
Question
Hello, can I get some help in creating these two functions for single linked list? I'm using two pointers (first, and last) to identify the first node in the list and last node in the list, and using count to know how many nodes there are in the list.
These classes have the information needed.
nodeType.h
#ifndef NODETYPE_H
#define NODETYPE_H
template <class Type>
class nodeType{
public:
Type info;
nodeType<Type> *next; //this is *link, changed it to next
//to not confuse myself
};
#endif /* NODETYPE_H */
linkedListIterator.h
#ifndef LINKEDLISTITERATOR_H_
#define LINKEDLISTITERATOR_H_
#include
#include
#include "nodeType.h"
using namespace std;
template
class linkedListIterator{
public:
linkedListIterator();
//default constructor
linkedListIterator(nodeType *ptr);
//constructor w/ parameters
Type operator*();
//function to overload dereferencing operator *
linkedListIterator operator++();
//function to overload pre-increment operator ++
bool operator==(const linkedListIterator &right) const;
//overload the equality operator
bool operator!=(const linkedListIterator &right) const;
//overload the not equal operator
private:
nodeType *current;
//pointer to point to current node in list
};
--------------------------------------
linkedListType.h
#ifndef LINKEDLISTTYPE_H_
#define LINKEDLISTTYPE_H_
#include
#include "linkedListIterator.h"
template
class linkedListType{
public:
const linkedListType &operator=
(const linkedListType &);
//overload = operator
void initializeList();
//initialize list to empty
bool isEmptyList();
//function to see if list is empty
void print() const;
//function to print data from each node
int length() const;
//function to return # of nodes in list
void destroyList();
//function to delete all nodes
Type front() const;
//function to return first element of list
Type back() const;
//function to return last element of list
virtual bool search(const Type& searchItem) const = 0;
//function to see if seatchItem is in the list
virtual void insertFirst(const Type& newItem) = 0;
//function to insert newItem at beginning of list
virtual void insertLast(const Type& newItem) = 0;
//function to insert newItem at end of list
virtual void deleteNode(const Type& deleteItem) = 0;
//function to delete a node from list
virtual void deleteSmallest() = 0;
//new function to delete smallest node in list
virtual void deleteLargest() = 0;
//new function to delete largest node in list
virtual void deleteAll(const Type& deleteItem) = 0;
//new function to delete all nodes with deleteItem
virtual void rotate() = 0;
//new function to rotate the first node to last
linkedListIterator begin();
//function to return an iterator at the beginning of list
linkedListIterator end();
//function to return an iterator one element past the last element
linkedListType();
//default constructor
linkedListType(const linkedListType &otherList);
//copy constructor
~linkedListType();
//destructor
protected:
int count;
//variable to store number of elements in list
nodeType *first;//pointer for first node
nodeType *last;//pointer for last node
private:
void copyList(const linkedListType *otherList);
//function to make a copy of otherList
};
----------------------------------------------------
for #3: I'd like to have the function work on both ordered and unordered lists. As for #4, just having a function for an unordered list is enough. TIA.
3. Find and delete all occurrences of a given info from the list. Traverse the list only once Use a pure virtual function virtual void deleteAll (const Type &deleteItem;)0; // Function to delete every deleteItem from the list // Postcondition: first points to beginning of list, list points to end of list count decremented appropriately. 4. Create a function to remove the first node of a linked list and put it at the end of the list. Use a pure virtual function virtual void rotate0; Function to remove the first node of a linked list / and put it at the end of the list. // Postcondition: first points to the new first node, last points to the old first node (which is the new last node), and count is unchanged. Because an ordered linked list must remain sorted, the orderedLinkedList template class should refuse to rotate the list, and produce a message that states "The ordered linked list cannot be rotated."Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*head;
void append(int num)
{
struct node *tmp,*r;
tmp= (struct node *)malloc(sizeof(struct node));
tmp->data=num;
r=(struct node *)head;
while(r->next != NULL)
r=r->next;
r->next =tmp;
r=tmp;
r->next=NULL;
}
void add( int num )
{
struct node *tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=num;
if (head== NULL)
{
head=tmp;
head->next=NULL;
}
else
{
tmp->next=head;
head=tmp;
}
}
void addafter(int num, int loc)
{
int i;
struct node *tmp,*left,*r;
r=head;
for(i=1;i<loc;i++)
{
left=r;
r=r->next;
}
tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=num;
left->next=tmp;
left=tmp;
left->next=r;
return;
}
void insert(int num)
{
int c=0;
struct node *tmp;
tmp=head;
if(tmp==NULL)
{
add(num);
}
else
{
while(tmp!=NULL)
{
if(tmp->data<num)
c++;
tmp=tmp->next;
}
if(c==0)
add(num);
else if(c<count())
addafter(num,++c);
else
append(num);
}
}
int delete(int num)
{
struct node *tmp, *prev;
tmp=head;
while(tmp!=NULL)
{
if(tmp->data==num)
{
if(tmp==head)
{
head=tmp->next;
free(tmp);
return 1;
}
else
{
prev->next=tmp->next;
free(tmp);
return 1;
}
}
else
{
prev=tmp;
tmp= tmp->next;
}
}
return 0;
}
void display(struct node *r)
{
r=head;
if(r==NULL)
{
return;
}
while(r!=NULL)
{
printf("%d ",r->data);
r=r->next;
}
printf(" ");
}
int count()
{
struct node *n;
int c=0;
n=head;
while(n!=NULL)
{
n=n->next;
c++;
}
return c;
}
int main()
{
int i,num;
struct node *n;
head=NULL;
while(1)
{
printf(" List Operations ");
printf("=============== ");
printf("1.Insert ");
printf("2.Display ");
printf("3.Size ");
printf("4.Delete ");
printf("5.Exit ");
printf("Enter your choice : ");
if(scanf("%d",&i)<=0){
printf("Enter only an Integer ");
exit(0);
} else {
switch(i)
{
case 1: printf("Enter the number to insert : ");
scanf("%d",&num);
insert(num);
break;
case 2: if(head==NULL)
{
printf("List is Empty ");
}
else
{
printf("Element(s) in the list are : ");
}
display(n);
break;
case 3: printf("Size of the list is %d ",count());
break;
case 4: if(head==NULL)
printf("List is Empty ");
else{
printf("Enter the number to delete : ");
scanf("%d",&num);
if(delete(num))
printf("%d deleted successfully ",num);
else
printf("%d not found in the list ",num);
}
break;
case 5: return 0;
default: printf("Invalid option ");
}
}
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.