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。

                      C点(一)C++基础点

                      基于C的基础上再补充C++的一些基础要点。

                      一.数组指针

                      #include &lt;iostream&gt; using namespace std; const int MAX = 3; int main () { int var[MAX] = {10, 100, 200}; for (int i = 0; i &lt; MAX; i++) { *var = i; // 这是正确的语法 *(var + i) = 20;//正确 var++; // 这是不正确的 } return 0; } 

                      二.引用 vs 指针
                      区别:

                      引用很容易与指针混淆,它们之间有三个主要的不同:

                      • 不存在空引用。引用必须连接到一块合法的内存。
                      • 一旦引用被初始化为一个对象,就不能被指向到另一个对象。指针可以在任何时候指向到另一个对象。
                      • 引用必须在创建时被初始化。指针可以在任何时间被初始化。
                      引用的使用:

                      作为形参使用:更加安全高效,不需要内存复制操作。

                      作为返回值:被引用的对象不能超出作用域。

                      int&amp; func() { int q; //! return q; // 在编译时发生错误 static int x; return x; // 安全,x 在函数作用域外依然是有效的 }

                      三.类对象-封装
                      拷贝构造函数

                      拷贝构造函数是一种特殊的构造函数,它在创建对象时,是使用同一类中之前创建的对象来初始化新创建的对象。拷贝构造函数通常用于:

                      • 通过使用另一个同类型的对象来初始化新创建的对象。

                      • 复制对象把它作为参数传递给函数。

                      • 复制对象,并从函数返回这个对象。

                      如果在类中没有定义拷贝构造函数,编译器会自行定义一个。如果类带有指针变量,并有动态内存分配,则它必须有一个拷贝构造函数。拷贝构造函数的最常见形式如下:

                      #include &lt;iostream&gt; using namespace std; class Box { double width; public: friend void printWidth( Box box ); void setWidth( double wid ); }; // 成员函数定义 void Box::setWidth( double wid ) { width = wid; } // 请注意:printWidth() 不是任何类的成员函数 void printWidth( Box box ) { /* 因为 printWidth() 是 Box 的友元,它可以直接访问该类的任何成员 */ cout &lt;&lt; "Width of box : " &lt;&lt; box.width &lt;&lt;endl; } // 程序的主函数 int main( ) { Box box; // 使用成员函数设置宽度 box.setWidth(10.0); // 使用友元函数输出宽度 printWidth( box ); return 0; }
                      内联函数

                      C++ 内联函数是通常与类一起使用。如果一个函数是内联的,那么在编译时,编译器会把该函数的代码副本放置在每个调用该函数的地方。

                      对内联函数进行任何修改,都需要重新编译函数的所有客户端,因为编译器需要重新更换一次所有的代码,否则将会继续使用旧的函数。

                      如果想把一个函数定义为内联函数,则需要在函数名前面放置关键字 inline,在调用函数之前需要对函数进行定义。如果已定义的函数多于一行,编译器会忽略 inline 限定符。

                      在类定义中的定义的函数都是内联函数,即使没有使用 inline 说明符。

                      类静态成员与静态函数

                      我们可以使用 static 关键字来把类成员定义为静态的。当我们声明类的成员为静态时,这意味着无论创建多少个类的对象,静态成员都只有一个副本。

                      静态成员在类的所有对象中是共享的。如果不存在其他的初始化语句,在创建第一个对象时,所有的静态数据都会被初始化为零。我们不能把静态成员放置在类的定义中,但是可以在类的外部通过使用范围解析运算符 :: 来重新声明静态变量从而对它进行初始化,如下面的实例所示。

                      如果把函数成员声明为静态的,就可以把函数与类的任何特定对象独立开来。静态成员函数即使在类对象不存在的情况下也能被调用,静态函数只要使用类名加范围解析运算符 :: 就可以访问。

                      静态成员函数只能访问静态数据成员,不能访问其他静态成员函数和类外部的其他函数。

                      静态成员函数有一个类范围,他们不能访问类的 this 指针。您可以使用静态成员函数来判断类的某些对象是否已被创建.

                      #include <iostream> using namespace std; class Box { public: static int objectCount; // 构造函数定义 Box(double l=2.0, double b=2.0, double h=2.0) { cout <<"Constructor called." << endl; length = l; breadth = b; height = h; // 每次创建对象时增加 1 objectCount++; } double Volume() { return length * breadth * height; } static int getCount() { return objectCount; } private: double length; // 长度 double breadth; // 宽度 double height; // 高度 }; // 初始化类 Box 的静态成员 int Box::objectCount = 0; int main(void) { // 在创建对象之前输出对象的总数 cout << "Inital Stage Count: " << Box::getCount() << endl; Box Box1(3.3, 1.2, 1.5); // 声明 box1 Box Box2(8.5, 6.0, 2.0); // 声明 box2 // 在创建对象之后输出对象的总数 cout << "Final Stage Count: " << Box::getCount() << endl; return 0; }

                      四.继承+多态

                      继承:is-a

                      多态:以虚函数实现,进行面向对象的抽象。同时通过纯虚函数,实现接口设计编程。

                      五.异常处理

                      C++ 标准的异常

                      C++ 提供了一系列标准的异常,定义在 <exception> 中,我们可以在程序中使用这些标准的异常。它们是以父子类层次结构组织起来的,如下所示:

                      C++ 异常的层次结构

                      下表是对上面层次结构中出现的每个异常的说明:

                      image

                      定义新的异常

                      可以通过继承和重载 exception 类来定义新的异常。下面的实例演示了如何使用 std::exception 类来实现自己的异常

                      #include &lt;iostream&gt; #include &lt;exception&gt; using namespace std; struct MyException : public exception { const char * what () const throw () { return "C++ Exception"; } }; int main() { try { throw MyException(); } catch(MyException&amp; e) { std::cout &lt;&lt; "MyException caught" &lt;&lt; std::endl; std::cout &lt;&lt; e.what() &lt;&lt; std::endl; } catch(std::exception&amp; e) { //其他的错误 } }

                      抛出异常+捕获异常

                      throw:

                      double division(int a, int b) { if( b == 0 ) { throw "Division by zero condition!"; } return (a/b); }

                      try…catch…

                      try { // 保护代码 }catch( ExceptionName e1 ) { // catch 块 }catch( ExceptionName e2 ) { //任何异常,作为保护代码使用 }catch(... ) { // catch 块 }

                      六.内存管理

                      new 可以对内存进行初始化操作即有构造函数,malloc只申请分配内存。

                      七.预处理*宏

                      # 和 ## 运算符

                      # 和 ## 预处理运算符在 C++ 和 ANSI/ISO C 中都是可用的。# 运算符会把 replacement-text 令牌转换为用引号引起来的字符串。

                      ## 运算符用于连接两个令牌。

                      #include <iostream>
                      using namespace std;
                      
                      #define concat(a, b) a ## b
                      int main()
                      {
                         int xy = 100;
                         
                         cout << concat(x, y);
                         return 0;
                      }

                      c点(一)C基础点

                      记录下C编程的一些基础注意点。常量,全局变量,局部变量,形参变量,作用域,运算符,修饰符。

                      编译,环境

                      一.常量

                      使用 #define 预处理器。:

                      #include &lt;stdio.h&gt; #define LENGTH 10 #define WIDTH 5 #define NEWLINE '\n' 

                      使用 const 关键字。:

                      const int LENGTH = 10; const int WIDTH = 5; const char NEWLINE = '\n';

                      二:变量+作用域

                      任何一种编程中,作用域是程序中定义的变量所存在的区域,超过该区域变量就不能被访问。C 语言中有三个地方可以声明变量:

                      1. 在函数或块内部的局部变量
                      2. 在所有函数外部的全局变量
                      3. 形式参数的函数参数定义中

                      让我们来看看什么是局部变量、全局变量和形式参数。

                      局部变量

                      在某个函数或块的内部声明的变量称为局部变量。它们只能被该函数或该代码块内部的语句使用。局部变量在函数外部是不可知的。

                      全局变量

                      全局变量是定义在函数外部,通常是在程序的顶部。全局变量在整个程序生命周期内都是有效的,在任意的函数内部能访问全局变量。

                      全局变量可以被任何函数访问。也就是说,全局变量在声明后整个程序中都是可用的。

                      形式参数

                      函数的参数,形式参数,被当作该函数内的局部变量,它们会优先覆盖全局变量。

                      初始化局部变量和全局变量

                      当局部变量被定义时,系统不会对其初始化,您必须自行对其初始化。定义全局变量时,系统会自动对其初始化。

                      image

                      #include &lt;stdio.h&gt; /* 全局变量声明 */ int a = 20; int main () { /* 在主函数中的局部变量声明 */ int a = 10; int b = 20; int c = 0; int sum(int, int); printf ("value of a in main() = %d\n", a); c = sum( a, b); printf ("value of c in main() = %d\n", c); return 0; } /* 添加两个整数的函数 */ int sum(int a, int b) { printf ("value of a in sum() = %d\n", a); printf ("value of b in sum() = %d\n", b); return a + b; }
                      三.存储类
                      auto 存储类:

                      auto 存储类是所有局部变量默认的存储类。

                      register 存储类

                      register 存储类用于定义存储在寄存器中而不是 RAM 中的局部变量。这意味着变量的最大尺寸等于寄存器的大小(通常是一个词),且不能对它应用一元的 ‘&’ 运算符(因为它没有内存位置)。

                      static 存储类

                      static 存储类指示编译器在程序的生命周期内保持局部变量的存在,而不需要在每次它进入和离开作用域时进行创建和销毁。因此,使用 static 修饰局部变量可以在函数调用之间保持局部变量的值。

                      static 修饰符也可以应用于全局变量。当 static 修饰全局变量时,会使变量的作用域限制在声明它的文件内。

                      在 C 编程中,当 static 用在类数据成员上时,会导致仅有一个该成员的副本被类的所有对象共享。

                      extern 存储类

                      extern 存储类用于提供一个全局变量的引用,全局变量对所有的程序文件都是可见的。当您使用 ‘extern’ 时,对于无法初始化的变量,会把变量名指向一个之前定义过的存储位置。

                      四.运算符

                      位运算符

                      位运算符作用于位,并逐位执行操作。&、 | 和 ^ 的真值表如下所示:

                      image

                      假设如果 A = 60,且 B = 13,现在以二进制格式表示,它们如下所示:

                      A = 0011 1100

                      B = 0000 1101

                      —————–

                      A&B = 0000 1100

                      A|B = 0011 1101

                      A^B = 0011 0001

                      ~A  = 1100 0011

                      下表显示了 C 语言支持的位运算符。假设变量 A 的值为 60,变量 B 的值为 13,则:

                      image

                      五.形参

                      image

                      引用:

                      /* 函数定义 */ void swap(int &amp;x, int &amp;y) { int temp; temp = x; /* 保存地址 x 的值 */ x = y; /* 把 y 赋值给 x */ y = temp; /* 把 temp 赋值给 y */ return; }

                      指针:

                      /* 函数定义 */ void swap(int *x, int *y) { int temp; temp = *x; /* 保存地址 x 的值 */ *x = *y; /* 把 y 赋值给 x */ *y = temp; /* 把 temp 赋值给 y */ return; }

                      六.指针+数组
                      数组:

                      #include &lt;stdio.h&gt; /* 函数声明 */ double getAverage(int arr[], int size); int main () { /* 带有 5 个元素的整型数组 */ int balance[5] = {1000, 2, 3, 17, 50}; double avg; /* 传递一个指向数组的指针作为参数 */ avg = getAverage( balance, 5 ) ; /* 输出返回值 */ printf( "平均值是: %f ", avg ); return 0; }

                      数组指针:

                      数组名是一个指向数组中第一个元素的常量指针。因此,在下面的声明中:

                      double balance[50];

                      balance 是一个指向 &balance[0] 的指针,即数组 balance 的第一个元素的地址。因此,下面的程序片段把 p 赋值为 balance 的第一个元素的地址:

                      double *p;
                      double balance[10];
                      
                      p = balance;

                      使用数组名作为常量指针是合法的,反之亦然。因此,*(balance + 4) 是一种访问 balance[4] 数据的合法方式。

                      一旦您把第一个元素的地址存储在 p 中,您就可以使用 *p、*(p+1)、*(p+2) 等来访问数组元素。

                      指针的指针

                      指向指针的指针是一种多级间接寻址的形式,或者说是一个指针链。通常,一个指针包含一个变量的地址。当我们定义一个指向指针的指针时,第一个指针包含了第二个指针的地址,第二个指针指向包含实际值的位置。

                      C 中指向指针的指针

                      七.字符串
                      字符串

                      在 C 语言中,字符串实际上是使用 null 字符 ‘\0′ 终止的一维字符数组。因此,一个以 null 结尾的字符串,包含了组成字符串的字符。

                      下面的声明和初始化创建了一个 “Hello” 字符串。由于在数组的末尾存储了空字符,所以字符数组的大小比单词 “Hello” 的字符数多一个。

                      char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

                      依据数组初始化规则,您可以把上面的语句写成以下语句:

                      char greeting[] = "Hello";

                      以下是 C/C++ 中定义的字符串的内存表示:

                      C/C++ 中的字符串表示

                      其实,您不需要把 null 字符放在字符串常量的末尾。C 编译器会在初始化数组时,自动把 ‘\0′ 放在字符串的末尾。

                      操作字符串的函数

                      image

                      八.可变参数

                      有时,您可能会碰到这样的情况,您希望函数带有可变数量的参数,而不是预定义数量的参数。C 语言为这种情况提供了一个解决方案,它允许您定义一个函数,能根据具体的需求接受可变数量的参数。下面的实例演示了这种函数的定义。

                      int func(int, ... ) 
                      {
                         .
                         .
                         .
                      }
                      
                      int main()
                      {
                         func(1, 2, 3);
                         func(1, 2, 3, 4);
                      }

                      请注意,函数 func() 最后一个参数写成省略号,即三个点号(),省略号之前的那个参数总是 int,代表了要传递的可变参数的总数。为了使用这个功能,您需要使用 stdarg.h 头文件,该文件提供了实现可变参数功能的函数和宏。具体步骤如下:

                      • 定义一个函数,最后一个参数为省略号,省略号前面的那个参数总是 int,表示了参数的个数。
                      • 在函数定义中创建一个 va_list 类型变量,该类型是在 stdarg.h 头文件中定义的。
                      • 使用 int 参数和 va_start 宏来初始化 va_list 变量为一个参数列表。宏 va_start 是在 stdarg.h 头文件中定义的。
                      • 使用 va_arg 宏和 va_list 变量来访问参数列表中的每个项。
                      • 使用宏 va_end 来清理赋予 va_list 变量的内存。

                      现在让我们按照上面的步骤,来编写一个带有可变数量参数的函数,并返回它们的平均值:

                      #include <stdio.h>
                      #include <stdarg.h>
                      
                      double average(int num,...)
                      {
                      
                          va_list valist;
                          double sum = 0.0;
                          int i;
                      
                          /* 为 num 个参数初始化 valist */
                          va_start(valist, num);
                      
                          /* 访问所有赋给 valist 的参数 */
                          for (i = 0; i < num; i++)
                          {
                             sum += va_arg(valist, int);
                          }
                          /* 清理为 valist 保留的内存 */
                          va_end(valist);
                      
                          return sum/num;
                      }
                      
                      int main()
                      {
                         printf("Average of 2, 3, 4, 5 = %f\n", average(4, 2,3,4,5));
                         printf("Average of 5, 10, 15 = %f\n", average(3, 5,10,15));
                      }

                      当上面的代码被编译和执行时,它会产生下列结果。应该指出的是,函数 average() 被调用两次,每次第一个参数都是表示被传的可变参数的总数。省略号被用来传递可变数量的参数。

                      Average of 2, 3, 4, 5 = 3.500000
                      Average of 5, 10, 15 = 10.000000
                      九.字符串

                       

                      strlen():返回的长度不包括空结束字符 sizeof() 运算符

                      int _tmain(int argc, _TCHAR* argv[]) { char str[10] = "1234567"; const char* cstr = "1234567"; void * pvoid; int len = strlen("1234567");// len = 7; len = sizeof("1234567");// len = 8 * sizeof(char) = 8; len = sizeof(str); // len = 10* sizeof(char) = 10; len = sizeof(pvoid);// len = 4 ;指针长度 len = sizeof(cstr);// len = 4 = sizeof(void *) len = strlen(cstr); // len = 7* sizeof(char) = 7; return 0; }