数据结构学习心得

2．排序

计数排序

基数排序

桶排序

3. 基数排序树

4. 二叉查找树

5．二叉查找树中检索出第i小的元素 

      给每个节点增加一个域

(x的秩表示的是x在整个序列中所处的位置是第几, 往上找小于它的节点。)

这样通过以上的扩展的二叉树的构造，可以得到某个序列中第n大或第n小的元素。此处的size属性指的是以当前节点为根的树的节点的个数。

6．区间树

注：

(该定理的证明简单)

7．最长公共子序列

（可以通过辅助数组b和c来输出LCS序列）

8．Huffman编码

(1) 哈夫曼树的存储结构

    用一个大小为2n-1的向量来存储哈夫曼树中的结点，其存储结构为：

  #define n 100 //叶子数目

  #define m 2*n-1//树中结点总数

  typedef struct { //结点类型

      float weight； //权值，不妨设权值均大于零

      int lchild，rchild，parent； //左右孩子及双亲指针

    }HTNode；

  typedef HTNode HuffmanTree[m]； //HuffmanTree是向量类型

(2) 算法

void CreateHuffmanTree(HuffmanTree T)

    {//构造哈夫曼树，T[m-1]为其根结点

      int i，p1，p2；

      InitHuffmanTree(T)； //将T初始化

      InputWeight(T)； //输入叶子权值至T[0．．n-1]的weight域

      for(i=n；i          SelectMin(T，i-1，&p1，&p2)；  (可以用建堆的形式来得到)

          //在T[0．．i-1]中选择两个权最小的根结点，其序号分别为p1和p2

          T[p1].parent=T[p2].parent=i；

          TIi].1child=p1； //最小权的根结点是新结点的左孩子

          T[j].rchild=p2； //次小权的根结点是新结点的右孩子

          T[i].weight=T[p1].weight+T[p2].weight；

        } // end for

    }

9．优先级队列

10．字符串匹配算法

KMP算法

理解：

 每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离，继续进行比较。

为此,定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。

         max{k|1     next[j]=               0                          当j=1时

                            1                          其他情况

改进next，变成nextval:                                               

next[j] = k，而pj=pk，则 主串中si和pj不等时，不需再和pk进行比较，而直接和pnext[k]进行比较。

   j       1 2 3 4 5 

模式    a a a a b

next[j] 0 1 2 3 4

nextval[j] 0 0 0 0 4

程序：

void get_nextval(SString T, int &nextval[])

{

     i= 1; nextval[1] = 0; j = 0;   

while( i{

          if(j==0 || T[i] == T[j])

{

                ++i; ++j; 

                if(T[i] != T[j])

nextval[i] = j;

                else

  nextval[i] = nextval[j];

          }

          else 

 j = nextval[j];

     }

}          

BM算法

11．BloomFilter算法(c#实现)

  1 public class BloomFilter

  2    {

  3        private BitArray _bitArray = null;

  4        private int _count = 0;

  5        private int _hashcount = 1;

  6

  7        public BloomFilter(int size, int hashcount)

  8        {

  9            _bitArray = new BitArray(size, false);

 10            _hashcount = hashcount;

 11         }

 12

 13        public void Add(T item)

 14        {

 15            int h1 = item.GetHashCode();

 16            int h2 = Hash(h1.ToString());

 17

 18            bool result = false;

 19            unchecked

 20          {

 21                h1 = (int)(((uint)h1) % _bitArray.Count);

 22                h2 = (int)(((uint)h2) % _bitArray.Count);

 23            }

 24            for (int i = 0; i < _hashcount; i++)

 25            {

 26                if (!_bitArray[h1])

 27                {

 28                    _bitArray[h1] = result = true;

 29                }

 30

 31                unchecked

 32               {

 33            h1 = (int)((uint)(h1 + h2) % _bitArray.Count);

 34            h2 = (int)((uint)(h2 + i) % _bitArray.Count);

 35                }

 36            }

 37            if (result)

 38            {

 39                _count++;

 40            }

 41        }

 42

 43        public bool Contains(T item)

 44        {

 45

 46            int h1 = item.GetHashCode();

 47            int h2 = Hash(h1.ToString());

 48            unchecked

 49            {

 50                h1 = (int)(((uint)h1) % _bitArray.Count);

 51                h2 = (int)(((uint)h2) % _bitArray.Count);

 52            }

 53            for (int i = 0; i < _hashcount; i++)

 54            {

 55                if (_bitArray[h1] == false)

 56                {

 57                    return false;

 58                }

 59                unchecked

 60                {

 61            h1 = (int)((uint)(h1 + h2) % _bitArray.Count);

 62            h2 = (int)((uint)(h2 + i) % _bitArray.Count);

 63                }

             }

 65            return true;

 66

 67        }

 68

 69

 70

 71        protected int Hash(T item)

 72        {

 73            int hashcode = item.GetHashCode();

 74

 75            hashcode = Hash(hashcode.ToString());

 76

 77            return hashcode;

 78        }

 79

 80        /**//// 

 83        /// 需要Hash的字符串

 84        /// 

 85        protected int Hash(string str)

 86        {

 87            long hash = 0;

 88

             for (int i = 0; i < str.Length; i++)

 90            {

 91                if ((i & 1) == 0)

 92                {

 93              hash ^= ((hash << 7) ^ str[i] ^ (hash >> 3));

 94                }

 95                else

 96                {

 97         hash ^= (~((hash << 11) ^ str[i] ^ (hash > > 5)));

 98                }

 99            }

100            unchecked

101            {

102                return (int)hash;

103            }

104        }

105

106

107        /**//// 

110        public int Count

111        {

112            get

113            {

114                return _count;

115            }

116        }

117

118        public int SizeBytes

119        {

120            get

121            {

122                return _bitArray.Length;

123            }

124        }

12．基本知识

二叉树的前趋，后继，删除操作，判断是某数是该树中第几大的。

用二叉树进行词频的统计(包括查找 插入等)

用字符串的hash function进行词频统计，其中hash表可以用桶。(每个桶里面包含对应的关键字的链表)