头像

BUPT-Spider




离线:15天前



BUPT-Spider
1个月前
#include<stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, int len)
{
    for(int i = 0; i < len; i++)
        printf(" %.2x", start[i]);

    printf("\n");
} //show_bytes

int main(void)
{
    short sx = -12345;
    unsigned short uy = sx;

    printf("uy = %u :\t", uy);
    show_bytes((byte_pointer) &uy, sizeof(unsigned short));

    return 0;
}



BUPT-Spider
2个月前
//自顶向下伸展树的插入
SplayTree Insert(ElementType Item, SplayTree T)
{
    static Position NewNode = NULL;

    if(NewNode == NULL)
    {
        NewNode = malloc(sizeof(struct SplayNode);
        if(NewNode == NULL)
            FatalError("Out of space!!!");
    }
    NewNode->Element = Item;

    if(T == NullNode)
    {
        NewNode->Left = NewNode->Right = NullNode;
        T = NewNode;
    }
    else
    {
        T = Splay(Item, T);
        if(Item < T->Element)
        {
            NewNode->Left = T->Left;
            NewNode->Right = T;
            T->Left = NullNode;
            T = NewNode;
        }
        else if(Item > T->Element)
        {
            NewNode->Right = T->Right;
            NewNode->Left = T;
            T->Right = NullNode;
            T = NewNode;
        }
        else return T;
    }

    NewNode = NULL; /*So next insert will call malloc;*/
    return T;
}

//自顶向下的删除过程
SplayTree Remove(ElementType Item, SplayTree T)
{
    Position NewTree;

    if(T != NullNode)
    {
        T = Splay(Item, T);
        if(Item == T->Element)
        {
            if(T->Left == NullNode)
                NewTree = T->Right;
            else
            {
                NewTree = T->Left;
                NewTree = Splay(Item, NewTree);
                NewTree->Right = T->Right;
            }
            free(T);
            T = NewTree;
        }
    }

    return T;
}




BUPT-Spider
2个月前

伸展树

//自顶向下的展开过程

SplayTree Splay(ElementType Item, Position X)
{
    static struct SplayNode Header;
    Position LeftTreeMax, RightTreeMin;

    Header.Left = Header.Right = NullNode;
    LeftTreeMax = RightTreeMin = &Header;
    NullNode->Element = Item;

    while(Item != X->Element)
    {
        if(Item < X->Element)
        {
            if(Item < X->Left->Element)
                X = SingleRotateWithLeft(X);
            if(X->Left == NullNode)
                break;
            RightTreeMin->Left = X;
            RightTreeMin = X;
            X = X->Left;
        }
        else 
        {
            if(Item > X->Right->Element)
                X = SingleRotateWithRight(X);
            if(X->Right == NullNode)
                break;
            LeftTreeMax->Right = X;
            LeftTreeMax = X;
            X = X->Right;
        }
    }

    /*Reassemble*/
    LeftTreeMax->Right = X->Left;
    RightTreeMin->Left = X->Right;
    X->Left = Header.Right;
    X->Right = Header.Left;

    return X;
}



BUPT-Spider
2个月前

沃舍尔算法

//Warshall Algorithm

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110;

int n;
int M[N][N];

int main(void)
{
    cin >> n;
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= n; j++) cin >> M[i][j];

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(M[i][j] == 0) M[i][j] = M[i][k] & M[k][j];

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
            cout << M[i][j] << ' ';
        cout << endl;
    }    

    return 0;
}



BUPT-Spider
2个月前

伸展树声明和初始化

//北京邮电大学 计算机学院 Spider

#ifndef _Splay_H

struct SplayNode;
typedef struct SplayNode *SplayTree;

SplayTree MakeEmpty(SplayTree T);
SplayTree Find(ElementType X, SplayTree T);
SplayTree FindMin(SplayTree T);
SplayTree FindMax(SplayTree T);
SplayTree Initialize(void);
SplayTree Insert(ElementType X, SplayTree T);
SplayTree Remove(ElementType X, SplayTree T);
ElementType Retrieve(SplayTree T);

#endif

struct SplayNode
{
    ElementType Element;
    SplayTree Left;
    SplayTree Right;
};

typedef struct SplayNode *Position;
static Position NullNode = NULL;

