线性表

【什么是算法？】
空间复杂度S(n)：根据算法写成的程序在执行时占用存储单元的长度。
时间复杂度T(n)：根据算法写成的程序在执行时消耗的时间长度。
分析算法复杂度
Tworst(n)：最坏情况复杂度
Tav(n)：平均复杂度
【什么是线性表？】
“线性表（Linear List）”：由同类数据元素构成有序序列的线性结构
表中的元素个数称为线性表的长度，没有元素时称为空表，表的起始位置称为表头，结束位置称为表尾。
【线性表的顺序存储实现】

typedef struct Lnode *List;
struct Lnode {
          ElementType Data[MAXSIZE];
          int Last;     //线性表最后一个元素
};
struct LNode L;
List PtrL; //PtrL为指向结构体的指针 || struct Lnode * PtrL

访问下标为i的元素：L.Data[i]或者PtrL->Data[i]
线性表长度：L.Last+1或者PtrL->Last+1
【线性表的主要操作】
1、初始化（建立空的顺序表）

List MakeEmpty()
{
    List PtrL;
    PtrL=(List )malloc(sizeof(struct LNode));
    PtrL->Last=-1;
    return PtrL;
}

2、查找

/* 查找成功的平均比较次数是（n+1）/2
    平均时间性能是O（n） */
int Find()(ElementType X,List PtrL)
{
    int i=0;
    while(i<=PtrL->Last && PtrL->Data[i]!=X)
            i++;
     if(i>PtrL->Last)    return -1;
     else  return i;
}

3、插入

/* 第i个位置上插入一个值为x的新元素 */
void Insert(ElementType X, int i, List PtrL)
{
        /*MAXSIZE 数组大小*/
    if (PtrL->Last == MAXSIZE - 1) {
        printf("表满");
        return;
    }
    if (i<1 || i>PtrL->Last + 2) {
        printf("位置不合法");
        return;
    }
    for (j = PtrL->Last; j >= i - 1; j--)
        PtrL->Data[j + 1] = PtrL->Data[j];
    PtrL->Data[i - 1] = X;
    PtrL->Last++;
    return;
}

4、删除

/* 删除表的第i个位置上的元素 */
void Delete(int i, List PtrL)
{
    int j;
    if (i<1 || i>PtrL->Last + 1) {
        printf("不存在第%d个元素", i);
        return;
    }
    for (j = i; j <= PtrL->Last; j++)
        PtrL->Data[j - 1] = PtrL->Data[j];
    PtrL->Last--;
    return;
}