当前位置: 首页 > news >正文

数据结构零基础入门篇(C语言实现)

前言:数据结构属于C++学习中较难的一部分,对应学习者的要求较高,如基础不扎实,建议着重学习C语言中的指针和结构体,万丈高楼平地起。

目录:

 

一,链表

1)单链表的大致结构实现

2)单链表的思考(然后找到链表和判断链表的结束)

3)单链表的程序实现及源代码讲解

1)链表的实现前提准备

2)单链表的创建及初始化

3)单链表的尾插

4)单链表的头插

5)单链表的头删

6)单链表的尾删

7)在单链表中查找元素

8)单链表指定结点的后面插入和删除元素

9)单链表的内存销毁

2)带头双向循环链表的提示(自己实现)

二,队列和栈

1)队列特性

2)栈的特性

3)队列用链表实现(源代码及详细讲解)

1)队列结构和功能实现前准备

2)初始化队列

3)入列数据

4)出列数据

5)获取队列头部元素 

6)获取队列尾部元素

7)销毁队列元素

4)栈的代码实现(提供另外一种思路,自己实现)


 

一,链表

1)单链表的大致结构实现

用C语言实现链表一般是使用结构体,首先我们可以通过链表的结构特性反推结构体的成员。单链表是只能通过前一个节点找到下一个节点,并且是单向的,每一个节点还要存储数据元素,我们实现这个的手段是指针,因此我们需要在前一个结点存储下一个地址。

typedef int SLTDateType;//方便以后修改链表类型
typedef struct STLListNode {SLTDateType n;struct STLListNode* next;
}SListNode;//减少代码的冗余

2)单链表的思考(然后找到链表和判断链表的结束)

首先是如何找到链表的第一个元素,每次,我们之前的图上给了提示,我们可以用一个head指针来标记第一个结点,但有一个很大的注意事项,我们不能随便改变head的地址,不然我们将会无法找到这个链表。

那如何判断链表的结束呢,看上面的手绘图,最后一个结点所指向的是NULL指针,根据这个特点我们就可以判断链表的结束。

注:我们为什么要考虑这两个问题是因为如果我们不严格的控制指针的指向,当指针指向为开辟的空间,会导致程序出现各种意外甚至无法运行。

3)单链表的程序实现及源代码讲解

1)链表的实现前提准备
#include<stdio.h>
#include<assert.h>
typedef int SLTDateType;//方便以后修改链表类型
typedef struct STLListNode {SLTDateType n;struct STLListNode* next;
}SListNode;//减少代码的冗余
2)单链表的创建及初始化
SListNode* BuySListNode(SLTDateType x);
SListNode* BuySListNode(SLTDateType x) {SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//分配内存空间assert(newnode);//防止分配失败导致的访问非法空间newnode->n= x;return newnode;//返回创建空间地址
}
3)单链表的尾插

void SListPushBack(SListNode** pplist, SLTDateType x);
void SListPushBack(SListNode** pplist, SLTDateType x) {//链表要传地址用二级指针接受,因为头插的时候是要改变链表的地址,是需要二级指针才能改变一级指针SListNode* ptemp = *pplist;SListNode** plist = pplist;//防止头指针丢失if (*plist == NULL) {*plist = BuySListNode(x);(*plist)->next = NULL;return;}//如果是空链表需要单独处理while ((*plist)->next != NULL) {*plist = (*plist)->next;}//找到尾节点(*plist)->next  = BuySListNode(x);//分配一个新空间(*plist)->next->next = NULL;//置空方便下次找尾结点*pplist = ptemp;//维持头指针
}
4)单链表的头插

void SListPushFront(SListNode** pplist, SLTDateType x) {//要改变头指针的地址,需要二级指针if (*pplist == NULL) {*pplist = BuySListNode(x);(*pplist)->next = NULL;return;//如果链表为空,单独处理}SListNode* plist= BuySListNode(x);//分配空间plist->next = (*pplist);//将新结点的next指针指向原来的头指针*pplist = plist;//改变头指针
}
5)单链表的头删

void SListPopFront(SListNode** pplist){assert(*pplist);//判断是否为空链表,防止访问非法空间SListNode* plist = *pplist;*pplist = (*pplist)->next;//保留新头plist->next = NULL;//老的头指针置空,防止通过这个非法访问free(plist);//释放老头指针空间
}
6)单链表的尾删

