即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

单链表的基本操作

编程语言 fern_girl 21℃ 0评论

头文件:

#define _CTR_SECURE_NO_WARNINGS 1
#ifndef _SEQLIST__H_
#define _SEQLIST__H_

#include
#include
#include
#include

typedef int DataType;

typedef struct Node
{
    DataType _data;
    struct Node *_pNext;
}Node,*PNode;

typedef struct RNode
{
    DataType _data;
    struct RNode *_pNext;
    struct RNode *random;
}RNode,*pRNode;

void InitList(Node ** pHead);
void PushBack(Node **pHead,DataType data);
void PrintList(PNode pHead);
void Popback(PNode *pHead);
void PushFront(PNode *pHead,DataType data);
void PopFront(PNode *pHead);
void PrintFromTail2Head(PNode pHead);
Node *Find(PNode pHead,DataType data);
void Insert(Node *pos,DataType data);
void Erase(PNode *pHead,Node *pos);
//void DeleNoTailNode(PNode pos);
void Remove(PNode* pHead,DataType data);
void RemoveAll(PNode* pHead, DataType data);
size_t Size(PNode pHead);
PNode Back(PNode * pHead);
PNode Front(PNode pHead);
//void InsertNotHeadNode(PNode pos,DataType data);
//PNode JosephCricle(PNode * pHead,size_t M);
//void BubbleSort(PNode * pHead);
//PNode FindMidNode(PNode pHead);
//PNode FindLastKNode(PNode *pHead,size_t k);
//void DelLastKNode(PNode *pHead,size_t k);
//int IsListCross(PNode L1,PNode L2);
//PNode GetcrossNode(PNode pHead1,PNode pHead2);
//PNode ReverseList(PNode pHead);
//PNode MergeList(PNode pHead1,PNode pHead2);
//PNode IsWithCross(PNode pHead);
//size_t GetCirclenLen(PNode pMeetNode);
//PNode GetEnterNode(PNode pHead,PNode pMeetNode);
//int CrossWithCircle(PNode pHead1,PNode pHead2);
//PNode GetEnterNodeCrossWithCircle(PNode //pHead1,PNode pHead2);
//RNode *CopyComplexList(pRNode pHead);
//PNode ReverseList_R(PNode pHead);



#endif //_SEQLIST__H_

函数具体实现:

#include"Seqlist.h"

void InitList(PNode* pHead)    //初始化指向单链表的指针
{
    assert(pHead);
    *pHead = NULL;
}

Node* BuyNode(DataType data)   //创建新的结点
{
    Node *pNewNode = (Node*)malloc(sizeof(Node));
    if(NULL != pNewNode)
    {
        pNewNode->_data = data;
        pNewNode->_pNext = NULL;
    }
    return pNewNode;
}

void PushBack(PNode *pHead,DataType data)  //不带头结点的单链表尾插结点
{
    assert(pHead);
    if((NULL == *pHead)&&(NULL != BuyNode(data)))
    {
        *pHead = BuyNode(data);
    }
    else
    {
        PNode pTailNode = *pHead;
        /*while(NULL != pTailNode)
        {
            pTailNode = pTailNode->_pNext;
        }
        if(NULL != BuyNode(data))
        {
            pTailNode = BuyNode(data);
        }*/

        while(pTailNode->_pNext != NULL)
        {
            pTailNode = pTailNode->_pNext;
        }
        if(NULL != BuyNode(data))
        {
            pTailNode->_pNext = BuyNode(data);
        }
    }
}


void PopBack(PNode *pHead)    //不带头结点的单链表尾删结点
{
    assert(pHead);
    if(NULL == *pHead)
    {
        return;
    }
    else if(NULL == (*pHead)->_pNext)
    {
        free(*pHead);
        *pHead = NULL;
    }
    else
    {
        Node *pPreNode = *pHead;
        Node *pTailNode = *pHead;

        while(NULL != pTailNode->_pNext)
        {
            pPreNode = pTailNode;
            pTailNode = pTailNode->_pNext;
        }
        free(pTailNode);
        pPreNode->_pNext = NULL;
    }
}

void PushFront(PNode *pHead,DataType data)    //不带头结点的单链表头插结点
{
    PNode pNewNode = NULL;
    assert(pHead);
    /*if(NULL == *pHead)
    {
        *pHead = BuyNode(data);
    }*/

    pNewNode = BuyNode(data);
    pNewNode->_pNext = *pHead;
    *pHead = pNewNode;  
}

