数据结构

  • 先进后出

操作

    StackEmpty( S )         //判断栈是否为空
        if top[S] == 0      //栈顶等于0就为空   
            return true ;       
        else
            return false ;

    //=========
    Push( S, x )            //将x入栈
        top[S]++ ;          //此处未作栈是否满了的检查
        S[top[S]] = x ;

    //=========
    Pop( S )                //弹栈
        x = S[top[s]] ;     //未作是否为空栈的检查
        top[S]-- ;
        return x ;

队列

  • 先进先出

操作

    Enqueue( Q, x )             //用数组Q表示环形队列
        Q[tail[Q]] = x ;        //tail[Q]要指向队尾元素之后的位置
        if tail[Q] == length[Q] //当head[Q] == tail[Q]时,队列满
            tail[Q] = 1 ;       //当((head[Q]+1)%n)+1 == tail[Q]时,队列空  
        else
            tail[Q]++ ;

    //========
    Dequeue( Q )        //出队
        x = head[Q] ;
        if head[Q] == length[Q] 
            head[Q] = 1 ;
        else
            head[Q]++ ;
        return x ;      //返回对头元素

链表

搜索操作

    ListSearch( L, k )  //L为链表,k为要查找的关键字
        x = head[L] ;   //x指向链表头
        while x != nil and key[x] != k
            x = next[x] ;
        return x ;
    //T(n) = O(1) 

插入节点

    ListInsert( L, x )  //将x插入到表头,此处L为双链表
        next[x] = head[L] ;
        if head[L] != nil
            prev[head[L]] = x ;
        head[L] = x ;   
    //T(n) = O(1)

删除节点

    ListDelete( L, x )  //将x从双链表中删除
        if prev[x] != nil 
            next[prev[x]] = next[x] ;
        else
            head[L] = next[x] ;

        if next[x] != nil
            prev[next[x]] = prev[x] ;
    //T(n) = O(1)

哨兵 :是一个既不带关键字又不带卫星数据的空对象,可以用nil[L]表示,nil[L]与链表中其他节点具有一样的数据结构,用nil[L]代替原来代码中的nil,可以有效减少代码中的检测

    ListDelete( L, x ) //用nil[L]代替nil,可以不用检测prev[x],next[x]是否为空
        prev[next[x]] = prev[x] ;
        next[prev[x]] = next[x] ;

    //==========
    ListSearch( L, k )
        x = Next[nil[L]] ;
        while x != nil[L] and key != k
            x = next[x] ;
        return x ;

    //==========
    ListInsert( L, x )
        prev[x] = nil[L] ;
        next[x] = next[nil[L]] ;
        prev[next[x]] = x ;
        next[nil[L]] = x ;
  • 异或的性质
    A xor A = 0
    A xor 0 = A
    A xor B = B xor A       #交换律
    A xor B xor C = A xor ( B xor C )  #结合律
    A xor B xor B = A xor ( B xor B ) = A xor 0 = A 

    #交换A,B两个变量
    A = A xor B     # a xor b
    B = B xor A     # b xor a xor b = a
    A = A xor B     # a xor b xor a = b

二叉树

  • 数据结构
    struct BinTree                      //二叉树
        struct BinTree *left ;          //左子树
        struct BinTree *right ;         //右子树
        struct BinTree *parent ;        //父节点
        key_t key ;                     //关键字

    //分支树无限制的有根树
    struct Xtree
        struct Xtree *parent ;          //父节点
        struct Xtree *child ;           //左孩子
        struct Xtree *sibling ;         //右兄弟

后序遍历(递归)

    VisitTreeLast( x )         //x为子树根节点
        if x == nil
            return ;
        VisitTreeFirst( left[x] ) ;
        VisitTreeFirst( right[x] ) ;
        visit( x ) ;

先序遍历(非递归)

    VisitTreeLast( T )          //T为二叉树
        x = root[T] ;
        x and Push( S, x ) ;
        while !StackEmpty( S ) 
            x = Pop(  S ) ;
            visit( x ) ;
            right[x] and Push( S, right[x] ) ;
            left[x] and Push( S, left[x] ) ;

中序遍历(非递归)

    /*
    节点必须有父指针
    
    通过当前节点是其父节点的左孩子还是右孩子来判断其父节点是否被访问过.
    1.如果当前结点是其父节点的左孩子,则父节点未被访问
    2.如果当前节点是其父节点的右孩子,则父节点已被访问
    */
    VisitTreeMid( T )           //T为二叉树
        x = root[x] ;

        while x
            if left[x]
                x = left[x] ;
                continue ;
            else
                visit( x ) ;
                x = right[x] ;
                continue ;

            while 1             //从这里开始,指针开始回溯
                if x == root[x]
                    return ;
                if( left[parent[x]] == x )
                    visit( parent[x] ) ;
                    if( right[parent[x]] )
                        x = right[parent[x]] ;
                        break ;
                x = parent[x] ;         //x是其父节点的右孩子

二叉查找树的查找

    //递归算法
    BinTreeSearch( x, k )       //x为子树根,k为关键字
        if x == nil
            return nil ;
        if key[x] == k
            return x ;
        else if key[x] > k
            return BinTreeSearch( left[x], k ) ;
        else 
            return BinTreeSearch( right[x], k ) ;
    //==========
    //非递归算法
    BinTreeSearch( T, k )       //T为树根,k为关键字
        x = root[T] ;
        while x
            if key[x] == k
                return x ;
            else if key[x] > k
                x = left[x] ;
            else 
                x = right[x] ;

二叉查找树的最大关键字和最小关键字

    /*x为子树根*/
    MaxBinTree( x )     //最大值
        while x and right[x]
            x = right[x] ;
        return x ;
    //==========
    MinBinTree( x )     //最小值
        while x and left[x]
            x = left[x] ;
        return x ;

二叉查找树的前趋和后继

    BinTreeSuccessor( x )      //后继
        if right[x]
            return MinBinTree( right[x] ) ;
        else
            while parent[x] and left[parent[x]] != x
                x = parent[x] ;
            return parent[x] ;
    //如果x有右子树,则x的后继是x右子树的最小值
    //如果没有右子树,则x的后继为其层数最低的祖先,且x在这个祖先的左子树上面
    //==========
    BinTreePredecessor( x )
        if left[x]
            return MaxBinTree( left[x] ) ;
        else 
            while parent[x] and right[parent[x]] != x
                x = parent[x] ;
            return parent[x] ;
    //如果x有左子树,则x的前趋是x左子树的最大值
    //如果没有左子树,则x的前趋为其层数最低的祖先,且x在这个祖先的右子树上面

二叉查找树的插入

    BinTreeInsert( T, z )           //T(n) = O(h),h为树高
        x = root[T] ;
        if x == nil
            root[T] = z ;
            return ;

        while x
            if key[x] == key[z]     //重复关键字
                return ERROR ;  
            else if key[x] > key[z]
                if left[x]
                    x = left[x] ;
                else
                    left[x] = z ;
                    parent[z] = x ;
                    break ;
            else
                if right[x]
                    x = right[x] ;
                else
                    right[x] = z ;
                    parent[z] = x ;
                    break ;

二叉查找树的删除

    BinTreeDelete( T, z )
        if !left[z] or !right[z]        //
            y = z ;                     //
        else                            // y是确定要删除的元素
            y = BinTreeSuccessor( z ) ; //

        if left[y]
            x = left[y] ;
        else
            x = right[y] ;

        if x                            //y有孩子
            parent[x] = parent[y] ;

        if !parent[y]                   //y为树根
            root[T] = x ;
        else                            //y不为树根
            if left[parent[y]] == y
                left[parent[y]] = x ;
            else
                right[parent[y]] = x ;

        if y != z                       //删除的是z的后继
            copy y to z except( left, right, parent )

        parent[y] = nil ;
        right[y] = nil ;
        left[y] = nil ;

散列表

  • 函数h将关键字域U映射到散列表T[0..m-1]的槽位上

