数据结构--线性表（顺序结构）

1.线性表的定义和基本操作

1.1线性表以及基本逻辑

1.1.1线性表

（1）n(>=0)个数据元素的有限序列，记作（a1,a2,...an），其中ai是线性表中的数据元素，n是表的长度。

（2）ai是线性表中“第i个”元素在线性表中的位序。

注意：数组下标从0（a[0]）开始，位序从1开始.

1.1.2逻辑特征（n>0）

存在唯一的一个被称为“第一个”的数据元素。

存在唯一的一个被称为“最后一个”的数据元素。

除了第一个元素以外，其他元素均只有一个直接前驱。

除了最后一个元素外，其他元素均只有一个直接后继。

1.2线性表的基本操作

InitList(&L) //创建一个新的线性表L

ListEmpty(L) //判断L是否为空

ListLength(L) //求L的长度

GetElem(L,i,&e) //取i位置数据元素的值

ClearList(&L) //将L置为空表

ListInsert(&L,i,e) //在i位置插入值为e的数据元素

ListDelete(&L,i,&e) //删除i位置的元素e

1.ListInsert(&L,i,e) ，传值

2.ListDelete(&L,i,&e)，传引用

3.ListDelete(&L,i,*e)，传指针

1.形参改变->不会影响实参

2.3.形参改变->会影响实参（传引用，传指针）

下面用一张图来介绍形参和实参的区别：（by 通义千问）

传引用（&）适用场景：

1.需要函数修改原始数据。

2.对于大型数组或对象，为了节省内存开销和提升运算效率，使用引用传递。

一句话：对参数的修改结果要“带回来”。

2.线性表的顺序表示

2.1线性表和顺序表的定义

（1）线性表：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。

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

2.2静态分配和动态分配

2.2.1静态分配

#define MAX 10
int arr[MAX];
int n;         //数据元素个数小于n个

结构体进行封装：

#define MAX 100
typedef struct
{
    ElemType elem[MAX];
    int n;
}Sqlist;

2.2.2动态存储

（1）动态申请和释放内存空间

（2）C语言--malloc,free函数

L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize)
//malloc函数返回一个指针，需要用“(ElemType *)”强制类型转化为自己定义的数据元素类型指针

2.2.3顺序表基本操作实现

1.初始化顺序表InitList_Sq(&L)

操作结果：构造一个空的顺序表L.

Status InitList_Sq(SqList&L)       // 定义一个函数名为 InitList_Sq 的函数，参数是对 SqList 类型的引用 L，返回类型为 Status（这里 Status 可能是一个自定义的表示状态的类型）
{
    L.elem=(ElemType*)malloc(initial_size*sizeof(ElemType));  // 为 L 的 elem 属性分配一块内存空间，大小为 initial_size 个 ElemType 类型元素所需的空间，并将其地址转换为 ElemType*类型赋给 L.elem
    if(!L.elem)                    // 如果分配内存失败（L.elem 为假，即内存分配不成功得到的是 null 指针等情况）
        exit(OVERFLOW);            // 退出程序并表示存储空间分配失败（OVERFLOW 可能是一个表示溢出或错误的常量）
    L.length=0;                    // 将顺序表 L 的当前长度设置为 0
    L.listsize=initial_size;       // 将顺序表 L 的初始容量设置为 initial_size
    return 0;                      // 返回一个状态值（这里可能表示成功初始化）
}

下面是对顺序表中长度和容量的解释：

在顺序表（Sequential List）中：

一、长度（length）

指的是顺序表中当前实际存储的元素个数。

例如，如果有一个顺序表存储了 5 个整数，那么这个顺序表的长度就是 5。随着向顺序表中添加或删除元素，长度会相应地发生变化。

二、容量（listsize）

指的是顺序表预先分配的能够存储元素的最大空间大小。

例如，一开始创建顺序表时可能分配了一块可以存储 10 个整数的连续内存空间，那么此时这个顺序表的容量就是 10。当顺序表中的元素个数达到容量时，如果要继续添加元素，通常需要进行扩容操作（重新分配更大的连续内存空间）。而如果顺序表中的元素个数远小于容量，那么就存在一部分未被使用的内存空间。

2.销毁顺序表DestroyList_Sq(&L):

释放L所占用的内存空间

