线性表——顺序表

2.2、顺序表

1、定义

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

线性表逻辑上相邻的两个元素在对应的顺序表中存储位置也相邻，称为直接映射

随机存取的存储结构，就是可以通过首地址加逻辑序号直接在某个位置，存储或取出数据

顺序表类型定义：

typedef struct
{
    ElemType data[MaxSize];	//ElemType是自定义数据类型，是自己定义的，可以是int ,char等等
    int length;		//length成员存放线性表的实际长度
}SqList;
//data成员存放元素
//逻辑位序和物理位序相差1

2、运算的实现

建立顺序表

a[0..n-1]——整体创建顺序表

void CreateList(SqLiST *&L,ElemType a[],int n)	//由a中的n个元素建立顺序表
{
	int i = 0,k = 0;	//k表示L中的元素个数，初始值为0
    L = (SqList * )malloc(sizeof(SqList));	//分配存放线性表的空间
    while(i < n)	//i扫描数字a的元素
    {
        L->data[k] = a[i];	//将元素a[i]存放到L中
        k++;
        i++;
    }
    L->length = k;	//设置L的长度k
}
// *&L是引用类型指针，它代表的是原指针，它和原指针的关系 就相当于 两台手机共用一个账号，信息是共享的
//	*L是指针变量，存放的是内存地址，在函数中，它是形参，是单方向的，它的修改，改变了内存地址，但不会对原地址进行修改

//sizeof是一个操作符，返回一个内存空间的大小
//sizeof(SqList)返回SqList的内存空间大小
//malloc(sizeof(SqList))是分配一个这样的内存空间，并返回首地址
//(SqList * )malloc(sizeof(SqList)):将这个首地址作为SqList的指针

3、基本运算算法

（1）初始化线性表InitList(&L)

该运算的结构是构建一个空的线性表L。实际上只需将 length 成员设置为0

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

（2）销毁线性表 DestroyList(L)

void DestroyList(SqList *&L)
{
    free(L);	//释放线性表L 的内存空间
}

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

该运算返回一个值表示L是否为空表。若L 是控辩，返回true, 否则返回 false.

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

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

该运算返回顺序表L的长度。

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

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

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

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

（6）求线性表L 中指定位置的某个数据元素 GetElem(L, i, &e)：用e返回

bool GetElem(SqList *L, int i, ElemType &e)
{
    if(i < 1 || i > L->length)
    {
        return false;
    }
    e = L->data[i - 1];
    return true;
}
//本算法的时间复杂度为 O(1),体现了顺序表的随机存取特性

（7）L中第i个元素的值定位查找 LocateElem(L, e)：返回L 中第一个值域与 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)

在顺序表的第 i 个位置插入新元素 e。

bool ListInsert(SqList *&L, int i, ElemType e)
{
    int j;
    if(i < 1 || i > L->lenght + 1)
    {
        return false;	//如果 i 值不正确，返回 false,
    }
    i--;
    for(j = L->length; j > i; j--)
    {
        L->data[j] = L->data[j - 1];	//插入位置后面的元素向后移一个位置
    }
    L->data[i] = e;
    L->length++;
    return true;
}
//平均时间复杂度为 O(n)

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

bool ListDelete(SqList *&L,int i,ElemType &e)
{
	int j;
    if(i<1 || i>L->length)
        return false;		//参数错误时返回false
    i--;		//将顺序表逻辑序号 转化为 物理序号
    e=L->data[i];
    for(j=i;ilength-1;j++)
        L->data[j]=L->data[j+1];
    L->length--;
    return true;
}
//平均时间复杂度为 O(n)

4、算法设计

空间复杂度与临时变量有关，一个临时变量，空间复杂度为O(1)

解法一：（重建法）设删除A中所有值等于x元素后的顺序表为 A1，显然A1包含在A中，为此A1重建A的空间

思路：扫描顺序表A，重建A只包含不等于x的元素

void delnode1(SqList *&A, ElemType x)
{
    int k = 0, i;	//k记录值不等于X的元素个数
    for(i = 0; i < A->length; i++)
    {
		if(A->data[i] != x)	//若当前元素不为x，将其插入A中
        {
			A->data[k] = A->data[i];
             k++;	//不等于x的元素增1
        }
    }
    A->length = k;	//顺序表A的长度等于k
}

解法二（前移法）：用k记录顺序表A中等于x的元素个数，一边扫描A一边统计k值。

思路：将不为x的元素前移k 个位置，最后修改A的长度。

void delnode2(SqList *&A, ElemType x)
{
    int k = 0, i = 0;	//k记录值等于x的元素个数
    while(i < A->length)
    {
        if(A->data[i] == x)
        {
            k++;	//当前元素值为x时，k增1
        }else{
            A->data[i - k] = A->data[i];	//当前元素不为x时将其前移k个位置
        }
        i++;
	}
    A->length -= k;	//顺序表A的长度减K
}