jenkins持续集成二——spring boot集成设置

前面安装好了环境,这一篇主要讲下设置

系统管理->管理插件

image_thumb9

以下是默认安装插件之外,需要额外安装的插件。

系统管理->全局工具配置

image_thumb4

配置JDK

image_thumb1

配置git

image_thumb3

配置maven

image_thumb7

系统管理->系统设置

image_thumb11

这里主要需要对jenkins 将集成应用通过ssh部署到应用服务器的SSH 连接配置

示例如下,同时需要了解SSH免密登录相关内容。

image_thumb14

SSH免密登录

#ubuntu环境在客户机器上生成密钥对,密钥会生成在~/.ssh/目录下
ssh-keygen -t rsa

生成多机器不同密钥对免密登录配置

#配置多远程机器不同密钥的配置,在~/.ssh/ 生成config
touch config

示例配置如下

image_thumb16

将公钥拷贝到远程机器上

#ssh-copy-id [-i [identity_file]] [user@]machine
ssh-copy-id -i id_rsa_git git@127.0.0.1
#该公钥信息会记录到git 服务器的~/.ssh/authorized_keys 文件

测试

ssh git@git #or ssh git@127.0.0.1

Credentials

从git 拉取代码,使用SSH 信用连接,设置 Credentials,添加git 相关的SSH 连接认证,如下图示例:

image_thumb20

Maven 构建项目配置

新建按钮如下

image_thumb18

配置

git源

image_thumb22

构建触发

image_thumb24

10分钟构建一次

自动部署

image_thumb26

文件存档

image_thumb28

jenkins持续集成(一)-基础安装设置

jenkins  作为持续集成现在用得越来越广,以前都是公司直接配置好了用上就好,现在就按部就班从0开始弄个持续集成环境吧。


jenkins

安装

wget -q -O - https://jenkins-ci.org/debian/jenkins-ci.org.key | sudo apt-key add -
sudo sh -c 'echo deb http://pkg.jenkins-ci.org/debian binary/ > /etc/apt/sources.list.d/jenkins.list'
sudo apt-get update
sudo apt-get install jenkins

启动

启动:  
sudo service jenkins start  
停止:  
sudo service jenkins stop

路径

log 路径:/var/log/jenkins/jenkins.log
jenkins的home路径:/var/lib/jenkins
端口号修改路径:sudo vi /etc/default/jenkins

初始化

通过浏览器就可以访问Jenkins了。比如我的地址:http://192.168.2.126:7777/,按照页面提示安装插件及设置管理员账户密码。

image

为了确保Jenkins的安全,将管理员的密码写入文件,需要复制到下面的文本框做验证。

/var/lib/jenkins/secrets/initialAdminPassword

然后,到了选择插件的界面,通过附加功能扩展Jenkins可以支持许多不同的需求。

image

image

image

image

git

安装

安装
sudo apt-get install git
#添加用户
useradd git
#配置SSH登录
cd ~
mkdir .ssh 
cd .ssh
touch authorized_keys
cat ~/id_rsa.pub >> ~/.ssh/authorized_keys
rm ~/id_rsa.pub
#授权
chmod 600 ~/.ssh/authorized_keys
chmod 700 ~/.ssh

使用

#新建目录
mkdir   zwr
#新建初始化仓库
git init --bare test.git

Maven

安装

方式一

#下载
wget http://mirrors.tuna.tsinghua.edu.cn/apache/maven/maven-3/3.3.9/binaries/apache-maven-3.3.9-bin.tar.gz
#解压
tar -xzf apache-maven-3.3.9-bin.tar.gz
#移动
mv apache-maven-3.3.9  /usr/share/maven
#设置环境变量
vim /etc/profile
#环境变量内容
M2_HOME=/usr/share/maven
CLASSPATH=$CLASSPATH:$M2_HOME/lib
PATH=$PATH:$M2_HOME/bin
export   PATH    CLASSPATH   M2_HOME
#生效
source /etc/profile

方式二

apt-get install -y maven
mvn -version

mysql优化系列(一)

使用新数据库,玩一段时间后,我想大家就应该会碰到一系列的小问题,那是正常的,因为就像处女朋友一样,作为一个负责的男人,不能随便玩一玩了事。

当然,本人也不是泡妞高手,所以也需要不断学习充电,当然老毛子说理论实践是要结合的,在此留下一记。

    1.全表扫描

查询一定要避免全表扫描,如果你有前任,不管她的名字是不是叫oracle,你一定吃过全表扫描的亏,如果很不幸,你一直是只单身狗,那么你也不要沮丧,这里有现成的理论,单身狗们快拿去实践一下:

  • 在查询条件字段建立索引,这是最基本的常识,如果你不记牢你女朋友的电话号码,你大冬天的每次都去她楼下找她么!当然索引也不是越多越好,就像衣服穿多了,你何时才能上三垒!insert update 看到索引就说不要不要的!
  • 在查询条件中,不要拿null值进行判断,既然这样,如果可以,请把你的字段都设置成非NULL,跟默认值进行判断,0 就是0,NULL是什么鬼,你女朋友一定会河东狮吼!
  • 对于 like 这类关键字,大家也尽量少用为好,不要问我为什么,你女朋友真的要大海捞针!
  • 不要给你女朋友太多的选择条件,直接告诉她怎么做,所以 or 这种条件字段也尽量不要用了!
  • 如果字段可以使用 int 类型,那么就不要使用 字符串类型,你女朋友的脑子有时候没有你想象中的那么好,你把字符串给她一个个对比,你们约好的出门时间应该又要推迟了,电影也只能看后半场了,所以给她处理的东西也越简单越好.

当然,mysql 既然是你的新女朋友,那么她也会有自己的一些特性,请在查询的时候限制她查询的范围,limit n,你只需要 n个记录,那么就不要让她找出 n+m来,不然她真的会这么干!

有时候,即使你给了限制,还是会出错!

请看

select * from order where kj_customer_acco =

@kj_customer_acco and position_int > @position_int order by position_int asc limit 0,@request_num

上面给出的示范,除了

select *

这个是不好的外(增加多余的网络传输压力等),其他应该都是几乎完美的一个语句,但是就是如此,有时候你女朋友还是爽约了,那一天你在雨中苦等了2小时,以为会有一场雨中浪漫的约会,结果是你淋成了落汤鸡!因为你没有从实际国情出发,我们是一国两制的社会,胡乱套用也会水土不服,所以我们一定要具体问题具体分析,那么就先来看下国情:

CREATE TABLE order
(
	position_int                   bigint          NOT NULL AUTO_INCREMENT,
	kj_customer_acco               varchar(10)     DEFAULT ' '        ,
	update_date                    int             DEFAULT 0          ,
	update_time                    int             DEFAULT 0          ,
	PRIMARY KEY(position_int)
);
CREATE INDEX idx_position_int ON order(position_int ASC );

然后我们造了测试数据进去

begin
    declare i int default 1000;
    
	while i < 1300 do
    BEGIN
    declare j int default 1;
		while j < 9060 do
       insert into `order` values(DEFAULT,i,20151203,111111);
       set j=j+1;
    end while; 
    set i=i+1;
    END;
   end while;
   commit;
end

我们使用上面的语句对这个表进行翻页式查询,在查询中,每当如下语句

select * from order where kj_customer_acco = @kj_customer_acco  and position_int > @position_int

查询出来的数据不足 @request_num,的时候,就会特别的慢,使用 EXPLAIN 关键字查看下执行计划

image

我们发现查询搜索的边界在我们的意料之外,它的搜索范围是1231780行数据,当剩余查询的数据条数大于@request_num,因为我们加了limit 的限制,所以查询搜索到@request_num 条数据的时候就结束搜索了,但是当剩余查询的有效数据量不足@request_num时,就会继续往下查询把rows 条记录都会搜一遍!

spring_mvc_mybatis傻瓜入门篇之二spring与spring-mvc

上篇我们已经弄好了spring 与mybatis,即搞定了数据model层的东西,已经可以对外提供数据服务了,那么现在就要将spring-mvc加上去,增加逻辑与展示!

