关于一个大学生写一个题目写一天
到了学校之后发现自己啥都不会,有点伤心了,罢了,开始进入正题:
设计算法实现将两个递增的带头结点有序链表合并为一个递增的有序链表,要求结果链表仍 然使用原来两个链表的存储空间,表中不允许有重复的数据。
来看看我的成品(大多数属于发牢骚,还有就是只有自己能听懂的语言),所以注释可以看下面。
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;//
typedef struct LNode
{
ElemType data;
struct LNode* next;
} LNode,* LinkList;
void InitList(LinkList &L)
{
L=(LinkList )malloc(sizeof(LNode));//就把它当作头节点
L->next=NULL;
}
void create(LinkList &L,int n)
{
/*//前插法创建链表
InitList(L);
for(int i=0;i<n;i++)
{
LNode *p=(LNode *)malloc(sizeof(LNode));
scanf("%d",&(p->data));
p->next=L->next;//前插法,新创一个空间,将这个空间连接原来的空间并消除原来空间的联系,相当于在原来的空间里面挤入了一个新空间
L->next=p;
}*/
//#include<bits/stdc++.h>
//这个头插法不行,要用尾插法
InitList(L);
LNode *r;
r=L;
for(int i=0; i<n; i++)
{
LNode *p=(LNode *)malloc(sizeof(LNode));
p->next=NULL;
scanf("%d",&(p->data));
r->next=p;
r=p;//别忘了这一步;
}
}
void MergeLost(LinkList &LA,LinkList &LB,LinkList &LC)
{
LNode *pa=LA->next;
LNode *pb=LB->next;
LC=LA;
//不合常理 LNode *pc=pa;
LNode *pc=LC;
while(pa&&pb)
{
if(pa->data<=pb->data)
{
//先后顺序很重要
if(pa->data==pb->data)//这样就行了,题目为递增的,也就是最多出现一个重复的
{
//一定要重新写
LNode *temp;
temp=pb;
pb=pb->next;
// pc=pb;
free(temp);
pc->next=pa;
pc=pa;//书上是说把这个c总是放在目前有元素的地方
pa=pa->next;
}
// pa++;//最容易错的地方
else
{
pc->next=pa;
pc=pa;//书上是说把这个c总是放在目前有元素的地方
pa=pa->next;
}
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
if(pa)pc->next=pa;
else if(pb)pc->next=pb;//看清条件!!!!!!!!
free (LB);//别忘了要释放空间
}
void print(LinkList L)
{
LinkList p;//=(LinkList )(malloc(sizeof (LNode)));
p=L->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
}
int main()
{
LinkList LA;
LinkList LB;
LinkList LC;
create(LA,4);
create(LB,4);
MergeLost(LA,LB,LC);
print(LC);
return 0;
}
先来说几个这个题目的引言哈哈,关于这个题,要注意,本来他就是算法题,只要写核心代码就行,之所以写的是完整代码,一是为了巩固之前自己学的,创建链表的知识,还有就是为了验证自己是否对这个算法真正理解,还有对题目的理解,所以我们先来注意一点,这个题目给了前提,两个表原本要都是递增的,所以在一个表中是没有重复的,但是两个表中可以有相同的,这也就为后面我们最多只要删除一个重复的数奠定了条件,别问我为什么 这么强调,因为自己的血泪史QAQ,感觉代码本身比他的解释更重要,主要是靠自己探索,所以我就简述一下思路和我自己写的时候犯的错。
首先就是思路吧:这个题目我们要有合并就必须先要有链表,所以先创建链表,别用前插法,因为前插法是键盘输入和插入的链表顺序显示出来是相反的,而且还有一点就是我们这个代码是专门为递增的链表合并的,所以这样合并后输出来就会是玩全没有顺序而言的东东,然后我们用后插法插入链表后,这时候我们就就解释一下核心代码的思路:
void MergeLost(LinkList &LA,LinkList &LB,LinkList &LC)
{
LC=LA;//先将一个LC头结点指向链表的LA,然后再将pa,pb分别放在两个要合并的链表的首元结点上;
LNode *pa=LA->next;
LNode *pb=LB->next;
//不合常理 LNode *pc=pa;//这里一般我们创建链表都是开始把指针放在头接点上,而这里虽然没有给LC分配空间但它其实就相当于建一个新链表,只不过空间用的是LA,LB的空间。
LNode *pc=LC;
while(pa&&pb)//把已经比完了较小的元素放进LC中,且让pc移到该元素上,再把pa或者pb移到待重新比较的元素上//比较pa,pb两个指针指向的元素的值。
{//如果碰见LA和LB里面相等的元素,就将pb往后移同时把pa此是的元素放在LC里面,并让pa往后移;
if(pa->data<=pb->data)
{
if(pa->data==pb->data)//这样就行了,题目为递增的,也就是最多出现一个重复的
{
//一定要重新写
LNode *temp;//
temp=pb;//别想着把这两句串作为上下部分的公用,这也就是我一直没发现的错误,随着改变下面的判断条件也会变,这时候就改变了我们原来的意思。
pb=pb->next;
free(temp);
pc->next=pa;
pc=pa;//把这个pc总是放在目前有元素的地方
pa=pa->next;
}
// pa++;//最容易错的地方,往后移不是加加TAT
else
{
pc->next=pa;
pc=pa;
pa=pa->next;//这才是表示pa往后移,表示指向下一个已经建立了链表联系的元素
}
}
else
{
pc->next=pb;
pc=pb;//要了解链表的结构,这里就相当于pc=pb;
pb=pb->next;
}
}
if(pa)pc->next=pa;//如果pa还不为空,那么肯定就它后面的元素放在LC里面哈哈
else if(pb)pc->next=pb;//看清条件!!!!!!!!
free (LB);//别忘了要释放空间
}
然后就打印就行了。
然后就是我写这个代码的时候犯的错误:1.我们创建的一般是头节点,除非没有头节点,而非头指针。
2.在插入数据的时候我们先对这个的数据附上原来链表的最后,然后再把这个数据和原链表建立联系,不可以颠倒顺序,不然就是错的;
3.每次插入一个数据的时候在最后都要记得把目前链表的指针放在该元素上,如果不放虽然对目前的这个元素没什么影响,但是到后面就有影响了;
4.还有就是,在打印函数的时候要先让一个指针和要打印的链表的头节点产生联系,再通过这个指针来引出数据,不然就会出错;
5.上面的可能光看完全不可以理解,到时候我会补上这些图便于理解。
相信如果能上这个网站看的文章的人都不是一般人,要时刻相信自己哦!!!