如何用C语言实现无头单向非循环链表Single List ？-阿里云开发者社区

如何用C语言实现无头单向非循环链表Single List ？

2024-05-24 48

版权

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

简介： 这篇文档介绍了一个关于单链表数据结构的实现和相关操作。单链表是一种线性数据结构，每个元素（节点）包含数据和指向下一个节点的指针。文档中列出了单链表的图示，并提供了C语言实现单链表的代码，包括动态申请节点、打印链表、头插、尾插、头删、尾删、查找和在特定位置插入或删除节点等函数。此外，文档还包含了三个测试用例（TestSList1至TestSList4），展示了如何使用这些函数创建、修改和操作单链表。这些测试用例涵盖了插入、删除、查找等基本操作，以及在链表中特定位置插入和删除节点的场景。

一、单链表结构

图示

代码实现

//结构
typedef int SLTDataType;
struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
};
typedef struct SListNode SLTNode;

二、函数接口

动态申请一个节点 BuySListNode

//插入时--动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //创建一个新的节点newnode
  newnode->data = x;  //将要插入的数据放入该节点
  newnode->next = NULL; //初始化该节点的next为NULL，因为只是申请，还没有具体使用
 
  return newnode;   //将新开辟出的节点返回
}

单链表打印 SListPrint

//单链表打印
void SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;    //phead是头指针，在main函数种创建，指向该链表第一个节点
  while (cur != NULL)    //cur指针用于链表遍历
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

尾插 SListPushBack

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)    
//二级指针，理解为传址调用即可
//若不用二级指针而用一级指针，无法做到在该函数体内改变main函数中我们创建的单链表
 
{
  SLTNode* newnode = BuySListNode(x);
 
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    // 找尾节点的指针
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
 
    // 尾节点，链接新节点
    tail->next = newnode;
  }
}

头插 SListPushFront

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySListNode(x);
 
  newnode->next = *pphead;
  *pphead = newnode;
}

尾删 SListPopBack

void SListPopBack(SLTNode** pphead)
{
  if (*pphead == NULL)  // 1、空
  {
    return;
  }
  else if ((*pphead)->next == NULL) // 2、链表中只有一个节点时
  {
    free(*pphead);
    *pphead = NULL;
  }
  else  // 3、有一个以上的节点
  {
    SLTNode* prev = NULL;
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
 
    free(tail);
    prev->next = NULL;
  }
}

头删 SListPopFront

//头删
void SListPopFront(SLTNode** pphead)
{
  SLTNode* next = (*pphead)->next;
  free(*pphead);
 
  *pphead = next;
}

查找 SListFind

//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  SListNode* cur = phead;
  //while (cur != NULL)
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
 
    cur = cur->next;
  }
 
  return NULL;
}

任意位置（pos）前插入 SListInsert

// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  if (pos == *pphead)
  {
    SListPushFront(pphead, x);
  }
  else
  {
    SLTNode* newnode = BuySListNode(x);
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
 
    prev->next = newnode;
    newnode->next = pos;
  }
}

任意位置（pos）值删除 SListErase

// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  if (pos == *pphead)
  {
    SListPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
 
    prev->next = pos->next;
    free(pos);
  }
}

三、整体实现

头文件 Slist.h

//头文件 Slist.h
 
#pragma once
#include <stdio.h>
#include <stdlib.h>
 
//结构
typedef int SLTDataType;
struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
};
typedef struct SListNode SLTNode;
 
 
//插入之前开辟一个新的节点
SLTNode* BuySListNode(SLTDataType x);
 
// 不会改变链表的头指针，传一级指针
void SListPrint(SLTNode* phead);
 
// 可能会改变链表的头指针，传二级指针
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPopFront(SLTNode** pphead);
void SListPopBack(SLTNode** pphead);
 
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
// 在pos的前面插入x
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);
// 删除pos位置的值
void SListErase(SLTNode** phead, SLTNode* pos);
 
// 有些地方也有这样的
 在pos的前面插入x
//void SListInsert(SLTNode** phead, int i, SLTDataType x);
 删除pos位置的值
//void SListErase(SLTNode** phead, int i);

源文件 Slist.c

// Slist.c
 
