当前位置:C++技术网 > 资讯 > 数据结构之单链表翻转--简单地思路实现

数据结构之单链表翻转--简单地思路实现

更新时间:2016-05-17 22:28:18浏览次数:1+次

单链表的翻转问题,切入点就是链表数据倒置。那么,怎么倒置呢?在数据结构中的单链表中,有这样一个操作函数来实现单链表结点的插入:
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;
}

上面给出的是实际的代码,而非主要的算法实现片段,你可以自己运行试试。

实现: