数据结构学习心得

1、1同时找到最小元素和最大元素2排序计数排序基数排序桶排序3. 基数排序树4. 二叉查找树5二叉查找树中检索出第i小的元素 给每个节点增加一个域(x的秩表示的是x在整个序列中所处的位置是第几, 往上找小于它的节点。)这样通过以上的扩展的二叉树的构造，可以得到某个序列中第n大或第n小的元素。此处的size属性指的是以当前节点为根的树的节点的个数。6区间树注：(该定理的证明简单)7最长公共子序列（可以通过辅助数组b和c来输出LCS序列）8Huffman编码(1) 哈夫曼树的存储结构 用一个大小为2n-1的向量来存储哈夫曼树中的结点，其存储结构为： #define n 100 /叶子数目 #defin

2、e m 2*n-1/树中结点总数 typedef struct /结点类型 float weight； /权值，不妨设权值均大于零 int lchild，rchild，parent； /左右孩子及双亲指针 HTNode； typedef HTNode HuffmanTreem； /HuffmanTree是向量类型(2) 算法void CreateHuffmanTree(HuffmanTree T) /构造哈夫曼树，Tm-1为其根结点 int i，p1，p2； InitHuffmanTree(T)； /将T初始化 InputWeight(T)； /输入叶子权值至T0n-1的weight域 for

3、(i=n；im；i+)/共进行n-1次合并，新结点依次存于Ti中 SelectMin(T，i-1，&p1，&p2)； (可以用建堆的形式来得到) /在T0i-1中选择两个权最小的根结点，其序号分别为p1和p2 Tp1.parent=Tp2.parent=i； TIi.1child=p1； /最小权的根结点是新结点的左孩子 Tj.rchild=p2； /次小权的根结点是新结点的右孩子 Ti.weight=Tp1.weight+Tp2.weight； / end for 9优先级队列10字符串匹配算法KMP算法理解： 每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用已得到的“部分匹配”结果将

4、模式向右滑动尽可能远的一段距离，继续进行比较。为此,定义nextj函数，表明当模式中第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#实现) 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函数(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中的元素个数109/110publicintCount111112get113114return_count;115116117118publicintSizeBytes119120