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

初阶数据结构之---顺序表和链表（C语言）

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

引言-线性表

线性表：

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构，也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时，通常以数组和链式结构的形式存储。

我们今天的主角，顺序表和链表，其实都是线性表，当然线性表不止包含这两个

线性表：

  • 顺序表
  • 链表
  • 栈
  • 队列
  • 字符串
  • ……

再次声明：线性表的逻辑结构是线性的，物理结构不一定是线性

顺序表

概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1.静态顺序表：使用定长存储元素

2.动态顺序表：使用动态开辟数组的存储

来跟我一起手搓个顺序表吧

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们手搓动态顺序表。

我们先写一个头文件，里面写好我们维护的动态顺序表以及要实现的接口函数

结构及接口Sqlist.h

//Sqlist.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<assert.h>
#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
    SLDataType* a;//指向动态开辟数组
    int size;     // 有效数据个数
    int capacity; // 空间容量
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//顺序表查找数据
int SLFind(SL* ps,SLDataType x);

往下就可以开始实现我们的顺序表内容了，下面对于接口的实现放在 Sqlist.c 中

初始化和销毁

void SLInit(SL* ps)
{
    ps->a = NULL; //开始时，给一个空指针
    ps->capacity = ps->size = 0;
}
void SLDestroy(SL* ps)
{
    assert(ps); //断言，防止ps为空指针
    ps->capacity = ps->size = 0;
    free(ps->a);
    ps->a = NULL;
}

顺序表打印

void SLPrint(SL* ps)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        printf("%d\n",ps->a[i]);
    }
    printf("\n");
}

这里需要注意的是，在打印过程中，往顺序表中放置的数据类型不同，所打印的方式也会有所不同，在头文件Sqlist.h中

typedef int SLDataType;

这句代码说明放入的数据类型是int，所以我这里就使用int的打印方式了。

扩容

void SLCheckCapacity(SL* ps)
{
    if (ps->size == ps->capacity) {
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
        //防止开辟空间失败返回空指针
        if (tmp == NULL) {
            perror("malloc fail:");
            exit(1);
        }
        ps->a = tmp;
        //更新容量
        ps->capacity = newCapacity;
    }
}

扩容的部分在整个动态顺序表中占据非常重要的地位，关系到堆中空间的开辟，保证后续数据操作的顺利进行。

头部插入删除和尾部插入删除数据

//头部插入删除
void SLPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);//保证插入时不会越界
    for (int i = ps->size; i > 0; i--) {
        ps->a[i] = ps->a[i - 1];
    }
    ps->a[0] = x;
    ps->size++;
}
void SLPopFront(SL* ps)
{
    assert(ps);
    assert(ps->size);
    for (int i = 0; i < ps->size - 1; i++) {
        ps->a[i] = ps->a[i + 1];
    }
    ps->size--;
}
//尾部插入删除
void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);
    ps->a[ps->size++] = x;
}
void SLPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size != 0);
    ps->size--;
}

这里要注意的是，头部插入删除的实现方式，是将整个后面的数据做了一个移动操作，时间耗费比较大，所以顺序表在实际应用当中，尽量避免使用头插头删。

指定位置之前插入数据和指定位置删除数据

void SLInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--) {
        ps->a[i] = ps->a[i - 1];
    }
    ps->a[pos] = x;
    ps->size++;
}
void SLErase(SL* ps, int pos)
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    for (int i = pos; i < ps->size - 1; i++) {
        ps->a[i] = ps->a[i + 1];
    }
    ps->size--;
}

这里的插入和删除操作在顺序表中其实也避免不了数据的移动，这也体现了顺序表的一个缺陷，中间部分数据的插入删除的时间复杂度较高。

查找数据

最后就是查找列表中数据，返回找到的下标

int SLFind(SL* ps,SLDataType x)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->a[i] == x)return i;
    }
    return -1;
}

这里注意一下，数据的匹配查找其实也要匹配 a 动态数组中的的数据类型，这里我们定义的数据类型为int，就以int的查找方式查找。

体验体验手搓的动态顺序表

以下是体验码