void SListPopBack(SListNode** pplist) {assert(*pplist);//判断是否为空链表,防止访问非法空间SListNode* plist = (*pplist);//保存头指针,防止丢失if (plist->next == NULL) {free(plist);plist = NULL;}//如果只有一个元素,直接释放while (plist->next->next != NULL) {plist = plist->next;}//找到尾结点free(plist->next);plist->next = NULL;//置空
}
7)在单链表中查找元素
SListNode* SListFind(SListNode* plist, SLTDateType x) {assert(plist);//判断是否为空链表,防止访问非法空间while (plist->next != NULL) {if (plist->n = x)return plist;//如果找到直接返回地址plist = plist->next;//否则下一个}return NULL;//找到了尾结点都没找到,返回空指针
}
8)单链表指定结点的后面插入和删除元素
void SListInsertAfter(SListNode* pos, SLTDateType x) {assert(pos);//判断是否为空链表,防止访问非法空间SListNode* temp = pos->next;pos->next = BuySListNode(x);pos->next->next = temp;
}
void SListEraseAfter(SListNode* pos) {assert(pos);//判断是否为空链表,防止访问非法空间assert(pos->next );//判断是否有下一个元素SListNode* temp = pos->next;pos->next = pos->next->next;//改变前一个指针的next指针,防止断层free(temp);
}
9)单链表的内存销毁
void SListDestroy(SListNode* plist) {assert(plist);//防止多次释放空间SListNode* cur = plist->next;//记录当前指针,因为当前指针释放后无法访问到下一个指针的地址while (cur) {free(plist);plist = cur;cur = plist->next;}plist = NULL;
}

2)带头双向循环链表的提示(自己实现)

与单链表相比,带头双向循环链表,会有多开辟一个空间,不用来存储数据,用来指向head指针,这样可以简化许多操作。还要多一个指针指向前一个结点,并且尾指针不在置空,而且指向第一个结点。

二,队列和栈

1)队列特性

就像如图的核酸检测,你先进入队列,你就能比别人先做完核酸离开。因此队列的特性是先进先出。

2)栈的特性

栈的特性就像往一个一次只能拿出一个石头的瓶子里面投石头,你想要拿到最下面的石头你就需要先拿出前面所有的石头,因此栈的特性就是先进后出。

3)队列用链表实现(源代码及详细讲解)

1)队列结构和功能实现前准备

和链表一样,我们队列也使用结构体指针的方法实现,与链表实现大同小异,但会有一个另外的结构体用来存储队列的第一个元素指针的地址,和最后一个元素指针的地址,这样方便我们接下来的各个功能实现,可以省下很多代码量。

#include<stdio.h>
#include<assert.h>
typedef int QDataType;//方便以后将队列修改为其他类型
typedef struct QListNode
{struct QListNode* _next;//下一个队列的指针QDataType _data;//数据元素
}QNode;//减少代码长度
typedef struct Queue
{QNode* _front;//队列第一个元素指针QNode* _rear;//队列最后一个元素指针
}Queue;
2)初始化队列
void QueueInit(Queue* q) {q->_front = (QNode*)malloc(sizeof(QNode));//开辟空间q->_front->_data = -1;//数据随意初始化q->_rear = q->_front ;//此时只有一个元素,头和尾相等
}
3)入列数据
void QueuePush(Queue* q, QDataType data) {q->_rear->_data = data;//从尾开始入列q->_rear->_next = (QNode*)malloc(sizeof(QNode));//给下一个队列分配空间q->_rear = q->_rear->_next;//移动尾指针
}
4)出列数据
void QueuePop(Queue* q) {assert(q->_front!=q->_rear );//防止出列空队列QNode* list = q->_front ;//保存头指针,防止丢失while (list->_next != q->_rear) {list = list->_next;}//找到尾指针free(q->_rear);//释放尾指针q->_rear = list;//重新恢复尾指针
}
5)获取队列头部元素 
QDataType QueueFront(Queue* q) {assert(q->_front != q->_rear);return q->_front->_data;
}
6)获取队列尾部元素
QDataType QueueBack(Queue* q) {assert(q->_front != q->_rear);//判断是否有至少两个元素,防止数组越界QNode* list = q->_front;//保存头指针,防止丢失while (list->_next != q->_rear) {list = list->_next;}//找到尾结点,队列最后一个元素指针return list->_data;
}
7)销毁队列元素
void QueueDestroy(Queue* q) {while (q->_front != q->_rear) {QNode* list = q->_front;//利用list来销毁上一个指针,防止销毁之后找不到下一个元素q->_front = q->_front->_next;//头指针换为下一个元素free(list);//销毁}free(q->_rear);//不要忘记还落下了一个尾结点q->_front = NULL;q->_rear = NULL;//置空,防止非法访问
}

4)栈的代码实现(提供另外一种思路,自己实现)

之前说过栈就像往一次只够拿一个石头的瓶子里放石头和取石头,有没有发现栈和数组有很大的相似,当我们打开这个思路,我们会发现如果用数组实现的话,我们的代码思路和代码量突然就小了很多。我这里只提供结构和功能实现前的准备,其他望诸君自己勤练。

#include<stdio.h>
#include<assert.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a; //到时候用maolloc开辟空间,可以随时调节数组大小int _top;		// 栈顶int _capacity;  // 容量 
}Stack;

最后言:数据结构是需要大量题目来练手的,单纯的理论知识是纸上谈兵,真正实现的时候是变化万千。牢记:纸上得来终觉浅,绝知此事要躬行。

相关文章:

数据结构零基础入门篇(C语言实现)

前言&#xff1a;数据结构属于C学习中较难的一部分&#xff0c;对应学习者的要求较高&#xff0c;如基础不扎实&#xff0c;建议着重学习C语言中的指针和结构体&#xff0c;万丈高楼平地起。 目录&#xff1a; 一&#xff0c;链表 1&#xff09;单链表的大致结构实现 2&…...

Hugging News #0904: 登陆 AWS Marketplace

每一周&#xff0c;我们的同事都会向社区的成员们发布一些关于 Hugging Face 相关的更新&#xff0c;包括我们的产品和平台更新、社区活动、学习资源和内容更新、开源库和模型更新等&#xff0c;我们将其称之为「Hugging News」。本期 Hugging News 有哪些有趣的消息&#xff0…...

Redis Redis的数据结构 - 通用命令 - String类型命令 - Hash类型命令

目录 Redis的数据结构&#xff1a; Redis命令&#xff1a; 通用命令&#xff1a;&#xff08;通用指令是部分数据类型的&#xff0c;都可以使用的指令&#xff09; KEYS查询命令&#xff1a; DEL删除命令&#xff1a; EXISTS判断命令&#xff1a; EXPIPE有效期设置命令&…...

vue中的几种name属性

vue中的几种name属性 组件名name name选项 export default{name:xxx } // 获取组件的name属性 this.$options.namevue-devtools调试工具里显示的组件名称&#xff1b; 未配置name选项&#xff0c;就是组件的文件名&#xff1b; vue3配置name通过defineOptions()函数 de…...

论文《面向大规模日志数据分析的自动化日志解析》翻译

论文《Towards Automated Log Parsing for Large-Scale Log Data Analysis》翻译 面向大规模日志数据分析的自动化日志解析翻译...

element-ui dialog弹窗 设置点击空白处不关闭

根据官网提供方法 场景&#xff1a;vue实现的网站有两个弹窗同时出现时&#xff0c;关闭报警&#xff0c;批量进度条弹窗也关闭了&#xff0c; 1、每一个页面都有可能出现的报警弹窗&#xff0c; 2、页面a批量操控硬件添加操作的进度条弹窗 开始以为是因为点击报警弹窗&#…...

第16节-PhotoShop基础课程-修复工具组-去水印

文章目录 前言1.污点修复画笔1.功能原理2.调整1.调整大小 Alt 右键 左右2.调整软硬 Alt 右键 上下 2.修复画笔工具 Alt 选取源1.常规2.选择图案 3.修补工具1.类型1.源2.目标 2.扩展 4.内容感知移动工具5.红眼工具 前言 去水印等 1.污点修复画笔 比如把下面的土豆&#xff08…...

conda的使用教程

conda的介绍 简单来说&#xff0c;conda软件就是来管理包的软件。以Python为例&#xff0c;在实际生活中&#xff0c;我们要处理多个不同的项目&#xff0c;因此&#xff0c;要安装不同的项目所需要的包&#xff0c;为了管理方便&#xff0c;conda就是用来打理不同项目的包&…...

