线性表 顺序存储实现

（1）如何存储

//如何存储
typedef struct
{
    ElementType Data[MAXSIZE];
    int Last;
}List;
List L, *PtrL;

访问下标为i的元素：L.Data[i] 或 PtrL->Data[i]

线性表的长度：L.Last+1 或者 PtrL->Last+1

（2）初始化（建立空的顺序表）

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

（3）查找

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;
}

查找成功的平均比较次数为（n+1）/ 2（第一次比较就找到或者最后一次比较才找到），平均时间性能为O（n）。

（4）插入

插入到第 i 个位置（即下标+1：1<=i<=n+1）上插入一个值为X的新元素）

//插入
void Insert(ElementType X, int i, List *PtrL)
{
    if (PtrL->Last == MAXSIZE-1)
    {
        printf("表满");
        return;
    }
    if (i < 1 || PtrL->Last+2)
    {
        printf("位置不合法");
        return;
    }
    for (int j = PtrL->Last; j >= i-1; --j)
    {
        PtrL->Data[j+1] = PtrL->Data[j]; //将 an~a1 依次向后移动一位
    }  
    PtrL->Data[i-1] = X;//插入新元素
    PtrL->Last++; //Last仍指向最后元素
return;
}

（5）删除

//删除
void Delete(int i, List *PtrL)
{
    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]; //将ai+1~an顺序向前移动
    }
    PtrL->Last--;
return;
}

平均移动次数为(n-1)/2，平均时间性能为O(n)。

线性表 顺序存储实现

原文：http://www.cnblogs.com/claremore/p/4721888.html