#include"Sqlist.h"
int main()
{
  struct SeqList sq;
  SLInit(&sq);
  SLPushBack(&sq, 1);
  SLPushBack(&sq, 2);
  SLPushBack(&sq, 5);
  SLPushBack(&sq, 6);
  SLPushBack(&sq, 3);
  SLPushFront(&sq, 4);
  SLPrint(&sq);//4 1 2 5 6 3 
  SLPopBack(&sq);
  SLPrint(&sq);//4 1 2 5 6
  SLPopFront(&sq);
  SLPrint(&sq);//1 2 5 6
  int pos1 = SLFind(&sq, 5);
  SLErase(&sq, pos1);
  SLPrint(&sq);//1 2 6
  int pos2 = SLFind(&sq, 6);
  SLInsert(&sq, pos2, 100);
  SLPrint(&sq);//1 2 100 6
    SLDestroy(&sq);
  return 0;
}

以上就是手搓的动态顺序表以及使用了。

链表

链表的概念及结构

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

大概是这样一个东西

注：

  1. 从图上可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
  2. 现实中的结点一般都是从堆上申请出来的
  3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

链表的分类

其实链表不止我刚刚展示的一种，以下情况组合起来就有8种链表结构

1.单像或者双向

图中，上面的是单向，下面为双向

2.带头或者不带头

图中，上面是不带头，下面是带头

3.循环或者非循环

图中，上面是，不循环，下面是循环

它们两两排列组合 2 * 2 * 2 刚好就为8

虽然有这么多结构，但是实际上最常用的只有两种结构：

  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
    构的子结构    ，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

这次手搓个单链表怎样

这里的单链表当然指的是无头单项非循环链表喽。

SList.h存放了单链表结点结构和函数声明

//SList.h
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
//打印单向链表内容
void SLTPrint(SLTNode* phead);
//创建新节点
SLTNode* CreatNewNode(SLTDataType x);
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

下面来实现函数声明的源代码

链表打印

void SLTPrint(SLTNode* phead)
{
  assert(phead);
  SLTNode* pcur = phead;
  while (pcur != NULL) {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("NULL\n");
}

动态申请一个结点

SLTNode* CreatNewNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL) {
    perror("malloc fail:");
    exit(1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

这里创建新结点的重要性不亚于顺序表中的扩容，结点的内存也是开辟在堆上的。

头部的插入删除和尾部的插入删除

//头部插入删除
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = CreatNewNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
void SLTPopFront(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLTNode* prev = *pphead;
  *pphead = (*pphead)->next;
  free(prev);
  prev = NULL;
}
//尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = CreatNewNode(x);
  if (*pphead == NULL) {
    *pphead = newnode;
    return;
  }
  SLTNode* ptail = *pphead;
  while (ptail->next) {
    ptail = ptail->next;
  }
  ptail->next = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  if ((*pphead)->next == NULL) {
    free(*pphead);
    *pphead == NULL;
    return;
  }
  SListNode* ptail = *pphead;
  SListNode* prev = NULL;
  while (ptail->next) {
    prev = ptail;
    ptail = ptail->next;
  }
  prev->next = NULL;
  free(ptail);
  ptail = NULL;
}

这里链表头插头删的时间复杂度相比顺序表就大大降低了，可是尾插尾删还是有一定缺陷的，其操作必须走到链表末尾才能进行。

查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  assert(phead);
  SLTNode* pcur = phead;
  while (pcur) {
    if (pcur->data == x) {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}

这里查找的逻辑非常简单，就是遍历链表匹配元素，如果没找到返回一个空指针。

删除pos结点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  assert(*pphead);
  if (*pphead == pos) {
    SLTNode* del = *pphead;
    *pphead = (*pphead)->next;
    free(del);
    del = NULL;
  }
  SLTNode* pcur = *pphead;
  while (pcur&&pcur->next != pos) {
    pcur = pcur->next;
  }
  pcur->next = pos->next;
  free(pos);
  pos = NULL;
}

这里稍微注意传入的pos是一个指针，指向链表中的元素

这里你是否注意到pphead是一个二级指针，是的，当pos指向头结点时，需要改变外部phead结点的指向，改变phead指针指向就需要使用二级指针pphead了。

指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = CreatNewNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

为什么不提供在指定数据之前插入数据呢？是由于此单链表的无头和单向性，使其很难确定前驱节点的位置和情况，不过硬要提供其实也是可实现的。

同时这里的pos也是一个指针

删除pos之后的结点

void SLTEraseAfter(SLTNode* pos)
{
  assert(pos && pos->next);
  SLTNode* del = pos->next;
  pos->next = del->next;
  free(del);
  del = NULL;
}

删除链表释放空间

void SListDesTroy(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLTNode* next = (*pphead)->next;
  SLTNode* pcur = (*pphead);
  while (pcur) {
    next = pcur->next;
    free(pcur);
    pcur = next;
  }
  *pphead = NULL;
}

注：这里的链表是一个结点一个结点释放的。

体验下手搓的单链表

int main()
{
  SLTNode* phead = NULL;
  SLTPushBack(&phead, 1);
  SLTPushBack(&phead, 2);
  SLTPushBack(&phead, 3);
  SLTPushBack(&phead, 4);
  SLTPushFront(&phead, 5);
  SLTPrint(phead);//5->1->2->3->4->NULL
  SLTPopBack(&phead);
  SLTPopFront(&phead);
  SLTPrint(phead);//1->2->3->NULL
  SLTNode* ret1 = SLTFind(phead, 3);
  SLTInsert(&phead, ret1, 100);
  SLTPrint(phead);//1->2->100->3->NULL
  SLTNode* ret2 = SLTFind(phead, 2);
  SLTErase(&phead, ret2);
  SLTPrint(phead);//1->100->3->NULL
    SLTDestroy(phead);
  return 0;
}

以上就是单项不循环链表的内容了。

来来来，再手搓个双向链表可否？

这里的双向链表便是带头循环双向链表，复杂了些，但用起来确实不知道比单链表爽多少倍。

下面放到LTList.h中

//LTList.h
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;
  struct ListNode* next;
}LTNode;
//创建双向链表结点
LTNode* LTBuyNode(LTDataType x);
//下面有两种初始化方式，这里我们选择第二种，两个其实差别不大
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//销毁链表
void LTDestroy(LTNode* phead);
//打印链表
void LTPrint(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//双向链表的尾插和尾删
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
//双向链表的头插和头删
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos位置之后插入和删除数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

然后就可以实现我们函数声明的源代码了，放到LTList.c中

创建双向链表结点

LTNode* LTBuyNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  newnode->data = x;
  newnode->next = newnode->prev = newnode;
  return newnode;
}