h : U —> {0, 1, … , m-1}

  • 碰撞:当h(k1) == h(k2)时,k1和k2发生碰撞
  • 链表解决碰撞法,当发生碰撞时,直接使用链表链接起来.
  • 删除,插入,查找都在以T[h(k)]为表头的链表中进行

直接寻址散列表

    DirectAddressSearch( T, k ) //T为直接寻址表,k为关键字,x为元素
        return T[k] ;           //例:将关键字1,2,10,11,...,n插入到表T[1..n]中
    //==========                     即:
    DirectAddressInsert( T, x ) //   初始化:T[1..n] = nil ;
        T[key[x]] = x ;         //   插入:T[key[x]] = x ==> T[1]=1,T[11]=11 ;
    //==========                     查找:关键字11,即返回 T[11] = 11 ;
    DirectAddressDelete( T, x ) //   删除:关键字11,即 T[11] = nil ;
        T[key[x]] = nil ;

散列函数

好的散列函数应(近似的)满足一致散列的假设:每个关键字都等可能的散列到m个槽位之一,且与其他关键字已被散列到哪一个槽位无关

如果一个关键字不是自然数,请想办法将其解释为自然数

除法散列法

h(k) = k mod m

m不应是2的幂.如果m=2^p,则h(k)就是k的p个最低位数
可选与2的整数幂不太接近的质数

乘法散列法

h(k) = m * ( KA mod 1 ); 0 < A < 1

KA mod 1 即取KA的小数部分
m一般选2的幂,A= (5^(1/2) - 1)/2 = 0.618 033 988 7…效果较好

全域散列

  • 从一族仔细设计的函数中随机的选择一个作为散列函数
设计一个全域散列函数
  1. 选择一个够大的质数p,使得 0 <= k <= p
  2. 设 Zp={0, 1,…, p-1}, Z`p={1, 2,…, p-1}

h<a,b\ >(k) = ( ( a*k + b ) mod P ) mod m

P为关键字域的范围,m为槽位, a in Z`p, b in Zp

  • H<P,m> = { h<a,b> : a in Z`p and b in Zp }
开放寻址法(碰撞的解决办法)

对于开放寻址法来说,要求对每一个关键字k,其探求序列<h(k,0), h(k,1),…,h(k,m-1)>必须是<0, 1, …, m-1>的一个排列
最长的探查期望长度为E[l] = O(lgn)

使用开放寻址法的Insert,Search
    HashInsert( T, x )
        for i = 0 to m-1
            if T[h(key[x], i)] == nil
                T[h(key[x], i)] = x ;
                break ;
    //==========
    HashSearch( T, k )
        for i = 0 to m-1
            j = h( k, i ) ;
            if key[T[j]] == k
                return T[j] ;
            if T[j] == nil 
                return NotFoundError ;
开放寻址的方法
  • 线性探测
    给定一个普通的散列函数 h1:u –> {0, 1, …, m-1},线性探测的散列函数为: h(k,i) = ( h1(k) + i ) mod m ( i=0,1,…, m-1)

  • 二次探测
    h(k, i) = ( h1(k) + c1i + c2i^2 ) mod m

  • 双重散列 h(k, i) = ( h1(k) + i*h2(k) ) mod m, 值h2(k)要与表的大小m互质

确保这个条件成立的方法:

  1. m取2的幂,并设计一个总产生奇数的h2
  2. m去质数,并设计一个总产生比m小的正整数的h2

完全散列

将散列分为两级,每一级都使用全域散列函数
即:h(k) = ((a*k+b) mod p) mod m

  1. 对关键字k使用h(k),选中第一级的槽位Tj;
  2. 再对k使用hj(k),选中Tj中的槽位,将k放入

注意:为了能真正确保第二级不出现碰撞,需要让Tj的大小mj为散列Tj的关键字个数nj的平方,即: mj = nj^2

    | 1 |   ----> |  |  |  |  |  |     T1
    | 2 |
    | 3 |
    | 4 |
    | 5 |   ----> |  |  |  |  |  |     T5
    | 6 |
    | 7 |