精华内容
下载资源
问答
  • 概念数据模型(conceptual data model)独立于计算机系统,完全不涉及信息在计算机系统表示,只关心用来描述某个特定组织所关心的信息结构用户和数据库设计人员之间进行交流工具。可以看成现实世界大牌...

    概念数据模型(conceptual data model)

    独立于计算机系统,完全不涉及信息在计算机系统的表示,只关心用来描述某个特定组织所关心的信息结构。是用户和数据库设计人员之间进行交流的工具。可以看成是现实世界大牌机器世界的一过渡的中间层次。其中最著名的实体联系模型(entity relationship model,简记为ER模型)、

    ER模型的相关概念:

    1、实体:客观存在并可相互区别的事物。可以是具体是人,物,事。也可以是抽象的概念或联系。比如学生,老师。一次选课。

    2、属性:实体具有的某一特性或性质,一个实体可以由若干属性来刻画。比如:学生:学号、性别。

    3、实体型:具有相同属性的实体必然具有共同的特征和性质。用实体名及其属性名集合来抽象和刻画同类实体。比如学生(学号,性别,年龄)是一个实体集。

    4、实体集:同一类型实体的集合称实体集。全体学生是一个实体集。

    5、联系事物内部以及事物是有联系的,两个实体型之间的联系分为三种:一对一联系(一个学校只有一个正大门,表示为:1:1)、一对多联系(一个教室有多个学生,表示为1:n)、多对多联系(一辆车可以再多个加油站加油,一个加油站也可以有多辆车加油,m:n)

    E-R模型的表示方法:

    用矩形表示实体,框内标明实体名。

    用椭圆框表示实体的属性,并在其内写上属性名。

    用菱形框表示实体间的联系,框内写上联系名。

    实体与其属性之间以无向边链接,菱形框及相关实体之间用无向边链接。并在无向边旁表明联系的类型。


    逻辑数据模型

    逻辑数据模型直接面向数据库的逻辑结构。它实现世界的第二层抽象。这类模型涉及计算机系统和数据库管理系统。比如:层次,网状,关系和面向对象等模型。这类模型有严格的形式化定义,以便在计算机系统中实现。它通常是严格定义了无二义的语法和语义的数据库语言。可以用这种语言来定义、操纵数据库中的数据。





    展开全文
  • 什么是数据模型

    2021-01-30 17:53:50
    1.一种是独立于任何计算机系统实现,如实体联系模型,这类模型完全不涉及信息在计算机系统中表示,只是用来描述某个特定组织所关心的信息结构,因而又被称作“概念数据模型”。2.另一类数据模型直接面向...
  • 多维数据结构是数据仓库普遍使用的数据建模方式,而标准信息立方体就是多维数据结构SAP BW实现。通过它,我们可以构建出相对高效多维数据结构,而不需要关心太多多维数据结构细节。标准信息立方体就是一种...

    多维数据结构是数据仓库普遍使用的数据建模方式,而标准信息立方体就是多维数据结构的SAP BW实现。通过它,我们可以构建出相对高效的多维数据结构,而不需要关心太多的多维数据结构的细节。标准信息立方体就是一种星系结构,不过SAP BW对它做了一定的扩展,也就是所谓的扩展星形结构。而且信息立方体通过使用SID (SURROGATE ID)来关联维度和主数据,这样可以提高数据的访问效率。


    119153_201001262012171.jpg

    如图所示,一个信息立方体包括两个事实表:一个用来存储压缩数据(E表),一个用来存储未压缩数据(F表)。另外一个信息立方体还以最多有16个维度表,这16个维度中的3个是系统自动产生的:PACKAGE维度,TIME维度,还有UNIT维度(戏称PTU)。其他的维度是开发顾问构建的。

    信息立方体的事实表包含两部分的信息:一是所谓的事实信息,比如数量,收入,折扣等。还有就是对维度表数据的引用,也就是维度ID(DIMID)。维度ID是数据导入的时候自动产生并写入到事实表和各个维度表中的。通过DIMID,事实表的数据可以和各个维度表的数据关联起来。信息立方体的维度表,一方面用来减少事实表中的字段,因为多个特征值可以被组合到一个维度中;另一方面,维度表可以减少一些高关联度的特征值组合的存储冗余问题。

    信息立方体维度的一个特例是LINE ITEM维度,它主要用于那些高基数(HIGH CARDINALITY)的特征值。典型的例子就是DOCUMENT NUMBER;对于那些终端用户量非常大的行业来说,CUSTOMER NUMBER也可以是LINE ITEM维度,比如电信、银行、保险等。对于LINE ITEM维度来说,系统其实并没有产生一个维度表,而是直接把主数据SID表中的SID作为DIMID写入到事实表中。也就是说事实表和主数据表直接关联,中间不产生维度表这一层。

    当你设计完信息立方体的结构并激活它的时候,系统会自动生成上诉这些数据库表,不需要我们的手工干预。而且,这些数据库表是有一定的命名规范的:SAP定义的信息立方体的数据库表以/BI/开头,而用户自定义的数据库表以/BIC/开头。

    /BI/

    例子: 信息立方体 0SD_C01

    表名                         描述
    /BI0/D0SD_C011  Business Content−defined dimension table
    /BI0/D0SD_C012  Business Content−defined dimension table
    /BI0/D0SD_C013  Business Content−defined dimension table
    /BI0/D0SD_C014  Business Content−defined dimension table
    /BI0/D0SD_C015  Business Content−defined dimension table
    /BI0/D0SD_C01P  Package dimension table
    /BI0/D0SD_C01U  Unit dimension table
    /BI0/D0SD_C01T  Time dimension table
    /BI0/E0SD_C01     Compressed fact table
    /BI0/F0SD_C01     Uncompressed fact table

    fj.pngInfoCube_01.JPG

    来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/119153/viewspace-626084/,如需转载,请注明出处,否则将追究法律责任。

    user_pic_default.png
    请登录后发表评论 登录
    全部评论
    <%=items[i].createtime%>

    <%=items[i].content%>

    <%if(items[i].items.items.length) { %>
    <%for(var j=0;j
    <%=items[i].items.items[j].createtime%> 回复

    <%=items[i].items.items[j].username%>   回复   <%=items[i].items.items[j].tousername%><%=items[i].items.items[j].content%>

    <%}%> <%if(items[i].items.total > 5) { %>
    还有<%=items[i].items.total-5%>条评论) data-count=1 data-flag=true>点击查看
    <%}%>
    <%}%> <%}%>

    转载于:http://blog.itpub.net/119153/viewspace-626084/

    展开全文
  • 队列:简单的是就是一种数据结构 先进先出 消息队列:就是用来进行消息传输 消息中间件:就是用来传输消息中间载体 编程中 有点类似咋们 协议 中间件 他只有一个作用:就是将你信息发送到接受方 他并不关心 ...

    RabbitMQ的使用

    1、MQ是什么

    MQ:Message Queue :消息队列

    队列:简单的是就是一种数据结构 先进先出

    消息队列:就是用来进行消息传输的

    消息中间件:就是用来传输消息的中间载体

    编程中 有点类似咋们的 协议

    中间件 他只有一个作用:就是将你的信息发送到接受方 他并不关心 你发送的数据长啥样? 就类似于咋们生成中一个快递员的职责

    RabbitMQ就是消息中间件

    2、使用这个MQ能干什么

    2.1、流量消峰(解决高并发)
    流量消峰

    2.2、模块之间的异步通信
    异步通信

    3、消息队列的中间件有哪些

    ActiveMQ---------JMS(SUN公司提供的规范) Java message Server

    RabbitMQ-------在当下很多公司都用这一个

    RocketMQ------阿里的

    kafka------------用的比较多—最初的设计 是用来 完成分布式下日志的收集框架

    4、RabbitMQ的基本安装

    #安装之前需要的环境
    yum install epel-release
    yum install erlang
    
    #安装rabbitMQ了
    下载rpm文件
     wget http://www.rabbitmq.com/releases/rabbitmq-server/v3.6.15/rabbitmq-server-3.6.15-1.el7.noarch.rpm
    #下载完成需要安装
     yum install rabbitmq-server-3.6.15-1.el7.noarch.rpm
    #设置开机启动
     systemctl enable rabbitmq-server.service
    #查看服务的状态
     systemctl status rabbitmq-server.service
    #启动这个服务
     systemctl start rabbitmq-server.service
    #停止这个服务
     systemctl stop rabbitmq-server.service
    #查看当前所有的用户
     rabbitmqctl list_users
    #查看guest用户所有拥有的权限
      rabbitmqctl list_user_permissions guest
    #删除原来的guest用户
      rabbitmqctl delete_user guest
    #添加一个新的用户
      rabbitmqctl add_user zhangsan 12345678
    #给小波波设置个角色(tag)
       rabbitmqctl set_user_tags zhangsan administrator
    #给xiaobobo赋予权限
       rabbitmqctl set_permissions -p / zhangsan ".*" ".*" ".*"
    #查看用户所拥有的权限
       rabbitmqctl list_user_permissions zhangsan
       
    #开启web的管理端
    rabbitmq-plugins enable rabbitmq_management
    

    5、RabbitMQ中的五种通信模型

    5.1、helloworld模型

    helloworld模型

    意思是:生产者将消息发送到队列 然后队列将这个消息发送给消费者

    5.1.1、导包

      <!--导入RabbitMQ的相关的包-->
            <dependency>
                <groupId>com.rabbitmq</groupId>
                <artifactId>amqp-client</artifactId>
                <version>4.5.0</version>
            </dependency>
    

    5.1.2、生产者的写法

     //申明队列的名字
        private static final String QUEUE_NAME="nz-helloword";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            //第一步:获取连接
            Connection connection = ConnectionUtils.getConnection();
            //第二步:创建数据传输的通道
            Channel channel = connection.createChannel();
            //第三步:申明队列
            /**
             * 第一个参数:队列的名字
             * 第二个参数:是否持久化   比如现在发送到队列里面的消息 如果没有持久化 重启这个队列后数据会丢失(false) true:重启之后数据依然在
             * 第三个参数:是否排外
             *            1:连接关闭之后 这个队列是否自动删除
             *            2:是否允许其他通道来进行访问这个数据
             * 第四个参数:是否允许自动删除
             *            就是当最后一个连接断开的时候  这个时候是否允许自动删除这个队列
             * 第五个参数:申明队列的时候 要附带的一些参数
             */
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
            //发送数据到队列
    
            /**
             * 第一个参数:exchange  交换机  没有就设置为"值就可以了"
             * 第二个参数:原本的意思是路由的key  现在没有key直接使用队列的名字
             * 第三个参数:发送数据到队列的时候 是否要带一些参数  没有带任何参数
             * 第四个参数:向队列中发送的数据
             */
            channel.basicPublish("",QUEUE_NAME,null,"我是1111".getBytes());
            channel.close();
            connection.close();
        }
    

    5.1.3、消费者的写法

     //申明队列的名字
        private static final String QUEUE_NAME="nz-helloword";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            //获取连接
            Connection connection = ConnectionUtils.getConnection();
    
            //创建通道
            final Channel channel = connection.createChannel();
    
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
    
    
            //消费者的申明
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                /**
                 *
                 * @param consumerTag:这个消息的唯一标记
                 * @param envelope:信封(请求的消息属性的一个封装)
                 * @param properties:前面队列带过来的值
                 * @param body  :接受到的消息
                 * @throws IOException
                 */
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    System.out.println("接受到的消息是:"+new String(body));
                    //进行手动应答
                    /**
                     * 第一个参数:自动应答的这个消息标记
                     * 第二个参数:false 就相当于告诉队列受到消息了
                     */
                    channel.basicAck(envelope.getDeliveryTag(),false);
                }
            };
    
            //绑定这个消费者
            /**
             * 第一个参数:队列的名字
             * 第二个参数:是否自动应答
             * 第三个参数:消费者的申明
             */
            channel.basicConsume(QUEUE_NAME,false,defaultConsumer);
    }
    

    5.2、work模型

    多个消费者消费的数据之和才是原来队列中的所有数据 适用于流量的消峰

    work模型

    5.2.1、生产者的编写

    public class Producer {
    
        private static final String QUEUE_NAME="nz-work";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
            //下面向队列中发送100条消息
            for (int i = 0; i <100 ; i++) {
                channel.basicPublish("",QUEUE_NAME,null,("我是工作模型:"+i).getBytes());
            }
            channel.close();
            connection.close();
        }
    
    }
    

    5.2.2、消费者1的编写

    public class Consumer {
    
        //申明队列的名字
        private static final String QUEUE_NAME="nz-work";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            //获取连接
            Connection connection = ConnectionUtils.getConnection();
    
            //创建通道
            final Channel channel = connection.createChannel();
    
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
    
    
            //消费者的申明
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                /**
                 *
                 * @param consumerTag:这个消息的唯一标记
                 * @param envelope:信封(请求的消息属性的一个封装)
                 * @param properties:前面队列带过来的值
                 * @param body  :接受到的消息
                 * @throws IOException
                 */
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    System.out.println("消费者1接受到的消息是:"+new String(body));
                    //进行手动应答
                    /**
                     * 第一个参数:自动应答的这个消息标记
                     * 第二个参数:false 就相当于告诉队列受到消息了
                     */
                    channel.basicAck(envelope.getDeliveryTag(),false);
                }
            };
    
            //绑定这个消费者
            /**
             * 第一个参数:队列的名字
             * 第二个参数:是否自动应答
             * 第三个参数:消费者的申明
             */
            channel.basicConsume(QUEUE_NAME,false,defaultConsumer);
    
        }
    }
    

    5.2.3、消费者2的编写

    public class Consumer1 {
    
        //申明队列的名字
        private static final String QUEUE_NAME="nz-work";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            //获取连接
            Connection connection = ConnectionUtils.getConnection();
    
            //创建通道
            final Channel channel = connection.createChannel();
    
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
    
    
            //消费者的申明
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                /**
                 *
                 * @param consumerTag:这个消息的唯一标记
                 * @param envelope:信封(请求的消息属性的一个封装)
                 * @param properties:前面队列带过来的值
                 * @param body  :接受到的消息
                 * @throws IOException
                 */
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    System.out.println("消费者2接受到的消息是:"+new String(body));
                    //进行手动应答
                    /**
                     * 第一个参数:自动应答的这个消息标记
                     * 第二个参数:false 就相当于告诉队列受到消息了
                     */
                    channel.basicAck(envelope.getDeliveryTag(),false);
                }
            };
    
            //绑定这个消费者
            /**
             * 第一个参数:队列的名字
             * 第二个参数:是否自动应答
             * 第三个参数:消费者的申明
             */
            channel.basicConsume(QUEUE_NAME,false,defaultConsumer);
    
        }
    }
    

    5.3、发布订阅模型
    发布订阅模型

    就是队列里面的消息会被几个消费者 同时接受到

    模型 适合于做模块之间的异步通信

    例子: 就可以使用这种模型 来发送日志信息 ------ 立马就会被log收集程序

    收集到 直接写到咋们的文件里面

    例子:springcloud的config组件里面通知配置自动更新

    例子:缓存同步也可以使用这一个

    例子:高并发下实现下单逻辑

    5.3.1、编写生产者

    public class Producer {
    
        //申明交换机的名字
        private static final String EXCHANGE_NAME="nz-fanout-01";
    
        public static void main(String[] args) throws IOException, TimeoutException {
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            //申明交换机
            /**
             * 第一个参数:交换机的名字
             * 第二个参数:交换机的类型
             *    交换机的类型是不能乱写的   如果使用的是发布订阅模型  只能写 fanout
             */
            channel.exchangeDeclare(EXCHANGE_NAME,"fanout");
            //发送消息到交换机了
            for (int i = 0; i <100 ; i++) {
                channel.basicPublish(EXCHANGE_NAME,"",null,("发布订阅模型的值:"+i).getBytes());
            }
            //关闭资源
            channel.close();
            connection.close();
        }
    
    }
    

    5.3.2、编写消费者

    public class Consumer {
        //申明交换机的名字
        private static final String EXCHANGE_NAME="nz-fanout-01";
        //队列的名字
        private static final String QUEUE_NAME="nz-fanout-queue1";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
            //申明交换机
            channel.exchangeDeclare(EXCHANGE_NAME,"fanout");
            //将队列绑定到交换机
            /**
             * 第一个参数:队列的名字
             * 第二个参数:交换机的名字
             * 第三个参数:路由的key(现在没有用到这个路由的key)
             */
            channel.queueBind(QUEUE_NAME,EXCHANGE_NAME,"");
    
            //申明消费者
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    System.out.println("队列1接受到的数据是:"+new String(body));
                }
            };
    
            //就进行消费者的绑定
            channel.basicConsume(QUEUE_NAME,true,defaultConsumer);
        }
    }
    

    5.3.2、编写消费者2

    public class Consumer1 {
    
        //申明交换机的名字
        private static final String EXCHANGE_NAME="nz-fanout-01";
        //队列的名字
        private static final String QUEUE_NAME="nz-fanout-queue2";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
            //申明交换机
            channel.exchangeDeclare(EXCHANGE_NAME,"fanout");
            //将队列绑定到交换机
            /**
             * 第一个参数:队列的名字
             * 第二个参数:交换机的名字
             * 第三个参数:路由的key(现在没有用到这个路由的key)
             */
            channel.queueBind(QUEUE_NAME,EXCHANGE_NAME,"");
    
            //申明消费者
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    System.out.println("队列2接受到的数据是:"+new String(body));
                }
            };
    
            //就进行消费者的绑定
            channel.basicConsume(QUEUE_NAME,true,defaultConsumer);
        }
    }
    

    5.4、路由模型

    路由模式相当于是分布订阅模式的升级版
    路由模型

    5.4.1、生产者的写法

    public class Producer {
        private static final String EXCHANGE_NAME="nz-exchange-direct-01";
        public static void main(String[] args) throws IOException, TimeoutException {
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            /**
             * 如果玩的是路由模型 交换机的类型只能是  direct
             */
            channel.exchangeDeclare(EXCHANGE_NAME,"direct");
            //发送信息到交换机
            for (int i = 0; i <100 ; i++) {
                if(i%2==0){
                    //这个路由的key是可以随便设置的
                    channel.basicPublish(EXCHANGE_NAME,"xiaowangzi",null,("路由模型的值:"+i).getBytes());
                }else{
                    //这个路由的key是可以随便设置的
                    channel.basicPublish(EXCHANGE_NAME,"xiaodidi",null,("路由模型的值:"+i).getBytes());
                }
            }
            channel.close();
            connection.close();
        }
    }
    

    5.4.2、消费者1的写法

    public class Cosnumer1 {
    
        private static final String QUEUE_NAME="nz-direct-queue-01";
        private static final String EXCHANGE_NAME="nz-exchange-direct-01";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
            //申明交换机
            channel.exchangeDeclare(EXCHANGE_NAME,"direct");
            //绑定队列到交换机
            //第三个参数:表示的是路由key
            channel.queueBind(QUEUE_NAME,EXCHANGE_NAME,"xiaodidi");
            //申明消费者
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                   //这里就是接受消息的地方
                    System.out.println("路由key是xiaodidi的这个队列接受到数据:"+new String(body));
                }
            };
            //绑定消费者
            channel.basicConsume(QUEUE_NAME,true,defaultConsumer);
        }
    }
    

    5.4.3、消费者2的写法

    public class Consumer2 {
        private static final String QUEUE_NAME="nz-direct-queue-02";
        private static final String EXCHANGE_NAME="nz-exchange-direct-01";
    
        public static void main(String[] args) throws IOException, TimeoutException {
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            //申明队列
          channel.queueDeclare(QUEUE_NAME,false,false,false,null);
            //申明交换机
            channel.exchangeDeclare(EXCHANGE_NAME,"direct");
            //绑定队列到交换机
            //第三个参数:表示的是路由key
            channel.queueBind(QUEUE_NAME,EXCHANGE_NAME,"xiaowangzi");
            //申明消费者
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    //这里就是接受消息的地方
                    System.out.println("路由key是xiaowangzi的这个队列接受到数据:"+new String(body));
                }
            };
            //绑定消费者
            channel.basicConsume(QUEUE_NAME,true,defaultConsumer);
        }
    }
    

    5.5、topic模式

    说明:topic模式相当于是对 路由模式的一个升级 topic模式主要就是在匹配的规则上可以实现模糊匹配

    topic模式

    5.5.1、生产者的写法

    public class Producer {
        private static final String EXCHANGE_NAME = "nz-exchange-topic-01";
    
        public static void main(String[] args) throws IOException, TimeoutException {
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            /**
             * 如果玩的是路由模型 交换机的类型只能是  direct
             */
            channel.exchangeDeclare(EXCHANGE_NAME, "topic");
            //发送信息到交换机
            for (int i = 0; i < 100; i++) {
                //这个路由的key是可以随便设置的
                //topic在路由基础上只有 路由的key发生改变  其余的都不变
                channel.basicPublish(EXCHANGE_NAME, "xiaowangzi.xiaowangzi.xiaowangzi", null, ("路由模型的值:" + i).getBytes());
            }
            channel.close();
            connection.close();
        }
    }
    

    5.5.3、消费者1的写法

    public class Cosnumer1 {
    
        private static final String QUEUE_NAME="nz-topic-queue-01";
        private static final String EXCHANGE_NAME="nz-exchange-topic-01";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
            //申明交换机
            channel.exchangeDeclare(EXCHANGE_NAME,"topic");
            //绑定队列到交换机
            //第三个参数:表示的是路由key
            /**
             *    注意  * :只是代表一个单词
             *         # :这个才代表  一个或者多个单词
             *         记住如果有多个单词组成的路由key  那么多个单词之间使用 . 好连接
             *
             *
             */
            channel.queueBind(QUEUE_NAME,EXCHANGE_NAME,"xiaodidi.*");
            //申明消费者
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                   //这里就是接受消息的地方
                    System.out.println("路由key是xiaobobo的这个队列接受到数据:"+new String(body));
                }
            };
            //绑定消费者
            channel.basicConsume(QUEUE_NAME,true,defaultConsumer);
        }
    }
    

    5.5.3、消费者2的写法

    public class Consumer2 {
        private static final String QUEUE_NAME="nz-topic-queue-02";
        private static final String EXCHANGE_NAME="nz-exchange-topic-01";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
            //申明交换机
            channel.exchangeDeclare(EXCHANGE_NAME,"topic");
            //绑定队列到交换机
            //第三个参数:表示的是路由key
            channel.queueBind(QUEUE_NAME,EXCHANGE_NAME,"xiaowangzi.#");
            //申明消费者
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    //这里就是接受消息的地方
                    System.out.println("路由key是xiaowangzi的这个队列接受到数据:"+new String(body));
                }
            };
            //绑定消费者
            channel.basicConsume(QUEUE_NAME,true,defaultConsumer);
        }
    }
    

    备注:使用了交换机发送了数据 如果没有消费者的话那么这个数据会发生丢失 通过设置这样的属性来解决这个问题

    channel.basicPublish(EXCHANGE_NAME, "xiaowangzi.xiaowangzi.xiaowangzi", MessageProperties.PERSISTENT_TEXT_PLAIN, ("路由模型的值:" + i).getBytes());
    

    备注2:通道的问题

    原本没有通道我们也可以完成这个请求 RabbitMQ官方考虑到一个问题生产者 和 消费者 实际上 Connection 引入这个通道这个概念 是为了降低TCP连接的这样一个消耗 相当于是为了 TCP的复用 还有一个目的 就是为了线程隐私 相当于每一个线程都给你创建了一个通道

    6、RabbitMQ中的一些高级属性

    6.0、参数的含义

    channel.queueDeclare(QUEUE_NAME,true,false,true,null);
    第二个参数:如果是false   重启之后 队列都没有了 数据也会丢失
    第三个参数:连接一旦关闭  那么就会删除这个队列
    第四个参数:就是最后一个消费者 退出去之后 那么这个队列是否自动删除
    
    
    channel.basicPublish("",QUEUE_NAME,null,"我是1111".getBytes());
    
    第一个参数 :交换机
    第二个参数:路由key
    第三个参数:设置的队列的属性
    第四个参数:值
    

    6.1、confirm机制

    问题:就是放到队列中的消息 怎么保证一定就是成功的放入了队列

    引入了 confirm机制:这个机制的意思是 只要放消息到 queue是成功的那么队列就一定会进行反馈

    public class Producer {
    
        //申明队列的名字
        private static final String QUEUE_NAME="nz-confirm-01";
    
        public static void main(String[] args) throws IOException, TimeoutException, InterruptedException {
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            //第一步:开启confirm消息确认机制
            channel.confirmSelect();
            //我们就要对消息的可达性实施监听
            //下面就是对消息的签收情况进行确认
            channel.addConfirmListener(new ConfirmListener() {
                @Override
                public void handleAck(long l, boolean b) throws IOException {
                    System.out.println("发送成功的监听.....");
                }
    
                @Override
                public void handleNack(long l, boolean b) throws IOException {
                    System.out.println("发送失败的监听.....");
                }
            });
    
            channel.queueDeclare(QUEUE_NAME,false,false,true,null);
            channel.basicPublish("",QUEUE_NAME,null,"我是1111".getBytes());
    
        }
    }
    

    6.2、return机制

    场景:我们在发送消息的是时候、我们指定的交换机不存在 或者 指定的路由key不存在 这种时候我们就需要监听这种不可达的消息 我们的return机制就产生了

    前提:当前的队列必须要有消费者存在

    //有一个参数需要设置

    mandatory  如果设置为ture:就表示的是要监听不可达的消息 进行处理
    如果设置为false  那么队列端会直接删除这个消息
    

    6.2.1、生产者的编写

    public class Producer {
    
        private static final String EXCHANGE_NAME="test_return_exchange1";
        //是能路由的key
        private static final String ROUTING_KEY="return.save";
        //是不能路由的key
        private static final String ROUTING_ERROR_KEY="abc.save";
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            //添加监听
            channel.addReturnListener(new ReturnListener() {
                /**
                 *
                 * @param i:队列响应给浏览器的状态码
                 * @param s:表示的是状态码对应的文本信息
                 * @param s1:交换机的名字
                 * @param s2:表示的是路由的key
                 * @param basicProperties:表示的是消息的属性
                 * @param bytes:消息体的内容
                 * @throws IOException
                 */
                @Override
                public void handleReturn(int i, String s, String s1, String s2, AMQP.BasicProperties basicProperties, byte[] bytes) throws IOException {
                    System.out.println("监听到不可达的消息");
                    System.out.println("状态码:"+i+"---文本信息:"+s+"---交换机名字:"+s1+"----路由的key:s2");
                    System.out.println("监听到不可达的消息");
                    System.out.println("监听到不可达的消息");
                    System.out.println("监听到不可达的消息");
                }
            });
            channel.basicPublish(EXCHANGE_NAME,ROUTING_ERROR_KEY,true,null,"这里是测试Return机制".getBytes());
    
        }
    

    6.2.2、消费者的编写

    public class Consumer {
    
        private static final String EXCHANGE_NAME="test_return_exchange1";
    
        //是能路由的key
        private static final String ROUTING_KEY="return.#";
        //制定绑定的队列
        private static final String QUEUE_NAME="test_return_queue";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
    
            //申明队列
            channel.queueDeclare(QUEUE_NAME,true,false,false,null);
            //申明交换机
            channel.exchangeDeclare(EXCHANGE_NAME,"topic");
            //绑定
            channel.queueBind(QUEUE_NAME,EXCHANGE_NAME,ROUTING_KEY);
            //申明消费者
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    System.out.println("收到这个消息了....");
                }
            };
            //进行消费的绑定
            channel.basicConsume(QUEUE_NAME,true,defaultConsumer);
        }
    
    }
    

    6.3、消费端的限流

    场景:消费者死了 队列里面一瞬间就就积累了上万条数据、这个时候当我们打开客户端的时候、瞬间就有巨量的信息给推送过来、但是我们的客户端是没有办法同时处理这么多数据的 结果就是消费者死了…

    这种场景下我们就需要对消费端进行限流

    6.3.1、生产者的编写

    public class Producer {
    
        //申明队列的名字
        private static final String QUEUE_NAME="nz1904-limit-01";
    
        public static void main(String[] args) throws IOException, TimeoutException, InterruptedException {
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
    
            for (int i = 0; i <100 ; i++) {
                channel.basicPublish("",QUEUE_NAME, null,("我是张三"+i).getBytes());
            }
            channel.close();
            connection.close();
        }
    }
    

    6.3.2、消费者1的编写

    public class Consumer {
    
        //申明队列的名字
        private static final String QUEUE_NAME="nz-limit-01";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            //获取连接
            Connection connection = ConnectionUtils.getConnection();
    
            //创建通道
            final Channel channel = connection.createChannel();
    
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
    
            //消费者的申明
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    System.out.println("消费者1接受到的消息是:"+new String(body));
                    //进行手动应答
                    channel.basicAck(envelope.getDeliveryTag(),false);
                }
            };
    
            //绑定这个消费者
            /**
             * 第一个参数:队列的名字
             * 第二个参数:是否自动应答
             * 第三个参数:消费者的申明
             */     channel.basicConsume(QUEUE_NAME,false,defaultConsumer);
    
        }
    }
    

    6.3.3、消费者2的编写

    public class Consumer1 {
    
        //申明队列的名字
        private static final String QUEUE_NAME="nz-limit-01";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            //获取连接
            Connection connection = ConnectionUtils.getConnection();
    
            //创建通道
            final Channel channel = connection.createChannel();
    
            //申明队列
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
    
            //设置限流机制
            /**
             * 第一个参数:消息本身的大小 如果设置为0  那么表示对消息本身的大小不限制
             * 第二个参数:告诉rabbitmq不要一次性给消费者推送大于N个消息 你要推送的前提是
             * 现在这N个消息 已经手动被确认 已经完成
             * 第三个参数:true/false :是否将上面的设置应用于整个通道  true :表示整个通道的消费者
             * 都是这个策略  如果是false表示的是 只有当前的consumer 是这个策略
             */
            channel.basicQos(0,5,false);
            //结论:实际上如果不设置的话 分配任务的事 一开始就分配好了
            //必须手动签收
    
            //消费者的申明
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    System.out.println("消费者2接受到的消息是:"+new String(body));
                    try {
                      Thread.sleep(200);
                    }catch (Exception err){
    
                    }
                    //进行手动应答
                    channel.basicAck(envelope.getDeliveryTag(),false);
                }
            };
    
            //绑定这个消费者
            /**
             * 第一个参数:队列的名字
             * 第二个参数:是否自动应答
             * 第三个参数:消费者的申明
             */
           channel.basicConsume(QUEUE_NAME,false,defaultConsumer);
    
        }
    }
    

    6.4、TTL队列(Time To Live)

    场景:我要下单 下单之后 在一定的时间内、我的订单如果没有被处理 那么自动失效

    备注:就是队列中的消息是有时间限制的、如果超时那么这个消息将会被队列给删除

    public class Producer {
        //申明队列的名字
        private static final String QUEUE_NAME="nz-ttl-01";
    
        public static void main(String[] args) throws IOException, TimeoutException, InterruptedException {
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
    
            //我们只需要给下面的队列设置好属性 那么这个队列 就自动变成 ttl队列了
            Map<String,Object> map=new HashMap<>();
            map.put("x-message-ttl",5000);
            channel.queueDeclare(QUEUE_NAME,false,false,false,map);
    
            channel.basicPublish("",QUEUE_NAME, null,("我是张三").getBytes());
            channel.close();
            connection.close();
        }
    }
    

    6.5、死信队列

    什么是死信队列

    当消息在队列中编程死信之后、可以定义它重新push 到另外一个交换机上、这个交换机 也有自己对应的队列 这个队列就称为死信队列

    死信:

       发送到队列中的消息被拒绝了
    
        消息的ttl时间过期
    
        队列达到了最大长度 再往里面放信息
    

    在满足上面死信的前提下 、现在我们可以定义一个队列 这个队列专门用来

    死信队列也是一个正常的交换机、和一般的交换机没有什么区别

    当这个队列中如果有这个死信的时候、rabbitmq就会将这个消息自动发送到我们提前定义好的死信队列中去(简单的说就是路由到另外一个队列)

    6.5.1、生产者的编写

    public class Producer {
        //定义的是队列(正常的交换机)  这里发送消息是在交换机上面
        private static final String EXCHANGE_NAME="ttl-dlx-didi-exchange";
        //定义一个路由的key
        private static final String  ROUTING_KEY="dlx.#";
    
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
            for (int i = 0; i <5 ; i++) {
                 channel.basicPublish(EXCHANGE_NAME,ROUTING_KEY,false,null,("我是张三"+i).getBytes());
            }
        }
    }
    

    6.5.2、消费者的编写

    public class Consumer {
    
        //定义的是交换机
        private static final String EXCHANGE_NAME="ttl-dlx-didi-exchange";
        //正常情况下的队列
        private static final String QUEUE_NAME="ttl-dlx-didi-queue";
    
        //定义死信队列的交换机的名字
        private static final  String DLX_EXCHANGE_NAME="dlx-didi-exchange";
        //死信队列的定义
        private static final  String DLX_QUEUE_NAME="dlx-didi-queue";
        
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
            final Channel channel = connection.createChannel();
            //创建交换机和队列进行绑定
            channel.exchangeDeclare(EXCHANGE_NAME,"topic",true);
            //队列的申明
            //我们要申明成死信队列
            Map<String,Object> map=new HashMap<>();
            map.put("x-message-ttl",5000);
            //添加一个死信的属性  //后面这个名字就是死信队列交换机的名字
            map.put("x-dead-letter-exchange",DLX_EXCHANGE_NAME);
    
            channel.queueDeclare(QUEUE_NAME,true,false,false,map);
    
            //进行队列和交换机进行绑定
            channel.queueBind(QUEUE_NAME,EXCHANGE_NAME,"dlx.#");
    
            //上面是正常的队列的申明
            //下面就是死信队列的申明
            channel.exchangeDeclare(DLX_EXCHANGE_NAME,"topic");
            //申明队列
            channel.queueDeclare(DLX_QUEUE_NAME,true,false,false,null);
            //绑定这个死信队列
            channel.queueBind(DLX_QUEUE_NAME,DLX_EXCHANGE_NAME,"#");
    
    
            //直接性的来调用这个
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    System.out.println("获取到数据了:"+new String(body));
    
                }
            };
            //绑定消费者
            channel.basicConsume(DLX_QUEUE_NAME,true,defaultConsumer);
            //现在有这个问题呀?
        } 
    }
    

    6.6、消费者端手动签收和消息的重回队列

    6.6.1、生产者的编写

    public class Producer {
        //申明队列的名字
        private static final String QUEUE_NAME="nz-ack-02";
        public static void main(String[] args) throws IOException, TimeoutException, InterruptedException {
    
            Connection connection = ConnectionUtils.getConnection();
            Channel channel = connection.createChannel();
       channel.queueDeclare(QUEUE_NAME,false,false,false,null);
            channel.basicPublish("",QUEUE_NAME, null,"我是1111".getBytes());
            channel.close();
            connection.close();
        }
    }
    

    6.6.2、消费者的编写

    public class Consumer {
    
        //申明队列的名字
        private static final String QUEUE_NAME="nz-ack-02";
        public static void main(String[] args) throws IOException, TimeoutException {
    
            Connection connection = ConnectionUtils.getConnection();
    
            final Channel channel = connection.createChannel();
            channel.queueDeclare(QUEUE_NAME,false,false,false,null);
            DefaultConsumer defaultConsumer = new DefaultConsumer(channel) {
                @Override
                public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties, byte[] body) throws IOException {
                    System.out.println("接受到的消息是:"+new String(body));
                    /**第一个参数:当前消息的标记
                     * 第二个参数:是否批量进行应答
                     * 下面是签收
                     */
                    //channel.basicAck(envelope.getDeliveryTag(),false);
                    //下面也可以拒绝签收
                    /**
                     * 第三个参数:表示决绝签收之后这个消息是否要重回队列?
                     */
                    channel.basicNack(envelope.getDeliveryTag(),false,true);
                }
            };     channel.basicConsume(QUEUE_NAME,false,defaultConsumer);
        }
    }
    
    展开全文
  • 这次总结如何使用自己写迭代器实现红黑树 一.什么是迭代器? 迭代器是连接容器和算法纽带,为数据提供了抽象,使写算法人不必关心各种数据结构的细节。...迭代器是一种广义指针,是指向序列元素指

    这次总结如何使用自己写的迭代器实现红黑树


    一.什么是迭代器?

    迭代器是连接容器和算法的纽带,为数据提供了抽象,使写算法的人不必关心各种数据结构的细节。迭代器提供了数据访问的标准模型——对象序列,使对容器更广泛的访问操作成为可能。

    泛型编程的关键所在,就是如何找到一种通用的方法,来访问具有不同结构的各种容器中的每个元素,而这正是迭代器的功能。

    迭代器是一种广义的指针,是指向序列元素指针概念的一种抽象。迭代器可以指向容器中的任意元素,还能遍历整个容器。


    每种容器类型都定义了自己的C++迭代器类型,如vectorvector<int>::iterator iter;这符语句定义了一个名为 iter的变量,它的数据类型是 vector<int>定义的 iterator类型。每个标准库容器类型都定义了一个名为 iterator的成员,这里的 iterator与迭代器实际类型的含义相同。


    二.迭代器的基本操作?

    ——通过解除引用*来间接引用容器中的元素值,例如x = *p;

    ——通过解除引用*来给容器中的元素赋值,例如*p= x;

    访问——通过下标和指向引用容器中的元素及其成员,例如p[2]和p->m

    迭代——利用增量和减量运算(++和--、+和-、+=和-=)在容器中遍历、漫游和跳跃,例如p++、--p、p+5、p-=8

    比较——利用比较运算符(==、!=、<、>、<=、>=)来比较两个迭代器是否相等或谁大谁小,例如if(p < q)……;、wihle(p != c.end())……;

     

    三.什么是红黑树?及如何实现

    请参考我上一篇博客:

    http://blog.csdn.net/sayhello_world/article/details/71550605

     

    四.迭代器实现红黑树(这里在头节点前加一个结构体begin指向最小的end指向)

    迭代器应该有的操作:

    1.      *

    2.      –>

    3.      前置++ && 后置++

    4.      前置-- && 后置—

    5.      != && ==

     

    这里主要说++ 与 -- 操作

    思路:红黑树自增遍历,按照中序遍历结果,左中右。

    先找到最左边的结点,看此结点是否有右结点。

    如果有右结点,则此结点下一个应该为右结点子树中最小的结点(右子树最左边的结点)。

    如果没有右结点,则此结点应该逐层向上走。

     

    代码实现:

    //指针自增操作(按照中序遍历的结果输出)
        //如图1所示
        voidIncrement()
        {
           //如果此结点的右子树存在则应该找右子树最小的结点也就为右子树最左边的结点
           if(_pNode->_pRight)
           {
               _pNode= _pNode->_pRight;
               while(_pNode->_pLeft)
                  _pNode= _pNode->_pLeft;
           }
           //若不存在
           //若此结点为父亲结点的右结点则应该一直向上找(因为上面的都比下面的小不为++的结果)
           //否则为左节点时此时的父亲结点比pNode大此时父亲结点就为++的下一个节点
           else
           {
               Node* pParent = _pNode->_pParent;
               while(pParent->_pRight== _pNode)
               {
                  _pNode= pParent;
                  pParent= pParent->_pParent;
               }
               //这里要特殊处理因为如果此时是跟跟的右子树不存在则应该再加就赋给跟的parent
               if(pParent->_pRight!= _pNode)
                  _pNode= pParent;
            }
        }

    思路:自减操作

    从end开始自减,因为自减最后会减到跟(就是起始的结点 左为begin右为end),所以先判断此结点是否是跟。

    如果是跟的话,再减就为最大的结点。

    如果不是跟,判断此结点是否有左子树,如果有左子树,则应该找左子树中最大的结点为减减后的结点。

    否则,不是跟也没有左子树,那就在右子树中逐层向上找。

     

    代码实现:

    void Decrement()
        {
           //如果是end()为起始结点的话起始结点自减就应该为根节点右子树的第一个结点
           if(_pNode->_color== RED && _pNode->_pParent->_pParent== _pNode)
               _pNode= _pNode->_pRight;
           //否则此结点存在左子树就应该找左子树最右边的结点找左子树最大的结点
           elseif(_pNode->_pLeft)
           {
               _pNode= _pNode->_pLeft;
               while(_pNode->_pRight)
                  _pNode= _pNode->_pRight;
           }
           //否则不是根结点也没有左子树如图4 就应该找此子树的根节点
           else
           {
               Node* pParent = _pNode->_pParent;
               while(pParent->_pLeft== _pNode)
               {
                  _pNode= pParent;
                  pParent= pParent->_pParent;
               }
               //此时就不用再判断如上加加的条件了因为走到这一步pParent一定是减减后最小的
               _pNode= pParent;
            }
        }

    代码下载:

    github:

    https://github.com/Noctis-xjw/Code-Cpp/blob/master/IteratorRBTree.h

    有兴趣的点一个star


    总代码:

    #pragma once
     
    #include <iostream>
    using namespacestd;
     
    enum Color
    {
        RED,
        BLACK
    };
     
    template<classK, class V>
    struct RBTreeNode
    {
    public:
        RBTreeNode(const V&value, constK& key)
           :_value(value)
           , _key(value)
           , _pLeft(NULL)
           , _pRight(NULL)
           , _pParent(NULL)
           , _color(RED)
        {}
     
        V _value;
        K _key;
        RBTreeNode<K, V>* _pLeft;
        RBTreeNode<K, V>* _pRight;
        RBTreeNode<K, V>* _pParent;
        Color _color;
    };
     
    template<classK,class V,class Ref,class Ptr>
    class Iterator
    {
        typedefIterator<K, V, Ref, Ptr> Self;
        typedefRBTreeNode<K, V> Node;
     
    public:
        Iterator()
           :_pNode(NULL)
        {}
     
        Iterator(const Self& it)
           :_pNode(it._pNode)
        {}
     
        Iterator(Node* node)
           :_pNode(node)
        {}
     
        Ref operator*()
        {
           return_pNode->_key;
        }
     
        Ptr operator->()
        {
           return&(operator*());
        }
     
        //前置++
        Self& operator++()
        {
           Increment();
           return*this;
        }
     
        //后置++
        Self operator++(int)
        {
           Self temp(*this);
           Increment();
           returntemp;
        }
     
        //前置--
        Self& operator--()
        {
           Decrement();
           return*this;
        }
     
        //后置--
        Self operator--(int)
        {
           Self temp(*this);
           Decrement();
           returntemp;
        }
     
        booloperator!=(const Self&sf)
        {
           return_pNode!= sf._pNode;
        }
     
        booloperator==(const Self&sf)
        {
           return_pNode== sf._pNode;
        }
    protected:
        //指针自增操作(按照中序遍历的结果输出)
        //如图1所示
        voidIncrement()
        {
           //如果此结点的右子树存在则应该找右子树最小的结点也就为右子树最左边的结点
           if(_pNode->_pRight)
           {
               _pNode= _pNode->_pRight;
               while(_pNode->_pLeft)
                  _pNode= _pNode->_pLeft;
           }
           //若不存在
           //若此结点为父亲结点的右结点则应该一直向上找(因为上面的都比下面的小不为++的结果)
           //否则为左节点时此时的父亲结点比pNode大此时父亲结点就为++的下一个节点
           else
           {
               Node* pParent = _pNode->_pParent;
               while(pParent->_pRight== _pNode)
               {
                  _pNode= pParent;
                  pParent= pParent->_pParent;
               }
               //这里要特殊处理因为如果此时是跟跟的右子树不存在则应该再加就赋给跟的parent如图3
               if(pParent->_pRight!= _pNode)
                  _pNode= pParent;
           }
        }
     
        voidDecrement()
        {
           //如果是end()为起始结点的话起始结点自减就应该为根节点右子树的第一个结点
           if(_pNode->_color== RED && _pNode->_pParent->_pParent== _pNode)
               _pNode= _pNode->_pRight;
           //否则此结点存在左子树就应该找左子树最右边的结点找左子树最大的结点
           elseif(_pNode->_pLeft)
           {
               _pNode= _pNode->_pLeft;
               while(_pNode->_pRight)
                  _pNode= _pNode->_pRight;
           }
           //否则不是根结点也没有左子树如图4 就应该找此子树的根节点
           else
           {
               Node* pParent = _pNode->_pParent;
               while(pParent->_pLeft== _pNode)
               {
                  _pNode= pParent;
                  pParent= pParent->_pParent;
               }
               //此时就不用再判断如上加加的条件了因为走到这一步pParent一定是减减后最小的
               _pNode= pParent;
           }
        }
     
    private:
        Node* _pNode;
    };
     
    template < classK, class V>
    class RBTree
    {
        typedefIterator<K, V, K&, V*> Iterator;
        typedefRBTreeNode<K, V> Node;
    public:
        RBTree()
        {
           _pHead= new Node(K(),V());
           _pHead->_color= RED;
           _pHead->_pLeft= _pHead;
           _pHead->_pRight= _pHead;
           _pHead->_pParent= NULL;
        }
     
        boolInsert(const K& key, constV& value)
        {
           //判断根节点是否为空
           Node* _pRoot = GetRoot();
           if(NULL == _pRoot)
           {
               _pRoot= new Node(key,value);
               _pRoot->_pParent= _pHead;
               _pHead->_pParent= _pRoot;
               _pRoot->_color= BLACK;
               returntrue;
           }
               Node* pCur = _pRoot;
               Node* pParent = NULL;
               //找插入位置
               while(pCur)
               {
                  if(key > pCur->_key)
                  {
                      pParent= pCur;
                      pCur= pCur->_pRight;
                  }
                  elseif(key < pCur->_key)
                  {
                      pParent= pCur;
                      pCur= pCur->_pLeft;
                  }
                  else
                      returnfalse;
               }
     
               //插入结点
               pCur= new Node(key,value);
               if(key < pParent->_key)
                  pParent->_pLeft= pCur;
               elseif(key > pParent->_key)
                  pParent->_pRight= pCur;
     
               pCur->_pParent= pParent;
     
               //对结点的颜色进行处理
               //从下往上修改颜色到根节点且根节点为红结束
               while(_pRoot != pCur&& pParent->_color== RED)
               {
                  Node* grandFather = pParent->_pParent;
                  if(pParent == grandFather->_pLeft)
                  {
                      Node* uncle = grandFather->_pRight;
                      //当前插得为红,双亲为红,叔叔也为红
                      //此时应该把祖先变为红,把双亲叔叔变为黑
                      if(uncle && uncle->_color== RED)
                      {
                         grandFather->_color= RED;
                         pParent->_color= BLACK;
                         uncle->_color= BLACK;
     
                         pCur= grandFather;
                         pParent= pCur->_pParent;
                      }
                      //否则叔叔不存在或者叔叔为黑
                      else
                      {
                         //如果cur在父母的右边则左单旋再右单旋
                         if(pParent->_pRight== pCur)
                         {
                             RotateLeft(pParent);
                             std::swap(pParent,pCur);
                         }
                         //否则只右单旋
                         pParent->_color= BLACK;
                         grandFather->_color= RED;
                         RotateRight(grandFather);
                         break;
                      }
                  }
                  //否则父母结点在祖先节点的右边
                  else
                  {
                      Node* uncle = grandFather->_pLeft;
                      if(uncle && uncle->_color== RED)
                      {
                         pParent->_color= BLACK;
                         uncle->_color= BLACK;
                         grandFather->_color= RED;
     
                         pCur= grandFather;
                         pParent= pCur->_pParent;
                      }
                      else
                      {
                         if(pCur == pParent->_pLeft)
                         {
                             RotateRight(pParent);
                             std::swap(pParent,pCur);
                         }
                         grandFather->_color= RED;
                         pParent->_color= BLACK;
                         RotateLeft(grandFather);
                         break;
                      }
                  }
               }
           //旋转后要把根节点重新获取一下
           _pRoot= GetRoot();
     
           //最后要把根节点换成黑色的
           _pRoot->_color= BLACK;
           _pHead->_pLeft= GetMin();
           _pHead->_pRight= GetMax();
           returntrue;
        }
     
        boolCheckRBTree()
        {
           Node* _pRoot = GetRoot();
           if(_pRoot == NULL)
               returntrue;
     
           if(_pRoot->_color== RED)
           {
               cout<< "根为红色不满足" << endl;
               returnfalse;
           }
     
           //计算黑色结点的个数应该每一条路径上数目都相同
           intBlackCount= 0;
           Node* pCur = _pRoot;
           //只走最左边的那一条路
           while(pCur)
           {
               if(pCur->_color== BLACK)
                  BlackCount++;
               pCur= pCur->_pLeft;
           }
           intk= 0;
           return_CheckRBTree(_pRoot, BlackCount,k);
        }
     
        bool_CheckRBTree(Node* pRoot,constsize_t blackCount, size_t k)
        {
           if(pRoot == NULL)
               returntrue;
     
           //如果两个连续的红色就违反规则
           Node* Parent = pRoot->_pParent;
           if(Parent && Parent->_color== RED && pRoot->_color== RED)
           {
               cout<< "两个红色不能相连接" << endl;
               returnfalse;
           }
     
           //判断是否k=blackCount
           //如果此时为黑色结点 k要++
           if(pRoot->_color== BLACK)
               k++;
     
           if(pRoot->_pLeft== NULL && pRoot->_pRight== NULL)
           {
               if(k != blackCount)
               {
                  cout<< "违反两个黑色结点相同原则" << endl;
                  returnfalse;
               }
           }
           return_CheckRBTree(pRoot->_pLeft,blackCount,k)&& _CheckRBTree(pRoot->_pRight,blackCount,k);
        }
     
        voidInOrder()
        {
           cout<< "中序遍历:";
           Node* _pRoot = GetRoot();
           _InOrder(_pRoot);
        }
     
        Iterator Begin()
        {
           returnIterator(_pHead->_pLeft);
        }
     
        Iterator End()
        {
           returnIterator(_pHead);
        }
     
    private:
        //获取根
        Node*& GetRoot()
        {
           return_pHead->_pParent;
        }
     
        Node* GetMin()
        {
           Node* pRoot = _pHead->_pParent;
           while(pRoot->_pLeft)
           {
               pRoot= pRoot->_pLeft;
           }
           returnpRoot;
        }
     
        Node* GetMax()
        {
           Node* pRoot = _pHead->_pParent;
           while(pRoot->_pRight)
           {
               pRoot= pRoot->_pRight;
           }
           returnpRoot;
        }
     
        void_InOrder(Node* pRoot)
        {
           if(pRoot == NULL)
               return;
           _InOrder(pRoot->_pLeft);
           cout<< pRoot->_key<< "  ";
           _InOrder(pRoot->_pRight);
        }
     
        voidRotateLeft(Node*& pRoot)
        {
           Node* SubR = pRoot->_pRight;
           Node* SubRL = SubR->_pLeft;
           pRoot->_pRight= SubRL;
     
           if(SubRL)
               SubRL->_pParent= pRoot;
           SubR->_pLeft= pRoot;
           SubR->_pParent= pRoot->_pParent;
     
           pRoot->_pParent= SubR;
           pRoot= SubR;
     
           if(pRoot->_pParent== _pHead)
               _pHead->_pParent= pRoot;
           else
           {
               if(pRoot->_pParent->_key> pRoot->_key)
               pRoot->_pParent->_pLeft= pRoot;
               else
               pRoot->_pParent->_pRight= pRoot;
           }
        }
     
        voidRotateRight(Node*& pRoot)
        {
           Node* SubL = pRoot->_pLeft;
           Node* SubLR = SubL->_pRight;
           pRoot->_pLeft= SubLR;
           if(SubLR)
               SubLR->_pParent= pRoot;
           SubL->_pRight= pRoot;
           SubL->_pParent= pRoot->_pParent;
     
           pRoot->_pParent= SubL;
           pRoot= SubL;
     
           if(pRoot->_pParent== _pHead)
               _pHead->_pParent= pRoot;
           else{
               if(pRoot->_pParent->_key> pRoot->_key)
                  pRoot->_pParent->_pLeft= pRoot;
               else
                  pRoot->_pParent->_pRight= pRoot;
           }
        }
     
    private:
        Node* _pHead;
        //int_Size;
    };


    展开全文
  • 一般存储图方式有两:一是用邻接矩阵表示,二是用邻接链表。 所谓用邻接矩阵,是用一个二维数组存储,边...无向图矩阵一定是一个对称矩阵,因为无向图只关心边是否存在,而不关心方向,V0和V1有边,那么...
  • IEEE 802.16协议作用在用户站点同核心网络之间建立起个通信路径,该协议所关心的是用户收发 信机同基站收发信机之间无线接口,专门对在网络中传输大数据块时无线传输地址问题作出了规定。 IEEE 802.16...
  • 基于中间件的查询优化模型 传统的客户/服务器模式是一种双层的结构,通常是一台个人计算机做客户机使用(运行客户端程序),另外一台服务器用于存放后台的数据库系统,应用程序可客户端直接相连,中间没有其他的...
  •  表示层并不"关心"上层-应用层的数据格式而是把整个应用层递交数据包看成是一个整体进行封装,即加上表示层报头(Presentation Header,PH)。然后,递交到下层-会话层。  同样,会话层、传输层、网络层、数据...
  • 应用程序中使用 XML 文档多数方法都把重点放在 XML 上:从 XML 观点使用...数据绑定提供了一种更简单使用 XML 方法。 文档模型数据绑定 本系列文章上一篇(请参阅 参考资料)所讨论文档模型与数
  • Xcessiv是一个工具,可以帮助您创建您可以想到的最大,最疯狂和最过量的堆叠乐团。 从理论上讲,堆叠的乐团很简单。 您可以合并较小模型的预测,然后将其输入另一个模型。 但是,在实践中,实施它们可能是头疼的...
  • 设计模式的一点点笔记

    千次阅读 2005-09-30 09:46:00
    设计模式描述了对象之间在互不关心彼此数据模型的情况下怎样进行通信。软件复用的个重要方法。 设计模式有很多,总的来分有——(1)构造模式(Creational patterns):用来在不同的情况下创建不同的对象,而...
  • 数据库作为一种专门管理数据软件就出现了。应用程序不需要自己管理数据,而是通过数据库软件提供接口来读写数据。至于数据本身如何存储到文件,那数据库软件事情,应用程序自己并不关心: 2.数据模型 ...
  •  本书是一本关于oracle database 9i、10g 和11g 数据库体系结构的权威图书,涵盖了所有重要oracle 体系结构特性,包括文件、内存结构和进程,锁和闩,事务、并发和多版本,表和索引,数据类型,分区和并行,以及...
  • 数据库作为一种专门管理数据的软件就出现了。应用程序不需要自己管理数据,而是通过数据库软件提供接口来读写数据。至于数据本身如何存储到文件,那数据库软件事情,应用程序自己并不关心: 随着时间推移和...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 138
精华内容 55
关键字:

关心数据模型的结构是一种