c语言单链表源码

2022-12-02 86

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： c语言，单链表源码

总代码：

1、SList.h文件

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//相当于下面的重定义
//struct SListNode
//{
//  STLDataType data;
//  struct SListNode* next;
//};
//typedef struct SListNode SLTNode;
//void SLTPushBack(SLTDataType x)
//{
//  SLTNode node;//这样定义的结点出作用域销毁
//}
typedef int SLTDataType;//重定义数据类型，方便切换数据类型
typedef struct SListNode//定义单链表结构   32位环境下共8个字节，
{
  SLTDataType data;//定义数据
  struct SListNode* next;//指向下一个结构的指针，指向同类
  //SLTNode* next;
}SLTNode;//重定义 缩写，在本行之后起效，在结构体中不能使用
SLTNode* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
void SLTPrint(SLTNode* phead);
//尾插尾删
void SLTPushBack(SLTNode** phead, SLTDataType x);
void SLTPopBack(SLTNode** phead);
//头插头删
void SLTPushFront(SLTNode** phead, SLTDataType x);
void SLTPopFront(SLTNode** phead);
//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置之后的值
void SListEraseAfter(SLTNode* pos);
//在pos位置之前插入x
void SListInsert(SLTNode** phead,SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos);
//单链表的释放
void SLTDestory(SLTNode** phead);

