【数据结构】第二章线性表-摩杜云开发者社区

重难点：顺序表和链表。

线性表的分类

【数据结构】第二章线性表_链表

逻辑机构在存储结构中的实现：

【数据结构】第二章线性表_链表_02

2.1 线性表的定义

定义： 线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长。

每个元素所占用的空间一样大
有次序，且有限

Eg: 所有整数按递增次序排列是线性表吗？答：不是，因为不是有限。

线性表的特点：在数据元素的非空有限集合中，除第一个元素无直接前驱、最后一个元素无直接后继外，集合中其余每个数据元素均有唯一的直接前驱和唯一的直接后继。

存储：连续地址。是随机存储结构。

线性表的基本术语

起始结点
终端结点
直接前驱
直接后继
线性表长度
空表

2.2 线性表的基本运算（在逻辑结构上实现）

线性表的基本运算

【数据结构】第二章线性表_链表_03

2.3 线性表的顺序存储表示和实现-顺序表

顺序表存放数据的特点和数组这种数据类型完全吻合，因此顺序表的实现使用的是数组。需要注意的是，使用数组实现顺序表时，一定要预先申请足够大的内存空间，避免因存储空间不足，造成数据溢出，导致不必要的程序错误甚至崩溃。

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表：可动态增长的数组，要求数据是连续存储的

2.3.1 基本概念

线性表在内存中按照顺序存储的形式村存储的示意图：

【数据结构】第二章线性表_List_04

顺序存储的顺序表的在创建的时候需要指定长度；长度必须要大于等于要存储的数据的长度。

顺序表的顺序存储结构：

数组下标	0	1	2	3	4	5	6
值域	'H'	'e'	'l'	'l'	'o'	' '	'W'
序号	a1	a2	a3	a4	a5	a6	a7

注意:序号从1开始，数组下标从0开始。

静态顺序表 VS. 动态顺序表

【数据结构】第二章线性表_顺序表_05

2.3.2 算法实现（静态顺序表[定长数组]-用的少）

静态顺序表：使用静态数组来存储元素，数组的大小在创建时确定，不可改变。这意味着静态顺序表在使用前需要预先分配足够的内存空间。

缺陷：给小了不够用，给大了可能浪费，非常不实用
静态顺序表一旦分配了固定大小的内存空间，其容量是固定的。如果元素数量超过了预分配的容量，就需要进行扩容操作，并可能导致内存浪费或数据迁移。同样地，如果删除了元素，也不能动态减小内存空间。因此，静态顺序表对于元素数量的变化较难适应。

顺序表的结构体定义（静态顺序表）

// 根据学生档案信息，给出顺序表具体的类型定义
//const int Maxsize = 7; // 预先定义数组大小;注意这里是 //这里是错误用户，因为结构体中定义了数组，数组的[]内不允许使用变量的；因此这里需要使用
#define Maxsize 7
typedef struct {
    int num; // 学号
    char name[8]; // 姓名
    char sex[2]; // 性别
    int age; // 年龄
    int score; // 入学成绩
} DataType; // 定义结点的类型※※※※

typedef struct {
    DataType data[Maxsize]; // 存放数据的数组;Maxsize不能是变量；因此需要使用define定义 | [静态]定长数组
    int length; // 线性表的实际长度
} SeqList; // 定义顺序表的类型※※※※
SeqList student; // student 为顺序表的名称

根据上述定义，该顺序表的名称为 student，表的最大长度为 7，表的实际长度值在 student.length中。

常用算法清单：

1、创建：申请空间 2、初始化：顺序表数据结构大小、长度 3、赋值：顺序表数据结构赋值 4、插入：在指定位置插入数据，后续数据循环后移，长度增加，空间大小增加或者不变 5、删除：删除指定位置的数据，后续数据循环前移，长度减小、空间大小不变 6、查询：查看指定数据是否在顺序表结构中 7、替换：将顺序表结构中指定数值替换为另外的数值 8、输出：输出顺序表结构中存储的数据（根据长度大小输出）

