AI 助理
备案控制台
开发者社区 云计算 文章 正文

＜单链表（含头结点）＞《数据结构(C语言版)》

2022-11-27 79
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ＜单链表（含头结点）＞《数据结构(C语言版)》

博文内容：

数据结构（C语言版）之单链表及其功能实现（增删查改）

博文作者：

新晓·故知

注：

★博文转载请注明出处。

★博文仅供学习交流，禁止用于商业用途。

目录

博文内容：

数据结构（C语言版）之单链表及其功能实现（增删查改）

博文作者：

新晓·故知

注：

★博文转载请注明出处。

★博文仅供学习交流，禁止用于商业用途。

《数据结构(C语言版)》实战项目之单链表（增删查改）功能实现

一、完整源码：

完整源码如下，欢迎复制测试指正！

单链表（增删查改）功能实现测试示例：

完整源码：

二、实现分析：

问题导引：

3.链表

3.1 链表的概念及结构

单链表尾插：

单链表头插：

单链表尾删：

单链表头删:

单链表查找（按值查找）:

单链表在指定数据位置（pos）插入数据：

单链表在指定数据位置（pos）后插：

单链表在指定数据位置（pos）删除：

单链表在指定数据位置（pos）后删：

单链表销毁：

单链表动态开辟新结点：

后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                              ——By 作者：新晓·故知

《数据结构(C语言版)》实战项目之单链表（增删查改）功能实现

一、完整源码：

完整源码如下，欢迎复制测试指正！

单链表（增删查改）功能实现测试示例：

image.gif编辑

完整源码：

Test.c:

#include "SList.h"
//单链表
//打印测试
void TestSList1()
{
  SListNode* slist = NULL;
  //malloc需要检查，防止开辟失败
  SListNode* n1 = malloc(sizeof(SListNode));
  SListNode* n2 = malloc(sizeof(SListNode));
  SListNode* n3 = malloc(sizeof(SListNode));
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n1->next = n3;
  n3->next = n2;
  n2->next = NULL;
  slist = n1;
  //SListNode* slist = NULL;
  //SListNode* n1 = malloc(sizeof(SListNode));
  //SListNode* n2 = malloc(sizeof(SListNode));
  //SListNode* n3 = malloc(sizeof(SListNode));
  //n1->data = 1;
  //n2->data = 2;
  //n3->data = 3;
  //n1->next = n2;
  //n2->next = n3;
  //n3->next = NULL;
  //slist = n1; 
  SListPrint(slist);
}
//尾插测试
void TestSList2()
{
  SListNode* slist = NULL; //空链表
  //一个一个创建
  /*SListPushBack(slist, 1);
  SListPushBack(slist, 2);
  SListPushBack(slist, 3);
  SListPushBack(slist, 4);*/
  //使用循环创建
  for (int i = 0; i < 4; ++i)
  {
    SListPushBack(&slist, i);
  }
  SListPrint(slist);
}
//头插测试
void TestSList3()
{
  SListNode* slist = NULL; //空链表
  //使用循环创建
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
}
//尾删测试
void TestSList4()
{
  SListNode* slist = NULL; //空链表
  //使用尾插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushBack(&slist, i);
  }
  SListPrint(slist);
  //尾删5次
  SListPopBack(&slist);
  SListPopBack(&slist);
  SListPopBack(&slist);
  SListPopBack(&slist);
  SListPopBack(&slist);
  SListPopBack(&slist);
  SListPrint(slist);
}
//头删测试
void TestSList5()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  //头删
  SListPopFront(&slist);
  SListPrint(slist);
  SListPopFront(&slist);
  SListPopFront(&slist);
  SListPrint(slist);
  SListPopFront(&slist);
  SListPrint(slist);
}
//查找（按值查找）测试
void TestSList6()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  //查找
  SListNode* pos = SListFind(slist, 2);
  if (pos)
  {
    printf("找到了:%p\n", pos);
    // 修改
    pos->data *= 10; //扩大10倍
  }
  SListPrint(slist);
}
//在指定数据（pos）位置插入数据测试
void TestSList7()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  //在指定数据（pos）位置插入数据
  //查找（按值查找）
  SListNode* pos = SListFind(slist, 3);
  if (pos)
  {
    SListInsert(&slist, pos, 30);
  }
  SListPrint(slist);
  //查找（按值查找）
  pos = SListFind(slist, 1);
  if (pos)
  {
    SListInsert(&slist, pos, 50);
  }
  SListPrint(slist);
}
// 在指定数据位置（pos）后插测试
void TestSList8()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  // 在指定数据位置（pos）后插
  //查找（按值查找）
  SListNode* pos = SListFind(slist, 2);
  if (pos)
  {
    SListInsertAfter(pos, 30);
  }
  SListPrint(slist);
}
// 在指定数据位置（pos）删除测试
void TestSList9()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  // 在指定数据位置（pos）删除
  //查找（按值查找）
  SListNode* pos = SListFind(slist, 2);
  if (pos)
  {
    SListErase(&slist, pos);
  }
  SListPrint(slist);
  //查找（按值查找）
  pos = SListFind(slist, 1);
  if (pos)
  {
    SListErase(&slist, pos);
  }
  SListPrint(slist);
}
// 在指定数据位置（pos）位置后删测试
void TestSList10()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  //在指定数据位置（pos）位置后删
  //查找（按值查找）
  SListNode* pos = SListFind(slist, 2);
  if (pos)
  {
    SListEraseAfter(pos);
  }
  SListPrint(slist);
  //查找（按值查找）
  pos = SListFind(slist, 3);
  if (pos)
  {
    SListEraseAfter(pos);
  }
  SListPrint(slist);
}
//销毁单链表测试
void TestSList11()
{
  SListNode* slist = NULL; //空链表
  //使用头插+循环创建 4个数据
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
  //销毁单链表
  SListDestroy(&slist);
}
int main()
{
  TestSList1();
  TestSList2();
  TestSList3();
  TestSList4();
  TestSList5();
  TestSList6();
  TestSList7();
  TestSList8();
  TestSList9();
  TestSList10();
  TestSList11();
  return 0;
}
image.gif

