首页 文章 精选 留言 我的

精选列表

搜索[国密算法]，共10000篇文章
优秀的个人博客,低调大师

骨灰级乐高粉讲述：我是怎么用算法给两吨积木自动分类的

本文来自AI新媒体量子位（QbitAI） 本文的作者Jacques Mattheij自小就是一名乐高粉。在接触乐高的过程中，他发现了这么一种现象：不同种类的乐高售价是不同的。比如精装乐高的售价大概是每公斤40欧元，散装的乐高只需要10欧元；而一些限量、稀有版本以及乐高机械组的售价能达到每公斤100欧元。 为此甚至有人专门去买那些散装和精装新品的乐高，然后把它们进行重新分类以获取更高的价值。 然而，手动给那些千奇百怪的乐高分类看上去并不是个好主意。于是Mattheij某日突发奇想，决定尝试用机器干这件事。他在各个拍卖网站上拍下了能装满一整车库的乐高（运回来途中还丢了辆卡车）来做这个实验。 这是Mattheij在个人网站上发布的第二篇帖子，讲的是他为给这堆乐高分类而在软件上尝试过的方法；在第一篇帖子里，他介绍了硬件方面的准备和面临的困难。 我们
2018-01-15
优秀的个人博客,低调大师

Hyperledger Fabric无排序组织以Raft共识算法启动多个Orderer服务、多组织共同运行维护Orderer服务

