linearlist.cpp

linearlist线性表的源代码数据结构需要的

//////////////////////////////////////////////////////////////////////////
//	线性表各种实现的公共部分
//////////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include <stdio.h>
#include "linearlist.h"

/*
 *	判断L是否为空表
 ************************************************************************/
bool			ListEmpty(LList*	L)
{
	return 0 == ListLength(L);
}

/*
 *	根据两个元素的大小，分别返回1、0或-1
 ************************************************************************/
int			Compare(
	LValueType	ele1,
	LValueType	ele2)
{
			if (ele1 > ele2)	return 1;
	else	if (ele1 < ele2)	return -1;
	else							return 0;
}

/*
 *	判断两个元素是否相等
 ************************************************************************/
bool			Equal(
	LValueType	ele1,
	LValueType	ele2)
{
	return ele1 == ele2;
}

/*
 *	判断元素1是否大于或等于元素2
 ************************************************************************/
bool			NLT( //No Less Than
	LValueType	ele1,
	LValueType	ele2)
{
	return ele1 >= ele2;
}

/*
 *	判断元素1是否大于元素2
 ************************************************************************/
bool			GT( //Greater Than
	LValueType	ele1,
	LValueType	ele2)
{
	return ele1 > ele2;
}

/*
 *	判断元素1是否小于或等于元素2
 ************************************************************************/
bool			NGT( //No Greater Than
	LValueType	ele1,
	LValueType	ele2)
{
	return ele1 <= ele2;
}

/*
 *	判断元素1是否小于元素2
 ************************************************************************/
bool			LT( //Less Than
	LValueType	ele1,
	LValueType	ele2)
{
	return ele1 < ele2;
}

/*
 * 插入首元素
 ************************************************************************/
Position		ListInsertFirst(
	LList*		L,
	LValueType	e)
{
	return(ListInsert(L, 0, e));
}

/*
 * 插入末元素——双向链表可利用trailer改进
 ************************************************************************/
Position		ListInsertLast(
	LList*		L,
	LValueType	e)
{
	return(ListInsert(L, ListLength(L), e));
}

/*
 * 删除首元素
 ************************************************************************/
LValueType	ListDeleteFirst(
	LList*		L)
{
	return(ListDelete(L, 0));
}

/*
 * 删除末元素——双向链表可利用trailer改进
 ************************************************************************/
LValueType	ListDeleteLast(
	LList*		L)
{
	return(ListDelete(L, ListLength(L)-1));
}

/*
 *	依次对L的每个数据元素调用函数visit()，并用visit()的返回值来更新各数据域
 * O(n)——假定visit()函数需要常数时间
 ************************************************************************/
void			ListTraverse(
	LList*			L,
	LValueType		(*visit)(LValueType))
{	//O(n)——假定visit()函数需要常数时间
	Position p = ListFirst(L); //从首元素开始
	while (NULL != p) {//逐一
		ListSetValue(p, (*visit)(ListGetValue(p))); //访问
		p = ListNext(p); //L的各个元素
	}
} //提问：为何不通过秩实现遍历？

/*
 *	依次对L的每个数据元素调用函数visit()
 * 一旦失败，则返回false；否则，返回true
 * O(n)——假定visit()函数需要常数时间
 ************************************************************************/
bool			ListCheck(
	LList*			L,
	bool				(*visit)(LValueType))
{	//O(n)——假定visit()函数需要常数时间
	Position p = ListFirst(L); //从首元素开始
	while (NULL != p) {//逐一
		if (!(*visit)(ListGetValue(p)))	return(false); //访问
		p = ListNext(p); //L的各个元素
	}

	return(true);
} //提问：为何不通过秩实现遍历？

/*
 *	根据不同类型，输出对应的数据域
 ************************************************************************/
LValueType	PrintLValue(LValueType elem)
{
#if		defined(LLIST_ELEM_TYPE_INT)
	printf("%d ", elem);

#elif		defined(LLIST_ELEM_TYPE_INT64)
	printf("%I64d ", elem);

#elif	defined(LLIST_ELEM_TYPE_CHAR)
	printf("%c ", elem);

#elif	defined(LLIST_ELEM_TYPE_FLOAT)
	printf("%f ", elem);

#elif	defined(LLIST_ELEM_TYPE_DOUBLE)
	printf("%f ", elem);

#endif

	return(elem);
}

/*
 * 根据不同的实现，按照最佳的方式将e插入L中
 * 注意体会不同实现下的最佳插入方式
 ************************************************************************/
Position		ListInsertAuto(
	LList*		L,
	LValueType	e)
{	//O(1)
#if	defined(LLIST_TYPE_ARRAY)
	return(ListInsertLast(L, e)); //后插

#elif	defined(LLIST_TYPE_LINKEDLIST)
	return(ListInsertFirst(L, e)); //前插

#else
	return(ListInsertFirst(L, e)); //前插

#endif
}

/*
 *	已知线性表listA和listB中的数据元素按值非递减排列
 * 将listA和listB归并成一个新的线性表
 * 新表中的数据元素也须按值非递减排列
 ************************************************************************/
LList*		ListMerge(
	LList*		listA,
	LList*		listB)
{	//O(n+m)
	#if defined(VERBOSE)
	printf("Merging List%2d and List%2d ...\n", ListGetID(listA), ListGetID(listB));
	#endif

//	初始化
	LList*	L	= ListInit(-1); //生成一个空表L

	Position	pA = ListFirst(listA); //指向listA中的当前元素
	Position	pB = ListFirst(listB); //指向listB中的当前元素

//	归并（注意不同插法的效率）
	while ((NULL != pA) && (NULL != pB)) { //不断
		LValueType	valueA = ListGetValue(pA);  //取listA当前节点的数据域
		LValueType	valueB = ListGetValue(pB);  //取listB当前节点的数据域

		if (NGT(valueA, valueB)) { //摘出更小的数据域valueMin
			ListInsertAuto(L, valueA);	pA = ListNext(pA);
		} else {
			ListInsertAuto(L, valueB);	pB = ListNext(pB);
		}
	} //while

//	listA的未完成部分
	while (NULL != pA) {	//listB先扫描完
		ListInsertAuto(L, ListGetValue(pA));	pA = ListNext(pA);
	}

//	listB的未完成部分
	while (NULL != pB) {	//listA先扫描完
		ListInsertAuto(L, ListGetValue(pB));	pB = ListNext(pB);
	}

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

	return(L);
}

/*
 * listA和listB表示两个集合
 * 将其并集中的元素组成一个新的线性表
 ************************************************************************/
LList*		ListUnion(
	LList*		listA,
	LList*		listB)
{	//O((n+1)*(m+1)
	#if defined(VERBOSE)
	printf("Getting the union of List%2d and List%2d ...\n", ListGetID(listA), ListGetID(listB));
	#endif

	int		lenA	= ListLength(listA);
	int		lenB	= ListLength(listB);

//	初始化
	LList*	L = ListInit(-1); //生成一个空表L
	Position	p;

//	复制listA（注意不同插法的效率）
	p = ListFirst(listA);
	while (NULL != p) { //逐一
		ListInsertAuto(L, ListGetValue(p)); //将listA中的元素复制到新表
		p = ListNext(p);
	}

//	复制listB（注意不同插法的效率）
	p = ListFirst(listB);
	while (NULL != p) { //逐一
		LValueType	elem = ListGetValue(p); //取出listB的各个元素
		if (lenA <= ListLocate(listA, elem, Equal)) //若该元素没有出现在listA中
			ListInsertAuto(L, elem); //则将其插入到listA的表头位置
		p = ListNext(p);
	}

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

	return(L);
}