[数据结构与算法]链表删除及插入

• 题目：设指针la和lb分别指向两个无头结点单链表中的首元结点，试设计算法，从表la中删除自第i个元素起共len个元素，并将它们插入表lb的第j个元素之后

1. 构造结构体

typedef struct node
{
	int data;   //数据
	struct node *next;
}LNode,*LinkList;    //单链表结构体

• 通过尾插法构造链表，并返回所构造的链表

LinkList CreatList()    //尾插法
{
	LinkList H = (LinkList)malloc(sizeof(LNode));
	H -> next = NULL;
	LNode *s,*r = H;
	int x;
	//r -> count = 1;
	printf("请输入第一个数据：");
	scanf("%d",&x);
	while(x != -1)
	{
		s = (LinkList)malloc(sizeof(LNode));
		s -> data = x;
		r -> next = s;
		r = s;
		//r -> count ++;
		printf("请输入下一个数据,若需要结束输入，则输入-1:");
		scanf("%d",&x);
	}
	r -> next = NULL;
	return H;
}

• 打印链表函数

void PrintList(LinkList L)     //打印链表
{
	L = L -> next;
	while(L != NULL)
	{
		printf("%d  ",L -> data);
		L = L -> next;
	}
}

• 查找第i个结点

LinkList Listsreach(LinkList L,int i)      //找到第i个结点
{
	LNode *p = L;
	int j = 0;
	while(p -> next != NULL && j < i)
	{
		p = p -> next;
		j ++;
	}
	//PrintList(L);
	if(j == i) return p;
	else return NULL;
}

• 保存删除的数据

LinkList SaveDelete(LinkList L,int i,int len)    //保存删除的数据
{
	LinkList p,q;
	LinkList delete = init();
	LNode *s,*r;
	p = Listsreach(L,i - 1);
	delete = p ;
	s = p -> next;
	p -> next = delete -> next;
	r = Listsreach(delete,len);
	r -> next = NULL;
	return delete;
}

• 删除数据

LinkList ListDelete(LinkList L,int i,int len)    //删除指定数据
{
	LinkList p,q;
	int j;
	p = Listsreach(L,i - 1);
	for(j = i;j < i + len;j ++)
	{
		q = p -> next;
		p -> next = q -> next;
		free(q);
	}
	return L;
}

• 插入数据

LinkList ListInsert(LinkList L,int j,LinkList delete,int len)   //插入数据
{
	LNode *p,*s,*r;
	int i;
	p = Listsreach(L,j);
	s = p -> next;
	p -> next = delete -> next;
	r = Listsreach(delete,len);
	r -> next = s;
	// PrintList(L);
	return L;
}

• 拷贝链表

LinkList  copyNode(LinkList L)    //链表拷贝
{
	LinkList  Lnew  = init();    //新链表初始化
	LinkList  pb = Lnew ;    //新链表还没有值,指向头指针 
	LinkList  pa = L->next;
	while(pa != NULL){
		LinkList n =(LinkList)malloc(sizeof(LNode));    //为新节点开辟内存空间
		n->data = pa->data;    //尾插法
		n->next = NULL;
		pb->next = n;   //保证指针始终指向最后一个节点
		pb = pb->next;
		pa = pa->next;		
	} 
	return Lnew ;
}

• 源代码

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

typedef struct node
{
	int data;   //数据
	struct node *next;
}LNode,*LinkList;    //单链表结构体

LinkList CreatList()    //尾插法
{
	LinkList H = (LinkList)malloc(sizeof(LNode));
	H -> next = NULL;
	LNode *s,*r = H;
	int x;
	//r -> count = 1;
	printf("请输入第一个数据：");
	scanf("%d",&x);
	while(x != -1)
	{
		s = (LinkList)malloc(sizeof(LNode));
		s -> data = x;
		r -> next = s;
		r = s;
		//r -> count ++;
		printf("请输入下一个数据,若需要结束输入，则输入-1:");
		scanf("%d",&x);
	}
	r -> next = NULL;
	return H;
}

void PrintList(LinkList L)     //打印链表
{
	L = L -> next;
	while(L != NULL)
	{
		printf("%d  ",L -> data);
		L = L -> next;
	}
}

LinkList Listsreach(LinkList L,int i)      //找到第i个结点
{
	LNode *p = L;
	int j = 0;
	while(p -> next != NULL && j < i)
	{
		p = p -> next;
		j ++;
	}
	//PrintList(L);
	if(j == i) return p;
	else return NULL;
}

LinkList init()    //创立头指针
{
	LinkList head =(LinkList)malloc(sizeof(LNode));
	head->data = 0;
	head->next = NULL;
	return head;
}

LinkList SaveDelete(LinkList L,int i,int len)    //保存删除的数据
{
	LinkList p,q;
	LinkList delete = init();
	LNode *s,*r;
	p = Listsreach(L,i - 1);
	delete = p ;
	s = p -> next;
	p -> next = delete -> next;
	r = Listsreach(delete,len);
	r -> next = NULL;
	return delete;
}

LinkList ListDelete(LinkList L,int i,int len)    //删除指定数据
{
	LinkList p,q;
	int j;
	p = Listsreach(L,i - 1);
	for(j = i;j < i + len;j ++)
	{
		q = p -> next;
		p -> next = q -> next;
		free(q);
	}
	return L;
}

LinkList ListInsert(LinkList L,int j,LinkList delete,int len)   //插入数据
{
	LNode *p,*s,*r;
	int i;
	p = Listsreach(L,j);
	s = p -> next;
	p -> next = delete -> next;
	r = Listsreach(delete,len);
	r -> next = s;
	// PrintList(L);
	return L;
}

LinkList  copyNode(LinkList L)    //链表拷贝
{
	LinkList  Lnew  = init();    //新链表初始化
	LinkList  pb = Lnew ;    //新链表还没有值,指向头指针 
	LinkList  pa = L->next;
	while(pa != NULL){
		LinkList n =(LinkList)malloc(sizeof(LNode));    //为新节点开辟内存空间
		n->data = pa->data;    //尾插法
		n->next = NULL;
		pb->next = n;   //保证指针始终指向最后一个节点
		pb = pb->next;
		pa = pa->next;		
	} 
	return Lnew ;
} 

void main()
{
	LinkList La,Lb,Lanew,Lbnew;
	LinkList delete;
	int i,j,len;
	printf("请输入单链表La的数据");
	La = CreatList();
	printf("请输入单链表Lb的数据");
	Lb = CreatList();
	Lanew = copyNode(La);
	printf("请输入i:");
	scanf("%d",&i);
	printf("请输入len:");
	scanf("%d",&len);
	delete = SaveDelete(La,i,len);
	printf("删除的链表数据：");
	PrintList(delete);
	printf("\n");
	printf("此时链表La数据为：");
	Lanew = ListDelete(Lanew,i,len);
	PrintList(Lanew);
	printf("\n");
	printf("请输入j:");
	scanf("%d",&j);
	printf("此时链表Lb的数据为：");
	Lbnew = ListInsert(Lb,j,delete,len);
	PrintList(Lb);
}