顺序表

1. 适用范围:

1.1. 顺序存储结构的优缺点

1.1.1. 缺点：

1. 插入或删除运算效率低
2. 不方便动态拓展长度

1.1.2. 优点

1. 空间占用少
   1. 无须为元素间的逻辑关系增加额外的储存空间

2. 性质:

1. 可以通过物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系

3. 梗概:

顺序表即采用顺序存储结构的线性表

3.1. 顺序存储结构梗概:

1. 规定结点序号从1开始
   1. 0号元素不使用
2. 描述线性表需要两个变量
   1. 一个last指针,表示实际最后一个元素在数组中的下标值
      1. 用来描述实际长度
   2. 一个Seq_MAXSIZE属性
      1. 用来表示最大长度

4. 在c语言的实现:

4.1. 定义顺序表:

梗概:

1. 习惯创建结构体类型Seqlist指代顺序表
   1. 习惯性规定结点序号从1开始
      1. 0号元素不使用
2. 描述线性表需要两个变量
   1. 一个last,表示实际最后一个元素在数组elem中的下标值
      1. 用来描述实际长度
   2. 一个Seq_MAXSIZE
      1. 用来表示最大长度 代码:

#define Seq_MAXSIZE 128
typedef char ElemType;
typedef struct{
    ElemType elem[Seq_MAXSIZE];
    int last;
}SeqList;

4.2. 按值查找

int Locate(SeqList *L, ElemType e){
    for(int i=0;(i<L->last)&&(L->elem[i]!=e);++i);
    if(i<=L->last) return(i+1);
    return(-1);
}

4.3. 插入元素

int InsList(SeqList *L,int i, ElemType e){
//插入位置不合法返回1,表满返回2,成功返回0
    int k;
    if((i<1)||(i>L->last+2))return 1;
    if(L->last>=Seq_MAXSIZE-1)return 2;
    for(k=L->last;k>=i-1;--k)
        L->elem[k+1]=L->elem[k];
    L->elem[i-1]=e;
    L->last++;
    return 0;
}

4.4. 删除元素

int DelList(SeqList *L, int i, ElemType *e){
    int k;
    if((i<1)||(i>L->last+1))return 0;
    *e =L->elem[i-1];
    for(k=i;i<=L->last;++k)
        L->elem[k-1]=L->elem[k];
    L->last--;
    return 1;
}

4.5. 合并两顺序表为第三个顺序表

void mergeList(SeqList *LA, SeqList *LB, SeqList *LC){
    int i=0,j=0,k=0,l;
    /*从两数组中取较小值,知道其中一个数组为空*/
    for(;i<=LA->last&&j<=LB->last;++i,++k)
        if(LA->elem[i]<=LB->elem[j])
            LC->elem[k]=LA->elem[i];
        else LC->elem[k]=LB->elem[j];
    /*两个for分别保证把两个数组的剩余元素都搬到新数组中*/
    for(;i<=LA->last;++i,++k)
        LC->elem[k]=LA->elem[i];
    for(;j<=LB->last;++j,++k)
        LC->elem[k]=LB->elem[j];
    LC->last=LA->last+LB->last+1;
}