初始化链表

LTNode* LTInit()
{
  LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
  if (phead == NULL) {
    perror("malloc phead fail:");
    exit(1);
  }
  phead->data = -1;
  phead->next = phead->prev = phead;
  return phead;
}

头节点data里其实放什么值都无所谓

销毁链表

void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  LTNode* pnext = pcur->next;
  while (pcur != phead) {
    free(pcur);
    pcur = pnext;
    pnext = pnext->next;
  }
  free(phead);
  pcur = pnext = phead = NULL;
}

这里和单链表销毁同理

打印链表

void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead) {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}

判断链表是否为空

bool LTEmpty(LTNode* phead)
{
  assert(phead);
  if (phead->next == phead)
    return true;
  else
    return false;
}

链表头和链表末尾的插入删除

//链表头的插入和删除
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
  newnode->next = phead->next;
  newnode->prev = phead;
  phead->next->prev = newnode;
  phead->next = newnode;
}
void LTPopFront(LTNode* phead)
{
  assert(phead);
  LTNode* del = phead->next;
  phead->next = del->next;
  del->next->prev = phead;
  free(del);
  del = NULL;
}
//链表末尾的插入和删除
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
  newnode->next = phead;
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  phead->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
  assert(phead);
  LTNode* del = phead->prev;
  phead->prev = del->prev;
  del->prev->next = phead;
  free(del);
  del = NULL;
}

这里链表尾的插入删除就和单链表尾的插入删除不一样了，双向链表可以直接通过head->prev直接找到链表末尾，因此时间复杂度大大降低。

在pos元素之后插入和删除结点

void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = LTBuyNode(x);
  newnode->prev = pos;
  newnode->next = pos->next;
  pos->next->prev = newnode;
  pos->next = newnode;
}
void LTErase(LTNode* pos)
{
  assert(pos);
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
  pos = NULL;
}

