原题链接：[编程入门]链表合并
解题思路:
要实现两个链表的升序合并，我们首先要明确有几个函数：
生成链表并读取数据的函数：目的是用来生成一个空链表，并输入的信息存储在链表的节点中；
计算链表长度的函数：计算链表所含有数据节点的个数，不包含头结点
对链表进行升序排序的函数：对链表进行升序排序，采用冒泡排序的方式。两层循环，外层控制循环次数，内存控制比较次数，注意与数组不同，每轮循环开始都要将指针指向首元结点
首元结点；
将两个链表合并为一个新链表的函数：采用将两个链表合并为一个新链表的方式，合并的原则是升序排序，前提是两个链表都是有序的；
输出链表数据的函数：与数组不同，只需要把链表头指针传递给函数即可，从首元结点开始输出数据
注意事项:
代码中的链表均是包含头节点的单链表；
写代码最重要的是思路，其次是实现功能的基础编程能力；
在代码实现的过程中可能会出现很多错误，不要灰心，要注意调试
代码较长，有需要的伙伴可以优化后使用
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 | /*他妈的链表*/#include <iostream>#include <cstdlib> using namespace std;//创建链表struct stu{ int sn; int score;}; typedef struct node{ stu tempstu; struct node* nest;}listnode,*listlink; //声明函数void display(listlink pp); void creat(listlink pp,int n){ //头插法和尾插法,采用尾插法 //创建一个节点 //尾插法需要一个尾结点 listnode* tail= pp; //初始化时：：：：尾结点等于头节点 for(int i=1;i<=n;++i) { //创建一个临时变量 listnode* ptemp= new listnode; //C++语法 //初始化临时变量 ptemp->nest=NULL; cin>>ptemp->tempstu.sn>>ptemp->tempstu.score; //tail是机动骑兵 tail->nest=ptemp; tail=ptemp; } //算是插入数据成功}void display(listlink pp) { listnode* ptemp = pp->nest; //等于首元结点 while(ptemp != NULL) //不是空指针就打印信息 { //pp是头节点 cout<<ptemp->tempstu.sn<<" "<<ptemp->tempstu.score<<endl; ptemp=ptemp->nest; } }//按学号升序合并listlink mergee(listlink p1,listlink p2) { //合并后的链表 listnode* p3 = new listnode; listnode* temp=p3; p3->nest=NULL; listnode* pt1=p1->nest; listnode* pt2=p2->nest; //开始合并 while(pt1!=NULL && pt2!=NULL) { if(pt1->tempstu.sn < pt2->tempstu.sn) { //将这个数值赋给p3 p3->nest=pt1; pt1=pt1->nest; } else { //将这个数值赋给p3 p3->nest=pt2; pt2=pt2->nest; } //更新P3的值 p3=p3->nest; } //判断 p3->nest = (pt1 != NULL ? pt1 : pt2); return temp;}//确定链表元素int geshu(listlink p){ int temp=-1; while(p) { ++temp; p=p->nest; } return temp;} //单链表冒泡排序void bubbsort(listlink pt){ //两轮循环，外轮层数，内轮每个 //确定个数 int pnum = geshu(pt); //cout<<"geshiwei---"<<pnum<<endl; //临时节点 listnode* ptemp = pt->nest; //指向首元结点 //n个数据，只需要判断n-1个数据即可 for(int i=1;i<=pnum-1;++i) { //次数而已 //将最大的数放到最后面 for(int j=1;j<=pnum-i;++j) { //首元结点与其下一个比较 if(ptemp->tempstu.sn > ptemp->nest->tempstu.sn) { //cout<<"da于"<<endl; //交换位置,只需要交换信息即可（数据域） listnode* ppp = new listnode; //先复制好信息 ppp->tempstu.sn = ptemp->tempstu.sn; ppp->tempstu.score = ptemp->tempstu.score; ptemp->tempstu.sn = ptemp->nest->tempstu.sn; ptemp->tempstu.score = ptemp->nest->tempstu.score; ptemp->nest->tempstu.sn = ppp->tempstu.sn; ptemp->nest->tempstu.score = ppp->tempstu.score; } else { //cout<<"xiao于"<<endl; //空语句 } ptemp=ptemp->nest; } ptemp = pt->nest; }} int main(){ //申请一块空间 //创建头节点p1,p2 listnode* p1=(listlink)malloc(sizeof(node)); //头文件cstdlib listnode* p2=(listlink)malloc(sizeof(node)); //头节点指针初始化 p1->nest=NULL; p2->nest=NULL; //读取键盘输入的两个链表的大小 int n,m; cin>>n>>m; //创建链表 creat(p1,n); creat(p2,m); bubbsort(p1); bubbsort(p2); //cout<<"************merge hou**************"<<endl; listlink ptemp = mergee(p1,p2); display(ptemp); return 0;} |
C/C++，期待与大家一起进步成长！
9.9 分
2 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复