C++ 用靜態鏈表進行排序

我感覺這個鏈表雖然不是什麼高級演算法，但是卻很好用～在我們學校的評測系統中，有很多可以用這個鏈表寫的題～雖然速度沒有快速排序、堆排序等n*logn的排序算法快，但是對於一些特殊的題目，這個還是不錯的。

代碼是我自己寫的，很劣質！
#include <fstream>
using namespace std;   
ifstream fin("lb.in");
ofstream fout("lb.out");
class data
{
public:
    int key;
    //Other members HERE...
    int sen;//前驱
    int next;//后继
};
data A[1000];
int top;//链表中元素的个数

void Insert(int key)
{
    int point=0;
    while (key>A[point].key)
    {
        point=A[point].next;
    }
    //Create a new node
    A[top].key=key;
    A[top].next=point;
    A[top].sen=A[point].sen;
   
    A[point].sen=top;//后继的前驱等于自己
   
    A[A[top].sen].next=top;//前驱的后继等于自己
   
    top++;
}

void DeleteOne(int key)
{
    int point=A[0].next;
    while(A[point].next!=-1)
    {
        if(A[point].key==key)
        {
            A[A[point].sen].next=A[point].next; //自己前驱的后继等于自己的后继
            A[A[point].next].sen=A[point].sen;  //自己后继的前驱等于自己的前驱
            return; //跳出函数
        }
        point=A[point].next;
    }
}

void DeleteAll(int key)
{
    int point=A[0].next;
    while(A[point].next!=-1)
    {
        if(A[point].key==key)
        {
            A[A[point].sen].next=A[point].next; //自己前驱的后继等于自己的后继
            A[A[point].next].sen=A[point].sen;  //自己后继的前驱等于自己的前驱
        }
        point=A[point].next;
    }
}


void print()
{
    int point=A[0].next;
    while(A[point].next!=-1)
    {
        fout<<A[point].key<<endl;
        point=A[point].next;
    }
}
void debug()
{
    for (int i=0;i<top;i++)
        fout<<i<<" "<<A[i].key<<" "<<A[i].sen<<" "<<A[i].next<<endl;
}
int main()
{

    //Initialize
    A[0].key=-1;A[0].next=1;A[0].sen=-1;
    A[1].key=65525;A[1].next=-1;A[0].sen=0;
    top=2;
    int num,key;
    fin>>num;
    for (int i=0;i<num;i++)
    {
        fin>>key;
        Insert(key);//插入一个关键字
    }
   
    fin>>num;
    for(int i=0;i<num;i++)
    {
        fin>>key;
        DeleteOne(key);//删除一个关键字
    }
   
    fin>>num;
    for (int i=0;i<num;i++)
    {
        fin>>key;
        DeleteAll(key);//删除所有这个关键字
    }
    //debug();
    //fout<<endl<<endl;
    print();
    return 0;
}

慶祝我用Psiphon 3翻牆成功！

以前，我都是用Goseas來翻牆，雖然Goseas是免費的，但是其帳戶需要兩天換一次，十分不方便～今天下午我用Google找到了Psiphon（賽風）3，它不僅可以傻瓜式翻牆，而且免費易用、速度尚可，十分不錯！特發此博文來慶祝我又一次虐爆GFW、虐爆方興賓校長！！

字典樹（Trie Tree）的應用舉例

字典樹是一種很牛的字符串操作算法，可以在短時間內完成字符串的插入、刪除、查找等功能，是NOIP、NOI必備資料之一。

關於字典樹的具體算法可以到維基百科 上學習，這裡我僅僅通過舉例來說明如何運用字典樹。


例題：

题目名	scanword
输入文件名	scanword.in
输出文件名	scanword.out
时间限制	1000 ms
内存限制	128 MB

全国英语四级考试就这样如期来了，可是小 y 依然没有做好充分准备。为了能够大学毕业可怜的小 y 决定作弊。
小 y 费尽心机，在考试的时候夹带了一本字典进考场，但是现在的问题是，考试的时候可能有很多的单词要查，小 y 能不能来得及呢？
输入格式：
第一行一个整数 N ，表示字典中一共有多少个单词（ N<=10000 ）。
接下来每两行表示一个单词，其中：
第一行是一个长度 <=100 的字符串，表示这个单词，全部小写字母，单词不会重复。
第二行是一个整数，表示这个单词在字典中的页码。
接下来是一个整数 M ，表示要查的单词数 (M<=10000) 。
接下来 M 行，每行一个字符串，表示要查的单词，保证在字典中存在。
输出格式：
M 行，每行一个整数，表示第 I 个单词在字典中的页数。
输入样例：
2
scan
10
word
15
2
scan
word
输出样例
10
15

