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

核心提示：以下是用c++实现的链表的数据结构，笔者还做了栈，用c++语言实现基本的数据结构（1），队列，循环队列，串等数据结构，如有需要者请E-mail:cangzhu@163.com#include"iostream.h"#include"stdio.h"#include"st

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