算法数据结构复习[单链表]

基本上关于带头结点的单链表能实现的都实现了，链表的转置写了递归和非递归，有些鸡肋的函数就没写。菜鸟一只，欢迎拍砖，高手无视。

 
 


  
  
//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("\nThe LinkList is empty."); 

  
  
    }else 

  
  
    { 

  
  
        printf("\nThe Linklink is not empty"); 

  
  
    } 

  
  
    printf("\nThe Linklist before reverse."); 

  
  
    printLinkLink(&LinkHeader); 

  
  
    NonCurReverse(&LinkHeader); 

  
  
    printf("\nThe Linklist after reverse."); 

  
  
    printLinkLink(&LinkHeader); 

  
  
    CurReverse(&LinkHeader); 

  
  
    printf("\nThe Linklist after second reverse."); 

  
  
    printLinkLink(&LinkHeader); 

  
  
    MakeEmpty(&LinkHeader); 

  
  
    bResult = isEmpty(&LinkHeader); 

  
  
    if(bResult) 

  
  
    { 

  
  
        printf("\nThe LinkList is empty."); 

  
  
    }else 

  
  
    { 

  
  
        printf("\nThe 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("\nAlloc memory on heap failed with error:%d",GetLastError()); 

  
  
        return; 

  
  
    } 

  
  
    NewNode->iElement = x; 

  
  
    NewNode->pNext = pPos->pNext; 

  
  
    pPos->pNext = NewNode; 

  
  
    printf("\nInsert 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("\nDelete node with element %d successfully.",x); 

  
  
} 

  
  
 

  
  
//返回指定值结点的前一个结点 

  
  
ptrNode FindPrev(Element_type x,LinkList L) 

  
  
{ 

  
  
    while(L->pNext != NULL) 

  
  
    { 

  
  
        if(L->pNext->iElement == x) 

  
  
        { 

  
  
            printf("\nFind 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("\nThe 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; 

  
  
    } 

  
  
} 
 
 

本文转hackfreer51CTO博客，原文链接：http://blog.51cto.com/pnig0s1992/811016，如需转载请自行联系原作者