数据结构 408-2-1&2 - 数据结构 - 计算机科学 | Flüstern = Whispering's Blog = 无需过去，无关未来，只有现在

# 线性表的定义和基本操作

# 线性表的定义

线性表是具有相同数据类型 (每个数据元素所占空间一样大) 的 $n(n\ge 0)$ 个数据元素的有限序列 (有次序)，其中 n 为表长，当 n=0 时线性表是一个空表。若用 L 命名线性表，则其一般表示为： $L=(a_1,a_2,...,a_i,a_{i+1},...,a_n)$

e.g: 所有的整数按递增次序排列，是线性表吗？由于整数是无限的，因此这个序列不是线性表

$a_i$ 是线性表中 "第 i 个" 元素线性表中的位序
$a_1$ 是表头元素， $a_n$ 是表尾元素
除了第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

# 线性表的基本操作

InitList (&L)：初始化表。构造一个空的线性表 L，分配内存空间
DestroyList (&L)：销毁表操作。销毁线性表，并释放线性表 L 所占用的内存空间
ListInsert (&L,i,e)：插入表操作。在表 L 的第 i 个位置上插入指定元素 e
ListDelete (&L,i,e)：删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值
LocateElem (L,e)：按值查找操作。在表 L 中查找具有给定关键字值的元素
GetElem (L,i)：按位查找操作。获取表 L 中第 i 个位置的元素的值
LengthL (L)：求表长。返回线性表 L 的长度，即 L 中数据元素的个数
PrintList (L)：输出操作。按前后顺序输出线性表 L 的所有元素的值
Empty (L)：判空操作。若 L 为空表，则返回 true，否则返回 false

总之：增删改查、创建销毁

注意：需要将结果带回的函数需要用引用 '&'，函数命名要有可读性

# 顺序表的定义

顺序表：用顺序存储的方式实现线性表（顺序存储具体定义参考 1-1）

C 语言中，数据元素大小用 sizeof 函数来获得

静态分配（一般是数组）
- 直接定义顺序表的大小、长度、类型，储存空间是静态的，无法改变
动态分配（一般是链表）
- 用一个指示动态分配数组的指针来表示顺序表，定义初始长度、大小、类型，存储空间是动态的，可以随意修改
- 动态申请和释放内存空间：
  - C——malloc、free 函数（<stdlib.h> 头文件中）
```
L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
```
    C++——new、delete 关键字

顺序表的特点：

随机访问，即可以在 O (1) 的时间内找到第 i 个元素
存储密度高，每个节点只存储数据元素
拓展容量不方便 (即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)
插入、删除操作不方便，需要移动大量元素

# 顺序表的插入

静态分配顺序表的插入：

#define MaxSize 10  //定义最大长度
typedef struct{
    int data[MaxSize]; //用静态的"数组"存放数据元素
    int length; //顺序表的当前长度
}SqList; //顺序表的类型定义

bool ListInsert(SqList &L,int i,int 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;
}

int main(){
    SqList L;
    InitList(L);
    // 此处省略插入一些元素的代码
    ListInsert(L,3,3);
    return 0;
}

平均时间复杂度：O (n)

# 顺序表的删除

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

int main(){
    SqList L;
    InitList(L);
    // 此处省略插入一些元素的代码
    int e=-1;
    if(ListDelete(L,3,e))
        printf("done\n");
   	else
        printf("error\n");
    return 0;
}

平均时间复杂度 O (n)

# 顺序表的查找

顺序表的按位查找

#define MaxSize 10
typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
} SqList;

ElemType GetItem(SeqList L,int i){
    return L.data[i-1];
}

时间复杂度 O (1)

顺序表的按值查找

#define MaxSize 10
typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
} SqList;

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

时间复杂度 O (n)

数据结构考研408