数据结构-U2 线性表

2.1 线性表

线性表，具有相同类型的，有序序列。

除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

线性表是逻辑结构。顺序表和链表是存储结构。

基本操作

初始化表,InitList(&L)
求表长,Length(L)
按值查找操作,LocateElem(L,e)
按位查找操作,GetElem(L,i)
插入操作,ListInsert(&L,i,e)
删除操作,ListDelete(&L,i,&e).【删除表L中的第i个位置的元素，并用e返回删除元素的值】
输出操作,PrintList(L)
判空操作,Empty(L)
销毁操作,DestoryList(&L)【销毁线性表，并放出线性表L所占用的内存空间】

# elem,是element元素的缩写
# &表示c++中的引用调用。&在C中是取地址符

2.2 线性表的顺序表示

又叫顺序表。

// 静态分配的顺序表的存储结构
#define MaxSize 50 // 定义线性表的最大长度
typedef struct{
    ElemType data[MaxSize]; // 顺序表的元素
    int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义

// 动态分配的顺序表的存储结构（不需要为线性表一次性地划分所有空间）
#define InitSize 100 // 表长度的初始定义
typedef struct{
    ElemType *data; // 指示动态分配数组的指针
    int MaxSize,Length; // 数组的最大容量和当前个数
}SeqList; // 动态分配数组顺序表的类型定义

顺序表的初始化

// 静态
//SqList L; 	// 声明一个顺序表
void InitList(SqList &L){ // 此处采用C++引用语法，纯C语言可用指针替代
    L.length = 0; // 顺序表的初始长度为0。（声明：原有数据会被后续写入覆盖）
}

// 动态
void InitList(SeqList &L){
    L.data = (ElemType *)malloc(InitSize*sizeof(ElemType)); // 分配存储空间
    L.length = 0; // 顺序表的初始长度为0
    L.MaxSize = InitSize; // 初始存储容量
}

插入操作

在第i个位置插入新元素e。

bool ListInsert(SqList &L,int i,ElemType e){
    if(i<1||i>L.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;
}

删除操作

删除表中第i个元素。

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

按值查找（顺序查找）

查找第一个元素等于e的元素，并返回其位序。

int LocateElem(Sqlist &L,ElemType e){
    int i;
    for(i=0;i<L.length;i++)
        if(L.data[i]==e)
            return  i+1;
    return 0;
}