一.增加依赖包

在pom.xml中增加配置项

<dependency> <groupId>org.springframework</groupId> <artifactId>spring-webmvc</artifactId> <version>${spring.version}</version> </dependency>

增加spring_mvc 的配置文件(servlet-context.xml)如下

<?xml version="1.0" encoding="UTF-8"?>
<beans:beans xmlns="http://www.springframework.org/schema/mvc"
	xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
	xmlns:beans="http://www.springframework.org/schema/beans"
	xmlns:context="http://www.springframework.org/schema/context"
	xsi:schemaLocation="http://www.springframework.org/schema/mvc http://www.springframework.org/schema/mvc/spring-mvc.xsd
		http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd
		http://www.springframework.org/schema/context http://www.springframework.org/schema/context/spring-context.xsd">

	<!-- DispatcherServlet Context: defines this servlet's request-processing infrastructure -->
	
	<!-- Enables the Spring MVC @Controller programming model -->
	<annotation-driven />

	<!-- Handles HTTP GET requests for /resources/** by efficiently serving up static resources in the ${webappRoot}/resources directory -->
	<resources mapping="/resources/**" location="/resources/" />

	<!-- Resolves views selected for rendering by @Controllers to .jsp resources in the /WEB-INF/views directory -->
	<beans:bean class="org.springframework.web.servlet.view.InternalResourceViewResolver">
		<beans:property name="prefix" value="/WEB-INF/views/" />
		<beans:property name="suffix" value=".jsp" />
	</beans:bean>
	
	<!-- SpringMVC上传文件时,需要配置MultipartResolver处理器 -->
	<beans:bean id="multipartResolver"
		class="org.springframework.web.multipart.commons.CommonsMultipartResolver">
		<beans:property name="defaultEncoding" value="utf-8" />
		<beans:property name="maxUploadSize" value="10485760000" />
		<beans:property name="maxInMemorySize" value="40960" />
	</beans:bean>
    
	<context:component-scan base-package="com.test.controller" />
	
</beans:beans>

将该 配置文件路径添加到web.xml上:

<!-- Processes application requests -->
	<servlet>
		<servlet-name>appServlet</servlet-name>
		<servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
		<init-param>
			<param-name>contextConfigLocation</param-name>
			<param-value>/WEB-INF/spring/appServlet/servlet-context.xml</param-value>
		</init-param>
		<load-on-startup>1</load-on-startup>
	</servlet>
		
	<servlet-mapping>
		<servlet-name>appServlet</servlet-name>
		<url-pattern>/</url-pattern>
	</servlet-mapping>

配置好了,然后就可以开始新建个页面测试下了

新建展示页面showUserInfo.jsp

<%@ page language="java" contentType="text/html; charset=utf-8"
    pageEncoding="utf-8"%>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Insert title here</title>
</head>
<body>
${userinfo.name}:${userinfo.passwd}
</body>
</html>

新建逻辑控制页面代码:

package com.test.controller;

import javax.annotation.Resource;  
import javax.servlet.http.HttpServletRequest;  
import org.springframework.stereotype.Controller;  
import org.springframework.ui.Model;  
import org.springframework.web.bind.annotation.RequestMapping;  
import com.test.model.UserInfo;  
import com.test.service.IUserInfoService;  


@Controller  
@RequestMapping("/user") 
public class queryUserController {

	 @Resource  
	 private IUserInfoService userService;  
	  
	    @RequestMapping("/showUserInfo")  
	    public String toIndex(HttpServletRequest request, Model model) {  
	        long pos_int = Long.parseLong(request.getParameter("id"));  
	        UserInfo userinfo = this.userService.getUserInfoById(pos_int);  
	        model.addAttribute("userinfo", userinfo);  
	        return "showUserInfo"; 
	    }
}

好了,就可以运行调试:http://localhost:8080/smvc/user/showUserInfo?id=1

QA:

有很大几率你是不能一次性就运行成功的,会报很多错误,那么耐性看他报错信息,然后找谷歌问一问你就可以得到答案!当然如果你怕麻烦,那么也可以预先做下如下处理以避免各种报错:

1.在项目属性中,添加如下图红框中的路径配置

image

其他的一时也记不起来了,出问题了百度吧,或者留言!

spring_mvc_mybatis傻瓜入门篇之spring与mybatis

  • 一.介绍

  • spring
  • 目前编程,一般我们都会在一个框架一下进行编程,而目前J2EE比较流行的框架,SPRING 当居其首。当然我们可以先撇开JAVA,撇开SPRING,一般进行编程都会运用到GOF中设计模式思想使得我们的代码程序可读可扩展解耦等等,那么在设计框架的时候,不管啥语言啥框架,他的中心思想就是屏蔽细节让我们用起来简单方便,实现这个目标有很多方式,那么作为GOD设计模式的延伸,一般的服务框架目前都已经运用IOC->AOP->SOA思想进行框架的设计实现!最基础的是 IOC,在此基础上实现AOP,SOA!关于其中的关系传送门在此!SPIRNG只是众多框架中的一种,但好用方便,所以用户众多!

  • SPRING_MVC

  • MVC是一种3层设计模式,web mvc 顾名思义就是web端的mvc,SPRING_MVC是对MVC的一种web实现!

  • Mybatis

  • mybaits封装了后台与数据库持久层的一个框架!

相互关系

spring作为核心可以自由的与各种持久层框架,web框架组合出不同的架构,如ssh(web框架struct,持久层框架hiberante)等!所以其他都可换,核心 spring 就不要换了,一个好的芯还是很重要的! 今天要入门的就是 spring + spring-mvc+mybatis

二.工具安装

工欲善其事必先利其器,spring 的开发都会有一个 sts的套件,其实 就是帮你安装好方便使用spring 相关插件的 eclipse !那就下载过来安装起来就好了!

三.创建项目

我们项目使用maven 管理,如果你还不知道maven ,那么找wikipedia 详细了解下,如果你只想知道在eclipse下的安装使用,那么这里你可以快速入门。 安装好之后之后,就可以建立maven工程,按说明next你就成功了:

image

通过pom.xml 配置文件引入各种需要的jar包具体看下面各个模块的需要引入!一般我们会引入日志,所以再配置下日志的配置文件如下(log4j.xml):

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE log4j:configuration PUBLIC "-//APACHE//DTD LOG4J 1.2//EN" "log4j.dtd">
<log4j:configuration xmlns:log4j="http://jakarta.apache.org/log4j/">

	<!-- Appenders -->
	<appender name="console" class="org.apache.log4j.ConsoleAppender">
		<param name="Target" value="System.out" />
		<layout class="org.apache.log4j.PatternLayout">
			<param name="ConversionPattern" value="%-5p: %c - %m%n" />
		</layout>
	</appender>
	
	<!-- Application Loggers -->
	<logger name="com.hundsun.smvc">
		<level value="info" />
	</logger>
	
	<!-- 3rdparty Loggers -->
	<logger name="org.springframework.core">
		<level value="info" />
	</logger>
	
	<logger name="org.springframework.beans">
		<level value="info" />
	</logger>
	
	<logger name="org.springframework.context">
		<level value="info" />
	</logger>

	<logger name="org.springframework.web">
		<level value="info" />
	</logger>

	<!-- Root Logger -->
	<root>
		<priority value="warn" />
		<appender-ref ref="console" />
	</root>
	
</log4j:configuration>

四 .spring

spring 框架只需要在 pom.xml上配置引入spring 的jar,如下

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
	<modelVersion>4.0.0</modelVersion>
	<groupId>com.hundsun</groupId>
	<artifactId>smvc</artifactId>
	<name>smvc</name>
	<packaging>war</packaging>
	<version>1.0.0-BUILD-SNAPSHOT</version>
	<properties>
		<java-version>1.6</java-version>
		<org.springframework-version>4.2.0.RELEASE</org.springframework-version>
		<org.aspectj-version>1.6.10</org.aspectj-version>
		<org.slf4j-version>1.6.6</org.slf4j-version>
	</properties>
	<dependencies>
	<!-- Spring -->
	<!-- spring核心包 -->  
    <dependency>  
        <groupId>org.springframework</groupId>  
        <artifactId>spring-core</artifactId>  
        <version>${org.springframework-version}</version>  
    </dependency>  
  
    <dependency>  
        <groupId>org.springframework</groupId>  
        <artifactId>spring-web</artifactId>  
        <version>${org.springframework-version}</version>  
    </dependency>  
  
    <dependency>  
        <groupId>org.springframework</groupId>  
        <artifactId>spring-oxm</artifactId>  
        <version>${org.springframework-version}</version>  
    </dependency>  
  
    <dependency>  
        <groupId>org.springframework</groupId>  
        <artifactId>spring-tx</artifactId>  
        <version>${org.springframework-version}</version>  
    </dependency>  
  
    <dependency>  
        <groupId>org.springframework</groupId>  
        <artifactId>spring-jdbc</artifactId>  
        <version>${org.springframework-version}</version>  
    </dependency>  
  
    <dependency>  
        <groupId>org.springframework</groupId>  
        <artifactId>spring-webmvc</artifactId>  
        <version>${org.springframework-version}</version>  
    </dependency>  
  
    <dependency>  
        <groupId>org.springframework</groupId>  
        <artifactId>spring-aop</artifactId>  
        <version>${org.springframework-version}</version>  
    </dependency>  
  
    <dependency>  
        <groupId>org.springframework</groupId>  
        <artifactId>spring-context-support</artifactId>  
        <version>${org.springframework-version}</version>  
    </dependency>  
  
    <dependency>  
        <groupId>org.springframework</groupId>  
        <artifactId>spring-test</artifactId>  
        <version>${org.springframework-version}</version>  
    </dependency>  
		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-context</artifactId>
			<version>${org.springframework-version}</version>
			<exclusions>
				<!-- Exclude Commons Logging in favor of SLF4j -->
				<exclusion>
					<groupId>commons-logging</groupId>
					<artifactId>commons-logging</artifactId>
				 </exclusion>
			</exclusions>
		</dependency>
		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-webmvc</artifactId>
			<version>${org.springframework-version}</version>
		</dependency>

	</dependencies>
</project>

五.在Spring中加入mybatis

先在pom.xml配置上mybatis 用到的引入包信息

<!-- jackson 包 -->
    <dependency>  
        <groupId>org.codehaus.jackson</groupId>  
        <artifactId>jackson-mapper-asl</artifactId>  
        <version>1.9.13</version>  
    </dependency>
		
		<!-- mybatis 包 -->
		<dependency>
			<groupId>org.mybatis</groupId>
			<artifactId>mybatis</artifactId>
			<version>3.2.8</version>
		</dependency>

		<!--mybatis spring 插件 -->
		<dependency>
			<groupId>org.mybatis</groupId>
			<artifactId>mybatis-spring</artifactId>
			<version>1.2.2</version>
		</dependency>
		
		<!-- mysql连接 -->
		<dependency>
			<groupId>mysql</groupId>
			<artifactId>mysql-connector-java</artifactId>
			<version>5.1.34</version>
		</dependency>
		
		<!-- dbcp的jar包,用来在applicationContext.xml中配置数据库 -->  
   		<dependency>  
           <groupId>commons-dbcp</groupId>  
           <artifactId>commons-dbcp</artifactId>  
           <version>1.2.2</version>  
   		</dependency>

配置jdbc 配置文件 (jdbc.properties)

url=jdbc:mysql://115.29.151.158:3306/mytrade?useUnicode=true&characterEncoding=utf8 
driver=com.mysql.jdbc.Driver
username=********
password=*******
#定义初始连接数  
initialSize=0 
#定义最大连接数  
maxActive=20  
#定义最大空闲  
maxIdle=20 
#定义最小空闲  
minIdle=1  
#定义最长等待时间  
maxWait=60000  
  • 配置spring 引入mybatis 的配置文件(spring-mybatis.xml)

  • <?xml version="1.0" encoding="UTF-8"?>
    <beans xmlns="http://www.springframework.org/schema/beans"  
        xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:p="http://www.springframework.org/schema/p"  
        xmlns:context="http://www.springframework.org/schema/context"  
        xmlns:mvc="http://www.springframework.org/schema/mvc"  
        xsi:schemaLocation="http://www.springframework.org/schema/beans    
      http://www.springframework.org/schema/beans/spring-beans-3.1.xsd    
      http://www.springframework.org/schema/context    
      http://www.springframework.org/schema/context/spring-context-3.1.xsd    
      http://www.springframework.org/schema/mvc    
      http://www.springframework.org/schema/mvc/spring-mvc-4.0.xsd">  
      
        <!-- 自动扫描 -->  
        <context:component-scan base-package="com.test" />  
      
        <!-- 引入配置文件 -->  
        <bean id="propertyConfigurer"  
            class="org.springframework.beans.factory.config.PropertyPlaceholderConfigurer">  
            <property name="location" value="classpath:jdbc.properties" />  
        </bean>  
      
        <bean id="dataSource" class="org.apache.commons.dbcp.BasicDataSource"  
            destroy-method="close">  
            <property name="driverClassName" value="${driver}" />  
            <property name="url" value="${url}" />  
            <property name="username" value="${username}" />  
            <property name="password" value="${password}" />  
            <!-- 初始化连接大小 -->  
            <property name="initialSize" value="${initialSize}"></property>  
            <!-- 连接池最大数量 -->  
            <property name="maxActive" value="${maxActive}"></property>  
            <!-- 连接池最大空闲 -->  
            <property name="maxIdle" value="${maxIdle}"></property>  
            <!-- 连接池最小空闲 -->  
            <property name="minIdle" value="${minIdle}"></property>  
            <!-- 获取连接最大等待时间 -->  
            <property name="maxWait" value="${maxWait}"></property>  
        </bean>  
      
        <!-- Spring和MyBatis完美整合,不需要mybatis的配置映射文件 -->  
        <bean id="sqlSessionFactory" class="org.mybatis.spring.SqlSessionFactoryBean">  
            <property name="dataSource" ref="dataSource" />  
            <!-- 自动扫描mapping.xml文件 -->  
            <property name="mapperLocations" value="classpath:com/test/mapping/*.xml"></property>  
        </bean>  
      
        <!-- DAO接口所在包名,Spring会自动查找其下的类 -->  
        <bean class="org.mybatis.spring.mapper.MapperScannerConfigurer">  
            <property name="basePackage" value="com.test.Dao" />  
            <property name="sqlSessionFactoryBeanName" value="sqlSessionFactory"></property>  
        </bean>  
      
        <!-- 事务管理 -->  
        <bean id="transactionManager"  
            class="org.springframework.jdbc.datasource.DataSourceTransactionManager">  
            <property name="dataSource" ref="dataSource" />  
        </bean>  
      
    </beans>  
  • 将该配置文件添加到web.xml中
    	<!-- The definition of the Root Spring Container shared by all Servlets and Filters -->
    	<context-param>
    		<param-name>contextConfigLocation</param-name>
    		<param-value>
    		/WEB-INF/spring/root-context.xml;
    		classpath:spring-mybatis.xml;
    		</param-value>
    到这里,我们需要的包都已经添加好了,然后我们就需要测试下我们的spring 通过mybatis与mysql 数据库是不是通的,当然我们得先把数据库,表都准备好了,这个就不说了!接下来你们可能觉得需要写代码,写一些model层出来通过mybatis与mysql进行联通了?不需要,我们只要借助一个mybatis中的神器 mybatis-generator 用来自动生成代码,当然你需要把mysql 的数据连接地址,需要生成的model 的表等一些信息配置起来!具体还是看前面链接里面的教程吧,就不重复说了:自动生成以下类:
    package com.test.Dao;
    
    import com.test.model.UserInfo;
    
    public interface UserInfoMapper {
        int deleteByPrimaryKey(Long positionInt);
    
        int insert(UserInfo record);
    
        int insertSelective(UserInfo record);
    
        UserInfo selectByPrimaryKey(Long positionInt);
    
        int updateByPrimaryKeySelective(UserInfo record);
    
        int updateByPrimaryKey(UserInfo record);
    }
                      然后把接口及服务层实现写出来,就写个简单的获取用户信息吧:

                      image

                      package com.test.service;
                      
                      import com.test.model.UserInfo;
                      
                      public interface IUserInfoService {
                      	public UserInfo getUserInfoById(long pos_int);
                      }
                      
                      package com.test.service.impl;
                      
                      import javax.annotation.Resource;  
                      import org.springframework.stereotype.Service;  
                      import com.test.model.UserInfo;  
                      import com.test.Dao.UserInfoMapper;  
                      import com.test.service.IUserInfoService; 
                      
                      @Service("userinfoService") 
                      public class UserInfoServiceImpl implements IUserInfoService {
                      	@Resource  
                          private UserInfoMapper userinfoDao;  
                      	
                      	@Override  
                          public UserInfo getUserInfoById(long pos_int) {  
                              return this.userinfoDao.selectByPrimaryKey(pos_int);  
                          }  
                      }
                      

                      然后写个 jtest:

                      package smvc;
                      
                      import javax.annotation.Resource;  
                      import org.apache.log4j.Logger;  
                      import org.junit.Test;  
                      import org.junit.runner.RunWith;  
                      import org.springframework.test.context.ContextConfiguration;  
                      import org.springframework.test.context.junit4.SpringJUnit4ClassRunner;  
                      import com.alibaba.fastjson.JSON;  
                      import com.test.model.UserInfo;  
                      import com.test.service.IUserInfoService;  
                      
                      
                      @RunWith(SpringJUnit4ClassRunner.class)  
                      @ContextConfiguration(locations = { "classpath:spring-mybatis.xml" })  
                      public class TestMyBatis {
                      	private static Logger logger = Logger.getLogger(TestMyBatis.class);  
                      	
                      	 @Resource  
                      	 private IUserInfoService userinfoService = null;  
                      	 
                      	 @Test  
                      	    public void test1() {  
                      	        UserInfo userinfo = userinfoService.getUserInfoById((long) 1);  
                      	        logger.info(JSON.toJSONString(userinfo));  
                      	    }  
                      }

                      运行下,我们就可以愉快的得到数据了!

                      Better understanding Linux secondary dependencies solving with examples

                      除了man 资料外觉得是挺详细的资料,收藏!

                      http://www.kaizou.org/2015/01/linux-libraries/

                      08 Jan 2015 by David Corvoysier

                      A few months ago I stumbled upon a linking problem with secondary dependencies I couldn’t solved without overlinking the corresponding libraries.

                      I only realized today in a discussion with my friend Yann E. Morin that not only did I use the wrong solution for that particular problem, but that my understanding of the gcc linking process was not as good as I had imagined.

                      This blog post is to summarize what I have now understood.

                      There is also a small repository on github with the mentioned samples.

                      A few words about Linux libraries

                      This paragraph is only a brief summary of what is very well described in The Linux Documentation Project library howto.

                      Man pages for the linux linker and loader are also a good source of information.

                      There are three kind of libraries in Linux: static, shared and dynamically loaded (DL).

                      Dynamically loaded libraries are very specific to some use cases like plugins, and would deserve an article on their own. I will only focus here on static and shared libraries.

                      Static libraries

                      A static library is simply an archive of object files conventionally starting with thelib prefix and ending with the .a suffix.

                      Example:

                      libfoobar.a

                      Static libraries are created using the ar program:

                      $ ar rcs libfoobar.a foo.o bar.o

                      Linking a program with a static library is as simple as adding it to the link command either directly with its full path:

                      $ gcc -o app main.c /path/to/foobar/libfoobar.a

                      or indirectly using the -l/L options:

                      $ gcc -o app main.c -lfoobar -L/path/to/foobar

                      Shared libraries

                      A shared library is an ELF object loaded by programs when they start.

                      Shared libraries follow the same naming conventions as static libraries, but with the .sosuffix instead of .a.

                      Example:

                      libfoobar.so

                      Shared library objects need to be compiled with the -fPIC option that produces position-independent code, ie code that can be relocated in memory.

                      $ gcc -fPIC -c foo.c
                      $ gcc -fPIC -c bar.c

                      The gcc command to create a shared library is similar to the one used to create a program, with the addition of the -shared option.

                      $ gcc -shared -o libfoobar.so foo.o bar.o

                      Linking against a shared library is achieved using the exact same commands as linking against a static library:

                      $ gcc -o app main.c libfoobar.so

                      or

                      $ gcc -o app main.c -lfoobar -L/path/to/foobar

                      Shared libraries and undefined symbols

                      An ELF object maintains a table of all the symbols it uses, including symbols belonging to another ELF object that are marked as undefined.

                      At compilation time, the linker will try to resolve an undefined symbol by linking it either statically to code included in the overall output ELF object or dynamically to code provided by a shared library.

                      If an undefined symbol is found in a shared library, a DT_NEEDED entry is created for that library in the output ELF target.

                      The content of the DT_NEEDED field depends on the link command: – the full path to the library if the library was linked with an absolute path, – the library name otherwise (or the library soname if it was defined).

                      You can check the dependencies of an ELF object using the readelf command:

                      $ readelf -d main

                      or

                      $ readelf -d libbar.so

                      When producing an executable a symbol that remains undefined after the link will raise an error: all dependencies must therefore be available to the linker in order to produce the output binary.

                      For historic reason, this behavior is disabled when building a shared library: you need to specify the --no-undefined (or -z defs) flag explicitly if you want errors to be raised when an undefined symbol is not resolved.

                      $ gcc -Wl,--no-undefined -shared -o libbar.so -fPIC bar.c

                      or

                      $ gcc -Wl,--no-undefined -shared -o libbar.so -fPIC bar.c

                      Note that when producing a static library, which is just an archive of object files, no actual ‘linking’ operation is performed, and undefined symbols are kept unchanged.

                      Library versioning and compatibility

                      Several versions of the same library can coexist in the system.

                      By conventions, two versions of the same library will use the same library name with a different version suffix that is composed of three numbers:

                      • major revision,
                      • minor revision,
                      • build revision.

                      Example:

                      libfoobar.so.1.2.3

                      This is often referred as the library real name.

                      Also by convention, the library major version should be modified every time the library binary interface (ABI) is modified.

                      Following that convention, an executable compiled with a shared library version is theoretically able to link with another version of the same major revision.

                      This concept if so fundamental for expressing compatibility between programs and shared libraries that each shared library can be associated a soname, which is the library name followed by a period and the major revision:

                      Example:

                      libfoobar.so.1

                      The library soname is stored in the DT_SONAME field of the ELF shared object.

                      The soname has to be passed as a linker option to gcc.

                      $ gcc -shared -Wl,-soname,libfoobar.so.1 -o libfoobar.so foo.o bar.o

                      As mentioned before, whenever a library defines a soname, it is that soname that is stored in the DT_NEEDED field of ELF objects linked against that library.

                      Solving versioned libraries dependencies at build time

                      As mentioned before, libraries to be linked against can be specified using a shortened name and a path:

                      $ gcc -o app main.c -lfoobar -L/path/to/foobar

                      When installing a library, the installer program will typically create a symbolic link from the library real name to its linker name to allow the linker to find the actual library file.

                      Example:

                      /usr/lib/libfoobar.so -> libfoobar.so.1.5.3

                      The linker uses the following search paths to locate required shared libraries:

                      • directories specified by -rpath-link options (more on that later)
                      • directories specified by -rpath options (more on that later)
                      • directories specified by the environment variable LD_RUN_PATH
                      • directories specified by the environment variable LD_LIBRARY_PATH
                      • directories specified in DT_RUNPATH or DT_RPATH of a shared library are searched for shared libraries needed by it
                      • default directories, normally /lib and /usr/lib
                      • directories listed inthe /etc/ld.so.conf file

                      Solving versioned shared libraries dependencies at runtime

                      On GNU glibc-based systems, including all Linux systems, starting up an ELF binary executable automatically causes the program loader to be loaded and run.

                      On Linux systems, this loader is named /lib/ld-linux.so.X (where X is a version number). This loader, in turn, finds and loads recursively all other shared libraries listed in theDT_NEEDED fields of the ELF binary.

                      Please note that if a soname was specified for a library when the executable was compiled, the loader will look for the soname instead of the library real name. For that reason, installation tools automatically create symbolic names from the library soname to its real name.

                      Example:

                      /usr/lib/libfoobar.so.1 -> libfoobar.so.1.5.3

                      When looking fo a specific library, if the value described in the DT_NEEDED doesn’t contain a /, the loader will consecutively look in:

                      • directories specified at compilation time in the ELF object DT_RPATH (deprecated),
                      • directories specified using the environment variable LD_LIBRARY_PATH,
                      • directories specified at compile time in the ELF object DT_RUNPATH,
                      • from the cache file /etc/ld.so.cache, which contains a compiled list of candidate libraries previously found in the augmented library path (can be disabled at compilation time),
                      • in the default path /lib, and then /usr/lib (can be disabled at compilation time).

                      Proper handling of secondary dependencies

                      As mentioned in the introduction, my issue was related to secondary dependencies, ie shared libraries dependencies that are exported from one library to a target.

                      Let’s imagine for instance a program main that depends on a library libbar that itself depends on a shared library libfoo.

                      We will use either a static libbar.a or a shared libbar.so.

                      foo.c

                      int foo()
                      {
                          return 42;
                      }

                      bar.c

                      int foo();
                      
                      int bar()
                      {
                          return foo();
                      }

                      main.c

                      int bar();
                      
                      int main(int argc, char** argv)
                      {
                          return bar();
                      }

                      Creating the libfoo.so shared library

                      libfoo has no dependencies but the libc, so we can create it with the simplest command:

                      $ gcc -shared -o libfoo.so -fPIC foo.c

                      Creating the libbar.a static library

                      As said before, static libraries are just archives of object files, without any means to declare external dependencies.

                      In our case, there is therefore no explicit connection whatsoever between libbar.a and libfoo.so.

                      $ gcc -c bar.c
                      $ ar rcs libbar.a bar.o

                      Creating the libbar.so dynamic library

                      The proper way to create the libbar.so shared library it by explicitly specifying it depends on libfoo:

                      $ gcc -shared -o libbar2.so -fPIC bar.c -lfoo -L$(pwd)

                      This will create the library with a proper DT_NEEDED entry for libfoo.

                      $ readelf -d libbar.so
                      Dynamic section at offset 0xe08 contains 25 entries:
                        Tag        Type                         Name/Value
                       0x0000000000000001 (NEEDED)             Shared library: [libfoo.so]
                       0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
                      ...

                      However, since undefined symbols are not by default resolved when building a shared library, we can also create a “dumb” version without any DT_NEEDED entry:

                      $ gcc -shared -o libbar_dumb.so -fPIC bar.c

                      Note that it is very unlikely that someone actually chooses to create such an incomplete library on purpose, but it may happen that by misfortune you encounter one of these beasts in binary form and still need to link against it (yeah, sh… happens !).

                      Creating the main executable

                      Linking against the libbar.a static library

                      As mentioned before, when linking an executable, the linker must resolve all undefined symbols before producing the output binary.

                      Trying to link only with libbar.a produces an error, since it has an undefined symbol and the linker has no clue where to find it:

                      $ gcc -o app_s main.c libbar.a
                      libbar.a(bar.o): In function `bar':
                      bar.c:(.text+0xa): undefined reference to `foo'
                      collect2: error: ld returned 1 exit status

                      Adding libfoo.so to the link command solves the problem:

                      $ gcc -o app main.c libbar.a -L$(pwd) -lfoo

                      You can verify that the app binary now explicitly depends on libfoo:

                      $ readelf -d app
                      Dynamic section at offset 0xe18 contains 25 entries:
                        Tag        Type                         Name/Value
                       0x0000000000000001 (NEEDED)             Shared library: [libfoo.so]
                       0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
                      ...

                      At run-time, the dynamic linker will look for libfoo.so, so unless you have installed it in standard directories (/lib or /usr/lib) you need to tell it where it is:

                      LD_LIBRARY_PATH=$(pwd) ./app

                      To summarize, when linking an executable against a static library, you need to specify explicitly all dependencies towards shared libraries introduced by the static library on the link command.

                      Note however that expressing, discovering and adding implicit static libraries dependencies is typically a feature of your build system (autotools, cmake).

                      Linking against the libbar.so shared library

                      As specified in the linker documentation, when the linker encounters an input shared library it processes all its DT_NEEDED entries as secondary dependencies:

                      • if the linker output is a shared relocatable ELF object (ie a shared library), it will add all DT_NEEDED entries from the input library as new DT_NEEDED entries in the output,
                      • if the linker ouput is a non-shared, non-relocatable link (our case), it will automatically add the libraries listed in the DT_NEEDED of the input library on the link command line, producing an error if it can’t locate them.

                      So, let’s see what happens when dealing with our two shared libraries.

                      Linking against the “dumb” library

                      When trying to link an executable against the “dumb” version of libbar.so, the linker encounters undefined symbols in the library itself it cannot resolve since it lacks theDT_NEEDED entry related to libfoo:

                      $ gcc -o app main.c -L$(pwd) -lbar_dumb
                      libbar_dumb.so: undefined reference to `foo'
                      collect2: error: ld returned 1 exit status

                      Let’s see how we can solve this.

                      Adding explicitly the libfoo.so dependency

                      Just like we did when we linked against the static version, we can just add libfoo to the link command to solve the problem:

                      $ gcc -o app main.c -L$(pwd) -lbar_dumb -lfoo

                      It creates an explicit dependency in the app binary:

                      $ readelf -d app
                      Dynamic section at offset 0xe18 contains 25 entries:
                        Tag        Type                         Name/Value
                       0x0000000000000001 (NEEDED)             Shared library: [libbar_dumb.so]
                       0x0000000000000001 (NEEDED)             Shared library: [libfoo.so]
                       0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
                      ...

                      Again, at runtime you may need to tell the dynamic linker where libfoo.so is:

                      $ LD_LIBRARY_PATH=$(pwd) ./app

                      Note that having an explicit dependency to libfoo is not quite right, since our application doesn’t use directly any symbols from libfoo. What we’ve just done here is called overlinking, and it is BAD.

                      Let’s imagine for instance that in the future we decide to provide a newer version oflibbar that uses the same ABI, but based on a new version of libfoo with a different ABI: we should theoretically be able to use that new version of libbar without recompiling our application, but what would really happen here is that the dynamic linker would actually try to load the two versions of libfoo at the same time, leading to unpredictable results. We would therefore need to recompile our application even if it is still compatible with the newest libbar.

                      As a matter of fact, this actually happened in the past: a libfreetype update in the debian distro caused 583 packages to be recompiled, with only 178 of them actually using it.

                      Ignoring libfoo dependency

                      There is another option you can use when dealing with the “dumb” library: tell the linker to ignore its undefined symbols altogether:

                      $ gcc -o app main.c -L$(pwd) -lbar_dumb -Wl,--allow-shlib-undefined

                      This will produce a binary that doesn’t declare its hidden dependencies towards libfoo:

                      $ readelf -d app
                      Dynamic section at offset 0xe18 contains 25 entries:
                        Tag        Type                         Name/Value
                       0x0000000000000001 (NEEDED)             Shared library: [libbar_dumb.so]
                       0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
                      ...

                      This isn’t without consequences at runtime though, since the dynamic linker is now unable to resolve the executable dependencies:

                      $ ./app: symbol lookup error: ./libbar_dumb.so: undefined symbol: foo

                      Your only option is then to load libfoo explicitly (yes, this is getting uglier and uglier):

                      $ LD_PRELOAD=$(pwd)/libfoo.so LD_LIBRARY_PATH=$(pwd) ./app
                      Linking against the “correct” library
                      Doing it the right way

                      As mentioned before, when linking against the correct shared library, the linker encounters the libfoo.so DT_NEEDED entry, adds it to the link command and finds it at the path specified by -L, thus solving the undefined symbols … or at least that is what I expected:

                      $ gcc -o app main.c -L$(pwd) -lbar
                      /usr/bin/ld: warning: libfoo.so, needed by libbar.so, not found (try using -rpath or -rpath-link)
                      /home/diec7483/dev/linker-example/libbar.so: undefined reference to `foo'
                      collect2: error: ld returned 1 exit status

                      Why the error ? I thought I had done everything by the book !

                      Okay, let’s take a look at the ld man page again, looking at the -rpath-link option. This says:

                      When using ELF or SunOS, one shared library may require another. This happens when an “ld -shared” link includes a shared library as one of the input files. When the linker encounters such a dependency when doing a non-shared, non-relocatable link, it will automatically try to locate the required shared library and include it in the link, if it is not included explicitly. In such a case, the -rpath-link option specifies the first set of directories to search. The -rpath-link option may specify a sequence of directory names either by specifying a list of names separated by colons, or by appearing multiple times.

                      Ok, this is not crystal-clear, but what it actually means is that when specifying the path for a secondary dependency, you should not use -L but -rpath-link:

                      $ gcc -o app main.c -L$(pwd) -lbar -Wl,-rpath-link=$(pwd)

                      You can now verify that app depends only on libbar:

                      $ readelf -d app
                      Dynamic section at offset 0xe18 contains 25 entries:
                        Tag        Type                         Name/Value
                       0x0000000000000001 (NEEDED)             Shared library: [libbar.so]
                       0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
                      ...

                      And this is finally how things should be done.

                      You may also use -rpath instead of -rpath-link but in that case the specified path will be stored in the resulting executable, which is not suitable if you plan to relocate your binaries. Tools like cmake use the -rpath during the build phase (make), but remove the specified path from the executable during the installation phase(make install).

                      Conclusion

                      To summarize, when linking an executable against:

                      • a static library, you need to specify all dependencies towards other shared libraries this static library depends on explicitly on the link command.

                      • a shared library, you don’t need to specify dependencies towards other shared libraries this shared library depends on, but you may need to specify the path to these libraries on the link command using the -rpath/-rpath-link options.

                      Note however that expressing, discovering and adding implicit libraries dependencies is typically a feature of your build system (autotools, cmake), as demonstrated in my samples.

                      C/C++拾遗一

                      一. new是一个操作符,具体的实现:

                      1.调用 operate new 函数 分配内存空间!

                      2.然后调用构造函数!

                      3.返回正确的指针!

                      所以new 跟 malloc 的基本差别:

                      1.属性上:new 是个运算符,malloc 是个函数,malloc 可等同与operate new 函数(operate new stl中的实现就是调用了 malloc)

                      2.功能上,new 比malloc 多了调用构造函数的过程!

                      引申:

                      如果需要限制类对象实例只能分配在堆上:那么我们只需要做的事情是把析构函数设置为私有,这样编译器管理不了对象的生命周期就不能分配在栈上,当然我们需要设置一个公有函数实现对象的释放!同时因为按照编程习惯new/delete 都是成对出现的,现在析构私有,则delete 会报错,所以我们把new 也封装到一个静态函数中去!不直接使用 new!

                      如果需要限制类对象示例只能分配在栈上:把operate new  函数重载为私有,则new 运算符就调用不了operate new 函数!

                      二、虚函数实现

                      C++多态的实现依靠虚函数,而虚函数又是通过虚函数表来实现的。那么里面的实现细节需要关注如下几点:

                      1.位置:为了最大化查找虚函数效率,V-Table  的指针存放在对象实例最前面的位置!

                      2.虚函数在虚表中的组织形式:

                          2.1.V-Table 存储的是一个类的所有虚函数指针,虚函数地址基类的放在前面,子类在后面,按顺序存储。

                          2.2.如果子类中有覆盖基类的,则子类的对象实例中,在虚函数表中,该虚函数地址直接覆盖基类的虚函数地址!

                         2.3.如果存在多重继承,会有多个虚函数表,子类虚函数放在第一个虚函数表中,如果存在覆盖,则全部基类函数都被覆盖!

                      安全性:

                      因为虚函数表是顺序存储的,所以有时候我们其实可以通过直接函数指针直接寻址的的方式绕过编译器检查访问到一些不能访问的函数,如子类存在而父类中没有的,受保护的虚函数等!

                      详情见:(http://ibinguo.net/2009/06/)

                      三、对象内存空间

                      这个也只讲个皮毛,深入的话还是要对汇编,编译原理有深入了解!

                      前面讲虚函数、虚表的时候,就说了,虚表指针是放在对象实例最前面的位置。那么再来看看类的各种不同成员,不同继承关系的对象内存分布

                      1.单一继承结构:虚表在最前面,并且虚函数按照顺序在虚表中排列,而各成员变量也按照声明的顺序排列!

                      2.多重继承结构:每个基类一个虚表,而成员变量紧跟在虚表后面,并且共同的基类每个基类都会重复!

                      歧义:因为每个基类都有一个重复基类的成员,所以不同子类在调用的时候编译器就不知道要调用具体哪个一个,调用的时候需要加上具体的基类名!

                      3.由于2的歧义性问题,C++还有一个虚继承,这样多重继承就不会有多个重复拷贝,但是虚继承的基类会在最下面!

                      四、初始化异常处理

                      为了处理构造函数成员初始化列表产生的异常,必须将构造函数编写为函数测试块(function try block)。

                      template <class T> Handle<T>::Handle(T *p)

                      try : ptr(p), use(new size_t(1))

                      {

                        // empty function body

                      } catch(const std::bad_alloc &e) {

                        handle_out_of_memory(e);

                      }

                      关键字try出现在成员初始化列表之前,测试块的复合语句包围了构造函数的函数体。catch子句既可以处理从成员初始化列表中抛出的异常,也可以处理从构造函数函数体中抛出的异常。

                      数据结构与算法( 七)字符串串算法

                      编程中还是经常用到字符串匹配的算发。

                      一.字符串匹配算法

                      字符串匹配算法通常分为两个步骤:预处理(Preprocessing)和匹配(Matching)。预处理就是计算每次匹配的时候滑动窗口,所以算法的总运行时间为预处理和匹配的时间的总和。

                      朴素的字符串匹配算法

                      从左向右匹配,每次匹配一个字串, 匹配失败后 向右移动一个字串。具体流程如下:

                      1.

                      首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

                      2.

                      因为B与A不匹配,搜索词再往后移。

                      3.

                      就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

                      4.

                      接着比较字符串和搜索词的下一个字符,还是相同。

                      5.

                      直到字符串有一个字符,与搜索词对应的字符不相同为止。

                      6.

                      这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。(下面部分就是KMP改进过程,原理在后面中讲)

                      7.

                      一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是,设法利用这个已知信息,不要把”搜索位置”移回已经比较过的位置,继续把它向后移,这样就提高了效率。

                      8.

                      怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

                      9.

                      已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。查表可知,最后一个匹配字符B对应的”部分匹配值”为2,因此按照下面的公式算出向后移动的位数:

                        移动位数 = 已匹配的字符数 – 对应的部分匹配值

                      因为 6 – 2 等于4,所以将搜索词向后移动4位。

                      10.

                      因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2(”AB”),对应的”部分匹配值”为0。所以,移动位数 = 2 – 0,结果为 2,于是将搜索词向后移2位。

                      11.

                      因为空格与A不匹配,继续后移一位。

                      12.

                      逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 – 2,继续将搜索词向后移动4位。

                      13.

                      逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 – 0,再将搜索词向后移动7位,这里就不再重复了。

                      KMP算法

                      KMP算法是在朴素算法上的优化,因为我们发现,匹配失败后,每次向右移动一个字串,能不能移动多几个字串呢?

                      其实这也是以空间,时间,换时间的方式。进行一个预处理。

                      其实就是要找到匹配过的字串中的前缀与后缀匹配的字串长度,这样直接移动过去就好了,再演化一下,预处理就是先建立起部分匹配表(索引(hash)),寻找待匹配字串的前缀集与后缀集中的匹配长度。这样就可以计算出失败后的位移长度。

                      下面介绍《部分匹配表》是如何产生的。

                      首先,要了解两个概念:”前缀”和”后缀”。 “前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。

                      15.

                      “部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例,

                        - ”A”的前缀和后缀都为空集,共有元素的长度为0;

                        - ”AB”的前缀为[A],后缀为[B],共有元素的长度为0;

                        - ”ABC”的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

                        - ”ABCD”的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

                        - ”ABCDA”的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为”A”,长度为1;

                        - ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为”AB”,长度为2;

                        - ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

                      16.

                      “部分匹配”的实质是,有时候,字符串头部和尾部会有重复。比如,”ABCDAB”之中有两个”AB”,那么它的”部分匹配值”就是2(”AB”的长度)。搜索词移动的时候,第一个”AB”向后移动4位(字符串长度-部分匹配值),就可以来到第二个”AB”的位置。

                      数据结构与算法( 六)图

                      没有最好的数据结构,只有最适合的数据结构,没有最快的算法,只有最适合的算法。

                      图是一种常见的非线性数据结构,探究图,其实就是将非线性数据线性化的尝试。

                      图的遍历部分发现一个博客写得挺好,直接修改转过来了

                      http://www.cnblogs.com/dolphin0520/archive/2011/07/13/2105236.html

                      一.图定义

                      1.有向图:边有方向的图。 无相图:边无方向。

                      2.无向完全图:任两个点之间都有边的图。

                      3.有向完全图:任两点之间都存在两个有向边的图。

                      4.路径:任两个顶点之间经过的顶点序列集,长度是顶点序列之间边的的数目。

                      5.简单路径:路径中没有重复的顶点。

                      6.连通图:任两个顶点之间都存在路径的图

                      7.连通分量(极大连通子图):image

                      8.连通图的生成树:包含图中全部的顶点,但只有n-1条边

                      9.图可以使用2维数组来表示他们之间的关系,(邻接矩阵单元值为0,表示没有边,1表示有边)。

                      image

                      二.图的遍历

                      图的遍历是树的遍历的推广,是按照某种规则(或次序)访问图中各顶点依次且仅一次的操作,亦是将网络结构按某种规则线性化的过程

                      由于图存在回路,为区别一顶点是否被访问过和避免顶点被多次访问,在遍历过程中,应记下每个访问过的顶点,即每个顶点对应有一个标志位,初始为False,一旦该顶点被访问,就将其置为True,以后若又碰到该顶点时,视其标志的状态,而决定是否对其访问。

                      对图的遍历通常有”深度优先搜索“和”广度优先搜索“方法,二者是人工智能的一个基础。

                      深度优先搜索(Depth First Search,简称DFS)

                      算法思路:

                      类似树的先根遍历。设初始化时,图中各顶点均未被访问,从图中某个顶点(设为V0)出发,访问V0,然后搜索V0的一个邻接点Vi,若Vi未被访问,则访问之,在 搜索Vi的一个邻接点(深度优先)…。若某顶点的邻接点全部访问完毕,则回溯(Backtracking)到它的上一顶点,然后再从此顶点又按深度优先的方法搜索下去,…,直到能访问的顶点都访问完毕为止。

                      设图G10如下图所示:

                      通过深度优先如下:

                      广度优先搜索(Breadth First Search),简称BFS

                      算法思路:

                      类似树的按层次遍历。初始时,图中各顶点均未被访问,从图中某顶点(V0)出发,访问V0,并依次访问V0的各邻接点(广度优先)。然后,分别从这些被访问过的顶点出发,扔仍按照广度优先的策略搜索其它顶点,….,直到能访问的顶点都访问完毕为止。

                      为控制广度优先的正确搜索,要用到队列技术,即访问完一个顶点后,让该顶点的序号进队。然后取相应队头(出队),考察访问过的顶点的各邻接点,将未访问过的邻接点访问 后再依次进队,…,直到队空为止。

                      通过广度优先如下:

                      下面看一下实现代码:

                      1. #include <stdio.h>
                      2. #include <stdlib.h>
                      3. #include <string.h>
                      4. #define MAX 20
                      5. //访问记录
                      6. int visit[MAX];
                      7. //图的结构设计
                      8. typedef struct
                      9. {
                      10. int vex[MAX];//记录顶点
                      11. int adjmatrix[MAX][MAX];//邻接矩阵
                      12. int n;//顶点的个数
                      13. }GRAPH;
                      14. //初始化图
                      15. int init_graph(GRAPH *pG)
                      16. {
                      17.     memset(pG,0,sizeof(GRAPH));
                      18.     pG->n = -1;
                      19.     printf(“input vex\n”);
                      20. while(scanf(“%d”,&pG->vex[++pG->n]));
                      21. while(getchar() != ‘\n’);
                      22. #ifndef _DEBUG_
                      23. int i = 0;
                      24. for(i = 0;i < pG->n ;i ++)
                      25. {
                      26.         printf(“V%d “,pG->vex[i]);
                      27. }
                      28.     printf(“\n”);
                      29. #endif
                      30.     return 0;
                      31. }
                      32. //获取顶点的位置
                      33. int locatevex(GRAPH *pG,int vex)
                      34. {
                      35. int i = 0;
                      36. for(i = 0;i < pG->n;i ++)
                      37. {
                      38. if(pG->vex[i] == vex )
                      39.             return i;
                      40. }
                      41.     return 0;
                      42. }
                      43. //输入图的顶点之间的边
                      44. int input_edge(GRAPH *pG)
                      45. {
                      46. int vex1,vex2;
                      47. int i,j;
                      48.     printf(“input edge(i,j):\n”);
                      49. //任意字母键结束
                      50. while(scanf(“(%d,%d)”,&vex1,&vex2))
                      51. {
                      52.         getchar();
                      53.         i = locatevex(pG,vex1);
                      54.         j = locatevex(pG,vex2);
                      55.         pG->adjmatrix[i][j] = pG->adjmatrix[j][i] = 1;
                      56. }
                      57. #ifndef _DEBUG_
                      58. int m,n;
                      59. for(m = 0;m < pG->n;m ++)
                      60. {
                      61. for(n = 0;n < pG->n; n ++)
                      62. {
                      63.             printf(“%d “,pG->adjmatrix[m][n]);
                      64. }
                      65.         printf(“\n”);
                      66. }
                      67. #endif
                      68.     return 0;
                      69. }
                      70. //栈的设计
                      71. typedef struct
                      72. {
                      73. int buf[MAX];
                      74. int n;
                      75. }Stack;
                      76. //创建空栈
                      77. Stack *create_empty_stack()
                      78. {
                      79.     Stack *stack;
                      80.     stack = (Stack *)malloc(sizeof(Stack));
                      81.     stack->n = -1;
                      82.     return stack;
                      83. }
                      84. //出栈
                      85. int pop_stack(Stack *stack)
                      86. {
                      87. int temp;
                      88.     temp = stack->buf[stack->n];
                      89.     stack->n –;
                      90.     return temp;
                      91. }
                      92. //入栈
                      93. int push_stack(Stack *stack,int data)
                      94. {
                      95.     stack->n ++;
                      96.     stack->buf[stack->n] = data;
                      97.     return 0;
                      98. }
                      99. //判断空栈
                      100. int is_empty_stack(Stack *stack)
                      101. {
                      102. if(stack->n == -1)
                      103.         return 1;
                      104. else
                      105.         return 0;
                      106. }
                      107. int visit_all(GRAPH *pG)
                      108. {
                      109. int i = 0;
                      110. for(i = 0;i < pG->n; i ++)
                      111. {
                      112. if(visit[i] != 1)
                      113.             break;
                      114. }
                      115. if(i == pG->n)
                      116.         return 1;
                      117. else
                      118.         return 0;
                      119. }
                      120. //图的深度非递归遍历
                      121. int DFS(GRAPH *pG,int v)
                      122. {
                      123.     Stack *stack;
                      124. int i = 0;
                      125.     stack = create_empty_stack();
                      126.     push_stack(stack,pG->vex[v]);
                      127.     visit[v] = 1;
                      128.     printf(“V%d “,pG->vex[v]);
                      129. while(!is_empty_stack(stack) || !visit_all(pG))
                      130. {
                      131. for(i = 0;i < pG->n;i ++)
                      132. {
                      133. if(visit[i] == 0 && pG->adjmatrix[v][i] == 1)
                      134.                 break;
                      135. }
                      136. if(i == pG->n)
                      137. {
                      138.             v = pop_stack(stack);
                      139. }else{
                      140.             v = i;
                      141.             push_stack(stack,pG->vex[v]);
                      142.             visit[v] = 1;
                      143.             printf(“V%d “,pG->vex[v]);
                      144. }
                      145. }
                      146.     printf(“\n”);
                      147.     return 0;
                      148. }
                      149. //队列的设计
                      150. typedef struct node
                      151. {
                      152. int data;
                      153.     struct node *next;
                      154. }ListNode;
                      155. typedef struct
                      156. {
                      157.     ListNode *front;
                      158.     ListNode *rear;
                      159. }Queue;
                      160. //创建空队列
                      161. Queue *create_empty_queue()
                      162. {
                      163.     Queue *queue;
                      164.     ListNode *head;
                      165.     queue = (Queue *)malloc(sizeof(Queue));
                      166.     head = (ListNode *)malloc(sizeof(ListNode));
                      167.     queue->front = queue->rear = head;
                      168.     return queue;
                      169. }
                      170. //判断队列是否为空
                      171. int is_empty_queue(Queue *queue)
                      172. {
                      173. if(queue->rear == queue->front)
                      174.         return 1;
                      175. else
                      176.         return 0;
                      177. }
                      178. //入队
                      179. int EnterQueue(Queue *queue,int data)
                      180. {
                      181.     ListNode *temp;
                      182.     temp = (ListNode *)malloc(sizeof(ListNode));
                      183.     temp->data = data;
                      184.     temp->next = NULL;
                      185.     queue->rear->next = temp;
                      186.     queue->rear = temp;
                      187.     return 0;
                      188. }
                      189. //出队
                      190. int DelQueue(Queue *queue)
                      191. {
                      192.     ListNode *temp;
                      193.     temp = queue->front;
                      194.     queue->front = queue->front->next;
                      195.     free(temp);
                      196.     temp = NULL;
                      197.     return queue->front->data;
                      198. }
                      199. //图的广度遍历
                      200. int BFS(GRAPH *pG,int v)
                      201. {
                      202.     Queue *queue = create_empty_queue();
                      203. int i = 0;
                      204.     memset(&visit,0,sizeof(visit));
                      205.     EnterQueue(queue,v);
                      206.     visit[v] = 1;
                      207. while(!is_empty_queue(queue))
                      208. {
                      209.         v = DelQueue(queue);
                      210.         printf(“V%d “,pG->vex[v]);
                      211. for(i = 0;i < pG->n;i ++)
                      212. {
                      213. if(visit[i] == 0 && pG->adjmatrix[v][i] == 1)
                      214. {
                      215.                 EnterQueue(queue,i);
                      216.                 visit[i] = 1;
                      217. }
                      218. }
                      219. }
                      220.     printf(“\n”);
                      221.     return 0;
                      222. }
                      223. int main()
                      224. {
                      225.     GRAPH G;
                      226. int n;
                      227. //输入顶点,初始化图
                      228.     init_graph(&G);
                      229. //初始化邻接矩阵
                      230.     input_edge(&G);
                      231. //图的深度遍历
                      232.     DFS(&G, 0);
                      233. //图的广度遍历
                      234.     BFS(&G,0);
                      235.     return 0;
                      236. }

                      输出结果:

                      C点(三)G

                      前面基本总结介绍了C/C++的基础点,现在再总结下需要注意的高级点。

                      一.C++模板

                      模板是泛型编程的基础,泛型编程即以一种独立于任何特定类型的方式编写代码。

                      模板是创建泛型类或函数的蓝图或公式。库容器,比如迭代器和算法,都是泛型编程的例子,它们都使用了模板的概念。

                      每个容器都有一个单一的定义,比如 向量,我们可以定义许多不同类型的向量,比如 vector <int>vector <string>

                      您可以使用模板来定义函数和类,接下来让我们一起来看看如何使用。

                      函数模板

                      模板函数定义的一般形式如下所示:

                      template <class type> ret-type func-name(parameter list)
                      {
                         // 函数的主体
                      }  

                      在这里,type 是函数所使用的数据类型的占位符名称。这个名称可以在函数定义中使用。

                      下面是函数模板的实例,返回两个数种的最大值:

                      #include &lt;iostream&gt; #include &lt;string&gt; using namespace std; template &lt;typename T&gt; inline T const&amp; Max (T const&amp; a, T const&amp; b) { return a &lt; b ? b:a; } int main () { int i = 39; int j = 20; cout &lt;&lt; "Max(i, j): " &lt;&lt; Max(i, j) &lt;&lt; endl; double f1 = 13.5; double f2 = 20.7; cout &lt;&lt; "Max(f1, f2): " &lt;&lt; Max(f1, f2) &lt;&lt; endl; string s1 = "Hello"; string s2 = "World"; cout &lt;&lt; "Max(s1, s2): " &lt;&lt; Max(s1, s2) &lt;&lt; endl; return 0; }

                      类模板

                      正如我们定义函数模板一样,我们也可以定义类模板。泛型类声明的一般形式如下所示:

                      template <class type> class class-name {
                      .
                      .
                      .
                      }

                      在这里,type 是占位符类型名称,可以在类被实例化的时候进行指定。您可以使用一个逗号分隔的列表来定义多个泛型数据类型。

                      下面的实例定义了类 Stack<>,并实现了泛型方法来对元素进行入栈出栈操作:

                      #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cstdlib&gt; #include &lt;string&gt; #include &lt;stdexcept&gt; using namespace std; template &lt;class T&gt; class Stack { private: vector&lt;T&gt; elems; // 元素 public: void push(T const&amp;); // 入栈 void pop(); // 出栈 T top() const; // 返回栈顶元素 bool empty() const{ // 如果为空则返回真。 return elems.empty(); } }; template &lt;class T&gt; void Stack&lt;T&gt;::push (T const&amp; elem) { // 追加传入元素的副本 elems.push_back(elem); } template &lt;class T&gt; void Stack&lt;T&gt;::pop () { if (elems.empty()) { throw out_of_range("Stack&lt;&gt;::pop(): empty stack"); } // 删除最后一个元素 elems.pop_back(); } template &lt;class T&gt; T Stack&lt;T&gt;::top () const { if (elems.empty()) { throw out_of_range("Stack&lt;&gt;::top(): empty stack"); } // 返回最后一个元素的副本 return elems.back(); } int main() { try { Stack&lt;int&gt; intStack; // int 类型的栈 Stack&lt;string&gt; stringStack; // string 类型的栈 // 操作 int 类型的栈 intStack.push(7); cout &lt;&lt; intStack.top() &lt;&lt;endl; // 操作 string 类型的栈 stringStack.push("hello"); cout &lt;&lt; stringStack.top() &lt;&lt; std::endl; stringStack.pop(); stringStack.pop(); } catch (exception const&amp; ex) { cerr &lt;&lt; "Exception: " &lt;&lt; ex.what() &lt;&lt;endl; return -1; } } 
                      二.多线程
                      //参数依次是:创建的线程id,线程参数,调用的函数,传入的函数参数
                              int ret = pthread_create(&tids[i], NULL, say_hello, NULL);
                      三.C/C++标准库
                      C标准函数库

                      image

                      C++ 标准函数库

                      继承了C标准函数库及做了一些线程上的修改

                      C++标准类库

                      STL,输入输出等,重点就是STL。