欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

链表逆序

程序员文章站 2024-03-06 08:14:19
...
  • 链表结构的简单介绍

链表在C语言中属于相对非常基础的数据结构,采用的时候指针指向下一块要用的数据。直到链表数据的最后一块。本小节只讨论单链表的数据结构,所以在数据的最后用NULL 结尾。这里将介绍2中链表逆序的方式递归链表逆序和直接链表逆序。下面是定义的简单的链表结构,并将链表头用一个全局处理。

typedef struct tag_NodeList
{
	int iData;
	struct tag_NodeList *pstNext;
}NodeList_S;

NodeList_S g_stNodeList;

int ListGlobleInit(void)
{
	 g_stNodeList.pstNext = NULL;
	 return 0; 
}

 

  • 链表的简单操作

本文包含的就是链表的插入和遍历显示,还有就是完全free的操作,这些就不做过多的说明了

int ListAddData(int iData)
{
	NodeList_S *pstNodeNew = NULL;
	pstNodeNew = (NodeList_S *)malloc(sizeof(NodeList_S));
	if (NULL == pstNodeNew)
	{
		printf("malloc fail");
		return -1;
	}
	pstNodeNew->iData = iData;
	pstNodeNew->pstNext = g_stNodeList.pstNext;
	g_stNodeList.pstNext = pstNodeNew;
	return 0;
}

int ListAddCheckData(void)
{
	int iCount = 1;
	for (iCount = 1; iCount <= 1000000; iCount ++)
	{
		ListAddData(iCount);	
	}	
	return 0;
}	
  
int ListFreeNodeList(void)
{
	NodeList_S *pstNode = g_stNodeList.pstNext;
	NodeList_S *pstNodeFree = NULL;
	while (NULL != pstNode)
	{
		pstNodeFree = pstNode;
		pstNode = pstNode->pstNext;
		free(pstNodeFree);
	}
}

int ListShowNodeList(NodeList_S *pstNodeList)
{
	if (NULL == pstNodeList)
	{
		return -1;
	}
	NodeList_S *pstNodeTmp = pstNodeList;
	while (NULL != pstNodeTmp)
	{
		printf("\r%d\n", pstNodeTmp->iData);
		pstNodeTmp = pstNodeTmp->pstNext;
	}
	return 0;
}
  • 直接逆序

采用如下的方式进行逆序 如果有一个head-1-2-3-4-NULL的数据插入到链表的数据结构中去,需要变为head-4-3-2-1-NULL.我这里采用的数据是2-1, 3-2-1, 4-3-2-1,head-4-3-2-1-NULL,这里用一个图来表示更为明显。

1
2
3
4
2
1
3
4

 

就以3图的2个例子,其实我将采用3个指针来记录这个 分别是Next,Cur, Tmp,Next 用于记录当前的下一个,Cur用于记录当前的指针,Tmp用于循环记录,因为逆序一直在下一个指向上一个,所以为了避免一直在2个记数种循环我采用了这么一个指针,其实进入的第一次Next就应该是2,而Cur就是1,我采用的第一次Tmp其实也用的2作为计数开始,因为至少要有2个数字才存在着逆序,当第一次改变后进入第二次逆序的时候cur就是2,Next就是3,Tmp也是3,当第3次的时候cur就是3,next  就是4,Tmp也是4.其实这时候也是最后一次了,因为tmp的next指针为NULL,应该跳出了,这个时候4是没有挂到Head上面的 同时1的下一个也没有指向NULL, 通过这个我们发现一个规律,其实cur 就是Tmp的上一个指针的位置,Next其实就是循环后下一次Tmp指针的位置,即上一个Tmp->pstNext,就可以做到如下的代码段。

int ListReverseNodeList(NodeList_S *pstNodeList)
{
	if (NULL == pstNodeList)
	{
		return -1;
	}
	NodeList_S *pstCurr = pstNodeList;
	NodeList_S *pstNext = NULL;
	NodeList_S *pstNodeTmp = pstNodeList->pstNext;
	
	while (NULL != pstNodeTmp)
	{
		pstNext = pstNodeTmp;
		pstNodeTmp = pstNodeTmp->pstNext;
		pstNext->pstNext = pstCurr;
		pstCurr = pstNext;
	}
	/* 最后一个还没有计数 */	
	pstNodeTmp = g_stNodeList.pstNext;
	pstNodeTmp->pstNext = NULL;
	g_stNodeList.pstNext = pstCurr;
	return 0;
}
  • 递归逆序

       下一次讲到,并将全部测试代码贴上。