初始化顺序表和创建顺序表是两个不同的概念。

初始化顺序表：初始化顺序表是指在使用顺序表之前，对顺序表进行一些初始化操作，例如分配内存空间、设置顺序表的初始容量等。初始化顺序表的目的是为了为顺序表的后续操作做准备。
创建顺序表：创建顺序表是指根据实际需求，将数据元素逐个添加到顺序表中，创建一个包含特定数据元素的顺序表。创建顺序表的过程是根据需求不断向顺序表中插入元素，直到顺序表达到期望的状态。

总结起来，初始化顺序表是对顺序表进行一些预备操作，而创建顺序表则是根据需求逐个添加元素到顺序表中。在数据结构中，初始化顺序表应该在创建顺序表之前进行。

初始化顺序表是指对顺序表进行一些必要的初始化操作，例如给顺序表的指针分配内存空间、设置初始容量等。这些操作需要在创建顺序表之前进行，以确保顺序表的正常运行。

初始化顺序表

创建顺序表

算法代码示例：

#include <stdio.h>
#define Maxsize 10

typedef struct{
    int data[Maxsize];  //顺序表存放数据的位置，这里定义的类型是整型
    int Length;         //顺序表的实际长度【元素的个数】
}SeqList;

void initSeqList(SeqList* list){  //SeqList初始化
    list->Length = 0;
}

void createSeqList(SeqList* list, int elements[], int n){ //创建SeqList需要传入目标顺序表的指针，存放的元素数据，元素个数
    for(int i=0; i < n; i++){
        list->data[i] = elements[i];   //逐个将数据存入顺序表中
    }
    list->Length = n;     //将顺序表的实际长度设置为存入的元素个数。
}

int main(){
    SeqList A;
    int B[] = {1,2,3,10,20};
    printf("%d \n", sizeof(B));
    printf("%d \n", sizeof(B[0]));
    int count = sizeof(B) / sizeof(B[0]);  //求元素个数;sizeof return bytes.

    //initSeqList(&B);
    createSeqList(&A, B, count);
    for(int i=0; i < A.Length; i++){
        printf("%d ",A.data[i]);
    }
    return 0;
}

增加(插入)

1）插入方法：

头插
尾插
任意位置插入

【数据结构】第二章线性表_链表_06

算法如下：

#include <stdio.h>

const int Maxsize = 10;
typedef struct{  //自定义节点类型
    int x;       //节点中存放一个整型的数据
}DataType;       //为定义的节点类型结构体取个别名

typedef struct{   //自定义顺序表类型
    DataType data[Maxsize];     //存放数据的数组，最大长度是前面定义的10
    int length;   //线性表的实际长度
} SeqList;        //为定义的顺序表结构体取个别名

void InsertSeqList(SeqList L, DataType d, int n){   //L:顺序表； d：节点数据， 插入位置。
    if(L.length = Maxsize){ printf("SeqList is full!"); exit(1); }    //判断表满
    if((n < 1) || (n > (L.length + 1))){ printf("Position error!"); exit(2);  }    //位置判断
    for(int i = L.length; i>=n; i--){
        L.data[i] = L.data[i-1];    //从表尾元素依此后移，直到插入要插入的位置
    }
    L.data[n-1] = d;     //将节点数据插入到第个位置，下标为n-1.
    L.length++;    //插入成功要记得将顺序表的实际长度+1.
}

此算法支持头插、尾插和中间任意位置插入。

以在位置1处插入10为例图示：

【数据结构】第二章线性表_数据_07

2）算法分析

假设线性表含有n个元素；在执行插入时有n+1个位置可供插入；因此，在任意一个位置插入的概率是1/(n+1)。

在第i个位置上插入数据时，需要移动n-i+1次；平均插入一个数据需要移动元素的次数为：

【数据结构】第二章 线性表_链表_08

