用c++语言实现基本的数据结构（1）

以下是用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<

　　 for(i=0;i<5;i++)

　　 cout<

　　 int e=22222;

　　 LL.SetCurElem(&node2[3],e);

　　 cout<<"changed:"<

　　 cout<<"先面遍历整个线性表："<

　　 for(Link q=LL.GetHead(LL)->next;q!=NULL;q=q->next)

　　 cout<data<

　　 cout<<"last:"<data<

　　 cout<

　　 if(LL.PriorPos(LL,&node[4],q))

　　 cout<data<

　　 else

　　 cout<

　　 cout<

　　 LL.PriorPos(LL,&node2[4],q);

　　 cout<data<

　　 cout<

　　 LL.NextPos(LL,&node2[3],q);

　　 cout<data<

　　 cout<<"remove :"<

　　 LL.Remove(LL,&node[3]);

　　 cout<<"先面遍历整个线性表："<

　　 for(i=0,q=LL.GetHead(LL)->next;i

cout<<"last:"<data<

　　 q=LL.GetLast(LL);

　　 Link qq;

　　 if(LL.NextPos(LL,q,qq))

　　 cout<data<

　　 else

　　 cout<data<<"是最后一个元素！"<

　　 cout<<"先面遍历整个线性表："<

　　 for(q=LL.GetHead(LL)->next;q!=NULL;q=q->next)

　　 cout<data<

　　 cout<<"remove :"<

　　 Link temp;

　　 if(LL.Search(LL,120,q))

　　 cout<

　　 LL.ClearList(LL);

　　 LNode test;

　　 test.data=10;

　　 LL.InsFirst(LL,&test);

　　 cout<<"先面遍历整个线性表："<

　　 for(q=LL.GetHead(LL)->next;q!=NULL;q=q->next)

　　 cout<data<

　　 if(LL.Search(LL,10,temp))

　　 cout<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<<"测试――先面遍历整个线性表："<

　　 for(q=LL.GetHead(LL);q->next!=NULL;q=q->next)

　　 cout<next->data<

　　 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<next->data<

}