线性表

---

阅读目录

一、线性表类型定义

1.定义

线性表是n个数据元素的有限序列

2.基本操作

InitList(&L)                #构造一个空的线性表L
DestroyList(&L)             #销毁线性表L
ClearList(&L)               #将L重置为空表
ListLength(L)               #返回L中数据元素个数
GetItem(L,i,&e)             #用e返回L中第i个数据元素的值
LocateElem(L,e,compare())   #返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据远古三不存在，则返回值为0
ListInsert(&L,i,e)          #在L中第i个位置之前插入新的数据元素e，L的长度加1
ListDelete(&L,i,&e)         #删除L的dii个数据元素，并用e返回其值，L的长度减1

二、顺序表

1.定义

线性表的顺序存储结构称为顺序表。
假设线性表的每个元素需占用l个存储单元，一般来说，线性表的第i个数据元素ai的存储位置为LOC(ai) = LOC(a1) + (i-1)*l

2.实现

由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。在此，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组
顺序开始为为1，区别于数组下标开始为0

2.1数据静态分配

#define MAXSIZE   50
typedef  struct{
    ElemType   elem[MAXSIZE]
    int        length;
    int        listsize
}SqList;

2.2数据动态分配

#define LIST_INIT_SIZE   100 //线性表存储空间的初始分配量
#define LISTINCREMENT    10  //线性表存储空间的分配增量
#define MAXSIZE   50

typedef  struct{
    ElemType   *data;    //存储空间的初始化分配量
    int        length;   //当前长度
    int        listsize  //当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList;

动态分配语句：
C      L.elem = (ElemType*)malloc(sizeof(ElemType)*InitSize);
C++    L.elem = new ElemType(InitSize);

2.3常用方法(C++)

2.3.1插入

bool ListInsert(sqList &L, int i, ElemType e){
    if(i <1 || i>L.length+1){   //插入的时候可以在最后插入，可以在最后插入，即length+1位，但是不能超过这一位(线性连续)
        return false;
    }
    if(L.length >= MaxSize){
        return false;
    }
    for(int j=L.length; j<=i; j--){
        L.data[j] = L.data[j-1]
    }
    L.data[i-1] = e;
    L.length++;
    return true;
}

2.3.2删除

bool ListDelete(sqList &L, int i, ElemType &e){
    if(i <1 || i>L.length){  //范围为1<=i<=L.length
        return false;
    }
    e = L.data[i]
    for(int j=i;j<L.length;j++){
        L.data[j-1] = L.data[j]
    }
    L.length--;
    return true;
}

2.3.3查找

int LocateElem(sqList L, ElemType e){
    int i;
    for(i=0;i<L.length;i++){
        if(L.data[i] == e){
            return i+1;  //返回数据索引下标+1即为值
        }
    }
    return 0;  //未查找到
}