C++ 顺序表和单链表的二路归并思想（详解+示例代码）

CSDN话题挑战赛第2期
参赛话题：学习笔记

有序顺序表的二路归并

我们有两个顺序表A和B，他们都是有序递增的，我们想要把这两个顺序表保持原有的递增顺序合成一个新的顺序表C

void merge_list(sqList& list1,sqList& list2,sqList& DstList)
{
	int A=0;
	int B=0;
	int Dst=0;    //合并后的顺序表的下标位置
	while (A<list1.length && B<list2.length)
	{
		if (list1.data[A]<list2.data[B])
		{
			//当A表元素比B表元素小 时，把这个元素添加到C表上面，并且递增A表的位置
			DstList.data[Dst++]=list1.data[A];
			A++;
		}
		else
		{
			//当B表的元素比A表的元素大或者等于 时，把这个元素添加到C表上，并且递增B表的位置
			DstList.data[Dst++]=list2.data[B];
			B++;
		}
	}
	//当遍历完A表或者B表后，一定还有一个表没有遍历完毕，接着在连接剩下来的元素
	while (A<list1.length)
	{
		DstList.data[Dst++]=list1.data[A++];
	}
	while (B<list2.length)
	{
		DstList.data[Dst++]=list2.data[B++];
	}
	DstList.length=Dst++;
}

本算法的空间复杂度为O（1），时间复杂度是O（n+m），n和m分别是A表和B表的长度。

测试：

合并相同的元素

与上一题的思路一致，使用二路归并思想找到二表中相同的元素，把此元素添加到C表上面。

//两个顺序表的公共元素组成新顺序表
void CommElem_list(sqList& list1,sqList& list2,sqList& DstList)
{
	int A = 0;
	int B = 0;
	int Dst = 0;
	while (A < list1.length && B < list2.length)
	{
		if (list1.data[A] < list2.data[B])
		{
			A++;
		}
		else if (list1.data[A] > list2.data[B])
		{
			B++;
		}
		else
		{
			//两个元素相同，可以放入到新表中,最后，两个表的位置同时往后面移动
			DstList.data[Dst++] = list1.data[A];
			A++;
			B++;
		}
	}
	DstList.length = Dst;
}

测试：

查找第k小的元素

描述：有两个顺序表A和B，他们都是有序递增的，分别含有n和m个元素，并且A表和B表的元素互不相同，设计一个算法找出n+m中第k小的元素，并用参数e表示找到的那个第k小的元素。

//找出第pos小的元素
void Find_Pos_Little_Elem(sqList& list1,sqList& list2,int pos,Element& elem)
{
#define INF 32767
	int A=0,B=0;
	//pos越界
	if (pos<1 || pos>list1.length+list2.length)
	{
		cout<<"没有找到!\n"<<endl;
		return;
	}
#if 1
	while (A < list1.length && B < list2.length)
	{
		pos--;
		if (list1.data[A] < list2.data[B])
		{
			if (pos == 0)
			{
				elem = list1.data[A];
				return;
			}
			A++;
		}
		else
		{
			if (pos == 0)
			{
				elem = list2.data[B];
				return;
			}
			B++;
		}
	}
	//如果遍历完A或者B表后没有找到元素，则说明第pos个位置的元素不在A或B表中，则根据位置关系可以直接确定此位置元素
	// A: 1 2 6 8 10
	// B: 3 4 5 7 11  
	/*
	pos=6  B： 0+1-1
	*/
   //已经找完了一个表，不在这个表里面，则必在另一个表里面
	if (A < list1.length)
	{
		elem = list1.data[A + pos - 1];
	}
	if (B < list2.length)
	{
		elem = list2.data[B + pos - 1];
	}
}

测试：

---

另一种简化的做法：我们注意到两个表肯定会有一个先遍历完，然后再去遍历另一个表，或者就只遍历一个表，我们可以想办法让他们都在一个地方完成，不用再出去完成了。

我们使用了INT_MAX ，如果某一个表已经遍历完成了，但是还没有结束，我们直接遍历另一个表就行了，怎么使用呢，直接把INT_MAX与另一个表比较，这样每一次都会比较我们还没有遍历完的表：

/*
简化版本
*/
	while (true)
	{
		pos--;
		//遍历完A表后没有找到，则直接让A表的元素大于B表的所有元素，这样就可以直接进入else继续判断
		int _list1=((A<list1.length)?list1.data[A]:INF);
		//遍历完B表后没有找到，则直接让B表的元素大于A表的所有元素，这样就可以直接进入if继续判断
		int _list2=((B<list2.length)?list2.data[B]:INF);
		if (_list1<_list2)
		{
			if (!pos)
			{
				elem=_list1;
				return;
			}
			A++;
		}
		else
		{
			if (!pos)
			{
				elem=_list2;
				return;
			}
			B++;
		}
	}

