提示：文章参考王道的课程，相当于课程笔记
目录
一、单链表的定义及初始化
1、定义
2、初始化
1)不带头结点的单链表
2)带头节的单链表
二、单链表插入和删除
1)插入
1、按位序插入（带头结点）
2、按位插入（不带头结点）
3、指定结点的后插操作
4、指定结点的前插操作
2）删除
1、按位序删除（带头结点）
2、指定结点删除
3、指定最后结点的删除
三、查找
1）按位查找
2）按值查找
四、建立
1）头插法
2）尾插法
六、补充求单链表长度
一、单链表的定义及初始化
首先介绍一个关键字typedef ——数据类型重命名
typedef < 数据类型> <别名> typedef struct LNode LNode
1、定义
代码语言：javascript复制typedef sturct LNode{ //定义单链表结点类型
ElemType date ; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
}LNode, *LinkList;
typedef LNode{ //定义单链表结点类型
ElemType date ; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
};
typedef struct LNode LNode;
typedef struct LNOde *LinkList;
//上面俩个是等价的
struct LNode *p = (struct LNode*) malloc(sizeof(struct LNode)); /*增加一个新结点：在内存中申请一个结点所需空间，并用指针p指向这个结点 */要表示一个单链表时，只需要声明一个头指针L，指向单链表的第一个节点
LNode *L ; //声明一个指向单链表第一个结点的指针 （强调这是一个结点用LNode*）
或： LinkList L； //声明一个指向单链表的第一个结点的指针 （强调这是一个单链表LinkList）
2、初始化
1)不带头结点的单链表
代码语言：javascript复制bool InitList(LinkList &L) //初始化空链表
{
L = NULL; //空表没有任何结点
return true;
}
void test()
{
LinkList L ; //声明一个指向单链表的指针
//初始化一个空表
InitList (L);
}判断是否为空
代码语言：javascript复制bool Empty(LinkList L){
if(L == NULL)
return true;
else
return false;
}
//或：
bool Empty(LinkList L){
return (L == NULL);
}2)带头节的单链表
代码语言：javascript复制//初始化一个单链表（带头结点）
bool InitList (LinkList &L){
L = (LNode * ) malloc (sizeof(LNode)); //分配一个头结点
if (L == NULL) //内存不足分配失败
return false;
L->next = NULL;
return true;
}判断是否为空
代码语言：javascript复制bool Empty(LinkList L){
if(L->next == NULL)
return true;
else
return false;
}二、单链表插入和删除
1)插入
1、按位序插入（带头结点）
代码语言：javascript复制//在第i个位置插入元素e
bool ListInsert(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;
LNode *s = (LNode*)malloc(sizeof(LNode));
s->date = e;
s->next = p->next;
p->next = s; //将结点s连到p之后
return true;
}2、按位插入（不带头结点）
代码语言：javascript复制bool ListInsert(LinkList &L, int i,,ElemType e){
if( i < 1)
return false;
if(i == 1){
LNode *s = (LNode *s)malloc(sizeof(LNode));
s->date = e;
s->next = L;
L = s;
return true;
}
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;
LNode *s = (LNode*)malloc(sizeof(LNode));
s->date = e;
s->next = p->next;
p->next = s; //将结点s连到p之后
return true;
}3、指定结点的后插操作
代码语言：javascript复制bool InsertNextNode (LNode *p ,Elemtype e){
if( p == NULL)
return false；
LNode *s = (LNode *) malloc(sizeof(LNode));
if (s == NULL) //内存分配失败
return false;
s->date = e; //用结点s保存数据元素e
s->next = p->next;
p->next = s; //将结点s连接到p之后
return true;
}4、指定结点的前插操作
代码语言：javascript复制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->date = p->date; //将p之中元素复制到s中
p->date = e; //p中元素覆盖W为e
}
//时间复杂度为O(1)2）删除
1、按位序删除（带头结点）
代码语言：javascript复制//按位序删除（带头结点）
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) return false; //i值不合法
if(p->next == NULL) return false; //第i-1个节点之后没有其他节点
LNode *q = p->next; //q指向被删除的节点
e = q->data;
p->next = q->next;
free(q);
return true;
} 2、指定结点删除
代码语言：javascript复制//指定节点的删除
bool DeleteNode(LNode *p){
if(p==NULL) return false;
LNode *q = p->next; //q指向*p的后继节点
p->data = p->next->data; //p的后继节点数据赋值给p
p->next = q->next; //q节点从链中断开
free(q); //释放
return true;
}3、指定最后结点的删除
代码语言：javascript复制//指定节点的删除
bool DeleteNode(LNode *p){
if(p==NULL) return false;
LNode *q = p->next; //q指向*p的后继节点
p->data = p->next->data; //p的后继节点数据赋值给p
p->next = q->next; //q节点从链中断开
free(q); //释放
return true;
}三、查找
1）按位查找
代码语言：javascript复制//按位查找，返回第i各元素带头节点
LNode * GetElem(LinkList L,int i){
if(i<0){
return NULL;
}
LNode *p; // 指针p指向当前扫描到的结点
int j = 0;
p = L; //L指向头结点 , L是第0个结点（不存放数据）
while(p!=NULL && j < i){ //循环到第i个结点
p = p->next;
j ;
}
return p;
} 2）按值查找
代码语言：javascript复制//按值查找，返回e元素
//带头节点
LNode * GetElem(LinkList L,ElemType e){
LNode *p = L->next; //从第一个结点开始查找数据域为e的结点
while(p!=NULL && p->data != e){
p = p -> next;
}
return p;
} 四、建立
1）头插法
代码语言：javascript复制//头插法
LinkList List_HeadInsert(LinkList &L){
int x; //假设ElemType为整型
L = (LinkList)malloc(sizeof(LNode)); //建立头结点
LNode *s; //r为表尾指针
L->next = NULL; //初始尾空链表 （必须初始化）
scanf("%d",&x);
while(x!=9999) {
s = (LNode*)malloc(sizeof(LNode));
s->next = L->next;
s->data = x;
L->next = s; //头结点指向新的结点
scanf("%d",&x);
}
return L;
} 2）尾插法
代码语言：javascript复制typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
//初始化一个单链表（带头节点）
bool InitList(LinkList &L){
L = (LNode*)malloc(sizeof(LNode));
if(L == NULL){
return false; //内存不足分配失败
}
L->next = NULL; //头结点之后暂时没有结点
return true;
}
//尾插法建立单链表： 初始化单链表长度
/*
while 循环{
每次取一个数据元素e
ListInsert(L,length 1,e) ;
length ;
}
时间复杂度：O（n2）
*/
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;
}
int main(){
LinkList L; //声明一个指向单链表的指针
InitList(L);//初始化一个空表
List_TailInsert(L);
return 0;
} 六、补充求单链表长度
代码语言：javascript复制//求单链表的长度
int Length (LinkList L){
int len = 0; //统计表长
LNode *p = L;
while(p->next != NULL){
p = p->next;
len ;
}
return len;
} 
