數(shù)據(jù)結(jié)構(gòu)學習心得

1、1同時找到最小元素和最大元素2排序計數(shù)排序基數(shù)排序桶排序3. 基數(shù)排序樹4. 二叉查找樹5二叉查找樹中檢索出第i小的元素 給每個節(jié)點增加一個域(x的秩表示的是x在整個序列中所處的位置是第幾, 往上找小于它的節(jié)點。)這樣通過以上的擴展的二叉樹的構(gòu)造，可以得到某個序列中第n大或第n小的元素。此處的size屬性指的是以當前節(jié)點為根的樹的節(jié)點的個數(shù)。6區(qū)間樹注：(該定理的證明簡單)7最長公共子序列（可以通過輔助數(shù)組b和c來輸出LCS序列）8Huffman編碼(1) 哈夫曼樹的存儲結(jié)構(gòu) 用一個大小為2n-1的向量來存儲哈夫曼樹中的結(jié)點，其存儲結(jié)構(gòu)為： #define n 100 /葉子數(shù)目 #defin

2、e m 2*n-1/樹中結(jié)點總數(shù) typedef struct /結(jié)點類型 float weight； /權(quán)值，不妨設權(quán)值均大于零 int lchild，rchild，parent； /左右孩子及雙親指針 HTNode； typedef HTNode HuffmanTreem； /HuffmanTree是向量類型(2) 算法void CreateHuffmanTree(HuffmanTree T) /構(gòu)造哈夫曼樹，Tm-1為其根結(jié)點 int i，p1，p2； InitHuffmanTree(T)； /將T初始化 InputWeight(T)； /輸入葉子權(quán)值至T0n-1的weight域 for

3、(i=n；im；i+)/共進行n-1次合并，新結(jié)點依次存于Ti中 SelectMin(T，i-1，&p1，&p2)； (可以用建堆的形式來得到) /在T0i-1中選擇兩個權(quán)最小的根結(jié)點，其序號分別為p1和p2 Tp1.parent=Tp2.parent=i； TIi.1child=p1； /最小權(quán)的根結(jié)點是新結(jié)點的左孩子 Tj.rchild=p2； /次小權(quán)的根結(jié)點是新結(jié)點的右孩子 Ti.weight=Tp1.weight+Tp2.weight； / end for 9優(yōu)先級隊列10字符串匹配算法KMP算法理解： 每趟匹配過程中出現(xiàn)字符比較不等時，不回溯主指針i，利用已得到的“部分匹配”結(jié)果將

4、模式向右滑動盡可能遠的一段距離，繼續(xù)進行比較。為此,定義nextj函數(shù)，表明當模式中第j個字符與主串中相應字符“失配”時，在模式中需重新和主串中該字符進行比較的字符的位置。 maxk|1kj,且“p1pk-1”=“pj-k+1pj-1” 當此集合非空時 nextj= 0 當j=1時 1 其他情況 改進next，變成nextval: nextj = k，而pj=pk，則 主串中si和pj不等時，不需再和pk進行比較，而直接和pnextk進行比較。 j 1 2 3 4 5 模式 a a a a bnextj 0 1 2 3 4nextvalj 0 0 0 0 4 程序：void get_nextv

5、al(SString T, int &nextval) i= 1; nextval1 = 0; j = 0; while( iT0) if(j=0 | Ti = Tj) +i; +j; if(Ti != Tj)nextvali = j; else nextvali = nextvalj; else j = nextvalj; BM算法11BloomFilter算法(c#實現(xiàn)) HYPERLINK :/www blogs / 1publicclassBloomFilter23privateBitArray_bitArray=null;4privateint_count=0;5privateint

6、_hashcount=1;67publicBloomFilter(intsize,inthashcount)89_bitArray=newBitArray(size,false);10_hashcount=hashcount;11 1213publicvoidAdd(Titem)1415inth1=item.GetHashCode();16inth2=Hash(h1.ToString();1718boolresult=false;19unchecked2021h1=(int)(uint)h1)%_bitArray.Count);22h2=(int)(uint)h2)%_bitArray.Cou

7、nt);2324for(inti=0;i_hashcount;i+)2526if(!_bitArrayh1)2728_bitArrayh1=result=true;293031unchecked3233h1=(int)(uint)(h1+h2)%_bitArray.Count);34h2=(int)(uint)(h2+i)%_bitArray.Count);353637if(result)3839_count+;40414243publicboolContains(Titem)444546inth1=item.GetHashCode();47inth2=Hash(h1.ToString();4

8、8unchecked4950h1=(int)(uint)h1)%_bitArray.Count);51h2=(int)(uint)h2)%_bitArray.Count);5253for(inti=0;i_hashcount;i+)5455if(_bitArrayh1=false)5657returnfalse;5859unchecked6061h1=(int)(uint)(h1+h2)%_bitArray.Count);62h2=(int)(uint)(h2+i)%_bitArray.Count);636465returntrue;666768697071protectedintHash(T

9、item)7273inthashcode=item.GetHashCode();7475hashcode=Hash(hashcode.ToString();7677returnhashcode;787980/*/81/字符串Hash函數(shù)(APHashFunction)82/83/需要Hash的字符串84/85protectedintHash(stringstr)8687longhash=0;8889for(inti=0;istr.Length;i+)9091if(i&1)=0)9293hash=(hash3);9495else9697hash=(hash 5);9899100unchecked101102return(int)hash;103104105106107/*/108/返回BloomFilter中的元素個數(shù)109/110publicintCount111112get113114return_count;115116117118publicintSizeBytes119120