我感覺這個鏈表雖然不是什麼高級演算法,但是卻很好用~在我們學校的評測系統中,有很多可以用這個鏈表寫的題~雖然速度沒有快速排序、堆排序等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;
}
沒有留言:
張貼留言