526互联

第二章 线性表 - 线性表的合并

发布时间 2023-09-21 15:05:15作者: ww0809

2.7 线性表的应用

2.7.1 线性表合并

2.7.2 有序表合并

  1. 顺序有序表

    void MergeList_Sq(SqList LA, SqList LB, SqList &LC) {
	LC.length = LA.length + LB.length;
	LC.elem = new ElemType[LC.length]; // 给新表分配数组空间
	pc = LC.elem;
	pa = LA.elem;
	pb = LB.elem;
	pa_last = LA.elem + LA.length - 1;
	pb_last = LB.elem + LB.length - 1;
	while(pa <= pa_last && pb <= pb_last) { // 两表都未到达表尾
		if(*pa < *pb) *pc++ = *pa++;
		else *pc++ = *pb++;
	}
	while(pa <= pa_last) *pc++ = *pa++; // LB到达表尾
	while(pb <= pb_last) *pc++ = *pb++; // LA到达表尾
}

    时间复杂度为O(m + n), 空间复杂度为O(m + n) 【m， n分别为两表的长度】

  2. 链表有序表

    非递减链表A，B，合成一个非递减链表C

    void MergeList(LinkList &LA, LinkList &LB, LinkList &LC) {
	pa = LA -> next;
	pb = LB -> next;
	LC = LA; // LA的头结点作为LC的头结点
	pc = LC;
	while(pa && pb) {
		if(pa -> data <= pb -> data) {
			pc -> next = pa; // pa指的结点连到pc后面
			pc = pa;
			pa = pa -> next;
		}
		else {
			pc -> next = pb;
			pc = pb;
			pb = pb -> next;
		}
	}
		pc -> next = pa ? pa : pb; // 非空表的剩余部分链接到pc所指结点之后
		delete LB; // 释放LB头结点
}

    时间复杂度为O(m + n), 空间复杂度为O(1) 【因为不需要建立新的结点空间，只需要将原表结点间的连接关系解除再重新建立新的关系】