以下是用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::DestroyList(LinkList &L)
{
return OK;
}
void LinkList::FreeNode(Link 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::ListLength(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::PriorPos(LinkList L,Link p,Position &q)
{
Link QQ=L.GetHead(L);
if(p==qqp==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[i].next=NULL;
for(i=0;i<5;i++)
node[i].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[i]);
for(i=0;i<5;i++)
LL.InsAfter(LL,&node[i],&node2[i]);
for(i=0;i<5;i++)
cout<<LL.GetElem(&node[i])<<endl;
for(i=0;i<5;i++)
cout<<LL.GetElem(&node2[i])<<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<<"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))
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[i].next=NULL;
for(i=0;i<10;i++)
no[i].data=100*i;
LL.InsFirst(LL,&no[9]);
for(i=8;i>=0;i--)
LL.InsBefore(LL,&no[i+1],&no[i]);
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[i].data=i*6;
for(i=0;i<6;i++)
stu.InsFirst(stu,&stu_node[i]);
cout<<stu.GetHead(stu)->next->data<<endl;
}
|
