adjust.h

C++编写的一个模拟短信接受予删除短信

#include	"stdlib.h"
#include	"stdio.h"

#ifndef ADJUST_H
#define ADJUST_H

#define	ERROR					-1
#define	OK						0

typedef	int	Status;
typedef	int		LValueType;

//////////////////////////////////////////////////////////
//	前视定义
//////////////////////////////////////////////////////////

typedef	struct _LListNode	LListNode; //节点类型
typedef	struct _LList		LList; //线性表类型

typedef	LListNode*			Position; //节点位置类型
typedef	int					Rank; //节点秩类型

/////////////////////////////////////////////////////////
//	线性表类型定义（双向链表实现）
/////////////////////////////////////////////////////////
typedef	struct _LListNode	{
	LValueType		value; //数据域
	Position			next; //后继指针
	Position			prev; //前驱指针
	LList*			list; //所属的线性表
}	LListNode; //线性表节点

typedef	struct _LList {
	int				id; //标识
	Position			header; //头结点哨兵
	Position			trailer; //尾节点哨兵
	int				length; //当前实际长度
}	LList; //线性表

/////////////////////////////////////////////////////////
//	线性表的双向链表实现
/////////////////////////////////////////////////////////



/*
*	构造一个空的线性表（用id标识）
************************************************************************/
LList*		ListInit(int	id)
{
	static		int sid = 0;
	LList*		L = (LList*)malloc(sizeof(LList));

	if (id > sid)	sid = id;
	else				id = sid++;

#if defined(VERBOSE)
	printf("Creating List%d...", id);
#endif

	L->header = (Position)malloc(sizeof(LListNode));
	L->trailer= (Position)malloc(sizeof(LListNode));
	L->header->prev	= NULL; //头结点哨兵
	L->header->next	= L->trailer;
	L->header->list	= L;
	L->trailer->next = NULL; //尾结点哨兵
	L->trailer->prev	= L->header;
	L->trailer->list	= L;

	L->length		= 0; //长度为0
	L->id			= id; 

#if defined(VERBOSE)
	printf("done\n");
#endif

	return(L);
}

/*
*	查询L的规模
************************************************************************/
int			ListLength(LList*	L)
{
	return L->length;
}

/********************************************************/
bool ListEmpty(LList* L)
{
	if(L->length)return 0;
	else return 1;
}

/*
* 若L非空，则返回L首节点的位置；否则返回NULL
* O(1)
************************************************************************/
Position		ListFirst(
						  LList*		L)
{
	return(ListEmpty(L) ? NULL : L->header->next); //头元素的后继
}


/*
*	若v不是v->list的首节点，则返回其前驱的位置；否则返回NULL
* 注意：尾节点的前驱就是末节点
************************************************************************/
Position		ListPrev(
						 Position	v)
{
	return (v->list->header == v->prev) ? NULL : v->prev; //直接返回v的前驱
}

/*
*	若v不是v->list的末节点，则返回其后继的位置；否则返回NULL
* 注意：头节点的后继就是首节点
************************************************************************/
Position		ListNext(
						 Position	v)
{
	return (v->list->trailer == v->next) ? NULL : v->next; //直接返回v的后继
}
/*
* 取L[i]的位置
* i可能越界
************************************************************************/
Position		ListRank2Pos(
							 LList*		L,
							 Rank			i)
{
	if (0 > i || i >= ListLength(L))	return(NULL);//秩越界

	Position	p = ListFirst(L); //从首元素开始
	while (0 < i--) //沿着线性表，依次
		p = ListNext(p); //跳过i-1个元素

	return(p);
}

/*
*	删除L[i]，L的长度减1，并返回被删除节点的数据域
* 0 <= i < ListLength(list)
************************************************************************/
LValueType	ListDelete(
					   LList*		L,
					   Rank			i)
{
#if defined(VERBOSE)
	printf("Removing List%d[%d] ...", L->id, i);
#endif

	//	确定删除位置：紧接在h之后
	Position	h = (0 < i) ? ListRank2Pos(L, i-1) : h = L->header;
	Position	t = h->next->next;

	//	删除h与t之间的p
	Position	p = h->next; //p指向待删除结点
	LValueType	vBak = p->value; //备份数据域
	h->next = t;	t->prev = h; //摘除p
	free(p);	//并释放其占用的空间
	L->length --;

#if defined(VERBOSE)
	printf("done\n");
#endif

	return(vBak);
}




/*
*	销毁线性表L
************************************************************************/
Status		ListDestroy(LList*	L)
{
#if defined(VERBOSE)
	printf("Destroying List%d of size %d ...\n", L->id, L->length);
#endif

	while (!ListEmpty(L)) //逐一
		ListDelete(L, 0); //删除各个节点

	free(L->header);	free(L->trailer);
	free(L);		L = NULL;

#if defined(VERBOSE)
	printf("done\n");
#endif

	return(OK);
}


/*
*返回查找该元素时所需要访问的元素个数，同时把被访问的元素提到链表的最前端
******************************************************************************/
Rank Visitnode(LList *L, LValueType e)
{
	Position	p = L->header; //从首节点开始
	Rank	rank = 1;
	while (NULL != (p = ListNext(p))&&p-> value!= e) {//依次
            rank++;
	}
	if (p)//如果p节点存在
	{
		if( p== ListNext( L->header) )			//如果链表中除了头节点和尾节点外只有一个节点，则直接返回元素位置
			
			return(rank);

		else{
			ListPrev( p )->next=  ListNext( p );//把被访问的元素提到链表的最前端
			
			ListNext( p )->prev=  ListPrev( p );
			
			p->next=  ListFirst( L );
			
			ListFirst( L )->prev=  p;
			
			L->header->next=  p;
			
			p->prev=  L->header;
			}
		return( rank) ;//返回被访问的元素位置
	}

	else return(-1); //如果不存在需要访问的元素，则返回-1

}


/*
*	在L中第i个位置之前插入新的数据元素e，L的长度加1，返回新元素的位置
************************************************************************/
Position		ListInsert(
						   LList*		L,
						   Rank			i,
						   LValueType	e)
{
#if defined(VERBOSE)
	printf("Inserting %d as List%d[%d] ...", e, L->id, i);
#endif

	//	确定插入位置：介于h和t之间
	Position	h = (0 < i) ? ListRank2Pos(L, i-1) : L->header;
	Position	t = h->next;

	//	将新节点p插至h与t之间
	Position	p = (Position) malloc(sizeof(LListNode)); //生成新结点
	p->list	=	L; //记录下所属的线性表
	p->value	=	e; //赋值
	p->next	=	t; //插入1
	p->prev	=	h; //插入2
	h->next	=	p; //插入3
	t->prev	=	p; //插入4
	L->length ++;

	return(p);
}

#endif