线性表

线性表定义：由n(n>=0)个相同类型的元素组成的有序集合。

L=(a~1~，a~2~，...，a~i-1~，a~i~，a~i+1~，a~n~)

线性表中的元素个数n，称为线性表的长度。当n=0时，线性表为空表。

a~1~是唯一的"第一个"数据元素，a~n~是唯一的"最后一个"数据元素。

a~i-1~为a~i~的直接前驱，a~i+1~为a~i~的直接后继。

线性表的特别

1、表中元素的个数是有限的。

2、表中元素的数据类型都相同。意味着每一个元素占用相同大小的空间。

3、表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序。

注：本节描述的是线性表的逻辑结构，是独立于存储结构的。

线性表的顺序表示(顺序表)

逻辑上相邻的两个元素在物理位置上也相邻

#define MaxSize 50 //定义线性表的长度
typedef int Elemtype;
typedef struct{
    Elemtype data[MaxSize];  //存放顺序表的元素
    int len; //存放顺序表当前的长度
}SqList; //顺序表的类型定义

顺序表的优缺点：

优点：

1、可以随机存储(根据表头元素地址和元素序号)表中任意一个元素。

2、存储密度高，每个节点只存储数据元素。

缺点：

1、插入和删除操作需要移动大量元素。

2、线性表变化较大时，难以确定存储空间的容量。

3、存储分配需要一整段连续的存储空间，不够灵活。

顺序表插入操作的时间复杂度

最好情况：在表尾插入元素，不需要移动元素，时间复杂度为O(1)

最坏情况：在表头插入元素，所有元素依次后移，时间复杂度为O(n)

/*
插入操作需要判断两个条件
1、插入位置i是否合法(满足1<=i<=len+1)
2、存储空间是否已满(插入x后是否会超出数组长度)
 */
for(int j=L.len;j>=i;j--){
    L.data[j]=L.data[j-1];
}
L.data[i-1]=x;  //线性表第一个元素的数组下标是0
L.len++;

顺序表删除操作的时间复杂度

最好情况：删除表尾元素，不需要移动元素，时间复杂度为O(1)

最坏情况：删除表头元素，所有元素依次前移，时间复杂度为O(n)

/*
删除操作需要判断一个条件
1、删除位置i是否合法(满足1<=i<=len)，插入和删除时，i的合法范围不同
 */
e=L.data[i-1]; //获取当前删除元素的值
for(int j=i;j<L.len;j++)
{
    L.data[j-1]=L.data[j];
}
L.len--;

动态分配数组

动态分配的数组仍然属于顺序存储结构。顺序存储结构是一种通过一段连续的内存空间来存储数据的方式。无论是静态分配的数组（在编译时就确定了大小）还是动态分配的数组（在运行时根据需要动态调整大小），它们都在内存中以连续的地址块进行存储。

#define InitSite 100 //表长度的初始定义
typedef int ElemType;
typedef struct {
    ElemType *data;
    int MaxSize,length;
}SeqList;

C的初始动态分配语句

L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);

C++的初始动态分配语句

L.data=new ElemType[InitSite]

顺序表的初始化及插入操作实战

#include <stdio.h>

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

//动态分配
#define InitSize 100
typedef struct {
    ElemType *data;
    int capacity; //动态数组的最大容量
    int length;
}SeqList;

//线性表插入
bool ListInsert(SqList &L,int i,ElemType e)
{
    if(i<1 || i>L.length+1) //判断插入的位置是否合法
    {
        return false;
    }
    if(L.length>=MaxSize)
    {
        return false;
    }
    int j;
    for(j=L.length; j >= i; j--)
    {
        L.data[j]=L.data[j-1];
    }
    L.data[i-1]=e; //数组下标从0开始，插入第一个位置，访问的下标为0
    L.length++;
    return true;
}

//打印顺序表元素
void PrintList(SqList L)
{
    for(int i=0;i<L.length;i++)
    {
        printf("%3d",L.data[i]);
    }
}

int main()
{
    SqList L; //顺序表的名称
    bool ret; //查看返回值，布尔型是True或者False
    ElemType ins; //要插入的元素
    //手动在顺序表内赋值
    L.data[0]=1;
    L.data[1]=2;
    L.data[2]=3;
    L.length=3;
    ret= ListInsert(L,3,82);
    if(ret)
    {
        printf("insert sucesses\n");
        PrintList(L);
    }else
    {
        printf("insert failed\n");
    }
    return 0;
}

