[c语言]单链表的实现

今天药忘吃喽~ 2022-01-17 09:09 232阅读 0赞

`一、基础知识：链表（线性表的链式存储结构）`

`（1）特点：逻辑关系相邻，物理位置不一定相邻。`

`（2）分类：`

`a.不带头节点`

`b.带头节点`

`（3）单链表的存储结构：`

typedef struct SListNode
    
    {
    
     DataType data;
    
     struct SListNode* next;
    
    }SListNode;

二、代码实现(因避开使用二级指针，所以代码中使用了c++中的引用)：此处构造的为不带头节点的链表

(1)sList.h

#pragma once
    typedef int DataType;
    typedef struct SListNode
    {
     DataType data;
     struct SListNode* next;
    }SListNode;
    void PushBack(SListNode* & pHead, DataType d);
    void PopBack(SListNode* & pHead);
    void PushFront(SListNode* & pHead, DataType d);
    void PopFront(SListNode* & pHead);
    void PrintList(SListNode* pHead);
    SListNode* Find(SListNode* & pHead, DataType d);
    void Insert(SListNode* & pos, DataType d);

(2)sList.cpp

#include <stdio.h>
    #include <malloc.h>
    #include <assert.h>
    #include "sList.h"
    SListNode* MakeNode(DataType d)
    {
     SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
     tmp->data = d;
     tmp->next = NULL;
     return tmp;
    }
    void PushBack(SListNode* & pHead, DataType d)
    {
     //1.空
     //2.不空
     if(pHead == NULL)
     {
      pHead = MakeNode(d);
     }
     else
     {
      //先找尾，再插入新节点
      SListNode* tail = pHead;
      while(tail->next != NULL)
      {
       tail = tail->next;
      }
      tail->next = MakeNode(d);
     }
    }
    void PopBack(SListNode* & pHead)
    {
     //1.空
     //2.一个节点
     //3.多个节点
     if(pHead == NULL)
     {
      return;
     }
     else if (pHead->next == NULL)
     {
      free(pHead);
      pHead = NULL;
     }
     else
     {
      SListNode* tail = pHead;
      SListNode* prev = NULL;
      while(tail->next != NULL)
      {
       prev = tail;
       tail = tail->next;
      }
      prev->next = NULL;
      free(tail);
     }
    }
    void PushFront(SListNode* & pHead, DataType d)
    {
     if(pHead == NULL)
     {
      pHead = MakeNode(d);
     }
     else
     {
      SListNode* tmp = pHead;
      pHead = MakeNode(d);
      pHead->next = tmp;
     }
    }
    void PopFront(SListNode* & pHead)
    {
     if(!pHead)
     {
      printf("List is empty!");
      return;
     }
     else
     {
      SListNode* tmp = pHead;
      pHead = pHead->next;
      free(tmp);
     }
    }
    SListNode* Find(SListNode* & pHead, DataType d)
    {
     SListNode* find = pHead;
     while(find)
     {
      if(find->data == d)
       return find;
      find = find->next;
     }
     return NULL;
    }
    void Insert(SListNode* & pos, DataType d)
    {
     assert(pos);
     /*
     方法一：
     SListNode* tmp = MakeNode(d);
     tmp->next = pos->next;
     pos->next = tmp;
     */
     //方法二：
     SListNode* next = pos->next;
     pos->next = MakeNode(d);
     pos->next->next = next;
    }
    void Erase(SListNode*& pHead,SListNode* & pos)
    {
     assert(pos&&pHead);
     SListNode* prev = pHead;
     while(prev->next != pos)
     {
      prev = prev->next;
     }
     prev->next = pos->next;
     free(pos);
     pos = NULL;
    }
    void PrintList(SListNode* pHead)
    {
     SListNode* tmp = pHead;
     while(tmp)
     {
      printf("%d->", tmp->data);
      tmp = tmp->next;
     }
     printf("NULL\n");

（3）test.cpp

#include "sList.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    void test1()
    {
     //不带头节点
     SListNode* list = NULL;
     PushBack(list, 1);
     PushBack(list, 2);
     PushBack(list, 3);
     PushBack(list, 4);
    // PushFront(list,0);
    // PopFront(list);
    // PopBack(list);
     SListNode* ret = Find(list, 2);
     if(ret == NULL)
     {
      printf("No Exist!\n");
      return;
     }
    // Insert(ret, 4);
     Erase(list,ret);
     PrintList(list);
    }
    int main()
    {
     test1();
     system("pause");
     return 0;

转载于:https://blog.51cto.com/10738651/1767650