线性表

一、线性表及其逻辑结构

1.线性表的定义

线性表是一个具有相同特性的数据元素的有限序列。

• 有限：数据元素个数是有限的。
• 序列：数据元素由逻辑序号唯一确定。
• 相同特性：所有元素属于同一数据类型。
  线性表中所含元素的个数叫做线性表的长度，用n表示，n>=0。n=0时，表示线性表是一个空表，即表中不包含任何元素。
  线性表的逻辑表示为：
  
  
  线性表的9个基本运算如下：
  1.初始化线性表InitList(&L):构造一个空的线性表L。
  2.销毁线性表DestroyList(&L):释放线性表L占用的内存空间。
  3.判断线性表是否为空表ListEmpty(L):若L为空表，则返回真，否则返回假。
  4.求线性表的长度ListLength(L):返回L中的元素个数n。
  5.输出线性表DispList(L):线性表L不为空时，顺序显示L中个结点的值域。
  6.求线性表L指定位置的某个数据元GetElem(L,i,&e):用e表示返回L中第i(1<=i<=n)个元素的值。
  7.定位查找LocateElem(L,e):返回L中第一个值域与e相等的逻辑位序。若这样的元素不存在，则返回值为0。
  8.插入一个元素ListInsert(&L，i，e)：在L的第i（1<=i<=n)个元素之前插入新的元素e，L的长度增加1。
  9.删除数据元素ListDelete(&L,i,&e):删除L的第i(1<=i<=n)个元素，并用e返回其值，L的长度减1。

2.线性表的作用

• 程序员可以直接使用它来存放数据——作为存放数据的容器。
• 程序员可以直接使用它的基本运算——完成更复杂的功能。
  

二、线性表的顺序存储——顺序表

顺序存储结构就是把线性表中所有的元素按照顺序存储方法进行存储。
按逻辑顺序依次存储在存储器中一片连续的存储空间中。

1.顺序表类型定义

typedef struct
{
ElemType data[MaxSize];
int length;
};SqList;//顺序表类型

假设ElemType为char类型。
其中data成员存放元素，length成员存放线性表的实际长度。
注：逻辑位序和物理位序相差1。

2.顺序表运算的实现

1.建立顺序表
a[0…n-1]$\Rightarrow$顺序表L——整体创建顺序表。

void CreateList(SqList *&L,ElemType a[],int n)	//L表示顺序表中的指针
{
int i=0,k=0;
L=(SqList *)malloc(sizeof(SqList));
while(i<n)	//i扫描a中元素
{
L->data[k]=a[i];
k++;	//k记录插入到L中的元素个数
i++;
}
L->length=k;
}

其中，

顺序表的基本运算算法

(1)初始化线性列表InitList(L)

构造一个空的线性表L。实际上只需将length成员设置为0即可。

void InitList(SqList *&L)
{
L=(SqList *)malloc(sizeof(SqList));	//分配存放线性表的顺序表空间
L->length=0;
}

(2)销毁线性表DestoryList(L)

释放线性表L占用的存储空间。

void DestroyList(SqList *&L)
{
free(L);	//释放L所指向的内存空间
}

顺序表采用指针传递的优点：

• 更清楚地看到顺序表创建和销毁过程(malloc/free)。
• 在算法的函数之间传递更加节省空间(在函数体内不必创建值形参。

(3)判定是否为空表ListEmpty(L)

回一个值表示L是否为空表。若L为空表，则返回ture，否则返回false。

bool ListEmpty(SqList *L)
{
return(L->length==0);

(4)求线性表的长度ListLength(L)

返回顺序表L的长度。实际上只需要返回length成员的值即可。

int ListLength(SqList *L)
{
return(L->length);
}

(5)输出线性表DispList(L)

当线性表不为空时，顺序显示L中个元素的值。

void DispList(SqList *L)
{
	int i;
	if(ListEmpty(L))
	return;
	for(i=0;L->length;i++)
	printf("%c",L->data[i]);
	printf("\n");
}

(6)求某个数据元素值GetElem(L,i,e)

返回L中第i(1<=i<=ListLength(L))个元素的值，存放在e中。

bool GetElem(SqList *L,int i,ElemType &e)
{
	if(i<1||i>L->length)
	return false;
	e=L->data[i-1];
	return true;
	}

本算法时间复杂度为0(1)。体现顺序表的随机存取特性。

(7)按元素值查找LocateElem(L,e)

顺序查找第一个值与e相等的元素的逻辑位序，若这样的元素不存在，则返回值为0。

int LocateElem(SqList *L,ElemType e)
{
	int i=0;
	while(i<L->length&&L->data[i]!=e)
	i++;
	if(i>=L-length)
	return 0;
	else return i+1;
}

(8)插入数据元素ListInsert(L,i,e)

在顺序表L的第i(1<=i<=ListLength(L)+1)个位置上插入新的元素e。

算法如下：

bool ListInsert(SqList *&L,int i,ElemType e)
{
	int j;
	if(i<1||i>L->Length+1)
	return false;	//参数错误时返回false
	i--;	//将顺序表逻辑序号转化为物理序号
	for(j=L->Length;j>i;j--)	//将data[i...n]元素后移一位
	L->data[j]=L->data[j-1];
	L->data[i]=e;	//插入元素e
	L->length++;	//顺序表长度增加1
	return ture;	//成功插入返回ture
}

插入方式如图所示：

对于该算法：

• 最好：当i=n+1时，即新元素插入到表尾，移动次数为0；(最好时间复杂度为0(1))
• 最坏：当i=1时，也即新元素插入到表头，移动次数为n，达到最大值。(最坏时间复杂度0(n))
• 平均情况：假设新元素插入到任何一个位置的概率相同，即i=1,2,3…length的概率为p=1/n;那么i=1，循环n-1次，i=2，循环n-2次…i=n，循环0次。
  则平均循环次数=n(-1)p+(n-2)p+…+1*p=n/2。

(9)删除数据元素ListDelete(L,i,e)

删除顺序表L中第i(1<=i<=ListLengh(L))个元素。

bool ListDelete(SqList *&L,int i,ElemType &e)
{
	int j;
	if(i<1||i>L->length)
	return false;	//此处作用为卡i的范围，判断i的值是否合法
	i--;	//执行这一步是因为数组都是从0开始取的，这样可以将逻辑位序转换化成物理位序
	e=L->data[i];
	for(j=1;j<L->length-1;j++)
	L->data[j]=L->data[j+1];	//将数据表的每个元素前移一位
	L->length--;	//顺序表长度减少一位
	return true;	//删除成功
}

解释：此处声明函数之所以使用&，对于L目的是使其在该函数与main函数中指向同一地址，对于e，目的是使其在main函数与该函数对应同一份数据。

对于该算法，元素移动次数也与删除元素的位置有关

• 最好时间复杂度：当i=n时，移动0次； 0(1)
• 最坏时间复杂度：当i=1时，移动n-1次。0(n)
• 平均时间复杂度：(n-1)/2。

三、知识点总结