快捷導(dǎo)航

C++實現(xiàn)線性表有序表的合并方式(順序表實現(xiàn)and鏈表實現(xiàn))

更新時間：2024年04月23日 11:06:59 作者：Daydreamer_cl

這篇文章主要介紹了C++實現(xiàn)線性表有序表的合并方式(順序表實現(xiàn)and鏈表實現(xiàn)),具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

一、順序表實現(xiàn)

#include<iostream>
using namespace std;
#define MAXSIZE 100 //定義最大存儲空間
 
//順序表的定義
struct SqList
{
	int* Elme; //動態(tài)數(shù)組
	int Length; //元素個數(shù)
 
};
 
//初始化
bool initList_Sq(SqList& L)
{
	L.Elme = new int[MAXSIZE]; //為順序表分配空間
	if (!L.Elme)
	{
		exit(0); //分配失敗退出系統(tǒng)
	}
	L.Length = 0; //空表長度為0
	return true; //分配成功返回1
}
 
//插入
bool Listinsert_Sq(SqList& L, int i, int e)
{
	if (i < 1 || i > L.Length + 1) //判斷輸入的i釋放合法
	{
		return false;
	}
 
	if (L.Length == MAXSIZE) //判斷空間是否已滿
	{
		return false;
	}
 
	for (int j = L.Length - 1; j >= i - 1; j--)
	{
		L.Elme[j + 1] = L.Elme[j]; //將插入位置及之后的元素后移
	}
	L.Elme[i - 1] = e; //將元素e放入位置i
	L.Length++; //表長加一
	return true;
 
}
 
//遍歷
void ListPrint_Sq(SqList L)
{
	for (int j = 0; j < L.Length; j++)
	{
		cout << L.Elme[j] << " ";
	}
	cout << endl;
}
 
//線性表有序表的合并
void MergeList_Sq(SqList La, SqList Lb, SqList& Lc)
{
	//指針pa,pb,pc的初值分別指向兩個表的第一個元素
	int* pa = La.Elme;  
	int* pb = Lb.Elme;
	Lc.Length = La.Length + Lb.Length; //新表長度等于兩表之和
	Lc.Elme = new int[Lc.Length]; //為新表分配存儲空間
	int* pc = Lc.Elme; 
	//pa_last、pb_last分別指向表中最后一個元素
	int *pa_last = &La.Elme[La.Length - 1];
	int* pb_last = &Lb.Elme[Lb.Length - 1];
 
	//判斷兩表是否為空，或當(dāng)其中一表摘取完，則停止循環(huán)
	while (pa <= pa_last && pb <= pb_last) 
	{
		if (*pa <= *pb) //依次摘取兩表中值較小的結(jié)點
		{
			*pc++ = *pa++;
		}
		else
		{
			*pc++ = *pb++;
		}
	}
 
	//如果條件為真，表明Lb表已經(jīng)到達表尾，將La中剩余元素加入Lc
	while (pa <= pa_last)
	{
		*pc++ = *pa++;
	}
 
	//如果條件為真，表明La表已經(jīng)到達表尾，將Lb中剩余元素加入Lc
	while (pb <= pb_last)
	{
		*pc++ = *pb++;
	}
 
}
 
int main()
{
	SqList La; //創(chuàng)建線性表La
	initList_Sq(La); //初始化
	//創(chuàng)建數(shù)組并把數(shù)組中元素插入到La中
	int arr1[3] = { 1,7,8 }; 
	for (int i = 1; i <= 3; i++)
	{
		Listinsert_Sq(La, i, arr1[i - 1]);
	}
	cout << "合并前La中元素：" << endl;
	ListPrint_Sq(La); //遍歷La
 
	SqList Lb;//創(chuàng)建線性表Lb
	initList_Sq(Lb); //初始化
	//創(chuàng)建數(shù)組并把數(shù)組中元素插入到Lb中
	int arr2[6] = { 2,4,6,8,10,11 };
	for (int i = 1; i <= 6; i++)
	{
		Listinsert_Sq(Lb, i, arr2[i - 1]);
	}
	cout << "合并前Lb中元素：" << endl;
	ListPrint_Sq(Lb); //遍歷La
 
	SqList Lc;
	MergeList_Sq(La, Lb, Lc); //合并La、Lb到Lc中
	cout << "合并后Lc中元素：" << endl;
	ListPrint_Sq(Lc); //遍歷Lc
 
 
	system("pause");
	return 0;
}

