链表逆序
- 链表结构的简单介绍
链表在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;
}
- 递归逆序
下一次讲到,并将全部测试代码贴上。
上一篇: ASP.NET缓存介绍