SList.c:

#include "SList.h"
//单链表
//打印
void SListPrint(SListNode* phead)
{    //Print不需要改变什么
  //assert(phead);  //没必要暴力终止程序,空链表也可打印
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//动态开辟新结点
SListNode* BuySListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  //检查是否开辟成功
  if (newnode == NULL)
  {
    printf("malloc fail！\n");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  return newnode;
}
//头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
  assert(pphead);
  //根据需要动态开辟新结点
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
  assert(pphead);
  //根据需要动态开辟新结点
  SListNode* newnode = BuySListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    // 找尾-需要从头遍历
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
////尾插-传参有误
//void SListPushBack(SListNode* phead, SLTDataType x)
//{  
//  //根据需要动态开辟新结点
//  SListNode* newnode = BuySListNode(x);
//  if (phead == NULL)
//  {
//    phead = newnode;
//  }
//  else
//  {
//    // 找尾-需要从头遍历
//    SListNode* tail = phead;
//    while (tail->next != NULL)
//    {
//      tail = tail->next;
//    }
//    tail->next = newnode;
//  }
//}
//尾删
void SListPopBack(SListNode** pphead)
{
  assert(pphead);
  // 也可以暴力检查为空的情况
  //assert(*pphead != NULL);
  // 1、空
  // 2、一个节点
  // 3、多个节点
  if (*pphead == NULL)  // 温柔检查
  {
    return;
  }
  else if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    //写法1——使用双指针
    /*SListNode* prev = NULL;
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
    prev = tail;
    tail = tail->next;
    }
    free(tail);
    tail = NULL;
    prev->next = NULL;*/
    //写法2——提前控制指针
    SListNode* tail = *pphead;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
//头删
void SListPopFront(SListNode** pphead)
{
  assert(pphead);
  // 1、空
  // 2、非空
  if (*pphead == NULL)
  {
    return;
  }
  else
  {
    SListNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
  }
}
//查找（按值查找）
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
  SListNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
// 在指定位置（pos）位置插入数据
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  // 1、pos是第一个节点
  // 2、pos不是第一个节点
  if (pos == *pphead)
  {
    SListPushFront(pphead, x);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    //根据需要动态开辟新结点
    SListNode* newnode = BuySListNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
// 在指定位置（pos）位置后插
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
  assert(pos);
  SListNode* next = pos->next;
  ////写法1
  ////根据需要动态开辟新结点
  //SListNode* newnode = BuySListNode(x);
  ////改动顺序随意
  //pos->next = newnode;
  //newnode->next = next;
  //写法2
  //根据需要动态开辟新结点
  SListNode* newnode = BuySListNode(x);
  //改动顺序指定
  newnode->next = pos->next;
  pos->next = newnode;
}
// 在指定位置（pos）位置删除
void SListErase(SListNode** pphead, SListNode* pos)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    SListPopFront(pphead);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
// 在指定位置（pos）位置后删
void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  //注：这个不会是头删
  SListNode* next = pos->next;
  if (next)
  {
    pos->next = next->next;
    free(next);
    next = NULL;
  }
}
//销毁单链表
void SListDestroy(SListNode** pphead)
{
  assert(pphead);
  SListNode* cur = *pphead;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}
image.gif

SList.h:

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;  //以后可以更改int为char或者double等
typedef struct SListNode
{
  SLTDataType data; // val
  struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SListNode** pphead);
//头删
void SListPopFront(SListNode** pphead);
//查找（按值查找）
//查找可以传二级指针，但没必要，因为不会改变数据，只是进行查找
SListNode* SListFind(SListNode* phead, SLTDataType x);
// 在指定位置（pos）位置前插
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
// 在指定位置（pos）位置删除
void SListErase(SListNode** pphead, SListNode* pos);
// 在指定位置（pos）位置后插
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 在指定位置（pos）位置后删
void SListEraseAfter(SListNode* pos);
//销毁单链表
void SListDestroy(SListNode** pphead);
image.gif

二、实现分析：

问题导引：

顺序表的问题及思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们

再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

3.链表

3.1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

image.gif编辑

image.gif编辑

也可以这样：

image.gif编辑

单链表实现测试：

测试示例：image.gif编辑 Test.c：

#include "SList.h"
void TestSList1()
{
  SListNode* slist = NULL;
  SListNode* n1 = malloc(sizeof(SListNode));
  SListNode* n2 = malloc(sizeof(SListNode));
  SListNode* n3 = malloc(sizeof(SListNode));
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n1->next = n3;
  n3->next = n2;
  n2->next = NULL;
  slist = n1;
  SListPrint(slist);
}
int main()
{
  TestSList1();
  return 0;
}
image.gif

SList.c:

#include "SList.h"
void SListPrint(SListNode* phead)
{
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
image.gif

SList.h:

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data; // val
  struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
image.gif

单链表不需要初始化，即使最初为空，也是一个空指针，而顺序表最初为空是一个结构体！

image.gif编辑image.gif编辑

image.gif编辑image.gif编辑

image.gif编辑image.gif编辑

举例传参分析：

1.image.gif编辑image.gif编辑

2.image.gif编辑image.gif编辑

image.gif编辑

image.gif编辑

单链表尾插：

测试示例：image.gif编辑

Test.c:

#include "SList.h"
//单链表尾插数据测试
void TestSList2()
{
  SListNode* slist = NULL; //空链表
  //一个一个创建
  /*SListPushBack(slist, 1);
  SListPushBack(slist, 2);
  SListPushBack(slist, 3);
  SListPushBack(slist, 4);*/
  //使用循环创建
  for (int i = 0; i < 4; ++i)
  {
    SListPushBack(&slist, i);
  }
  SListPrint(slist);
}
int main()
{
  TestSList2();
  return 0;
}
image.gif

SList.c:

#include "SList.h"
//单链表打印
void SListPrint(SListNode* phead)
{    //Print不需要改变什么
  //assert(phead);  //不需要暴力终止程序,空链表也可打印
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//单链表动态开辟新结点
SListNode* BuySListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  //检查是否开辟成功
  if (newnode == NULL)
  {
    printf("malloc fail！\n");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  return newnode;
}
//单链表尾插数据
void SListPushBack(SListNode** pphead, SLTDataType x)
{
  //根据需要动态开辟新结点
  SListNode* newnode = BuySListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    // 找尾-需要从头遍历
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
image.gif

SList.h:

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;  //以后可以更改int为char或者double等
typedef struct SListNode
{
  SLTDataType data; // val
  struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);
image.gif

单链表头插：

测试示例：image.gif编辑

Test.c:

#include "SList.h"
//单链表头插数据测试
void TestSList3()
{
  SListNode* slist = NULL; //空链表
  //使用循环创建
  for (int i = 0; i < 4; ++i)
  {
    SListPushFront(&slist, i);
  }
  SListPrint(slist);
}
int main()
{
  TestSList3();
  return 0;
}
image.gif

SList.c:

#include "SList.h"
//单链表打印
void SListPrint(SListNode* phead)
{    //Print不需要改变什么
  //assert(phead);  //不需要暴力终止程序,空链表也可打印
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//单链表动态开辟新结点
SListNode* BuySListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  //检查是否开辟成功
  if (newnode == NULL)
  {
    printf("malloc fail！\n");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  return newnode;
}
//单链表头插数据
void SListPushFront(SListNode** pphead, SLTDataType x)
{
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
image.gif

SList.h:

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;  //以后可以更改int为char或者double等
typedef struct SListNode
{
  SLTDataType data; // val
  struct SListNode* next; // 存储下一个结点的地址
}SListNode, SLN;
//头结点指针
void SListPrint(SListNode* phead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);
image.gif

单链表尾删：

image.gif编辑

image.gif编辑image.gif编辑

单链表头删:image.gif编辑

单链表查找（按值查找）:image.gif编辑

单链表在指定数据位置（pos）插入数据：image.gif编辑

单链表在指定数据位置（pos）后插：image.gif编辑

单链表在指定数据位置（pos）删除：image.gif编辑

单链表在指定数据位置（pos）后删：image.gif编辑

单链表销毁：image.gif编辑

单链表动态开辟新结点：image.gif编辑

image.gif编辑

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                   ——By 作者：新晓·故知

文章标签：
存储
关键词：
数据结构c语言
C语言数据结构
C语言单链表
数据结构单链表
单链表数据结构
新晓故知
目录
相关文章
小徐在进步
|
2天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
22 6
小徐在进步
|
2天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
10 3
小徐在进步
|
2天前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作；以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段，展示了每种算法的实现思路与步骤，帮助读者深入理解并掌握这些数据结构的基本操作方法。
小徐在进步
13 2
小徐在进步
|
2天前
|
算法 C语言 开发者
C语言手撕实战代码_单链表
本文档详细介绍了使用C语言实现单链表的各种基本操作和经典算法。内容涵盖单链表的构建、插入、查找、合并及特殊操作，如头插法和尾插法构建单链表、插入元素、查找倒数第m个节点、合并两个有序链表等。每部分均配有详细的代码示例和注释，帮助读者更好地理解和掌握单链表的编程技巧。此外，还提供了判断子链、查找公共后缀等进阶题目，适合初学者和有一定基础的开发者学习参考。
小徐在进步
11 2
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
12 2
小徐在进步
|
2天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现，涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例，展示了如何高效地处理顺序表数据结构的各种问题。
小徐在进步
10 1
小徐在进步
|
22小时前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
15 8
小徐在进步
|
22小时前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念，包括图的定义、无向图与有向图、简单图与多重图等，并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图，如完全图和树等。通过这些概念，读者可以更好地理解图论的基础知识。
小徐在进步
16 8
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
14 3
2的n次方_
|
4天前
|
Java
【数据结构】栈和队列的深度探索，从实现到应用详解
本文介绍了栈和队列这两种数据结构。栈是一种后进先出（LIFO）的数据结构，元素只能从栈顶进行插入和删除。栈的基本操作包括压栈、出栈、获取栈顶元素、判断是否为空及获取栈的大小。栈可以通过数组或链表实现，并可用于将递归转化为循环。队列则是一种先进先出（FIFO）的数据结构，元素只能从队尾插入，从队首移除。队列的基本操作包括入队、出队、获取队首元素、判断是否为空及获取队列大小。队列可通过双向链表或数组实现。此外，双端队列（Deque）支持两端插入和删除元素，提供了更丰富的操作。
2的n次方_
10 0
【数据结构】栈和队列的深度探索，从实现到应用详解