Friday, October 31, 2008

Singleton pettern in C#

In software engineering, the singleton pettern is a desgin pettern that is used to restrict instantiation of a class to one object.(This concept is also sometimes generalized to restrict the instance to a specific number of objects--for example, we can restrict the number of instance to five object). This is useful when exactly one object is needed to coordinate actions across the system. sometimes it is generalized to system that operate more efficiently when only one or a few objects exist. It is also considered a anti-pettern by some people, who feel that it is overused, introducing unneccessary limitation in situation where a sole instance of a class is not actually required.

OK, let's go!

UML Class Diagram


sample one:
//This structural code demonstrates the Singleton pattern
//which assures only a single instance (the singleton) of the class can be created.
namespace SingletonPetternTest
{
class Singleton
{
private static Singleton instance;

protected Singleton()
{ }

public static Singleton Instance()
{
//use "lazy initialization"
if (instance == null)
{
instance = new Singleton();
}
return instance;
}
}

class Program
{
static void Main(string[] args)
{
Singleton s1 = Singleton.Instance();
Singleton s2 = Singleton.Instance();

if (s1 == s2)
{
Console.WriteLine("objects are the same instance...");
}
}
}
}


sample two:
This real-world code demonstrates the Singleton pattern as a LoadBalancing object. Only a single instance (the singleton) of the class can be created because servers may dynamically come on- or off-line and every request must go throught the one object that has knowledge about the state of the (web) farm.
// Singleton pattern -- Real World example

using System;
using System.Collections;
using System.Threading;

namespace DoFactory.GangOfFour.Singleton.RealWorld
{

// MainApp test application

class MainApp
{
static void Main()
{
LoadBalancer b1 = LoadBalancer.GetLoadBalancer();
LoadBalancer b2 = LoadBalancer.GetLoadBalancer();
LoadBalancer b3 = LoadBalancer.GetLoadBalancer();
LoadBalancer b4 = LoadBalancer.GetLoadBalancer();

// Same instance?
if (b1 == b2 && b2 == b3 && b3 == b4)
{
Console.WriteLine("Same instance\n");
}

// All are the same instance -- use b1 arbitrarily
// Load balance 15 server requests
for (int i = 0; i < 15; i++)
{
Console.WriteLine(b1.Server);
}

// Wait for user
Console.Read();
}
}

// "Singleton"

class LoadBalancer
{
private static LoadBalancer instance;
private ArrayList servers = new ArrayList();

private Random random = new Random();

// Lock synchronization object
private static object syncLock = new object();

// Constructor (protected)
protected LoadBalancer()
{
// List of available servers
servers.Add("ServerI");
servers.Add("ServerII");
servers.Add("ServerIII");
servers.Add("ServerIV");
servers.Add("ServerV");
}

public static LoadBalancer GetLoadBalancer()
{
// Support multithreaded applications through
// 'Double checked locking' pattern which (once
// the instance exists) avoids locking each
// time the method is invoked
if (instance == null)
{
lock (syncLock)
{
if (instance == null)
{
instance = new LoadBalancer();
}
}
}

return instance;
}

// Simple, but effective random load balancer

public string Server
{
get
{
int r = random.Next(servers.Count);
return servers[r].ToString();
}
}
}
}


sample three:
This .NET optimized code demonstrates the same code as above but uses more modern, built-in .NET features.

Here an elegant .NET specific solution is offered. The Singleton pattern simply uses a private constructor and a static readonly instance variable that is lazily initialized. Thread safety is guaranteed by the compiler.

// Singleton pattern -- .NET optimized

using System;
using System.Collections;

namespace DoFactory.GangOfFour.Singleton.NETOptimized
{

// MainApp test application

class MainApp
{

static void Main()
{
LoadBalancer b1 = LoadBalancer.GetLoadBalancer();
LoadBalancer b2 = LoadBalancer.GetLoadBalancer();
LoadBalancer b3 = LoadBalancer.GetLoadBalancer();
LoadBalancer b4 = LoadBalancer.GetLoadBalancer();

// Confirm these are the same instance
if (b1 == b2 && b2 == b3 && b3 == b4)
{
Console.WriteLine("Same instance\n");
}

// All are the same instance -- use b1 arbitrarily
// Load balance 15 requests for a server
for (int i = 0; i < 15; i++)
{
Console.WriteLine(b1.Server);
}

// Wait for user
Console.Read();
}
}

// Singleton

sealed class LoadBalancer
{
// Static members are lazily initialized.
// .NET guarantees thread safety for static initialization
private static readonly LoadBalancer instance =
new LoadBalancer();

private ArrayList servers = new ArrayList();
private Random random = new Random();

// Note: constructor is private.
private LoadBalancer()
{
// List of available servers
servers.Add("ServerI");
servers.Add("ServerII");
servers.Add("ServerIII");
servers.Add("ServerIV");
servers.Add("ServerV");
}

public static LoadBalancer GetLoadBalancer()
{
return instance;
}

// Simple, but effective load balancer
public string Server
{
get
{
int r = random.Next(servers.Count);
return servers[r].ToString();
}
}
}
}


sample four:


using System.Threading;//
namespace SingletonPetternTest
{
public class Singleton
{
private static readonly Singleton _instance;
private int v;
//protected constructor is sufficient to prevent instantiation by using "new" keyword
protected Singleton()
{
Console.WriteLine("Singleton Instance Creating....");
this.V = 0;
Thread.Sleep(1000);//simulate a heavy creation cost
Console.WriteLine("Singleton Instance Created...");
}

//static constructor
static Singleton()
{
_instance = new Singleton();
}

public static Singleton Instance
{
get
{
return _instance;
}
}

public int V
{
get
{
return v;
}
set
{
v = value;
}
}

public void DoSomeWork()
{
Console.WriteLine("#");
lock (this)
{
V++;
}
Thread.Sleep(500);
}
}

class Program
{
//singleton with multithread
static void MultiThread()
{
Singleton instance = Singleton.Instance;
Thread t = new Thread(new ThreadStart(instance.DoSomeWork));
t.Start();
}

static void Main(string[] args)
{
int i;
for (i = 0; i < 10; i++)
{
Console.WriteLine("Do Some Work...");
Thread.Sleep(100);
}
//until now,this application has no any instance
for (i = 0; i < 300; i++)
{
MultiThread();
}

Thread.Sleep(1000); // wait for sure all threads finished
Console.WriteLine();
Console.WriteLine("V value expected: "+i+" actual value is : "+Singleton.Instance.V);
}
}
}

Monday, October 27, 2008