SplayTree Initialize(void)
{
    if(NullNode == NULL)
    {
        NullNode = malloc(sizeof(struct SplayNode);
        if(NullNode == NULL)
            FatalError("Out of space!!!");
        NullNode->Left = NullNode->Right = NullNode;
    }
    return NullNode;
}



分享 AVL树

BUPT-Spider
2个月前

AVL树相关代码

#ifndef _AvlTree_H

struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

AvlTree MakeEmpty(AvlTree T);
Position Find(ElementType X, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElementType X, AvlTree T);
AvlTree Delete(ElementType X, AvlTree T);
ElementType Retrieve(Position P);

#endif /*_AvlTree_H*/

/*Place in the implementation file*/
struct AvlNode
{
    ElementType Element;
    AvlTree Left;
    AvlTree Right;
    int Height;
};

//calculate the height
static int Height(Position P)
{
    if(P == NULL) return -1;
    else return P->Height;
}

AvlTree Insert(ElementType X, AvlTree T)
{
    if(T == NULL)
    {
        /*Create and return a one-node tree*/
        T = malloc(sizeof(struct AvlNode));
        if(T == NULL) FatalError("Out of space!!!");
        else
        {
            T->Element = X;
            T->Height = 0;
            T->Left = T->Right = NULL;
        }
    }
    else if(X < T->Element)
    {
        T->Left = Insert(X, T->Left);
        if(Height(T->Left) - Height(T->Right) == 2)
        {
            if(X < T->Left->Element) T = SingleRotateWithLeft(T);
            else T = DoubleRotateWithLeft(T);
        }
        else if(X > T->Element)
        {
            T->Right = Insert(X, T->Right);
            if(Height(T->Right - Height(T->Left) == 2)
            {
                if(X > T->Right->Element) T = SingleRotateWithRight(T);
                else T = DoubleRotateWithRight(T);
            }
        }
    }
    /*Else X is in the tree already; we'll do nothing*/

    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}

static Position SingleRotateWithLeft(Position K2)
{
    Position K1;

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;

    return K1;
}

static Position DoubleRotateWithLeft(Position K3)
{
    K3->Left = SingleRotateWithRight(K3->Left);

    return SingleRotateWithLeft(K3);
}




分享 再散列

BUPT-Spider
2个月前

再散列代码实现

HashTable Rehash(HashTable H)
{
    int i,OldSize;
    Cell *OldCells;

    OldCells=H->TheCells;
    OldSize=H->TableSize;

    /*Get a new,empty table*/
    H=InitializeTable(2*OldSize);

    /*Scan through old table,reinserting into new*/
    for(i=0;i<OldSize;i++)
        if(OldCells[i].Info==Legitimate)
            Insert(OldCells[i].Element,H);

    free(OldCells);

    return H;
}



BUPT-Spider
3个月前

C++代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=10010;

int msize,n,m;
int h[N];

bool is_prime(int x)
{
    if(x==1) return false;

    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0) return false;
    }
    return true;
}//is_prime

int main(void)
{
    scanf("%d%d%d",&msize,&n,&m);
    for(int i=msize;;i++)
    {
        if(is_prime(i)) 
        {
            msize=i;
            break;
        }
    }

    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);

        int index=x%msize;
        if(h[index])
        {
            int j;
            for(j=1;j<msize;j++)
            {
                int index_=index+j*j;
                if(index_>=msize) index_%=msize;

                if(!h[index_])
                {
                    h[index_]=x;
                    break;
                }
            }
            if(j==msize) printf("%d cannot be inserted.\n",x);
        }
        else h[index]=x;
    }

    int sum=0;
    for(int i=0;i<m;i++)
    {
        int x;
        scanf("%d",&x);

        int j;
        for(j=0;j<msize;j++)
        {
            int index=x%msize+j*j;
            if(index>=msize) index%=msize;
            if(h[index]==x||!h[index]) break;
        }
        sum+=j+1;
    }
    printf("%.1f\n",sum*1.0/m);

    return 0;
}




BUPT-Spider
3个月前

C++代码

//双链表
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e5+10;

int e[N],l[N],r[N],idx;

void init()
{
    r[0]=1,l[1]=0,idx=2;
}//init

void add(int k,int x)
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx;
    idx++;
}//add

void remove(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}//remove

int main(void)
{
    int m;
    cin>>m;

    init();

    while(m--)
    {
        string op;
        cin>>op;

        int k,x;

        if(op=="L")
        {
            cin>>x;
            add(0,x);
        }
        else if(op=="R")
        {
            cin>>x;
            add(l[1],x);
        }
        else if(op=="D")
        {
            cin>>k;
            remove(k+1);
        }
        else if(op=="IL")
        {
            cin>>k>>x;
            add(l[k+1],x);
        }
        else 
        {
            cin>>k>>x;
            add(k+1,x);
        }
    }

    for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<' ';
    cout<<endl;

    return 0;
} 





BUPT-Spider
3个月前

C++代码

#include<iostream>

using namespace std;

const int M=1e5+10;

int m;
int head,e[M],ne[M],idx;

void init()
{
    idx=0;
    head=-1;
}//init

void add_to_head(int x)
{
    e[idx]=x,ne[idx]=head,head=idx++;
}//add_to_head

void remove(int k)
{
    ne[k]=ne[ne[k]];
}//remove

void add(int k,int x)
{
    e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}//add

int main(void)
{
    init();

    cin>>m;
    while(m--)
    {
        int k,x;

        char op;
        cin>>op;
        switch(op)
        {
            case 'H':
                cin>>x;
                add_to_head(x);
                break;
            case 'D':
                cin>>k;
                if(!k) head=ne[head];
                remove(k-1);
                break;
            case 'I':
                cin>>k>>x;
                add(k-1,x);
                break;
        }
    }

    for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<' ';
    cout<<endl;

    return 0;
}