단일 체인 표 의 기본 알고리즘 2 - C 언어 구현

#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__
#include
#include
#include
typedef int DataType;//      
typedef struct Node
{
    DataType data;
    struct Node* pNext;
}Node, *PNode;
//     
void InitLinkList(PNode* pHead);
//        
PNode BuyNode(DataType x);
//      
void PrintLinkList(PNode pHead);
//     
void PushBack(PNode* pHead, DataType x);
//           
PNode Find(PNode pHead, DataType x);
 //        x    
PNode Insert(PNode pos, DataType x);
//   pos       
void Erase(PNode* pHead, PNode pos);
//          
void DeleteNotpTailNode(PNode pos);
//       data
void InsertNotHead(PNode pos, DataType x);
//      ——    (      ）
PNode ReverseLinkList(PNode pHead);
//      ——   
PNode ReverseLinkList(PNode pHead);
//         --         
PNode FindMidNode(PNode pHead);
#endif//__LINK_LIST_H__

#include"LinkList.h"
//     
void InitLinkList(PNode* pHead)
{
    assert(*pHead);
    (*pHead) = NULL;
}
//        
PNode BuyNode(DataType x)
{
    PNode pCur = (PNode)malloc(sizeof(Node));
    if (NULL == pCur)
        return NULL;
    else
    {
        pCur->data = x;
        pCur->pNext = NULL;
        return pCur;
    }
}
//      
void PrintLinkList(PNode pHead)
{
    if (NULL == pHead)
        printf("null
");
    else
    {
        while (pHead)
        {
            printf("%d--->", pHead->data);
            pHead = pHead->pNext;
        }
        printf("NULL
");
    }
}
//     
void PushBack(PNode* pHead, DataType x)//    
{
    PNode pTail = *pHead;
    PNode pCur = BuyNode(x);
    if (NULL == (*pHead))
        *pHead = pCur;
    else
    {
        while (pTail->pNext)
        {
            pTail = pTail->pNext;
        }
        pTail->pNext = pCur;
    }
}
//           
PNode Find(PNode pHead, DataType x)
{
    PNode pCur = pHead;
    PNode pPreCur = NULL;
    assert(pHead);
    if (NULL == pHead)
        return NULL;
    while (pCur)
    {
        if (pCur->data == x)
        {
            pPreCur = pCur;
            return pPreCur;
        }
        else
        {
            pCur = pCur->pNext;
        }
    }
    return NULL;
}
//        x    
PNode Insert(PNode pos, DataType x)
{
    PNode pCur = NULL;
    if (NULL == pos)
        return NULL;
     pCur = BuyNode(x);
     if (NULL == pCur)
         return NULL;
    pCur->pNext = pos->pNext;
    pos->pNext = pCur;
}
//   pos       
void Erase(PNode* pHead, PNode pos)
{
    assert(pHead);//     
    if (NULL ==(*pHead)&&NULL == pos)//      pos      ，      ，        
        return;
    if ((*pHead) == pos)
    {
        free(*pHead);
        (*pHead) = NULL;
    }
    else
    {
        PNode pCur = *pHead;
        while (pCur->pNext != pos)
        {
            pCur = pCur->pNext;
        }
        pCur->pNext = pos->pNext;
        free(pos);
        pos = NULL;
    }
}
//          （   pos     ，    pos     ，        ，  pos    ，     ）
void DeleteNotpTailNode(PNode pos)
{
    PNode pCur = pos->pNext;
    if (NULL == pos&&NULL==pos->pNext)
        return;
    pos->data = pCur->data;
    pos->pNext = pCur->pNext;
    free(pCur);
    pCur = NULL;
}
//       data
void InsertNotHead(PNode pos, DataType x)
{
    PNode pPreCur = NULL;
    DataType temp = 0;
    if (NULL == pos)
        return;
     pPreCur = BuyNode(x);
    if (NULL == pPreCur)
        return;
    pPreCur->pNext = pos->pNext;
    pos->pNext = pPreCur;
    temp = pos->data;
    pos->data = pPreCur->data;
    pPreCur->data = temp;
}
//      ——    (      ）
PNode ReverseLinkList1(PNode pHead)
{
    PNode pPreCur = NULL;
    PNode pCur = NULL;
    PNode pTail = NULL;
    assert(pHead);
    if (NULL == pHead&&pHead->pNext)
        return pHead;
    pPreCur = pHead;
    pCur = pHead->pNext;
    pTail = pHead->pNext->pNext;
    pHead->pNext = NULL;//   pHead      ，  ，     
    while (pTail)
    {
        pCur->pNext = pPreCur;
        pPreCur = pCur;
        pCur = pTail;
        pTail = pTail->pNext;
    }
    pCur->pNext = pPreCur;
    return pCur;
}
//      ——   
PNode ReverseLinkList(PNode pHead)
{
    PNode pPreCur = NULL;
    PNode pCur = NULL;
    PNode pTail = NULL;
    if (NULL == pHead&&NULL == pHead)
        return pHead;
    pPreCur = pHead;
    pCur = pHead->pNext;
    while (pCur)
    {
        pPreCur->pNext = pTail;
        pTail = pPreCur;
        pPreCur = pCur;
        pCur = pCur->pNext;
    }
    pPreCur->pNext = pTail;
    pTail = pPreCur;
    return pTail;
}
//         --         
PNode FindMidNode(PNode pHead)
{
    assert(pHead);
    PNode pFast = NULL;
    PNode pSlow = NULL;
    if (NULL == pHead&&pHead->pNext)
        return NULL;
    pFast = pHead;
    pSlow = pHead;
    while (pFast&&pFast->pNext)
    {
        pFast = pFast->pNext->pNext;
        pSlow = pSlow->pNext;
    }
    return pSlow;
}

#include"LinkList.h"
void test()
{
    PNode pHead;
    PNode p;
    PNode p2;
    PNode p3;
    PNode p4;
    InitLinkList(&pHead);
    PushBack(&pHead, 1);//  
    PushBack(&pHead, 2);//  
    PushBack(&pHead, 3);//  
    PushBack(&pHead, 4);//  
    PushBack(&pHead, 5);//  
    PushBack(&pHead, 6);//  
    PushBack(&pHead, 7);//  
    PrintLinkList(pHead);//      
    //           
    p=Find(pHead, 5);
    printf("%d
", p->data);
    //        x    
    Insert(Find(pHead, 2), 9);
    PrintLinkList(pHead);//      
    //   pos       
    Erase(&pHead, Find(pHead,3));
    PrintLinkList(pHead);//      
    //          
    DeleteNotpTailNode(Find(pHead,4));
    PrintLinkList(pHead);//      
    //       data
    InsertNotHead(Find(pHead, 6), 8);
    PrintLinkList(pHead);//      
    /*      ——    (      ）*/
    p3=ReverseLinkList1(pHead);
    PrintLinkList(p3);//      (           ，          ）
    //      ——   
    p4=ReverseLinkList(pHead);
    PrintLinkList(p4);//      (           ，          ）
             --         
    p2=FindMidNode(pHead);
    printf("%d
", p2->data);
}
int main()
{
    test();
    system("pause");
    return 0;
}