数据结构与算法-02-线性表

线性表

线性表概念

线性表(List):零个或者多个数据元素的有限序列线性表的长度应该小于等于数组长度，这样可以减少性能的损耗往线性表中插入数据的时候，插入位置后面的所有的数据都要往后挪动一位，同时要保证插入后的线性表长度要小于数组长度，插入的位置也要合理，不然会报错在删除数据的时候，删除位置后面的所有数据都要向前挪动一位，如果删除位置不合理，则报错

优点	缺点
无须为表示表中元素之间的逻辑关系而增加额外的储存空间	插入和删除操作需要移动大量元素
可以快速地存取表中任一位置的元素	当线性表长度变化比较大时，难以确定储存空间的容量
便于查找	造成储存空间的碎片

线性表结构

#define MAXSIZE 20
typedef int ElemType;
typedef struct{
	ElemType data[MAXSIZE];
	int length;	//线性表当前长度
}SqList;

(1) 并集操作

void unionL(List *La,list Lb)
{
	int La_len,Lb_len,i;
	ElemType e;
	La_len=ListLength(*La);
	Lb_len=ListLength(Lb); 

	for(i=1;i<=Lb_len;i++)
	{
		GetElem(Lb,i,&e); 
		if(!LocateElem(*La,e))
		{
			ListInsert(La,++La_len,e);
		}
	}

}

(2) 获取当前元素

*Status*是函数的类型，其值是函数结果状态代码，如*OK*等。初始条件：顺序线性表*L*已存在，*1<=i<=listLength(L)*操作结果：用*e*返回*L*中第*i*个数据元素的值。

#define OK 	1
#define ERROR 	0
#define TURE 	1
#define FALSE 	0

typedef int Status;

Status GetElem(SqList L, int i, ElemType *e)
{
	if(L.length==0 || i<1 || i>L.length)
	{
		return ERROR;
	}
	*e = L.data[i-1];
	return OK;
}

(3) 插入元素

初始条件：顺序线性表*L*已存在，*1<=i<=listLength(L)*操作结果：在*L*中第*i*个位置之前插入新的数据元素*e*，*L*长度*+1*

Status ListInsert(SqList *L, int i, ElemType e)
{
	int k;
	if(L->length == MAXSIZE)	//线性表满了
	{
		return ERROR;
	}
	if(i<1 || i>L->length+1)	//i越界
	{
		return ERROR;
	}
	if(i<=L->length)		//若插入位置不在表尾
	{
		//将要插入位置后数据元素向后移动一位
		for(k=L->length-1;k>i-1;k--)
		{
			L->data[k+1]=L->data[k];
		}
	}
	L->data[i-1]=e;			//插入新元素
	L->length++;
	return OK;
}

(4) 删除元素

初始条件：顺序线性表*L*已存在，*1<=i<-ListLength(L)*操作结果：删除*L*的第*i*个数据元素，并用返回其值，*L*的长度*-1*

Status ListDelete(SqList *L, int i, ElemType *e)
{
	int k;
	if(L->length ==0)		//链表为空
	{
		return ERROR;
	}
	if(i<1 || i>L->length)		//i越界
	{
		return ERROR;
	}
	*e = L->data[i-1];
	if(i<L->length)			//若删除位置不在表尾
	{
		for(k=i;k<L->length;k++)
		{
			L->data[k-1]=L->data[k];
		}
	}
	L->length--;
	return OK;
}

插入和删除的时间复杂度。
最好的情况：插入和删除操作刚好要求在最后一个位置操作，不需要移动任何元素，时间复杂度为O(1)

最坏的情况：要插入和删除的位置是第一个元素，意味着要移动所有的元素向后或者向前，时间复杂度为O(n)

平均情况：就取中间值O((n-1)/2)，即O(n)

优点：