bb.h

数据结构中相关ADT的C++实现,注解清晰,让你快速掌握

//实现单链表逆置算法
#include<iostream.h>
#include <stdlib.h>
typedef struct lnode
{//结点类型
	int data;
	lnode * next;
}*link,* position;
typedef struct  list
{//链表类型
	link head,tail;
	int len;
}linklist;
int makenode(link & p,int e)
{//分配由P指向的值为e结点,并返回1;若分配失败,返回0
	p=new lnode;
	p->data=e;
	p->next=NULL;
	if(p)return 1;
	else return 0;
}
void initlist(linklist & l)
{ //构造一个空的线性链表
if(	makenode(l.head,0))
{
	l.tail=l.head;
	l.len=0;
}
else exit(0);

}	
lnode * remove(linklist & l,link & q)
{
	link p;
	if(!l.head->next)exit(0);
	p=l.head;
	while(p->next!=l.tail)
		p=p->next;
	q=l.tail;
	l.tail=p;
	l.tail->next=NULL;
	l.len--;
	return q;
}
void Insbefore(linklist & l,link & p,link s)
{
	link q;

if(l.head==p)exit(0);
	q=l.head;
	while(q->next!=p)
		q=q->next;
s->next=p;
q->next=s;
p=s;
l.len++;
}
void Listtraverse(linklist l)
{
	link p=l.head;
	for(int i=1;i<=l.len;i++)
	{
		p=p->next;
		cout<<p->data<<endl;
	}
}
void listreverse(linklist & l)
{
	link p,q;
	p=l.head;
	for(int i=1;i<l.len;i++)
	{
		p=p->next;
    q=remove(l,q);
	Insbefore(l,p,q);
	}
}
void append(linklist &  l,link s)
{//将指针S所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点
	//之后,并改变链表L的尾指针指向新的尾结点
     l.tail->next=s;
		 l.len++;
		 l.tail=s;
     while(s->next)
	 {
		 s=s->next;
		 l.tail=s;
		 l.len++;
	 }
}
void main()
{
	int e;
	linklist l;
	initlist(l);
	link s;
	cout<<"请输入数，输入0为停止："<<endl;
	cin>>e;
    while(e!=0){
	 if(makenode(s,e)) 
	 append(l,s);
	 else exit(0);
	  cin>>e;
	}
	Listtraverse(l);
	listreverse(l);
	Listtraverse(l);
}