[数据结构与算法]单链表。。

一、单链表的结点

在单链表中，假设每个结点的类型都用JieDian表示，数据域用data表示，指针域用next表示，JieDian类型声明如下

typedef struct JieDian
{
	int data;
	struct JieDian *next;
}JieDian;

二、单链表的插入删除操作

假设有结点p1，p2，p1指向p2，现要插入s结点在p1，p2中间，那么绝对不能直接 让 p1->next=s 然后s->next=p1->next，因为此时的p1->next已经不指向p2，正确的如下

s->next=p1->next;
p->next=s;

假如有结点p1，p2，p3，p1指向p2，p2指向p3，现要删除p2结点那么直接让p1指向p3便可，如果有需要可以新建一个p4来保存p2的指向 代码如下

p4=p2->next;
p1->next=p2->next;
free(q)

三、单链表的头尾插法

1.头插法
想法为让新建的结点指向表头结点的指向，再让表头节点指向新建的结点 代码如下

L->next=NULL;
s=(JieDian *)malloc(sizeof(JieDian));
s->next=L->next;
L->next=s;

这样的话新建的s结点指向的就为上一个结点，s就一直为头结点，使后插入的结点反而排前面，输入1，2，3，4，5 如果输出应为5，4，3，2，1。
2.尾插法
想法为让表头结点指向新建结点，再让表头节点等于新建结点 代码如下

s=(JieDian *)malloc(sizeof(JieDian));
L->next=s;
L=s;

这样的话新建的s就被上一个新建的结点指向，s就一直为尾结点，输入1，2，3，4，5 如果输出应为5，4，3，2，1。

四、单链表应用举例

假设有一个带头结点的单链表L={a1，b1，a2，b2，…，an，bn}。设计一个算法将其拆分成两个带头结点的单链表L1和L2：　L1={a1，a2，…，an}，L2={bn，bn-1，…，b1}
要求L1使用L的头结点。

分析将L分成L1和L2两个表，并且L2内容是倒置的可知L1应为尾插法插入，L2应为头插法插入，又分析必须遍历取出L中的元素，假设p=L再从p开始遍历，由于p指向的元素要插入L1或者L2，p本身会发生改变从而找不到后继元素，于是可以新建一个q，让q=p->next ，再让p=q，这样问题就得到解决
代码如下

	L1=L;//L1要用L的头结点
	yoxi *p,*q,*r;
	r=L1;//保留头结点L1不被丢失
	p=L1->next;//p指向L的第一个节点
	while(p)
	{
		r->next=p;
		r=p;//尾插法插入元素
		p=p->next;//p指向下一个元素
		q=p->next;//q储存p的下一个元素
		p->next=L2->next;
		L2->next=p;//头插法插入元素
		p=q;//p再次指向p后面的元素
	}
	r->next=NULL;