线性表的定义

线性表(linear_list)是最常用且最简单的一种数据结构。简言之，一个线性表是 $n$ 个数据元素的有限序列。

线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。

线性表的抽象数据类型定义如下:

ADT List{ 
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 
数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
基本操作： 
InitList(&L) 
　　　操作结果 ：构造一个空的线性表L。 
DestroyList(&L) 
　　　初始条件 ：线性表L已存在。 
　　　操作结果 ：销毁线性表L。 
ClearList(&L) 
　　　初始条件 ：线性表L已存在。 
　　　操作结果 ：将L重置为空表。 
ListEmpty(L) 
　　　初始条件 ：线性表L已存在。 
　　　操作结果 ：若L为空表，则返回true，否则返回false。 
ListLength(L) 
　　　初始条件 ：线性表L已存在。 
　　　操作结果 ：返回L中数据元素的个数。 
GetElem(L,i,&e) 
　　　初始条件 ：线性表L已存在，且1≤i≤ListLength(L)。 
　　　操作结果 ：用e返回L中第i个数据元素的值。 
LocateElem(L,e) 
　　　初始条件 ：线性表L已存在。 
　　　操作结果：返回L中第1个值与e相同的元素在L中的位置。若这样的数据元素不存在，则返回值为0。
PriorElem(L,cur_e,&pre_e) 
　　　初始条件 ：线性表L已存在。 
　操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败，
pre_e无定义。 
NextElem(L,cur_e,&next_e) 
　　　初始条件 ：线性表L已存在。 
　操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，
next_e无定义。 
ListInsert(&L,i,e) 
　　　初始条件 ：线性表L已存在，且1≤i≤ListLength(L)+1。 
　　　操作结果 ：在L中第i个位置之前插入新的数据元素e，L的长度加1。 
ListDelete(&L,i)
　　　初始条件 ：线性表L已存在且非空，且1≤i≤ListLength(L)。 
　　　操作结果 ：删除L的第i个数据元素，L的长度减1。
TraverseList(L)
　　　初始条件 ：线性表L已存在。
　　　操作结果 ：对线性表L进行遍历，在遍历过程中对L的每个节点访问一次。
}ADT List

抽象数据类型仅是一个模型的定义，并不涉及模型的具体实现，因此这里描述中所涉及的参数不必考虑具体数据类型。在实际应用中，数据元素可能有多种类型，到时可根据具体需要选择使用不同的数据类型。

顺序表及其实现

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表（Sequential List）。其特点是，逻辑上相邻的数据元素，其物理位置也是相邻的。

只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

//
// Created by 朱玥 on 24-9-29.
//

#include <stdio.h>
#include "stdlib.h"

#define MAXSIZE 100  // 假设我们规定的顺序表长度最大为100

typedef struct {
    int *data;  //指向存储数据的动态数组的指针
    int length;  //表示当前顺序表中元素的数量
    int list_size; //表示顺序表的总容量（即分配的数组大小）
} SeqList;

//1.初始化一个顺序链表，这是一个返回类型为 SeqList* 的函数
SeqList *init_seq_list() { 
    SeqList *list = (SeqList *) malloc(sizeof(SeqList)); //预分配内存
    list->data = (int *) malloc(MAXSIZE * sizeof(int)); //这行代码为 list 中的 data 数组分配内存。
    list->length = 0;  //初始化 length，表示当前链表中还没有元素。
    list->list_size = MAXSIZE;  //设置链表的总容量为 MAXSIZE，也就是链表最多可以存储的元素数量。
    return list;
}

// 2. 销毁顺序链表
void destroy_seq_list(SeqList *list) {
    if (list == NULL) return;  //如果链表指针为NULL，直接返回。
    free(list->data);  //释放动态分配的 data 数组内存。
    list->length = 0;
    list->list_size = 0;  //将 length 和 list_size 设置为0，以确保链表状态被重置。
}

//5.清空顺序链表
void clear_seq_list(SeqList *list) {
    if (list == NULL) return;
    list->length = 0;  //我们要做的是清空而不是销毁，所以简单的将链表长度置零即可。
}

//6.索引链表元素
int get_seq_elem(SeqList *list, int i) {
    if (list == NULL || i < 0 || i >= list->length) //错误的条件
        return -1;
    return list->data[i];
}

//7.查找元素位置
int locate_seq_elem(SeqList *list, int e) {
    if (list == NULL) return -1;
    for (int i = 0; i < list->length; ++i) { //依次查找
        if (list->data[i] == e) return i;
    }
    return -1;
}