因此，算法的平均时间复杂度是：O(n)。

删除

线性表的删除运算是指将表的第i个结点删去；使得顺序表的实际长度减少。

1）删除方法

判断位置是否越界
删除节点数据（直接覆盖也ok的）
依此将被删除节点的后续从左到右依此向左移动一次

【数据结构】第二章线性表_数据_09

算法代码：

#include <stdio.h>

const int Maxsize = 10;
typedef struct{  //自定义节点类型
    int x;       //节点中存放一个整型的数据
}DataType;       //为定义的节点类型结构体取个别名

typedef struct{   //自定义顺序表类型
    DataType data[Maxsize];     //存放数据的数组，最大长度是前面定义的10
    int length;   //线性表的实际长度
} SeqList;        //为定义的顺序表结构体取个别名

void DeleteSeqList(SeqList L, int n){
    if(n<1 || n > L.length){ printf("Position error!"); exit(1); }
    for(int i=n; i<=L.length;i++){    //从第n个位置开始遍历到顺序表实际长度的位置
        L.data[n-1] = L.data[n];      //第n个位置的下标是n-1;将它的值使用其后的元素覆盖掉
    }
    L.length--;                       //昨晚所有操作后记得将顺序表的实际长度-1.
}

2）算法复杂度分析

平均时间复杂度是O(n)。

查找(定位)

1）已知位置查值

list[i]

2）已知值查位置

int value = x;
int location = 0
for(inti=0; i<list.length; i++){
    if(list[i].data == value){
        location = i + 1;
        return location;
    }
}
return location;  //若没有匹配的则location始终=0；否则返回匹配到的元素的位置

修改/替换

list[i] = x

销毁

//方法1：
//静态顺序表的销毁算法并不涉及手动释放内存，因为静态顺序表的内存是由编译器自动管理的。我们只需要将顺序表的指针置为NULL，表示顺序表已被销毁即可。
void destroyList(SeqList* list) {
    list = NULL;
}

//方法2：
//将顺序表的长度length设置为0，表示顺序表中没有有效的元素。我们还可以选择将数组元素置为0，以及将数组指针data置为NULL，这些操作是可选的，用于避免数据泄漏。
void destroyList(SeqList* list) {
    list->length = 0;
    // 可选操作，将数组元素置为0
    for (int i = 0; i < MAX_SIZE; i++) {
        list->data[i] = 0;
    }
    // 可选操作，将数组指针置为NULL
    // list->data = NULL;
}

2.3.3 算法实现（动态顺序表[动态数组]-用的多）

动态顺序表：静态顺序表使用静态数组来存储元素，数组的大小在创建时确定，不可改变。这意味着静态顺序表在使用前需要预先分配足够的内存空间。

动态顺序表可根据我们的需要分配空间大小
size 表示当前顺序表中已存放的数据个数
capacity 表示顺序表总共能够存放的数据个数
动态顺序表的内存空间可以根据需要动态调整，可以自动扩容或缩减内存。它可以有效地利用内存空间，并能够适应元素数量的变化。

需要注意：

动态顺序表分配的内存仍然是连续的。尽管动态顺序表的大小可以在运行时动态调整，但它仍然通过连续的内存块来存储数据元素。

当使用动态内存分配函数（如malloc()、realloc()等）在堆上分配内存时，这些函数会尽可能地为顺序表分配连续的内存块。这意味着顺序表的数据元素在内存中是依次存储的，相邻元素的地址是连续的。

通过连续的内存存储，动态顺序表可以通过索引来快速访问和操作元素，具有较高的访问效率。此外，动态顺序表还可以利用指针算术运算（如*(ptr + i)）来随机访问元素，而不需要进行额外的计算。

需要注意的是，尽管动态顺序表的内存是连续的，但由于动态分配的内存块可能不连续，因此在进行动态调整大小时可能会涉及到内存的重新分配和数据的拷贝。这是由动态内存管理函数自动完成的，对于程序员而言是透明的。