Factory Method Pattern(C#)

The Factory Method Pattern is an Object-Oriented design pattern, which deals with the problem of creating objects(products) without specifying the exact class of object that will be created. The Factory Method design pattern handles this problem by defining a separate method for creating the objects, whose subclasses can then override to specify the derived type of products that will be created. More generally,the term Factory Method is often used to refer to any method whose main purpose is creation of objects.
Definition:
The essence of Factory Method is to "Define a interface for creating an object, but let the subclasses decide which class to instantiate. The Factory Method lets a class defer instantiation to subclasses."
Common Usage:
* Factory Method are common in toolkits and frameworks where library code need to create objects of types which may be subclassed by application using the framework.
* Parallel class hierarchies often require objects from one hierarchy to be able to create appropriate objects from another.
Limitations:
* The first limitation is that refactoring an existing class to use factories breaks existing clients. For example, if class Complex was a standard class, it might have numerous clients with code like:
Complex c = new Complex(-1, 0);
Once we realize that two different factories are needed, we change the class (to the code shown earlier). But since the constructor is now private, the existing client code no longer compiles.
* The second limitation is that, since the pattern relies on using a private constructor, the class cannot be extended. Any subclass must invoke the inherited constructor, but this cannot be done if that constructor is private.
* The third limitation is that, if we do extend the class (e.g., by making the constructor protected -- this is risky but possible), the subclass must provide its own re-implementation of all factory methods with exactly the same signatures. For example, if class StrangeComplex extends Complex, then unless StrangeComplex provides its own version of all factory methods, the call StrangeComplex.fromPolar(1, pi) will yield an instance of Complex (the superclass) rather than the expected instance of the subclass.

All three problems could be alleviated by altering the underlying programming language to make factories first-class class members (rather than using the design pattern).

Example Code:

namespace FactoryMethod
{
public abstract class Pizza
{
public abstract decimal GetPrice();
public enum PizzaType
{
HamMushroom,Deluxe,Seafood
}

public static Pizza PizzaFactory(PizzaType pizzaType)
{
switch (pizzaType)
{
case PizzaType.HamMushroom:
return new HamAndMushroomPizza();
case PizzaType.Deluxe:
return new DeluxePizza();
case PizzaType.Seafood:
return new SeafoodPizza();
}

throw new System.NotSupportedException("The pizza type "+pizzaType.ToString()+" is not recognized.");
}
}

public class HamAndMushroomPizza : Pizza
{
private decimal Price = 8.5M;
public override decimal GetPrice()
{
return Price;
}
}

public class DeluxePizza : Pizza
{
private decimal Price = 10.5M;
public override decimal GetPrice()
{
return Price;
}
}

public class SeafoodPizza : Pizza
{
private decimal Price = 11.5M;
public override decimal GetPrice()
{
return Price;
}
}

class Program
{
static void Main(string[] args)
{
//output 11.50
Console.WriteLine(Pizza.PizzaFactory(Pizza.PizzaType.Seafood).GetPrice().ToString("C2"));
}
}
}

Wednesday, October 22, 2008

Sort the data alphabetically using SortedList class(C#)

Today I saw a blog about SortedList calss. This class can sort your datas alphabetical. But you must know it sort acccording to the Key but not the value. if you change the key sequence, the output will change according to new key sort.
OK, let's go!

using System.Collections;//
namespace SortListClass
{
class Program
{
static void Main(string[] args)
{
SortedList mySortList = new SortedList();
mySortList["b"] = "张三";
mySortList["A"] = "李四";
mySortList["D"] = "王五";
mySortList["c"] = "赵六";

foreach (DictionaryEntry Item in mySortList)
{
Console.WriteLine(Item.Key.ToString()+" : "+ Item.Value.ToString());
Console.WriteLine();
}
Console.WriteLine();
}
}
}


here is also a sample for website:

client code:
<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
<title>SortedList Class Test</title>
</head>
<body>
<form id="form1" runat="server">
<div>
<h1>This is a test for SortedList Class</h1>
<br />
<asp:DropDownList ID="ddlName" runat=server Width="100px"></asp:DropDownList>
<asp:Button ID="btnChoose" runat=server Text="Choose A Name"
onclick="btnChoose_Click" />
<br />
<br />
<br />
<br />
<asp:Label ID="lblMsg" runat=server></asp:Label>
</div>
</form>
</body>
</html>

code behind:

using System.Collections;//
public partial class _Default : System.Web.UI.Page
{
protected void Page_Load(object sender, EventArgs e)
{
SortedList mySortList = new SortedList();
mySortList["张三"] = "我是张三";
mySortList["李四"] = "我是李四";
mySortList["王五"] = "我是王五";
mySortList["赵六"] = "我是赵六";
mySortList["阿福"] = "我是阿福";
if (!IsPostBack)
{
foreach (DictionaryEntry Item in mySortList)
{
ListItem newListItem = new ListItem();
newListItem.Text = Item.Key.ToString();
newListItem.Value = Item.Value.ToString();
ddlName.Items.Add(newListItem);
}
}
}
protected void btnChoose_Click(object sender, EventArgs e)
{
lblMsg.Text = ddlName.SelectedItem.Value.ToString();
}
}

Tuesday, October 21, 2008

The Shell Sort Algorithm(C#)

namespace ShellSortAlgorithm
{
public class CArray
{
private int[] arr;
private int upper;
private int numElement;
public CArray(int size)
{
arr = new int[size];
upper = size - 1;
numElement = 0;
}

public void Insert(int item)
{
arr[numElement] = item;
numElement++;
}

public void DisplayElement()
{
for (int i = 0; i <= upper; i++)
{
Console.Write(arr[i]+" ");
}
}

public void Clear()
{
for (int i = 0; i <= upper; i++)
{
arr[i] = 0;
}
numElement = 0;
}

public void ShellSort()
{
int inner, temp;
int h = 1;
while (h < numElement / 3)
{
h = h * 3 + 1;
}

while (h > 0)
{
for (int outer = h; outer <= numElement-1; outer++)
{
temp = arr[outer];
inner = outer;
while ((inner > h - 1) && arr[inner - h] >= temp)
{
arr[inner] = arr[inner - h];
inner -= h;
}
arr[inner] = temp;
}
h = (h - 1) / 3;
}
}
}

class Program
{
static void Main(string[] args)
{
const int size = 19;
CArray theArray = new CArray(size);
Random rd = new Random(100);
for (int i = 0; i < size; i++)
{
theArray.Insert((int)(rd.NextDouble() * 100));
}
Console.WriteLine();
theArray.DisplayElement();
Console.WriteLine();
theArray.ShellSort();
theArray.DisplayElement();
Console.WriteLine();
}
}
}

Monday, October 20, 2008

BitArray Set Implementation(C#)

using System.Collections;//
namespace BitArraySet
{
public class CSet
{
private BitArray data;
public CSet()
{
data = new BitArray(5);
}

public void Add(int item)
{
data[item] = true;
}

public bool IsMember(int item)
{
return data[item];
}

public void Remove(int item)
{
data[item] = false;
}

public CSet Union(CSet aSet)
{
CSet tempSet = new CSet();
for (int i = 0; i < data.Count; i++)
{
tempSet.data[i] = (this.data[i] || aSet.data[i]);
}
return tempSet;
}

public CSet Intersection(CSet aSet)
{
CSet tempSet = new CSet();
for (int i = 0; i < data.Count; i++)
{
tempSet.data[i] = (this.data[i] && aSet.data[i]);
}
return tempSet;
}

public CSet Difference(CSet aSet)
{
CSet tempSet = new CSet();
for (int i = 0; i < data.Count; i++)
{
tempSet.data[i] = (this.data[i] && (!(aSet.data[i])));
}
return tempSet;
}

public bool IsSubset(CSet aSet)
{
CSet tempSet = new CSet();
for (int i = 0; i < data.Count; i++)
{
if (this.data[i] && (!(aSet.data[i])))
{
return false;
}
}
return true;
}

public override string ToString()
{
string s = "";
for (int i = 0; i < data.Count; i++)
{
if (data[i])
{
s += i.ToString(); ;
}
}
return s;
}
}

class Program
{
static void Main(string[] args)
{
CSet setA = new CSet();
CSet setB = new CSet();

setA.Add(1);
setA.Add(2);
setA.Add(3);
setB.Add(2);
setB.Add(3);

CSet setC = new CSet();
setC = setA.Union(setB);
Console.WriteLine();
Console.WriteLine(setA.ToString());
Console.WriteLine(setB.ToString());
setC = setA.Intersection(setB);
Console.WriteLine(setC.ToString());
setC = setA.Difference(setB);
Console.WriteLine(setC.ToString());
if (setB.IsSubset(setA))
{
Console.WriteLine("B is a subset of A");
}
else
{
Console.WriteLine("B is not a subset of A");
}
}
}
}

Define the Set Class(C#)

using System.Collections;//
namespace ClassSetPractise
{
public class CSet
{
//the two most important properties of sets are that
//the members of a set are unordered and no member
//can occur in a set more than once
//we only need one data member and one structors members for our CSet
private Hashtable data;
public CSet()
{
data = new Hashtable();
}

public void Add(Object item)
{
if (!(data.ContainsValue(item)))
{
data.Add(Hash(item),item);
}
}
private string Hash(Object item)
{
char[] chars;
int hashValue = 0;
string s = item.ToString();
chars = s.ToCharArray();
for (int i = 0; i <= chars.GetUpperBound(0); i++)
{
hashValue += (int)chars[i];
}
return hashValue.ToString();
}

public void Remove(Object item)
{
data.Remove(Hash(item));
}

public int Size()
{
return data.Count;
}

public CSet Union(CSet aSet)
{
CSet tempSet = new CSet();
foreach (Object hashObject in data.Keys)
{
tempSet.Add(this.data[hashObject]);
}
foreach (Object hashObject in aSet.data.Keys)
{
if (!(this.data.ContainsKey(hashObject)))
{
tempSet.Add(aSet.data[hashObject]);
}
}

return tempSet;
}

public CSet Intersection(CSet aSet)
{
CSet tempSet = new CSet();
foreach (Object hashObject in data.Keys)
{
if (aSet.data.Contains(hashObject))
{
tempSet.Add(aSet.data[hashObject]);//
}
}
return tempSet;
}

public bool Subset(CSet aSet)
{
//if (this.Size > aSet.Size)
//{
// return false;
//}
//else
//{
foreach (Object key in this.data.Keys)
{
if (!(aSet.data.Contains(key)))
{
return false;
}
}
//}
return true;
}

public CSet Different(CSet aSet)
{
CSet tempSet = new CSet();
foreach (Object hashObject in data.Keys)
{
if (!(aSet.data.Contains(hashObject)))
{
tempSet.Add(data[hashObject]);
}
}
return tempSet;
}

public override string ToString()
{
string s = "";
foreach (Object key in data.Keys)
{
s += data[key]+" ";
}
return s;
}
}
class Program
{
static void Main(string[] args)
{
CSet setA = new CSet();
CSet setB = new CSet();

setA.Add("milk");
setA.Add("eggs");
setA.Add("bacon");
setA.Add("cereal");

setB.Add("bacon");
setB.Add("eggs");
setB.Add("bread");

CSet setC = new CSet();
setC = setA.Union(setB);
Console.WriteLine();
Console.WriteLine("A: "+setA.ToString());
Console.WriteLine("B: "+setB.ToString());
Console.WriteLine("A union B: "+setC.ToString());
setC = setA.Intersection(setB);
Console.WriteLine("A intersect B: "+setC.ToString());
setC = setA.Different(setB);
Console.WriteLine("B diff A: "+setC.ToString());
if (setB.Subset(setA))
{
Console.WriteLine("B is a subset of A");
}
else
{
Console.WriteLine("B is not a subset of A");
}
}
}
}

How to delete node from binary search tree(C#)

namespace BinarySearchTreeDelete
{
//define a Node class for tree
public class Node
{
public int Data;
public Node Left;
public Node Right;

public void DisplayNode()
{
Console.Write(Data+" ");
}
}

public class BinarySearchTree
{
public Node root;
public BinarySearchTree()
{
root = null;
}

public void Insert(int i)
{
Node newNode = new Node();
newNode.Data = i;
if (root == null)
{
root = newNode;
}
else
{
Node Current = root;
Node parent;
while (true)
{
parent = Current;
if (i < Current.Data)
{
Current = Current.Left;
if (Current == null)
{
parent.Left = newNode;
break;
}
}
else
{
Current = Current.Right;
if (Current == null)
{
parent.Right = newNode;
break;
}
}
}
}
}

public void InOrder(Node theRoot)
{
if (theRoot != null)
{
InOrder(theRoot.Left);
theRoot.DisplayNode();
InOrder(theRoot.Right);
}
}

public Node GetSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.Right;

while (current != null)
{
successorParent = current;
successor = current;
current = current.Left;
}
if (successor != delNode.Right)
{
successorParent.Left = successor.Right;
successor.Right = delNode.Right;
}
return successor;
}

public bool Delete(int key)
{
Node current = root;
Node parent = root;
bool isLeftChild = true;
while (current.Data != key)
{
parent = current;
if (key < current.Data)
{
isLeftChild = true;
current = current.Left;//
}
else
{
isLeftChild = false;
current = current.Right;
}
if (current == null)
{
return false;
}
}

if (current.Left == null && current.Right == null)
{
if (current == root)
{
root = null;
}
else if (isLeftChild)
{
parent.Left = null;
}
else
{
parent.Right = null;
}
}
else if (current.Right == null)
{
if (current == root)
{
root = current.Left;
}
else if (isLeftChild)
{
parent.Left = current.Left;
}
else
{
parent.Right = current.Right;
}
}
else if (current.Left == null)
{
if (current == root)
{
root = current.Right;
}
else if (isLeftChild)
{
parent.Left = parent.Right;
}
else
{
parent.Right = current.Right;
}
}
else
{
Node successor = GetSuccessor(current);
if (current == root)
{
root = successor;
}
else if (isLeftChild)
{
parent.Left = successor;
}
else
{
parent.Right = successor;
}
successor.Left = current.Left;
}
return true;
}
}

class Program
{
static void Main(string[] args)
{
BinarySearchTree BST = new BinarySearchTree();
BST.Insert(23);
BST.Insert(45);
BST.Insert(16);
BST.Insert(37);
BST.Insert(3);
BST.Insert(99);
BST.Insert(22);
BST.Insert(5);
Console.WriteLine("InOrder traversing...");
BST.InOrder(BST.root);
Console.WriteLine();
if (BST.Delete(45))
{
BST.InOrder(BST.root);
}
else
{
Console.WriteLine("there is no this number...");
}
Console.WriteLine();
}
}
}

Search the Mini value and Max value in Tree(C#)

namespace BinaryTree
{
public class Node
{
public int Data;
public Node Left;
public Node Right;
public void DisplayNode()
{
Console.Write(Data+" ");
}
}

public class BinarySearchTree
{
public Node root;
public BinarySearchTree()
{
root = null;
}
public void Insert(int i)
{
Node newNode = new Node();
newNode.Data = i;
if (root == null)
{
root = newNode;
}
else
{
Node Current = root;
Node Parent;
while (true)
{
Parent = Current;
if (i < Parent.Data)
{
Current = Current.Left;
if (Current == null)
{
Parent.Left = newNode;
break;
}
}
else
{
Current = Current.Right;
if (Current == null)
{
Parent.Right = newNode;
break;
}
}
}
}
}

public void InOrder(Node theRoot)
{
if (theRoot != null)
{
InOrder(theRoot.Left);
theRoot.DisplayNode();
InOrder(theRoot.Right);
}
}
public void FindMini()
{
Node Current = root;
while (Current.Left != null)
{
Current = Current.Left;
}
Console.WriteLine("the Mini data is: "+Current.Data);
}

public void FindMax()
{
Node Current = root;
while (Current.Right != null)
{
Current = Current.Right;
}
Console.WriteLine("the Max data is: " + Current.Data);
}
}

class Program
{
static void Main(string[] args)
{
BinarySearchTree BST = new BinarySearchTree();
BST.Insert(23);
BST.Insert(45);
BST.Insert(16);
BST.Insert(37);
BST.Insert(3);
BST.Insert(99);
BST.Insert(22);
Console.WriteLine("traversing with InOrder...");
BST.InOrder(BST.root);
Console.WriteLine();
Console.WriteLine();
Console.WriteLine("Find the Mini data in this tree...");
BST.FindMini();
Console.WriteLine();
Console.WriteLine("Find the Max data in this tree...");
BST.FindMax();
Console.WriteLine();
}
}
}

How to Use Binary Search Tree(C#)

namespace BinaryTree
{
public class Node
{
public int Data;
public Node Left;
public Node Right;
public void DisplayNode()
{
Console.Write(Data+" ");
}
}

public class BinarySearchTree
{
public Node root;
public BinarySearchTree()
{
root = null;
}
public void Insert(int i)
{
Node newNode = new Node();
newNode.Data = i;
if (root == null)
{
root = newNode;
}
else
{
Node Current = root;
Node Parent;
while (true)
{
Parent = Current;
if (i < Parent.Data)
{
Current = Current.Left;
if (Current == null)
{
Parent.Left = newNode;
break;
}
}
else
{
Current = Current.Right;
if (Current == null)
{
Parent.Right = newNode;
break;
}
}
}
}
}

public void InOrder(Node theRoot)
{
if (theRoot != null)
{
InOrder(theRoot.Left);
theRoot.DisplayNode();
InOrder(theRoot.Right);
}
}
public void PreOrder(Node theRoot)
{
if (theRoot != null)
{
theRoot.DisplayNode();
PreOrder(theRoot.Left);
PreOrder(theRoot.Right);
}
}

public void PostOrder(Node theRoot)
{
if (theRoot != null)
{
PostOrder(theRoot.Left);
PostOrder(theRoot.Right);
theRoot.DisplayNode();
}
}
}

class Program
{
static void Main(string[] args)
{
BinarySearchTree BST = new BinarySearchTree();
BST.Insert(23);
BST.Insert(45);
BST.Insert(16);
BST.Insert(37);
BST.Insert(3);
BST.Insert(99);
BST.Insert(22);
Console.WriteLine("traversing with InOrder...");
BST.InOrder(BST.root);
Console.WriteLine();
Console.WriteLine();
Console.WriteLine("traversing with PreOrder...");
BST.PreOrder(BST.root);
Console.WriteLine();
Console.WriteLine();
Console.WriteLine("traversing with PostOrder...");
BST.PostOrder(BST.root);
Console.WriteLine();
Console.WriteLine();
}
}
}

how to Create a Binary Tree(C#)

namespace BinaryTree
{
public class Node
{
public int Data;
public Node Left;
public Node Right;
public void DisplayNode()
{
Console.WriteLine(Data+" ");
}
}

public class BinarySearchTree
{
public Node root;
public BinarySearchTree()
{
root = null;
}
public void Insert(int i)
{
Node newNode = new Node();
newNode.Data = i;
if (root == null)
{
root = newNode;
}
else
{
Node Current = root;
Node Parent;
while (true)
{
Parent = Current;
if (i < Parent.Data)
{
Current = Current.Left;
if (Current == null)
{
Parent.Left = newNode;
break;
}
}
else
{
Current = Current.Right;
if (Current == null)
{
Parent.Right = newNode;
break;
}
}
}
}
}

}

class Program
{
static void Main(string[] args)
{
BinarySearchTree BST = new BinarySearchTree();
Random rd = new Random();
for (int i = 0; i < 10; i++)
{
BST.Insert(rd.Next(30));
}
}
}
}

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("~~~~~~~~~~~~~");
}
}
}

Monday, October 13, 2008

Hashtable class(c#)

***********************this method missed a value, so we have to use better length in string array

namespace HashtableClass
{
class Program
{
static void Main(string[] args)
{
string [] names = new string[99];
string name;
string[] someNames = new string[] {

"David","Jennifer","Donnie","Mayo","Raymond",
"Bernica","Mike","Clayton","Beata","Michael"};
int hashVal;
for (int i = 0; i < 10; i++)
{
name = someNames[i];
hashVal = SimpleHash(name, names);
names[hashVal] = name;
}
ShowDistrib(names);
}

static int SimpleHash(string s, string[] arr)
{
int tot = 0;
char[] cname;
cname = s.ToCharArray();
for (int i = 0; i < cname.GetUpperBound(0); i++)
{
tot += (int)cname[i];
}

return tot % arr.GetUpperBound(0);
}

static void ShowDistrib(string[] arr)
{
for (int i = 0; i < arr.GetUpperBound(0); i++)
{
if (arr[i] != null)
{
Console.WriteLine(i+" "+arr[i]);
}
}
}
}
}


************************this is a better function
namespace HashtableClass
{
class Program
{
static void Main(string[] args)
{
string [] names = new string[10007];//10007 is the best length for hash table
string name;
string[] someNames = new string[] {

"David","Jennifer","Donnie","Mayo","Raymond",
"Bernica","Mike","Clayton","Beata","Michael"};
int hashVal;
for (int i = 0; i < 10; i++)
{
name = someNames[i];
hashVal = SimpleHash(name, names);
names[hashVal] = name;
}
ShowDistrib(names);
Console.WriteLine("search 'David' with function InHash.....");
InHash("David", names);
Console.WriteLine("search 'Dav' with function InHash.....");
InHash("Dav", names);
}

static int SimpleHash(string s, string[] arr)
{
int tot = 0;
char[] cname;
cname = s.ToCharArray();
for (int i = 0; i < cname.GetUpperBound(0); i++)
{
tot += 37*tot + (int)cname[i];//***
}
tot = tot % arr.GetUpperBound(0);
if (tot < 0)//***
{
tot += arr.GetUpperBound(0);
}
return tot;
}

static void ShowDistrib(string[] arr)
{
for (int i = 0; i < arr.GetUpperBound(0); i++)
{
if (arr[i] != null)
{
Console.WriteLine(i+" "+arr[i]);
}
}
}

static void InHash(string s, string[] arr)
{
int hval = SimpleHash(s,arr);
if (arr[hval] == s)
{
Console.WriteLine("True");
}
else
{
Console.WriteLine("False");
}
}
}
}

******************************************
///
/// some time,a hash function returns the same value for two data items(collision),
/// one solution to the collision problem is to implement the hash table using buckets.
/// when using bucket hashing, the most important thing you can do is keep the number
/// of arraylist elements used as low as possible. this minimize the extra work that
/// has to be done when adding items to or removing items from the hash table.
///

public class BucketHash
{
private const int SIZE = 101;
ArrayList[] data;
public BucketHash()
{
data = new ArrayList[SIZE];
for (int i = 0; i < SIZE; i++)
{
data[i] = new ArrayList(4);
}
}

public int Hash(string s)
{
long tot = 0;
char[] charray;
charray = s.ToCharArray();
for (int i = 0; i < s.Length; i++)
{
tot += 37 * tot + (int)charray[i];
}
tot = tot % data.GetUpperBound(0);
if (tot < 0)
{
tot += data.GetUpperBound(0);
}
return (int)tot;
}

public void Insert(string item)
{
int hash_value;
hash_value = Hash(item);
if (data[hash_value].Contains(item))
{
data[hash_value].Add(item);
}
}

public void Remove(string item)
{
int hash_value;
hash_value = Hash(item);
if (data[hash_value].Contains(item))
{
data[hash_value].Remove(item);
}
}
}
*****************************************
//please import the System.Collections
static void Main(string[] args)
{
//begin to sue hashtable
Hashtable symbols = new Hashtable(25);
symbols.Add("salary", 100000);
symbols.Add("name","Mike");
symbols.Add("age", 45);
symbols.Add("dept", "Information Technology");
symbols["sex"] = "Male";
Console.WriteLine("this is a test about using hash table...");
Console.WriteLine();
foreach (object key in symbols.Keys)
{
Console.WriteLine(key.ToString()+" : "+symbols[key].ToString());
}
Console.WriteLine();
symbols.Remove("sex");
foreach (object key in symbols.Keys)
{
Console.WriteLine(key.ToString() + " : " + symbols[key].ToString());
}
Console.WriteLine();
Console.WriteLine("to retrieve the 'name'...");
if (symbols.ContainsKey("name"))
{
Console.WriteLine("found the name: " + symbols["name"].ToString());
}
else
{
Console.WriteLine("not exist...");
}
//end hashtable
}

数据结构要点复习

数据结构要点复习


一 基本概念
1.数据:可以被计算机识别,存储和加工处理的符号的总称。
2.数据元素:数据的基本单位,有时,一个数据元素可由若干个数据项组成。
3.数据项:数据不可分割的最小单位。
4.数据对象:性质相同的数据元素的集合,是数据的一个子集
5.数据结构:数据之间的相互关系,包含3个方面的内容:
===>数据的逻辑结构,也就是数据元素之间的逻辑关系。数据的逻辑结构可以分为线性结构和非线性结构。
===>数据的存储结构:数据及其逻辑结构载存储器中的实现方式。
===>对数据可进行的操作:主要包括:查找,插入,删除,修改和排序等。

二 算法的描述和分析
1.算法:由有限条指令组成,规定了解决特定问题的一系列操作。
2.算法特性:算法具有有限性,确定性,输入,输出和可行性五个特性
===>有限性:任何一条指令都只能执行有限次,即算法必须载执行有限步后结束。
===>确定性:算法中每条指令的含义必须明确,不允许由二义性
===>输入:一个算法的输入可以包含零个或多个数据。
===>输出:算法有一个或多个输出
===>可行性:算法中待执行的操作都十分基本,算法应该在有限时间内执行完毕。
3.算法评价:一个好的算法应该考虑以下5条准则:
===>正确性:对一切合法的输入数据,该算法经过有限时间(算法意义上的有限)的执行都能产生正确的结果
===>时间复杂性:算法执行的实际时间是随着所用的计算机系统而改变的;而算法所执行的语句条数又依赖于算法设计者采用的算法描述语言和算法的设计风格。所以,用一个算法的基本(!!)运算次数来作为算法的时间复杂度并以此来衡量算法的时间效率。要注意的是,一个算法所执行的基本运算次数常常因输入不同而异,与输入规模和输入数据的性质有关。
===>空间复杂度:一个算法执行所需要的存储空间,用于存储语句,常数,变量,中间结果等。
在算法执行的不同时间,其空间复杂度也是不同的。注意:降低算法的时间复杂度和空间复杂度有时是冲突的,需要在这两者之间进行衡量。但算法的时间复杂度往往比算法的空间复杂度更加重要。
===>可读性:可读性好的算法有助于设计者和他人阅读,理解,修改和重用。
===>坚固性:在输入非法数据时,算法能适当地作出合适的反应。
4.算法时间复杂度的分析:一般情况下,计算一个算法的基本运算次数是相当困难的,甚至是不可能的(因为算法的不同输入往往产生不同的运算次数,而一个算法的所有不同输入的数目可能十分庞大)。一种可行的方法是计算算法的平均运算次数。这样的结果在实际中可能不是特别有用,因为某些输入较其他输入可能更经常出现,所以对数目足够的不同输入的加权平均将会给出更有意义的结果。

三 数组和字符串
1.稀疏矩阵
===>设矩阵Amn中有s个非零元素,若s远远小于矩阵元素的总数(即s<===>稀疏矩阵的压缩存储
为了节省存储单元,可只存储非零元素。由于非零元素的分布一般是没有规律的,因此在存储非零元素的同时,还必须存储非零元素所在的行号、列号,才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。其中每一个非零元素所在的行号、列号和值组成一个三元组(i,j,aij),并由此三元组惟一确定。
稀疏矩阵进行压缩存储通常有两类方法:顺序存储和链式存储。
===>三元组表
将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素),并依次存放在向量中,这种稀疏矩阵的顺序存储结构称为三元组表。
===>稀疏矩阵的链式结构
当稀疏矩阵中非零元的位置或个数经常变动时,三元组就不适合于作稀疏矩阵的存储结构,此时,采用链表作为存储结构更为恰当。 稀疏矩阵的链式结构有十字链表等方法
十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法,在该方法中:
矩阵的每一行和每一列都设置一个由表头结点引导的循环(!!!)链表
每一个非零元用一个结点表示,结点中除了表示非零元所在的行(row)、列(col)和值(val)的域外,还需增加两个链域:行指针域(right),用来指向本行中下一个非零元素;列指针域(down) ,用来指向本列中下一个非零元素。


四 队列和栈
栈是后进先出的,队列是先进先出的;
队列的入队序列=出队序列
栈的入栈序列!=出栈序列,由多种可能性。
例见《全国计算机等级考试应试指导及模拟试题集四级》
P58 例1 P64 例14 P71 45 P76 79
P74 65,69。

五 线性表
===>除第一个元素和最后一个元素外,其他每个元素都有且仅有一个直接前驱和一个直接后继;线性表可以为空。
===>线性表中的元素不需要按递增(减)的顺序排列
===>线性表的顺序存储:必须占用一片连续的存储单元,便于随即存取表中的任一元素,但不利于插入删除操作。
===>线性表的链式存储:不必占用连续的存储空间,只适于顺序存取,便于插入删除操作

六 树:
1. 相关概念:
1.)树:树(Tree)是n(n≥0)个结点的有限集。在任意一颗非空树中
(1)有且仅有一个特定的称为根(Root)的结点
(2)当n>1时,其余结点可以分为m(m>0)个互不相交的有限集,其中每一个集合本身又是一颗树,并且称为根的子树。
2.)结点的度:结点拥有的子树数
3.)叶子:度为0的结点称为叶子或终端结点。
4.)树的度:树内各结点的度的最大值。
5.)孩子和双亲:结点的子树的根称为该结点的孩子,相应地,该结点称为孩子的双亲(双亲是一个结点,而不是两个结点!)
5.)兄弟:同一个双亲的孩子之间互称为兄弟。
6.)祖先:从根到该结点所经分支上的所有结点。
7.)子孙:以某结点为根的子树中的任一结点都称为该结点的子孙。
8.)堂兄弟:其双亲在同一层的结点互为堂兄弟。
9.)有序/无序树:如果将树中结点的各子树看成是从左到右有次序的(不能互换),则称该树为有序树,否则为无序树。
10.)森林:森林是m颗互不相交的树的集合。
11.)二叉树:每个结点至多只有二颗子树的有序树。
12.)满二叉树:深度为k且有2的k次方-1个结点的二叉树(具备所有可能的结点)。
13.)完全二叉树:深度为k有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树