前言 在Hyperledger Fabric无系统通道启动及通道的创建和删除中，我们已经完成了以无系统通道的方式启动 Hyperledger Fabric 网络，并将链码安装到指定通道。但目前为止，实验中的 orderer 服务都是通过单独的排序组织来维护且只有一个，那能不能不要排序组织而使用普通组织来运行维护多个 orderer 服务呢？当然是可以的，本文将在之前的实验基础上，启动一个没有 orderer 组织的 Fabric 网络，网络中包含三个组织且每个组织运行维护着一个 Raft 协议的 orderer 节点，最后成功在其上部署运行链码。 背景介绍 实验准备 本文网络结构直接将 Hyperledger Fabric无系统通道启动及通道的创建和删除 中创建的 3_RunWithNoSystemChannel 复制为 4-1_RunOrdererByOneself （建议直接将本案例仓库 FabricLearn 下的 4-1_RunOrdererByOneself 目录拷贝到本地运行）。默认情况下，所有命令皆在 4-1_RunOrdererByOneself 根目录下执行，在开始后面的实验前按照以下命令启动基础实验网络（主要修改为删除 orderer 组织相关配置）： 设置环境变量 source envpeer1soft 启动CA网络 ./0_Restart.sh 本实验初始 docker 网络为： 本文工作 以无排序组织的方式启动 Hyperledger Fabric 网络，其中包含三个组织—— soft 、 web 、 hard ， 每个组织都运行维护着一个 peer 节点和一个 orderer，并使用 osnadmin 工具通过 orderer 的 admin 服务使 orderer 加入这两条通道（实验代码已上传至：https://github.com/wefantasy/FabricLearn 的 4-1_RunOrdererByOneself 下）： 项 运行端口 说明 council.ifantasy.net 7050 council 组织的 CA 服务， 为联盟链网络提供 TLS-CA 服务 soft.ifantasy.net 7250 soft 组织的 CA 服务， 包含成员： peer1 、 admin1 peer1.soft.ifantasy.net 7251 soft 组织的 peer1 成员节点 orderer1.soft.ifantasy.net 8251 soft 组织的 orderer1 服务 orderer1.soft.ifantasy.net 8252 soft 组织的 orderer1 服务的 admin 服务 web.ifantasy.net 7350 web 组织的 CA 服务， 包含成员： peer1 、 admin1 peer1.web.ifantasy.net 7351 web 组织的 peer1 成员节点 orderer1.soft.ifantasy.net 8351 web 组织的 orderer1 服务 orderer1.soft.ifantasy.net 8352 web 组织的 orderer1 服务的 admin 服务 hard.ifantasy.net 7450 hard 组织的 CA 服务， 包含成员： peer1 、 admin1 peer1.hard.ifantasy.net 7451 hard 组织的 peer1 成员节点 orderer1.soft.ifantasy.net 8451 hard 组织的 orderer1 服务 orderer1.soft.ifantasy.net 8452 hard 组织的 orderer1 服务的 admin 服务 实验步骤 配置文件 修改配置文件 compose/docker-compose.yaml ，删除所有关于 orderer 组织的配置，并新增 hard 组织相关容器和普通组织的 orderer 容器： hard.ifantasy.net: container_name: hard.ifantasy.net extends: file: docker-base.yaml service: ca-base command: sh -c 'fabric-ca-server start -d -b ca-admin:ca-adminpw --port 7050' environment: - FABRIC_CA_SERVER_CSR_CN=hard.ifantasy.net - FABRIC_CA_SERVER_CSR_HOSTS=hard.ifantasy.net volumes: - ${LOCAL_CA_PATH}/hard.ifantasy.net/ca:${DOCKER_CA_PATH}/ca ports: - 7450:7050 peer1.hard.ifantasy.net: container_name: peer1.hard.ifantasy.net extends: file: docker-base.yaml service: peer-base environment: - CORE_PEER_ID=peer1.hard.ifantasy.net - CORE_PEER_LISTENADDRESS=0.0.0.0:7051 - CORE_PEER_ADDRESS=peer1.hard.ifantasy.net:7051 - CORE_PEER_LOCALMSPID=hardMSP - CORE_PEER_GOSSIP_EXTERNALENDPOINT=peer1.hard.ifantasy.net:7051 volumes: - ${LOCAL_CA_PATH}/hard.ifantasy.net/registers/peer1:${DOCKER_CA_PATH}/peer ports: - 7451:7051 orderer1.soft.ifantasy.net: container_name: orderer1.soft.ifantasy.net extends: file: docker-base.yaml service: orderer-base environment: - ORDERER_HOST=orderer1.soft.ifantasy.net - ORDERER_GENERAL_LOCALMSPID=softMSP - ORDERER_GENERAL_LISTENPORT=8251 volumes: - ${LOCAL_CA_PATH}/soft.ifantasy.net/registers/orderer1:${DOCKER_CA_PATH}/orderer ports: - 8251:8251 - 8252:8888 - 8253:9999 orderer1.web.ifantasy.net: container_name: orderer1.web.ifantasy.net extends: file: docker-base.yaml service: orderer-base environment: - ORDERER_HOST=orderer1.web.ifantasy.net - ORDERER_GENERAL_LOCALMSPID=webMSP - ORDERER_GENERAL_LISTENPORT=8351 volumes: - ${LOCAL_CA_PATH}/web.ifantasy.net/registers/orderer1:${DOCKER_CA_PATH}/orderer ports: - 8351:8351 - 8352:8888 - 8353:9999 orderer1.hard.ifantasy.net: container_name: orderer1.hard.ifantasy.net extends: file: docker-base.yaml service: orderer-base environment: - ORDERER_HOST=orderer1.hard.ifantasy.net - ORDERER_GENERAL_LOCALMSPID=hardMSP - ORDERER_GENERAL_LISTENPORT=8451 volumes: - ${LOCAL_CA_PATH}/hard.ifantasy.net/registers/orderer1:${DOCKER_CA_PATH}/orderer ports: - 8451:8451 - 8452:8888 - 8453:9999 修改配置文件 config/configtx.yaml ，源文件太长在此不贴，其主要修改内容为： 每个组织 MSP 下增加本组织维护的 OrdererEndpoints 配置： Orderer 配置下修改 orderer 服务的地址： Profiles 配置下修改排序节点的维护组织为 softMSP 、 webMSP 、 hardMSP： 必须有一个组织 MSP 的 Policies 中的 Readers 和 Writers 下 Rule 值为 member ，文末会有解释： 各组织的环境变量文件中添加 orderer 服务的管理证书环境变量，以 envpeer1soft 为例： export ORDERER_CA=$LOCAL_CA_PATH/soft.ifantasy.net/registers/orderer1/tls-msp/tlscacerts/tls-council-ifantasy-net-7050.pem export ORDERER_ADMIN_TLS_SIGN_CERT=$LOCAL_CA_PATH/soft.ifantasy.net/registers/orderer1/tls-msp/signcerts/cert.pem export ORDERER_ADMIN_TLS_PRIVATE_KEY=$LOCAL_CA_PATH/soft.ifantasy.net/registers/orderer1/tls-msp/keystore/key.pem 将 envpeer1soft 复制为 envpeer1hard 作为 hard 组织的环境变量，其内容为： export LOCAL_ROOT_PATH=$PWD export LOCAL_CA_PATH=$LOCAL_ROOT_PATH/orgs export DOCKER_CA_PATH=/tmp export COMPOSE_PROJECT_NAME=fabriclearn export DOCKER_NETWORKS=network export FABRIC_BASE_VERSION=2.4 export FABRIC_CA_VERSION=1.5 echo "init terminal hard" export FABRIC_CFG_PATH=$LOCAL_ROOT_PATH/config export CORE_PEER_TLS_ENABLED=true export CORE_PEER_LOCALMSPID="hardMSP" export CORE_PEER_ADDRESS=peer1.hard.ifantasy.net:7451 export CORE_PEER_TLS_ROOTCERT_FILE=$LOCAL_CA_PATH/hard.ifantasy.net/assets/tls-ca-cert.pem export CORE_PEER_MSPCONFIGPATH=$LOCAL_CA_PATH/hard.ifantasy.net/registers/admin1/msp export ORDERER_CA=$LOCAL_CA_PATH/hard.ifantasy.net/registers/orderer1/tls-msp/tlscacerts/tls-council-ifantasy-net-7050.pem export ORDERER_ADMIN_TLS_SIGN_CERT=$LOCAL_CA_PATH/hard.ifantasy.net/registers/orderer1/tls-msp/signcerts/cert.pem export ORDERER_ADMIN_TLS_PRIVATE_KEY=$LOCAL_CA_PATH/hard.ifantasy.net/registers/orderer1/tls-msp/keystore/key.pem 注册用户 在注册脚本 1_RegisterUser.sh 中删除 orderer 组织账户并添加三组织排序服务的 msp 账户和 tls-msp 账户，默认密码与账户名相同： 登录账户 在登录脚本 2_EnrollUser.sh 中删除 orderer 组织相关内容并添加三组织排序服务的 msp 账户和 tls-msp 账户，如 soft 组织下新增登录 orderer1 的代码： echo "Enroll Orderer1" export FABRIC_CA_CLIENT_HOME=$LOCAL_CA_PATH/soft.ifantasy.net/registers/orderer1 export FABRIC_CA_CLIENT_TLS_CERTFILES=$LOCAL_CA_PATH/soft.ifantasy.net/assets/ca-cert.pem export FABRIC_CA_CLIENT_MSPDIR=msp fabric-ca-client enroll -d -u https://orderer1:orderer1@soft.ifantasy.net:7250 # for TLS export FABRIC_CA_CLIENT_MSPDIR=tls-msp export FABRIC_CA_CLIENT_TLS_CERTFILES=$LOCAL_CA_PATH/soft.ifantasy.net/assets/tls-ca-cert.pem fabric-ca-client enroll -d -u https://orderer1soft:orderer1soft@council.ifantasy.net:7050 --enrollment.profile tls --csr.hosts orderer1.soft.ifantasy.net cp $LOCAL_CA_PATH/soft.ifantasy.net/registers/orderer1/tls-msp/keystore/*_sk $LOCAL_CA_PATH/soft.ifantasy.net/registers/orderer1/tls-msp/keystore/key.pem mkdir -p $LOCAL_CA_PATH/soft.ifantasy.net/registers/orderer1/msp/admincerts cp $LOCAL_CA_PATH/soft.ifantasy.net/registers/admin1/msp/signcerts/cert.pem $LOCAL_CA_PATH/soft.ifantasy.net/registers/orderer1/msp/admincerts/cert.pem 创建通道并加入 在执行上述脚本后，在脚本 3_CreateChannel.sh 中创建通道并使所有节点加入： 启动 peer 和 orderer 容器： docker-compose -f $LOCAL_ROOT_PATH/compose/docker-compose.yaml up -d peer1.soft.ifantasy.net peer1.web.ifantasy.net peer1.hard.ifantasy.net docker-compose -f $LOCAL_ROOT_PATH/compose/docker-compose.yaml up -d orderer1.soft.ifantasy.net orderer1.web.ifantasy.net orderer1.hard.ifantasy.net 此时本实验所有容器启动完成： 2. 创建通道文件 testchannel ： configtxgen -profile OrgsChannel -outputCreateChannelTx $LOCAL_ROOT_PATH/data/testchannel.tx -channelID testchannel configtxgen -profile OrgsChannel -outputBlock $LOCAL_ROOT_PATH/data/testchannel.block -channelID testchannel soft 组织的 orderer 服务加入通道： source envpeer1soft osnadmin channel list -o orderer1.soft.ifantasy.net:8252 --ca-file $ORDERER_CA --client-cert $ORDERER_ADMIN_TLS_SIGN_CERT --client-key $ORDERER_ADMIN_TLS_PRIVATE_KEY osnadmin channel join -o orderer1.soft.ifantasy.net:8252 --channelID testchannel --config-block $LOCAL_ROOT_PATH/data/testchannel.block --ca-file "$ORDERER_CA" --client-cert "$ORDERER_ADMIN_TLS_SIGN_CERT" --client-key "$ORDERER_ADMIN_TLS_PRIVATE_KEY" osnadmin channel list -o orderer1.soft.ifantasy.net:8252 --ca-file $ORDERER_CA --client-cert $ORDERER_ADMIN_TLS_SIGN_CERT --client-key $ORDERER_ADMIN_TLS_PRIVATE_KEY web 组织的 orderer 服务加入通道： source envpeer1web osnadmin channel list -o orderer1.web.ifantasy.net:8352 --ca-file $ORDERER_CA --client-cert $ORDERER_ADMIN_TLS_SIGN_CERT --client-key $ORDERER_ADMIN_TLS_PRIVATE_KEY osnadmin channel join -o orderer1.web.ifantasy.net:8352 --channelID testchannel --config-block $LOCAL_ROOT_PATH/data/testchannel.block --ca-file "$ORDERER_CA" --client-cert "$ORDERER_ADMIN_TLS_SIGN_CERT" --client-key "$ORDERER_ADMIN_TLS_PRIVATE_KEY" osnadmin channel list -o orderer1.web.ifantasy.net:8352 --ca-file $ORDERER_CA --client-cert $ORDERER_ADMIN_TLS_SIGN_CERT --client-key $ORDERER_ADMIN_TLS_PRIVATE_KEY hard 组织的 orderer 服务加入通道： source envpeer1hard osnadmin channel list -o orderer1.hard.ifantasy.net:8452 --ca-file $ORDERER_CA --client-cert $ORDERER_ADMIN_TLS_SIGN_CERT --client-key $ORDERER_ADMIN_TLS_PRIVATE_KEY osnadmin channel join -o orderer1.hard.ifantasy.net:8452 --channelID testchannel --config-block $LOCAL_ROOT_PATH/data/testchannel.block --ca-file "$ORDERER_CA" --client-cert "$ORDERER_ADMIN_TLS_SIGN_CERT" --client-key "$ORDERER_ADMIN_TLS_PRIVATE_KEY" osnadmin channel list -o orderer1.hard.ifantasy.net:8452 --ca-file $ORDERER_CA --client-cert $ORDERER_ADMIN_TLS_SIGN_CERT --client-key $ORDERER_ADMIN_TLS_PRIVATE_KEY 将通道文件复制到各组织资产目录下： cp $LOCAL_ROOT_PATH/data/testchannel.block $LOCAL_CA_PATH/soft.ifantasy.net/assets/ cp $LOCAL_ROOT_PATH/data/testchannel.block $LOCAL_CA_PATH/web.ifantasy.net/assets/ cp $LOCAL_ROOT_PATH/data/testchannel.block $LOCAL_CA_PATH/hard.ifantasy.net/assets/ 各组织 peer 节点加入通道： cp $LOCAL_ROOT_PATH/data/testchannel.block $LOCAL_CA_PATH/soft.ifantasy.net/assets/ cp $LOCAL_ROOT_PATH/data/testchannel.block $LOCAL_CA_PATH/web.ifantasy.net/assets/ cp $LOCAL_ROOT_PATH/data/testchannel.block $LOCAL_CA_PATH/hard.ifantasy.net/assets/ 部署测试链码 在执行上述脚本后，在脚本 4_TestChaincode.sh 中安装链码并调用执行： 各组织安装测试链码： source envpeer1soft # peer lifecycle chaincode package basic.tar.gz --path asset-transfer-basic/chaincode-go --label basic_1 peer lifecycle chaincode install basic.tar.gz peer lifecycle chaincode queryinstalled source envpeer1web peer lifecycle chaincode install basic.tar.gz peer lifecycle chaincode queryinstalled source envpeer1hard peer lifecycle chaincode install basic.tar.gz peer lifecycle chaincode queryinstalled 设置链码 ID 环境变量： export CHAINCODE_ID=basic_1:06613e463ef6694805dd896ca79634a2de36fdf019fa7976467e6e632104d718 soft 组织批准链码： source envpeer1soft peer lifecycle chaincode approveformyorg -o orderer1.soft.ifantasy.net:8251 --tls --cafile $ORDERER_CA --channelID testchannel --name basic --version 1.0 --sequence 1 --waitForEvent --init-required --package-id $CHAINCODE_ID peer lifecycle chaincode queryapproved -C testchannel -n basic --sequence 1 web 组织批准链码： source envpeer1web peer lifecycle chaincode approveformyorg -o orderer1.web.ifantasy.net:8351 --tls --cafile $ORDERER_CA --channelID testchannel --name basic --version 1.0 --sequence 1 --waitForEvent --init-required --package-id $CHAINCODE_ID peer lifecycle chaincode queryapproved -C testchannel -n basic --sequence 1 hard 组织批准链码： source envpeer1hard peer lifecycle chaincode approveformyorg -o orderer1.hard.ifantasy.net:8451 --tls --cafile $ORDERER_CA --channelID testchannel --name basic --version 1.0 --sequence 1 --waitForEvent --init-required --package-id $CHAINCODE_ID peer lifecycle chaincode queryapproved -C testchannel -n basic --sequence 1 注意，这里各组织批准链码时的 -o 参数可以指定任意一个 orderer 服务。 4. 检查链码批准情况： peer lifecycle chaincode checkcommitreadiness -o orderer1.soft.ifantasy.net:8251 --tls --cafile $ORDERER_CA --channelID testchannel --name basic --version 1.0 --sequence 1 --init-required 测试调用链码： source envpeer1soft peer lifecycle chaincode commit -o orderer1.soft.ifantasy.net:8251 --tls --cafile $ORDERER_CA --channelID testchannel --name basic --init-required --version 1.0 --sequence 1 --peerAddresses peer1.soft.ifantasy.net:7251 --tlsRootCertFiles $CORE_PEER_TLS_ROOTCERT_FILE --peerAddresses peer1.web.ifantasy.net:7351 --tlsRootCertFiles $CORE_PEER_TLS_ROOTCERT_FILE peer lifecycle chaincode querycommitted --channelID testchannel --name basic -o orderer1.soft.ifantasy.net:8251 --tls --cafile $ORDERER_CA --peerAddresses peer1.soft.ifantasy.net:7251 --tlsRootCertFiles $CORE_PEER_TLS_ROOTCERT_FILE peer chaincode invoke --isInit -o orderer1.soft.ifantasy.net:8251 --tls --cafile $ORDERER_CA --channelID testchannel --name basic --peerAddresses peer1.soft.ifantasy.net:7251 --tlsRootCertFiles $CORE_PEER_TLS_ROOTCERT_FILE --peerAddresses peer1.web.ifantasy.net:7351 --tlsRootCertFiles $CORE_PEER_TLS_ROOTCERT_FILE -c '{"Args":["InitLedger"]}' sleep 3 peer chaincode invoke -o orderer1.soft.ifantasy.net:8251 --tls --cafile $ORDERER_CA --channelID testchannel --name basic --peerAddresses peer1.soft.ifantasy.net:7251 --tlsRootCertFiles $CORE_PEER_TLS_ROOTCERT_FILE --peerAddresses peer1.web.ifantasy.net:7351 --tlsRootCertFiles $CORE_PEER_TLS_ROOTCERT_FILE -c '{"Args":["GetAllAssets"]}' 常见错误 没有领导节点 Error: failed to send transaction: got unexpected status: SERVICE_UNAVAILABLE -- no Raft leader 上述错误归结起来就是 orderer 之间没有选出领导节点，此时应该检查： 网络中 orderer 节点的数量是否为 2n+1 个，否则可能无法完成选举 各 orderer 容器的 ORDERER_GENERAL_LOCALMSPID 配置是否正确，必须为自身所属组织的 MSPID 检查 configtx.yaml 中各组织的 Policies 配置是否正确 排序节点之间无法通信 2022-04-09 05:32:07.086 UTC 0032 ERRO [orderer.consensus.etcdraft] logSendFailure -> Failed to send StepRequest to 3, because: rpc error: code = Unavailable desc = connection error: desc = "transport: Error while dialing dial tcp 172.19.0.10:8451: connect: connection refused" channel=syschannel node=1 上述错误的原因是 orderer 节点间无法通信， 此时应该检查 configtx.yaml 中相关的 orderer 地址是否正确。这里有个大坑：所有 configtx.yaml 文件内的 orderer 相关配置的端口必须设置为容器内 ORDERER_GENERAL_LISTENPORT 的监听端口，而不是容器外的映射端口，假如 orderer 容器配置如下图， configtx.yaml 中的 orderer 端口必须为 7050 而不能填 8251 （所以为了避免冲突，强烈建议这两个端口设置成一样的 8251）。 peer 节点之间无法通信 Error: timed out waiting for txid on all peers 2022-04-10 02:57:37.135 UTC 00a1 WARN [peer.blocksprovider] DeliverBlocks -> Got error while attempting to receive blocks: block from orderer could not be verified: implicit policy evaluation failed - 0 sub-policies were satisfied, but this policy requires 1 of the 'Writers' sub-policies to be satisfied channel=testchannel orderer-address=orderer1.soft.ifantasy.net:8251 错误原因是没有操作权限，通常是 configtx.yaml 中的策略问题，在本实验中如果三个组织的 Policies 都设置为下列内容则会触发本错误： Policies: Readers: Type: Signature Rule: "OR('softMSP.admin', 'softMSP.peer', 'softMSP.client')" Writers: Type: Signature Rule: "OR('softMSP.admin', 'softMSP.client')" Admins: Type: Signature Rule: "OR('softMSP.admin')" Endorsement: Type: Signature Rule: "OR('softMSP.peer')" 此时需要将任意组织（比如 web）的 Readers 和 Writers 的 Rule 改为 menber 即可解决，解决后实验各步骤结果符合预期： Policies: Readers: Type: Signature Rule: "OR('webMSP.member')" Writers: Type: Signature Rule: "OR('webMSP.member')" Admins: Type: Signature Rule: "OR('webMSP.admin')" Endorsement: Type: Signature Rule: "OR('webMSP.peer')" 至于为什么会导致如此尚未发现，猜测是普通组织的策略与排序节点所需要的策略存在冲突，因此建议排序服务独立于普通组织。
2022-04-12
优秀的个人博客,低调大师