void PopFront(PNode *pHead)   //不带头结点的单链表头删结点
{
    PNode pNewNode = NULL;
    assert(pHead);
    if(NULL == *pHead)
    {
        return;
    }
    /*else if(NULL == (*pHead)->_pNext)
    {
        free(*pHead);
        *pHead = NULL;
    }
    else
    {
        PNode pNewNode = *pHead;
        *pHead = (*pHead)->_pNext;
        free(pNewNode);
    }*/
    pNewNode = *pHead;
    *pHead = (*pHead)->_pNext;
    free(pNewNode);
}

Node *Find(PNode pHead,DataType data)     //查找单链表中数据为data的结点位置
{
    PNode pCurNode = pHead;
    while(NULL != pCurNode)
    {
        if(pCurNode->_data == data)
        {
            return pCurNode;
        }
        pCurNode = pCurNode->_pNext;
    }
    return NULL;
}

void Insert(Node *pos,DataType data)    //在单链表某个值为data后插入结点
{
    Node *pNewNode = NULL;
    if(pos == NULL)
    {
        return;
    }
    pNewNode = BuyNode(data);
    if(NULL == pNewNode)
    {
        return;
    }
    else
    {
        pNewNode->_pNext = pos->_pNext;
        pos->_pNext = pNewNode;
    }
}

void Erase(PNode *pHead,Node *pos)      //删除单链表中值为data位置的结点删除
{
    assert(pHead);
    if(NULL == *pHead||NULL == pos)
    {
        return;
    }
    else if(pos == *pHead)
    {
        PopFront(pHead);
    }
    else
    {
        Node *pPreNode = *pHead;
        while(pPreNode->_pNext != pos)
        {
            pPreNode = pPreNode->_pNext;
        }
        pPreNode->_pNext = pos->_pNext;
        free(pos);
    }
}

void Remove(PNode* pHead, DataType data)      // 移除单链表中第一个值为data的结点
{
    PNode pCurNode = NULL;
    assert(pHead);
    if(NULL == pHead)
    {
        return;
    }
    pCurNode = *pHead;
    while(pCurNode != NULL)
    {
        if(pCurNode->_data == data)
        {
            Erase(pHead,pCurNode);
            break;
        }
        else
        {
            pCurNode = pCurNode->_pNext;
        }
    }
}

//void RemoveAll(PNode* pHead, DataType data)      // 移除单链表中所有值为data的结点
//{
//  PNode pCurNode = NULL;
//  PNode pRemNode = NULL;
//  PNode pos = NULL;
//  assert(pHead);
//  pCurNode = *pHead;
//  pRemNode = *pHead;
//  pos = pCurNode->_pNext;
//  
//
//
//  for(pRemNode=pos; pRemNode!=NULL; )
//  {
//      pCurNode = pos->_pNext;
//      while(pCurNode != NULL)
//      {
//          if(pCurNode->_data == data)
//          {
//              
//              Erase(pHead,pCurNode);
//              break;
//          }
//          else
//          {
//              pCurNode = pCurNode->_pNext;
//          }
//      }
//      /*Remove(pHead,data);*/
//      
//      pRemNode = pRemNode->_pNext;
//  }
//}

size_t Size(PNode pHead)     // 获取单链表总结点的总个数
{
    int count = 0;
    PNode pRemNode = pHead;

    if(pHead == NULL)
    {
        return 0;
    }
    while(pRemNode != NULL)
    {
        count++;
        pRemNode = pRemNode->_pNext;
    }
    return count;

}
PNode Back(PNode pHead)     // 返回单链表的最后一个结点的位置
{
    PNode pRemNode = NULL;
    if(NULL == pHead)
    {
        return NULL;
    }
    pRemNode = pHead;
    while(pRemNode->_pNext != NULL)
    {
        pRemNode = pRemNode->_pNext;
    }
    return pRemNode;
}

void PrintList(PNode pHead)   //打印不带头结点的单链表
{
    Node * pCurNode = pHead;
    while(NULL != pCurNode)
    {
        printf("%d->",pCurNode->_data);
        pCurNode = pCurNode->_pNext;
    }
    printf("NULL\n");
}

PNode Front(PNode pHead)      // 返回单链表的第一个结点的位置
{
    if(NULL == pHead)
    {
        return NULL;
    }
    return pHead;
}

转载请注明:CodingBlog » 单链表的基本操作

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情