顺序表的结构体定义（动态顺序表）

#include <stdio.h>

typedef int DataType;    //给int数据类型取个别名；方便统一修改;方便修改为其他类型2。
typedef struct{
    DataType* data;      //存放数据的指针，指向数据存放的第1个内存地址。地址空间是动态开辟。
    int size;            //实际存储的数据元素数量。
    int capacity;        //顺序表的容量（实际可以存多少个数据元素；可根据算法动态调整）。
}DSeqList;

初始化顺序表

DSeqList InitSeqList(DSeqList* L){    //初始化
    L->data = NULL;                   //数据置为NULL
    L->length = 0;                    //实际表长置为0
    L->size = 0;                      //表的最大容量置为0
}

创建顺序表

根据给出的数据将数据按照设计好的顺序逐个插入（可自由选择头插或尾插）顺序表。因此这里我们就不给出实际的算法代码了。

求表长

List.length

检查表满（满则扩容；也可以满不扩容同时禁止插入；完全根据算法定义）

#include <stdio.h>

typedef int DataType;    //给int数据类型取个别名；方便统一修改;方便修改为其他类型2。
typedef struct{
    DataType* data;      //存放数据的指针，指向数据存放的第1个内存地址。地址空间是动态开辟。
    int size;            //实际存储的数据元素数量。
    int capacity;        //顺序表的容量（实际可以存多少个数据元素；可根据算法动态调整）。
}DSeqList;

void CheckFull(DSeqList* L){    //逐个示例只是简单实现判满扩容；实际环境中还要考虑空指针、内存泄漏等问题（我们这里先不考虑）
    if(L->length == L->size){  //判表满
        printf("is full.");
        //若表满；则判断表的容量是不是0，如果是0则将表的容量置为4，否则将表的容量置为当前容量的2倍(根据自己的实际情况调整)
        int newsize = ( (L->size == 0)?4:(2*L->size) );
        DataType* tmp = NULL;      //定义一个临时变量(类型是顺表的data域的数据类型)并置为NULL
        tmp = (DataType*)realloc(L->data, newsize*sizeof(DataType));  //原表数据赋给新分配的存储空间
        if(tmp == NULL){   //若tmp还是NULL，则扩容失败并退出
            printf("resize error!");
            exit(-1);
        }
        L->data = tmp;     //将tmp的指向赋给L->data
        L->size = newsize; //修改L的容量值
    }else{
        printf("not full!");
    }
}

插入数据-头插

//插入-头插
void SeqListPushFront(DSeqList* L, DataType x){
    CheckFull(L);     //插入先判满
    for(int end = L->size - 1; end >= 0; end--){ //从尾部逐个将元素向后挪一位
        L->data[end+1] = L->data[end];
    }
    L->data[0] = x;  //将要插入的数据赋给表的第一个元素
    L->length++;       //实际表长+1
}

插入数据-尾插

//插入-尾插
void SeqListPushEnd(DSeqList* L, DataType x){
    CheckFull(L);   //检查是否已满
    L->data[L->length] = x;  //数据存入表尾元素
    L->length++;             //顺序表的实际长度+1
}

插入数据-指定下标

//插入-任意位置
void SeqListInsert(DSeqList* L, int pos, DataType x){
    if(pos < 0 || pos >= L->length+1){ exit(1);}
    CheckFull(L);
    for(int end = L->length - 1; end >= pos; end--){  //从尾部逐个将元素向后挪一位
        L->data[end + 1] = L->data[end];
    }
    L->data[pos] = x;
    L->length++;
}

删除数据-头删

//删除-头删
void SeqListPopFront(DSeqList* L){
    if(L->length <= 0){    //表中有数据才能删
        exit(1);
    }
    for(int start=0; start < L->length; start++){ //从头部逐个将元素向前挪一位
        L->data[start] == L->data[start+1];
    }
    L->length--;
}

删除数据-尾删

