南航数据结构上机作业2---链表求交，拆分链表

45 阅读 0 评论 30 点赞

我是靠谱客的博主靓丽飞鸟，最近开发中收集的这篇文章主要介绍南航数据结构上机作业2---链表求交，拆分链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、调试成功程序及说明
1、
题目：
两个有序单向链表A,B（升序有序，均无重复元素）。请设计高效计算法求取两个链表的交集元素，A=common(A,B),要求处理后链表A降序有序，并且没有重复元素，链表B不变。请分析时间复杂度，要求空间复杂度为O©
算法思想：
首先，我们用指针pa1指向头节点A（这很重要，这决定了我们后面的插入方式），用pa指向链表A，pb指向链表B，然后在pa,pb不等于NULL(即)我们开始比较pa->data和pb->data。如果pa->data小于pb->data，我们就删除pa；如果pa->data大于pb->data，我们就对pb进行移动。相等的话，我们采用链表逆置是思路，进行插入操作，但是由于我们没有令 A->next=NULL，所以我们需要区分pa1是否为头节点。
由于题目要求空间复杂度为O©，所以我们采用内地求交的思路，然后加上链表逆置是思路相融合。

运行结果：
在这里插入图片描述

结果分析：
从结构==结果上来看，是非常正确的，我们测试的数据中，有pa的第一个就是交元素的例子，而且也运行正确了。我们来分析该算法的时间复杂度。我们不妨考虑插入最多的情况，若n<m,则A中的元素B中都有；若n>m,则B中的元素A中都有，此时插入最多，我们需要将A，B中的数据遍历一遍，并且每一次判断都要进行一次插入，需要m/n（取决于m,n大小）次,因此时间复杂度为O(m)或者O(n).
附源程序：

void common(LI *A,LI *B)
{
	LI *pa,*pa1;  //pa指向A的节点，pa1是pa的前继 
	LI *pb;       //pb为指向B的节点 
	pa1=A;        //pa1初始化为头节点 
	pa=A->next;   //pa初始化为A的第一个节点 
	pb=B->next;   //pb初始化为B的第一个节点 
	while(pa&&pb) //pa,pb有一个为NULL，即有一个到达末位时，退出循环 
	{
		if(pa->data < pb->data)      //当 pa->data < pb->data时，我们将节点pa删除掉 
		{
			pa1->next = pa->next;
			free(pa);
			pa = pa1->next;
		}
		else if(pa->data > pb->data) //当 pa->data > pb->data时，我们将节点pb向后移动，判断下一个节点pb->data和pa->data的关系 
			pb = pb->next;
		else
		{
			if(pa1==A)    //要判断 pa1是否为头节点，这决定了插入的方式，如果不做判断，会发生：当pa1为头节点，pa要指向自己了。 
			{
				pa1 = pa;
				pa = pa->next;
			}
			else
			{
				pa1->next = pa->next;
				pa->next = A->next;
				A->next = pa;
				pa = pa1->next;
			}
		}
	}
	if(pa)              //如果A中还有剩余，我们是不要的，先把pa1指向NULL；如果B中有剩余，那么就不用管了 
		pa1->next=NULL;
	while(pa)           //然后释放A中剩余元素 
	{
		pa1=pa->next;
		free(pa);
		pa=pa1;
	}
}

2、
题目：
设A={a1,b1,a2,b2,…,an,bn}为一单链表，设计算法将其就地拆分为两个链表，
使得A={a1,a2,…an},B={b1,b2,…,bn}，要求空间复杂度O©
算法思想：
由于这道题是要求拆分链表A，所以，我们只需要做一次遍历就可以了，用pa,pb来进行，分开给链表A和链表B，唯一需要注意的就是，在B的插入过程中，我们要判断是否为头节点。
运行结果：
在这里插入图片描述

结果分析：
运行结果非常正确，无论链表的数量是偶数，还是奇数，都是对的，我们甚至测试了A的节点个数为1，2的特殊情况，发现也是对的。因为我们遍历了链表A就做完了。因此时间复杂度为O(n)。
附源程序：

LI *splitlist(LI *A)
{
	LI *B;
	LI *pa,*pa1,*pb,*pb1; //pa是当前节点，pa1是pa的前驱，pb是pa的后继，pb1是pb的前驱 
	B = (LI*)malloc(sizeof(LI));   //动态生成一个头指针 
	B->next = NULL;                //让B为空指针 
	pa1 = A;                       //初始化节点pa1 
	pa = A->next;                  //初始化节点pa 
	pb1 = B; 
	while(pa)
	{
		pb = pa->next;
		if(pb)
		{
			pa->next = pb->next;
			pa1 = pa;
			pa = pa1->next;
			if(pb1 == B)   //判断是否为头节点
			{
				B->next = pb;
				pb->next = NULL;
				pb1 = pb;
			}
			else
			{
				pb1->next = pb;
				pb->next = NULL;
				pb1 = pb;
			}
		}
		else
			break;
	}
	return B;
}