Considering that the width of the tree is defined as the maximum number of nodes at any one level, the following code should hold good. Drop a comment if you think that this code s***s [:)]
|
public void maxWidthBST(NodeType rootNode) public int NodeCount(NodeType root, int level) |
I have used C# for this code snippet.
public class checkString
{
public static void Main()
{
string strSource = "ABCacd12";
if(CheckString1(strSource))
{
Console.WriteLine("Unique!!!");
}
else
{
Console.WriteLine("Not Unique!!!");
}
}
public static bool CheckString1(string str)
{
int strLength = str.Length;
for(int i=0;i<strLength;i++)
{
for(int j=i+1;j<strLength;j++)
{
if(str.ElementAt(i)==str.ElementAt(j)) return false;
}
}
return true;
}
}
void SLList::removeDuplicates()
{
if(header)
{
Node *temp, *curChkNode, *last;
temp=curChkNode=header;
int curVal=0, length=0, counter=0;
length=sllLength();
cout<<"\nThe length of the list is:\t"<<length;
while(counter!=length && curChkNode)
{
temp=curChkNode->next;
curVal=curChkNode->data;
while(temp)
{
if(curVal==temp->data)
{
cout<<"\nA DUPLICATE IS PRESENT FOR:\t"<<curVal;
last->next=temp->next;
}
last=temp;
temp=temp->next;
}
curChkNode=curChkNode->next;
counter++;
}
}
else
{
cout<<"\nThe list is empty\n";
}
return;
}
The compiler showed the error:
“
error C2470: ‘SLList’ : looks like a function definition, but there is no parameter list; skipping apparent body
“
I had coded this snippet using a notepad and hence after lots of head banging figured out that the issue was a stupid missed (:):
class SLList
{
private:
Node *header;
public:
SLList()
{
header=NULL;
}
void createList();
void displayList();
int sllLength();
void removeDuplicates();
};
:::::::::::::
:::::::::::::::
int SLList:sllLength()
{
int counter=0;
if(header)
{
Node *temp;
temp=header;
while(temp)
{
counter++;
}
delete temp;
}
return counter;
}
should have been:
int SLList::sllLength()
{
int counter=0;
if(header)
{
Node *temp;
temp=header;
while(temp)
{
counter++;
}
delete temp;
}
return counter;
}
#include
using namespace std;
class Node
{
public:
int data;
Node *prev, *next;
Node()
{
data=NULL;
prev=NULL;
next=NULL;
}
};
class dll
{
private:
Node *header;
public:
dll(){
header=NULL;
}
void createList();
void displayList();
void insertEnd();
void deleteFirstNode();
void deleteLastNode();
void deleteNthNode();
};
void dll::deleteFirstNode()
{
if(header)
{
Node *temp;
temp=header;
header=temp->next;
header->prev=NULL;
delete temp;
}
else
{cout<<"\nThe list is empty!\n";}
return;
}
void dll::deleteLastNode()
{
if(header)
{
Node *temp, *last;
temp=header;
while(temp)
{
last=temp;
temp=temp->next;
}
last->prev->next=NULL;
delete last;
delete temp;
}
else
{cout<<"\nThe list is empty!\n";}
return;
}
void dll::deleteNthNode()
{
if(header)
{
Node *temp, *last;
temp=header;
int position=0, counter=0;
cout<<"Enter the node position that you want to delete: \t";
cin>>position;
if(position>=0)
{
while(counter!=position && temp)
{
last=temp;
temp=temp->next;
counter++;
}
if(temp)
{
cout<<"\nThe node that you want to delete has value:\t\n"<data;
last->prev->next=temp;
temp->prev=last->prev;
delete last;
}
else{cout<<"\nThe list does not contain that many elements\n";}
}
}
return;
}
void dll::insertEnd()
{
if(header==NULL)
{
createList();
}
else
{
Node *newNode, *temp, *last;
newNode=new Node;
cout<<"Enter the value for the node:\t";
cin>>newNode->data;
temp=header;
while(temp)
{
last=temp;
temp=temp->next;
}
newNode->next=NULL; //newNode is the new last node
newNode->prev=last;
newNode->prev->next=newNode;
}
return;
}
void dll::createList()
{
int in_val;
Node *temp;
temp=new Node;
cout<<"Enter the value for the node:\t";
cin>>temp->data;
if(header == NULL)
{
//This is the first node in the double linked list
temp->next=NULL;
temp->prev=NULL;
}
else
{
//If this is a new node at the front of an already populated linkedlist
temp->next=header;
temp->next->prev=temp;
header=temp;
}
header=temp;
return;
}
void dll::displayList()
{
Node *temp, *last;
temp=header;
cout<<"Display the list from first to last using the NEXT pointer.\n";
while(temp)
{
cout<data<<"\t"<<endl;
last=temp;
temp=temp->next;
}
/*if(last)
{
cout<<"Display the list from last to last using the PREV pointer.\n";
while(last)
{
cout<data<<"\t"<<endl;
last=last->prev;
}
}*/
}
void main()
{
cout<<"******This is a Doubly Linked List Demo******"<<endl;
int choice=0;
dll objDLL;
do{
cout<<"Enter the opration you want to perform: ";
cout<<"\n1). Add a node at front of the list";
cout<<"\n2). Display a node";
cout<<"\n3). Add a node at end of the list";
cout<<"\n4). Delete the node at head of the list";
cout<<"\n5). Delete the node at tail of the list";
cout<<"\n6). Delete the node at nth position of the list";
cout<<"\n7). Exit\t";
cin>>choice;
switch(choice)
{
case 1: objDLL.createList(); break;
case 2: objDLL.displayList(); break;
case 3: objDLL.insertEnd(); break;
case 4: objDLL.deleteFirstNode();break;
case 5: objDLL.deleteLastNode();break;
case 6: objDLL.deleteNthNode();break;
case 7: exit(0);
default: cout<<"\n Invalid operation/input detected. Please try again later.";
}
}while(choice!=7);
}
The operations to be supported:
1. PUSH
2. POP
3. Check if Empty
4. Check if Full
//I have just created the skeleton. Exception handling is not put in yet.
|
#include class stack //Class method implementation now stack::~stack() void stack::Push(int inData) //Note that the Pop operation is intended to return the data stored in the top most node and free //that space in the stack bool stack::IsEmpty() void stack::display() void main() <<endl; <<endl; |
/*
Find the nth Element from last in a linked list.
*/
#include
using namespace std;
struct node{int data; struct node *next;};
struct node* createlist()
{
node *nodeHolder,*pointerToTheFirstNode, *temp;
int elementCount=0;
pointerToTheFirstNode = (node*)malloc(sizeof(node));
temp=pointerToTheFirstNode;
cout<<"Enter the number of elements you want in the list: ";
cin>>elementCount;
cout<<endl;
while(elementCount!=0)
{
temp->next=(node*)malloc(sizeof(node));
cout<<"Enter the elements for the nodes: ";
cin>>temp->data;
nodeHolder=temp;
temp=temp->next;
elementCount–;
}
nodeHolder->next =NULL;
free(temp);
return pointerToTheFirstNode;
}
void display(struct node *headerPointer)
{
node *ptr;
ptr = headerPointer;
cout<<endl<<"The list that we just created is: ";
while(ptr!=NULL)
{
cout<data<<" ";
ptr=ptr->next;
}
cout<<endl;
}
int lenlist(struct node *header)
{
node *ptr;
int len=0;
ptr=header;
while(ptr!=NULL)
{
len=len+1;
ptr=ptr->next;
};
return len;
}
void findElementFromLast(struct node *header, int intPos)
{
node *ptr;
ptr=header;
int matchPos=0;
int listLen = lenlist(ptr);
cout<<"The length of the list is: "<<listLen<<endl;
cout<<"The element that is at "<< intPos <<" from the last node will be at "<<listLen-intPos<< " from the first node."<<endl;
while(ptr!=NULL)
{
matchPos=matchPos+1;
if(matchPos == (listLen-intPos))
{
cout<<"The value of the node that is at "<< intPos <<"th position from last is: "<data;
}
ptr=ptr->next ;
}
}
void main()
{
node *header;
int intPosFromLast=0;
header=createlist();
display(header);
cout<<"Enter the position element that you want to find in the list we just created: ";
cin>>intPosFromLast;
findElementFromLast(header,intPosFromLast);
}
/*
Find the nth Element in a linked list.
*/
#include
using namespace std;
struct node{int data; struct node *next;};
struct node* createlist()
{
node *nodeHolder,*pointerToTheFirstNode, *temp;
int elementCount=0;
pointerToTheFirstNode = (node*)malloc(sizeof(node));
temp=pointerToTheFirstNode;
cout<<"Enter the number of elements you want in the list: ";
cin>>elementCount;
cout<<endl;
while(elementCount!=0)
{
temp->next=(node*)malloc(sizeof(node));
cout<<"Enter the elements for the nodes: ";
cin>>temp->data;
nodeHolder=temp;
temp=temp->next;
elementCount–;
}
nodeHolder->next =NULL;
free(temp);
return pointerToTheFirstNode;
}
void display(struct node *headerPointer)
{
node *ptr;
ptr = headerPointer;
while(ptr!=NULL)
{
cout<data<<" ";
ptr=ptr->next;
}
cout<<endl;
}
void findElement(struct node *header, int intPos)
{
node *ptr;
int matchPos=0;
ptr=header;
while(ptr!=NULL)
{
matchPos=matchPos+1;
if(matchPos == intPos)
{
cout<<"The value at the node at position "<< intPos << " is: "<data;
}
ptr=ptr->next ;
}
}
void main()
{
node *header;
int intPos=0;
header=createlist();
display(header);
cout<<"Enter the position element that you want to find in the list we just created: ";
cin>>intPos;
findElement(header,intPos);
}
/*
Write a function to reverse a linked list. No double pointers please.
*/
#include
using namespace std;
struct node{int data; struct node *next;};
struct node* createlist()
{
int counter=0;
node *first, *temp, *last;
first = (node*)malloc(sizeof(node));
temp=first;
cin>>temp->data;
cout<<"Please enter the number of elements in the list that you want: ";
cin>>counter;
while(counter!=0)
{
temp->next=(node*)malloc(sizeof(node));
cout<<"Enter node data: ";
cin>>temp->data;
last=temp;
temp=temp->next;
counter–;
}
last->next =NULL;
delete(temp);
return first;
}
void display(struct node *header)
{
node *ptr;
ptr=header;
cout<<"The list now looks like: ";
while(ptr!=NULL)
{
cout<data<<" ";
ptr=ptr->next;
}
cout<<endl;
}
int lenlist(struct node *header)
{
node *ptr;
int len=0;
ptr=header;
while(ptr->next!=NULL)
{
len=len+1;
ptr=ptr->next;
};
return len;
}
struct node* reverselist(struct node *header)
{
int counter=5, tempHolder=0;
node *temp, *ptr,*prev, *last;
prev=NULL;
ptr=header;
//Obtain the length of the linked list
counter=lenlist(header);
while(counter!=0)
{
while(ptr->next!=NULL && ptr!=last)
{
if(ptr!=NULL)
{
tempHolder=ptr->data;
ptr->data=(ptr->next)->data;
(ptr->next)->data=tempHolder;
prev=ptr;
}
else
{
cout<<"IF YOU SEE THIS, THE CODE IS FAULTY. The value of ptr is NULL for counter value "<<counter<<endl;
}
ptr=ptr->next;
};
ptr=header;
last=prev;
counter–;
}
return header;
}
void main()
{
node *header, *latest;
node *header1;
header=createlist();
display(header);
latest=reverselist(header);
display(latest);
}
/*
You have two “set” of numbers represented by “two” linked lists, where each node contains a single digit.
Write a function that adds the two numbers “in the corresponding nodes” and returns the sum as a “third” linked list
*/
#include
using namespace std;
struct node{int data;struct node *next;};
void display(struct node *header)
{
cout<<endl;
node *ptr;
ptr=header;
cout<<"The list is: ";
while(ptr!=NULL)
{
cout<data<<" ";
ptr=ptr->next;
}
}
struct node* createlist()
{
int counter=0;
node *first, *last, *temp;
first= (node*)malloc(sizeof(node));
temp=first;
cout<<"Enter the number of elements: ";
cin>>counter;
while(counter!=0)
{
temp->next=(node*)malloc(sizeof(node));
cout<<"The node data is: ";
cin>>temp->data;
last=temp;
temp=temp->next;
counter–;
}
last->next=NULL;
return first;
}
struct node* createlist(node *pointer3,int nodevalue)
{
node *ptr;
ptr=pointer3;
if(ptr==NULL)
{
node *temp;
temp=(node*)malloc(sizeof(node));
temp->data=nodevalue;
return temp;
}
else
{
node *last;
last=pointer3;
pointer3->next=(node*)malloc(sizeof(node));
pointer3=pointer3->next;
pointer3->data=nodevalue;
return pointer3;
}
}
struct node* addlinkedlist(struct node *header1, struct node *header2)
{
cout<<endl;
node *firstlist,*secondlist, *pointer3, *baseptr;
firstlist=header1;
secondlist=header2;
pointer3 = NULL;
while(firstlist !=NULL && secondlist !=NULL)
{
if(pointer3==NULL)
{
baseptr = createlist(pointer3,firstlist->data + secondlist->data);
pointer3=baseptr;
}
else
{
pointer3 = createlist(pointer3,firstlist->data + secondlist->data);
}
secondlist=secondlist->next;
firstlist= firstlist->next;
}
return baseptr;
}
void main()
{
cout<<"You have two set of numbers represented by two linked lists, where each node contains a single digit.";
cout<<"Write a function that adds the two numbers in the corresponding nodes and returns the sum as a third linked list";
node *header1, *header2, *header3;
header1 = createlist();
header2=createlist();
display(header1);
display(header2);
header3= addlinkedlist(header1, header2);
display(header3);
}
Random Thoughtz 