数据结构与算法 | 来来来，让我们重新认识一下什么是树

Hi! 大家好，我是小小，我们开始今天的内容，今天主要讲解什么是树。 树的递归结构 从一张图中解释什么是树这张图，主要讲解关于cart这个单词的所有的可能组合，按照常理，需要先考虑三个字母的排列，然后对三个字母进行拆分，直到最后一个节点，这个过程就类似于树 到底什么是树 什么是树 树是节点集合(A tree is a collection of nodes)， 集合：集合是允许一个元素都没有的集合，称之为空集。 首先，集合是允许一个元素都没有的集合，称之为空集，那么书是不是也允许一个节点都没有的呢，是的，一个节点都没有的树，称之为空树，如果不是空的，则会存在根节点r和零个或更多非空子树，T1，T2.。。Tk，他们的根由来自r的有向连接，什么叫有向边，大致可以理解为箭头。用图的关系说明树的内部关系 根节点（root）一棵树只有一个跟节点，所有的节点都在该节点的下面，尝试把图倒过来看，可以看成一个我们日常见到的数的根部，在这里显然字母A就是这颗树的根节点。 子节点，父节点，一个节点，它对应的下面有连这的节点，那么被连着的节点就是这个节点的子节点，也叫做孩子，那么这个节点叫做被连接的节点的父亲，看图，B被A连这，所以B是A的一个孩子，同理，CDE等等这一行都是A的孩子，同时F，它连这K L M 同时被A连这，那么F是A的一个孩子，同时又是K L M 的父亲。 树叶：树叶就是那些没有孩子的节点，比如B，C，D等等，例如下图的绿色部分。 兄弟: 按照我们的理解，同一个父母生的当然是兄妹，如下图所示，颜色相同的都是兄妹 路径 我们同样可以定义从父亲到他孩子的路径，下面的路径，我们就取上图的一部分，一个子树，作为例子比如，A->O的路径为A->E->J->O它的长度为3，实际为它的边数，图中红色的部分。 节点的深度：节点的深度指的是节点到树根的长度，看下图，我们可以轻易的知道，j节点的深度为2，可以理解为 A-> E -> J 边长为2.显然，此时根节点的深度为0. 节点的高度：高度是从节点到叶子的最长路径，比如节点F的高度为1，显然所有叶子节点高度为0. 树的高度，树的高度是跟的高度，显然在这图中，树的高度为3，A->O 树的特点 按照正常的逻辑，一个人不能同时有两个父亲，所以树也一样，下图的两个就解释了这个问题 一颗正常的树，它的树枝是不会长成一个圆的，所以，树中，是不可能出现环形的。图中，红色箭头构成了一个环，所以都不是一颗树。 树的存储结构 树的存储结构有三种，分别为，双亲表示法，孩子表示法，孩子兄弟表示法。 双亲表示法 假设一组连续空间保存着树的特点，同时在每个节点中，附带一个指示器表示双亲节点中链表的为位置，也就是说，每个节点除了知道自己是谁以外，还知道他的双亲在哪里。其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。 //树的双亲表示法结点结构定义#define MAX_TRUE_SIZE 100typedef int TElemType //树结点的数据类型//结点结构typedef struct PTNode { TElemType data; //结点数据 int parent; //双亲位置}PTNode//树结构typedef struct{ PTNode nodes[MAX_TRUE_SIZE]; //结点数组 int r,n //根的位置和结点数}PTree 有了这样的数据结构就可以来实现双亲表示法。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，这也就意味着，我们所有的结点都存有他双亲的位置。如图1-2中的树结构和表1-3中的树双亲表示。这样的存储结构，我们可以根据结点的parent’指针很容易找到他的双亲结点，时间复杂度为O(1)，直到parent为-1时，表示找到了树结点的根 孩子表示法 换一种完全不同的考虑方法，由于树中每个结点可能有多棵子树，可以考虑用多重链表。每个结点有多个指针域，其中每个指针指向一颗子树的根结点，我们把这种方法叫做多重链表的表示方法。不过，树的每个结点的度，也就是他的孩子个数是不同的，所以设计两种方法： 方案一 指针域的个数就等于树的度，树的度就是树各个结点度的最大值。其结构如图 其中data是数据域，child1到childd是指针域，用来指向该结点的孩子结点。对于图1-1来说，树的度是3，所以我们指针域个数就是3， 方案二 每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针的个数。data为指针域，degree为度域，也就是存储该结点的孩子结点的个数这就是我们要说的孩子表示法，把每个结点的孩子都排列起来，以单链表为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组，为此，设计两种存储结构，一个是孩子链表的孩子结点，child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来存储指向结点的下一个孩子结点的指针。另一个是表头数组的表头结点。data是数据域，存储某结点的数据信息，firstchild是头指针域，存储该结点的孩子链表的头指针。 //树的孩子表示法结构定义#define MAX_TRUE_SIZE 100typedef struct CTNode //孩子结点{ int child； struct CTNode *next;}*ChildPtr;//表头结构typedef struct{ TElemType data; ChildPtr firstchild;}CTBox;//树结构typedef struct{ CTBox nodes[MAX_TRUE_SIZE]; //结点数组 int r,n; //根的位置和结点数}CTree 把把双亲表示法和孩子表示法综合一下表示如下这种表示法叫做双亲孩子表示法，应该算是孩子表示法的改进。 孩子兄弟表示法 任一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此。我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。data是数据域，fitstchild为指针域，存储该结点的第一个孩子结点的存储地址，rightsib是指针域，存储该结点的右兄弟结点的存储位置。 //孩子兄弟表示法结构定义typedef struct CSDNode{ TElemType data; struct CSNode *firstchild,*rightsib;}CSNode,*CSTree; 这种方法的示意图如下所示这种表示法，给查找某个结点的某个孩子带来了方便，只需要通过firstchild找到此结点的长子，然后在通过长子结点的rightsib找到它的二弟，接着一直找下去，直到找到具体的孩子。 推荐阅读 ●面试官 | Java转List三种方式，你说说吧。我。。懵逼。啥时候有三种了 ●面试官 | 这位连单点登录都不知道，让他回家等通知去吧 ●问题解决 | maven包冲突了怎么办，这款插件你不容错过 ●必知必会 | 关于Redis缓存这三大问题，必知必会 ●必备收藏 |详解 | 求你别用效率低下的I/O了，要不试试这种I/O 给我个好看再走好吗？ 本文分享自微信公众号 - 小明菜市场（fileGeek）。如有侵权，请联系 support@oschina.cn 删除。本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
2020-10-14

资源下载

更多资源
Spring

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

时间: 2025-12-17 大小: 5MB 下载: 1次
Rocky Linux

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

时间: 2026-04-12 大小: 1.42GB 下载: 4次
Sublime Text

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。

时间: 2025-12-03 大小: 9.84MB 下载: 39次
WebStorm

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。

时间: 2025-12-13 大小: 249.54MB 下载: 22次
热门标签
DeepSeek Jdk25 OpenAi HarmonyOS6 Nacos3 SpringBoot4 SpringCloud Docker Kubernetes Service Mesh Redis Gemini3 Rocky

欢迎您来访！

登录后，您将获得更多功能！
热门文章
联系我们

有任何问题或合作意向欢迎联系我们

Email: 99873273@qq.com

QQ: 99873273

用户登录
用户注册