[数据结构与算法]数据结构学习笔记——线性表

线性表：由同类型数据元素构成有序序列的线性结构。

表中元素个数称为线性表的长度。

线性表没有元素时，称为空表。

表起始位置称表头，表结束位置称表尾。

在数据结构中，我们可以利用数组的连续存储空间顺序存放线性表的各个元素。

typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    int last;
};
struct LNode L;
List 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.查找

int Find(ElementType X,List PtrL)
{
    int i=0;
    while(i<=PtrL->last&&PtrL->Data[i]!=X)
        i++;
    if(i>PtrL->Last) return -1;//如果没有找到，返回-1
    else return i;//找到后返回存储位置
}

3.插入（第i(1≤i≤n+1)个位置上插入一个值为x的新元素）

void insert(ElementType X,int i,List PtrL)
{
    int j;
    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.删除操作实现

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