2、SList.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//直接用malloc需要自行赋值，检查空，很烦，所以封装一个函数
SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);//未开辟成功，结束程序
  }
  newnode->data = x;
  newnode->next = NULL;//最后一个结点默认为空
  return newnode;
}
SLTNode* CreateSList(int n)
{
  SLTNode* phead = NULL, * ptail = NULL;
  /*int x = 0;*/
  for (int i = 0; i < n; ++i)
  {
    /*scanf("%d", &x);
    SLTNode* newnode = BuySLTNode(x);*/
    SLTNode* newnode = BuySLTNode(i);
    if (phead == NULL)
    {
      ptail = phead = newnode;
    }
    else
    {
      ptail->next = newnode;
      ptail = newnode;
    }
  }
  return phead;
}
//打印函数封装
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("[%d|%p]->", cur->data,cur->next);
    cur = cur->next;
  }
  printf("NULL\n");
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    //找尾
    while (tail->next)
    {
      tail = tail->next;//不是结尾，tail向后移动。
    }
    tail->next = newnode;//是结尾，tail->next链接新结点
  }
}
//尾删
//void SLTPopBack(SLTNode* phead)
//{
//  SLTNode* tail = phead;
//  SLTNode* prev = NULL;
//  while (tail->next)
//  {
//    prev = tail;
//    tail = tail->next;
//  }
//  free(tail);
//  prev->next = NULL;
//}
//尾删
void SLTPopBack(SLTNode** phead)
{
  assert(*phead);
  if ((*phead)->next == NULL)
  {
    free(*phead);
    *phead = NULL;
  }
  else
  {
    SLTNode* tail = *phead;
    while (tail->next->next)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
//头插
void SLTPushFront(SLTNode** phead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = *phead;
  *phead = newnode;
}
//头删
void SLTPopFront(SLTNode** phead)
{
  assert(*phead);
  SLTNode* next = (*phead)->next;
  free(*phead);
  *phead = next;
}
//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
}
//在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//在pos位置之前插入x
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
  assert(pos);
  if (*phead == pos)
  {
    SLTPushFront(phead, x);
  }
  else
  {
    SLTNode* prev = *phead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
//删除pos位置之后的值
void SListEraseAfter(SLTNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    /*free(pos->next);
    pos->next = pos->next->next;*///错误，释放了后一个，这个空间被置为随机值，找不到后面的结点
    SLTNode* nextNode = pos->next;
    pos->next = nextNode->next;
    free(nextNode);
  }
}
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos)
{
  assert(pos);
  if (pos == *phead)
  {
    SLTPopFront(phead);
  }
  else
  {
    SLTNode* prev = *phead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
//单链表的释放
void SLTDestory(SLTNode** phead)
{
  SLTNode* cur = *phead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *phead = NULL;//plist置空，防止释放后再调用
}

3、test.c测试文件

#include"SList.h"
void TestSList1()
{
  //SLTNode* n1 = malloc();//直接用malloc需要自行赋值，检查空，很烦，所以封装一个函数
  SLTNode* n1 = BuySLTNode(1);
  SLTNode* n2 = BuySLTNode(2);
  SLTNode* n3 = BuySLTNode(3);
  SLTNode* n4 = BuySLTNode(4);
  n1->next = n2;
  n2->next = n3;
  n3->next = n4;
  n4->next = NULL;
  //SLTNode n1;//为什么不直接定义结构体变量
  //SLTNode n2;
  //n1.next = &n2;//这样也可以链接，但是不可行
  //SLTNode* plist = CreateSList(5);
  //SLTPrint(plist);
}
//初始测试代码
void TestSList2()
{
  SLTNode* plist = CreateSList(5);
  SLTPushBack(&plist, 100);
  SLTPushBack(&plist, 200);
  SLTPushBack(&plist, 300);
  SLTPrint(plist);
}
void TestSList3()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 100);
  SLTPushBack(&plist, 200);
  SLTPushBack(&plist, 300);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
}
void TestSList4()
{
  SLTNode* plist = NULL;
  SLTPushFront(&plist, 100);
  SLTPushFront(&plist, 200);
  SLTPushFront(&plist, 300);
  SLTPushFront(&plist, 400);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
}
void TestSList5()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPushBack(&plist, 5);
  SLTPrint(plist);
  SLTNode* pos = SListFind(plist, 3);
  SListInsertAfter(pos, 30);
  pos = SListFind(plist, 2);
  SListInsert(&plist, pos, 200);
  SLTPrint(plist);
  //  if (pos)
  //  {
  //    SListInsertAfter(pos, 30);//找到之后在后面插入30
  //    printf("找到了\n");
  //
  //  }
  //  else
  //  {
  //    printf("找不到\n");
  //  }
  //  SLTPrint(plist);
}
void TestSList6()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPushBack(&plist, 5);
  SLTPrint(plist);
  SLTNode* pos = SListFind(plist, 3);
  SListEraseAfter(pos);
  SLTPrint(plist);
  pos = SListFind(plist, 3);
  SListErase(&plist,pos);
  pos = NULL;
  SLTPrint(plist);
  SLTDestory(&plist);
  SLTPrint(plist);
}
int main()
{
  //TestSList1();
  //TestSList2();
  //TestSList3();
  //TestSList4();
  //TestSList5();
  TestSList6();
  return 0;
}
////二级指针经典例子
//void Swap1(int* p1, int* p2)
//{
//  int tmp = *p1;
//  *p1 = *p2;
//  *p2 = tmp;
//}
//void Swap2(int** pp1, int** pp2)
//{
//  int tmp = *pp1;
//  *pp1 = *pp2;
//  *pp2 = tmp;
//}
//
//int main()
//{
//  int a = 0, b = 1;
//  swap1(&a, &b);
//  
//  int* ptr1 = &a, * ptr2 = &b;
//  swap2(&ptr1, &ptr2);
//
//  return 0;
//
//}

注意：

如果不用二级指针，我们可以用返回值，但是每次返回得接收，c++中可以用引用

不需要修改头指针就用一级，需要修改就用二级，必须将实参的地址传给形参

结语：

这里本章内容就介绍完了，文章中某些内容我们之前有介绍，所以只是一笔带过，还请谅解。希望以上内容对大家有所帮助👀，如有不足望指出🙏

前路漫漫！努力变强💪💪 吧！！

c语言单链表源码

总代码：

结语：

热门文章

最新文章

相关课程

相关电子书