cc.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 freenode(link & p)
{//释放P所指的结点
	delete p;
	p=NULL;
}
int initlist(linklist & l)
{ //构造一个空的线性链表
if(	makenode(l.head,0))
{
	l.tail=l.head;
	l.len=0;
	return 1;
}
else exit(0);

}
void destroylist(linklist & l)
{//销毁一个线性链表
	link p=l.head;
	while(p)
	{
		l.head=p->next;
		delete p;
		p=NULL;
		p=l.head;
	}
}
	
void clearlist(linklist & l)
{//清空链表
		link p=l.head;
	while(p->next)
	{
		l.head=p->next;
		delete p;
		p=NULL;
		p=l.head;
	}
	l.head->data=l.tail->data=0;
	l.head->next=l.tail->next=NULL;
	l.len=0;
}
void insfirst(link  h,link s)
{//已知h指向线性链表的头结点,将S所指结点插在第一个结点之前,注意第一个结点不是头结点
	if(!h->next){h->next=s;}
	else
	{
		s->next=h->next;
		h->next=s;
	}
}
void delfirst(link h,link & q)
{//已知h指向线性表的头结点,删除链表中的第一个结点并以q返回
	
	if(h->next==NULL)exit(0);
else	if(h->next->next!=NULL)
	{   q=h->next;
		h->next=h->next->next;
		
	}
else   {q=h->next;h->next=NULL;}
     

}

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++;
	 }
}
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 Insafter(linklist & l,link & p,link s)
{
	
	s->next=p->next;
	p->next=s;
	p=s;
	l.len++;
}
void Setcurelem(link & p,int e)
{
	p->data=e;
}
int Getcurelem(link p)
{
	return p->data;
}
int Listempty(linklist l)
{
	if(l.head->next==NULL)return 1;
	else return 0;
}
int Listlength(linklist l)
{
	return l.len;
}
lnode * Gethead(linklist l)
{ 
	return l.head;
}
lnode * Getlast(linklist l)
{
	return l.tail;
}
lnode * Priopos(linklist l,link p)
{
	if(p==l.head)return NULL;
	link q;
	q=l.head;
	while(q->next!=p)
		q=q->next;
	return q;
}
lnode * Nextpos(linklist l,link p)
{
	if(p==l.tail) return NULL;
	return p->next;
}
int Locatepos(linklist l,int i,link & p)
{
	
	if(l.len<i) return 0;
	p=l.head;
	for(int j=1;j<=i;j++) p=p->next;
	return 1;
}
int compare(int e1,int e2)
{
	if(e1>e2)return 1;
	if(e1<e2)return -1;
	if(e1==e2)return 0;
}
lnode * locatelem(linklist l,int e,int compare(int,int))
{
	if(l.head->next==NULL)return NULL;
	link p=l.head;
	do
	{
		p=p->next;
	if(!compare(p->data,e))return p;
	}
	while(p->next);
}
void Listtraverse(linklist l)
{
	link p=l.head;
	for(int i=1;i<=l.len;i++)
	{
		p=p->next;
		cout<<p->data<<endl;
	}
}
int mergelist(linklist & la,linklist & lb,linklist & lc,int compare(int ,int))
{
	link ha,hb,pa,pb;
	if(!initlist(lc))return 0;
	ha=Gethead(la); hb=Gethead(lb);
	pa=Nextpos(la,ha);  pb=Nextpos(lb,hb);
	while(pa&&pb)
	{
		link q;
		int a,b;
		a=Getcurelem(pa);b=Getcurelem(pb);
		if(compare(a,b)<=0)
		{
			
			delfirst(ha,q); append(lc,q);pa=Nextpos(la,ha);
		}
		else
		{
			delfirst(hb,q); append(lc,q); pb=Nextpos(lb,hb);
		}
	}
	if(pa) append(lc,pa);
	else append(lc,pb);
	freenode(ha);freenode(hb);
	return 1;
}
void main()
{
	linklist la,lb,lc;
	initlist(la);initlist(lb);
	link s;
	for(int i=1;i<=5;i++)
	{
		if(makenode(s,i))
			append(la,s);
	
	}
	for( i=6;i<=10;i++)
	{
		if(makenode(s,i))
			append(la,s);
	
	}
	if(mergelist(la,lb,lc,compare))
		Listtraverse(lc);
}