2. 树的高度(或深度):
就是树中结点的最大层次(树最高一层的层次)。
有两种情况。假设树总共有三层,
若设根的层次为0,则高h为2
若设根的层次为1,则高h为3。
无特别声明的时候,通常认为根的层次为1(解题时特别要注意这一点)。
3. 树的结点的相关计算
1.)对所有的树均有:叶子结点=度为0的结点
非叶子结点=度>0的结点
叶子结点+非叶子结点=总结点
2.)对任意一棵树,若度为n,且度为m的结点树为Pm(m=1,2,3,4.....)则有:
总结点树=1+1*P1+2*P2+3*P3+4*P4+.......+n*Pn (加1是表示根结点)
非叶子结点数=P1+P2+P3....+P*n.
叶子结点数=总结点数-叶子结点数。
例见《全国计算机等级考试应试指导及模拟试题集四级》P63 例8
4. 二叉树:
1.)定义:二叉树是每个结点至多只有二颗子树的有序树。
2.)二叉树的性质(设根的层次为1)
(1)第i层上最多有2的(i-1)次方个结点。
(2)若二叉树的高度为h,则二叉树最多有2的h次方-1个结点,此时二叉树即为满二叉数。
(3)对任意一颗二叉树,如果其叶子结点(度为0)的结点数为n0,度为2的结点树为n2,则n0=n2+1
例见《全国计算机等级考试应试指导及模拟试题集四级》P68 13,23,33,46,81,83。
5 完全二叉树:
1.)定义:深度为k有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。
2.)性质:
===>若将最高一层除去,则剩下的二叉树为满二叉树。(若深度为k有n个结点,则n>2的(k-1)次方-1)
===>叶子结点只可能出现在层次最大的两层上。
===>具有n个结点的完全二叉树的深度为[Log2 n]+1
===>对n个结点的完全二叉树编号,则对任一结点i有
--->结点i的双亲是[i/2] (i>1)
--->结点i的左孩子是结点2i (2i≤n)
--->结点i的右孩子是结点2i+1 (2i+1≤n)
6. 树的特性
===>二叉树的度不一定为2;
===>根据同一颗二叉树的两种遍历顺序,可唯一地确定一颗二叉树(也可以得到用另一种遍历方法得到的遍历序列)
===>二叉树的三种遍历方法所得到的遍历序列中,所有叶子结点之间的相对顺序不变。
7. 二叉树的存储
1.)分为数组存储和链表存储
2.)顺序存储--数组表示法:采用一组连续存储空间存储二叉树结点中的数据元素。
仅适用于完全二叉树,当用于存储一般二叉树时,一个主要的问题是空间利用率低。
3.)链表表示法:链表比较适合存储一般的二叉树;通常将树中的每一个元素用一个结点表示,结点一般包括三个域,即元素的数值,指向其左孩子结点的指针和指向其右孩子结点的指针,称为二叉链表。
4.)三叉链表:在二叉链表的基础上,加上一个指向结点的双亲的指针,这样就可以方便的找到一个结点的父结点。
8. 树的遍历
1.)四种方法:先根(序)遍历,中根(序)遍历,后根(序)遍历,层次遍历。
2.)遍历二叉树所得到的遍历序列中:
--->三种遍历序列中,叶子结点的相对顺序相同。 参见《全国计算机等级考试应试指导及模拟试 题集四级》P64例18
--->先根遍历序列:根结点+左子树结点群+右子树结点群
中根遍历序列:左子树结点群+根结点+右子树结点群
后根遍历序列:左子树结点群+右子树结点群+根结点
例见《全国计算机等级考试应试指导及模拟试题集四级》P65 例18 P82 140
--->由任意二种遍历序列可唯一确定一颗二叉树 P77 86,89,141
3.)二叉排序树的中根遍历得到一个递增序列。
4.)层次遍历:从二叉树的第一层(根结点)开始,自上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。
在进行层次遍历时,对一层结点访问完后,再按照它们的访问顺序对各个结点的左孩子和右孩子顺序访问。
9. 线索二叉树:对二叉树以某种方式遍历后,得到二叉树中所有结点的一个线性序列。这样,二叉树中的结点就有了唯一直接前驱结点和唯一直接后继结点。
在线索二叉树时,二叉树采用二叉链表作为存储结构,每个结点有五个域leftChild,leftTag,data,rightTag,rightChild
规定:如果某结点的左指针域为空,令其指向依某种方式遍历时所得到的该结点的前驱结点,否则指向左孩子。
如果某结点的右指针域为空,令其指向依某种方式遍历时所得到的该结点的后继结点,否则指向右孩子(??)
为了区分一个结点的指针是指向左右孩子还是指向前驱,后继结点,可用标志为来区分:
如果 leftTag/rightTag=0,那么指向左/右孩子。
如果 leftTag/rightTag=1,那么指向前驱/后继线索。
对一颗二叉树的遍历方法不同,得到的线索二叉树也不同。通常有前序线索二叉树,中序线索二叉树,后序线索二叉树。
10.哈夫曼树
1.)路径:在一颗二叉树中由根结点到某个结点所经过的分支序列叫做由根结点到这个结点的路径。
2.)路径的长度:由根结点到某个结点所经过的分支数称为由根结点到该结点的路径长度。
3.)二叉树的路径长度:由根结点到所有叶结点(!!)的路径长度之和称为该二叉树的路径长度。!!
4.)二叉树的带权路径长度:设一颗具有n个带权值叶结点(!!)的二叉树,从根结点到各个叶结点(!!)的路径长度与对应叶结点权值的乘积之和叫做二叉树的带权路径长度WPL!!!
5.)哈夫曼树(最优二叉树):对于一组确定权值的叶结点,可以构造出多重不同形态的二叉树,它们的带权路径长度也不同 ,把其中带权路径长度最小的二叉树称为最优二叉树,也叫哈夫曼树!!!!
6.)构造哈夫曼树:要使一颗二叉树的WPL最小,显然必须使权值越大的叶结点越靠近根结点。
构造哈夫曼树的方法是:
===>将给定的n个权值看做是n颗只有一个结点的二叉树,就构成了森林F
===>在森林F中选两颗根结点(!!)的权值最小的二叉树Ti,Tj,分别作为左子树,右子树构造一棵新的二叉树Tk,置Tk的根结点的劝止为(Ti根结点的权值+Tj根结点的权值)
===>在F中删去二叉树Ti,Tj,将新的Tk加入森林F
===>重复步骤(2),(3)直到F中仅剩下一颗树为止。
11. 树,森林和二叉树的转换
1.)树---->二叉树
由于二叉树是有序的,所以约定树中每一个结点的孩子结点按从左到右的次序顺序编号。
树---->二叉树:连线--删线----美化
===>连线:树中所有相邻兄弟连线
===>删线:对每个结点,只保留它与第一个孩子结点之间的连线。
===>美化
由这个转化过程可知:
树中任意一个结点P的第一个孩子结点---->二叉树中结点P的左孩子结点
树中任意一个结点P的第一个右兄弟----->二叉树中结点P的右孩子结点
树转化成的二叉树根结点没有右子树(因为原树的根结点不可能有兄弟,所以转化后根结点也不可能有右子树,这一个性质在森林转化为一颗二叉树的过程中得到了体现)

2.)森林--->二叉树
(1)森林中的每颗树---->二叉树
(2)从第二颗二叉树开始,依次把当前的二叉树作为前一颗二叉树结点的右子树
森林转化成的二叉树是有右子树的。
3.)二叉树---->树/森林
(1)连线:P是F的左孩子,那么把P沿右分支找到的所有结点和F连起来
(2)删线:删除二叉树中所有结点和其右孩子结点之间的连线
(3)美化
照这个步骤转化,如果原二叉树有右子树,则会转化为森林,如果没有,则会转化为树。

七 图
图的邻接矩阵:
若图中没有结点到自己的边,那么对角线上全是0;
若为无向图,则邻接矩阵关于对角线对称:A[i,j]和A[j,i]都是表示结点Vi,Vj之间的边。
若为有向图,则邻接矩阵通常不对称,A[i,j]是由Vi到Vj的边,A[j,i]是Vj到Vi的边。

图的遍历:深度遍历和广度遍历
深度优先遍历DFS:深度遍历是从图中的任一个结点V1出发,访问V1的一个邻接点V2,再访问V2的邻接点V3,再访问V3的邻接点V4.....直到访问到Vn,而Vn的所有邻接点都已被访问过了,这时开始回溯,访问V(n-1)结点的未被访问过的邻接点,如果V(n-1)的邻接点都已被访问过了,则回溯到V(n-2)结点,访问它的邻接点......(!!????)
广度优先遍历BFS:略

