using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms
{
class Tree
{
private TreeNode root;
public Tree()
{
root = null;
}
public TreeNode FindRecursive(TreeNode root, int dataValue)
{
if (root == null)
{ return null; }
else if (root.DataValue == dataValue)
{ return root; }
else if (root.DataValue < dataValue)
{ return FindRecursive(root.RightNode, dataValue);}
else
{ return FindRecursive(root.LeftNode, dataValue);
}
}
public TreeNode Find(int dataValue)
{
if (root == null)
{
return null;
}
else
{
TreeNode currentNode = root;
while (currentNode != null)
{
if (currentNode.DataValue == dataValue)
{
return currentNode;
}
else if (currentNode.DataValue < dataValue)
{
currentNode = currentNode.RightNode;
}
else if (currentNode.DataValue > dataValue)
{
currentNode = currentNode.LeftNode;
}
return null;
}
return null;
}
}
}
public class TreeNode
{
private int dataValue;
private TreeNode leftNode = null;
private TreeNode rightNode = null;
public TreeNode(int data)
{
dataValue = data;
}
public TreeNode LeftNode
{
get
{
return leftNode;
}
set
{
leftNode = value;
}
}
public TreeNode RightNode
{
get
{
return rightNode;
}
set
{
rightNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}
}
}
Sunday, March 25, 2007
Tree Data structure in C Sharp .NET
Here is a simple Tree data structure in C sharp.NET
Sunday, February 25, 2007
Check If Cycle exists in a Linked List
Check if the linked list contains a cycle
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms
{
public class LinkedList
{
private Node head;
public LinkedList()
{
head = null;
}
public bool CheckCycle()
{
Node step1Node = head;
Node step2Node = head.NextNode;
while (true)
{
if ((step2Node == null)||(step2Node.NextNode == null))
return false;
else if ((step1Node.Equals(step2Node))||(step1Node.Equals(step2Node.NextNode)))
return true;
else
{
step2Node = step2Node.NextNode;
step2Node = step2Node.NextNode;
step1Node = step1Node.NextNode;
}
}
}
public int FindPosition(int data)
{
Node checkNode = head;
int position = 1;
int dataPosition = 0;
while (checkNode != null)
{
if (checkNode.DataValue == data)
{
dataPosition = position;
}
checkNode = checkNode.NextNode;
position = position + 1;
}
return dataPosition;
}
}
public class Node
{
private int dataValue;
private Node nextNode = null;
public Node(int data)
{
dataValue = data;
}
public Node NextNode
{
get
{
return nextNode;
}
set
{
nextNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}
}
}
Nth Element from the last in a Linked List
Another advanced algorithm is to find the Nth Element from the LAST with the optimal performance.
Here is the implementation
Here is the implementation
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms
{
public class LinkedList
{
private Node head;
public LinkedList()
{
head = null;
}
public int FindNthElementFromLast(int m)
{
int n = m - 1;
int returnValue = -1;
if (n >= 0)
{
Node nthElement = head;
Node currentElement = head;
for (int i =0;i less than n;i++)
{
if (currentElement.NextNode != null)
{
currentElement = currentElement.NextNode;
}
else
{
returnValue = -1;
return returnValue;
}
}
if (returnValue != -1)
{
while (currentElement.NextNode != null)
{
currentElement = currentElement.NextNode;
nthElement = nthElement.NextNode;
}
returnValue = nthElement.DataValue;
}
}
return returnValue;
}
}
public class Node
{
private int dataValue;
private Node nextNode = null;
public Node(int data)
{
dataValue = data;
}
public Node NextNode
{
get
{
return nextNode;
}
set
{
nextNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}
}
}
Linked List SORT Algorithm
If you need a sort algorithm in Linked List. Please check other implementation in my last blog.
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms
{
public class LinkedList
{
private Node head;
public LinkedList()
{
head = null;
}
public void Sort()
{
if (head != null)
{
int j = 0;
Node MinElement = head;
Node currentElement = MinElement.NextNode;
while (currentElement != null)
{
if (currentElement.DataValue < MinElement.DataValue)
{
MinElement = currentElement;
Insert(MinElement.DataValue);
DeleteAtPosition(j+1);
}
MinElement = MinElement.NextNode;
}
}
}
}
public class Node
{
private int dataValue;
private Node nextNode = null;
public Node(int data)
{
dataValue = data;
}
public Node NextNode
{
get
{
return nextNode;
}
set
{
nextNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}
}
}
Saturday, January 20, 2007
Linked List in C Sharp.NET
I got tones of emails, lately for Linklist and Tree data structure implemetation
Here is a simple Linked List Data structure in C Sharp.NET. A LinkedList will always have two class a LinkedList class and a Node Class.
I have also included most common options to insert and Delete nodes.
Here is a simple Linked List Data structure in C Sharp.NET. A LinkedList will always have two class a LinkedList class and a Node Class.
I have also included most common options to insert and Delete nodes.
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms
{
public class LinkedList
{
private Node head;
public LinkedList()
{
head = null;
}
public void Insert(int dataValue)
{
if (head == null)
{
Node nodeInsert = new Node(dataValue);
head = nodeInsert;
nodeInsert.NextNode = null;
}
else
{
Node nodeInsert = new Node(dataValue);
nodeInsert.NextNode = head;
head = nodeInsert;
}
}
public void InsertAtPosition(Node insertNode, int i)
{
if (i == 0)
{
insertNode.NextNode = head;
head = insertNode;
}
else
{
Node currentNode = head;
Node currentNodeNext = head.NextNode;
for (int j = 0; j < i; j++)
{
currentNode = currentNode.NextNode;
currentNodeNext = currentNode.NextNode;
}
if (currentNode != null)
{
currentNode.NextNode = insertNode;
insertNode.NextNode = currentNodeNext;
}
}
}
public void DeleteAtPosition(int i)
{
if (i == 0)
{
head = null;
}
else
{
Node currentNode = head;
Node currentNodeNext = head.NextNode;
for (int j = 0; j < i; j++)
{
currentNode = currentNode.NextNode;
currentNodeNext = currentNode.NextNode;
}
if (currentNode != null)
{
currentNode.NextNode = currentNodeNext.NextNode;
}
}
}
public bool Delete(Node nodeToDelete)
{
bool returnFlag = false;
if (head == null)
returnFlag = false;
else if (head.Equals(nodeToDelete))
{
head = null;
returnFlag = true;
}
else
{
Node checkNode = head;
Node checkNodeNext = head.NextNode;
while (checkNodeNext != null)
{
if (checkNodeNext.Equals(nodeToDelete))
{
checkNode.NextNode = checkNodeNext.NextNode;
checkNodeNext = null;
returnFlag = true;
}
}
}
return returnFlag;
}
public void Print()
{
Node firstNode = head;
while (firstNode != null)
{
Console.Write(firstNode.DataValue + " ");
firstNode = firstNode.NextNode;
}
}
public void Clear()
{
Node checkNode = head;
Node checkNodeNext;
while (checkNode != null)
{
checkNodeNext = checkNode.NextNode;
checkNode = null;
checkNode = checkNodeNext;
}
}
}
public class Node
{
private int dataValue;
private Node nextNode = null;
public Node(int data)
{
dataValue = data;
}
public Node NextNode
{
get
{
return nextNode;
}
set
{
nextNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}
}
}
Monday, December 25, 2006
First Non-Repeated Character from a UNICODE String using Hash Table
the only difference here is the input string can be UNICODE (65000 characters) instead of ASCII Code (256 characters) so using a hash table makes more sense
public static char FirstNonRepeatedHash(string stringToCheck)
{
Hashtable cHash = new Hashtable();
int length = stringToCheck.Length;
int i = 0;
bool hashPresent = false;
char charToReturn = '\0';
for (i = 0; i < length; i++)
{
hashPresent = cHash.Contains(stringToCheck[i]);
if (hashPresent)
{
cHash[stringToCheck[i]] = 1 + Convert.ToInt32(cHash[stringToCheck[i]]);
}
else
{
cHash.Add(Convert.ToChar(stringToCheck[i]), 1);
}
}
for (i = 0; i < length; i++)
{
if (Convert.ToInt32(cHash[stringToCheck[i]]) ==1 )
{
charToReturn = stringToCheck[i];
break;
}
}
return charToReturn;
}
First Non repeated Character in a String using an Array
Here is how to find the first non repeated character in an a string using an array
the assumption is the String is ASCII other wise check for the hash table function
For example If the input is "TEETOTALAR" The First non repeated Character is "O"
the assumption is the String is ASCII other wise check for the hash table function
For example If the input is "TEETOTALAR" The First non repeated Character is "O"
public static char FirstNonRepeatedArray(string stringToCheck)
{
int length = stringToCheck.Length;
int i = 0;
int[] intCollection = new int[256];
char returnChar = '\0';
for (i = 0; i < length; i++)
{
intCollection[stringToCheck[i]] = intCollection[stringToCheck[i]] + 1;
}
for (i = 0; i < length; i++)
{
if (intCollection[stringToCheck[i]] == 1)
{
returnChar = stringToCheck[i];
break;
}
}
return returnChar;
}
Subscribe to:
Posts (Atom)