申請SAE

如果您發現本博客的外觀很難看,那是因為部分外觀文件被中國.國家.防火.牆屏.蔽所致!
請翻~牆!

我的Wordpress博客的地址: http://zhuyf.tk/

2011年10月22日 星期六

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;
}

沒有留言:

張貼留言