//删除-尾删
void SeqListPopEnd(DSeqList* L){
    if(L->length > 0){   //表中有数据才能删
        L->length--;     //直接表长减一即可；若考虑安全性也可提前将数据置为NULL
    }
}

删除数据-指定下标

//删除-任意位置
void SeqListDelete(DSeqList* L, int pos){
    if(pos < 0 || pos >= L->length ){ exit(1); }  //位置不当；包含了length=0的情况
    for(int start = pos; start < L->length; start++){ //从指定位置逐个将元素向前挪一位
        L->data[start] = L->data[start+1]; 
    }
    L->length--;
}

查找-按值

int SeqListFind(const DSeqList* L, DataType x)
{
    int i = 0;
    for (i = 0; i < L->length; i++)
    {
        if (L->data[i] == x)
        {
            return i+1;  //查找到，返回该值在数组中的位置(下标+1)
        }
    }
    return -1;  //没有查找到
}

查找-按下标

List.data[i]

更新/替换-按下标

List.data[i] = x

销毁(释放)顺序表

//销毁、释放
void SeqListDestory(DSeqList* L){
    free(L->data);    //释放动态开辟的空间
    L->data = NULL;
    L->size = 0;
    L->length = 0;
}

整体算法代码

#include <stdio.h>

typedef int DataType;    //给int数据类型取个别名；方便统一修改。
typedef struct{
    DataType* data;      //存放数据的指针，指向数据存放的第1个内存地址。地址空间是动态开辟。
    int length;            //实际存储的数据元素数量。
    int size;        //顺序表的容量（实际可以存多少个数据元素；可根据算法动态调整）。
}DSeqList;

//初始化
void InitSeqList(DSeqList* L){    //初始化
    L->data = NULL;                   //数据置为NULL
    L->length = 0;                    //实际表长置为0
    L->size = 0;                      //表的最大容量置为0
}

//判满+扩容
void CheckFull(DSeqList* L){    //逐个示例只是简单实现判满扩容；实际环境中还要考虑空指针、内存泄漏等问题（我们这里先不考虑）
    if(L->length == L->size){  //判表满
        printf("is full.");
        //若表满；则判断表的容量是不是0，如果是0则将表的容量置为4，否则将表的容量置为当前容量的2倍(根据自己的实际情况调整)
        int newsize = ( (L->size == 0)?4:(2*L->size) );
        DataType* tmp = NULL;      //定义一个临时变量(类型是顺表的data域的数据类型)并置为NULL
        tmp = (DataType*)realloc(L->data, newsize*sizeof(DataType));  //原表数据赋给新分配的存储空间
        if(tmp == NULL){   //若tmp还是NULL，则扩容失败并退出
            printf("resize error!");
            exit(-1);
        }
        L->data = tmp;     //将tmp的指向赋给L->data
        L->size = newsize; //修改L的容量值
    }else{
        printf("not full!");
    }
}

//查找-按值
int SeqListFind(const DSeqList* L, DataType x)
{
    int i = 0;
    for (i = 0; i < L->length; i++)
    {
        if (L->data[i] == x)
        {
            return i+1;  //查找到，返回该值在数组中的位置(下标+1)
        }
    }
    return -1;  //没有查找到
}

//插入-尾插
void SeqListPushEnd(DSeqList* L, DataType x){
    CheckFull(L);   //检查是否已满
    L->data[L->length] = x;  //数据存入表尾元素
    L->length++;             //顺序表的实际长度+1
}

//删除-尾删
void SeqListPopEnd(DSeqList* L){
    if(L->length > 0){   //表中有数据才能删
        L->length--;     //直接表长减一即可；若考虑安全性也可提前将数据置为NULL
    }
}

//插入-头插
void SeqListPushFront(DSeqList* L, DataType x){
    CheckFull(L);     //插入先判满
    for(int end = L->size - 1; end >= 0; end--){ //从尾部逐个将元素向后挪一位
        L->data[end+1] = L->data[end];
    }
    L->data[0] = x;  //将要插入的数据赋给表的第一个元素
    L->length++;       //实际表长+1
}

//删除-头删
void SeqListPopFront(DSeqList* L){
    if(L->length <= 0){    //表中有数据才能删
        exit(1);
    }
    for(int start=0; start < L->length; start++){ //从头部逐个将元素向前挪一位
        L->data[start] == L->data[start+1];
    }
    L->length--;
}

//插入-任意位置
void SeqListInsert(DSeqList* L, int pos, DataType x){
    if(pos < 0 || pos >= L->length+1){ exit(1);}
    CheckFull(L);
    for(int end = L->length - 1; end >= pos; end--){  //从尾部逐个将元素向后挪一位
        L->data[end + 1] = L->data[end];
    }
    L->data[pos] = x;
    L->length++;
}

//删除-任意位置
void SeqListDelete(DSeqList* L, int pos){
    if(pos < 0 || pos >= L->length ){ exit(1); }  //位置不当；包含了length=0的情况
    for(int start = pos; start < L->length; start++){ //从指定位置逐个将元素向前挪一位
        L->data[start] = L->data[start+1]; 
    }
    L->length--;
}

//销毁、释放
void SeqListDestory(DSeqList* L){
    free(L->data);    //释放动态开辟的空间
    L->data = NULL;
    L->size = 0;
    L->length = 0;
}

2.3.4 时间复杂度分析

中间/头部的插入删除，时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
增容一般是呈2倍的增长，势必会有一定的空间浪费，不能完全实现按需所取。

【数据结构】第二章线性表_顺序表_10

顺序表还是比较好理解的，当然也有一下不足之处；比如需要分配连续的存储空间，受表的容量限制，即使动态地扩容，但是不够灵活，且在数据量较大时扩容需要复制的数据也随之增大，从而消耗系统的开销。

2.4 线性表的链式存储表示和实现-链表

2.4.1 基本概念

链表的具体存储表示为： ①用一组任意的存储单元来存放。 ②链表中结点的逻辑次序和物理次序不一定相同。还必须存储指示其后继结点的地址信息。

链表的构成：

【数据结构】第二章线性表_顺序表_11

因此；虽然链表在存储上不依赖连续的存储空间但是逻辑上链表的结点间还是前后有序的。

2.4.2 单链表

定义: 单链表是指用链式存储的方式实现线性表。

单链表的特点：

不要求大片的连续空间，改变容量方便。
不可随机存取
需要耗费空间来存储指针

初始化单链表： 可以分为带头结点的单链表和不带头结点的单链表

单链表的构成：

【数据结构】第二章线性表_链表_12

单链表中第一个结点内一般不存数据，称为头结点，利用头指针存放该结点地址。

为什么要加设头结点？增加头结点的目的是：方便运算的实现。。

2.4.2.1 单链表的类型定义

typedef int DataType;
typedef struct {
    DataType data;
    struct Node* next;
    
} Node, *LinkList;


//或者
typedef int DataType;
typedef struct node{
    DataType data;
    struct node* next;
    
} Node, *LinkList;

2.4.2.2 单链表上的算法（以带头结点的单链表为例）

初始化

//初始化
LinkList InitiateLinkList(){
    LinkList P;  //头指针
    P = malloc(sizeof(Node));  //动态申请一个结点大小的内存空间。
    P->next = NULL;   //初始化后为空链表;data域时值是随机的无意义。
    return P;
}

返回值类型：Linklist的地址

求表长

步骤： 1、令计数器 j 为 0 2、令 pos 指向头结点 3、当下一个结点非空时，j 加 1，pos 指向下一个结点 4、j 的值即为链表中结点个数，即表长度

返回值类型：int

//求表长
int LengthLinkList(LinkList L){
    Node* pos;
    int j = 0;
    pos = L;
    while(pos->next != NULL){
        pos = pos->next;
        j++;
    }
    return j;
}

