问题：
单链表的各种插入和删除操作。
思路：
（1）按位插入（带头结点）：
- 创建一个单链表结点。——typedef struct lnode{ int data; lnode *next}lnode,*linklist;
- 初始化单链表——void inilist(linklist &l)
- 进行插入操作——bool listinsert(linklist &l,int i,int e) // i表示插入位置，e表示插入的数值
- 插入函数中，我们先判断插入位置是否有误——if(i<1)return false;//因为带头结点，实际存储位置就是从数组下标1开始的，所以，插入位置应该大于等于1
- 之后，要想在第i个位置插入，需要先知道第i-1个位置在哪，所以找位置。
- 定义一个结构体指针lnode*p;让他开始指向头结点。——p=l;
- 在定义一个变量 j 表示p指针所指的位置（这是为了计算出p最后的位置）——int j=0；
- 来个while循环，终止条件为p不指向空，并且p所指位置，等于i-1时，跳出循环,所以j才<i-1,而不是=i-1；——while(p!=NULL&& j<i-1)
- 每次循环,p就往右移一位——p=p->next,j随之跟着变，j++从而保证j表示p所指的位置。
- 找到位置后，判断p是否为空，为空则无效，返回false；
- 之后进行连接，创一块空间，数据类型为lnode——lnode *s=(lnode*)malloc(sizeof(lnode));
- 然后给该空间数据域赋值——s->data=e;
- 之后该空间的指针域指向i-1的下一个位置，即——s->next=p->next;
- 随后p指向该空间——p->next=s;
代码如下：
bool listinsert(linklist &l,int i,int e)
{
if(i<1)
{
return false;
}
//找出第i-1的结点
lnode* p;
p=l;
int j=0;//表示p所指向的结点
while(p!=NULL && j<i-1)//找到第i-1的结点，因此不能<=i-1,应< ，while循环，先判断，再变化。
{
p=p->next; //每次循环，p结点从头结点，往后移1位。
j++;
}
//创建新节点，进行连接
if(p==NULL)
return false;
lnode* s=(lnode*)malloc(sizeof(lnode));
s->data=e;//数据域赋值
s->next=p->next;
p->next=s;
return true;
}
（2）按位插入（不带头结点）
- 由于单链表不带头结点，因此在插入第一位时，需要额外进行一步插入操作。
- 之后与带结点操作一样。
代码如下：
bool notouinsert(linklist &l,int i,int e)//无头结点 插入
{
if(i==1)
{
lnode *s=(lnode*)malloc(sizeof(lnode));
s->data=e;
s->next=l;
l=s; //头指针，指向s ，这里l为头指针，没头结点
return true;
}
lnode *p=l;
int j=1;
while(p!=NULL&&j<i-1)
{
p=p->next;
j++;
}
if(p==NULL)
return false;
lnode *s=(lnode*)malloc(sizeof(lnode));
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
（3）指定结点后插操作
- 就是在该节点之后，插入节点并赋值，相当于按位插入最后一步。
- bool houcha(lnode *p,int e)——结点以及插入值
代码如下：
bool houcha(lnode *p,int e) //后插操作
{
lnode *s=(lnode*)malloc(sizeof(lnode));//由于直接可以在该节点后插入，所以直接给结点赋值扩展空间
if(s==NULL)
return false;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
有了这个后插操作函数，下次写按位插入时，最后一步可以直接写该函数。
如这样：
bool insertlist(linklist &l,int i,int e)//带头结点 插入
{
if(i<1)
return false;
lnode* p;
p=l;
int j=0;
while(p!=NULL && j<i-1)
{
p=p->next;
j++;
}
houcha(p,e);
return true;
}
（4）指定节点——前插操作
- 在一个节点前，插入一个节点。
- bool qiancha(lnode *p,lnode* s)——在p节点前插入s节点。
- 我们需要先在p节点之后，创建节点或者给需要插入的结点放在后面先——为了最后数据对换，p中的数据跑s中，s中跑p中。
- 先判断，两个结点是否为空，为空，返回false；
- 之后给链，穿起来。s->next=p-next; p->next = s;
- 然后定义一个中间值，用来存放p中data域的数值。 int temp = p-data;
- 这时候就可以放心给p->data中赋值，给s结点中的数值赋值给p结点——p->data=s->data;
- 再给中间值存放的原p的值存进s结点中。——s->data=temp;
代码如下：
bool charu(lnode *p,lnode *s)
{
if(p==NULL ||s==NULL)
return false;
s->next=p->next;
p->next=s;
int temp =p->data;
p->data=s->data;
s->data=temp;
return true;
}
（5）按位序删除结点（带头结点）
- 删除节点，还是需要找到第i-1个结点。
- 然后再新建个q指向被删除结点，给删除节点数据赋值给e带回去。
- 随后p节点直接指向q节点后继即可。
代码如下：
bool wei_delete(linklist &l,int i,int &e)//因为e的值需要带回主函数去，所以加个&符号
{
if(i<1)
return false;
//找第i-1个结点
lnode* p=l;
int j=0;
while(p!=NULL&&j<i-1)
{
p=p->next;
j++;
}
//进行排错
if(p==NULL) //p结点若不存在，则i的位置不对
return false;
if(p->next=NULL)//p结点后为结点，则没有要删除的结点
return false;
lnode *q=p->next;//q指向p结点的后继结点，即需要删除的结点
e=q->data; //给删除节点中的数值，赋值给e
p->next=q->next;//直接把p结点连接到q结点的后继，绕过删除节点，相当于从单链表中剔除掉
free(q); //释放q结点
return true;
}
（6）按位查找
- 按照结点位置，返回该结点。
- lnode * getinsert(linklist &l,int i)——由于该函数为返回结点，所以类型为lnode*,形参为整个链表l，所需返回的第几个结点i。
代码如下：
lnode * getlist(linklist l,int i) //我所查找该位置的结点
{
if(i<0) //第0个结点为头结点，如果比头结点还靠前，则肯定不对，返回false
return false;
lnode *p; //定义结点指针p指向所需返回的结点
p=l; //让p初试位置为头结点处
int j=0;
while(p!=NULL && j<i)//因为需要返回第i个位置的结点，所以j<i
{
p=p->next;
j++;
}
return p;
}
这个就类似于之前按位插入中的查找第i-1个结点的操作，因此可以替换成如下：
bool insertlist(linklist &l,int i,int e)//带头结点 插入
{
if(i<1)
return false;
lnode* p;
p=getlist(l,i-1);//查找第i-1个结点，然后返回该节点，给p
houcha(p,e);
return true;
}
删除操作中也有
bool wei_delete(linklist &l,int i,int &e)//因为e的值需要带回主函数去，所以加个&符号
{
if(i<1)
return false;
lnode* p;
p=getlist(l,i-1);
if(p==NULL)
return false;
if(p->next=NULL)
return false;
lnode *q=p->next;
e=q->data;
p->next=q->next;
free(q);
return true;
}
（7）按值查找
- 给出数据域的值，查找链表中的结点有无一样的。
- lnode *getzhi(linklist &l,int e)——需要返回所查找数据域的结点，所以类型为lnode*
- 令p结点指针，指向第一个节点，依次往后扫描，看是否满足p->data==e,直到扫描到或扫描结束，最后返回p即可。
代码如下：
lnode *getzhi(linklist &l,int e)
{
lnode *p=l->next;//直接指向头结点的后继结点，即实际第一个结点
if(p==NULL)
return false;
while(p!=NULL&&p->data!=e)
{
p=p->next;
}
return p;
}
（8）求链表长度
- 类似于按值查找，从头结点开始，依次往后扫描，每扫一个节点，长度++，直到扫到NULL为止。
代码如下：
int lengthlist(linklist &l)
{
lnode *p=l;//掐头去尾，去中间，从头结点开始算
int len=0;
while(p!=NULL&&p->next!=NULL)//扫描到链尾为止
{
p=p->next;
len++;
}
return len;
}
