-
2019-08-01 14:45:28
将两个有序单链表合并为一个有序单链表
//完整代码段 #include<stdio.h> #include<stdlib.h> typedef struct LNode{ int data; struct LNode* next; }LNode; LNode* Createlist(int length)//尾插法建立链表 { LNode* L=(LNode*)malloc(sizeof(LNode)); L->next=NULL; LNode* p=L; for(int i=0;i<length;i++) { LNode* t=(LNode*)malloc(sizeof(LNode)); t->next=NULL; scanf("%d",&t->data); p->next=t; p=t; } return L; } LNode* combine(LNode* La,LNode* Lb)//将Lb上元素合并到La上 { LNode* pa=La->next; LNode* pb=Lb->next; LNode* q=La;//分别用三个指针标记两个表的三个位置 while(pa&&pb) { if(pa->data>pb->data)//pb指向的元素小于pa指向的元素,则将pb指向元素插入 { LNode* t=pb; pb=pb->next; t->next=pa; q->next=t; q=t; } else//若pb指向元素不小于pa,则pa指向下一元素直到可以找到 { q=q->next;pa=pa->next; } } if(pb) q->next=pb;//如果pb指向的元素最后仍有大于La表元素的值 return La; } void scan(LNode* L)//遍历链表 { LNode* p=L->next; while(p) { printf("%d ",p->data); p=p->next; } printf("\n"); } int main() { LNode* L1=Createlist(3); LNode* L2=Createlist(3); combine(L1,L2); scan(L1); return 0; }
更多相关内容 -
C语言:有序单链表的创建
2018-12-16 16:59:01如何创建一个带头结点的有序的单链表? 链表在创建的时候就把它创建成有序的会显得专业许多(雾), 而不是先创建无序链表再排序; 拿一道典型例题举个栗子,相信你们都见过这道题; Problem Description 输入N个...如何创建一个带头结点的有序的单链表?
链表在创建的时候就把它创建成有序的会显得专业许多(雾),
而不是先创建无序链表再排序;
拿一道典型例题举个栗子,相信你们都见过这道题;Problem Description
输入N个无序的整数,建立一个有序链表,链表中的结点按照数值非降序排列,输出该有序链表。
Input
第一行输入整数个数N;
第二行输入N个无序的整数。
Output
依次输出有序链表的结点值。
Sample Input
6
33 6 22 9 44 5
Sample Output
5 6 9 22 33 44
Hint
不得使用数组!那么思路是什么呢?
我们可以再输入新的结点时逐个进行查找与插入操作,这样建立的就是有序的链表啦#include<stdio.h> struct node { int data; struct node * next; }; struct node * sort(struct node * p,int x) { struct node *ph,*pte,*paf; ph=p; pte = (struct node *)malloc(sizeof(struct node)); pte->data = x;pte->next = NULL; while (p->next) { paf = p->next; if (paf->data >= x) { pte->next = p->next; p->next = pte; return ph; } p = p->next; } pte->next = p->next; p->next = pte; return ph; //while外表示的是创建第一个结点和最后一个结点时的情况 //大小排序为p<pte<=paf } void list(struct node *p) { p = p->next; while (p) { printf("%d ", p->data); p = p->next; } } int main() { struct node *ph; ph = (struct node *)malloc(sizeof(struct node)); ph->next = NULL; int n, i, x; scanf("%d", &n); for (i = 0;i < n;i++) { scanf("%d", &x); ph = sort(ph, x); } list(ph); getchar(); getchar(); return 0; }
鸣谢这位V家厨(https://www.cnblogs.com/luoxiaoyi/p/9726720.html)
-
C语言创建两个递增单链表,并合并成递增单链表
2020-10-29 11:19:14通过冒泡排序进行单链表的有序插入,并将这两个有序单链表合并成一个有序单链表,使用两个单链表的原有空间进行合并,将生成的有序单链表输出显示 -
建立有序单链表 & 单链表的反转操作
2021-04-16 17:23:04建立有序单链表 & 单链表的反转操作 最近才知道比较主流的...输入一系列数据,以0为结束,建立有序单链表,并将其反转输出 代码如下: #include<iostream> using namespace std; struct linker { int num;建立有序单链表 & 单链表的反转操作
最近才知道比较主流的使用单链表方式为“head指针不指向数据,从head->next开始指向数据”,之前几个月写的都是按“直接从head开始指向数据”来写的。真·村网通…于是按新方法写了建立链表的模板和反转操作,就当图一乐了hhh输入一系列数据,以0为结束,建立有序单链表,并将其反转输出
代码如下:
#include<iostream> using namespace std; struct linker { int num; linker* next; }; linker* Create() { linker* head = NULL, * temp = NULL, * ahead = NULL; head = new linker; //注意申请空间 head->next = NULL; int number; while (1) { cin >> number; if (!number) break; temp = new linker; temp->num = number; if (!head->next) head->next = temp; //把head和temp连上 if (ahead) ahead->next = temp; ahead = temp; } temp->next = NULL; //不加上NULL就会导致Reverse函数里访问非法内存而报错 return head; } void Reverse(linker* head) { linker* p, * q, * r; p = head->next; //此时p(1) q = NULL; head->next = NULL; //此时head->123的"链"断开 while (p) { r = p->next; p->next = q; q = p; p = r; } head->next = q; //下面假如head后面的三个链表指针指向的分别是数字123,来演示一下反转函数的作用机制 //p(1)代表p自己对应数字1,p->1代表p的指向下一个链子对应数字1 /* * 初始状态:head->1->2->3 * 第一循环: * r = p->next; //此时p->r(2) * p->next = q; //此时p->q(NULL) * q = p; //此时p=q,pq(1)->NULL,但pq->r(2)的链子在上一条语句时已经断开了 * p = r; //此时q(1),q->NULL,q与pr之间没有链子,p=r,pr(2)->3 * 第二循环 * r = p->next; //此时p(2)->r(3) * p->next = q; //此时p->r链子断开,p(2)->q(1),完成第一次反转 * q = p; //此时p=q,pq(2)->1 * p = r; //此时p=r,pr(3)与q之间并没有联系 * 第三循环 * r = p->next; //此时p->NULL,故r(NULL) * p->next = q; //此时p(3)->q(2)->1,反转工作已经完成 * q = p; //此时p=q,q(3)->2->1 * p = r; //此时p=r,p(NULL),于是再次试图进入循环时判断p==false,即退出循环 * 退出循环后运行head->next = q,则head->3->2->1 */ } void Out(linker* head) { linker* temp = head->next; while (1) { cout << temp->num << (temp->next ? " " : ""); if (!temp->next) break; temp = temp->next; } } int main() { linker* head = Create(); Reverse(head); Out(head); return 0; }
输入
1 2 3 0
输出
3 2 1
-
将两个有序单链表合并成一个有序单链表的递归做法(C语言)
2021-05-22 13:06:43一、递归算法如下:/*有序单链表的合并,生成一个有序的单链表,递归做法*/Linklist MergerLinklist(Linklist L0,Linklist L1){LNode *Newhead;if(L0 == NULL){return L1;}else if(L1 == NULL){return L0;}else{if(L...一、递归算法如下:
/*有序单链表的合并,生成一个有序的单链表,递归做法*/
Linklist MergerLinklist(Linklist L0,Linklist L1)
{
LNode *Newhead;
if(L0 == NULL)
{
return L1;
}
else if(L1 == NULL)
{
return L0;
}
else
{
if(L0->data < L1->data )
{
Newhead=L0;
Newhead->next = MergerLinklist(L0->next,L1);
}
else
{
Newhead=L1;
Newhead->next = MergerLinklist(L1->next,L0);
}
}
return Newhead;
}
二、实例程序代码如下:
#include#include#include#define LEN 5
typedef int Elemtype;
typedef struct LNode{
Elemtype data;
struct LNode *next;
}LNode,*Linklist;
/*单链表初始化*/
void Init_Linklist(Linklist *L)
{
*L=(Linklist)malloc(sizeof(LNode));
assert(*L != NULL);
(*L)->next=NULL;
}
/*创建单链表*/
void Create_Linklist(Linklist *L)
{
LNode *p,*q;
p = *L;
for(int i=0;idata);
p->next=q;
p=q;
}
p->next=NULL;
}
/*有序单链表的合并,生成一个有序的单链表,递归做法*/
Linklist MergerLinklist(Linklist L0,Linklist L1)
{
LNode *Newhead;
if(L0 == NULL)
{
return L1;
}
else if(L1 == NULL)
{
return L0;
}
else
{
if(L0->data < L1->data )
{
Newhead=L0;
Newhead->next = MergerLinklist(L0->next,L1);
}
else
{
Newhead=L1;
Newhead->next = MergerLinklist(L1->next,L0);
}
}
return Newhead;
}
/*单链表的输出*/
void Print_Linklist(Linklist *L)
{
LNode *p;
p = *L;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
int main()
{
Linklist L0,L1,head=NULL;
/*单链表L0的初始化*/
printf("请输入第一个有序单链表:\n");
Init_Linklist(&L0);
Create_Linklist(&L0);
/*单链表L1的初始化*/
printf("请输入第一个有序单链表:\n");
Init_Linklist(&L1);
Create_Linklist(&L1);
/*单链表的有序合并*/
head=MergerLinklist(L0->next,L1->next);
printf("单链表合并后为:\n");
Print_Linklist(&head);
return 0;
}
二、运行截图为:
-
c++ 创建有序单链表,以及两个有序单链表合并
2017-10-25 22:58:38首先是Node结点的建立//建立结点 class Node { public: Node(){ next=NULL;data=0; } Node(int n){ next=NULL;data=n; } int data; ...这道题需要三个函数实现相应功能 打印 void show(N -
合并两个有序单链表
2021-09-11 21:48:47我们考虑如何将两个值域有序的单链表合并成一个新的有序单链表,使用原有的单链表的头结点作为新链表的头结点。 -
构造有序的单链表
2020-10-21 20:21:43单链表的生成,做的时候有点偷懒了,本来应该生成单链表的时候就应该完成为升序的插入(也就是先插入一个数,然后后面的小的就插前面,大的就往后面插;结果我只是先将数据排序,然后再顺序插;)。 实质:单链表的... -
把两个有序单链表,合并为一个单链表
2020-06-26 18:54:26public static Node mergeTwoLists(Node headA,Node headB){ Node newHead=new Node(-1); Node tmp=newHead; while(headA!=null&&headB!=null){ if(headA.data<headB.data){ tmp.next=headA;... . -
两个有序单链表合并成一个有序单链表--java版本
2019-07-30 15:36:14两个有序链表合并成一个有序链表----两种方法 -
数据结构实验:创建并合并两个有序单链表
2020-04-14 08:21:08} } void merge(linklist &LA,linklist &LB,linklist &LC)//算法2.16 链式有序表的合并 { //已知单链表LA和LB的元素按值非递减排列 //归并LA和LB得到新的单链表LC,LC的元素也按值非递减排列 lnode *pa,*pb,*pc;... -
将两个单链表合并成一个有序单链表
2019-04-19 15:18:43将两个单链表合并成一个有序单链表 思路:因为链表可以由结点轻松构造,所以首先需要创建单链表的元素,然后选择构造方式构造单链表,本代码为后插构造单链表。然后有了链表,怎么合并为一个有序单链表。大体可以先... -
两个有序链表合并成一个有序的单链表
2022-04-18 15:57:10将这两个有序链表合并成一个有序的单链表 要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间 表中允许有重复数据 算法描述 (1)定义一个合并后的指针pc指向La表的头结点。由于要求不占用新的... -
【数据结构】 合并两个非递减有序单链表为一个A-B的非递减有序单链表
2020-11-02 11:46:22【数据结构】 合并两个非递减有序单链表为一个A-B的非递减有序单链表 题目 实现两个单链表La和Lb的相减链表LC,LC的元素为LA中有但LB中没有的元素。LA和LB都为非递减有序链表 分析 LC是LA和LA的相减链表,即LC= ... -
单链表——两个有序链表合并为一个有序
2020-02-23 21:22:27(1)new一个新的链表,定义结点用来遍历两个待排序的链表; (2)两个待排序的链表,哪个头结点小,哪个作为新链表的头结点; (3)对两个链表的结点进行比较,让新链表的next指向较小的结点,更新新链表的尾巴,... -
c++两有序单链表的合并算法
2011-11-10 20:36:57求表长以及有序单链表的合并算法的实现 [问题描述] 假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并计算表长。要求利用原来两个... -
合并两个有序单链表,合并后的单链表也有序
2021-12-22 16:26:23思路:创建一个新的头节点,从第一个有效数据开始比较链表1和链表2的顺序值,将顺序值小的节点放到新创建头结点的后面,依次循环。 代码实现: //合并两个有序的单链表,合并后的新链表仍然有序 public Node ... -
【c语言/链表】两个有序单链表合成为一个有序单链表,自己写的代码运行出错,求助
2020-02-09 00:23:06两个有序单链表合成为一个有序单链表,自己写的代码运行出错, 弄了很久都没解决,是我的思路错了,还是代码细节出问题了?求大神帮忙 编译通过,但是运行是直接提示exe停止运行 ``` #include #include ... -
合并两个有序单链表使之依然有序
2021-08-04 10:35:11合并两个有序单链表使之依然有序 代码实现 public static SingleLinkList mergeLinkedList(HeroNode head1, HeroNode head2) { if (head1 == null && head2 == null) { throw new RuntimeException(... -
【数据结构】链表的应用-两个有序单链表合并
2018-12-19 02:00:39例题2-7:请设计算法,将两个按值递增有序的单链表合并成一个按值递增有序的单链表 进行了:原地处理和异地处理 #include<stdio.h> #include<stdlib.h> #include<string.... -
将两条有序单链表合成一条链表(两种写法)
2018-09-17 21:17:32cout 输出第一个链表:"; list.print(); /*list.insert(2, 100); list.print(); cout 插入某个节点完毕!" ; list.Delete(3); list.print(); cout 删除某个节点完毕!" ; cout (3) ; cout 插入某位置节点... -
编程实现两个有序单链表的合并
2017-12-29 14:21:15实现两个单链表的合并就是将多个原链表的结点进行重新组合排列,重组成一个新的链表。 可以采用下面算法实现,这里list1和list2都是按值递增的序列。 LinkList MergeList(LinkList list1, LinkList list2) { ... -
java 实现有序单链表
2021-03-21 09:49:26} }以上就是关于 java 实现有序单链表 的全部内容了,喜欢的小伙伴别忘了点赞分享一下哦, 关注优讯网,优讯有你更精彩! 转载自: https://my.oschina.net/u/4118445/blog/3112331 版权归原作者所有,如有侵权请... -
java实现合并两个有序单链表
2019-03-12 17:01:51* 将两个有序的单链表合并 * @param node1 * @param node2 * @return */ public static NodeList mergeLink(NodeList node1,NodeList node2){ if(node1 ==null){ return node2; } if(node2 ==... -
两个有序单链表的合并(二路归并)
2019-01-12 18:54:39pa,pb,pc分别作为La,Lb,Lc的工作指针,pa,pb初始化分别指向两个有序链表的第一个元素,pc初始化指向La。从第一个指针开始比较,哪个元素小,就接在Lc后面,如果两个元素相当,就把一个链表接在后面,删除另一个... -
JAVA合并两个有序的单链表,合并之后的链表依然有序
2021-01-29 18:10:00思路:利用第三个单链表,先将其中一个链表连接至链表3,再遍历另外一个链表,将其节点按顺序连接到链表3上。 package linkedlist; public class TwoLinkedListDemo { public static void main(String[] args) {... -
实现两个有序单链表的合并
2012-03-13 23:01:52实现两个有序单链表的合并。要求:随机创建两个单链表,实现单链表的排序,再对两个有序单链表进行合并。 -
有序单链表删除值域重复结点算法
2021-08-20 08:52:24已知一个有序单链表L(允许出现值域重复的结点),设计一个高效算法删除值域重复的结点,并分析算法的时间复杂度。 解:由于是有序单链表,所以相同值域的结点都是相邻的。用p扫描递增单链表,若p所指结点的值域等于...