查找-按位置

步骤：查找第 i 个结点 1、令计数器 j 为 0 2、令 pos 指向头结点 3、当下一个结点非空时，并且 j < i 时，j + 1，pos 指向下一个结点 4、如果 j 等于 i，则 pos 所指结点为要找的第 i 结点。否则，链表中无第 i 结点。

返回值类型：Node

//查找-按位置
Node* GetNode(LinkList L, int n){
    Node* pos;
    int j = 0;
    pos = L->next;
    while(j < n && pos->next != NULL){
        pos = pos->next;
        j++;
    }
    if(n == j){ return pos; }else{ return NULL; }
}

查找-按值

具体步骤： 1、令 pos 指向头结点 2、令 i = 1； 3、当下一个结点不空时，pos 指向下一个结点，同时 i 的值加1 4、直到 pos 指向的结点的值为 x，返回 i 的值。 5、如果找不到结点值为 x 的话，返回值为 0.

返回值类型：int

//查找-按值
int GetLocation(LinkList L, DataType x){
    Node* pos;
    pos = pos->next;
    int j = 1;
    while(pos != NULL && pos->data != x){
        pos = pos->next;
        j++;
    }
    if(pos != NULL){ return j; }else{ return 0;}
}

插入结点

插入运算是将值为 x 的新结点插入到表的第 i 个结点的位置上，即插入到 ai-1 与 ai 之间。具体步骤： 1、找到 ai-1 存储位置q 2、生成一个数据域为 x 的新结点 *p(开辟新的存储空间) 3、令结点 *p 的指针域指向 *q 的后继结点 4、新结点的指针域指向结点ai。

//插入
void InsertLinkList(LinkList L, DataType x, int n){
    Node *p, *q;
    q = GetNode(L, n);
    if(q == NULL){ 
        if(n == 1 ){q = L;}else{ printf("插入位置错误！\n"); }
    }
    
    if(q != NULL ){
        p = malloc(sizeof(Node));
        p->data = x;
        p->next = q->next;
        q->next = p;
    }
}

删除结点

1、找到ai - 1（待删结点的直接前驱）的存储位置q 2、令 q -> next指向 ai 的直接后继结点 3、释放结点 ai 的空间，将其归还给“存储池”。

//删除
void DeleteNode(LinkList L, int n){
    Node *p, *q;
    q = GetNode(L, n-1);
    if(q == NULL){ 
        printf("未找到要删除的结点！\n"); 
    }else{
        p = q->next;
        q->next = p->next;
        free(p);
    }
}

销毁/释放表

在destroyLinkedList函数中，使用了一个指针p来遍历链表，每次释放当前结点的内存后，将指针p指向下一个结点，直到链表结束。

// 释放单链表内存空间
void destroyLinkedList(LinkList L) {
    Node* pos = L;
    while (pos != NULL) {
        Node* temp = pos;
        pos = pos->next;
        free(temp);   //必不可少的，因为当一个结点从链表移出后，如果不释放它的空间，它将变成一个无用的结点，它会一直占用着系统内存空间，其他程序将无法使用这块空间。
    }
}

全部算法代码

#include <stdio.h>

/*
typedef int DataType;
typedef struct {
    DataType data;
    struct Node* next;
    
} Node, *LinkList; 
*/

typedef int DataType;
typedef struct{
    DataType data;
    struct Node* next;
    
} Node;
typedef Node *LinkList;

//初始化
LinkList InitiateLinkList(){
    LinkList P;  //头指针
    P = malloc(sizeof(Node));  //动态申请一个结点大小的内存空间。
    P->next = NULL;   //初始化后为空链表;data域时值是随机的无意义。
    return P;
}

//求表长
int LengthLinkList(LinkList L){
    Node* pos;
    int j = 0;
    pos = L;
    while(pos->next != NULL){
        pos = pos->next;
        j++;
    }
    return j;
}

