- 元素结点的单链表--kuan -

2007-04-12 晴

出处或者来源:课本

struct ALNode
{
ElemType data;
int next;
};
typedef ALNode ALinkList[MaxSize];

void InitList(ALinkList AL)
{
AL[0].next=0;

for(int i=2; i<MaxSize-1; i++)
AL.next = i+1; //构成空闲链接表
AL[MaxSize=1].next=0;//将空闲链接表的最后一个结点的指针域置0表示空指针

AL[1].next=2;// 以下标为1结点的指针域保存空闲链接表的表头指针
}

void ClearList(ALindList AL)//与初始化算法相同
{
AL[0].next=0;

for(int i=2; i<MaxSize-1; i++)
AL.next = i+1;
AL[MaxSize=1].next=0;

AL[1].next=2;
}

int ListSize(ALinkList AL)//得到单链表的长度
{
int p=AL[0].next;
int i=0;
while(p != 0)
{
i++;
p=AL[p].next;
}
return i;
}

int ListEmpty(ALinkList AL)//单链表是否为空
{
return(AL.next == 0);
}

ElemType GetElem(ALinkList AL, int pos)
{
if(pos<1)
{
cerr<<"pos is out range!"<<endl;
exit(1);
}
int p=AL[0].next;
int i=0;
while(p != 0)
{
i++;
if(i == pos)
break;
p=AL[p].next;//往后找
}
if(p != 0)
{
return AL[p].data;
}
else
{
cerr<"pos is out range!"<<endl;
}
}

void TraverseList(ALinkList AL)//遍历
{
int p = AL[0].next;
while(p != 0)
{
cout<<AL[p].data<<' ';
p=AL[p].next;
}
cout<<endl;
}

int Find(ALinkList AL, ElemThype &item)//查找一个给定值的第一个元素
{
int p = AL[0].next;
while(p != 0)
{
if(AL[p].data == item)
{
item = AL[p].data;
return 1;
}
else
p=AL[p].next;

}
return 0;
}

int Updata(ALinkList AL, const ElemType &item)//更新单链表中具有给定值的第一个元素
{
int p =AL[0].next;
while(p != 0)
{
if(AL[p].data == item)
{
AL[p].data == item;
return 1;
}
else
p =AL[p].next;
}
return 0;
}

void InserRear(ALinkList AL, const ElemType &item)//向单链表的末尾添加一个元素
{
int newptr;
newptr = AL[1].next; //从空闲表中取出表头结点
if(newptr == 0)
{
cerr<<"No empty node!"<<endl;
exit(1);
}
AL[1].next=AL[newptr].next; //使空闲表中第二个结点成为的表头结点

AL[newptr].data=item;
AL[newptr].next=0;

int p=AL[0].next;
while(AL[p].next != 0)//找表尾
p=AL[p].next;

AL[p].next = newptr;//插入
}

void InsertFront(ALinkList AL, const ElemType &item)//向单表的表头插入一个元素
{

int newptr;
newptr = AL[1].next;
if(newptr == 0)
{
cerr<<"No empty node!"<<endl;
exit(1);
}
AL[1].next=AL[newptr].next;
AL[newptr].data=item;

AL[newptr].next=AL[0].next;//把新结点插到表头
AL[0].next=newptr;
}

void Insert(ALinkList AL, const ElemType &item)
{

int newptr;
newptr = AL[1].next;
if(newptr == 0)
{
cerr<<"No empty node!"<<endl;
exit(1);
}
AL[1].next=AL[newptr].next;
AL[newptr].data=item;

//查找item的插入位置及前驱结点位置
int ap,cp;
ap=0;
cp=AL[0].next;
while(cp != 0)
{
if(ietm < AL[cp].data)
break;
else
{
ap=cp;
cp=AL[cp].next;
}

//插入
AL[newpr].next=cp; //AL[newpr].next=AL[ap].next;
AL[ap].next=newptr;
}
}

ElemType DeleteFront(ALinkList AL)//从单链表中删除表头元素
{
if(AL[0].next == 0)
{
cerr<<"Deleting from an empty list!"<<endl;
exit(1);
}
int p=AL[0].next;//取表头结点
AL[0].next=AL[p].next;//使第二个结点成为新表头结点

//把删除的结点插入到空闲表的表头
AL[p].next = AL[1].next;
AL[1].next = p;

return AL[p].data;
}

int Delete(ALinkList AL, const ElemType &item)//删除等于给定值的第一个元素
{
if(AL[0].next == 0)
{
cerr<<"Deleting from an empty list!"<<endl;
exit(1);
}
//查找被删除的结点及前驱结点
int ap,cp;
ap=0;
cp=AL[0].next;
while(cp !=0)
{
if(AL[cp].data == item)
break;
else
{
ap = cp;
cp = AL[cp].next;
}
}

//若有存在被　删除的元素则返回　0
if( cp == 0)
{
cerr<<"Deleted element is not exist!"<<endl;
return 0;
}

//从单链表醒到的下标为cp的结点
AL[ap].next = AL[cp].next;

//把删除的结点插入到空闲表的表头
AL[cp].next = AL[1].next;
AL[1].next = cp;

return 1;

}

void LinkSort(ElemType a[], int n)//排序
{
ALinkList b;
InitList(b);
int i;
for(i=0; i<; i++)
Insert(b,a);
int p = b[0].next;
i=0;
while(p != 0)
{
a[i++]=b[p].data;
p=b[p].next;
}
ClearList(b);
}

void WriteLinkList(ALinkList AL, char *fname)//把单链表数组AL的内容存储到由fname所指定的文件中
{
ofstream ofstr(fname);
if(Aofstr)
{
cerr<<"File"<<"\'"<<fname<<"\'"<<"no open!"<<endl;
exit(1);
}
for(int i=0; i<MaxSize; i++)
{
ofstr.write((char *)(AL+i), sizeof(ALNode));
ofstr.close();
}
}

void ReadLinkList(ALinkList AL, char *fname)
{
ifstream ifstr(fname, ios::in|ios::nocreate);
if(!ifstr)
{
cerr<<"File"<<"\'"<<fname<<"\'"<<"not found!"<<endl;
exit(1);
}
for(int i=0; i<MaxSize; i++)
ifstr.read((char*)(AL+i),sizeof(ALNode));
ifstr.close();
}.

[全部]

# posted by kuan @ 2007-04-12 12:48:54 评论(0)

笔名：

评论：

最多1000字。当前字数：0
*

联系方式：