#include "SList.h"
 
//单链表打印
void SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
 
//插入时--动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //创建一个新的节点newnode
  newnode->data = x;  //将要插入的数据放入该节点
  newnode->next = NULL; //初始化该节点的next为NULL，因为只是申请，还没有具体使用
 
  return newnode;   //将新开辟出的节点返回
}
 
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySListNode(x);
 
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    // 找尾节点的指针
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
 
    // 尾节点，链接新节点
    tail->next = newnode;
  }
}
 
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySListNode(x);
 
  newnode->next = *pphead;
  *pphead = newnode;
}
 
//头删
void SListPopFront(SLTNode** pphead)
{
  SLTNode* next = (*pphead)->next;
  free(*pphead);
 
  *pphead = next;
}
 
//尾删
void SListPopBack(SLTNode** pphead)
{
  if (*pphead == NULL)  // 1、空
  {
    return;
  }
  else if ((*pphead)->next == NULL) // 2、链表中只有一个节点时
  {
    free(*pphead);
    *pphead = NULL;
  }
  else  // 3、有一个以上的节点
  {
    SLTNode* prev = NULL;
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
 
    free(tail);
    prev->next = NULL;
  }
}
 
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  SListNode* cur = phead;
  //while (cur != NULL)
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
 
    cur = cur->next;
  }
 
  return NULL;
}
 
// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  if (pos == *pphead)
  {
    SListPushFront(pphead, x);
  }
  else
  {
    SLTNode* newnode = BuySListNode(x);
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
 
    prev->next = newnode;
    newnode->next = pos;
  }
}
 
// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  if (pos == *pphead)
  {
    SListPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
 
    prev->next = pos->next;
    free(pos);
  }
}

四、使用

源文件 test.c

// test.c 
 
#include "SList.h"
 
void TestSList1()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushFront(&plist, 0);
  SListPrint(plist);
 
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPrint(plist);
 
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPrint(plist);
}
 
void TestSList2()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPrint(plist);
 
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPrint(plist);
}
 
void TestSList3()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPrint(plist);
 
  // 想在3的前面插入一个30
  SLTNode* pos = SListFind(plist, 1);
  if (pos)
  {
    SListInsert(&plist, pos, 10);
  }
  SListPrint(plist);
 
  pos = SListFind(plist, 3);
  if (pos)
  {
    SListInsert(&plist, pos, 30);
  }
  SListPrint(plist);
}
 
void TestSList4()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPrint(plist);
 
  SLTNode* pos = SListFind(plist, 1);
  if (pos)
  {
    SListErase(&plist, pos);
  }
  SListPrint(plist);
 
  pos = SListFind(plist, 4);
  if (pos)
  {
    SListErase(&plist, pos);
  }
  SListPrint(plist);
 
  pos = SListFind(plist, 3);
  if (pos)
  {
    SListErase(&plist, pos);
  }
  SListPrint(plist);
 
  pos = SListFind(plist, 2);
  if (pos)
  {
    SListErase(&plist, pos);
  }
  SListPrint(plist);
}
 
 
int main()
{
  TestSList4();
 
  return 0;
}

如何用C语言实现无头单向非循环链表Single List ？

一、单链表结构

图示

代码实现

二、函数接口

动态申请一个节点 BuySListNode

单链表打印 SListPrint

尾插 SListPushBack

头插 SListPushFront

尾删 SListPopBack

头删 SListPopFront

查找 SListFind

任意位置（pos）前插入 SListInsert

任意位置（pos）值删除 SListErase

三、整体实现

头文件 Slist.h

源文件 Slist.c

四、使用

源文件 test.c

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

如何用C语言实现无头单向非循环链表Single List ？

一、单链表结构

图示

代码实现

二、函数接口

动态申请一个节点 BuySListNode

单链表打印 SListPrint

尾插 SListPushBack

头插 SListPushFront

尾删 SListPopBack

头删 SListPopFront

查找 SListFind

任意位置（pos）前插入 SListInsert

任意位置（pos）值删除 SListErase

三、整体实现

头文件 Slist.h

源文件 Slist.c

四、使用

源文件 test.c

热门文章

最新文章

相关课程

相关电子书