用c++实现的链表的数据结构

a11005422

以下是用c++实现的链表的数据结构。
笔者还做了栈，队列，循环队列，串等数据结构，如有需要者请
E-mail:cangzhu@163.com
#include\"iostream.h\"
#include\"stdio.h\"
#include\"stdlib.h\"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOAT -2
#define MAXSIZE 100
typedef int status;
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
} *Link,*Position;
class LinkList
{
private:
Link head;
int len;
public:
status InitList(LinkList &L);
status DestroyList(LinkList &L);
void FreeNode(Link p);
status ClearList(LinkList &L);
status InsFirst(LinkList &L,Link s);
status Remove(LinkList &L,Link p);
status InsBefore(LinkList &L,Link p,Link s);
status InsAfter(LinkList &L,Link p,Link s);
status SetCurElem(Link p,ElemType &e);
ElemType GetElem(Link p);
int ListLength(LinkList L);
Position GetHead(LinkList L);
Position GetLast(LinkList L);
status PriorPos(LinkList L,Link p,Position &q);
status NextPos(LinkList L,Link p,Position &q);
status Search(LinkList L,ElemType e,Position &p);
};
status LinkList::InitList(LinkList &L)
{
Link L1;
L1=(LNode *)malloc (sizeof(LinkList)*MAXSIZE);
L.head=L1;
L.head->next=NULL;
L.len=0;
if(L1==NULL)
  return OVERFLOAT;
else
  return OK;
}
status LinkList:estroyList(LinkList &L)
{
return OK;
}
void LinkList::FreeNode(Link p)
{
free(p);
}
status LinkList::ClearList(LinkList &L)
{
L.head->next=NULL;
len=0;
return OK;
}
status LinkList::InsFirst(LinkList &L, Link s)
{
s->next=L.head->next;
L.head->next=s;
len++;
return OK;
}
status LinkList::Remove(LinkList &L,Link p)
{
Link q=L.GetHead(L);
while(q->next!=p)
  q=q->next;
q->next=q->next->next;
L.len--;
return OK;
}
status LinkList::InsBefore(LinkList &L,Link p,Link s)
{
Link q=L.head;
while(q->next!=p)
  q=q->next;
s->next=q->next;
q->next=s;
len++;
return OK;
}
status LinkList::InsAfter(LinkList &L,Link p,Link s)
{
s->next=p->next;
p->next=s;
len++;
return OK;
}
status LinkList::SetCurElem(Link p,ElemType &e)
{
p->data=e;
return OK;
}
ElemType LinkList::GetElem(Link p)
{
return p->data;
}
int LinkList:istLength(LinkList L)
{
return L.len;
}
Position LinkList::GetHead(LinkList L)
{
return L.head;
}
Position LinkList::GetLast(LinkList L)
{
Link q=head;
while(q->next!=NULL)
  q=q->next;
return q;
}
status LinkList:riorPos(LinkList L,Link p,Position &q)
{

Link qq=L.GetHead(L);
if(p==qq||p==qq->next)
  return FALSE;
while(qq->next!=p)
  qq=qq->next;
q=qq;
return OK;
}
status LinkList::NextPos(LinkList L,Link p,Position &q)
{
if(p->next==NULL)
  return FALSE;
q=p->next;
return OK;
}
status LinkList::Search(LinkList L,ElemType e,Position &p)
{
Link q=L.GetHead(L);
int i=0;
do
{
  i++;
  q=q->next;
  if(i>L.len)
  return FALSE;
}
while(q->data!=e);
p=q;
return OK;
}
//下面是测试程序，读者可以按自己的要求，修改并测试！
void main()
{
/*LinkList LL;
LL.InitList(LL);
LNode node[5];
int i;
for(i=0;i<5;i++)
  node.next=NULL;
for(i=0;i<5;i++)
  node.data=10*i;
LNode node2[5];
int j;
for(j=0;j<5;j++)
  node2[j].next=NULL;
for(j=0;j<5;j++)
  node2[j].data=100+10*j;
for(i=0;i<5;i++)
  LL.InsFirst(LL,&node);
for(i=0;i<5;i++)
  LL.InsAfter(LL,&node,&node2);
for(i=0;i<5;i++)
  cout<<LL.GetElem(&node)<<endl;
for(i=0;i<5;i++)
  cout<<LL.GetElem(&node2)<<endl;
int e=22222;
LL.SetCurElem(&node2[3],e);
cout<<\"changed:\"<<LL.GetElem(&node2[3])<<endl;
cout<<\"先面遍历整个线性表：\"<<endl;
for(Link q=LL.GetHead(LL)->next;q!=NULL;q=q->next)
  cout<<q->data<<endl;

cout<<\"last:\"<<LL.GetLast(LL)->data<<endl;

cout<<node[4].data<<\"的前一个元素：\"<<endl;
if(LL.PriorPos(LL,&node[4],q))
  cout<<q->data<<endl;
else
  cout<<node[4].data<<\"是最前一个元素\"<<endl;
cout<<node2[4].data<<\"的前一个元素：\"<<endl;
LL.PriorPos(LL,&node2[4],q);
cout<<q->data<<endl;
cout<<node2[3].data<<\"的下一个元素：\"<<endl;
LL.NextPos(LL,&node2[3],q);
cout<<q->data<<endl;
cout<<\"remove :\"<<node[3].data<<endl;
LL.Remove(LL,&node[3]);
cout<<\"先面遍历整个线性表：\"<<endl;
for(i=0,q=LL.GetHead(LL)->next;i<LL.ListLength(LL);i++)
{
  cout<<q->data<<endl;
  q=q->next;
}
cout<<\"last:\"<<LL.GetLast(LL)->data<<endl;
q=LL.GetLast(LL);
Link qq;
if(LL.NextPos(LL,q,qq))
  cout<<qq->data<<endl;
else
  cout<<q->data<<\"是最后一个元素！\"<<endl;
cout<<\"先面遍历整个线性表：\"<<endl;
for(q=LL.GetHead(LL)->next;q!=NULL;q=q->next)
  cout<<q->data<<endl;
cout<<\"remove :\"<<node[3].data<<endl;
Link temp;
if(LL.Search(LL,120,q))
{
  LL.NextPos(LL,q,temp);
  cout<<\"120\"<<\"在\"<<temp->data<<\"之前\"<<endl;
  LL.PriorPos(LL,q,temp);
  cout<<\"120\"<<\"在\"<<temp->data<<\"之后\"<<endl;
}
cout<<LL.Search(LL,22222,temp)<<endl;
LL.ClearList(LL);
LNode test;
test.data=10;
LL.InsFirst(LL,&test);
cout<<\"先面遍历整个线性表：\"<<endl;
for(q=LL.GetHead(LL)->next;q!=NULL;q=q->next)
  cout<<q->data<<endl;
if(LL.Search(LL,10,temp))
  cout<<temp->data;
LNode no[10];
for(i=0;i<10;i++)
  no.next=NULL;
for(i=0;i<10;i++)
  no.data=100*i;
LL.InsFirst(LL,&no[9]);
for(i=8;i>=0;i--)
  LL.InsBefore(LL,&no[i+1],&no);
cout<<\"测试——先面遍历整个线性表：\"<<endl;
for(q=LL.GetHead(LL);q->next!=NULL;q=q->next)
  cout<<q->next->data<<endl;*/
int i;
LinkList stu;
stu.InitList(stu);
LNode stu_node[6];
for(i=0;i<6;i++)
  stu_node.data=i*6;
for(i=0;i<6;i++)
  stu.InsFirst(stu,&stu_node);
cout<<stu.GetHead(stu)->next->data<<endl;
}