数据结构笔记 3.线性表(1)顺序存储

线性表(List):0个或多个数据元素的有限序列

a₁是a₂的直接前驱, a₂是a₁的直接后继。a₁有且仅有一个直接后继，a_n有且仅有一个直接前驱。

一、线性表的抽象数据类型定义如下

ADT 线性表(List)
Data
    线性表的数据对象集合为{a1, a2,...an},每个元素的类型均为DataType.其中，除第一个元素a1外，每一个元素有且只有一个直接前驱，除了最后一个元素an外。每一个元素有且仅有一个直接后继元素。数据元素之间的关系是一对一的关系。

Operation
    InitList(*L):   //初始化操作，建立一个空的线性表L。
    ListEmpty(L);    //若线性表为空，返回true， 否则返回false.
    ClearList(*L):  //将线性表清空
    GetElem(L, i, *e): //将线性表L中的第i个元素位置返回给e
    LocateElem(L, e): //在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则， 返回0表示失败。
    ListInsert(*L, i, e): //在线性表L中的第i个位置插入新元素e
    ListDelete(*L, i,*e): //删除线性表L中的第i个位置元素，并且e返回其值
    ListLength(L): //返回线性表L的元素个数。
endADT

例：实现两个线性表集合A和B的并集操作。

分析： 我们只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。

/*将所有的在线性表Lb中但不在La中的元素插入到La中*/
void union(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);  //取Lb中第i个数据元素赋给e
        if(!LocateElem(La, e)) {   //La中不存在和e相同数据元素
            ListInsert(La, ++La_len, e);
        }
    }
}

二、 顺序存储结构

顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。示意图如下

//顺序存储的结构代码：
#define MAXSIZE 20
typedef int ElemType;
typedef struct {
    ElemType data[MAXSIZE];
    int length;
}SqList;

我们发现描述顺序存储结构需要三个属性：

• 存储空间的超始位置： 数组data, 它的存储位置就是存储空间的存储位置。
• 线性表的最大存储容量：数组长度MaxSize。
• 线性表的当前长度：length

1、 GetElem获得元素操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
/*Status是函数类型，其值是函数结果状态代码， 如OK等*/
/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/
/*操作结构： 用e返回L中第i个数据元素的值*/
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;
}

2、 插入操作ListInsert(*L, i, e)

插入算法思路：

• 如果插入位置不合理，抛出异常；
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
• 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
• 将要插入元素填入位置i处
• 表长加1

/**
 * 初始条件：顺序线性表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;
}

3、删除操作

删除算法思路:

1. 如果删除位置不合理，抛出异常
2. 取出删除元素
3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
4. 表长减1

/**
 * 1<=i<=ListLength(L)
 * 删除L的第i个数据元素， 并用e返回其值，L的长度减1
 */
Status ListDelete(SqList *L, int i, ElemType *e) {
	int k;
	if (L->length ==0) { //表为空
		return ERROR;
	}
	if(i<1 || i>L->length) { //删除位置不正确
		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(1)；， 而插入或删除时，时间复杂度都是O(n)。它比较适合元素个数不太变化，而更多是存取数据的应用。

4、 线性表顺序存储结构的优缺点