這是一道基礎的字典樹的應用題，以下是我的代碼，十分簡單易懂，適合參加各種OI的選手。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int sonnum=26;
const char base='a';
class Trie
{
public:
    bool isStr;
    int Page;
    class Trie *son[sonnum];
};

Trie *NewTrie()
{
    Trie *temp=new Trie;
    temp->isStr=false;
    for (int i=0;i<sonnum;i++)
        temp->son[i]=NULL;
    return temp;
}

void InsertStr(Trie *pnt,char *s,unsigned int len,int P)
{
    Trie *temp=pnt;
    for (unsigned int i=0;i<len;i++)
    {
        if (temp->son[s[i]-base]==NULL)
            temp->son[s[i]-base]=NewTrie();
        temp=temp->son[s[i]-base];
    }
    temp->isStr=true;
    temp->Page=P;
}

int GetPage(Trie *pnt,char *s,unsigned int len)
{
    Trie *temp=pnt;
    for (unsigned int i=0;i<len;i++)
        temp=temp->son[s[i]-base];
    return temp->Page;
}

Trie *pnt=NewTrie();

void init()
{
    int N;
    cin>>N;
    for (int i=1;i<=N;i++)
    {
        char STR[101];
        int p;
        cin>>STR>>p;
        InsertStr(pnt,STR,strlen(STR),p);
    }
    cin>>N;
    for (int i=1;i<=N;i++)
    {
        char STR[101];
        cin>>STR;
        cout<<GetPage(pnt,STR,strlen(STR))<<endl;
    }
}

int main()
{
   
    freopen("scanword.in","r",stdin);
    freopen("scanword.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

NOIP2011提高组初赛 C++组 完善程序第一题 大整数开方

NOIP2011提高组初赛 C++组  完善程序第一题  大整数开方

输入一个正整数n（1<= n <10^100），试用二分法计算它的平方根的整数部分。

这是我补全的代码，已经运行通过：

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int SIZE=200;

struct hugeint
{
    int len,num[SIZE];
};

hugeint times(hugeint a,hugeint b)
{
    int i,j;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    for (i=1;i<=a.len;i++)
        for (j=1;j<=b.len;j++)
            ans.num[i+j-1]+=a.num[i]*b.num[j];
    for (i=1;i<=a.len+b.len;i++)
    {
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]=ans.num[i]%10;
    }
    if (ans.num[a.len+b.len]>0)
        ans.len=a.len+b.len;
    else
        ans.len=a.len+b.len-1;
    return ans;
}

hugeint add(hugeint a,hugeint b)
{
    int i;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    if (a.len>b.len)
        ans.len=a.len;
    else
        ans.len=b.len;
    for (i=1;i<=ans.len;i++)
    {
        ans.num[i]+=(a.num[i]+b.num[i]);
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]%=10;
    }
    if (ans.num[ans.len+1]>0)
        ans.len++;
    return ans;
}

hugeint average(hugeint a,hugeint b)
{
    int i;
    hugeint ans;
    ans=add(a,b);
    for (i=ans.len;i>=2;i--)
    {
        ans.num[i-1]+=(ans.num[i]%2)*10;
        ans.num[i]/=2;
    }
    ans.num[i]/=2;
    if (ans.num[ans.len]==0)
        ans.len--;
    return ans;
}

hugeint plustwo(hugeint a)
{
    int i;
    hugeint ans;
   
    ans=a;
    ans.num[1]+=2;
    i=1;
    while ((i<=ans.len) && (ans.num[i]>=10) )
    {
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]%=10;
        i++;
    }
    if (ans.num[ans.len+1]>0)
        ans.len++;
    return ans;
}

bool over(hugeint a,hugeint b)
{
    int i;
    if (a.len<b.len)
        return false;
    if (a.len>b.len)
        return true;
    for (i=a.len;i>=1;i--)
    {
        if (a.num[i]<b.num[i])
            return false;
        if (a.num[i]>b.num[i])
            return true;
    }
    return false;
}

int main()
{
    freopen("highsquare.in","r",stdin);
    freopen("highsquare.out","w",stdout);
    string s;
    int i;
    hugeint target,left,middle,right;
   
    cin>>s;
    memset(target.num,0,sizeof(target.num));
    target.len=s.length();
    for (i=1;i<=target.len;i++)
        target.num[i]=s[target.len-i]-'0';
    memset(left.num,0,sizeof(left.num));
    left.len=1;
    left.num[1]=1;
    right=target;
    do
    {
        middle=average(left,right);
        hugeint sp=times(middle,middle);
        if ( over(sp,target) )
            right=middle;
        else
            left=middle;
    }while (!over(plustwo(left),right));
   
    for (i=left.len;i>=1;i--)
        cout<<left.num[i];
    cout<<endl;
    return 0;
}