C语言实现单链表逆序与逆序输出实例
单链表的逆序输出分为两种情况,一种是只逆序输出,实际上不逆序;另一种是把链表逆序。本文就分别实例讲述一下两种方法。具体如下:
1.逆序输出
实例代码如下:
#include<iostream> #include<stack> #include<assert.h> usingnamespacestd; typedefstructnode{ intdata; node*next; }node; //尾部添加 node*add(intn,node*head){ node*t=newnode; t->data=n; t->next=NULL; if(head==NULL){ head=t; } elseif(head->next==NULL){ head->next=t; } else{ node*p=head->next; while(p->next!=NULL){ p=p->next; } p->next=t; } returnhead; } //顺序输出 voidprint(node*head){ node*p=head; while(p!=NULL){ cout<<p->data<<""; p=p->next; } cout<<endl; } //递归 voidreversePrint(node*p){ if(p!=NULL){ reversePrint(p->next); cout<<p->data<<""; } } //栈 voidreversePrint2(node*head){ stack<int>s; while(head!=NULL){ s.push(head->data); head=head->next; } while(!s.empty()){ cout<<s.top()<<""; s.pop(); } } intmain(){ node*head=NULL; for(inti=1;i<=5;i++){ head=add(i,head); } print(head); reversePrint(head); reversePrint2(head); system("pause"); return0; }
逆序输出可以用三种方法:递归,栈,逆序后输出。最后一种接下来讲到。
2.单链表逆序
实例代码如下:
#include<iostream> #include<stack> #include<assert.h> usingnamespacestd; typedefstructnode{ intdata; node*next; }node; node*add(intn,node*head){ node*t=newnode; t->data=n; t->next=NULL; if(head==NULL){ head=t; } elseif(head->next==NULL){ head->next=t; } else{ node*p=head->next; while(p->next!=NULL){ p=p->next; } p->next=t; } returnhead; } //循环 node*reverse(node*head){ if(head==NULL||head->next==NULL){ returnhead; } node*p1=head; node*p2=head->next; node*p3=NULL; head->next=NULL; while(p2!=NULL){ p3=p2; p2=p2->next; p3->next=p1; p1=p3; } head=p1; returnhead; } voidprint(node*head){ node*p=head; while(p!=NULL){ cout<<p->data<<""; p=p->next; } cout<<endl; } //递归 node*reverse2(node*p){ if(p==NULL||p->next==NULL){ returnp; } node*newHead=reverse2(p->next); p->next->next=p; p->next=NULL; returnnewHead; } intmain(){ node*head=NULL; for(inti=1;i<=5;i++){ head=add(i,head); } print(head); head=reverse(head); print(head); head=reverse2(head); print(head); system("pause"); return0; }
这里链表逆序用了两种方法:循环,递归。读者最容易理解的方法就是在纸上自己画一下。
希望本文所述实例对大家的数据结构与算法学习能有所帮助。