数据结构——顺序线性表（向量）

参考文章：

数据结构（顺序表——线性表）_创建顺序线性表sl,调用initlist()函数对sl初始化-CSDN博客

以下是作为个人笔记，自己学习用。

线性表是具有相同特性的数据元素的一个有限序列，在线性表中每个数据元素由逻辑序号唯一确定。

线性表的特性：

1.有穷性：表中元素个数是有限的。

2.一致性：表中所有元素的性质相同，具有相同的数据类型。

3.序列性：各元素在线性表中的位置只取决于它们的序号，一个表中可以有两个相同的元素。

ADT List
{
	数据对象：
		D={ai|1<=i<=n,n>=0,ai为ElemType类型}//ElemType是自定义类型标识符
  数据关系：
    R={<ai,ai+1>|ai,ai+1含于Di=1,2,……n-1}
}

运算：

    InitList(&L):初始化线性表，构造一个空的线性表L
    DestroyList(&L):销毁线性表，释放线性表L所占用的内存空间
    
    ListEmpty(L):判断线性表是否为空，为空则返回真
    
    Listlength(L):求线性表的长度，返回L中元素的个数
    
    DispList(L):输出线性表，L不为空时，顺序显示L中各结点的值域
    GetElem(L,i,&e):求线性表中某个元素的值，用e来返回第i个值
    
    LocateElem(L,e):按元素值查找，返回第1个值域与e相等的元素的序号，若不存在则返回0
    ListInsert(&L,i,e):插入数据元素，在L中第i个位置插入一个新的元素e，L的长度加1
    ListDelete(&L,i,e):删除数据元素，删除L中第i个元素，并用e返回其值，L的长度减1

线性表的顺序存储结构

线性表的顺序存储结构——顺序表

线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到计算机存储器中指定存储位置的一块连续的存储空间中。

在C/C++中借助数组类型来实现顺序表，用数组存放线性表的元素及其逻辑关系。 顺序表采用数组来实现，但不能将任何一个数组都当作是一个线性表，二者的运算是不同的。

顺序表基本运算的实现

线性表元素的逻辑序号从1开始，而数组从0开始，要注意区分。

顺序表指针L和顺序表Q都可以都可以提供一个顺序表，前者的定义方式是SqList*L后者的定义方式是

SqList Q。前者引用length域的方式为L->length,后者引用length域的方式为Q.length。

之所以采用顺序表指针是为了方便顺序表的释放算法设计，并且在函数之间传递顺序表指针时会节省为形参分配的空间。

1.建立顺序表

#define maxsize 100
typedef int Elempyte;
typedef struct
{
	Elempyte date[100];
	int length;
}SqList;
 
void CraetList(SqList*& L, Elempyte a[], int n)
{
	int i=0, k=0;
	L = (SqList*)malloc(sizeof(SqList));
	while (i < n)
	{
		L->date[k] = a[i];
		k++; i++;
	}
	L->length = k;
}

形参L前加上引用符“&”的原因是建立好顺序表需要返回值给形参。

2.顺序表的应用示例

例1：假设一个线性表采用顺序表示，设计一个算法，删除其中所有值等于X的元素，要求时间复杂度O(n),空间复杂度O(1)。

void deletex(SqList*& L, Elempyte x)
{
	int i, k=0;
	for (i = 0; i < L->length; i++)
	{
		if (L->date[i] != x)
		{
			L->date[k] = L->date[i];
			k++;
		}
	}
	L->length = k;
}

void deletex(SqList*& L, Elempyte x)
{
	int i=0, k=0;
	while (i < L->length)
	{
		if (L->date[i] == x)
			k++;
		else
			L->date[i - k] = L->date[i];
		i++;
	}
	L->length -= k;
}