数据结构

第二章 线性表

线性表的顺序表示

顺序表的定义

1. 静态分配

# define MaxSize 50
typedef struct{
    Elemtype data[MaxSize];
    int length;
}Sqlist;

2. 动态分配

# define InitSize 100
typedef struct{
    ElemType *data;
    int MaxSize,length;
}SeqList;

// C初始动态分配
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);

// C++初始动态分配
L.data = new ElemType[InitSize];

顺序表基本操作的实现

插入操作

bool ListInsert(SqList &L, int i, ElemType e) //将元素e插入到顺序表L中的第i个位置
{
    if(i<1 || i>L.length+1)    //无效范围
        return false;
    if(L.length>MaxSize)     //空间已满
        return false;
    for (int j=L.length;j>=i;j--)   //将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;     //第i个位置放入e
    L.length++;        //线性表长度+1
    return true;
}

删除操作

bool ListDelete(SqList &L, int i, Elemtype &e){
    //删除顺序表L中的第i个位置元素，使用引用变量e返回
    if(i<1||i>L.length)    //无效范围
        return false;
    e = L.data[i-1];      //赋值给e
    for(int j=i;j<L.length;j++)   //将第i个位置后的元素前移
        L.data[j-1] = L.data[j];
    L.length--;           //线性表长度-1
    return true;
}

#### 按值查找

```c
int LocateElem(SqList L, ElemType e){
    //查找第一个值等于e的元素，返回位序
    int i;
    for(i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;   //下标为i的元素值等于e，返回其位序i+1
    return 0   //没找到
}