链表

1.单链表拆分成两个二个单链表

要求：将一个带头结点的单链表
L=(a1, b1, a2, b2, …, an, bn)拆分成两个带头结点的单链表L1和L2，L1=(a1, a2,…,an), L2 = (bn, bn-1, …,b1).

• 算法思想
  split函数实现拆分

  void Split(Lnode *L, Lnode *L1, Lnode *L2)
  {
      Lnode *p = L->next, *q, *r;
      r = L1; 
      while(p)            //尾插法得L1，头插法得L2 
      {
  	    r->next = p; // 将p(valude值为ai)插入L1 
  	    r = p;
  	    p = p->next; //p移到下一个结点(value值为bi) 
  	    q = p->next;//头插法会修改p的next域，用q保存p的后继结点 
  	    p->next = L2->next;   
      	L2->next = p;
      	p = q;	    //p重新指向ai+1的结点 
     	}
      r->next = NULL; 
  }

DispList函数输出单链表

void DispList(Lnode *L)
{
    Lnode *p = L->next;
    while(p)
    {
	    printf("%d ", p->value);
	    p = p->next;
	}
   	printf("\n");
}

——————完整代码——————

#include <stdio.h>
#include <stdlib.h>

typedef struct lnode Lnode;
struct lnode
{
	int value;
	Lnode *next;
};
void Split(Lnode *L, Lnode *L1, Lnode *L2)
{
	Lnode *p = L->next, *q, *r;
	r = L1; 
	while(p)            //尾插法得L1，头插法得L2 
	{
		r->next = p; // 将p(valude值为ai)插入L1 
		r = p;
		p = p->next; //p移到下一个结点(value值为bi) 
		q = p->next;//头插法会修改p的next域，用q保存p的后继结点 
		p->next = L2->next;   
		L2->next = p;
		p = q;	    //p重新指向ai+1的结点 
	}
	r->next = NULL; 
}
void DispList(Lnode *L)
{
	Lnode *p = L->next;
	while(p)
	{
		printf("%d ", p->value);
		p = p->next;
	}
	printf("\n");
}
int main()
{
	Lnode *L = (Lnode *)malloc(sizeof(Lnode)), 
	*L1 = (Lnode *)malloc(sizeof(Lnode)), 
	*L2 = (Lnode *)malloc(sizeof(Lnode));
	L->next = NULL;
	L1->next = NULL;
	L2->next = NULL;
	Lnode *current = L;
	int i = 0;
	while(i<1)
	{
		Lnode *p = (Lnode *)malloc(sizeof(Lnode));
		scanf("%d", &p->value);
		current->next = p;
		current = p;
		if(getchar() == '\n')
			i++;
	}
	current->next = NULL;
	Split(L, L1, L2);
	DispList(L1);
	DispList(L2);
	return 0;
}

——————运行结果——————

2.判断循环双链表中数据结点(含两个以上的结点)是否对称

• 算法思想
  P从左到右扫描L，q从右到左扫描L，然后循环，直到p=q 或 p=q->prior.
  IsSymm函数扫描L.

  int IsSymm(DLnode *L)
  {
  	DLnode *p = L->next;	//p指向首结点	
  	DLnode *q = L->prior;	//q指向尾结点 
  	while(p->value == q->value)    //当结点值不一样，退出循环 
  	{
  	    if(p==q || p->prior == q)  //结点数为奇数||结点数为偶数 
  			return 1;
  		p = p->next;
  		q = q->prior;
  	}
  	return 0;
  }

——————完整代码——————

#include <stdio.h>
#include <stdlib.h>

typedef struct Dlnode DLnode;
struct Dlnode
{
	int value;
	DLnode *prior;
	DLnode *next;
};
int IsSymm(DLnode *L)
{
	DLnode *p = L->next;	//p指向首结点	
	DLnode *q = L->prior;	//q指向尾结点 
	while(p->value == q->value)    //当结点值不一样，退出循环 
	{
	    if(p==q || p->prior == q)  //结点数为奇数||结点数为偶数 
			return 1;
		p = p->next;
		q = q->prior;
	}
	return 0;
}
int main()
{
	DLnode *L = (DLnode *)malloc(sizeof(DLnode));
	L->next = L->prior = NULL;
	int i = 0;
	DLnode *r = L, *p; 
	while(i<1)
	{
		p = (DLnode *)malloc(sizeof(DLnode));
		scanf("%d", &p->value);
		r->next = p;
		p->prior = r;       // 双链表尾插法存入L 
		r = p;                    
		if(getchar() == '\n')
			i++;
	}
	r->next = L;
	L->prior = r;
	if(IsSymm(L))
		printf("该循环双链表对称\n");
	else
		printf("该循环双链表不对称\n");		
	return 0;
}

——————运行结果——————