🌍首页
📁归档
⏳时光机
🚩友链
📫留言
📧订阅
🌟推荐
📕考研课程
🏜️ 免费壁纸
❤ 捐助本站
💰资助名单
🎵音乐实验
Search
1
【NPN/PNP三极管】放大电路饱和失真和截止失真的区别
20,138 阅读
2
论文写作中如何把word/wps里面所有数字和字母替换为新罗马字体
10,697 阅读
3
【高数】形心计算公式讲解大全
9,075 阅读
4
Vivado-FPGA Verilog烧写固化教程
8,051 阅读
5
【概论】一阶矩、二阶矩原点矩，中心矩区别与概念
7,846 阅读
🪶微语&随笔
励志美文
我的随笔
工作办公
📡电子&通信
嵌入式＆系统
通信&信息处理
编程&脚本笔记
⌨️IC＆系统
FPGA&ASIC
VLSI&IC验证
EDA&虚拟机
💻电子&计算机
IP&SOC设计
机器学习
软硬件算法
登录
/
注册
Python(共3篇)
找到
3
篇与
Python
相关的结果
在FPGA上部署轻量BP神经网络-Python与Verilog：信号检测实战
摘要本文介绍了在FPGA上部署轻量BP神经网络进行信号检测的实战，包括系统架构、神经网络模型设计、FPGA硬件实现详解以及关键优化技巧，实验结果表明该方案功耗低、性能好。关键词：FPGA, BP神经网络, 信号检测, 低功耗, 实时处理目录 储备知识： 一、背景：为什么要在FPGA上跑神经网络？ 二、系统整体架构 三、神经网络模型设计：极致轻量 四、FPGA硬件实现详解4.1 串并转换模块（Serial-to-Parallel 4.2 数据归一化模块 4.3 隐藏层神经元模块（核心计算单元） 4.4 ReLU激活函数模块 4.5 输出层神经元模块 4.6 阈值判断模块 五、关键优化技巧5.1 归一化的"逆向"处理 5.2 权值二值化（BWN）降低功耗 5.3 亚稳态消除 六、实验结果：功耗与性能 七、总结与思考 python和verilog源程序下载 储备知识： 我们在前文讲了BP神经网络算法和激活函数 BP神经网络算法 https://ee.ac.cn/index.php/archives/612.html 激活函数讲解 https://ee.ac.cn/index.php/archives/617.html 一、背景：为什么要在FPGA上跑神经网络？ 在无源物联网（Battery-free IoT）和反向散射通信（Backscatter）场景中，传统的信号检测方法（如能量检测）虽然电路简单，但无法区分同频段的多种信号，且受噪声影响大；而基于PC或GPU的深度学习方案虽然精度高，但功耗动辄数十瓦，显然无法部署在依赖能量采集的微瓦级标签上。 核心矛盾在于：缺乏一种检测精度高、功耗极低（毫瓦级）、且能实时处理的解决方案。 答案是将轻量级的BP神经网络部署到低功耗FPGA上，在边缘端完成信号推理。 二、系统整体架构 整个检测系统的链路如下： graph LR subgraph 射频前端 A[目标信号] --> B[天线] B --> C[阻抗匹配] C --> D[LNA放大] end subgraph 信号处理 D --> E["包络检波(ENV)"] E --> F["ADC采样<br>1MSPS, 12bit"] end subgraph 智能决策 F --> G["FPGA<br>BP神经网络推理"] G --> H[调制控制信号] end在FPGA内部，BP神经网络负责识别当前输入的512点采样数据是否为目标信号的前导码（Preamble）。一旦识别成功，输出控制信号，开启后端的Backscatter调制模块。 FPGA选型：Actel IGLOO/e系列 AGLE600V5-FG484。选择它的原因是： Flash架构：上电即运行，无需外部配置芯片，适合无源系统； 超低功耗：静态功耗仅0.046mW，适合能量采集场景； 资源适中：13824个逻辑单元，足以容纳轻量级网络。 三、神经网络模型设计：极致轻量 为了在FPGA上高效部署，网络结构必须足够"轻"。本文设计的网络结构如下： pasted_1785558315326_lc6zyp.png图片 层级神经元数说明输入层512对应ADC采集的一条信号的512个采样点隐藏层2仅2个神经元，大幅降低计算量输出层1二分类：是目标信号(1) / 非目标信号(0)激活函数：隐藏层和输出层均采用 ReLU。 $$f(x) = \max(0, x)$$ 选择ReLU的原因不仅是训练效果好，更重要的是硬件实现极其简单——只需一个比较器判断正负，无需计算指数或乘法，这对FPGA非常友好。 pasted_1785561816152_bsny25.png图片 训练环境：TensorFlow/Keras，使用Adam优化器和MSE损失函数。在真实环境数据集上训练后，测试集识别准确率可达 95.76%。 pasted_1785561967835_yy5zgm.png图片 四、FPGA硬件实现详解 FPGA内部的神经网络是一个纯推理引擎。本节按数据流方向，逐个拆解每个模块的设计思路和Verilog实现要点。 pasted_1785562098406_gf64mu.png图片 整体RTL结构如下： pasted_1785563631508_f74j4w.png图片 4.1 串并转换模块（Serial-to-Parallel pasted_1785563649652_chqrj8.png图片 ADC（ADS7042）在片选信号CS拉低后，先输出2个前导0，再输出12位有效数据（D11→D0），每个数据位占用一个CLK周期。 设计要点： CS和CLK由FPGA内部产生，CS每16个CLK周期拉低一次； 在CS下降沿开始，用计数器对串行数据移位寄存； 凑齐12位有效数据后，输出一组并行数据 adc_data[11:0]。 波形图 pmhbofe.png图片 module serial_p(input data0_in,input cs,input clk,output[12:0] data0_out,input rst); reg[11:0] temp; reg[12:0] save; integer count; integer cnt; always @(negedge clk or negedge rst) begin if(!rst) begin//reset temp<=12'b000000000000; count<=-1; save<=12'b111111111111; cnt<=-1; end else if(cs&&count%16==0) begin save<={1'b0,temp}; count<=1; cnt<=cnt+1; if(cnt==512) begin cnt<=1; end end else if(cs) begin temp<=12'b0; count<=1; end else if(count<3) count<=count+1; else begin temp<={temp,data0_in}; count<=count+1; end end assign data0_out=save; endmodule 4.2 数据归一化模块 问题：训练时，输入数据被归一化到 [0, 1.8]（对应ADC参考电压1.8V）。如果在FPGA中直接用除法做 Vin = adc_data / 4095 * 1.8，会消耗大量逻辑资源（FPGA做除法器代价极高）。 解决方案：在软件端完成归一化，FPGA端只做整数运算。 具体做法： 在Python/Keras训练时，将输入数据 x 归一化为 x_norm = x / 4095 * 1.8； 在提取权值时，将第一层权值 w 除以 1.8 并放大 1024 倍取整； 这样FPGA输入的原始ADC值 adc_data（范围0~4095）直接与预处理后的权值相乘，等效于完成了归一化+加权。 # 创建一个自定义的回调对象 cb = MyCallback() # 以只读方式打开训练数据文件 with open('/content/work/data/data.txt') as traindata: # 读取文件内容 data = traindata.read() # 将文件内容转换为numpy数组，并将数据类型转换为float，并将数组形状调整为(47100, 2) data = np.array(list(data.split()), dtype=float).reshape((47100, 2)) # 创建一个最大最小归一化对象 min_max_scaler = preprocessing.MinMaxScaler() # 归一化 data = data * (1/65535) # 以只读方式打开训练标签文件 with open('/content/work/data/label.txt') as labda: # 读取文件内容 labels = labda.read() # 将文件内容转换为numpy数组，并将数据类型转换为float，并将数组形状调整为(47100, 2) labels = np.array(list(labels.split()), dtype=float).reshape((47100, 2)) # 对data和labels进行乱序，保持它们的对应关系 # 为了保持对应关系，需要先将data和labels沿着第二个维度拼接起来，形成一个(100, 4)的数组 # 然后对这个数组进行乱序，再将它们沿着第二个维度分开，还原成data和labels data_labels = np.concatenate((data, labels), axis=1) np.random.shuffle(data_labels) data = data_labels[:, :2] labels = data_labels[:, 2:]FPGA端实现： 实际上，归一化模块在FPGA中被合并到了权值预处理阶段，硬件上不需要额外的归一化电路。但为了模块化清晰，也可以显式设计一个"电压映射"模块，将12bit ADC码值转换为定点数格式： 工程建议：永远不要在FPGA里做除法。所有线性变换（归一化、缩放）都应在软件端合并到权值中，FPGA只做整数乘加。 4.3 隐藏层神经元模块（核心计算单元） 隐藏层的数学表达式： $$y = \text{ReLU}\left( \sum_{i=1}^{512} x_i \cdot w_i + b \right)$$ , i = 1..512 工程难点： 512次乘累加如果在一个时钟周期完成，需要512个乘法器，资源爆炸； 如果纯串行完成，需要512个时钟周期，一条chirp要512×512=262144个周期，太慢。 解决方案：采用 串行MAC流水线 + 双缓冲FIFO 架构。 设计思路： 权值存储：512个权值和1个偏置在编译时以 reg [31:0] w[0:511] 形式固化在FPGA中； FIFO缓存：ADC每输出一个采样点，立即写入FIFO。FIFO深度设为16即可（只要保证不溢出），因为读出速度（MAC运算）和写入速度（ADC采样）基本匹配； 串行MAC：每个时钟周期从FIFO读出一个数据 xi，与对应的 wi 相乘，累加到累加器 acc； 512个周期后：累加器结果加上偏置 b，送入ReLU模块。 pasted_1785563798085_32317i.png图片 FIFO波形图 pmhqDBt.png图片 关键设计细节： 位宽设计：输入22bit × 权值32bit = 乘法结果54bit，累加512次需要额外9bit，因此累加器至少需要 63bit。如果位宽不够，累加会溢出，导致结果完全错误。 时序约束：乘法器和加法器要满足16MHz时钟的建立保持时间。如果组合逻辑延迟太大，需要插入流水线寄存器（将乘法器和加法器分两级完成）。 双神经元并行：隐藏层有2个神经元，需要例化两个上述模块，各自独立的权值存储和累加器，但共享同一个FIFO输入。 4.4 ReLU激活函数模块 ReLU的硬件实现是整个网络中最简单的部分： pmhqWcj.png图片 module relu ( input wire clk, input wire rst_n, input wire [31:0] x_in, // MAC+bias结果 input wire x_valid, output reg [31:0] y_out, output reg y_valid ); always @(posedge clk or negedge rst_n) begin if (!rst_n) begin y_out <= 32'd0; y_valid <= 1'b0; end else begin y_valid <= x_valid; if ($signed(x_in) >= 0) y_out <= x_in; else y_out <= 32'd0; end end endmodule4.5 输出层神经元模块 输出层只有1个神经元，输入是隐藏层2个神经元的输出： $$\text{output} = \text{ReLU}\left( h_1 \cdot w'_1 + h_2 \cdot w'_2 + b' \right)$$ 这个模块与隐藏层类似，但逻辑资源消耗极小。 pmhq7NT.png图片 module nerual_out( clk, rst,x1,x2,data_out ); input clk, rst; input signed[0:49] x1,x2; output signed[79:0] data_out; //<statements> //reg signed[0:28] weight[0:1]; reg signed[0:7] save,save1,save2; localparam bais=-50'd214979034352654; //localparam bais = -26'd6406874; localparam weight0 = 29'd22506522; localparam weight1 =-29'd341584992; //integer bais; integer count; always @(negedge clk or negedge rst) begin if(!rst) //reset,set values and bias begin // bais<=-50'd214979034352654; // weight[0]<=29'd22506522; // weight[1]<=-29'd341584992; save<=0; save1<=0; save2<=0; count<=0; end else begin save1<=x1*weight0; save2<=x2*weight1; count<=count+1; if(count>518) save<=save1+save2+bais;//Multiply the input by the weights and add up the results end end assign data_out=save; endmodule4.6 阈值判断模块 为什么需要阈值判断？ 前面提到，我们在保存权值时将所有参数扩大了 1024 倍（即 $2^{10}$）。这意味着： 隐藏层的输出值也被放大了约1024倍； 输出层的计算结果同样被放大； 原本训练时，输出层ReLU后大于0即判定为目标信号； 现在由于数值被放大，不能简单以0为界，需要设定一个等效的阈值。 阈值推导： 原始判定边界：输出 > 0.5（二分类常用阈值）； 放大后等效边界：threshold = 0.5 × 1024 × 1024 = 524288； 实际上，由于隐藏层和输出层都放大了1024倍，总放大倍数为 $1024^2 = 1048576$，因此： threshold = 0.5 × 1048576 = 524288。 波形图 pmhqXv9.png图片 五、关键优化技巧 5.1 归一化的"逆向"处理 再次强调这个最重要的优化： 处理方式FPGA资源消耗推荐度FPGA内做除法（adc/4095）极高，需除法器IP❌FPGA内用移位近似除法中等，精度损失大△权值预处理（本文方法）零额外消耗✅具体做法： 训练时归一化：$V_{\text{in}} = \frac{\text{adc_data}}{4095} \times 1.8$； 提取权值时：$w' = \frac{w}{1.8} \times 1024$，取整； FPGA输入：直接使用原始ADC值 $x$（0~4095）； 等效运算。 5.2 权值二值化（BWN）降低功耗 为了进一步压缩模型、降低功耗，本文采用了 Binary-Weight-Networks (BWN) 对权值进行二值化： 权值只取 +1 或 -1； 引入缩放因子 α 保证量化后的权值尽可能接近原始浮点权值。 二值化后，乘法运算退化为加减法或符号位判断，FPGA资源占用和动态功耗大幅下降。虽然精度略有损失，但在本场景中仍能保持97%以上的识别率。 二值化乘法器的Verilog实现： // 二值化权值乘法：只需判断符号 wire signed [31:0] product; assign product = bin_weight ? x_in : -x_in; // bin_weight=1为正，0为负相比32bit×32bit的硬件乘法器，这个逻辑几乎不消耗DSP资源。 5.3 亚稳态消除 ADC数据输入和CS信号是异步信号（相对于16MHz系统时钟），必须做双级触发器同步，防止亚稳态传播： reg adc_dat_d1, adc_dat_d2; always @(posedge clk) begin adc_dat_d1 <= adc_dat; // 第一级 adc_dat_d2 <= adc_dat_d1; // 第二级（稳定后使用） end wire adc_dat_sync = adc_dat_d2;六、实验结果：功耗与性能 通过 Actel Libero SOC 对FPGA各模块进行功耗仿真，结果如下： 工作模式静态功耗动态功耗总功耗空闲态0.046 mW00.046 mW正常工作0.046 mW2.79 mW2.835 mWFlash*Freeze模式0.115 mW00.115 mW2.835 mW 的总功耗，对于低功耗设备来说是完全可以接受的。 各子模块动态功耗分解： 串并转换：0.01 mW 隐藏层神经元（含FIFO）：0.083 mW ReLU激活：0.067 mW 输出层神经元：0.067 mW 七、总结与思考 本文介绍了一套完整的从算法到硬件的轻量化神经网络部署方案： 算法层：针对低功耗约束，设计了512-2-1极简BP网络，避免使用CNN/RNN等重算力模型； 数据层：在真实环境中采集目标信号，建立含噪样本库，并通过数据增强提升泛化能力； 硬件层：基于Actel低功耗FPGA，用FIFO流水、整数运算、ReLU硬判决、权值二值化等手段，实现了毫瓦级推理； 系统层：与射频前端（LNA、包络检波、ADC）紧密配合，形成完整的标签信号检测链路。 可扩展性：该FPGA神经网络框架不仅可用于目标信号检测，只需更换训练数据集和权值参数，即可用于FMCW、RFID等其他射频信号的识别，具备良好的通用性。 python和verilog源程序下载
FPGA&ASIC
通信&信息处理
机器学习
软硬件算法
# ASIC/FPGA
# 信号处理
# 机器学习
# 软件算法
# 物联网
# Python
刘航宇
8月1日
0
56
6
2023-07-23
Python机器学习- 鸢尾花分类
摘要本文介绍了使用Python和sklearn库实现鸢尾花分类的机器学习项目。首先，通过train_and_predict函数使用高斯朴素贝叶斯分类器进行分类，然后通过transform_three2two_cate函数将数据集转化为二分类问题，并使用决策树分类器进行训练和评估，要求测试集准确率不小于0.95。关键词：Python, 机器学习, 鸢尾花分类, sklearn, 朴素贝叶斯1、描述 2、code 3、描述 4、code 1、描述 请编写代码实现train_and_predict功能，实现能够根据四个特征对三种类型的鸢尾花进行分类。 train_and_predict函数接收三个参数: train_input_features—二维NumPy数组，其中每个元素都是一个数组，它包含:萼片长度、萼片宽度、花瓣长度和花瓣宽度。 train_outputs—一维NumPy数组，其中每个元素都是一个数字，表示在train_input_features的同一行中描述的鸢尾花种类。0表示鸢尾setosa，1表示versicolor，2代表Iris virginica。 prediction_features—二维NumPy数组，其中每个元素都是一个数组，包含:萼片长度、萼片宽度、花瓣长度和花瓣宽度。 该函数使用train_input_features作为输入数据，使用train_outputs作为预期结果来训练分类器。请使用训练过的分类器来预测prediction_features的标签，并将它们作为可迭代对象返回(如list或numpy.ndarray)。结果中的第n个位置是prediction_features参数的第n行。 2、code # 导入numpy库，用于处理多维数组 import numpy as np # 导入sklearn库中的数据集、模型选择、度量和朴素贝叶斯模块 from sklearn import datasets from sklearn.model_selection import train_test_split from sklearn import metrics from sklearn.naive_bayes import GaussianNB # 定义train_and_predict函数，接收三个参数:训练输入特征、训练输出标签和预测输入特征 def train_and_predict(train_input_features, train_outputs, prediction_features): # 创建一个高斯朴素贝叶斯分类器对象 clf = GaussianNB() # 使用训练输入特征和训练输出标签来训练分类器 clf.fit(train_input_features, train_outputs) # 使用预测输入特征来预测输出标签，并将结果返回 y_pred = clf.predict(prediction_features) return y_pred # 加载鸢尾花数据集，包含150个样本，每个样本有四个特征和一个标签 iris = datasets.load_iris() # 将数据集随机分成训练集和测试集，其中训练集占70%，测试集占30%，并设置随机种子为0 X_train, X_test, y_train, y_test = train_test_split( iris.data, iris.target, test_size=0.3, random_state=0 ) # 调用train_and_predict函数，使用训练集来训练分类器，并使用测试集来预测标签，将结果赋值给y_pred y_pred = train_and_predict(X_train, y_train, X_test) # 如果y_pred不为空，打印预测标签和真实标签的准确率，即正确预测的比例 if y_pred is not None: print(metrics.accuracy_score(y_test, y_pred))3、描述 机器学习库 sklearn 自带鸢尾花分类数据集，分为四个特征和三个类别，其中这三个类别在数据集中分别表示为 0, 1 和 2，请实现 transform_three2two_cate 函数的功能，该函数是一个无参函数，要求将数据集中 label 为 2 的数据进行移除，也就是说仅保留 label 为 0 和为 1 的情况，并且对 label 为 0 和 1 的特征数据进行保留，返回值为 numpy.ndarray 格式的训练特征数据和 label 数据，分别为命名为 new_feat 和 new_label。 然后在此基础上，实现 train_and_evaluate 功能，并使用生成的 new_feat 和 new_label 数据集进行二分类训练，限定机器学习分类器只能从逻辑回归和决策树中进行选择，将训练数据和测试数据按照 8:2 的比例进行分割。 要求输出测试集上的 accuracy_score，同时要求 accuracy_score 要不小于 0.95。 4、code #导入numpy库，它是一个提供了多维数组和矩阵运算等功能的Python库 import numpy as np #导入sklearn库中的datasets模块，它提供了一些内置的数据集 from sklearn import datasets #导入sklearn库中的model_selection模块，它提供了一些用于模型选择和评估的工具，比如划分训练集和测试集 from sklearn.model_selection import train_test_split #导入sklearn库中的preprocessing模块，它提供了一些用于数据预处理的工具，比如归一化 from sklearn.preprocessing import MinMaxScaler #导入sklearn库中的linear_model模块，它提供了一些线性模型，比如逻辑回归 from sklearn.linear_model import LogisticRegression #导入sklearn库中的metrics模块，它提供了一些用于评估模型性能的指标，比如F1分数、ROC曲线面积、准确率等 from sklearn.metrics import f1_score,roc_auc_score,accuracy_score #导入sklearn库中的tree模块，它提供了一些树形模型，比如决策树 from sklearn.tree import DecisionTreeClassifier #定义一个函数transform_three2two_cate，它的作用是将鸢尾花数据集中的三分类问题转化为二分类问题 def transform_three2two_cate(): #从datasets模块中加载鸢尾花数据集，并赋值给data变量 data = datasets.load_iris() #其中data特征数据的key为data，标签数据的key为target #需要取出原来的特征数据和标签数据，移除标签为2的label和特征数据，返回值new_feat为numpy.ndarray格式特征数据，new_label为对应的numpy.ndarray格式label数据 #需要注意特征和标签的顺序一致性，否则数据集将混乱 #code start here #使用numpy库中的where函数找出标签为2的索引，并赋值给index_arr变量 index_arr = np.where(data.target == 2)[0] #使用numpy库中的delete函数删除特征数据中对应索引的行，并赋值给new_feat变量 new_feat = np.delete(data.data, index_arr, 0) #使用numpy库中的delete函数删除标签数据中对应索引的元素，并赋值给new_label变量 new_label = np.delete(data.target, index_arr) #code end here #返回新的特征数据和标签数据 return new_feat,new_label #定义一个函数train_and_evaluate，它的作用是用决策树分类器来训练和评估鸢尾花数据集 def train_and_evaluate(): #调用transform_three2two_cate函数，得到新的特征数据和标签数据，并赋值给data_X和data_Y变量 data_X,data_Y = transform_three2two_cate() #使用train_test_split函数，将数据集划分为训练集和测试集，其中测试集占20%，并赋值给train_x,test_x,train_y,test_y变量 train_x,test_x,train_y,test_y = train_test_split(data_X,data_Y,test_size = 0.2) #已经划分好训练集和测试集，接下来请实现对数据的训练 #code start here #创建一个决策树分类器的实例，并赋值给estimator变量 estimator = DecisionTreeClassifier() #使用fit方法，用训练集的特征和标签来训练决策树分类器 estimator.fit(train_x, train_y) #使用predict方法，用测试集的特征来预测标签，并赋值给y_predict变量 y_predict = estimator.predict(test_x) #code end here #注意模型预测的label需要定义为 y_predict，格式为list或numpy.ndarray #使用accuracy_score函数，计算测试集上的准确率分数，并打印出来 print(accuracy_score(y_predict,test_y)) #如果这个文件是作为主程序运行，则执行以下代码 if __name__ == "__main__": #调用train_and_evaluate函数 train_and_evaluate() #要求执行train_and_evaluate()后输出为： #1、{0,1}，代表数据label为0和1 #2、测试集上的准确率分数，要求>0.95
机器学习
# 机器学习
# Python
刘航宇
3年前
0
591
0
算法-反转链表C&Python实现
摘要本文介绍了如何使用C++和Python实现单链表的反转。文章首先回顾了空间复杂度和时间复杂度的概念，然后分别给出了C++和Python的实现代码，包括初始化指针、遍历链表和反转节点指向的步骤。关键词：算法, 反转链表, C++, Python, 空间复杂度描述 基础数据结构知识回顾 题解C++篇 题解Python篇 描述 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。 数据范围： 0≤n≤1000 要求：空间复杂度 O(1) ，时间复杂度 O(n) 。 如当输入链表{1,2,3}时， 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。 以上转换过程如下图所示： pCqibqO.png图片 基础数据结构知识回顾 空间复杂度 O (1) 表示算法执行所需要的临时空间不随着某个变量 n 的大小而变化，即此算法空间复杂度为一个常量，可表示为 O (1)。例如，下面的代码中，变量 i、j、m 所分配的空间都不随着 n 的变化而变化，因此它的空间复杂度是 O (1)。 int i = 1; int j = 2; ++i; j++; int m = i + j;时间复杂度 O (n) 表示算法执行的时间与 n 成正比，即此算法时间复杂度为线性阶，可表示为 O (n)。例如，下面的代码中，for 循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此这类代码都可以用 O (n) 来表示它的时间复杂度。 for (i=1; i<=n; ++i) { j = i; j++; }题解C++篇 可以先用一个vector将单链表的指针都存起来，然后再构造链表。 此方法简单易懂，代码好些。 // 定义一个Solution类 class Solution { public: // 定义一个函数，接收一个链表的头节点指针，返回一个反转后的链表的头节点指针 ListNode* ReverseList(ListNode* pHead) { // 如果头节点指针为空，直接返回空指针 if (!pHead) return nullptr; // 定义一个vector，用于存储链表中的每个节点指针 vector<ListNode*> v; // 遍历链表，将每个节点指针放入vector中 while (pHead) { v.push_back(pHead); pHead = pHead->next; } // 反转vector，也可以逆向遍历 reverse(v.begin(), v.end()); // 取出vector中的第一个元素，作为反转后的链表的头节点指针 ListNode *head = v[0]; // 定义一个当前节点指针，初始化为头节点指针 ListNode *cur = head; // 从第二个元素开始遍历vector，构造反转后的链表 for (int i=1; i<v.size(); ++i) { // 当前节点的下一个指针指向下一个节点 cur->next = v[i]; // 当前节点后移 cur = cur->next; } // 切记最后一个节点的下一个指针指向nullptr cur->next = nullptr; // 返回反转后的链表的头节点指针 return head; } };初始化：3个指针 1）pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr 2）cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head 3）nex指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存 接下来，循环执行以下三个操作 1）nex = cur->next, 保存作用 2）cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点 3）pre = cur， cur = nex; 指针后移，操作下一个未反转链表的第一个节点 循环条件，当然是cur != nullptr 循环结束后，cur当然为nullptr，所以返回pre，即为反转后的头结点 这里以1->2->3->4->5 举例： pCqAcsP.png图片 pCqAgqf.png图片 pCqAWdS.png图片 pCqA4iQ.png图片 pCqAIRs.png图片 // 定义一个Solution类 class Solution { public: // 定义一个函数，接收一个链表的头节点指针，返回一个反转后的链表的头节点指针 ListNode* ReverseList(ListNode* pHead) { // 定义一个前驱节点指针，初始化为nullptr ListNode *pre = nullptr; // 定义一个当前节点指针，初始化为头节点指针 ListNode *cur = pHead; // 定义一个后继节点指针，初始化为nullptr ListNode *nex = nullptr; // 遍历链表，反转每个节点的指向 while (cur) { // 记录当前节点的下一个节点 nex = cur->next; // 将当前节点的下一个指针指向前驱节点 cur->next = pre; // 将前驱节点更新为当前节点 pre = cur; // 将当前节点更新为后继节点 cur = nex; } // 返回反转后的链表的头节点指针，即原链表的尾节点指针 return pre; } };题解Python篇 假设 链表为 1->2->3->4->null 空就是链表的尾 obj： 4->3->2->1->null 那么逻辑是 首先设定待反转链表的尾 pre = none head 代表一个动态的表头 逐步取下一次链表的值 然后利用temp保存 head.next 第一次迭代head为1 temp 为2 原始链表中是1->2 现在我们需要翻转 即 令head.next = pre 实现 1->none 但此时链表切断了 变成了 1->none 2->3->4 所以我们要移动指针，另pre = head 也就是pre从none 变成1 下一次即可完成2->1的链接 此外另head = next 也就是说 把指针移动到后面仍然链接的链表上 这样执行下一次循环 则实现 把2->3 转变为 2->1->none 然后再次迭代 直到最后一次 head 变成了none 而pre变成了4 则pre是新的链表的表头 完成翻转 # -*- coding:utf-8 -*- # 定义一个ListNode类，表示链表中的节点 # class ListNode: # def __init__(self, x): # self.val = x # 节点的值 # self.next = None # 节点的下一个指针 # 定义一个Solution类，用于解决问题 class Solution: # 定义一个函数，接收一个链表的头节点，返回一个反转后的链表的头节点 def ReverseList(self, pHead): # write code here pre = None # 定义一个前驱节点，初始化为None head = pHead # 定义一个当前节点，初始化为头节点 while head: # 遍历链表，反转每个节点的指向 temp = head.next # 记录当前节点的下一个节点 head.next = pre # 将当前节点的下一个指针指向前驱节点 pre = head # 将前驱节点更新为当前节点 head = temp # 将当前节点更新为下一个节点 return pre # 返回反转后的链表的头节点，即原链表的尾节点
编程&脚本笔记
软硬件算法
# 软件算法
# C/C++
# Python
刘航宇
3年前
0
390
2