void DestroyList_Sq(SqList &L)
{
    free(L.elem); // 释放顺序表 L 的存储数据的内存空间。free 函数用于释放由 malloc、calloc 或 realloc 等函数分配的动态内存。
    L.elem = NULL; // 将 L 的 elem 指针设置为 NULL，避免出现悬空指针。
    L.length = 0; // 将顺序表的长度设置为 0，表示表中没有元素。
    L.listsize = 0; // 将顺序表的容量设置为 0。
}

3.判定是否为空表 ListEmpty_Sq(L):

若L为空表，返回1，否则返回0；

int ListEmpty_Sq(SqList L)
{
    if (L.length==0)
        return 1;
    else 
        return 0;

4.输出顺序表 DispList_Sq(L):

操作结果：当L不为空时，顺序显示L中各个元素的值。

Status DispList_Sq(SqList L)
{
    if (ListEmpty_Sq(L))
        return ERROR;
    // 如果顺序表为空（通过调用 ListEmpty_Sq 函数判断），则返回 ERROR（可能是一个表示错误的状态码）。

    for(i=0;i<=L-1;i++){
        print(L.elem[i]);
    }
    // 如果顺序表不为空，遍历顺序表，从第一个元素（下标为 0）开始，直到最后一个元素（下标为 L-1），逐个打印顺序表中的元素。

    return OK;
    // 遍历完成后，返回 OK（可能是一个表示成功的状态码）。
}

5.插入数据元素 ListInsert_Sq(&L,i,e):

操作结果：在顺序表L的第i个位置前插入新元素e.

ListInsert_Sq(SqList &L, int i, ElemType e) 
{
    if (i < 1 || i > L.length + 1) {
        return ERROR;
    }
    // 判断插入位置 i 是否合法，i 应该在 1 到（当前顺序表长度 + 1）之间，否则返回错误状态码 ERROR。

    if (L.length >= L.listsize) {
        newbase = (ElemType*)malloc(L.elem,(L.listsize + ElemNumber)*sizeof(ElemType));
        L.elem = newbase;
        L.listsize += ElemNumber;
    }
    // 如果当前顺序表中已存储的元素个数（L.length）等于或超过了顺序表的容量（L.listsize），则进行扩容操作。
    // 分配一块新的内存空间，大小为原来的容量加上 ElemNumber 个 ElemType 类型元素所需的空间，然后将新分配的内存地址赋给 L.elem，并更新顺序表的容量 L.listsize。

    for (j = L.length; j >= i; j--) {
        L.elem[j] = L.elem[j - 1];
    }
    // 将插入位置 i 及之后的元素向后移动一位。

    L.elem[i - 1] = e;
    // 在插入位置 i 处放入新元素 e。

    ++L.length;
    // 顺序表长度加一。

    return 1;
    // 返回一个表示成功的状态码（这里是 1）。
}

时间复杂度：

-最好情况：新元素插到表尾，不需要移动元素i=n+1,循环0次，T(n)=O(1);

-最坏情况：新元素插到表头，需要将原有的n个元素全部向后移动i=1,循环n次，T(n)=O(n);

-平均情况：,新元素插入到任意一个位置概率相同，需要的时间是n/2，考虑到时间复杂度量级，T(n)=O(n).

6.删除数据元素 ListDelete_Sq(&L,i,&e):

操作结果：删除顺序表L中的第i个元素，用引用变量e返回删除的元素。

ListInsert_Sq(SqList &L, int i, ElemType &e) 
{
    if (i < 1 || i > L.length) {
        return ERROR;
    }
    // 判断插入位置 i 是否合法。i 应该在 1 到顺序表的当前长度之间，如果不合法则返回错误状态码 ERROR。

    e = L.elem[i - 1];
    // 将顺序表中位置 i 处的元素赋值给参数 e。

    for (j = i; j < L.length; j++) {
        L.elem[j - 1] = L.elem[j];
    }
    // 从位置 i 开始，将后面的元素依次向前移动一位。

    --L.length;
    // 顺序表的长度减一，表示删除了一个元素。

    return 1;
    // 返回一个表示成功的状态码（这里是 1）。
}

时间复杂度：

-最好情况：T(n)=O(1);

-最坏情况：T(n)=O(n);

-平均情况：T(n)=O(n).

7.按位查找操作 GetElem(L,i):

操作结果：获取表L中的第i个位置元素的值。

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

时间复杂度：O（1）

8.按值查找操作 LocateElem(L,e):

操作结果：在表L中查找具有给定关键字值的元素（第一个）。

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L,ElemType e)
{
    for(int i=0;i<=L.length-1;i++){
        if(L.data[i]==e){
            return i+1;
        }
    }
    return 0;
}