24.8.2数据结构|双链表

双链表 

1、定义结构：2个指针域、数据域

2、初始化：创建一个含有N个结点的带头结点双链表head

（双链表头结点的前驱与和尾节点的后继与置为空）

3、求表长：返回双链表head的长度

4、取元素：取出双链表head中第I个结点的值， I的取值范围是小于等于N大于等于1.

5、定位：返回双链表head中第一个值为X的节点的位置

6、删除：删除双链表head中的第i个节点

7、插入：在双链表head中第I个结点之前插入一个值为X的结点

8、输出：从两个方向输出双链表head中各节点的值

void fun(LinkList*head){
	LinkList*p,*q;
	int i;
	for(q=head;q->next!=NULL;q=q->next);
	p=head;
	while(p!=q){
		while(p->date<0)p=p->next;
		while(q->date>0)q=q->pre;
		if(p!=q){
			//交换
			int t;
			t=p->date;
			p->date=q->date;
			q->date=t;
		 
		}
	}
}
//把所有不小于零的节点放在所有值小于零的节点之前  

单向循环链表

 单向循环链表与单链表的结点类型完全相同差别仅在于算法中的循环条件不是判断P或P指向next是否为空而是判断它们是否等于头指针。

1、定义：结构体单向循环链表的类型与单向链表的类型一样

2、初始化：创建一个含有N个结点的带头结点单向循环链表head。

3、求表长：返回单向循环链表head的表长

4、取元素：取出单向循环链表head的第I个节点的元素值

5、定位：在单向循环head中查找第一个值为X的结点

6、删除：删除带头结点单向循环链表head中的第i个结点

7、插入：操作在带头结点单向循环链表head中的第二个结点之前插入一个值为X的结点

8、输出：带头结点增效循环列表hard中的各点的值

 头结点里边没有数据作为一个判断标准存在把。

例题

由N个已经按1，2，3，...，n编号的人围成一圈，从编号为1的人开始按1，2，3顺序循环报数，凡报到3者退出，最后只留一个人，问其编号是多少?（用带头结点单向循环链表实现）

自解：

int fun(LinkList *fhead,int n){
//用单向循环连表
 LinkList*p;
 p=head->next;
 int i=1;
 while(p!=NULL){
 	p=p->next;
 	i++;
 	if(i==2&&p->next!=NULL){
 		p->next=p->next->next;
 		i=0;
	 }
 }printf("%d\n",p->date);
 return 1;
}
 
应该对吧？？？

注意释放删除后的内存

课本是：（int n）只有n