//查找-按位置
Node* GetNode(LinkList L, int n){
    Node* pos;
    int j = 0;
    pos = L->next;
    while(j < n && pos->next != NULL){
        pos = pos->next;
        j++;
    }
    if(n == j){ return pos; }else{ return NULL; }
}

//查找-按值
int GetLocation(LinkList L, DataType x){
    Node* pos;
    pos = pos->next;
    int j = 1;
    while(pos != NULL && pos->data != x){
        pos = pos->next;
        j++;
    }
    if(pos != NULL){ return j; }else{ return 0;}
}


//插入
void InsertLinkList(LinkList L, DataType x, int n){
    Node *p, *q;
    q = GetNode(L, n);
    if(q == NULL){ 
        if(n == 1 ){q = L;}else{ printf("插入位置错误！\n"); }
    }
    
    if(q != NULL ){
        p = malloc(sizeof(Node));
        p->data = x;
        p->next = q->next;
        q->next = p;
    }
}

//删除
void DeleteNode(LinkList L, int n){
    Node *p, *q;
    q = GetNode(L, n-1);
    if(q == NULL){ 
        printf("未找到要删除的结点！\n"); 
    }else{
        p = q->next;
        q->next = p->next;
        free(p);
    }
}


// 释放单链表内存空间
void destroyLinkedList(LinkList L) {
    Node* pos = L;
    while (pos != NULL) {
        Node* temp = pos;
        pos = pos->next;
        free(temp);   //必不可少的，因为当一个结点从链表移出后，如果不释放它的空间，它将变成一个无用的结点，它会一直占用着系统内存空间，其他程序将无法使用这块空间。
    }
}

其他常用算法

创建单链表

1.初始化一个空链表InitiateLinkList()

2.依此将数据插入到表中InsertLinkList()；这里有很多选择，插入位置n可以设设置为1（头插）；可以设置n=表长（尾插）。当然也可以结合辅助变量实现更优的插入方法。

删除重复结点

1.从首结点（head->next）开始，逐个后续的所有结点（while( pos != NULL )）和当前结点进行比较；若后续的结点和当前节点的data相同则删除（DeleteNode()）。

2.4.3 循环链表-单循环链表

单循环链表也经常被叫做：循环链表

单循环链表结点的结构和单链表一样。

循环链表的结构

【数据结构】第二章线性表_算法_13

常考算法

1）插入

【数据结构】第二章线性表_数据_14

2）删除

【数据结构】第二章线性表_链表_15

2.4.4 循环链表-双向循环链表

双向循环链表适合应用在需要经常查找结点的前驱和后继的场合。

其查找前驱和后继的复杂度均为：O(1)。

双向循环链表结点的结构和单链表不一样。

双向循环链表的结构

【数据结构】第二章线性表_算法_16

常考算法

1）插入

更多指针要调整，一定要注意顺序。

【数据结构】第二章线性表_链表_17

2）删除

【数据结构】第二章线性表_List_18

2.5 顺序实现与链式实现的比较

1. 线性表与链表的优缺点

1、单链表的每个结点包括数据域与指针域，指针域需要占用额外空间。 2、从整体考虑，顺序表要预分配存储空间，如果预先分配得过大，将造成浪费，若分配得过小，又将发生上溢；单链表不需要预先分配空间，只要内存空间没有耗尽，单链表中的结点个数就没有限制。

2. 时间性能的比较

顺序表：

操作	时间性能
读表元素	O(1)
定位-按值（找x）	O(n)
插入	O(n)
删除	O(n)

链表：

操作	时间性能
读表元	O(n)
定位-按值（找x）	O(n)
插入	O(n)
删除	O(n)

【数据结构】第二章线性表_算法_19

水平有限，难免有误，欢迎大家斧正~

喜欢本文的朋友请三连哦！！！

另外本文也参考了网络上其他优秀博主的观点和实例，这里虽不能一一列举但内心属实感谢无私分享知识的每一位你们。