// 8.获取前驱元素
int prior_elem(SeqList *list, int cur_e) {
    if (list == NULL) return -1;
    for (int i = 1; i < list->length; ++i) {
        if (list->data[i] == cur_e) return list->data[i - 1];
    }
    return -1;
}

//9.插入元素
int insert_elem(SeqList *list, int i) {
    if (list == NULL || list->length >= list->list_size) return -1;
    for (int j = list->length; j > i; --j) {
        list->data[j] = list->data[j - 1];
    }
    list->data[i] = i;
    list->length++;
    return 0;
}

//10.删除元素
int del_elem(SeqList *list, int i) {
    if (list == NULL || i < 0 || i >= list->length) return -1;
    for (int j = i; j < list->length - 1; ++j) {  //直接将后面的元素依次左移即可。
        list->data[j] = list->data[j + 1];
    }
    list->length--;
    return 0;
}

预分配内存浪费问题及其解决

1	SeqList list = (SeqList ) malloc(sizeof(SeqList)); //预分配内存

SeqList *list: 定义了一个指针变量 list，它指向一个 SeqList 类型的结构体。通过 malloc 函数来为这个结构体动态分配内存。
malloc(sizeof(SeqList)):malloc 分配内存的大小由 sizeof(SeqList) 决定，也就是 SeqList 结构体的大小。
(SeqList *): malloc 返回的是一个 void* 类型的指针，需要通过强制类型转换 (SeqList *) 转换为 SeqList 类型的指针

你提到的 list->data = (int *) malloc(MAXSIZE * sizeof(int)); 是在初始化顺序表时为数据数组 data 预分配了一块固定大小的内存。在这个例子中，MAXSIZE 代表了最多可以存储的元素个数，而 sizeof(int) 表示每个 int 类型所占的内存大小。

1. 内存预分配是否会造成浪费？
是的，这种直接分配 MAXSIZE * sizeof(int) 的方式确实可能会在某些情况下造成内存浪费，尤其是当你不确定最终会存储多少数据时。比如如果你只使用了很少的空间（比如只存了几个元素），但系统依然为你分配了足够存储 MAXSIZE 个元素的空间，这部分未使用的内存就浪费了。

2. 如何体现动态？
要真正体现动态内存分配，可以根据实际需要逐步增加内存，而不是一开始就分配固定的 MAXSIZE 空间。可以采用 动态扩容 的策略。

一个常见的做法是：

初始时分配一个相对较小的空间（例如10个元素的空间）。

当空间不足时，通过倍增的方式动态扩展空间。即当数组达到当前容量时，重新分配一块更大的内存（比如原来的2倍），然后将原来的数据拷贝到新分配的空间。

这样可以减少内存浪费，同时在需要的时候自动扩容。

3. 改进方案
你可以实现类似于 动态数组 的结构，采用按需扩展空间的方式。以下是一个改进的例子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#define INIT_SIZE 10   // 初始容量
#define INCREASE_FACTOR 2   // 扩展倍数

typedef struct {
    int *data;
    int length;
    int list_size;
} SeqList;

// 初始化顺序表，初始容量为 INIT_SIZE
SeqList* init_seq_list() {
    SeqList* list = (SeqList*)malloc(sizeof(SeqList));
    list->data = (int*)malloc(INIT_SIZE * sizeof(int));  // 初始分配较小的内存
    list->length = 0;
    list->list_size = INIT_SIZE;
    return list;
}

// 扩展顺序表容量
void expand_seq_list(SeqList* list) {
    int new_size = list->list_size * INCREASE_FACTOR;  // 扩展为原来的两倍
    list->data = (int*)realloc(list->data, new_size * sizeof(int));  // 扩容
    if (list->data == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    list->list_size = new_size;  // 更新容量大小
}

// 添加元素到顺序表
void add_element(SeqList* list, int elem) {
    if (list->length >= list->list_size) {
        expand_seq_list(list);  // 当容量不足时，进行扩容
    }
    list->data[list->length++] = elem;  // 添加元素
}

int main() {
    SeqList* list = init_seq_list();

    // 测试添加多个元素
    for (int i = 0; i < 100; ++i) {
        add_element(list, i);
        printf("已添加元素: %d, 当前长度: %d, 当前容量: %d\n", i, list->length, list->list_size);
    }

    // 记得释放内存
    free(list->data);
    free(list);

    return 0;
}
4. 改进后的优点

节省内存：一开始只分配较小的空间，真正需要时才扩展内存，避免初期的内存浪费。

动态扩展：顺序表可以根据需要不断扩展，容量不再固定为 MAXSIZE，而是动态增长。

高效使用内存：虽然扩展内存时可能有一定的开销（重新分配和拷贝），但这种方式可以有效平衡内存使用和性能。

通过这种方式，你可以实现一个真正的“动态”数组，不再局限于一开始预设的固定内存大小。

各个操作时间复杂度分析

操作	时间复杂度	备注
索引（取值）	$O(1)$
查找	$O(n)$	平均查找长度（Average Search Length，ASL)为$\frac{n+1}{2}$
插入	$O(n)$
删除	$O(n)$

索引是通过根据指定的位置序号i，获取顺序表中第i个数据元素的值。查找是根据指定的元素值e，查找顺序表中第1个值与e相等的元素。

单向链表

为了表示每个数据元素 $a_i$ 与其直接后继数据元素 $a_i+1$ 之间的逻辑关系，对数据元素 $a_i$ 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（直接后继的存储位置）。这两部分信息组成数据元素 $a_i$ 的存储映像，称为节点（node）。它包括两个域：

其中存储数据元素信息的域称为数据域；
存储直接后继存储位置的域称为指针域。

指针域中存储的信息称作指针或链。$n$ 个节点[ $a_i(1≤i≤n)$ 的存储映像]链接成一个链表，即为线性表：

$(a_1, a_2,…, a_n)$

的链式存储结构。又由于此链表的每个节点中只包含一个指针域，故又称线性链表或单链表。

根据链表节点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和双向链表多用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。

一般情况下，为了处理方便，在单链表的第一个节点之前附设一个节点，称之为头节点。图2.8所示的单链表增加头节点后如下图所示。

单链表基本操作的实现

如下代码所示:

定义单链表结点类型

//
// Created by 朱玥 on 2024/10/10.
//

#include "stdio.h"
#include "stdlib.h"

// 定义单链表结点类型
typedef struct LNode {
    int data;
    struct LNode *next;  //指向下一个节点的指针
} LNode, *LinkList;

为了提高程序的可读性，在此对同一结构体指针类型起了两个名称，LinkList与LNode *，两者本质上是等价的。通常习惯上用LinkList定义单链表，强调定义的是某个单链表的头指针；用LNode *定义指向单链表中任意节点的指针变量。例如，
若定义LinkList L，则L为单链表的头指针，
若定义LNode *p，则p为指向单链表中某个节点的指针，用*p代表该节点。
当然也可以使用定义LinkList p，这种定义形式完全等价于LNode *p。

注意区分指针变量和节点变量两个不同的概念，若定义 LinkList p或LNode *p，则p为指向某节点的指针变量，表示该节点的地址；而*p为对应的节点变量，表示该节点的名称。

初始化单向链表

//1.初始化单向链表
int init_list(LinkList *L) {//传入参数为二级指针
    *L = (LinkList) malloc(sizeof(LNode));  
    if (*L == NULL) {
        return 0;
    }
    (*L)->next = NULL;  //指向下一个节点的指针为空。
    return 1;
}

在 C 语言中，LinkList *L 表示传入的是一个指向指针的指针。*L 用于解引用这个指针，允许函数直接修改调用该函数时传入的头指针。

具体来说：

LinkList *L 是一个指向 LinkList 的指针，也就是指向一个指向 LNode 的指针。
使用 *L 可以访问并修改这个指针的值，即将新分配的内存地址赋给它。

因此，在初始化链表时，我们需要通过 *L 来给传入的头指针分配内存。这样，链表的头指针在函数外部也能反映这个变化。

销毁单向链表

//2.销毁单向链表
int destroy_list(LinkList *L) {
    LinkList p;
    while (*L) {      //和前面说的一样，*L是个指针
        p = (*L)->next;
        free(*L);
        *L = p;
    }
    return 1;
}

查找节点

算法:单链表的按值查找

① 用指针p指向首元节点。

② 从首元节点开始依次顺着链域next向下查找，只要指向当前节点的指针p不为空，并且p所指节点的数据域不等于给定值e，则循环执行以下操作：p指向下一个节点。

③ 返回p。若查找成功，p此时指向节点的地址值，若查找失败，则p的值为NULL。

LNode* find_node(LinkList L, int value) { //这个时候传入的参数是一个一级指针
    LNode* p = L->next;
    while (p != NULL) {
        if (p->data == value) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

获取元素(取值)

算法:单链表的取值

① 用指针p指向首元节点，用j做计数器初值赋为1。

② 从首元节点开始依次顺着链域next向下访问，只要指向当前节点的指针p不为空（NULL），并且没有到达序号为i的节点，则循环执行以下操作：

p指向下一个节点；

计数器j相应加1。

退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i 值不合法（i大于表长n或i小于等于0），取值失败返回ERROR；否则取值成功，此时j = i时，p所指的节点就是要找的第i个节点，用参数e保存当前节点的数据域，返回1

时间复杂度为 $O(n)$

int get_elem(LinkList L, int i, int *e) {
    LNode* p = L->next;  // p是一个结构体指针，一级指针
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }
    *e = p->data;
    return 1;
}

因为规定了函数的返回值代表操作成功与否，所以又用了*e 参数来接受获得的值。

插入元素

假设要在单链表的两个数据元素 $a$ 和 $ b$ 之间插入一个数据元素 $ x$，已知p为其单链表存储结构中指向节点 $a$的指针，如图2.11（a）所示。

算法:单链表的插入

将值为e的新节点插入表的第i个节点的位置，即插入节点 $a_{i-1}$ 与 $a_i$ 之间，具体插入过程如图所示，图中对应的5个步骤说明如下。

① 查找节点 $a_{i-1}$ 并由指针p指向该节点。

② 生成一个新节点*s。

③ 将新节点*s的数据域置为e。

④ 将新节点*s的指针域指向节点 $a_i$ .

⑤ 将节点*p的指针域指向新节点*s。

时间复杂度为 $O(n)$

int insert_elem(LinkList L, int i, int e) { //这个时候传入的参数是一个一级指针
    LNode* p = L;   //p是一级指针
    int j = 0;
    //while循环用于找到这个元素，相当于重新实现了获取元素功能。
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) {
        return 0;
    }
    //为新节点分配内存
    LNode* s = (LNode*) malloc(sizeof(LNode));
    //下面三句把原有的指针断开，又连接上。
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 1;
}

删除元素

删除第 i 个节点，并返回该节点的数据

算法:单链表的删除

删除单链表的第 $i$个节点 $a_i$的具体过程如图所示，图中对应的4个步骤说明如下。

① 查找节点$a_{i−1}$并由指针p指向该节点。

② 临时保存待删除节点 $a_i$ 的地址在q中，以备释放。

③ 将节点*p的指针域指向 $ a_i$ 的直接后继节点。

④ 释放节点 $ a_i$ 的空间。

时间复杂度为 $O(n)$

int delete_elem(LinkList L, int i, int *e) {
    LNode* p = L;
    int j = 0;
    //while循环用于找到这个元素的前一个元素，即下标为i-1的，获取元素功能。
    while (p->next && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p->next || j > i - 1) {
        return 0;
    }
    LNode* q = p->next; // 保存待删除节点
    *e = q->data;       // 获取数据
    p->next = q->next;  // 更新前一个节点的指针
    free(q);            // 释放待删除节点

    return 1;
}

在 delete_elem 函数中，while 循环中找到的 p 是待删除元素的前一个节点，而不是待删除的元素本身。

具体来说：

p 最终指向的是待删除元素的前一个节点，这样才能通过 p->next 访问待删除的元素。
待删除的元素 q 是通过 q = p->next 获取的。因此，q 是要被删除的节点，而 p 是其前一个节点。这样才能在删除时更新指针，确保链表的结构不被破坏。

头插法创建链表

头插法(前插法)是通过将新节点逐个插入链表的头部（头节点之后）来创建链表，每次申请一个新节点，读入相应的数据元素值，然后将新节点插入到头节点之后。

算法2.11　

头插法(前插法)创建单链表

① 创建一个只有头节点的空链表。

② 根据待创建链表包括的元素个数$n$，循环$n$次执行以下操作：

生成一个新节点*p；

输入元素值赋给新节点*p的数据域；

将新节点*p插入到头节点之后。

时间复杂度为 $O(n)$ .

程序如下:

int create_list_by_head(LinkList L, int n) {
    LNode* p;
    for (int i = 0; i < n; i++) {
        p = (LNode*) malloc(sizeof(LNode));
        if (!p) {  //p不为NULL函数返回，链表创建失败。
            return 0;//如果内存分配失败，返回 0，表示链表创建失败。
        }
        scanf("%d", &p->data);
        p->next = L->next;//先让p的指针指向L的后继元素
        L->next = p;//再让L的指针指向p
    }
    return 1;
}

:warning:注意,下面两句是有顺序的.否则会造成链表元素丢失

1 2	p->next = L->next;//先让p的指针指向L的后继元素 L->next = p;//再让L的指针指向p

同时,注意输入顺序,如果想创建逻辑顺序为 $a\rightarrow b\rightarrow c\rightarrow d\rightarrow e$ 的单项链表,如果用头插法,输入顺序,应该是 $e\rightarrow d\rightarrow c\rightarrow b\rightarrow a$ ,恰好反过来.

尾插法创建链表

尾插法(后插法)是通过将新节点逐个插入链表的尾部来创建链表。同前插法一样，每次申请一个新节点，读入相应的数据元素值。不同的是，为了使新节点能够插入表尾，需要增加一个尾指针q 指向链表的尾节点。

算法2.12　

尾插法(后插法)创建单链表

① 创建一个只有头节点的空链表。

② 尾指针q初始化，指向头节点。

③ 根据创建链表包括的元素个数 $n$ ，循环 $n$ 次执行以下操作：

生成一个新节点*p；

输入元素值赋给新节点p的数据域；

将新节点*p插入尾节点*q之后；

尾指针r指向新的尾节点*p。

时间复杂度为 $O(n)$ .


int create_list_by_tail(LinkList L, int n) {
    LNode* p = L; //起初，p 指向链表的头指针 L，也就是链表的头结点，因为只有一个节点 ，所以也是尾节点。
    for (int i = 0; i < n; i++) {
        LNode* q = (LNode*) malloc(sizeof(LNode));
        if (!q) {
            return 0;//如果内存分配失败，返回 0，表示链表创建失败。
        }
        scanf("%d", &q->data);
        q->next = NULL;//让q的指针为NULL，使得q为新的尾节点。
        p->next = q; //让原来尾节点p的指针指向q
        p = q;//尾节点更新，每次输入一个数，尾节点就变成了当前这个元素
    }
    return 1;
}

尾插法的优点是链表的构建顺序与输入顺序一致，适合需要从前往后逐步生成链表的情况。如果想创建逻辑顺序为 $a\rightarrow b\rightarrow c\rightarrow d\rightarrow e$ 的单项链表,输入顺序,应该是 $a\rightarrow b\rightarrow c\rightarrow d\rightarrow e$ ,保持一致.

在这种情况下,下面的语句的顺序没有影响:

1 2	q->next = NULL;//让q的指针为NULL，使得q为新的尾节点。 p->next = q; //让原来尾节点p的指针指向q

时间复杂度分析

操作	时间复杂度	备注
销毁单向链表	$O(n)$
按值查找节点	$O(n)$
获取元素(取值)	$O(n)$
删除元素	$O(n)$
头插法创建单向链表	$O(n)$
尾插法创建单向链表	$O(n)$

循环链表

循环链表（Circular Linked List）是另一种形式的链式存储结构。其特点是表中最后一个节点的指针域指向头节点，整个链表形成一个环。由此，从表中任一节点出发均可找到表中其他节点，图2.17所示为单链的循环链表。类似地，还可以有多重链的循环链表。

循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时，判别当前指针p是否指向表尾节点的终止条件不同。在单链表中，判别条件为p!=NULL或p->next!=NULL，而循环单链表的判别条件为p!=L或p->next!=L

在某些情况下，若在循环链表中设立尾指针而不设头指针[见图2.18（a）]，可使一些操作简化。例如，将两个线性表合并成一个表时，仅需将第一个表的尾指针指向第二个表的第一个节点，第二个表的尾指针指向第一个表的头节点，然后释放第二个表的头节点。当线性表以图 2.18（a）的循环链表作存储结构时，这个操作仅需改变两个指针值即可，主要语句段如下：

1
2
3

p = B->next->next; 
B->next = A->next;
A->next = p;

双向链表

双向链表实现大同小异，只需要把prev指针处理好就行:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// 定义双链表结点类型
typedef struct LNode {
    int data;
    struct LNode* next;
    struct LNode* prev;
} LNode, * LinkList;


//初始化双链表
int init_list(LinkList* L) {
    *L = (LinkList)malloc(sizeof(LNode));
    if (*L == NULL) {
        return 0;
    }
    (*L)->next = NULL;
    (*L)->prev = NULL;
    return 1;
}

//销毁链表
int destroy_list(LinkList* L) {  //指向结构体指针的指针
    LinkList p = *L;  //p是结构体指针，对L解引。
    while (p != NULL) {
        LinkList q = p->next;  //q用于存储p的下一个节点，防止释放内存后找不到
        free(p);
        p = q;
    }
    return 1;
}

//根据值查找节点
LNode* find_node(LinkList L, int value) {
    LNode* p = L->next;
    while (p != NULL) {
        if (p->data == value) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

//根据下标索引节点
int get_elem(LinkList L, int i, int* e) {
    LNode* p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }
    *e = p->data;
    return 1;
}

//插入节点到指定位置
int insert_elem(LinkList L, int i, int e) {
    LNode* p = L;
    int j = 0;
    //找到这个位置
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) {
        return 0;
    }
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;

    s->next = p->next;  //令s的next指向p的下一个节点。
    s->prev = p;        //令s的prev指向p。
    if (p->next != NULL) {  // 如果 p 的下一个节点不是 NULL，更新 p->next 的 prev 指针
        p->next->prev = s;
    }
    p->next = s;        //令p的next指向s。
    return 1;
}


//删除节点并且得到删除的元素
int delete_elem(LinkList L, int i, int* e) {
    LNode* p = L;
    int j = 0;
    while (p->next && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p->next || j > i - 1) {
        return 0;
    }
    LNode* q = p->next;
    p->next = q->next;
    if (q->next != NULL) {  // 如果 q->next 不是 NULL，更新它的 prev 指针
        q->next->prev = p;
    }
    *e = q->data;
    free(q);
    return 1;
}


//头插法创建链表
int create_list_by_head(LinkList L, int n) {
    LNode* p;   //p是要插入的节点
    for (int i = 0; i < n; i++) {
        p = (LNode*)malloc(sizeof(LNode));
        if (!p) {
            return 0;
        }
        scanf("%d", &(p->data));  //读入p的数据
        p->next = L->next;  //令p的next指向L的下一个节点。
        p->prev = L;        //令p的prev指向L。
        if (L->next != NULL) {  // 判断 L->next 是否为空，避免空指针访问
            L->next->prev = p;
        }
        L->next = p;        //令L的next指向p
    }
    return 1;
}


//尾插法创建链表
int create_list_by_tail(LinkList L, int n) {
    LNode* p = L; //p是尾节点
    for (int i = 0; i < n; i++) {
        LNode* q = (LNode*)malloc(sizeof(LNode));
        if (!q) {
            return 0;
        }
        scanf("%d", &q->data);
        q->next = NULL;     //令q的next指向NULL
        p->next = q;        //令原来尾结点的p的next指向q
        q->prev = p;        //令q的prev指向p
        p = q;              //更新尾节点
    }
    return 1;
}

// 打印链表
void printList(LNode* head) {
    LNode* temp = head->next; //不需要打印头节点，从第一个节点开始打印
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}



//测试信息
int main() {

	//创建链表
	LinkList L ;
	//初始化
	init_list(&L);

	create_list_by_head(L, 5);
	printf("下面是头插法创建的链表\n");
	printList(L);

	//插入节点
	insert_elem(L, 2, 1000);
	printf("下面是在2位置插入操作后的的链表\n");
	printList(L);

	//删除某个元素
	int elem_deleted;
	delete_elem(L, 2, &elem_deleted);
	printf("要删除的节点是 %d\n", elem_deleted);
	printf("删除第二个节点后的链表为:\n");
	printList(L);

	//下表索引和查找节点
	int elem;
	get_elem(L, 3, &elem);
	printf("第3个节点为%d\n", elem);
	
	LNode* node;
	node = find_node(L, elem);
	printf("这个节点的元素是 %d\n", node->data);

	// 销毁链表，防止内存泄漏
	destroy_list(&L);

	return 0;
w
}

Data Structures and Algorithms-linear list

线性表的定义

顺序表及其实现

预分配内存浪费问题及其解决

1. 内存预分配是否会造成浪费？

2. 如何体现动态？

3. 改进方案

4. 改进后的优点

各个操作时间复杂度分析

单向链表

单链表基本操作的实现

定义单链表结点类型

初始化单向链表

销毁单向链表

查找节点

获取元素(取值)

插入元素

删除元素

头插法创建链表

尾插法创建链表

时间复杂度分析

循环链表

双向链表