1.单链表基本知识点

2.单链表代码实现

1.带头结点（基本操作代码实现）

1.头插法可以实现单链表 逆置
2. 偷天换日(见文末代码)-----在某个结点前插入结点
3.头插法和尾插法中心思想------- 结点后插法 (见文末代码)
4.注意代码 封装 思想(见文末代码)

#include<bits/stdc++.h>
using namespace std;

//定义结点
typedef struct LNode{
	int data;	//存储数据
	struct LNode *next;	//	存储下一个结点的指针 
}LNode,*LinkList; 	//通常LinkList代表单链表，LNode *代表某个结点 

//0.初始化单链表
void InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode));
	L->next=NULL;
} 

//创建单链表核心思想——结点后插法 
//1.尾插法
LinkList TailCreate(int a[],int n){		//
	LinkList L=(LNode *)malloc(sizeof(LNode));	//	创建单链表头节点 
	L->next=NULL;	//末尾指针指向null 
	
	LNode *s,*r=L;	//r始终指向最后一个结点 //声明的是指针变量
	
	//核心思想——结点后插法 （在r后插入结点s） 
	for(int i=0;i<n;i++){
		s=(LNode *)malloc(sizeof(LNode));	//为指针变量分配存储空间 
		s->data=a[i];
		s->next=r->next;
		r->next=s;
		r=s;	
	}
	return L;
} 

//2.头插法——可以实现单链表逆置
LinkList HeadCreate(int a[],int n){
	LinkList L=(LNode *)malloc(sizeof(LNode));
	L->next=NULL;
	
	LNode *s;	//声明的是指针变量 
	//核心思想——结点后插法
	for(int i=0;i<n;i++){
		s=(LNode *)malloc(sizeof(LNode));	//为指针变量分配存储空间 
		s->data=a[i];
		s->next=L->next;
		L->next=s; 
	} 
	return L;
} 

//1.插入
bool Insert(LinkList &L,int i,int e){
	if(i<1){
		return false;
	}
	LNode *p;	//指针p指到当前扫描到的节点
	int j=0;	//指针p当前扫描到的位置
	p=L;	//p指向头节点，头节点是第0个节点
	
	while(p!=NULL&&j<i-1){	//	找到第i-1个位置 
		p=p->next;
		j++; 
	} 
	
	if(p==NULL){	//	检查i的值，即找到表末尾也未找到i-1的位置 
		return 0; 
	}
	
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	
	//以下两个顺序不能颠倒 
	s->next=p->next;
	p->next=s;
	
	return true;
} 

//2.删除
bool Delete(LinkList &L,int i,int &e){		//&e带回删除的值
	if(i<1){
		return false;
	} 
	LNode *p;
	int j=0;
	p=L;
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
	
	if(p==NULL){	//判断i的值是否合法 
		return false; 
	}
	
	LNode *s=(LNode *)malloc(sizeof(LNode));	//方便释放结点空间 
	s=p->next; 
	e=s->data;	//存储要删除结点的值
	p->next=s->next;
	free(s);
	return true;
}
 	
//3.按位查找
LNode * Get(LinkList L,int i){
	if(i<1){
		return NULL;
	}
	LNode *p=L;		//指向正在扫描的结点 
	int j=0;	//正在扫描的结点为第几个结点 
	while(p!=NULL&&j<i){
		p=p->next;
		j++;
	} 
	return p;
} 
 
//4.按值查找
int Locate(LinkList L,int e){	
	LNode *p=L;	//	指向第一个存有数据的节点 
	int j=0;
	
	while(p->next!=NULL){
		p=p->next;
		j++;
		if(p->data==e){
			return j;	//查找成功，返回位置 
		}
	}
	
	return 0;
} 
 
//5.单链表长度 
int Length(LinkList L){
	LNode *p=L;
	int cnt=0;
	while(p->next!=NULL){
		p=p->next;
		cnt++;
	}
	return cnt;
} 

//6.循环遍历输出
void PrintList(LinkList L){
	LNode *p=L;
	while(p->next!=NULL){
		p=p->next;
		cout<<p->data<<" ";
	}
	cout<<endl;
} 
 
//主程序 
int main(){
	
	LinkList L; 
	int a[]={1,2,3,4,5,6}; 
	//0.测试头插法 和尾插法 遍历输出 
//	L=HeadCreate(a,6);
//	PrintList(L);
	
	L=TailCreate(a,6);
	PrintList(L);
	
	//1.测试插入
//	if(Insert(L,3,8)){
//		PrintList(L);
//	} else{
//		cout<<"插入异常！！！"<<endl;
//	}
	
	//2.测试删除
//	int e=-1;
//	if(Delete(L,3,e)){
//		PrintList(L);
//		cout<<e<<endl; 
//	} else{
//		cout<<"删除异常！！！"<<endl;
//	} 
	
	//3.测试按位查找
//	LNode *p=Get(L,3);
//	cout<<p->data<<endl;
	
	//4.测试按值查找
//	int i=Locate(L,3);
//	cout<<i<<endl; 
	
	//5.测试单链表长度
//	int len=Length(L);
//	cout<<len<<endl; 

	return 0;
} 

2.结点后插法 偷天换日 封装思想

//指定结点的后插操作
bool InsertNextNode(LNode *p,int e){
	if(p==NULL){
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

//指定结点的前插入操作——偷天换日 
bool InsertPriorNode(LNode *p,int e){
	if(p==NULL){
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));
	
	//换值，并交换p、s结点的位置 
	s->data=p->data;
	s->next=p->next;
	p->next=s;
	p->data=e;
	return true;
}

// 删除指定结点——偷天换日 
bool DeleteNode(LNode *p){
	if(p==NULL){
		return false;
	}
	
	//含有小bug,不能删除指定的表末最后一个结点 
	LNode *s=p->next;
	p->data=s->data;
	p->next=s->next;
	free(s);
	return true;
} 

//封装思想测试
int main(){
	
	LinkList L; 
	int a[]={1,2,3,4,5,6}; 
//0.尾插法 遍历输出 
	L=TailCreate(a,6);
	PrintList(L);
	
//6.在封装的基础上，测试插入
	//6.1查找i-1的位置
	LNode *p=Get(L,2);	//按位查找结点
	//6.2在第i-1个节点后插入元素
	if(InsertNextNode(p,8)){	//偷天换日
		PrintList(L);
	} else{
		cout<<"插入异常！！！"<<endl;
	}
	
	return 0;
}