200字范文 > 【C语言】单向链表排序合并逆序分离(链表的头节点不储存数据)

【C语言】单向链表排序合并逆序分离(链表的头节点不储存数据)

时间：2020-06-19 12:33:33

一、排序

编写程序，在第1题(第1题：编写程序，建立2个带头结点单链表，输入若干整数将正整数插入第1个单链表，将负整数插入第2个单链表，插入前和插入后单链表保持递增或相等次序，显示2个单链表，最后销毁。程序不可存在内存泄漏。)基础上合并2个单链表，合并前后单链表保持递增或相等次序，显示合并前后单链表。注意不可存在内存泄漏。

输入样例:

100 2 3 -2 -8 -6 -9 -10 50 2 -1

输出样例:

2->2->3->50->100-10->-9->-8->-6->-2->-1

代码如下：

#include <stdio.h>#include <stdlib.h>struct Node{int data;struct Node *next;};//malloc创建新的节点struct Node* createNew(){struct Node *pnew;pnew = (struct Node*)malloc(sizeof(struct Node));pnew -> next = NULL;return pnew;}//insertvoid insert(struct Node *phead,int a){struct Node *pold, *pnext, *p;p = createNew();p -> data = a;//第一次插入if(phead -> next == NULL) {phead -> next = p;}//插入在头节点后else {pold = phead;pnext = pold -> next;while(pnext -> data <= p -> data) {//找寻插入位置后移pold = pold -> next;pnext = pold -> next;if(pnext == NULL)//跳出循环的条件break;}//插入p -> next = pnext;pold -> next = p;}};void print(struct Node *p){struct Node *afterHead;afterHead = p -> next;while(afterHead) {if(afterHead != p -> next)printf("->");printf("%d",afterHead -> data);afterHead = afterHead -> next;}printf("\n");}void destroy(struct Node *p){struct Node *pnext;while(p) {pnext = p -> next;free(p);p = pnext;}}int main(){//建立两个链表的头节点struct Node *phead1, *phead2;phead1 = createNew();phead2 = createNew();//输入数据int a;do{scanf("%d",&a);a > 0 ? insert(phead1, a) : insert(phead2, a);}while(getchar() == ' ');//打印数据print(phead1);print(phead2);//销毁数据destroy(phead1);destroy(phead2);return 0;}

二、排序+合并

编写程序，在第1题(第1题：编写程序，建立2个带头结点单链表，输入若干整数将正整数插入第1个单链表，将负整数插入第2个单链表，插入前和插入后单链表保持递增或相等次序，显示2个单链表，最后销毁。程序不可存在内存泄漏。)基础上合并2个单链表，合并前后单链表保持递增或相等次序，显示合并前后单链表。注意不可存在内存泄漏。

输入样例:

100 2 3 -2 -8 -6 -9 -10 50 2 -1

输出样例:

2->2->3->50->100-10->-9->-8->-6->-2->-1-10->-9->-8->-6->-2->-1->2->2->3->50->100

代码如下：

#include <stdio.h>#include <stdlib.h>struct Node{int data;struct Node *next;};//malloc创建新的节点struct Node* createNew(){struct Node *pnew;pnew = (struct Node*)malloc(sizeof(struct Node));pnew -> next = NULL;return pnew;}//insertvoid insert(struct Node *phead,int a){struct Node *pold, *pnext, *p;p = createNew();p -> data = a;//第一次插入if(phead -> next == NULL) {phead -> next = p;}//插入在头节点后else {pold = phead;pnext = pold -> next;while(pnext -> data <= p -> data) {//找寻插入位置后移pold = pold -> next;pnext = pold -> next;if(pnext == NULL)//跳出循环的条件break;}//插入p -> next = pnext;pold -> next = p;}};void print(struct Node *p){struct Node *afterHead;afterHead = p -> next;while(afterHead) {if(afterHead != p -> next)printf("->");printf("%d",afterHead -> data);afterHead = afterHead -> next;}printf("\n");}void destroy(struct Node *p){struct Node *pnext;while(p) {pnext = p -> next;free(p);p = pnext;}}int main(){//建立两个链表的头节点struct Node *phead1, *phead2;phead1 = createNew();phead2 = createNew();//输入数据int a;do{scanf("%d",&a);a > 0 ? insert(phead1, a) : insert(phead2, a);}while(getchar() == ' ');//打印数据print(phead1);print(phead2);// 合并链表struct Node *L = phead2;struct Node *pnew = L;while (pnew->next) pnew = pnew->next; // 最终p为L链表最后一个结点pnew->next = phead1->next, phead1->next = NULL;destroy(phead1);print(L);destroy(L);return 0;}

三、排序+逆序

在第1题( 编写程序，建立2个带头结点单链表，输入若干整数将正整数插入第1个单链表，将负整数插入第2个单链表，插入前和插入后单链表保持递增或相等次序，显示2个单链表，最后销毁。程序不可存在内存泄漏。)建立2个单链表基础上，设计和实现就地逆置单链表函数，即利用原单链表结点建立元素次序相反的单链表。编写程序，建立2个单链表，就地逆置这2个单链表，显示逆置前后的各单链表。注意不可存在内存泄漏。