二、鏈表表實現(xiàn)

#include<iostream>
using namespace std;
 
 
//結(jié)點
struct Lnode
{
	int Data; //數(shù)據(jù)域
	Lnode* Next; //指針域
};
 
typedef Lnode* LinkList; //將LinkList定義為Lnode*類型
 
//初始化
void Listinit_L(LinkList& L)
{
	L = new Lnode;
	L->Next = NULL;
}
 
//插入
bool Listinsert_L(LinkList& L, int i, int e)
{
	Lnode* p = L;
	int j = 0;
	while (p && j < i - 1) //利用循環(huán)找到i-1的結(jié)點
	{
		p = p->Next;
		++j;
	}
 
	if (!(p) || j > i - 1)//判斷輸入的i是否合法
	{
		return false;
	}
	else
	{
		Lnode* s = new Lnode; //創(chuàng)建新結(jié)點s
		s->Data = e; //將輸入的元素e存入s的數(shù)據(jù)域
		s->Next = p->Next; //s指向第i個結(jié)點
		p->Next = s; //i-1結(jié)點指向s地址
		return true;
	}
 
}
 
//打印
void ListPrint_L(LinkList L)
{
	Lnode* p = L->Next; //p指向第一個元素
	while (p)
	{
		cout << p->Data << " ";
		p = p->Next;
	}
	cout << endl;
}
 
 
//有序表的合并
void MergeList_L(LinkList La, LinkList Lb, LinkList& Lc)
{
	Lnode* pa = La->Next;//pa指向La中第一個元素
	Lnode* pb = Lb->Next;//pb指向Lb中第一個元素
	Lnode* pc = Lc = La;//使用La的頭結(jié)點作為Lc的頭結(jié)點
	while (pa && pb) //pa或pb為空時停止循環(huán)
	{
		//判斷pa的值是否小于等于pb的值，為真插入pa的值，不為真插入pb的值
		if (pa->Data <= pb->Data) 
		{
			pc->Next = pa; 
			pc = pa;
			pa = pa->Next;
		}
		else
		{
			pc->Next = pb;
			pc = pb;
			pb = pb->Next;
		}
	}
 
	pc->Next = pa ? pa : pb; //利用三目運算插入pa或pb中剩余內(nèi)容
	delete Lb; //釋放Lb頭結(jié)點
}
 
int main()
{
	//1.創(chuàng)建單鏈表La
	LinkList La;
	Listinit_L(La); //初始話
	//將數(shù)組中的數(shù)據(jù)插入La
	int arr1[3] = { 1,7,8 };
	for (int i = 1; i <= 3; i++)
	{
		Listinsert_L(La, i, arr1[i-1]);
	}
	cout << "合并前La中的數(shù)據(jù)為：" << endl;
	ListPrint_L(La); 
 
 
	//2.創(chuàng)建單鏈表Lb
	LinkList Lb;
	Listinit_L(Lb); //初始話
	//將數(shù)組中的數(shù)據(jù)插入Lb
	int arr2[6] = {2,4,6,8,10,11};
	for (int i = 1; i <= 6; i++)
	{
		Listinsert_L(Lb, i, arr2[i - 1]);
	}
	cout << "合并前Lb中的數(shù)據(jù)為：" << endl;
	ListPrint_L(Lb);
 
	//3.創(chuàng)建Lc，將La與Lb中的值合并到Lc
	LinkList Lc;
	MergeList_L(La, Lb, Lc);
	cout << "合并后Lc的值為：" << endl;
	ListPrint_L(Lc);
 
 	
 
 
	system("pause");
	return 0;
}