MyException - 我的异常网
当前位置:我的异常网» 编程 » 链表逆放

链表逆放

www.myexceptions.net  网友分享于:2013-04-10  浏览:2次
链表逆置

好些时间没有搞数据结构了,昨天下午老师让我么写个单链表的逆置,当时做了几到都没有测试过;晚上耍CF去了……今天上午又做了一到过了,

这次感觉比较有意义,对内存上的分配更加清新了;上课没听老师讲好像记得他用的两个指针,我写的时候用了四个指针,

我做的时候在桌面画了一个图,看着这个图写出来的;


主要说下算法:

void Reverse(List Head)
{
	List pTwo,pMid,JIE,Haha;    //JIE Haha用于中转用的
	pTwo=Head->pNext;     //pTwo指向头结点的下一个节点
	pMid=pTwo->pNext;     //指向pTwo下一个节点
	pTwo->pNext=NULL;
	while(pMid!=NULL)
	{
		Haha=pMid;
		JIE=pMid->pNext;
		pMid->pNext=pTwo;
		Head->pNext=pMid;
		pTwo=Haha;
		pMid=JIE;
	}
}

说这个算法之前要先搞清楚一个地方:之前生成的节点的内存地址是固定不变的,我们只是改变了这个节点中的数据(指针域),使其在遍历时顺序变一下而已,而其本身的地址没变,

算法思路是这样的:把第二个节点(pTwo下一个节点)插到Head节点的后一个位置——>把第三个节点插到Head节点的后一个位置——>第四个...知道插完;

再解释一下上面代码的实现过程:

将pMid指向的节点的指针域指向pTwo,把Head的指针域指向pMid这样就完成了一个元素的插入,

下面就很接着我们要把此时的pMid赋值给pTwo(赋值的是本身地址而不是数据(指针域));

这里的pMid应该往下面继续走,但是前面:将pMid指向的节点的指针域指向pTwo,这里就造成了走不动的现象了;

所以要用一个中转指针来储存原先pMid的地址,所以中转指针Haha JIE就起到了一系列的中转作用;

看这个代码然后自己画一下图句懂了;


文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有