发信人: evilknights (只为一品香), 信区: DotNET        
标  题: C#的B+树程序
发信站: BBS 水木清华站 (Fri Dec 13 16:37:39 2002), 转信

我写的，为.NET做点宣传，大家随便看看。
using System;
using System.Xml;
using System.Xml.Serialization;
using System.IO;
namespace Kingsun
{
#region Node Definition Group
public class Pair//Each BPNode stores an array of Pair
{
  [XmlElement("pointer")]
  public object pointer;//BPNode leaves point to string,
  //BPNode internal nodes point to BPNode,a downcast will work when needed
  [XmlAttribute("key")]
  public int key;//The key value for this pair,in C#,'int' is 32-bit(4-byte)
,
      //so there is no need to define it as 'long'
  public Pair(int key,object pointer)
  {
   this.key=key;
   this.pointer=pointer;
  }
  public Pair()
  {
  }
}//class Pair
[XmlRoot("BPTroot")]
public class BPNode//The BPNode class
{
  [XmlAttribute("isLeaf")]
  public bool isLeaf;//True if this is a leaf
  [XmlElement("Pair")]
  public Pair[] recarray;//Array of key/pointer pairs
  [XmlAttribute("numrec")]
  public int numrec;//Number of pairs currently in node
  private BPNode leftptr,rightptr;//Each level forms a doubly-linked table
  public void setPrev(BPNode LNode)//protect leftptr from being serialized
  {
   leftptr=LNode;
  }
  public BPNode getPrev()
  {
   return leftptr;
  }
  public void setNext(BPNode RNode)//protect rightptr from being serialized
  {
   rightptr=RNode;
  }
  public BPNode getNext()
  {
   return rightptr;
  }
  public bool isFull//read-only property
  {
   get
   {
    if(numrec==maxSize)
     return true;
    else return false;
   }
  }
  public int maxSize//read-only property
  {
   get
   {
    if(isLeaf)
     return 5;
    else return 4;
   }
  }
  public BPNode()//constructor
  {
   recarray=new Pair[5];
   for(int i=0;i<5;i++)
    recarray[i]=new Pair();
  }
}//class BPNode
#endregion
public class BPT
{
  #region Base Section
  public BPNode BPTroot;
  public BPT()//Initialization
  {
   BPTroot=new BPNode();
   BPTroot.recarray[0]=new Pair(0,"VIRTUAL RECORD");//Virtual record whose k
ey is less than any
   BPTroot.numrec=1;
   BPTroot.isLeaf=true;
  }
  [STAThread]
  static void Main(string[] args)
  {
   BPT myBPT=new BPT();
   bool running=true;
   char inp;
   Console.WriteLine("I.Insert a Record");
   Console.WriteLine("D.Delete a Record");
   Console.WriteLine("V.View a Range");
   Console.WriteLine("F.Find a Record");
   Console.WriteLine("S.Save to XML");
   Console.WriteLine("L.Load from XML");
   Console.WriteLine("Q.Quit");
   while(running)
   {
    Console.Write("Please Input[I,D,V,F,S,L,Q]:");
    inp=(char)Console.Read();
    Console.ReadLine();
    switch(inp)//message mapping
    {
     case 'i':goto case 'I';
     case 'I':myBPT.InsertBPT();break;
     case 'd':goto case 'D';
     case 'D':myBPT.RemoveBPT();break;
     case 'v':goto case 'V';
     case 'V':myBPT.ViewRange();break;
     case 'f':goto case 'F';
     case 'F':myBPT.FindBPT();break;
     case 's':goto case 'S';
     case 'S':myBPT.SaveBPT();break;
     case 'l':goto case 'L';
     case 'L':myBPT.LoadBPT();break;
     case 'q':goto case 'Q';
     case 'Q':running=false;break;
    }
   }
  }
  #endregion
  #region Insert Function Group
  void InsertBPT()
  {
   try
   {
    Pair tmpPair=new Pair();
    Console.Write("Insert Key:");
    tmpPair.key=Convert.ToInt32(Console.ReadLine());
    if(tmpPair.key<=0)throw new Exception("Keys must be above zero!");
    Console.Write("Filename:");
    tmpPair.pointer=Console.ReadLine();
    Pair retPair=inserthelp(BPTroot,tmpPair);
    if(retPair!=null)
    {
     BPNode NewRoot=new BPNode();
     NewRoot.numrec=2;
     NewRoot.isLeaf=false;
     NewRoot.recarray[0].key=BPTroot.recarray[0].key;
     NewRoot.recarray[0].pointer=BPTroot;
     NewRoot.recarray[1].key=retPair.key;
     NewRoot.recarray[1].pointer=retPair.pointer;
     BPTroot=NewRoot;
    }
   }
   catch(Exception e)
   {
    Console.WriteLine(e.Message);
   }
  }
  //insert recursive entry
  Pair inserthelp(BPNode root,Pair tmpPair)
  {
   Pair insPair;
   int currec=binaryle(root.recarray,root.numrec,tmpPair.key);
   if(root.isLeaf)//Leaf node -- set up values to insert
   {
    if(root.recarray[currec].key==tmpPair.key)
    {
     Console.WriteLine("Duplicates are not allowed for primary key! ");
     return null;
    }
    else insPair=tmpPair;
   }
   else//internal node
   {
    insPair=inserthelp((BPNode)root.recarray[currec].pointer,tmpPair);
    if(insPair==null)return null;//Child did not split, so no insert into cu
rrent node
   }
   //Now, do the insert to the current node. Split if neccessary
   if(!root.isFull)
   {
    putinarray(root,currec,insPair);
    return null;
   }
   else
   {
    BPNode tp=splitnode(root,currec,insPair);
    return new Pair(tp.recarray[0].key,tp);
   }
  }
  //putinarray(A,pos,pair) places pair in array A at position pos.
  void putinarray(BPNode root,int pos,Pair pair)
  {
   for(int i=root.numrec-1;i>pos;i--)
   {
    root.recarray[i+1].key=root.recarray[i].key;
    root.recarray[i+1].pointer=root.recarray[i].pointer;
   }
   root.numrec++;
   root.recarray[pos+1].key=pair.key;
   root.recarray[pos+1].pointer=pair.pointer;
  }
  //Function splitnode(rt,pos,pair) places in rt at pos.
  //But, int the process, rt is split into two nodes, each
  //taking half of the records, and the new node is returned.
  BPNode splitnode(BPNode root,int pos,Pair pair)
  {
   BPNode RNode=new BPNode();
   RNode.setNext(root.getNext());
   root.setNext(RNode);
   RNode.setPrev(root);
   if(RNode.getNext()!=null)
    RNode.getNext().setPrev(RNode);
   //How to split the root depends on whether it's a leaf or non-leaf node
   if(root.isLeaf)
   {
    RNode.numrec=root.numrec=3;//(5+1)/2
    RNode.isLeaf=true;
   }
   else
   {
    RNode.numrec=2;root.numrec=3;
    RNode.isLeaf=false;
   }
   for(int i=0;i<5;i++)//move the former records
   {
    int n=i;
    if(i>pos)
     n=i+1;
    if(n>2)
    {
     RNode.recarray[n-3].key=root.recarray[i].key;
     RNode.recarray[n-3].pointer=root.recarray[i].pointer;
    }
   }
   if(pos+1>2)//process the inserted record
   {
    RNode.recarray[pos-2].key=pair.key;
    RNode.recarray[pos-2].pointer=pair.pointer;
   }
   else
   {
    root.recarray[pos+1].key=pair.key;
    root.recarray[pos+1].pointer=pair.pointer;
   }//step2:redirect pointers
   return RNode;
  }
  #endregion
  #region Find/View Function Group
  void FindBPT()
  {
   try
   {
    Console.Write(" Find Key:");
    int K=Convert.ToInt32(Console.ReadLine());
    int key=K;
    BPNode ResultNode=findhelp(BPTroot,ref K);//K is used to pass a key to c
hild function
              //and retrieve the index of the key from child funtion
    if(ResultNode.recarray[K].key==key)Console.WriteLine((string)ResultNode.
recarray[K].pointer);
    else Console.WriteLine("Cannot Find Any!");
   }
   catch(Exception e)
   {
    Console.WriteLine(e.Message);
   }
  }
  //find recursive entry
  BPNode findhelp(BPNode root,ref int K)
  {
   int currec=binaryle(root.recarray,root.numrec,K);
   if(root.isLeaf)//if it is a leaf node...
   {
    K=currec;
    return root;
   }
   else return findhelp((BPNode)root.recarray[currec].pointer,ref K);//Proce
ss Child
  }
  //function binaryle(A,n,K) returns the index of the greatest value
  //less than or equal to K in array A containing n records.
  int binaryle(Pair[] recarray,int numrec,int K)
  {
   int i=1;//the first virtual one(i=0) can never be greater than K
   while(i<numrec)//do-while is OK
   {
    if(recarray[i].key>K)break;
    else i++;
   }
   return i-1;
  }
  void ViewRange()
  {
   try
   {
    Console.Write("Range Start Key:");
    int K1=Convert.ToInt32(Console.ReadLine());
    int key=K1;
    Console.Write("Range End Key:");
    int K2=Convert.ToInt32(Console.ReadLine());
    BPNode ResultNode=findhelp(BPTroot,ref key);//K is used to pass a key to
child function
             //and retrieve the index of the key from child funtion
                if(ResultNode.recarray[key].key==K1)Console.WriteLine("{0}\t
{1}",K1,(string)ResultNode.recarray[key].pointer);
    key++;
    for(;;)
    {
     if(key==ResultNode.numrec)
     {
      ResultNode=ResultNode.getNext();
      key=0;
     }
     if((ResultNode!=null)&&(ResultNode.recarray[key].pointer!=null)&&(Resul
tNode.recarray[key].key<=K2))
      Console.WriteLine("{0}\t{1}",ResultNode.recarray[key].key,(string)Resu
ltNode.recarray[key].pointer);
     else break;
     key++;
    }
   }
   catch(Exception e)
   {
    Console.WriteLine(e.Message);
   }
  }
  #endregion
  #region Save/Load Function Group
  void SaveBPT()
  {
   try
   {
    XmlSerializer serializerw = new XmlSerializer(typeof(BPNode));
    TextWriter writer = new StreamWriter("BPTExpr.xml");
    serializerw.Serialize(writer,BPTroot);
    writer.Close();
   }
   catch(Exception e)
   {
    Console.WriteLine(e.Message);
   }
  }
  void LoadBPT()
  {
   try
   {
    XmlSerializer serializerr = new XmlSerializer(typeof(BPNode));
    FileStream fs = new FileStream("BPTExpr.xml", FileMode.Open);
    BPTroot = (BPNode)serializerr.Deserialize(fs);
    fs.Close();
    ReCreateLink(BPTroot);
   }
   catch(Exception e)
   {
    Console.WriteLine(e.Message);
   }
  }
  void ReCreateLink(BPNode root)
  {
   if(root.isLeaf)return;//There's no need to re-create links for single-nod
e tree
   if(!((BPNode)root.recarray[0].pointer).isLeaf)
    for(int i=0;i<root.numrec;i++)
                    ReCreateLink((BPNode)root.recarray[i].pointer);
   for(int i=0;i<root.numrec-1;i++)
   {
    ((BPNode)root.recarray[i].pointer).setNext((BPNode)root.recarray[i+1].po
inter);
    ((BPNode)root.recarray[i+1].pointer).setPrev((BPNode)root.recarray[i].po
inter);
   }
  }
  #endregion
  #region Delete Function Group
  void RemoveBPT()
  {
   try
   {
    Console.Write("Delete Key:");
    int K=Convert.ToInt32(Console.ReadLine());
    if(K==0)throw new Exception("Virtual Record is not allowed to delete!");

    int retvalue=removehelp(BPTroot,K,0);
    if(retvalue==-2)
     throw new Exception("Record Not Found");
    else if(retvalue==0)
     BPTroot=(BPNode)BPTroot.recarray[0].pointer;
   }
   catch(Exception e)
   {
    Console.WriteLine(e.Message);
   }
  }
  //delete recursive entry removehelp returns position of the child node adj
usted,
  //if any. If the child node did not underflow or change its first record,
  //then return -1, to indicate the parent shouldn't be modified.
  int removehelp(BPNode root,int K,int thispos)
  {
   int currec=binaryle(root.recarray,root.numrec,K);
   if(root.isLeaf)
   {
    if(root.recarray[currec].key!=K)
     return -2;
   }
   else
   {//Delete from child
    currec=removehelp((BPNode)root.recarray[currec].pointer,K,currec);
    if(currec<0)//Child did not underflow -1 or cannot find record -2
     return currec;
    else if(((BPNode)root.recarray[currec].pointer).numrec!=0)
    {//Child was shuffled -- adjust key value
     root.recarray[currec].key= ((BPNode)root.recarray[currec].pointer).reca
rray[0].key;
     return -1;//Child did not underflow
    }
   }
   //Now,remove record at position currec,for internal node, this means its  
child has been cleared.
   removerec(root,currec);
   if(root.numrec>2)//Enough records, just remove it
    return -1;
   else
   {//Underflow, if it doesn't have any left neighbour,then merge right,else
merge left
    if((root.getPrev()==null)&&(root.getNext()==null))
    {//root node
     if((root.numrec==1)&&(!root.isLeaf))
      return 0;//0 notify BPTroot to decrease its level
     else return -1;
    }
    else if(root.getPrev()==null)
    {//the left most node
     if(root.numrec+root.getNext().numrec<=root.maxSize)
     {
      merge_nodes(root,root.getNext());
      return thispos+1;//Right neighbour is now empty
     }
     else
     {
      shuffle_nodes(root,root.getNext());
      return thispos+1;//Right neighbour has new first record
     }
    }
    else
    {//other node
     if(root.numrec+root.getPrev().numrec<=root.maxSize)
     {
      merge_nodes(root.getPrev(),root);
      return thispos;//This node is now empty
     }
     else
     {
      shuffle_nodes(root.getPrev(),root);
      return thispos;//This node has new first record
     }
    }
   }
  }
  //Funciton merge_nodes(N1,N2) merges together the record arrays of BPNodes
N1 and N2.
  void merge_nodes(BPNode left,BPNode right)
  {
   for(int i=left.numrec;i<left.numrec+right.numrec;i++)
   {
    left.recarray[i].key=right.recarray[i-left.numrec].key;
    left.recarray[i].pointer=right.recarray[i-left.numrec].pointer;
   }
   left.numrec+=right.numrec;
   right.numrec=0;
   left.setNext(right.getNext());
   if(right.getNext()!=null)
    right.getNext().setPrev(left);
  }
  //Function shuffle_nodes(N1,N2) copies records as necessary within
  //BPNodes N1 and N2, so that both have equal number of records.
  void shuffle_nodes(BPNode left,BPNode right)
  {
   if(left.numrec>right.numrec)
   {
    for(int i=1;i>=0;i--)//at most two need to move
    {
     right.recarray[i+1].key=right.recarray[i].key;
     right.recarray[i+1].pointer=right.recarray[i].pointer;
    }
    right.recarray[0].key=left.recarray[left.numrec-1].key;
    right.recarray[0].pointer=left.recarray[left.numrec-1].pointer;
    left.numrec--;right.numrec++;
   }
   else
   {
    left.recarray[left.numrec].key=right.recarray[0].key;
    left.recarray[left.numrec].pointer=right.recarray[0].pointer;
    for(int i=0;i<right.numrec-1;i++)
    {
     right.recarray[i].key=right.recarray[i+1].key;
     right.recarray[i].pointer=right.recarray[i+1].pointer;
    }
    left.numrec++;right.numrec--;
   }
  }
  //Function removerec(A,n,c) removes the record at position c from array A  
containing n records.
  void removerec(BPNode root,int pos)
  {
   for(int i=pos;i<root.numrec-1;i++)
   {
    root.recarray[i].key=root.recarray[i+1].key;
    root.recarray[i].pointer=root.recarray[i+1].pointer;
   }
   root.numrec--;
  }
  #endregion
}//class BPT
}//namespace Kingsun

--

※ 来源:·BBS 水木清华站 smth.edu.cn·[FROM: 166.111.203.12]
返回上一页
回到目录
回到页首
下一篇