这两种做法的时间复杂度都是O（n），空间复杂度复杂度为O（1）

---

单链表的二路归并

把两个递增的单链表合并成一个递增的有序单链表C，要求：不能销毁原来的单链表结构：

//有序单链表的二路归并: 两个递增链表合成一个递增链表   销毁原链表
void Merge_But_Destroy(sqListNode* list1,sqListNode* list2, sqListNode*& listDst)
{
    sqListNode* p1=list1->Next,*p2=list2->Next,*pTail=nullptr;
    pTail = listDst;
    sqListNode* pNew = nullptr;

    while (p1 && p2)
    {
        if (p1->data < p2->data)
        {
            sqListNode* pNew = CreateNode(p1->data);
            pTail->Next = pNew;
            pTail = pNew;
            p1 = p1->Next;
        }
        else
        {
            sqListNode* pNew = CreateNode(p2->data);
            pTail->Next = pNew;
            pTail = pNew;
            p2 = p2->Next;
        }
    }
    while (p1)
    {
        //p1链表不为空
        pNew = CreateNode(p1->data);
        pTail->Next = pNew;
        pTail = pNew;
        p1 = p1->Next;
    }
    while (p2)
    {
        //p2链表不为空
        pNew = CreateNode(p2->data);
        pTail->Next = pNew;
        pTail = pNew;
        p2 = p2->Next;
    }
}

算法的时间复杂度：O（n+m）,算法的空间复杂度为O（n+m）
当然了这是不销毁原链表的深度复制的做法，如果你想要空间复杂度为O（1），则只能借用A链表和B链表的节点来重新链表产生C节点，这样就不会有新产生的空间，不过由于A和B的节点被重构，再合成一个C表后，A链表和B链表也就被销毁了。

---

例题：求多项式的和

有两个多项式，例如：

5x^2 + 6x^5 - 8x^4 +4x^ 3
2x^2 + 9x^5 + 8x^4 +4x^ 3

计算他们和：

15x^5 + 8x^3 + 7x^2

这里也是用到了二路归并的思想，首先要确保链表一定是有序递增的，如果A表比B表的元素小，则A表上，A表递增；如果B表比A表的元素的元素小，则B表上，B表递增。

我们首先要创建多项式的链表，对于创建，我们要根据他们的指数和系数来创建链表，并要在Merge之前确保他们是已经递增的链表了，然后我们对其指数的大小进行二路归并，相同指数的多项式系数相加，然后再继续遍历多项式的下一项，直到最后某一个多项式处理完了，另一项还有剩余，再处理剩下的多项式的项 ：

void Merge(LinkNode* ha, LinkNode* hb, LinkNode*& list)
{
	LinkNode* pA = ha->next;
	LinkNode* pB = hb->next;
	
	InitLink(list);
	LinkNode* pList = list;
	LinkNode* pNew = nullptr;
	//二路归并
	while (pA && pB)
	{
		if (pA->exp < pB->exp)
		{
			pNew = CreateLinkNode(pB->coef, pB->exp);
			//尾插法连接
			pList->next = pNew;
			pList = pNew;
			pB = pB->next;
		}
		else if (pA->exp > pB->exp)
		{
			pNew = CreateLinkNode(pA->coef, pA->exp);
			//尾插法连接
			pList->next = pNew;
			pList = pNew;
			pA = pA->next;
		}
		else
		{
			//相等：多项式相加
			coefType coef = pA->coef + pB->coef;
			if (coef)
			{
				pNew = CreateLinkNode(coef, pA->exp);
				pList->next = pNew;
				pList = pNew;
			}
			pA = pA->next;
			pB = pB->next;
		}
	}
	if (pB)
	{
		pA = pB;
	}
	while (pA)
	{
		pNew = CreateLinkNode(pA->coef, pA->exp);
		pList->next = pNew;
		pList = pNew;
		pA = pA->next;
	}
}

运行结果如下：

注意：这道题还有较多的细节与知识点，我就不多说了，重点是让大家理解二路归并的思路。

---

如果想获取本节的所有源码和单链表和顺序表的操作大全（共计千行，包含了所有的基本操作），还有多项式的操作源码，访问我们github免费获取：
Github 单链表顺序表的操作模板，直接套就行，多项式操作源码大全

祝大家学习愉快！！！！