Sqlist

顺序表的类型定义：

 顺序表的逻辑结构与物理结构相同，可用一维数组来表示，但是需要实现对表的增删改查，这会改变表的长度。
故定义类型Sqlist,其中包括一维数组elem、表示顺序表当前长度的整型变量length

#define LIST_INIT_SIZE 100  // 线性表存储空间的初始分配量
typedef struct{
    Elemtype elem[LIST_INIT_SIZE];
    int length;     //线性表当前长度
}Sqlist;

在顺序表定义中使用动态分配的数组（类C）

#include<stdlib.h>
typedef struct{
    Elemtype *elem;
    int length;     //线性表当前长度
}Sqlist;

Sqlist L;
L.elem = (Elemtype*)malloc(sizeof(ElemType) * MaxSize);
// 用完之后可以销毁malloc动态分配的存储区域
free(L.elem);

顺序表基本操作的实现

线性表的基本操作：

InitList(&L)    //初始化操作，建立一个空的线性表L
DestroyList(&L) //销毁已存在的线性表L
ClearList(&L)   //将线性表清空
ListInsert(&L, i, e)    //在线性表L中第i个位置插入e
ListDelete(&L, i, &e)   //删除线性表L中的第i个元素，用e返回
IsEmpty(L)  //若线性表为空，返回true,否则返回false
ListLength(L)   //返回线性表L中元素的个数
LocateElem(L, e)    //在L中查找与给定值e相等的元素，若成功则返回第一个与e相等的元素的下标，失败则返回0
GetElem(L, i, &e)   //将线性表L中的第i个元素返回给e

通用算法中预定义了一些常量和类型作为函数结果状态的表示，如下：

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0 
#define INFEASIBLE -1
#define OVERFLOW -2

// Status是函数的类型，其值是函数结果状态值，
typedef int Status
typedef char Elemtype

InitList函数的实现-顺序表L的初始化

王卓课上的伪代码：

#define OVERFLOW -2
Status InitList_Sq(SqList &L){  //创造一个空的顺序表L
    L.elem = new ElemType[MAXSIZE]; //为顺序表分配内存空间
    if(!L.elem) exit(OVERFLOW); //则退出程序，返回-2
    L.length = 0;   //空表长度为0
    return OK；
}

用C语言实现InitList函数：

#define OK 1
#define OVERFLOW -2
Status InitList_Sq(Elemtype *L, int Maxsize)
{
    L -> elem = (Elemtype*)malloc(sizeof(Elemtype) * Maxsize);  //为顺序表分配内存空间
    if(!(L -> elem)) return OVERFLOW;  //分配失败  
    L -> length = 0;    //空表长度为0
    return OK;
}

DestroyList函数的实现-释放存储空间

王卓课上伪代码：

void DestroyList(SqList &L)
{
    if(L.elem) delete L.elem;  //释放内存空间
}

C语言代码：

void DestroyList(SqList* L)
{
    if(L.elem) free(L -> elem);
}

ClearList函数的实现-清空线性表L

王卓课上伪代码：

void ClearList(Sqlist &L)
{
    L.length = 0;    
}

C语言代码：

void ClearList(Sqlist *L)
{
    L -> length = 0;    //将线性表的长度置零
}

GetLength函数的实现-获取线性表的长度

王卓课上伪代码：

int GetLength(SqList L) //无需采用引用方式传参
{
    return (L.length);
}

C语言代码：

int GetLength(Sqlist* L)
{
    return (L -> length);
}

IsEmpty函数的实现-判断线性表是否为空

王卓课上伪代码：

int IsEmpty(SqList L)
{
    if(L.length == 0) return 1;
    else return 0;
}

C语言代码：

int IsEmpty(SqList *L)
{
    if((L -> length) == 0) return 1；
    else return 0;
}

GetElem函数的实现-获取位置为i的数据元素

王卓课上代码:

Status GetElem(Sqlist L, int i, ElemType &e)
{
    if(i < 1 || i > L.length) return ERROR;
    e = L.elem[i - 1];
    return OK;
}