最短路径:略(????)

例见《全国计算机等级考试应试指导及模拟试题集四级》P60例4

八 排序
1. 稳定和不稳定的排序方法
排序可以按照主关键字来排,也可以按次关键字来排
如果按次关键字来排序,且关键字Ki=Kj,且排序前记录Ri领先于Rj,那么如果在排序后的序列中Ri还是领先于Rj,那么称所用的排序方法是稳定的;反之,若可能(!!)使排序后的序列中Rj领先于Ri,那么称排序方法是不稳定的。
2. 内部排序和外部排序
根据待排序的记录数量和排序过程中涉及的存储器的不同,可将排序方法分为两大类:
内部排序:待排序记录存放在计算机随机存储器中进行的排序
外部排序:因为待排序的记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序。
3. 内部排序:
1.)分类:按照排序过程依照的原则可分为:插入排序,交换排序,选择排序,归并排序和基数排序。
2.)排序操作:在排序过程中需进行以下两种基本操作
(1)比较两个关键字的大小。
(2)将记录从一个位置移动到另一个位置。
3.)插入排序:有直接插入排序,折半插入排序,2-路插入排序,表插入排序等。
(1)直接插入排序:排序思想是将一个记录插入到已排好序的有序表中,得到一个新的有序表。
空间复杂度:需要一个记录的辅助空间;
时间复杂度:O(n*n);
(2) 折半插入排序:由于直接插入排序的基本操作是在一个有序表中进行查找和插入,因此,这个“查找”可以用“折半查找”来实现,由此进行的插入排序称之为折半插入排序。
空间复杂度和时间复杂度不变。
(3)2-路插入排序:参见课本P267;
(4)表插入排序:参见课本P268
4.)希尔(Shell)排序:由直接插入算法改进而来;
(1)排序思想:先将整个待排记录序列分割成为若干个子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。
(2)优点:对子序列进行直接插入排序使整个序列“基本有序”后,只要做记录的少量比较和移动即可完成排序,因此降低了时间复杂度
(3)希尔排序的分析是一个复杂的问题,究竟时间复杂度为多少还没有一个定论。
5.)快速(交换)排序:借助“交换”进行排序的方法。
(1)冒泡排序:
排序思想:将表中元素两个相邻元素依次比较,若不符合排序要求,则交换位置,这样经过了n-1次比较后,将确定出最大(或最小)元素的位置,称为一趟扫描。经过n-1次扫描后,就完成了整个表的排序。
时间复杂度:O(n*n)
(2)快速排序:
排序思想:通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
一趟快速排序的具体做法是:附设两个指针low和high,它们的初值分别low和high,设枢轴记录(任选一个关键字, 通常可选第一个记录)的关键字为pivotkey,则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换,然后从low所指位置起向后搜索,找到第一个关键字大于pivotkey的记录和枢轴记录互相交换重复这两步直到low=high位置。这是一趟排序。接着对这两个部分重复这样排序(要用到递归算法)
注意,在一趟排序过程中,pivotkey是始终不变的。
6.)选择排序:
(1)简单选择排序:一趟简单选择排序的操作为:通过n-i次关键字间的比较,从n-i+1个记录中选取关键字最小的记录,并和第i个记录交换。
简单选择排序所需进行记录移动的操作次数比较少,最小伪,最大为3(n-1)
无论记录的初始排列如何,所需进行的关键字的比较次数相同,均为n(n-1)/2;
时间复杂度为O(n*n);
(2)树形选择排序:选择排序的主要操作是进行关键字之间的比较,因此改进简单选择排序应该从如何减少“比较”出发考虑。
树形选择排序的思想:首先对n个记录的关键字两两比较,然后在其中[n/2]个较小者之间再两两比较,如此重复,直到选出最小关键字的记录为止。
时间复杂度:O(n*log2 n)
缺点:需要较多辅助存储空间,进行多余的比较等。
(3)堆排序(Heap Sort)
堆的定义:n个元素的序列,当且仅当满足下面关系时,称为堆。
ki≤k2i && ki≤k(2i+1)
或ki≥k2i && ki≥k(2i+1)
若将和此序列对应的一维数组看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左右孩子结点的值。,由此,若序列是堆,那么堆顶元素(完全二叉树的根)必为序列中n个元素的最小值(或最大值)。
若在输出堆顶的最小值后,使得剩余的n-1个元素的序列重右建成一个堆,则得到n个元素中的次小值,如此反复执行,便能得到一个有序序列,这个过程称为堆排序。
堆排序对记录数较大的文件比较有效。
7.)归并排序:“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表,
排序思想:将初始序列看做是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2]个长度为2或1的有序子序列,再两两归并.....如此重复,直至得到一个长度为n的有序序列为。这种排序方法称为2-路归并排序。
2-路归并排序的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。
归并排序的最大特点是:它是一种稳定的排序方法。
8.)基数排序:实现基数排序不需要进行记录关键字之间的比较。
基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法

