链表（linked list）的别称

线性表的链式表示、链式存储结构、链式映像、随机存取结构的储存结构

单向链表

长相

无头链表

指向首元结点的指针叫做头指针（head pointed）

有头链表

第一个结点叫头结点（head node）

结构体定义

别称

线性表的顺序表示、顺序存储结构、顺序映像、随机存取结构的储存结构

作用

利用数组的连续存储空间顺序存放线性表的各个元素
a[n-1] 是 a[n] 的直接前趋，a[n+1] 是 a[n] 的直接后继。

结构体代码

第一种写法

1
2
3
4

typedef struct sqList {
    ElementType Data[MAXSIZE];
    int Last;
} sqList;

Python

1
2
3
4

class LNode:
    def __init__(self):
        self.Data = []
        self.last = -1

前情提要

在之前的 C 语言的学习当中，我们提到了 malloc 和 free，这两个函数是用来动态分配内存的。
看好。
动态分配的代码是这样写的。

1
2
3
4
5
6
7
8

#include <stdio.h>
#include <stdlib.h>
int main() {
    int n;
    scanf("%d", &n);
    int *a = (int*)malloc(sizeof(int)*n);
    free(a);
} 

结构体结构

1
2
3
4
5

typedef struct {
    ElemType *data;
    int length;
    int listSize;
} DA;

我来解释一下，这个结构体声明。
length 是你实际存了多少的东西，listSize 是你目前表的最大长度。

动态分配的使用

其实，无非就是创、增、删、改、读、销。

创建一个动态分配

定义

线性表（linear list）有以下三个规则：

1. 存在唯一的一个 “第一个” 数据元素
2. 存在唯一的一个 “最后一个” 数据元素
3. 除 “第一个” 和 “最后一个” 元素均只有一个直接前驱（immediate predecessor）和一个直接后继（immediate successor）。

一些参数

线性表长度为 n，也可以直接用 xxLen 表示
当 n=0 时，就是空表
a 的下表 i 表示的是 a(i) 在线性表的位序

一些要说的东西

对于线性表存在两种输入的情况：

1. 不修改内容，只是把内容传入，如 List L
2. 譬如，getLength(List L)
3. 可修改内容，也可把内容传入，就传地址（指针），如 List *L
4. 譬如，initList(List *L)
5. 但是，在此后要访问这指针的内容要用到 L->

但是，我们要注意的是结构体。
举个例子
这是一个动态分配