查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead) {
    if (pcur->data == x) {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}

以上便是双向链表源代码实现的全部内容了

再来试试我们写的双向链表

int main()
{
  LTNode* phead = LTInit();
  LTPushBack(phead, 1);
  LTPushBack(phead, 2);
  LTPushBack(phead, 3);
  LTPushFront(phead, 4);
  LTPushFront(phead, 100);
  LTPrint(phead);//100->4->1->2->3->
  LTPopFront(phead);
  LTPopBack(phead);
  LTPrint(phead);//4->1->2->
  LTNode* ret = LTFind(phead, 2);
  LTInsert(ret, 120);
  LTPrint(phead);//4->1->2->120->
  LTErase(ret->next);
  LTPrint(phead);//4->1->2->
  LTDestroy(phead);
  return 0;
}

很好，到这里，双向链表的内容也就差不多了。

顺序表和链表小结

顺序表和链表虽然在物理上都是线性的，在实际包装好使用时差别也不大，但是底层却天差地别

合理运用顺序表和链表各自的优势很有利于一些项目的开发，下面是对顺序表和链表的对比总结

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续，但物理上不一定连续

随机访问

 支持：O(1) 不支持：O(N)
任意位置插入或者删除元素 可能需要搬移元素，效率低：O(N) 只需修改指针指向
插入 动态顺序表，空间不够需要扩容 没有容量的概念
应用场景 元素高效存储+频繁访问 让人难以位置插入和删除频繁
缓存利用率 高 低

如果你想了解缓存利用率相关的知识，可以看看下面博客

 与程序员相关的CPU缓存知识

结语

今天的内容到这里就结束了，本来想着把这篇博客分成三部分的，不知咋回事一口气给写完了，一万多字其实很多一部分是代码。后续博主还会继续产出数据结构系列的内容。如果本篇博客对你有帮助的话，还请多多支持博主，感谢大家♥

文章标签：
存储
C语言
缓存
程序员
关键词：
数据结构顺序表
数据结构c语言
数据结构链表
链表数据结构
数据结构顺序表链表
ForcibleBugMaker
目录
相关文章
2的n次方_
|
14天前
|
存储 Java 索引
【数据结构】链表从实现到应用，保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同，其元素在内存中非连续分布，通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念，包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表，说明了其拥有前后两个指针的特点，并展示了相关操作的代码实现。最后，对比了ArrayList与LinkedList的不同之处，包括它们底层实现、时间复杂度以及适用场景等方面。
2的n次方_
31 10
【数据结构】链表从实现到应用，保姆级攻略
2的n次方_
|
2天前
|
存储 Java 程序员
【数据结构】初识集合&深入剖析顺序表（Arraylist）
Java集合框架主要由接口、实现类及迭代器组成，包括Collection和Map两大类。Collection涵盖List（有序、可重复）、Set（无序、不可重复），Map则由键值对构成。集合通过接口定义基本操作，具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复，Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现，各有适用场景。其中ArrayList实现了动态数组功能，可根据需求自动调整大小。
2的n次方_
23 11
小徐在进步
|
8天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
26 8
小徐在进步
|
8天前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念，包括图的定义、无向图与有向图、简单图与多重图等，并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图，如完全图和树等。通过这些概念，读者可以更好地理解图论的基础知识。
小徐在进步
21 8
小徐在进步
|
10天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
25 6
小徐在进步
|
10天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
30 6
小徐在进步
|
10天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表：顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表，使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作，并提供了具体代码示例。静态分配方式下顺序表的长度固定，而动态分配则可根据需求调整大小。此外，还总结了顺序表的优点，如随机访问效率高、存储密度大，以及缺点，如扩展不便和插入删除操作成本高等特点。
小徐在进步
39 5
小徐在进步
|
10天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
14 3
小徐在进步
|
10天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
38 3
小徐在进步
|
10天前
|
存储 C语言
C语言程序设计核心详解 第九章 结构体与链表概要详解
本文档详细介绍了C语言中的结构体与链表。首先，讲解了结构体的定义、初始化及使用方法，并演示了如何通过不同方式定义结构体变量。接着，介绍了指向结构体的指针及其应用，包括结构体变量和结构体数组的指针操作。随后，概述了链表的概念与定义，解释了链表的基本操作如动态分配、插入和删除。最后，简述了共用体类型及其变量定义与引用方法。通过本文档，读者可以全面了解结构体与链表的基础知识及实际应用技巧。
小徐在进步
22 3