Dictionary Base----key value pair

content for test.txt :Mike,192.155.12.1,David,192.155.12.2,Bernica,192.155.12.3
*****************************************
using System.Collections;//
namespace DictionaryBaseTest
{
public class IPAddresses : DictionaryBase
{
public IPAddresses()
{ }
public void Add(string name, string ip)
{
base.InnerHashtable.Add(name, ip);
}
public string Item(string name)
{
return base.InnerHashtable[name].ToString();
}
public void Remove(string name)
{
base.InnerHashtable.Remove(name);
}
}

class Program
{
static void Main(string[] args)
{
IPAddresses myIPs = new IPAddresses();
myIPs.Add("Mike", "192.155.12.1");
myIPs.Add("David", "192.155.12.2");
myIPs.Add("Bernica", "192.155.12.3");
Console.WriteLine("There are "+myIPs.Count+" IP addresses");
Console.WriteLine("David's IP is: "+myIPs.Item("David"));
myIPs.Clear();
Console.WriteLine("There are " + myIPs.Count + " IP addresses");
}
}
}
*******************************************
using System.Collections;//DictionaryBase
using System.IO;//StreamReader
namespace DictionaryBaseTest
{
public class IPAddresses : DictionaryBase
{
public IPAddresses()
{
}
public IPAddresses(string txtFile)
{
string line;
string[] words;
StreamReader inFile;
inFile = File.OpenText(txtFile);
while (inFile.Peek() != -1)
{
line = inFile.ReadLine();
words = line.Split(',');
this.InnerHashtable.Add(words[0],words[1]);
this.InnerHashtable.Add(words[2], words[3]);
this.InnerHashtable.Add(words[4], words[5]);
}
inFile.Close();
//foreach (string str in words)
//{
// Console.WriteLine(str);
//}
//Console.WriteLine(line);
}
public void Add(string name, string ip)
{
base.InnerHashtable.Add(name, ip);
}
public string Item(string name)
{
return base.InnerHashtable[name].ToString();
}
public void Remove(string name)
{
base.InnerHashtable.Remove(name);
}
}

class Program
{
static void Main(string[] args)
{
IPAddresses myIPs = new IPAddresses("e:\\fund\\test.txt");

Console.WriteLine("There are " + myIPs.Count + " IP addresses");

Console.WriteLine("Mike's IP is: " + myIPs.Item("Mike"));
Console.WriteLine("David's IP is: " + myIPs.Item("David"));
Console.WriteLine("Bernica's IP is: " + myIPs.Item("Bernica"));
Console.WriteLine();
}
}
}
**********************************************
using System.Collections;//DictionaryBase
using System.IO;//StreamReader
namespace DictionaryBaseTest
{
public class IPAddresses : DictionaryBase
{
public IPAddresses()
{
}
public IPAddresses(string txtFile)
{
string line;
string[] words;
StreamReader inFile;
inFile = File.OpenText(txtFile);
while (inFile.Peek() != -1)
{
line = inFile.ReadLine();
words = line.Split(',');
this.InnerHashtable.Add(words[0],words[1]);
this.InnerHashtable.Add(words[2], words[3]);
this.InnerHashtable.Add(words[4], words[5]);
}
inFile.Close();
//foreach (string str in words)
//{
// Console.WriteLine(str);
//}
//Console.WriteLine(line);
}
public void Add(string name, string ip)
{
base.InnerHashtable.Add(name, ip);
}
public string Item(string name)
{
return base.InnerHashtable[name].ToString();
}
public void Remove(string name)
{
base.InnerHashtable.Remove(name);
}
}

class Program
{
static void Main(string[] args)
{
IPAddresses myIPs = new IPAddresses("e:\\fund\\test.txt");

Console.WriteLine("There are " + myIPs.Count + " IP addresses");

DictionaryEntry[] ips = new DictionaryEntry[myIPs.Count];
myIPs.CopyTo(ips, 0);
for (int i = 0; i <= ips.GetUpperBound(0); i++)
{
//Console.WriteLine(ips[i]);
Console.WriteLine(ips[i].Key);
Console.WriteLine(ips[i].Value);
}
}
}
}
****************************************
static void Main(string[] args)
{
KeyValuePair[] book = new KeyValuePair[10];
book[0] = new KeyValuePair("Mike",99);
book[1] = new KeyValuePair("David", 88);
book[2] = new KeyValuePair("Bernica", 77);
for (int i = 0; i < book.GetUpperBound(0); i++)
{
if (book[i].Value != 0)
{
Console.WriteLine(book[i].Key+" : "+book[i].Value);
}
}
Console.WriteLine();
}
******************************************
static void Main(string[] args)
{
SortedList myIPs = new SortedList();

myIPs.Add("Mike", "192.155.12.1");
myIPs.Add("David", "192.155.12.2");
myIPs.Add("Hernica", "192.155.12.3");
for (int i = 0; i < myIPs.Count; i++)
{
Console.WriteLine("Name: "+myIPs.GetKey(i)+" "+"IP: "+myIPs.GetByIndex(i));
}
}