输入样例:

100 2 3 -2 -8 -6 -9 -10 50 2 -1

输出样例:

2->2->3->50->100-10->-9->-8->-6->-2->-1100->50->3->2->2-1->-2->-6->-8->-9->-10

代码如下：

#include <stdio.h>#include <stdlib.h>struct Node{int data;struct Node *next;};//malloc创建新的节点struct Node* createNew(){struct Node *pnew;pnew = (struct Node*)malloc(sizeof(struct Node));pnew -> next = NULL;return pnew;}//insertvoid insert(struct Node *phead,int a){struct Node *pold, *pnext, *p;p = createNew();p -> data = a;//第一次插入if(phead -> next == NULL) {phead -> next = p;}//插入在头节点后else {pold = phead;pnext = pold -> next;while(pnext -> data <= p -> data) {//找寻插入位置后移pold = pold -> next;pnext = pold -> next;if(pnext == NULL)//跳出循环的条件break;}//插入p -> next = pnext;pold -> next = p;}};void print(struct Node *p){struct Node *afterHead;afterHead = p -> next;while(afterHead) {if(afterHead != p -> next)printf("->");printf("%d",afterHead -> data);afterHead = afterHead -> next;}printf("\n");}struct Node *reverse(struct Node *phead) {struct Node *pafter, *pnext;pafter = phead -> next;while(pafter) {if(pafter == phead -> next) {pnext = pafter -> next;pafter -> next = NULL;pafter = pnext;}else {pnext = pafter -> next;pafter -> next = phead -> next;phead -> next = pafter;pafter = pnext;}}return phead;}void destroy(struct Node *p){struct Node *pnext;while(p) {pnext = p -> next;free(p);p = pnext;}}int main(){//建立两个链表的头节点struct Node *phead1, *phead2;phead1 = createNew();phead2 = createNew();//输入数据int a;do{scanf("%d",&a);a > 0 ? insert(phead1, a) : insert(phead2, a);}while(getchar() == ' ');//打印数据print(phead1);print(phead2);//逆序phead1 = reverse(phead1);phead2 = reverse(phead2);//打印逆序后的链表print(phead1);print(phead2);//销毁数据destroy(phead1);destroy(phead2);return 0;}

四、排序+分离

编写程序，输入若干正整数，按从小到大次序建立1个带头结点单链表，设计一个实现单链表分离算法的Split函数，将原单链表中值为偶数的结点分离出来形成一个新单链表，新单链表中头结点重新申请，其余结点来自原链表，分离后，原链表中只剩非偶数值所在结点，最后显示2个单链表，在程序退出前销毁单链表。要求Split算法时间复杂性达到O（n）,程序不可存在内存泄漏。

输入样例:

100 2 3 50 2 1 5 8

输出样例:

1->2->2->3->5->8->50->1001->3->52->2->8->50->100

#include <stdio.h>#include <stdlib.h>struct Node {int data;struct Node* next;};//createNewstruct Node *createNew() {struct Node *p;p = (struct Node *)(malloc(sizeof(struct Node)));p -> next = NULL;return p;};//insertstruct Node *insert(struct Node *phead, int a) {struct Node *p, *pold, *pnext;p = createNew();p -> data = a;if(!(phead -> next))phead -> next = p;else {pold = phead;pnext = pold -> next;while(p -> data > pnext -> data) {pold = pold -> next;pnext = pold -> next;if(!pnext)break;}p -> next = pnext;pold -> next = p;}return phead;};//splitvoid split(struct Node **pp1,struct Node **pp2) {struct Node *phead1, *phead2;struct Node *pnext, *ptail, *pold;phead1 = *pp1;phead2 = *pp2;pnext = phead1 -> next;pold = phead1;while(pnext) {if(pnext -> data % 2 == 0) {if(!(phead2 -> next)) {phead2 -> next = pnext;ptail = phead2 -> next;}else {ptail -> next = pnext;ptail = ptail -> next;}pnext = pnext -> next;pold -> next = pnext;}else {pold = pnext;pnext = pnext -> next;}}};//printvoid print(struct Node *p){struct Node *afterHead;afterHead = p -> next;while(afterHead) {if(afterHead != p -> next)printf("->");printf("%d",afterHead -> data);afterHead = afterHead -> next;}printf("\n");}//destroyvoid destroy(struct Node *p){struct Node *pnext;while(p) {pnext = p -> next;free(p);p = pnext;}}int main(){//创建俩个链表struct Node *origin, *pnew;origin = createNew();pnew = createNew();int a;do {//输入数据scanf("%d",&a);//插入数据进行排序origin = insert(origin,a);}while(getchar() == ' ');//打印原链表print(origin);//分离链表split(&origin,&pnew);//打印print(origin);print(pnew);//销毁destroy(origin);destroy(pnew);return 0;}

本内容不代表本网观点和政治立场，如有侵犯你的权益请联系我们处理。

网友评论

网友评论仅供其表达个人看法，并不表明网站立场。