[C语言、C++]数据结构作业：线性表合并_用c语言实现两个线性表的合并

1、（5分）完成基于顺序表的合并函数：MergeSeqList（SeqList &LA, SeqList LB）

要求该函数的时间复杂度为：O（LB.Length）

====main中测试：

1、建立LA,LB，元素分别为：1，2,3,4,5以及0,9,8,7

2、遍历LA,LB

3、合并LB到LA

4、打印LA

#include <iostream>
using namespace std;
typedef int ElemType;
typedef int Status;
#define MAXSIZE 100
#define INITSIZE 100
#define OK 1
#define ERROR 0
typedef struct {
    ElemType* elem;         //存储空间的基地址
    int length;             //当前长度
    int listsize;
} SqList;                   //顺序表的结构类型为SqList
Status InitList(SqList& L) {//分配
    L.elem = new ElemType[INITSIZE];
    if (!L.elem) {
        cout << "存储分配失败!" << endl;
        exit(1);
        return ERROR;
    }
    L.length = 0; L.listsize = INITSIZE;
}
Status Listinsert(SqList& L, int i, ElemType e) {//插入函数
    if (i < 1 || i > L.length + 1) return ERROR;
    if (L.length >= L.listsize) return ERROR;//老师说ListExtend()可以先不写
    //移动元素，对i=L.length+1，无须移动
    for (int j = L.length - 1; j >= i - 1; j--)
        L.elem[j + 1] = L.elem[j];
    L.elem[i - 1] = e; //实际插在数组第i-1个位置
    L.length++;
    return OK;
}
Status printList(SqList L)//遍历打印
{
    if (L.length == 0)
    {
        printf("线性表为空\n");
        return 0;
    }
    int i;
    for (i = 0; i < L.length; i++)
    {
        printf("编号为%d,元素值:elem[%d]=%d\n", i + 1, i, L.elem[i]);
    }
    printf("\n");
    return OK;
}
void MergeSeqList(SqList& LA, SqList LB) {//完成基于顺序表的合并函数：MergeSeqList（SeqList &LA, SeqList LB)
	int N = LA.length;//要求该函数的时间复杂度为：O（LB.Length）
	for (int i = 1; i <= Getlength(LB); i++) {
		int e = 0;
		GetElemSq(LB, i, e);
		Listinsert(LA, ++N, e);
	}
}
int main(){
	SqList LA;
	SqList LB;
	InitList(LA);
	InitList(LB);
	int i = 0;
	for (i = 1; i <= 5; i++) {
		Listinsert(LA, i, i);//1、建立LA,LB，元素分别为：1，2,3,4,5
	}
	Listinsert(LB, 1, 0);//以及0,9,8,7
	Listinsert(LB, 2, 9);
	Listinsert(LB, 3, 8);
	Listinsert(LB, 4, 7);
	printList(LA);//2、遍历LA,LB
	printList(LB);
	MergeSeqList(LA, LB);//3、合并LB到LA
	printList(LA);//4、打印LA
}

2、完成基于单链表的合并函数:MergeLinkList（LinkList &LA, LinkList LB）

====main中测试：

1、建立LA,LB，元素分别为：1，2,3,4,5以及0,9,8,7

2、遍历LA,LB

3、合并LB到LA

4、打印LA

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LinkNode {
	ElemType data;
	LinkNode* next;
}*LinkList;
void InitLinkList(LinkList& L) {
	LinkNode* s = new LinkNode;
	s->next = NULL;
	L = s;
}
void Traverse(const LinkList& L) {
	LinkNode* p = L->next;
	while (p) {
		cout << p->data << endl;
		p = p->next;
	}
}
void CreatHead(LinkList& L, int n) {
	L = new LinkNode; L->next = NULL;
	for (int i = 0; i < n; i++) {
		LinkNode* s = new LinkNode;
		cin >> s->data;
		s->next = L->next;
		L->next = s;
	}
}
void CreatRear(LinkList& L, int n) {
	L = new LinkNode;
	LinkNode* r = L;
	for (int i = 0; i < n; i++) {
		LinkNode* s = new LinkNode;
		cin >> s->data;
		r->next = s;
		r = s;
	}
	r->next = NULL;
}
 
int Insert(const LinkList& L, int i, ElemType e) {
	LinkNode* p = L; int j = 0;
	while (p && j < i - 1) {
		p = p->next; j++;
	}
	if (!p || i < 1) return 0; //i非法。
	LinkNode* s = new LinkNode;
	s->data = e;
	s->next = p->next; p->next = s;
	return 1;
}
 
void MergeLinkList(LinkList& LA, LinkList& LB) {//2、完成基于单链表的合并数:MergeLinkList（LinkList &LA, LinkList LB）
	LinkNode* p=LA->next;
	LinkNode* r = LB->next;
	while (p->next) {
		p = p->next;
	}
	p->next = r;
}
int main(){
	LinkList LA;
	LinkList LB;
	InitLinkList(LA);//1、建立LA,LB，
	InitLinkList(LB);
	CreatRear(LA, 5);//元素分别为：1，2,3,4,5
	CreatRear(LB, 4);//以及0,9,8,7
	Traverse(LA);//2、遍历LA
	cout << "=======================================================" << endl;
	Traverse(LB);//2、遍历,LB
	cout << "=======================================================" << endl;
	MergeLinkList(LA, LB);//3、合并LB到LA
	Traverse(LA);//4、打印LA
}