顺序表的删除及查询实战

在上面实验的基础上，增加子函数

#include <stdio.h>

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

//动态分配
#define InitSize 100
typedef struct {
    ElemType *data;
    int capacity; //动态数组的最大容量
    int length;
}SeqList;

//线性表插入
bool ListInsert(SqList &L,int i,ElemType e)
{
    if(i<1 || i>L.length+1) //判断插入的位置是否合法
    {
        return false;
    }
    if(L.length>=MaxSize)
    {
        return false;
    }
    int j;
    for(j=L.length; j >= i; j--)
    {
        L.data[j]=L.data[j-1];
    }
    L.data[i-1]=e; //数组下标从0开始，插入第一个位置，访问的下标为0
    L.length++;
    return true;
}

//顺序表删除，并将删除的元素进行展示
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;
}

//查找元素操作，并返回元素所在的位置，位置从1开始，查找失败返回0
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i<L.length; i++) {
        if (L.data[i] == e) {
            return i+1; // 返回元素位置（位置从1开始）
        }
    }
    return 0; // 元素未找到
}

//打印顺序表元素
void PrintList(SqList L)
{
    for(int i=0;i<L.length;i++)
    {
        printf("%3d",L.data[i]);
    }
    printf("\n");
}

int main()
{
    SqList L; //顺序表的名称
    int ret; //查看返回值，布尔型是True或者False
    ElemType ins; //要插入的元素
    ElemType del; //要删除的元素
    //手动在顺序表内赋值
    L.data[0]=1;
    L.data[1]=2;
    L.data[2]=3;
    L.length=3;
    ret= ListInsert(L,3,82);
    if(ret)
    {
        printf("insert sucesses\n");
        PrintList(L);
    }else
    {
        printf("insert failed\n");
    }
    ret= ListDelete(L,2,del);
    if(ret)
    {
        printf("delete success\n");
        printf("delete element is %d\n",del);
        PrintList(L);
    }else
    {
        printf("delete failed\n");
    }
    ret=LocateElem(L,82);
    if(ret)
    {
        printf("find success\n");
        printf("element locate in %d\n",ret);
    }else
    {
        printf("find failed");
    }
    return 0;
}

线性表的链式表示(链表)

顺序表有一定的缺点，如插入和删除操作需要移动大量元素，数组的大小不好确定或者是占用一大段连续的存储空间，造成很多碎片。

在C语言中，链表（Linked List）是一种常见的数据结构，用于存储数据元素的集合。链表中的每个元素被称为节点（Node），每个节点包含两部分：数据（可以是任意类型的数据）和指向下一个节点的指针。

链表中的节点通过指针链接在一起，形成一个链式结构。最简单的链表是单链表，每个节点包含一个数据元素和一个指向下一个节点的指针。另外还有双向链表和循环链表等更复杂的链表结构。

以下是单链表的基本结构：

typedef struct LNode { //单链表节点类型
    int data; // 数据域
    struct Node* next; // 指向下一个节点的指针
}LNode,*LinkList;

单链表中的节点结构包含了一个整型数据元素和一个指向下一个节点的指针。链表的头部指针指向链表的第一个节点，而链表的尾部指针通常指向NULL，表示链表的末尾。

链表的优点之一是它的灵活性，因为它可以动态地分配内存，不需要事先知道要存储的数据的数量。但是它的缺点是访问节点的效率比较低，因为需要从头节点开始逐个遍历链表。

头指针：链表中第一个结点的存储位置，用来标识单链表。

头结点：在单链表第一个节点之前附加的一个节点，为了操作上的方便。有了头结点，我们在对链表进行操作时就可以统一处理边界情况，比如插入第一个节点、删除第一个节点等操作。而不需要特殊处理链表为空或者链表只有一个节点的情况。

若链表有头结点，则头指针永远指向头结点，不论链表是否为空，头指针均不为空，头指针是链表的必须元素，用于标识一个链表，

链表的优缺点

优点：

1、插入和删除操作不需要移动元素，只需要修改指针。

2、不需要大量的连续存储空间。

缺点：

1、单链表附加指针域，也存在浪费存储空间的缺点。

2、查找操作时需要从表头开始遍历，依次查找，不能随机存取。