算法数据结构复习：单链表

算法数据结构复习：单链表2013-11-29基本上关于带头结点的单链表能实现的都实现了，链表的转置写了递归和非递归，有些鸡肋的函数就没写。菜鸟一只，欢迎拍砖，高手无视。
//Code by Pnig0s1992 //Date:2012,3,20 #include <stdio.h> #include <Windows.h>typedef struct LinkNode { int iElement; struct LinkNode * pNext; }LinkNode; typedef int Element_type; typedef struct LinkNode * ptrNode; typedef ptrNode LinkList;void MakeEmpty（LinkList L）;//清空单链表 BOOL isEmpty（LinkList L）;//判断链表是否为空 BOOL isLast（ptrNode pPos,LinkList L）;//判断指定结点是否为最后 ptrNode FindNode（Element_type x,LinkList L）;//返回指定元素值的结点 ptrNode FindPrev（Element_type x,LinkList L）;//返回指定元素值的前一个结点 void Insert（Element_type x,ptrNode pPos）;//在指定位置插入一个结点 void Delete（Element_type x,LinkList L）;//删除指定值的结点 Element_type Retrieve（LinkList L）;//返回指定结点位置的元素值 void NonCurReverse（LinkList L）;//单链表的逆置（非递归） void CurReverse（LinkList L）;//单链表的逆置（递归） void printLinkLink（LinkList L）;//打印单链表 int main（int argc,char ** argv） { LinkNode LinkHeader; LinkHeader.pNext = NULL; Insert（20,&LinkHeader）; Insert（40,&LinkHeader）; Insert（10,&LinkHeader）; Insert（70,&LinkHeader）; Insert（30,&LinkHeader）; Insert（50,&LinkHeader）; Insert（80,&LinkHeader）; Insert（90,&LinkHeader）; ptrNode InsertPos = FindNode（50,&LinkHeader）; Delete（20,&LinkHeader）; BOOL bResult; bResult = isEmpty（&LinkHeader）; if（bResult） { printf（"
The LinkList is empty."）; }else{ printf（"
The Linklink is not empty"）; } printf（"
The Linklist before reverse."）; printLinkLink（&LinkHeader）; NonCurReverse（&LinkHeader）; printf（"
The Linklist after reverse."）; printLinkLink（&LinkHeader）; CurReverse（&LinkHeader）; printf（"
The Linklist after second reverse."）; printLinkLink（&LinkHeader）; MakeEmpty（&LinkHeader）; bResult = isEmpty（&LinkHeader）; if（bResult） { printf（"
The LinkList is empty."）; }else{ printf（"
The Linklink is not empty"）; } system（"pause"）; return 0; } //根据指定位置插入结点 void Insert（Element_type x,ptrNode pPos） { ptrNode NewNode = （ptrNode）HeapAlloc（GetProcessHeap（）,0,sizeof（LinkNode））; if（NewNode == NULL） { printf（"
Alloc memory on heap failed with error:%d",GetLastError（））; return; } NewNode->iElement = x; NewNode->pNext = pPos->pNext; pPos->pNext = NewNode; printf（"
Insert node with element %d successfully.",x）; } //返回指定数值所在的结点 ptrNode FindNode（Element_type x,LinkList L） { int iTarget = x; while（L->pNext ！= NULL && L->iElement ！= iTarget） { L = L->pNext; }//注意判断条件return L; }//删除指定数值所在的结点 void Delete（Element_type x,LinkList L） { ptrNode BeforeTarget= FindPrev（x,L）; ptrNode TargetNode = BeforeTarget->pNext; BeforeTarget->pNext = TargetNode->pNext; HeapFree（GetProcessHeap（）,0,TargetNode）; printf（"
Delete node with element %d successfully.",x）; }//返回指定值结点的前一个结点 ptrNode FindPrev（Element_type x,LinkList L） { while（L->pNext ！= NULL） { if（L->pNext->iElement == x） { printf（"
Find node before node with element %d successfully.",x）; return L; } L = L->pNext; } return NULL; } //判断链表是否为空 BOOL isEmpty（LinkList L） { return L->pNext == NULL; }//判断结点是否在最后 BOOL isLast（ptrNode pPos,LinkList L） { if（！isEmpty（L）） { return pPos->pNext == NULL; }else{ return TRUE; } }//返回指定结点的元素值 Element_type Retrieve（LinkList L） { return L->iElement; }//清空链表 void MakeEmpty（LinkList L） { ptrNode pTemp = L->pNext; L->pNext = NULL; ptrNode pT; while（pTemp ！= NULL） { pT = pTemp->pNext; HeapFree（GetProcessHeap（）,0,pTemp）; pTemp = pT; } printf（"
The LinkList has been emptyed successfully."）; }//链表的转置（非递归） void NonCurReverse（LinkList L） { ptrNode pFirst,pSecond; pFirst = L->pNext; pSecond = L->pNext; pSecond = pSecond->pNext; pFirst->pNext = NULL; pFirst = pSecond; while （pFirst ！= NULL） { pSecond = pSecond->pNext; pFirst->pNext = L->pNext; L->pNext = pFirst; pFirst = pSecond; } } //递归逆置单链表（带头结点） void CurReverse（LinkList L） { if（NULL == L || NULL == L->pNext） return; ptrNode q = L->pNext,r = L; while（NULL ！= q && NULL ！= q->pNext） { r = q; q = q->pNext; } r->pNext = NULL; q->pNext = L->pNext; L->pNext = q; CurReverse（q）; }//打印单链表 void printLinkLink（LinkList L） { ptrNode pFirst = L->pNext; while（pFirst ！= NULL） { printf（"%d ",pFirst ->iElement）; pFirst = pFirst->pNext; } }
本文出自 “About:Blank H4cking” 博客，请务必保留此出处http://pnig0s1992.blog.51cto.com/393390/811016