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

注：数据结构三要素——逻辑结构、数据的运算、存储结构（物理结构）。存储结构不同，运算的实现方式不同

1 线性表的定义（数据结构三要素——逻辑结构）

线性表（Linear List）是具有相同数据类型的n（n≥0）个数据元素的有限 序列，其中n为表长，当n = 0时线

性表是一个空表。若用L命名线性表，则其一般表示为

L = (a1, a2, … , ai, ai+1, … , an)

线性表中每个数据元素所占空间一样大，是有次序的。所有整数按递增次序排列，但是不是线性表，因为不是有限个元素。

几个概念：

ai 是线性表中的“第i个”元素线性表中的位序，数据元素的位序从1开始。

a1 是表头元素；an 是表尾元素。

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

线性表 L逻辑结构

2 线性表的基本操作

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个位置的元素的值。

其他常用操作：

Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。

PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。

Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

Tips：

①对数据的操作（记忆思路） —— 创销、增删改查

②C语言函数的定义 —— <返回值类型> 函数名 (<参数1类型> 参数1，<参数2类型> 参数2，……)

③实际开发中，可根据实际需求定义其他的基本操作

④函数名和参数的形式、命名都可改变（Reference：严蔚敏版《数据结构》）Key：命名要有可读性

⑤什么时候要传入引用“&” —— 对参数的修改结果需要“带回来”

#include<stdio.h>
void test(int &x){
    x=1024;
    printf("test函数内部 x=%d\n",x);
}
int main() {
    int x = 1;
    printf("调用test前 x=%d\n",x);
    test(x);
    printf("调用test后 x=%d\n",x);
}

二 顺序表的定义

1 顺序表的定义

线性表是具有相同数据类型的n（n≥0）个数据元素的有限 序列。

顺序表——用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

typedef struct {
    int num; //号数
    int people; //人数
} Customer;

sizeof(int) = 4B

sizeof(Customer) = 8B

2 顺序表的实现——静态分配

Q：如果“数组”存满了怎么办？

A：可以放弃治疗，顺序表的表长刚开始确定后就无法更改（存储空间是静态的）

3 顺序表的实现——动态分配

4 顺序表的实现

顺序表的特点：

①随机访问，即可以在 O(1) 时间内找到第 i 个元素。代码实现：data[i-1];静态分配、动态分配都一样

②存储密度高，每个节点只存储数据元素

③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）

④插入、删除操作不方便，需要移动大量元素