客户端发现pod并与之通信

客户端发现pod并与之通信 pod需要一种寻找其他pod的方法来使用其他pod提供的服务&#xff0c;不像在没有Kubernetes的世界&#xff0c;系统管理员要在用户端配置文件中明确指出服务的精确IP地址 或者主机名来配置每个客户端应用&#xff0c;但同样的方法在Kubernetes中不适用 …...

Powershell模拟实现Linux下的tree命令

Powershell模拟实现Linux下的tree命令 代码 环境&#xff1a; P o w e r s h e l l 7 Powershell\ 7 Powershell 7 function Get-Tree {param([string]$directory ".",[int]$d 1,[switch]$f)$absolutePath Resolve-Path -Relative $directoryWrite-Host $absol…...

嵌入式基础-电路

目录 1、电流 1.1电流方向 1.2交流电和直流电 2、电压 3、电阻 4、欧姆定律 1、电流 电流是指单位时间内通过导体的电荷量&#xff0c;用符号I表示&#xff0c;单位是安培&#xff08;A&#xff09;。电流是电磁学中的基本量纲之一&#xff0c;是七个基本量纲之一。电流的…...

【JS面试题】如何通过闭包漏洞在外部修改函数中的变量

✍️ 作者简介: 前端新手学习中。 &#x1f482; 作者主页: 作者主页查看更多前端教学 &#x1f393; 专栏分享&#xff1a;css重难点教学 Node.js教学 从头开始学习 ajax学习 前端面试题 文章目录 什么是闭包例 如何在函数外部修改闭包中变量 什么是闭包 闭包这个东西对新…...

【华为OD机试】按身高和体重排队【2023 B卷|100分】

【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述: 某学校举行运动会,学生们按编号(1、2、3…n)进行标识,现需要按照身高由低到高排列, 对身高相同的人,按体重由轻到重排列; 对于身高体重都相同的人,维持原有的编号顺序关系。请输…...

TCP原理(全网最详细)

一、确认应答&#xff08;可靠性机制&#xff09; TCP诞生的初衷就是可靠传输 可靠传输是TCP最核心的部分&#xff0c;TCP内部很多机制都是在保证可靠传输&#xff08;可以理解为发一条消息&#xff0c;上面显示已读未读&#xff0c;可靠传输就是发一条消息我知道对方是否收到…...

react 初级基础

react基本使用 项目创建 项目的创建命令 npx create-react-app react-basic创建一个基本元素进行渲染 // 1 导入react 和 react-dom import React from "react"; import ReactDOM from "react-dom";// 2 创建 react 元素 React提供了创建元素的api Rea…...

linux学习书籍推荐

《Linux程序设计&#xff08;第4版&#xff09;》&#xff0c;Neil Matthew和Richard Stones编写。这本书是Linux/UNIX专家编写的&#xff0c;详细介绍了Linux系统以及其他UNIX风格的操作系统上的程序开发&#xff0c;包括标准Linux C语言函数库和各种由Linux或UNIX标准指定的工…...

LeetCode 428. Serialize and Deserialize N-ary Tree【树,BFS,DFS】困难

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

javascript | 变量、函数、属性的命名规则

javascript标识符的命名规则 变量、函数、属性的名字、或者函数的参数&#xff0c;都可称为标识符。标识符可以是按照下列格式规则组合起来的一个或者多个字符。 第一个字符必须是一个字母、下划线_、或美元符号$。数字不可以作为标识符的首字符。其他字符可以是数字、字母、…...

手写Ribbon基本原理

本文已收录于专栏 《中间件合集》 目录 概念说明什么是RibbonRibbon和Nginx负载均衡的区别 工作流程代码实现RibbonSDK发送请求端引入RibbonSDK和Nacos的依赖配置文件中填写负载均衡策略调用代码 接收请求端执行效果发送请求端接收请求端 总结提升 概念说明 什么是Ribbon Ribb…...

k8s集群中ETCD备份和恢复

文章目录 [toc]一、etcd 概述二、安装etcdctl工具三、kubeadm部署方式部署1&#xff09;备份2&#xff09;恢复四、定时备份 五、二进制部署备份1&#xff09;备份2&#xff09;恢复1、停止apiserver和etcd2、etcd_1恢复3、etcd_2恢复4、etcd_3恢复5、启动etcd和apiserver6、检…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...