两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5，只能输出结果，不能修改两个链表的数据。

【问题描述】 两个非降序链表的并集,例如将链表1->2->3 和 2->3->5 并为 1->2->3-~

#include
#include
#include
#define OVERFLOW -2
#define null 0
typedef int datatype;
typedef int status;
/*定义单链表存储结构*/
typedef struct Lnode{
datatype data;
struct Lnode *next;
}Linklist;
/*初始化*/
Linklist *initList(){
Linklist *L;
L=(Linklist*)malloc(sizeof(Linklist));//产生头结点
if(!L) exit(OVERFLOW);
L->next=null;
return L;
}
/*销毁链表*/
void destoryLlist(Linklist *L){
Linklist *q;
while(L)
{
q=L->next;
free(L);
L=q;
}
}
/*并集*/
Linklist* ABList(Linklist *L1,Linklist *L2){

Linklist *head;
head=(Linklist*)malloc(sizeof(Linklist));//产生头结点
if(!head) exit(OVERFLOW);
head->next=null;

Linklist *p,*q,*s1,*s2;
p=head;
s1=L1->next;
s2=L2->next;
datatype e1,e2;

while(s1&&s2)
{
e1=s1->data;
e2=s2->data;
while(s1->next&&s1->next->data==e1) s1=s1->next;//不考虑单个链表有重复值则不需要此步骤
while(s2->next&&s2->next->data==e2) s2=s2->next;//不考虑单个链表有重复值则不需要此步骤
if(e1>e2)
{
q=(Linklist *)malloc(sizeof(Linklist));//尾插法插入元素
q->data=e2;
q->next=p->next;
p->next=q;
p=q;
s2=s2->next;
}
if(e1==e2)
{
q=(Linklist *)malloc(sizeof(Linklist));//尾插法插入元素
q->data=e2;
q->next=p->next;
p->next=q;
p=q;
s1=s1->next;
s2=s2->next;
}
else
{
q=(Linklist *)malloc(sizeof(Linklist));//尾插法插入元素
q->data=e1;
q->next=p->next;
p->next=q;
p=q;
s1=s1->next;
}
}
while(s1)
{
e1=s1->data;
while(s1->next&&s1->next->data==e1) s1=s1->next;//不考虑单个链表有重复值则不需要此步骤
q=(Linklist *)malloc(sizeof(Linklist));
q->data=e1;
q->next=p->next;
p->next=q;
p=q;
s1=s1->next;
}
while(s2)
{
e2=s2->data;
while(s2->next&&s2->next->data==e2) s2=s2->next;//不考虑单个链表有重复值则不需要此步骤
q=(Linklist *)malloc(sizeof(Linklist));
q->data=e2;
q->next=p->next;
p->next=q;
p=q;
s2=s2->next;
}
return head;
}
/*输出*/
status Llistdisplay(Linklist *L){
Linklist *p=L->next;
while(p)
{
printf("%5d",p->data);
p=p->next;
}
printf("
");
return 1;
}
/*带头结点的尾插法创建单链表*/
Linklist* B_creatLlist(){
datatype info;
Linklist *p,*head,*q;
p=head=(Linklist *)malloc(sizeof(Linklist));
head->next=null;
scanf("%d",&info);
while(info)
{
q=(Linklist *)malloc(sizeof(Linklist));
q->data=info;
q->next=p->next;
p->next=q;
p=q;
scanf("%d",&info);
}
return head;
}
int main(){
Linklist *L1;
Linklist *L2;
printf("请输入单链表L1的元素，每个数字以空格隔开,最后以0结尾
");
L1=B_creatLlist();
printf("请输入单链表L2的元素，每个数字以空格隔开,最后以0结尾
");
L2=B_creatLlist();
printf("创建后的单链表L1表为：
");
Llistdisplay(L1);
printf("创建后的单链表L2表为：
");
Llistdisplay(L2);
Linklist *LL;
LL=ABList(L1,L2);
printf("合并后的单链表LL表为：
");
Llistdisplay(LL);

destoryLlist(L1);
destoryLlist(L2);
destoryLlist(LL);
system("pause");
return 0;
}
我感觉逻辑没问题，但是最后的运行结果有问题，我也不知道咋整了

/*两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5，
* 只能输出结果，不能修改两个链表的数据。
* 下面是完整的程序，VC6运行正常。
*/
#define M 5 //第一个链表的结点个数
#define N 9 //第二个链表的结点个数
#define MOD 20 //随机数取值范围：0~MOD之间取值。这三个都可以修改


#include
#include
#include
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}NODE,*PNODE, *LinkList;


/*比较函数，用于qsort排序时回调*/
int CompareInt(const void *s1, const void *s2)
{
int x= *(int *)s1;
int y= *(int *)s2;
return(x-y);
}


/*根据数组x中的n个元素排序后创建*/
LinkList CreateLst(int x[], int n)
{
if(x==NULL || n<=0) return NULL;
qsort((void *)x, n, sizeof(int), CompareInt);/*按升序排列数组x的元素*/
int i=n;
PNODE p, head=NULL;
while(i--)
{
p = (NODE *)calloc(1, sizeof(NODE));
p->data = x[i];
if(head==NULL)
{
head = p;
p->next = NULL;
}
else
{
p->next = head;
head = p; //头插法创建链表
}
}
return head;
}
/*销毁链表*/
void DestroyList(LinkList list)
{
if(list == NULL) return;
NODE * p=list;
while(list != NULL)
{
list = list->next;
free(p);
p = list;
}
}
/*打印链表，但是重复元素只打印一次*/
void printListNoRepeat(LinkList list)
{
while(list!=NULL)
{
printf("%d ", list->data);
while(list->next!=NULL && list->next->data == list->data)
list = list->next;
list = list->next;
}
printf("
");
return;
}
/*主要功能实现：按增序顺序无重复输出两个链表中的数据，但不影响原有的链表*/
void printIncreasinglyNoRepeat(LinkList p1, LinkList p2)
{
int repeat_Flag=0;
while(p1 && p2)
{
while(p1 && p2 && (p1->data data))
{
while(p1->next && p1->data == p1->next->data)//跳过p1中的相邻相等结点
p1=p1->next;
printf("%d ", p1->data);

while (p1 &&p2 && p1->data==p2->data)//如果两个链表结点值相等，第2个链表指针向后移动
p2=p2->next; //避免重复输出
p1=p1->next;
}
while(p1 && p2 && (p2->data data))//跟上一个循环意义相同，p1,p2相反
{
while(p2->next && p2->data == p2->next->data)
p2=p2->next;
printf("%d ", p2->data);


while (p1 &&p2 && p2->data==p1->data)
p1=p1->next;
p2=p2->next;
}
}
/*处理尾巴结点*/
if(p1) printListNoRepeat(p1);
if(p2) printListNoRepeat(p2);


}
/*打印链表*/
void printList(LinkList list)
{
while(list!=NULL)
{
printf("%d ", list->data);
list = list->next;
}
printf("
");
return;
}


int main()
{

int x[M], y[N];
int i=0;
/*1.创建2个链表，其数据来自两个随机整数数组*/
LinkList list1, list2;
srand(time(NULL));//设置随机数种子，保证每次产生不同随机数。
while(i<M)
{
x[i++] = rand()%MOD;
}
i=0;
while(i<N)
{
y[i++] = rand()%MOD;
}
list1 = CreateLst( x, M );
list2 = CreateLst( y, N );

/*顺序打印链表*/
printf("链表1数据:
");
printList(list1);
printf("链表2数据:
");
printList(list2);

/*“合并”链表，非重复递增输出*/
printf("两个链表\"合并\"输出:
");
printIncreasinglyNoRepeat(list1, list2);
printf("

");
/*销毁两个链表，回收内存*/
DestroyList(list1);//销毁list1
DestroyList(list2);//销毁list2

return 0;
}

　　算法：

1. 初始化：定义两个链表p1，p2指针分别指向他们的头指针，再定义一个链表temp并用pt指向它

2. 比较p1,p2指向的元素大小

3. 如果相等  则插入该元素，并且p1，p2，pt指针均往后移动一个；否则 插入两个之中较小的哪一个，并且该指针与pt均往后移动一个

4. 如果p1，p2都指向了最后一个元素则退出，返回链表pt；否则跳转到2

定义两个链表p1，p2指针分别指向他们的头指针，再定义一个链表temp并用pt指向它，然后逐一比较并把较小的接入到temp中，可以参考下面的方式
for(int i=0,t=0;i<3;)
for(int j=0;j<3;)
{
if(p1[i]<=p1[j]) {pt[t]=p1[i];i++}
else if(p1[i]>p1[j]) {pt[t]=p2[i];j++}
t++;
}

你不是要在链表中定义一个数（比如int num），然后将1 2 3这些数字赋值给他吗，你将上面的p1[i]，p2[j]改为指向num就可以比较了，在将他们接到pt后面即可
for(int i=0,t=0;i<3;)
for(int j=0;j<3;)
{
if(p1[i]->num<=p1[j]->num) {pt[t]]->num=p1[i]]->num;pt[t]]->next=p1[i]]->next;i++}
else if(p1[i]]->num>p1[j]]->num) {pt[t]]->num=p2[j]]->num;pt[t]]->next=p2[j]]->next;j++}
t++;
}

lz记得打赏

---

天心区18758513993： 【问题描述】 两个非降序链表的并集,例如将链表1 - >2 - >3 和 2 - >3 - >5 并为 1 - >2 - >3 -- ？
欧秆复方： #include#include #include #define OVERFLOW -2 #define null 0 typedef int datatype; typedef int status; /*定义单链表存储结构*/ typedef struct Lnode{ datatype data; struct Lnode *next; }Linklist; /*初始化*/ Linklist *initList(){ Linklist *L; L=(Linklist*...

天心区18758513993： 两个非降序链表的并集,1 - >2 - >3 和 2 - >3 - >5 并为 1 - >2 - >3 - >5,只能输出结果,不能修改两个链表的数据. - ？
欧秆复方： list* join(list*a,list *b) { list *d = NULL;if (a!=NULL &&(b== NULL || a->data<b->data)d=a; else d=b; if (d==NULL)return d;while(a!= NULL && b!=NULL) {list *m=(a->data<b->data)?a:b;if (d->data <m->data)d->next=m;if (m==a)a=a->next;else b=b->next;} return d; }

天心区18758513993： 两个非降序链表的并集,1 - >2 - >3 和 2 - >3 - >5 并为 1 - >2 - >3 - >5,只能输出结果,不能修改两个链表的数据. - ？
欧秆复方：算法:初始化:定义两个链表p1,p2指针分别指向他们的头指针,再定义一个链表temp并...

天心区18758513993： 如何用C语言创建两个非递减的有序链表,并合并成一非递增的有序链表?? - ？
欧秆复方： 将其中一个链表插入到另一个链表就可以了,只需要修改指针,仍使用原来的存储空间. 可参考这里:http://zhidao.baidu.com/link?url=sI3yQkTWjmfSEfYqP9_s9CSrmt8D6yHQvP_EbHIqbsoIcDshn4E8VlzRnZ2XPZc7J8voSpuzyGaeDp4I3dTBaEv0-z3BpvRtX71yIw6qave

天心区18758513993： 数据结构链表问题将两个非递减的有序链表合并为一个非递增的有序链表 ？
欧秆复方： void MergeList(LinkList La,LinkList Lb,LinkList *Lc) { LinkList pa,pb,pc; pa=La->next;pb=Lb->next; *Lc=pc=La; while(pa && pb) { if(Less_EqualList(&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; free(Lb); } .

天心区18758513993： 两个链表的交叉合并,最简单的,求C++代码.？
欧秆复方： 在此我只给出两个链表交叉合并的函数代码,而且是基于下面前提的: 链表chain1,链表长度为a,链表chain2,链表长度为b; 当a&gt;=b时,chain1的结构依次排在chain2中相应的结构之前,且chain1中多出来的元素跟在chain2的结尾,例如...

天心区18758513993： C++中STL中list的merge函数实现两个无序链表合并,合并后的链表是怎么排序的?例如合并1 - ？
欧秆复方： 合并的链表需要有序,但是现在是无序的,所以结果是这样的: 首先两个头比较:10<30,因此10排在第一个 接着90和30比,30小,30排在第二个 40和90比,40小... 直到第二个链表全部完了,都比90小,这样第一个链表还有元素,接着直接将90连同后面所有元素连过来就是最后的结果(因为默认有序,认为90后面的都比90大,当然实际不是)

天心区18758513993： 用C语言实现两个线性链表的归并 - ？
欧秆复方： 以前学数据结构做过一个“非递减的链表合并一一个非递增的链表” 程序如下:#include <stdio.h>#include <stdlib.h> typedef struct node{ int data; struct node *next; }LinkList;/* 建立链表 */ LinkList *create_link(int m) { LinkList *head,*s,*p; int i; ...

天心区18758513993： 程序设计: 输入两个非降序列,转换成两个非升序列,合并成一个非升序列.(用链表解决) - ？
欧秆复方：#include <stdio.h>#include <stdlib.h>#define LEN sizeof(struct node) typedef struct node { int num; struct node *next; }list; //链表结点结构体 void main() { list *create(); list *turn(list *); list *reform(list *,list *); list *head1,*head2,*head; head1=create(); ...

天心区18758513993： 数据结构与算法 两个链表合并. - ？
欧秆复方： 代码自己写,原理是这样:ListPtr Merge(ListPtr list1, ListPtr list2) { ListPtr result = NULL; /*TODO: 遍历两个链表的每一个元素, 将这个元素与result中的每一个进行对比,若比其大,则将result指针向后移,和下一个元素对比,直到比遇到的元素小, 返回当前元素指针 如果指针为空, result = 这个元素指针, 否者插入result末尾. */ resturn result;} 这么简单的冒泡排序, 为什么不会?还有个方法是用并归排序. 先将两个链表排好序, 再合并,这个复杂度会低些