LocateElem函数的实现-顺序表的查找

该函数在线性表L中查找与给定值e相等的元素，若成功返回该元素在表中的序号，否则返回0

王卓课上伪代码：

int LocateElem(Sqlist L, ElemType e)
{
    for(int i = 0; i < L.length; i++)
    {
        if(e == (L.elem[i]))
        {
            return i + 1;   //查找成功
        }
    }
    return 0;   //查找失败，返回0
}

int LocateElem(Sqlist *L, ElemType e)
{
    for(int i = 0; i < (L -> length); i++)
    {
        if(e == (L -> elem[i]))
        {
            return i + 1;
        }
    }
    return 0;
}

对顺序表查找算法的时间复杂度分析：
 提出概念：平均查找长度ASL(Average Search length):

• 为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度
• 对于n个记录的表，查找成功时：

$$ASL = \sum_{i=1}^{n}P_iC_i$$

$$P_i是查找次数C_i的概率$$

InsertElem函数的实现-顺序表的插入

 顺序表的插入运算是指在表的第i（1<=i<=n+1）个位置上，插入一个新节点e，使长度为n的线性表变成长度为n+1的线性表，核心思路如下：

1. 判断插入位置i是否合法
2. 判断顺序表的存储空间是否已满，若满返回ERROR（OVERFOLW?)
3. 将第n至第i位的元素依次向后移动一个位置，空出第i个位置
    王卓课上伪代码如下：

Status ListInsert_Sq(Sqlist &L, int i, ElemType e)
{
    if(i < 1 || i > L.length + 1)   // i值不合法
    {   
        return ERROR;
    }
    if(L.length == MAXSIZE) //当前存储空间已满
    {
        return ERROR;
    }
    for(int j = length - 1; j >= i - 1; j--)    //元素后移
    {
        L.elem[j + 1] = L.elem[j];
    }
    L.elem[i - 1] = e;  //将e放到第i个位置
    L.length++;         //表长加1
}

 对顺序表插入算法的分析：
算法时间主要耗费在移动元素的操作上：

• 若插入在尾结点之后，则根本无需移动（特别快）
• 若插入在首结点之前，则表中元素全部后移（特别慢）
• 平均移动次数：

$$\frac{1}{n + 1}\sum_{i = 1}^{n}i = \frac{n}{2}$$

ListDelete函数的实现-顺序表删除

  线性表的删除运算是指将表的第i个节点删除使长度为n的线性表变成长度为n - 1的线性表
算法思想：

1. 判断删除位置i是否合法
2. 将欲删除的元素保留在e中
3. 将第i+1至第n位的元素依次向前移动一个位置
4. 表长减1，删除成功返回OK

Status ListDelete_Sq(Sqlist &L, int i)
{
    if((i<1) || (i > L.length))
    {
        return ERROR;
    }
    for(j = i; j < length; j++)
    {
        L.elem[j -1] = L.elem[j];
    }
    L.length--;
    return OK;
}

算法时间主要耗费在移动元素的操作上：

• 若删除尾结点，则无需移动
• 若删除首结点，则表中n-1个元素全部前移
• 平均次数：

  $$\frac{1}{n}\sum_{i=1}^{n}(n-i) = \frac{n-1}{2}$$

小结

顺序表的特点：

1. 利用数据元素的存储位置表示线性表中相邻元素之间的前后关系，即线性表的逻辑结构和存储结构一致
2. 在访问线性表时，可以快速地计算出任何一个数据元素地存储地址，因此可以粗略地认为，访问每个元素所花的时间相等
3. 将2.所述的存取元素的方法称为随机存取法

时间复杂度：

顺序表查找、插入、删除算法的平均时间复杂度为O(n)

空间复杂度：

顺序表操作算法没有占用辅助空间，空间复杂度为O(1)

优缺点：

• 优点：

1. 存储密度大
2. 可以随机存取表中任一元素

• 缺点：

1. 插入、删除某一元素时，需要移动大量元素
2. 浪费存储空间
3. 属于静态存储形式，数据元素的个数不能自由扩充