备案控制台
开发者社区 开发与运维 文章 正文

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

2024-05-24 23
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 这篇文档介绍了一个关于单链表数据结构的实现和相关操作。单链表是一种线性数据结构，每个元素（节点）包含数据和指向下一个节点的指针。文档中列出了单链表的图示，并提供了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语言
测试技术
关键词：
C语言链表
单向链表
链表list
C语言list
List c语言
碳基肥宅
目录
相关文章
邢仕冲的一亩三分地
|
9天前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
邢仕冲的一亩三分地
17 4
GR鲸鱼
|
28天前
|
编译器 C语言 C++
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值（中）
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值
GR鲸鱼
11 1
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值（中）
邢仕冲的一亩三分地
|
9天前
经典笔试题——单向链表的倒序
经典笔试题——单向链表的倒序
邢仕冲的一亩三分地
11 3
7fa6b5ui5pmtk
|
20天前
|
算法 C语言
数据结构——单向链表（C语言版）
数据结构——单向链表（C语言版）
7fa6b5ui5pmtk
16 2
倔强的石头_
|
19小时前
|
存储 缓存 前端开发
【数据结构/C语言】深入理解 双向链表
【数据结构/C语言】深入理解 双向链表
倔强的石头_
8 0
游客6z2krsj5iqmue
|
26天前
|
存储 C语言 Python
c语言链表
c语言链表
游客6z2krsj5iqmue
30 6
24k纯甄
|
1天前
|
存储 算法 前端开发
【C/数据结构与算法】：链表的实现（单向链表+双向链表）
【C/数据结构与算法】：链表的实现（单向链表+双向链表）
24k纯甄
5 0
GR鲸鱼
|
28天前
|
存储 安全 C语言
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值（上）
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值
GR鲸鱼
15 2
GR鲸鱼
|
28天前
|
编译器 C语言 C++
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值（下）
从C语言到C++_33(C++11_上)initializer_list+右值引用+完美转发+移动构造/赋值
GR鲸鱼
21 1
GR鲸鱼
|
28天前
|
C语言 容器
从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器(下 ）
从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器
GR鲸鱼
10 1