数据库结构笔记--线性表的合并
线性表合并
问题描述：
问题分析：
可以利用两个线性表 LA 和 LB 分别表示集合A和 B (即线性表中的数据元素为集合中的成
员）， 这样只需扩大线性表 LA, 将存在千 LB-中而不存在千 LA 中的数据元素插入到 LA 中去。
只要从 LB 中依次取得每个数据元素， 并依值在 LA 中进行查访， 若不存在， 则插入之。
【算法步骤】
-
分别获取 LA表长 m和 LB 表长n。
-
从 LB 中第 1 个数据元素开始， 循环n次执行以下操作：
? 从 LB 中查找第 i 个数据元素赋给 e;
? 在 LA 中查找元素 e, 如果不存在， 则将 e 插在表LA 的最后。
c语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct node{
int number;
struct node * next;
}Node,*LinkList;
//创建单链表,尾插法
LinkList initLink(){
LinkList head=(LinkList)malloc(sizeof(Node));//创建头节点
LinkList temp=head;//声明一个指针，用于遍历
LinkList p;
printf("链表初始化，输入0结束:\n");
int num;
while(1){
scanf("%d",&num);
fflush(stdin); //清空缓存
if (num==0) return head;//判断是否停止
p =(LinkList)malloc(sizeof(Node));
p->number=num;
p->next=NULL;
temp->next=p;
temp=p;
}
}
//遍历列表
void travelList(LinkList pNode){
LinkList temp=pNode;//用于遍历
int num;
while(temp->next){
temp=temp->next;
num=temp->number;
printf("%d\n",num);
}
}
//获取表长
int lenList(LinkList pNode){
LinkList temp=pNode;
int len=0;
while(temp->next){
temp=temp->next;
len++;
}
return len;
}
//查找函数，判断元素是否在链表中
bool search(LinkList pNode,int elem){
LinkList temp=pNode;
bool isExist=false;
while(temp->next){
temp=temp->next;
if (elem==temp->number) isExist=true;
}
return isExist;
}
//在链表尾部插入数据
void insert(LinkList pNode,int elem){
LinkList target,p;
for(target=pNode;target->next!=NULL;target=target->next) ;//找到最后一个节点
p=(LinkList)malloc(sizeof(Node));
p->next=NULL;
p->number=elem;
target->next=p;
}
//合并链表
void mergeList(LinkList La, LinkList Lb){
//用到两次遍历。一次时遍历lb表，取出每个元素然后和a表进行查找是否存在
//需要用一个查找函数
LinkList temp=Lb;
int elem;
while(temp->next){
temp=temp->next;
elem=temp->number;
if (search(La,elem)){//如果此元素存在La里
continue;
}else{//如果不存在，则进行连表插入
//再链表la尾部插入数据
insert(La,elem);
}
}
}
int main(){
Node *La,*Lb;//两个链表
printf("初始化la\n");
La=initLink();
printf("初始化后的链表La\n");
travelList(La);
n=lenList(La);
printf("La链表长度为：%d\n",n);
printf("初始化lb\n");
Lb=initLink();
printf("初始化后的链表Lb\n");
travelList(Lb);
n=lenList(Lb);
printf("Lb链表长度为：%d\n",n);
mergeList(La,Lb);
printf("合并后的来链表为\n");
travelList(La);
}
调试结果：
有序表的合并
链式有序表合并
问题分析：
假设头指针为LA和LB的单链表分别为线性表LA和LB的存储结构，现要归并LA和LB
得到单链表 LC。因为链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不
需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需把LA和LB两
个表中的结点重新进行链接即可。
【算法步骤】
-
指针 pa和 pb 初始化，分别指向LA和LB的第一个结点。
-
LC的结点取值为LA的头结点。
-
指针 pc初始化，指向LC的头结点。
-
当指针 pa 和 pb 均未到达相应表尾时， 则依次比较 pa 和 pb 所指向的元素值， 从 LA 或
LB 中 ＂摘取“ 元素值较小的结点插入到 LC 的最后。
-
将非空表的剩余段插入到 pc 所指结点之后。
-
释放 LB 的头结点。
c语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct node{
int number;
struct node * next;
}Node,*LinkList;
//创建单链表,尾插法
LinkList initLink(){
LinkList head=(LinkList)malloc(sizeof(Node));//创建头节点
LinkList temp=head;//声明一个指针，用于遍历
LinkList p;
printf("链表初始化，输入0结束:\n");
int num;
while(1){
scanf("%d",&num);
fflush(stdin); //清空缓存
if (num==0) return head;//判断是否停止
p =(LinkList)malloc(sizeof(Node));
p->number=num;
p->next=NULL;
temp->next=p;
temp=p;
}
}
//遍历列表
void travelList(LinkList pNode){
LinkList temp=pNode;//用于遍历
int num;
while(temp->next){
temp=temp->next;
num=temp->number;
printf("%d\n",num);
}
}
void Combine(LinkList La, LinkList Lb, LinkList Lc){
LinkList pa,pb,pc;
pa = La->next;
pb = Lb->next;
Lc = pc = La;
while(pa && pb){
if(pa->number <= pb->number){
pc->next = pa;
pc = pa;
pa = pa->next;
}
else{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa? pa:pb;
free(Lb);
travelList(Lc);
}
int main(){
Node *LA,*LB;//两个链表
printf("初始化顺序表a\n");
LA=initLink();
printf("初始化后的链顺序表La\n");
travelList(LA);
printf("初始化顺序表lb\n");
LB=initLink();
printf("初始化后的顺序表Lb\n");
travelList(LB);
LinkList Lc;//第三个表Lc
printf("合并化后的链表为：\n");
Combine(LA,LB,Lc);
}
调试结果：