线性表的概念及运算

• 线性表的逻辑结构
• • 定义
  • 特点
• 线性表的运算
• • 基本运算
• 线性表的顺序存储
• • 代码

线性表的逻辑结构

定义

线性表是n(n >= 0)个数据元素组成的有限序列。在表中，元素之间存在着线性的逻辑关系：表中有且仅有一个开始结点；有且仅有一个终端结点；除开始结点外，表中的结点均只有一个前驱结点(predecessor);处终端结点外，表中每个结点都仅有一个后继结点(successor)。根据它们之间的关系可以排成一个线性序列，记作：(a1,a2,…,an)。
在这里ai属于同一数据对象，具有相同的数据类型。线性表中数据元素的个数n为线性表的长度，称为表长，n = 0时称为空表。在非空表中的每个数据元素都有一个确定的位置。

特点

1. 同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象
2. 有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数
3. 有序性：线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>

线性表的运算

基本运算

对于线性表中的数据元素，可以进行查找、插入、删除等操作，线性表的长度可根据需要增加或缩短。具体有以下基本运算：
1.InitList(L), 线性表初始化，构造一个空的线性表L。
2.ListLength(L), 线性表的长度，并返回线性表L中数据元素的个数。
3.GetElem(L,i,x)，用x返回线性表中的第i个数据元素的值。
4.LocationElem(L,x)，按值查找，确定数据元素x在表中的位置。
5.ListInsert(L,i,x)，插入数据，在线性表L中第i个位置之前插入一个新元素x，L的长度加1。
6.ListDelete(L,i)，删除操作，删除线性表L中的第i个元素，L的长度减1。
7.ListEmpty(L)，判断线性表L是否为空，空表返回true，非空返回false。
8.ClearList(L)，将已知的线性表置为空表。
9.DestroyList(L)，销毁线性表L。
在实际应用中对线性表的运算有很多，有时候需要将多个线性表合并成一个线性表，或者进行有条件合并的，还有如分拆、复制、排序等。各种运算的具体采用哪种存储结构有关。

线性表的顺序存储

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表在逻辑结构上相邻的元素存储在连续的物理存储单元中，即：通过数据元素物理存储的连续性来反应元素之间逻辑上的相邻关系。采用顺序存储结构存储的线性表通常简称为顺序表。
顺序存储的线性表的特点：

1. 线性表的逻辑顺序与物理顺序一致;
2. 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
   

假设线性表中有n个元素，每个元素占k个存储单元，第一个元素的地址为Loc(a1),则第i个元素的地址Loc(ai): Loc(ai) = Loc(a1) + (i-1) * k;其中Loc(a1)称为基地址。

代码

用C语言定义线性表的顺序结构

#define ListSize 100      //线性表的最大长度
typedef int DataType;
typedef struct
{
    DataType data[ListSize];   //用数组存储线性表中的元素
    DataType length;           //顺序表中元素的个数
}SeqList, *PSeqList;

顺序表的初始化:初始化顺序表就是将顺序表的长度置为0。

void InitList(PSeqList L)
{
    if (L == NULL)
    {
        return;
    }
    L->length = 0;
}

顺序表的插入：
我们在插入的时候，我们需要先判断该表的长度有没有超出范围，如果没有超出范围，则就可以插入。插入的步骤是：

1. 将an~ai按从后向前的顺序向下移动，为新元素让出位置。
2. 将x置入空出的第i个位置。
3. 修改表长。

代码如下：

int Insert_SeqList(SeqList* L,int i ,ElemType x)
{
	int j;
	if (L -> length == MAXSIZE - 1)
	{
		printf("表满");
		return OVERFLOW;
	}
	if (i < 1 || i > L ->length + 1)
	{
		printf("位置错");
		return ERROR;
	}
	for (j = L->length; j >= 1; j--)
	L -> elem[j + 1] = L -> elem[j];
	L -> elem[i] = x;
	L -> length++;
	return TRUE; 
}

顺序表的删除
删除表中的第i个元素e，删除数据表中的第i个元素，需要将表中第i个元素之后的元素依次向前移动一位，将前面的元素覆盖掉。移动元素时要想将第i+1个元素移动到第i个位置，在将第i+2个元素移动i+1的位置，直到将最后一个元素移动到它的前一个位置，进行删除操作之前要判断顺序表是否为空，删除元素之后，将表长L->length–;
代码如下：

int DelList(PSeqList L, DataType i, DataType* e)
{
    if (L->length < 1)
    {
        printf("表为空！\n");
        return  0;
    }
    *e = L->data[i - 1];
    for (k = i; k < L->length; k++)
    {
        L->data[k - 1] = L->data[k];
    }
    L->length--;
    return *e;
}

按序号查找顺序表：
查找顺序表中第i个元素的值（按序号查找），如果找到，将将该元素值赋给e。查找第i个元素的值时，首先要判断查找的序号是否合法，如果合法，返回第i个元素对应的值。 如果不合法就继续遍历

代码如下：

nt GetData(PSeqList L, int i)
{
    if (L->length < 1 || (L->length > LengthList(L)))
    {
        return 0;
    }

    return L->data[i - 1];
}