Wednesday, October 15, 2008

bubble Sort for single linked list (C#)

**************this is a template for create a linked list
namespace SingleLinkedList
{
public class Node
{
public Object Element;
public Node Link;

///
/// constructor
///

public Node()
{
Element = null;
Link = null;
}

///
/// parameterized constructor
///

///
public Node(Object theElement)
{
Element = theElement;
Link = null;
}
}

public class LinkedList
{
protected Node header;
///
/// constructor used to assign default element to header
///

public LinkedList()
{
header = new Node("header");
}

///
/// find the node whose element is Item
///

///
///
private Node Find(Object Item)
{
Node current = new Node();
current = header;
while (current.Element != Item)
{
current = current.Link;
}
return current;
}
///
/// newitme will be insert behind the after
///

///
///
public void InsertAfter(Object newItem, Object after)
{
Node current = new Node();
Node newNode = new Node(newItem);
current = Find(after);
newNode.Link = current.Link;
current.Link = newNode;
}

///
/// find the previous node in front of element n
///

///
///
private Node FindPrevious(Object n)
{
Node current = header;
while (current.Link != null && current.Link.Element != n)
{
current = current.Link;
}
return current;
}

///
/// remove the node who has the element n
///

///
public void Remove(Object n)
{
Node p = FindPrevious(n);
if (p.Link != null)
{
p.Link = p.Link.Link;
}
}

///
/// insert the new element after the tail
///

///
public void Insert(Object Item)
{
Node current = new Node();
Node newNode = new Node(Item);
current = header;
while (current.Link != null)
{
current = current.Link;
}
current.Link = newNode;
}

///
/// print the linkedlist
///

public void PrintList()
{
Node current = new Node();
current = header;
while (current.Link != null)
{
Console.WriteLine(current.Link.Element);
current = current.Link;
}
}

}

class Program
{
static void Main(string[] args)
{
LinkedList myList = new LinkedList();
Random data = new Random();

for (int i = 0; i < 10; i++)
{
myList.Insert(data.Next(30));
}
myList.PrintList();
Console.WriteLine("~~~~~~~~~~~~~");
}
}
}

********************this is sample for linked list with bubble sort method
namespace SingleLinkedList
{
public class Node
{
public int Element;
public Node Link;

///
/// constructor
///

public Node()
{
Element = 0;
Link = null;
}

///
/// parameterized constructor
///

///
public Node(int theElement)
{
Element = theElement;
Link = null;
}
}

public class LinkedList
{
protected Node header;
///
/// constructor used to assign default element to header
///

public LinkedList()
{
header = new Node(-1);
}

///
/// find the node whose element is Item
///

///
///
private Node Find(int Item)
{
Node current = new Node();
current = header;
while (current.Element != Item)
{
current = current.Link;
}
return current;
}
///
/// newitme will be insert behind the after
///

///
///
public void InsertAfter(int newItem, int after)
{
Node current = new Node();
Node newNode = new Node(newItem);
current = Find(after);
newNode.Link = current.Link;
current.Link = newNode;
}

///
/// find the previous node in front of element n
///

///
///
private Node FindPrevious(int n)
{
Node current = header;
while (current.Link != null && current.Link.Element != n)
{
current = current.Link;
}
return current;
}

///
/// remove the node who has the element n
///

///
public void Remove(int n)
{
Node p = FindPrevious(n);
if (p.Link != null)
{
p.Link = p.Link.Link;
}
}

///
/// insert the new element after the tail
///

///
public void Insert(int Item)
{
Node current = new Node();
Node newNode = new Node(Item);
current = header;
while (current.Link != null)
{
current = current.Link;
}
current.Link = newNode;
}

///
/// print the linkedlist
///

public void PrintList()
{
Node current = new Node();
current = header;
while (current.Link != null)
{
Console.WriteLine(current.Link.Element);
current = current.Link;
}
}

public void SortL()
{
Node current = new Node();
Node next;

int count = 0;
Node LinkNode = new Node();
LinkNode = header;
//calculate the number of the link list node
while (LinkNode.Link != null)
{
count++;
LinkNode = LinkNode.Link;
}
//sort the linked list
for (int i = 0; i < count;i++ )
{
current = header;
while (current.Link != null)
{
next = new Node();
next = current.Link;

if (current.Element > next.Element)
{
int temp = current.Element;
current.Element = next.Element;
next.Element = temp;
}
current = current.Link;
}
}//end sort
}
}

class Program
{
static void Main(string[] args)
{
LinkedList myList = new LinkedList();
Random rd = new Random();

for (int i = 0; i < 20; i++)
{
myList.Insert(rd.Next(30));
}

myList.PrintList();
Console.WriteLine("~~~~~~~~~~~~~");
myList.SortL();
myList.PrintList();
Console.WriteLine("~~~~~~~~~~~~~");
}
}
}

No comments: