1、定义：
通过一组任意的存储单元来存储线性表中的数据元素。为了建设数据元素之间的线性关系，对每个链表节点，除了寄存元素本身的信息外，还须要寄存一个指向下一个节点
构造体：
typedef int ElemType;
typedef struct LNode { // 定义单链表节点类型
ElemType data; // 每个节点寄存一个数据元素
struct LNode *next; // 指针指向下一个节点
} LNode, *LinkList; // 强调这是一个单链表应用 LinkList，强调节点应用 LNode*2、创立一个单链表
2.1 用头插法建设单链表
新节点插入到以后列表的表头：
代码实现：
/**
* 用头插法建设单链表
* @param L
* @return
*/
LinkList List_HeadInsert(LinkList &L) { // 逆向建设单链表
LNode *s;
int x;
L = (LinkList) malloc(sizeof(LNode)); // 创立头节点
L->next = NULL; // 初始为空链表
scanf("%d", &x); // 输出节点的值
while (x != 9999) { // 输出 9999 示意完结
s = (LNode *) malloc(sizeof(LNode)); // 创立新节点
s->data = x;
s->next = L->next;
L->next = s; // 将新节点插入表中，L 为头指针
scanf("%d", &x);
}
return L;
}采纳头插法建设单链表时，读入数据的程序与生成的链表中的元素的程序式相同的
2.2 用尾插法建设单链表
新节点插入到以后列表的表尾，该办法须要一个尾指针指向链表的最初一个节点，图中未画出尾指针：
代码实现：
/**
* 用尾插法建设单链表
* @param L
* @return
*/
LinkList List_TailInsert(LinkList &L) { // 正向建设单链表
int x; // 设 ElemType 为整型
L = (LinkList) malloc(sizeof(LNode)); // 建设头节点
LNode *s, *r = L; // r 为表尾指针
scanf("%d", &x); // 输出节点的值
while (x != 9999) {s = (LNode *) malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; // r 指向新的表尾节点
scanf("%d", &x);
}
r->next = NULL; // 尾节点指针置空
return L;
}3、基本操作
3.1 在指定节点前插入元素
实现原理图：
代码实现:
/**
* 前插操作，在 p 节点之前插入元素 e
* @param p
* @param e
* @return
*/
bool InsertPriorNode(LNode *p, ElemType e) {if (p == NULL) {return false;}
LNode *s = (LNode *) malloc(sizeof(LNode));
if (s == NULL) {return false;}
s->next = p->next;
p->next = s; // 新节点 s 连到 p 之后
s->data = p->data; // 将 p 中元素复制到 s 中
p->data = e; // p 中的元素改为 e
return true;
}3.2 在指定节点后插
代码实现：
/**
* 后插操作，在 p 节点之后插入元素 e
* @param p
* @param e
* @return
*/
bool InsertNextNode(LNode *p, ElemType e) {if (p == NULL) {return false;}
LNode *s = (LNode *) malloc(sizeof(LNode));
if (s == NULL) { // 内存调配失败
return false;
}
s->data = e; // 用节点 s 保留数据元素 e
s->next = p->next; // 留神先后顺序
p->next = s;
return true;
}3.3 按位序删
代码实现：
/**
* 按位序删除，带头结点
* @param L
* @param i
* @param e
* @return
*/
bool ListDelete(LinkList &L, int i, ElemType e) {if (i < 1) {return false;}
LNode *p; // 指针 p 指向以后扫描到的节点
int j = 0; // 以后 p 指向的是第几个节点
p = L; // L 指向头节点，头节点是第 0 个节点，不存数据
while (p != NULL && j < i - 1) { // 循环找到第 i-1 个节点
p = p->next;
j++;
}
if (p == NULL) { // i 值不非法
return false;
}
if (p->next == NULL) { // 第 i - 1 个节点之后已无其余节点
return false;
}
LNode *q = p->next; // 令 q 指向被删除的节点
e = q->data; // 用 e 返回元素的值
p->next = q->next; // 将 * q 节点从链中断开
free(q); // 开释节点的存储空间
return true;
}3.4 按位查找
/**
* 按位查找，返回第 i 个元素，带头节点
* @param L
* @param i
* @return
*/
LNode *GetElem(LinkList L, int i) {if (i < 0) {return NULL;}
LNode *p; // 指针 p 指向以后扫描到的节点
int j = 0; // 以后 p 指向的是第几个节点
p = L; // L 指向头节点，头节点是第 0 个节点，不存数据
while (p != NULL && j < i) { // 循环找到第 i 个节点
p = p->next;
j++;
}
return