int InsertList(LinkList head, int i, int e)//在第i-1的位置插入结点
{
LinkList p,pre;
int j=0;
pre=head;
while(pre->next!=NULL && j<i-1)//找到前驱结点
{
pre=pre->next;
j++;
}
if(j!=i-1)
{
cout<<"插入出错!"<<endl;
}
p=(LinkList)malloc(sizeof(LinkList));
p->data=e;//以上这两句构造一个实实在在的结点
//插入操作
p->next=pre->next;
pre->next=p;
return 0;
}
这个函数实现的是什么?其实就是在刚刚创建的一个链表中插入一个个结点。这个函数的实现,在任何一本数据结构书上都有,我就不讲解了。它实现的是顺序的往我们链表中插入我们想要插入的数据。链表的倒置,也就是倒置我们要插入的数据(假设,我们是用数组来存这些数据的)也即是倒置数组!因此,我们就可以这样的利用上面这个函数:int InsertList_Last(LinkList head,int i,int e)
{
LinkList pre,p;
pre=head;
int j=len-1;
while(pre->next && j>i-1)
{
pre=pre->next;
j--;
}
if(j!=i-1)
{
cout<<"插入出错!"<<endl;
}
p=(LinkList)malloc(sizeof(LinkList));
p->data=e;//以上这两句构造一个实实在在的结点
//插入操作
p->next=pre->next;
pre->next=p;
return 0;
}
for(int i=sizeof(a)/sizeof(int); i>=1; i--)
{
InsertList_Last(M,i,a[i-1]);
}
就能够逆序输出单链表的值了。不过你也可以利用stack来做,在这里,我没有用到stack。
也就是说,我们实现倒置链表,就是在插入结点的时候,倒置了插入节点的顺序。下面看个完整的代码:
#include "windows.h"
#include "iostream"
#include "stdio.h"
using namespace std;
int len;//定义全局的变量来存数组数据的长度
typedef struct node{
int data;
struct node *next;
}*LinkList;
LinkList InitList()
{
LinkList H;
H=(LinkList)malloc(sizeof(LinkList));
if(H==NULL)
{
exit(-1);
}
H->next=NULL;//创建有头结点的空链表
return H;
}
int InsertList(LinkList head, int i, int e)//在第i-1的位置插入结点
{
LinkList p,pre;
int j=0;
pre=head;
while(pre->next!=NULL && j<i-1)//找到前驱结点
{
pre=pre->next;
j++;
}
if(j!=i-1)
{
cout<<"插入出错!"<<endl;
}
p=(LinkList)malloc(sizeof(LinkList));
p->data=e;//以上这两句构造一个实实在在的结点
//插入操作
p->next=pre->next;
pre->next=p;
return 0;
}
int Length_List(LinkList head)
{
LinkList p;
p=head->next;
int index=0;
while(p)
{
index++;
p=p->next;
}
return index;
}
LinkList GetList(LinkList head,int i)
{
LinkList p;
int j=0;
p=head;
while(p->next &&j!=i)
{
j++;
p=p->next;
}
if(j==i)
{
return p;
}
}
int InsertList_Last(LinkList head,int i,int e)
{
LinkList pre,p;
pre=head;
int j=len-1;
while(pre->next && j>i-1)
{
pre=pre->next;
j--;
}
if(j!=i-1)
{
cout<<"插入出错!"<<endl;
}
p=(LinkList)malloc(sizeof(LinkList));
p->data=e;//以上这两句构造一个实实在在的结点
//插入操作
p->next=pre->next;
pre->next=p;
return 0;
}
int main()
{
LinkList A,L,p,M;
L=InitList();
M=InitList();
int a[]={11,12,15,13,24,25,5};
/*for(int i=0; i<10; i++)
{
scanf("%d",&a[i]);
}*/
len=sizeof(a)/sizeof(int);
for(int i=1; i<=sizeof(a)/sizeof(int); i++)
{
InsertList(L,i,a[i-1]);
}
//翻转......
for(int i=sizeof(a)/sizeof(int); i>=1; i--)
{
InsertList_Last(M,i,a[i-1]);
}
for(int i=1; i<=Length_List(L); i++)
{
p=GetList(M,i);
cout<<p->data<<" ";
}
system("pause");
return 0;
}
上面给出的是实际的代码,而非主要的算法实现片段,你可以自己运行试试。
实现: