假设有两个按元素值递增有序排列的线性表 A 和 B,均以单链表作为存储结构,请编写算法将 A 表和 B 表归并成一个按元素递减有序排列的线性表 C,并要求利用原表的节点空间构造 C 表。
NOTICE: 代码是按照源码顺序依次贴上来的,直接复制就能跑!
环境:
Visual Stdio Code
题目
假设有两个按元素值递增有序排列的线性表 A 和 B,均以单链表作为存储结构,请编写算法将 A 表和 B 表归并成一个按元素递减有序排列的线性表 C,并要求利用原表(即 A 表和 B 表)的节点空间构造 C 表。
分析
因为表 A 和表 B 都是按照递增有序排列的,我们没有办法同时进行逆置跟归并,所以我们要先将 A 表和 B 表逆置,再将两个表归并。
程序
初始化:
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
typedef struct LNode
{
ElemType data;
LNode *next;
}LNode, *LinkList;
Status InitList(LinkList &L)
{ // 初始化单链表 L
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
return OK;
}//InitList
创建单链表 L:
Status CreateList(LinkList &L, int e)
{ // 创建单链表 L
LinkList p = L;
while(p->next)
p = p->next;
LinkList temp = (LinkList)malloc(sizeof(LNode));
temp->data = e;
temp->next = NULL;
p->next = temp;
return OK;
}//CreateList
打印单链表:
Status DispList(LinkList &L)
{ // 打印单链表 L
LinkList p = L->next;
while(p)
{
printf("%d\t", p->data);
p = p->next;
}
return OK;
}//DispList
逆置:
Status ListOppose(LinkList &L)
{ // 将带表头节点的单链表逆置
LinkList q, p, s;
p = L;
p = p->next;
L->next = NULL;
while(p)
{
q = p;
p = p->next;
q->next = L->next;
L->next = q;
}
return OK;
}//ListOppose
归并:
Status ListMerge(LinkList &A, LinkList &B, LinkList &C)
{ // 合并两个递增单链表 A, B 成一个递增有序单链表 C
LinkList qa, pa, pb, qb;
pa = A; qa = pa; pa = pa->next;
pb = B->next;
C = A;
while(pa && pb)
{
if(pa->data <= pb->data) // 当 pa 的值 小于等于 pb 的值的时候,将 pb 插入到 pa 的
// 前边
{
qb = pb; // qb 为待插入节点
pb = pb->next; // pb 后移,为以后的插入做准备
qb->next = qa->next; // 本行和下一行代码做插入操作
qa->next = qb;
qa = qa->next; // qa 后移,为以后的插入做准备
}
else // pa 的值大于 pb 的值
{
if(pa->data == pa->next->data) pa = pa->next; // pa 的值和 pa 直接后继节点的
// 值相等,pa 向后移
qb = pb; // qb 为待插入节点
pb = pb->next;
qb->next = pa->next; // 本行和下一行代码做插入操作
pa->next = qb;
pa = pa->next; // pa 后移,为以后的插入做准备
}
}
free(B); // 释放 B 链表的头结点
return OK;
}//ListMerge
主函数:
int main()
{
LinkList A, B, C;
InitList(A); InitList(B);
for(int i = 1; i< 6; i++)
CreateList(A, i);
for(int j = 4; j < 11; j++)
CreateList(B, j);
printf("\nA 链表为:\n");
DispList(A);
printf("\nB 链表为:\n");
DispList(B);
printf("\nC 链表为:\n");
// 逆置
ListOppose(A);
ListOppose(B);
printf("\n逆置后的 A 链表为:\n");
DispList(A);
printf("\n逆置后的 B 链表为:\n");
DispList(B);
// 归并
ListMerge(A, B, C);
printf("\n合并后的 C 链表为:\n");
DispList(C);
return OK;
}
详细说明:
从主函数中可以看出,经过初始化、创建以后的表 A 和表 B 分别为:
逆置之前有一篇文章单独细讲过,这里就不再赘述了。逆置后的两个表:
归并:
我们归并前先将所有可能发生的情况列出来:
(1) pa->data <= pb->data
(2) pa->data > pb->data
又分为以下两种种情况:
1. pa->data == pa->next->data
2. pa->data > pa->next->data
当 pa->data <= pb->data 的时候,我们直接将 pb 插入到 pa 的前边就行:
qb = pb;
qb->next = qa->next;
qa->next = qb;
当 pa->data > pb->data 的时候,又会细分为两种情况:
第一种 pa->data == pa->next->data 即:pa 的值等于 pa 直接后继的值(此时的 pa 指向的是两个相同元素的左边那个)。我们必须将 pa 向后移动,不然就会使得 pb 插入到这两个相同元素的中间;
第二种 pa->data > pa->next->data 这种情况直接将 pb 插入到 pa 的后边就行。
归并过程我整理了一个 动画(动画只是演示,并没有声音,请各位看客见谅)
运行结果示意图:
THE END!
m9_22458869: 我是用edge 和chorme都打不开,而且运行终端也没有报错
璐璐炒鸡酷: 连续函数经过加减乘除和复合在定义域内都是连续的,你举的这个例子因为分母不为零,所所以自然定义域就是不包括零点,定义域都没有零点何谈连续,但是在定义域上还是连续的。
m0_67132983: 不对吧
CSDN-Ada助手: 多亏了你这篇博客, 解决了问题: https://ask.csdn.net/questions/8025690, 请多输出高质量博客, 帮助更多的人
CSDN-Ada助手: 多亏了你这篇博客, 解决了问题: https://ask.csdn.net/questions/8024379, 请多输出高质量博客, 帮助更多的人