Sunday, October 12, 2008

Regular Expression (C#)

using System.Text.RegularExpressions;//
namespace RegularExpression
{
///
/// this method only match the first position
///

class Program
{
static void Main(string[] args)
{
string input= "the quick brown fox jumped over the lazy dog";
Regex reg = new Regex("the");//define the match metacharacter
Match matchSet;
int matchPos;
matchSet = reg.Match(input);//veryfy the string with the metacharcters
if (matchSet.Success)//if there's matched string, return true
{
matchPos = matchSet.Index;
Console.WriteLine("found the match at position: "+matchPos);
}
}
}
}

***************************************************
using System.Text.RegularExpressions;//
namespace RegularExpression
{
///
/// this method match mutiple position
///

class Program
{
static void Main(string[] args)
{
string input= "the quick brown fox jumped over the lazy dog";
Regex reg = new Regex("the");//define the match metacharacter
MatchCollection matchSet;
matchSet = reg.Matches(input);
if (matchSet.Count > 0)
{
foreach (Match aMatch in matchSet)
{
Console.WriteLine("found a match at: "+aMatch.Index);
}
}
Console.WriteLine();
}
}
}
**********************************************
using System.Text.RegularExpressions;//
namespace RegularExpression
{
///
/// regular expression also has a Replace method
///

class Program
{
static void Main(string[] args)
{
string input= "the quick brown fox jumped over the lazy dog";
Regex reg = new Regex("the");//define the match metacharacter
input = Regex.Replace(input, "brown", "black");
Console.WriteLine(input);
}
}
}
*****************************
using System.Text.RegularExpressions;//
namespace RegularExpression
{
///
///
///

class Program
{
static void Main(string[] args)
{
string[] words = new string[]{"bad","boy","baaad","bear","bend","ba"};
foreach (string word in words)
{
if (Regex.IsMatch(word, "ba+"))
{
Console.WriteLine(word);
}
}
}
}
}
*****************************
using System.Text.RegularExpressions;//
namespace RegularExpression
{
///
///
///

class Program
{
static void Main(string[] args)
{
string[] words = new string[]{"bad","boy","baaad","bear","bend","baad"};
foreach (string word in words)
{
if (Regex.IsMatch(word, "ba{2}d"))
{
Console.WriteLine(word);
}
}
}
}
}
********************************
using System.Text.RegularExpressions;//
namespace RegularExpression
{
///
///
///

class Program
{
static void Main(string[] args)
{
string[] words = new string[]{"part","of","this","string","is","bold"};
//string regExp = "<.*>";//this is a kind of expression
//string regExp = "<.+>";//
string regExp = "<.+?>";//try these three expressions
MatchCollection aMatch;
foreach (string word in words)
{
if (Regex.IsMatch(word, regExp))
{
aMatch = Regex.Matches(word,regExp);
for (int i = 0; i < aMatch.Count; i++)
{
Console.WriteLine(aMatch[i].Value);
}
}
}
}
}
}
***********************************
using System.Text.RegularExpressions;//
namespace RegularExpression
{
///
///
///

class Program
{
static void Main(string[] args)
{
string input = "the quick brown fox jumped over the lazy dog";
MatchCollection matchSet;
//matchSet = Regex.Matches(input,".");//out put all characters index
matchSet = Regex.Matches(input, "t.e");//out put two "the" characters index
foreach (Match aMatch in matchSet)
{
Console.WriteLine("matches at: "+aMatch.Index);
}
}
}
}

**************************************
using System.Text.RegularExpressions;//
namespace RegularExpression
{
///
///
///

class Program
{
static void Main(string[] args)
{
string input = "THE quick BROWN FOX JUMPED OVER THE LAZY dog";
MatchCollection matchSet;
//matchSet = Regex.Matches(input,".");//out put all characters index
matchSet = Regex.Matches(input, "[a-z]");//out put two "the" characters index
foreach (Match aMatch in matchSet)
{
Console.WriteLine("matches at: "+aMatch.Index);
}
}
}
}
***************************************
using System.Text.RegularExpressions;//
namespace RegularExpression
{
///
///
///

class Program
{
static void Main(string[] args)
{
string[] words = new string[] { "heal","heel","noah","techno"};
//string regExp = "^h";//match at the beginning of word
string regExp = "h$";//match at the end of word
Match aMatch;
foreach (string word in words)
{
if (Regex.IsMatch(word, regExp))
{
aMatch = Regex.Match(word, regExp);
Console.WriteLine("Matched: "+word+" at position: "+aMatch.Index);
}
}
}
}
}
**************************************
using System.Text.RegularExpressions;//
namespace RegularExpression
{
///
///
///

class Program
{
static void Main(string[] args)
{
string words = "08/14/1957 46 02/12/1959 45 08/09/1985 18 03/25/1988 15

09/09/1990 13";
string regExp = "(\\s\\d{2}\\s)";//method to get the age
string regBirthDay = "(?(\\d{2}/\\d{2}/\\d{4}))\\s";//method to get the

birth day

MatchCollection matchSet = Regex.Matches(words,regExp);
foreach (Match aMatch in matchSet)
{
Console.WriteLine(aMatch.Groups[0].Captures[0]);
}
MatchCollection matchSetDate = Regex.Matches(words,regBirthDay);
foreach (Match amatch in matchSetDate)
{
Console.WriteLine("Date: "+amatch.Groups["dates"]);
}
}
}
}

还是单链表排序的问题(C#)

这个问题是一个叫wartim的仁兄提供的代码,很方便。谢谢

namespace WindowsFormsApplication34
{
public partial class Form1 : Form
{
public class LinkedList
{
public LinkedList node = null;
public int data;
}

class Tree
{
public Tree Left = null;
public Tree Right = null;
public int Value;
}

LinkedList LL, Head;
Tree T = null;

public Form1()
{
InitializeComponent();
LinkedList Temp = null;

// 给 LL 赋点值。。。
LL = new LinkedList();
LL.data = 10;
Temp = LL;
LL = new LinkedList();
LL.data = 34;
LL.node = Temp;
Temp = LL;
LL = new LinkedList();
LL.data = 6;
LL.node = Temp;
Temp = LL;
LL = new LinkedList();
LL.data = 52;
LL.node = Temp;
Temp = LL;
LL = new LinkedList();
LL.data = 6;
LL.node = Temp;
Temp = LL;
LL = new LinkedList();
LL.data = 7;
LL.node = Temp;
Head = LL;

// 构建排序二叉树
for (LL = Head; LL != null; LL = LL.node)
AddToTree(ref T, LL.data);

// 输出排序结果
String S = String.Empty;
GetResult(ref T, ref S);
MessageBox.Show(S);
}

private void Form1_Load(object sender, EventArgs e)
{

}

void AddToTree(ref Tree T, int value)
{
if (T == null)
{
T = new Tree();
T.Value = value;
}
else if (value < T.Value) // 比当前值小于的往左
AddToTree(ref T.Left, value);
else if (value >= T.Value) // 比当前值大于等于的往右
AddToTree(ref T.Right, value);
}

void GetResult(ref Tree T, ref String S)
{
if (T == null)
return; // 已经没有节点了
if (T.Left != null)
GetResult(ref T.Left, ref S); // 向左走
S += T.Value.ToString() + " ";
if (T.Right != null)
GetResult(ref T.Right, ref S); // 向右走
}
}
}

单链表排序问题(C#)

只是个一直困然我的问题,单链表排序。如果谁有更简单的方法,希望各位不吝赐教。
题目就是:一个单链表(LinkedList),里面存储着整形数据,但是是无序排列的,请写一个方法,将它按升序排列。


namespace testSortLinklist
{
public class Employee : IComparable<Employee>
{
private string name;
public Employee(string name)
{
this.name = name;
}
public override string ToString()
{
return this.name;
}

public int CompareTo(Employee rhs)
{
return this.name.CompareTo(rhs.name);
}
public bool Equals(Employee rhs)
{
return this.name == rhs.name;
}
}

public class Node<T> : IComparable<Node<T>> where T : IComparable<T>
{
private T data;
private Node<T> next = null;
private Node<T> prev = null;

public Node(T data)
{
this.data = data;
}
public T Data
{
get
{
return this.data;
}
}
public Node<T> Next
{
get
{
return this.next;
}
}

public int CompareTo(Node<T> rhs)
{
return data.CompareTo(rhs.data);
}
public bool Equals(Node<T> rhs)
{
return this.data.Equals(rhs.data);
}

public Node<T> Add(Node<T> newNode)
{
if (this.CompareTo(newNode) > 0)
{
newNode.next = this;
if (this.prev != null)
{
this.prev.next = newNode;
newNode.prev = this.prev;
}
this.prev = newNode;
return newNode;
}
else
{
if (this.next != null)
{
this.next.Add(newNode);
}
else
{
this.next = newNode;
newNode.prev = this;
}
return this;
}
}

public override string ToString()
{
string output = data.ToString();
if (next != null)
output += ", " + next.ToString();
return output;
}
}

public class LinkedList<T> where T : IComparable<T>
{
private Node<T> headNode = null;

public T this[int index]
{
get
{
int ctr = 0;
Node<T> node = headNode;
while (node != null && ctr <= index)
{
if (ctr == index)
{
return node.Data;
}
else
{
node = node.Next;
}
++ctr;
}
throw new ArgumentOutOfRangeException();
}
}

public LinkedList()
{
}

public void Add(T data)
{
if (headNode == null)
{
headNode = new Node<T>(data);
}
else
{
headNode =headNode.Add (new Node<T>(data));
}
}

public override string ToString()
{
if (this.headNode != null)
return this.headNode.ToString();
else
return string.Empty;
}
}

class Program
{
static void Main(string[] args)
{
Run();
}
public static void Run()
{
LinkedList<int> myLinkedList = new LinkedList<int>();
Random rand = new Random();
Console.Write("Adding: ");
for (int i = 0; i < 10; i++)
{
int nextInt = rand.Next(30);
Console.Write("{0} ", nextInt);
myLinkedList.Add(nextInt);
}

LinkedList<Employee> employees = new LinkedList<Employee>();
employees.Add(new Employee ("John"));
employees.Add(new Employee("Paul"));
employees.Add(new Employee("George"));
employees.Add(new Employee("Ringo"));

Console.WriteLine(" Retrieving collections...");

Console.WriteLine("Integers: " + myLinkedList);
Console.WriteLine("Employees: " + employees);

Console.ReadKey();
}
}
}

Thursday, October 9, 2008

Remove some characters from string in C#

namespace RemoveCharacters
{
class Program
{
static void Main(string[] args)
{
string[] htmlComments = new string[] {"",
"",
"",
""};
char[] commentChar = new char[] { '!','-','<','>'};

Original(htmlComments);
Console.WriteLine("~~~~~~~~~~~~~~~~~~~~~");
RemoveCommentCharacter(htmlComments,commentChar);
Console.WriteLine("~~~~~~~~~~~~~~~~~~~~~");
RemoveWithReplace(htmlComments,commentChar);
}

public static void Original(string[] str)
{
for (int i = 0; i <= str.GetUpperBound(0); i++)
{
Console.WriteLine("Comments: "+str[i]);
}
}

public static void RemoveCommentCharacter(string[] str,char[] ch)
{
for (int i = 0; i <= str.GetUpperBound(0); i++)
{
str[i] = str[i].Trim(ch);
str[i] = str[i].TrimEnd(ch);
Console.WriteLine("Comments: " + str[i]);
}
}

public static void RemoveWithReplace(string[] str,char[] ch)
{
for (int i = 0; i <= str.GetUpperBound(0); i++)
{
for (int j = 0; j < ch.Length; j++)
{
str[i] = str[i].Replace(ch[j].ToString(),"");
}
Console.WriteLine("Comments: " + str[i]);
}
}
}
}

Merge two strings with C#

static void Main(string[] args)
{
string str1 = "hello";
string str2 = "kevin";
string str = string.Concat(str1," ",str2);//this is a good method to merge strings
Console.WriteLine(str);
string str3 = str1 + " " + str2;
Console.WriteLine(str3);
Console.WriteLine();
}