## 1.我们印象中的 SpringBoot 做了啥？

- mvc 功能
- 零配置
 - 没有 spring 相关的 xml
 - 没有 web.xml
- 内嵌容器（tomcat jetty）
- 自动配置



## 2.配置文件都干了什么？

### 2.1 spring 相关的 xml

#### 2.1.1 applicationContext.xml

```xml
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans" xmlns:context="http://www.springframework.org/schema/context" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:aop="http://www.springframework.org/schema/aop"
 xmlns:tx="http://www.springframework.org/schema/tx" xmlns:p="http://www.springframework.org/schema/p" xmlns:util="http://www.springframework.org/schema/util" xmlns:jdbc="http://www.springframework.org/schema/jdbc"
 xmlns:cache="http://www.springframework.org/schema/cache"
 xsi:schemaLocation="
 http://www.springframework.org/schema/context
 http://www.springframework.org/schema/context/spring-context.xsd
 http://www.springframework.org/schema/beans
 http://www.springframework.org/schema/beans/spring-beans.xsd
 http://www.springframework.org/schema/tx
 http://www.springframework.org/schema/tx/spring-tx.xsd
 http://www.springframework.org/schema/jdbc
 http://www.springframework.org/schema/jdbc/spring-jdbc-3.1.xsd
 http://www.springframework.org/schema/cache
 http://www.springframework.org/schema/cache/spring-cache-3.1.xsd
 http://www.springframework.org/schema/aop
 http://www.springframework.org/schema/aop/spring-aop.xsd
 http://www.springframework.org/schema/util
 http://www.springframework.org/schema/util/spring-util.xsd">
 
 
 <context:component-scan base-package="com.eduoinfo.finances.bank.web"></context:component-scan>
 
 
 <bean id="propertyConfigurer" class="org.springframework.beans.factory.config.PropertyPlaceholderConfigurer">
 <property name="locations">
 <list>
 <value>classpath*:jdbc.properties</value>
 </list>
 </property>
 </bean>
 
 
 <bean id="dataSource" class="com.alibaba.druid.pool.DruidDataSource" init-method="init" destroy-method="close">
 
 <property name="url" value="${jdbc.url}" />
 <property name="username" value="${jdbc.username}" />
 <property name="password" value="${jdbc.password}" />
 
 
 <property name="initialSize" value="1" />
 <property name="minIdle" value="1" />
 <property name="maxActive" value="20" />
 
 
 <property name="maxWait" value="60000" />
 
 
 <property name="timeBetweenEvictionRunsMillis" value="60000" />
 
 
 <property name="minEvictableIdleTimeMillis" value="300000" />
 
 <property name="validationQuery" value="SELECT 'x'" />
 <property name="testWhileIdle" value="true" />
 <property name="testOnBorrow" value="false" />
 <property name="testOnReturn" value="false" />
 
 
 <property name="poolPreparedStatements" value="false" />
 <property name="maxPoolPreparedStatementPerConnectionSize" value="20" />
 
 
 <property name="filters" value="stat" />
 </bean>
 
 
 <bean id="sqlSessionFactory" class="org.mybatis.spring.SqlSessionFactoryBean" p:dataSource-ref="dataSource" p:configLocation="classpath:mybatis-config.xml" p:mapperLocations="classpath:com/eduoinfo/finances/bank/web/dao/*.xml" />
 
 
 <bean class="org.mybatis.spring.mapper.MapperScannerConfigurer" p:basePackage="com.eduoinfo.finances.bank.web.dao" p:sqlSessionFactoryBeanName="sqlSessionFactory" />
 
 
 <bean id="transactionManager" class="org.springframework.jdbc.datasource.DataSourceTransactionManager" p:dataSource-ref="dataSource" />
 
 
 <aop:aspectj-autoproxy proxy-target-class="true" />
 
 
 <tx:annotation-driven transaction-manager="transactionManager" />
 
 
 <cache:annotation-driven cache-manager="cacheManager" />
 <bean id="ehCacheManagerFactory" class="org.springframework.cache.ehcache.EhCacheManagerFactoryBean" p:configLocation="classpath:ehcache.xml" />
 <bean id="cacheManager" class="org.springframework.cache.ehcache.EhCacheCacheManager" p:cacheManager-ref="ehCacheManagerFactory" />
 
</beans>
```

- 扫描业务 bean
- 配置 bean


#### 2.1.2 springMVC.xml 

```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" 
 xmlns:task="http://www.springframework.org/schema/task"
 xsi:schemaLocation="
 http://www.springframework.org/schema/beans 
 http://www.springframework.org/schema/beans/spring-beans-4.2.xsd 
 http://www.springframework.org/schema/context 
 http://www.springframework.org/schema/context/spring-context-4.2.xsd 
 http://www.springframework.org/schema/mvc 
 http://www.springframework.org/schema/mvc/spring-mvc-4.2.xsd 
 http://www.springframework.org/schema/task 
 http://www.springframework.org/schema/task/spring-task-4.2.xsd"> 
 
  
 <context:component-scan base-package="com.edu.test.controller"/>
		
		<bean id="mappingJacksonHttpMessageConverter"
			 class="org.springframework.http.converter.json.MappingJackson2HttpMessageConverter">
			<property name="supportedMediaTypes">
				<list>
					<value>text/html;charset=UTF-8</value>
				</list>
			</property>
		</bean>
  
 <bean class="org.springframework.web.servlet.view.InternalResourceViewResolver">
 
 <property name="prefix" value="/WEB-INF/jsp/"></property>
 
 <property name="suffix" value=".jsp"></property>
 </bean>
</beans>
```

- 扫描 controller
- Jackson2HttpMessageConverter(json 解析器，非必须的)
- 2.1.2.3 InternalResourceViewResolver（视图解析器）

### 2.2 web.xml


```xml
 
<?xml version="1.0" encoding="UTF-8"?>
<web-app xmlns="http://java.sun.com/xml/ns/javaee"
 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
 xsi:schemaLocation="http://java.sun.com/xml/ns/javaee http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd "
 version="2.5">
 <display-name>Archetype Created Web Application</display-name>
 <context-param>
 <param-name>webAppRootKey</param-name>
 <param-value>spring4.root</param-value>
 </context-param>


 
 
 <context-param>
 <param-name>contextConfigLocation</param-name>
 <param-value>classpath:Spring/applicationContext.xml,classpath:Spring/spring-mybatis.xml</param-value>
 </context-param>
 


 
 
 <filter>
 <filter-name>characterEncodingFilter</filter-name>
 <filter-class>org.springframework.web.filter.CharacterEncodingFilter</filter-class>
 <init-param>
 <param-name>encoding</param-name>
 <param-value>UTF-8</param-value>
 </init-param>
 <init-param>
 <param-name>forceEncoding</param-name>
 <param-value>true</param-value>
 </init-param>
 </filter>
 
 <filter-name>encodingFilter</filter-name>
 <filter-class>org.springframework.web.filter.CharacterEncodingFilter</filter-class>
 <init-param>
 
 <param-name>encoding</param-name>
 <param-value>UTF-8</param-value>
 </init-param>
 </filter>
 
 
 <listener>
 <listener-class>org.springframework.web.context.ContextLoaderListener</listener-class>
 </listener>

 
 <listener>
 <listener-class>org.springframework.web.context.request.RequestContextListener</listener-class>
 </listener>
 
 
 
 
 
 <servlet>
 <servlet-name>SpringMVC</servlet-name>
 <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
 <init-param>
 <param-name>contextConfigLocation</param-name>
 <param-value>classpath:Spring/spring-mvc.xml</param-value>
 </init-param>
 <load-on-startup>1</load-on-startup>
 </servlet>

 
 <servlet-mapping>
 <servlet-name>SpringMVC</servlet-name>
 <url-pattern>*.do</url-pattern>
 </servlet-mapping>

 
 <session-config>
 <session-timeout>60</session-timeout>
 </session-config>

 
 <welcome-file-list>
 <welcome-file>/index.jsp</welcome-file>
 </welcome-file-list>
</web-app>
```

#### 2.2.1 ContextLoaderListener

对于一个 spring 项目，在项目启动的时候需要初始化 spring 的环境，说白了就是执行下面的代码

```java
AnnotationConfigApplicationContext ac = new AnnotationConfigApplicationContext(Appconfig.class);
```

如果是在非 web 项目中，我们可以在 main 方法中，执行上述的代码；
但是在 web 项目中，由于项目的入口在容器( tomcat ) 中，而 tomcat 启动回去解析 web.xml ，于是 web.xml 中配置一个 ContextLoaderListener， 让容器在启动的时候去初始化 spring 环境

#### 2.2.2 DispatcherServlet 

	- 拦截请求
	- 负责解析 spring-mvc.xml
	- <load-on-startup>1</load-on-startup> 让容器启动的时候调用该 servlet 的 init 方法

### 2.3 基本流程

容器( tomcat )启动 -> 加载 web.xml -> 调用 ContextLoaderListener 去 init spring (spring.xml) -> DispatcherServlet 加载 springMVC.xml


## 3 实现零配置

**在 springBoot 之前，其实就已经可以实现无 xml 了**
基于 xml 配置的是原 spring 2 和之前版本的写法。在 spring4 之后，已经提供了无 xml 写法。

### 3.1 spring mvc官方文档 example

[SpringWebMVC 官方文档链接](https://docs.spring.io/spring/docs/current/spring-framework-reference/web.html#mvc-servlet)
The following example of the Java configuration registers and initializes the DispatcherServlet, which is auto-detected by the Servlet container (see Servlet Config):

```java
public class MyWebApplicationInitializer implements WebApplicationInitializer {

 @Override
 public void onStartup(ServletContext servletCxt) {

 // Load Spring web application configuration
 AnnotationConfigWebApplicationContext ac = new AnnotationConfigWebApplicationContext();
 ac.register(AppConfig.class);
 ac.refresh();

 // Create and register the DispatcherServlet
 DispatcherServlet servlet = new DispatcherServlet(ac);
 ServletRegistration.Dynamic registration = servletCxt.addServlet("app", servlet);
 registration.setLoadOnStartup(1);
 registration.addMapping("/app/*");
 }
}
```

```java
@Configuration
@ComponentScan(basePackages = "com.yui.study")
public class AppConfig {
/*	@Bean
	public MyService myService() {
		return new MyServiceImpl();
	}*/
}
```

### 3.2 如何注册 DispatcherServlet 

#### 3.2.1 怎么注册一个 servlet

- web.xml 中配置 <servlet></servlet>
- @WebServlet
- servletCxt.addServlet

### 3.2 零配置代码说明

- ContextLoaderListener： 初始化 spring 环境

```java
AnnotationConfigWebApplicationContext ac = new AnnotationConfigWebApplicationContext();
```

- spring.xml 和 springMVC.xml ：配置和扫描 bean

```java
ac.register(AppConfig.class);
```

```java
@Configuration
@ComponentScan(basePackages = "com.yui.study") // 扫描注解
public class AppConfig {
 	// 配置 bean
	@Bean
	public MyService myService() {
		return new MyServiceImpl();
	}
}
```

- DispatcherServlet 实现拦截

```java
	// 声明 DispatcherServlet
	DispatcherServlet servlet = new DispatcherServlet(ac);
	// 向容器注册 DispatcherServlet
 	ServletRegistration.Dynamic registration = servletCxt.addServlet("app", servlet);
	// 设置容器启动时加载该 servlet
	registration.setLoadOnStartup(1);
	// 拦截请求设置
	registration.addMapping("/app/*");
```

### 3.3 为什么会调到 onStartup

#### 3.3.1 servlet 3.0 - javax.servlet.ServletContainerInitializer

在web容器启动时为提供给第三方组件机会做一些初始化的工作，例如注册servlet或者filtes等，servlet规范中通过ServletContainerInitializer实现此功能。

每个框架要使用ServletContainerInitializer就必须在对应的jar包的META-INF/services 目录创建一个名为javax.servlet.ServletContainerInitializer的文件，文件内容指定具体的ServletContainerInitializer实现类，那么，当web容器启动时就会运行这个初始化器做一些组件内的初始化工作

#### 3.3.2 org.springframework.web.SpringServletContainerInitializer

```java
@HandlesTypes(WebApplicationInitializer.class)
public class SpringServletContainerInitializer implements ServletContainerInitializer {

	@Override
	public void onStartup(@Nullable Set<Class<?>> webAppInitializerClasses, ServletContext servletContext)
			throws ServletException {
		/**
		 1. webAppInitializerClasses 所有实现 WebApplicationInitializer 的接口,
		 {@link javax.servlet.annotation.HandlesTypes} 注解表示要拦截个规则
		 2. servletContext servlet初始化上下文
		 */
		// WebApplicationInitializer 实例化 list， 由 Class -> Object
		List<WebApplicationInitializer> initializers = new LinkedList<>();

		if (webAppInitializerClasses != null) {
			// 从 webAppInitializerClasses 中获取 WebApplicationInitializer 类型的类
			for (Class<?> waiClass : webAppInitializerClasses) {
				/*
				 如果 {waiClass 不是一个接口} 且 {waiClass 不是抽象的} 且 {waiClass 必须是实现 WebApplicationInitializer.class}
				 WebApplicationInitializer.class.isAssignableFrom(waiClass) 这句是为了防止容器( tomcat 等)实现有问题，传递了非指定类型过来
				 */
				if (!waiClass.isInterface() && !Modifier.isAbstract(waiClass.getModifiers()) &&
						WebApplicationInitializer.class.isAssignableFrom(waiClass)) {
					try {
						// 实例化 waiClass 并添加到 initializers list 中
						initializers.add((WebApplicationInitializer)
								ReflectionUtils.accessibleConstructor(waiClass).newInstance());
					} catch (Throwable ex) {
						throw new ServletException("Failed to instantiate WebApplicationInitializer class", ex);
					}
				}
			}
		}
		// 如果 initializers 为空 输出日志，并结束初始化
		if (initializers.isEmpty()) {
			servletContext.log("No Spring WebApplicationInitializer types detected on classpath");
			return;
		}

		servletContext.log(initializers.size() + " Spring WebApplicationInitializers detected on classpath");
		/**
		 对 initializers 进行排序,从小到大排
		 @see org.springframework.core.OrderComparator#doCompare
		 继承 Ordered 或者 PriorityOrdered 重写 getOrder 进行排序
		 排序规则： PriorityOrdered 在 Ordered 前面，同个接口实现，getOrder() 的值越小越排在前面
		 */
		AnnotationAwareOrderComparator.sort(initializers);
		// 调用所有 initializer 的 onStartUp() 方法, 并将 servlet 上下文传递过去
		for (WebApplicationInitializer initializer : initializers) {
			initializer.onStartup(servletContext);
		}
	}
}
```

#### 3.3.3 onStartup 的入参 - webAppInitializerClasses

- ```Set<Class<?>> webAppInitializerClasses```

```java
所有当前 class 的类注解 @HandlesTypes 的 value 的实现类
```

### 3.4 内嵌容器

#### 3.4.1 依赖

```gradle
 compile("org.apache.tomcat.embed:tomcat-embed-core:8.5.33")
```

#### 3.4.2 main

```
public class MySpringBootApplication {
	public static void main(String[] args) throws Exception{
		Tomcat myTomcat = new Tomcat();
		myTomcat.setPort(8090);

		myTomcat.addWebapp("/","D:\\data\\web");
		myTomcat.start();
		myTomcat.getServer().await();


		/*// Load Spring web application configuration
		myTomcat.addContext("/","D:\\data\\web");
		AnnotationConfigWebApplicationContext ac = new AnnotationConfigWebApplicationContext();
		ac.register(AppConfig.class);
//		ac.refresh();

		// Create and register the DispatcherServlet
		DispatcherServlet servlet = new DispatcherServlet(ac);
		Wrapper mvc = myTomcat.addServlet("/","app", servlet);
		mvc.setLoadOnStartup(1);
		mvc.addMapping("/*");
		myTomcat.start();
		myTomcat.getServer().await();*/
	}
}
```

What's SpringBoot do

## 1. 树(tree)

### 1.1 概念

#### 1.1.1 树的定义

- 树（Tree）是 n(n >= 0) 个结点的有限集。
- n = 0 时称为空树。
- 在任意一颗非空树中：
 - 有且仅有一个特定的称为根（root）的结点
 - 当 n > 1 时，其余结点可分为 m(m>0) 个互不相交的有限集 T1 、T2 ... Tn ，其中每一个集合本身有事一棵树，并且称为根的子树（SubTree)



#### 1.1.2 树的分类

- 树的结点包含一个数据元素及若干指向其子树的分支；
- 结点拥有的子树数称为结点的度（Degree）；
- 度为0的结点称为叶结点（Leaf）或终端结点；
- 度不为0的结点称为非终端结点或分支结点；
- 除根结点之外，分支结点也称为内部结点。
- 树的度是树内各结点的度的最大值；



![5.tree-category](https://raw.githubusercontent.com/XuZhuohao/picture/master/Algorithm/data-struct/5.tree-category.png)



#### 1.1.3 结点间关系

- 结点的子树的根称为该结点的孩子**（Child）**
- 该结点称为孩子的双亲**（Parent）**
- 同一个双亲的孩子之间互称兄弟**（Sibling）**。
- 结点的祖先是从根到该结点所经分支上的所有结点。
- 以某结点为根的子树中的任一结点都称为该结点的子孙。



#### 1.1.4 其他概念

- 结点的层次**（Level）**
 - 根为第一层，根的孩子为第二层，依次类推。
 - 树中结点的最大层次称为树的深度（Depth）或高度
- 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为**有序树**，否则称为**无序树**。
- **森林（Forest）**是m（m>0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。





### 1.2 树的抽象数据类型

```c
ADT树(tree)
	Data树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关系。
Operation 
	InitTree(*T):构造空树T。
	DestroyTree(*T):销毁树T。
	CreateTree(*T,definition):按definition中给出树的定义来构造树。
	ClearTree(*T):若树T存在,则将树T清为空树。
	TreeEmpty(T):若T为空树,返回true,否则返回false。
	Treepepth(T):返回T的深度。
	Root(T):返回T的根结点。
	Value(T,cur_e):cur_e是树T中一个结点,返回此结点的值。
	Assign(T,cur_e,value):给树T的结点cur_e赋值为value。
	Parent(T,cur_e):若cur_e是树T的非根结点,则返回它的双亲,否则返回空。
	Leftchild(T,cur_e):若cur_e是树T的非叶结点,则返回它的最左孩子,否则返回空。
	RightSibling(T,cur_e):若cur_e有右兄弟,则返回它的右兄弟,否则返回空。
	InsertChild(*T,*p,i,c):其中p指向树T的某个结点,i为所指结点p的度加上1,非空树c与T不相交,操作结果为插入c为树T中p指结点的第棵子树。
	Deletechild(*T,*p,i):其中p指向树T的某个结点,i为所指结点p的度,操作结果为删除T中p所指结点的第i棵子树。
endADT
```



### 1.3 树的存储结构

#### 1.3.1 双亲表示法

**在每个结点中，附设一个指示器指示其双亲结点到链表中的位置**

这种设置，我们可以很快找到结点的根节点，但是想要找到子结点，只能通过遍历整个结构，所以为了解决该问题，可以为其结点增加**长子域，右兄弟**域等等



#### 1.3.2 孩子表示法

##### 1.3.2.1多重链表表示法

**每个结点设置多个指针域，其中每个指针指向一颗子树有的根节点，我们吧这种方法叫做多重链表表示法**

由于树的每个结点的度是不同的，所以有以下两种方案来解决

###### 1.3.2.1.1 方案一（固定大小的指针域）

**用树的度作为作为指针域的大小去构建结点（树的度：树内各结点的度的最大值）**

以这种方案去构建，当树内各个结点的度相差比较远的时候，会造成空间浪费，相反，当树内各个结点的度相差比较小的时候，则该存储结构有更高的优势（减少运算）



###### 1.3.2.1.2 方案二（按需分配的指针域）

**每个结点指针域的个数等于该结点的度，用一个位置来存储结点指针域的个数**

这种方法克服了浪费空间的缺点，对空间利用率提高了，但是由于各个结点的链表结构式不同的，加上要维护结点的度的数值，运算上会带来时间上的损耗

##### 1.3.2.2 孩子表示法

**把每个结点的孩子结点排列起来，以单链表作存储结构，则 n 个结点有 n 个孩子链表，如果叶子结点则此单链表为空。然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中**



#### 1.3.3 双亲孩子表示法

孩子表示法对于查找孩子的双亲比较麻烦，于是结合孩子标识法和双亲表示法，构建一个双亲孩子表示法

**在孩子表示法中增加存放双亲结点指针的指针域**





## 2. 二叉树（Binary Tree)

**二叉树是 n ( n >= 0 ) 个结点的有限集合，改集合或者为空集（称为空二叉树），或者由一个根结点和两颗互不想交的、分别称为根结点的左子树和右子树的二叉树组成**

### 2.1 二叉树的特点

- 特点：
 - **每个结点最多有两棵子树**，所以二又树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。
 - **左子树和右子树是有顺序的，次序不能任意颠倒**。就像人是双手、双脚，但显然左手、左脚和右手、右脚是不一样的，右手戴左手套、右脚穿左鞋都会极其别扭和难受。
 - **即使树中某结点只有一棵子树，也要区分它是左子树还是右子树**。

- 形态：
 - 空二叉树
 - 只有根结点
 - 只有一个左子树
 - 只有一个右子树
 - 既有左子树，又有右子树

### 2.2 特殊二叉树

#### 2.2.1 斜树

**所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。**



#### 2.2.2 满二叉树

**在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所以叶子都在同一层中**



#### 2.2.3 完全二叉树

**对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i（1 < i < n）的结点与同样深度的满二又树中编号为i的结点在二又树中位置完全相同，则这棵二叉树称为完全二叉树**

- 叶子结点只能出现在最下两层。
- 最下层的叶子一定集中在左部连续位置。
- 倒数二层，若有叶子结点，一定都在右部连续位置。
- 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
- 同样结点数的二又树，完全二叉树的深度最小。



### 2.3 二叉树的性质

**性质1:**
$$
在二叉树的 i 层上最多结点数 = 2^{i-1}(i \geq 1)
$$
**性质2：**
$$
深度为k的二叉树至多有 2^K-1(K \geq 1) 个结点
$$
**性质3：**
$$
对任何一棵二又树 T，如果其终端结点数(叶子数)为 n_0，度为 2 的结点数为 n_2，则 n_0 = n_2 + 1 
$$
**性质4：**
$$
具有 n 个结点的完全二叉树的深度为 [log_2n] + 1 ([x] 表示不大于 x 的最大值)
$$
**性质5：**
$$
如果对一颗有 n 个结点的完全二叉树（其深度为[log_2n]+1)的结点按层序编号\\
（从第1层到低[log2n]+1层，每层从左到右），对任一结点 i（1 \leq i \leq n)有：\\
1.如果 i=1,则结点 i 是二叉树的根，五双亲；如果 i > 1,则其双亲是结点[i/2] \\
2.如果 2i>n ,则结点 i 无左孩子（结点i为叶子结点）；否则其左孩子是结点 2i； \\
3.如果 2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+12 \\
$$


### 2.4 二叉树的存储结构

#### 2.4.1 顺序存储结构

#### 2.4.2 链表存储结构



### 2.5 二叉树的遍历(traversing binary tree)

****

**二叉树的遍历是指从根结点出发，按照某种*次序*依次*访问*二叉树中所有结点，使得每个结点被访问一次且仅被访问一次**

![5.tree-a-tree](https://raw.githubusercontent.com/XuZhuohao/picture/master/Algorithm/data-struct/5.tree-a-tree.png)

#### 2.5.1 前序遍历

**规则是若二叉树为空，则空操作返回，否则先返回根结点，然后前序遍历左子树，再遍历右子树。上图的前序遍历顺序为：ABDGHCEIF**



#### 2.5.2 中序遍历

**规则是若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后访问根结点，最后中序遍历右子树。上图的中序遍历顺序为：GDHBAEICF**



#### 2.5.3 后序遍历

**规则是若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历左右子树，最后访问根节点。上图的后续遍历顺序为：GHDBIEFCA**



#### 2.5.4 层序遍历

**规则是若二叉树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，冲上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。上图的层序遍历顺序为：ABCDEFGHI**



#### 2.5.5 推导树的结构

- 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
- 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。



### 2.6 二叉树的建立

与二叉树的遍历一致



### 2.7 线索二叉树

**这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二又树就称为线索二又树（Threaded Binary Tree）。**



使为空的左孩子指针指向该结点的前驱，为空的右孩子指针指向该结点的后继；并设置标记，ltag 和 rtag ，为 0时指向孩子，为 1 时指向前驱、后继。（主要是为了充分利用空指针域）



## 3. 树、森林、二叉树的转换



### 3.1 树转二叉树

**步骤：**

1. 加线。在所有兄弟结点之间加一条连线。
2. 去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
3. 层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。



**树：**

```mermaid
graph TB;
 1((A)) --- 2((B))
 1((A)) --- 3((C))
 1((A)) --- 4((D))
 2((B)) --- 5((E))
 2((B)) --- 6((F))
 2((B)) --- 7((G))
 3((C)) --- 8((H))
 4((D)) --- 9((I))
 4((D)) --- 10((J))
```

**变化过程-连线：**

```mermaid
graph TB;
 1((A)) --- 2((B))
 1((A)) --- 3((C))
 1((A)) --- 4((D))
 2((B)) --- 5((E))
 2((B)) --- 6((F))
 2((B)) --- 7((G))
 3((C)) --- 8((H))
 4((D)) --- 9((I))
 4((D)) --- 10((J))
 
 2 -.- 3
 3 -.- 4
 
 5 -.- 6
 6 -.- 7
 
 9 -.- 10
```

**变化过程-删除连线：**

```mermaid
graph TB;
 1((A)) --- 2((B))
 2((B)) --- 5((E))
 3((C)) --- 8((H))
 4((D)) --- 9((I))
 
 2 -.- 3
 3 -.- 4
 
 5 -.- 6((F))
 6 -.- 7((G))
 
 9((I)) -.- 10((J))
```

### 3.2 森林转二叉树

**步骤：**

1. 把每个树转换为二又树。
2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二又树连接起来后就得到了由森林转换来的二叉树。



### 3.3 二叉树转树

**步骤：**

1. 加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点……哈，反正就是左孩子的 n 个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。
2. 去线。删除原二叉树中所有结点与其右孩子结点的连线。
3. 层次调整。使之结构层次分明。



### 3.4 二叉树转森林

**判断一棵二又树能够转换成一棵树还是森林**，标准很简单，那就是只要看这棵二又树的根结点有没有右孩子，有就是森林，没有就是一棵树。那么如果是转换成森林，**步骤**如下：

1. 从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树。
2. 再将每棵分离后的二又树转换为树即可。

数据结构：树(tree)

**串（string）是由零个或多个字符组成的有限序列，又名叫字符串。**

## 1. 定义

- **串（string）是由零个或多个字符组成的有限序列，又名叫字符串。**
- 0 个字符的串称之为空串（null String）
- 概念
 - 空格串：只包含空格，有内容有长度，不同于空串
 - 子串与主串：串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。
 - 子串在主串中的位置就是子串的第一个字符在主串中的序号。





## 2. 串的抽象数据类型

```c
ADT串(string)
	Data串中元素仅由一个字符组成,相邻元素具有前驱和后继关系。
Operation StrAssign(T,*chars):生成一个其值等于字符串常量chars的串T。
 StrCopy(T,S):串S存在,由率s复制得串T。
 ClearString(s):串S存在,将串清空。
 StringEmpty(s):若率s为空,返回true,否则返回false。
 StrLength(s):返回串S的元素个数,即串的长度。
 StrCompare(s,T):若s>T,返回值>0,若S=T,返回0,若S<T,返回值<0。
 Concat(T,S1,S2):用T返回由S1和S2联接而成的新串。
 subString(sub,S,pos,1en):串S存在,1≤pos≤StrLength(s),且0≤len≤StrLength(s)-pos+1,用Sub返回串S的第pos个字符起长度为1en的子串。
 Index(s,T,pos):串S和T存在,T是非空率,1≤pos≤StrLength(s)。
 若主串S中存在和串T值相同的子事,则返回它在主串S中第pos个字符之后第一次出现的位置,否则返回0。
 Replace(S,T,V):率S、T和V存在,T是非空率。用V替换主串S中出现的所有与T相等的不重叠的子串。
 StrInsert(s,pos,T):串S和T存在,1≤pos≤StrLength(s)+1。
 在串S的第pos个字符之前插入串T。
 StrDelete(s,pos,1en):率s存在,1≤possStrLength(s)-1en+1。从串S中删除第pos个字符起长度为1en的子串。
endADT
```



## 3. 串的存储结构

### 3.1 顺序存储（定长数组存储）

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

- 字符串长度
 - 有的语言会在下标为0的地方保存串的长度
 - 有的语言会在最后一个下标的地方保存串的长度
 - 有的语音不保存串的长度，而在结尾添加一个"\0" 来表示结束，需要获取长度时去遍历计算
- 对于定长的数组存储的弊端
 - 定长的数组，至多只能输入固定长度的字符

### 3.2 ~~链式存储~~

链式存储的话，每个节点要放多少个字符是一个问题。而且无论是从性能还是操作的方便性都不如顺序存储= =



## 4. 朴素的模式匹配算法



## 5. KMP 模式匹配算法

**初略讲解，会在算法动态规划中详讲**

### 5.1 KMP 模式匹配算法原理

#### 5.1.1 例一

主串 S="abcdefgab"

子串 T="abcdex"

**朴素的模式**

![4.string_simple_matching](https://raw.githubusercontent.com/XuZhuohao/picture/master/Algorithm/data-struct/4.string_simple_matching.png)



KMP 模式匹配算法与朴素的模式匹配算法不一样在于图的 ② 到 ⑤，对于匹配模式来讲依次遍历是必须的，而 KMP 算法，在判断到子串 T 的首字母 a， 与后面 bcdex 都不一样（**这是前提**），而在第一次匹配时 bcde 都匹配上了，只有 x 没有匹配到，那下一次，会从 ⑥ 处开始匹配

#### 5.1.2 例二

主串 S="abcabcabc"

子串 T="abcabx"

![4.string_simple_matching02](https://raw.githubusercontent.com/XuZhuohao/picture/master/Algorithm/data-struct/4.string_simple_matching02.png)



- 前五个字符完全相等，第六个字符不等，如①所示
- T 的首字母 "a" 与 第二，第三字符均不等，所以省略 ②③
- 因为 T 的首位与 T 的第四位相等，第二位与第五位相等。而在 ① 时，T 的第四，第五位均与主串 S 中的相应位置比较过了，所以 T 的首位和第二位字符与 S 的第四，第五位肯定是匹配的，不需要再匹配，所以第 ④⑤步骤是可以省略的



### 5.2 KMP



#### 5.2.1 匹配值表(next[])

**前缀**：从 0 位，依次截取 1 到(len - 1)长度字符串的集合
**后缀**：从 len - 1 位反序，依次截取 1 到(len - 1)长度字符串的集合

以子串 T="ABABABCA" 为例

| 字符串 | 前缀集合 | 后缀集合 | 前缀后缀交集 |
| :--------- | :----------------------------------- | :----------------------------------- | :----------- |
| "A" | [] | [] | [] |
| "AB" | [A] | [B] | [] |
| "ABA" | [A,AB] | [A,BA] | [A] |
| "ABAB" | [A,AB,ABA] | [B,AB,BAB] | [AB] |
| "ABABA" | [A,AB,ABA,ABAB] | [A,BA,ABA,BABA] | [A,ABA] |
| "ABABAB" | [A,AB,ABA,ABAB,ABABA] | [B,AB,BAB,ABAB,BABAB] | [AB,ABAB] |
| "ABABABC" | [A,AB,ABA,ABAB,ABABA,ABABAB] | [C,BC,ABC,BABC,ABABC,BABAC] | [] |
| "ABABABCA" | [A,AB,ABA,ABAB,ABABA,ABABAB,ABABABC] | [A,CA,BCA,ABCA,BABCA,ABABCA,BABABCA] | [A] |



**“匹配值”是指前缀和后缀集合，最长共有元素的长度，即交集中最长元素的长度**

所以**匹配值表**为

| -- | -- | -- | -- | -- | -- | -- | -- | -- |
| ----- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| char | A | B | A | B | A | B | C | A |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| value | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |



#### 5.2.2 匹配值表使用

**移动位数 = 已匹配字符长度 - 对应位的匹配值**

举例：

主串 S="BACBABABAABCBABABABCA"

子串 T="ABABABCA"

设主串匹配游标为 i, 子串游标为 j

```
第1次匹配成功：

BACBABABAABCBABABABCA
 |
 ABABABCA
此时 i = 1, j = 0;已匹配字符长度为=1
移动长度为 1 - 0 = 1

----------------------------------------
第2次匹配成功：
BACBABABAABCBABABABCA
 |||||
 ABABABCA
此时 i = 8, j = 4;已匹配字符长度为=5
移动长度为：5 - next[j=4] = 5-3 = 2;

BACBABABAABCBABABABCA
 XX|||
 ABABABCA
此时 i = 8, j = 2;已匹配字符长度为=3
移动长度为：3 - next[j=2] = 3-1 = 2;

BACBABABAABCBABABABCA
 XXxx|
 ABABABCA
此时 i = 8, j = 0;已匹配字符长度为=1
移动长度为：1 - next[j=0] = 1-0 = 1; 
 
```

数据结构：串(string)

## 1. 栈（stack）

**线性表的特例**

### 1.1 定义

**栈（stack）是限定仅在表尾进行插入和删除操作的线性表**

**Last in First Out**

- 栈顶（top）：允许插入和删除的一端
- 栈底（bottom）：不允许插入和删除的一端
- LIFO结构：栈又称为后进先出（Last In First Out）的线性表
- 栈的插入操作，叫进栈，也称压栈、入栈
- 栈的删除操作，叫出栈，也称弹栈





### 1.2 栈的抽象数据类型

```ADT
ADT 栈（stack）
Data
 同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系
Operation
	InitStack(*S): 初始化操作,建立一个空栈S。
 Destroystack(*s): 若栈存在,则销毁它。
 Clearstack(*s): 将栈清空。
 StackEmpty(s): 若为空,返回true,否则返回false。
 GetTop(s,*e): 若楼存在且非空,用e返回s的栈顶元素。
 Push(*s,e): 若栈S存在,插入新元素e到横S中并成为栈顶元素。
 Pop(*S,*e): 删除栈S中栈顶元素,并用e返回其值。
 StackLength(s): 返回栈S的元素个数。
endADT
```



### 1.3 顺序存储结构



####　1.3.1 栈的顺序存储结构

- 栈的顺序存储结构是线性表顺序存储的简单结构：顺序栈

- 使用数组来表达时，栈底在下标为0的位置；
 - StackSize 为数组长度，标识栈的长度
 - top 为栈顶游标，小于 StackSize
 - 空栈时 top=-1



#### 1.3.2 栈的顺序存储结构 - 进栈操作



```c
/* 插入元素 e 为新的栈顶元素 */
Status Push(SqStack *S, SElemType e)
{
 if(s -> top == MAXSIZE - 1) /* 栈满 */
 {
 return ERROR;
 }
 S -> top++;					/* 栈顶指针增加一 */
 S -> data[S -> top] = e; 	/* 将新插入元素赋值给栈顶空间 */
 return OK;
}
```



#### 1.3.3 栈的顺序存储结构 - 出栈操作

```c
/* 若栈不空，则删除 S 的栈顶元素，用 e 返回其值 */
Status Pop(SqStack *S, SElemType e)
{
 if(s -> top == - 1) 
 {
 return ERROR;
 }
 *e = S -> data[S -> top];	/* 将要删除的栈顶元素赋值给 e */
 S -> top--; 				/* 栈顶指针减一 */
 return OK;
}
```





#### 1.3.4 两栈共享空间

- 用同一个数据构建两个栈，共享空间
- 一个栈用下标为 0 做栈底， 另一个栈用下标为 MAXSIZE - 1 作为栈底
- 两个栈的 top 相遇则为栈满





### 1.4 链式存储结构

- 栈的链式存储：链栈
- 栈顶放在链的头部（只有栈顶进行数据操作）
- 在内存足够的情况下不存在栈满的情况
- 空栈即链的头部指针指向空



#### 1.4.1 栈的链式存储结构

```c
typedef struct StackNode
{
 SElemType data;
 struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack
{
 LinkStackPtr top;
 int count;
}LinkStack;
```



#### 1.4.2 栈的链式存储结构 - 进栈操作

```c
/* 插入新元素 e */
Status Push(LinkStack *S, SElemType e)
{
 LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
 s -> data = e;
 s -> next = S -> top; /* 把当前栈顶元素赋值给新结点的直接后继 */
 S -> top =s;		 /* 将新的结点 s 赋值给栈顶指针 */
 S -> count++;
 return OK;
}
```





#### 1.4.3 栈的链式存储结构 - 出栈操作

```c
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回 ERROR */
Status Pop(LinkStack *S, SElemType e)
{
 LinkStackPtr p;
 if(StackEmpty(*S))
 {
 return ERROR;
 }
 *e = S -> top -> data;
 p = S -> top;				/* 将栈顶结点赋值给 p */
 S -> top = S -> top -> next;/* 使得栈顶指针下移一位，指向后一结点*/
 free(p);					/* 释放结点 p */
 S -> count--;
 return OK;
}
```



### 1.5 栈的作用

#### 1.5.1 递归

##### 1.5.1.1 斐波那契数列（Fibonacci）

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。公式如下：
$$
F(n) = \begin{cases} 
0, 当 n=0 \\
1, 当 n=1 \\
F(n-1) + F(n-2), 当 n>1
\end{cases}
$$


##### 1.5.1.2 递归的定义

我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。



#### 1.5.2 四则运算表达式求值

##### 1.5.2.1 中缀表达式转后缀表达式

- 我们常见的标准四则运算表达式，就是中缀表达式；如： 9+(3-1)*3+10/2;

- 后缀表达式是后缀计算的关键;
- 规则：
 - 从左到右遍历中缀表达式的数字和符号
 - 遇到数字就输出，成为后缀表达式到的一部分
 - 遇到符号，先和栈顶符号对比优先级
 - 如果是右括号或者优先级低于栈顶符号，则栈内元素依次出栈并输出，并吧当前符号进栈
 - 如果是左括号或者优先级高于栈顶符号，这继续入栈

**举例：9+(3-1)*3+10/2**

-> 输出：9 3 1 - 3 * + 10 2 / +

![rpn](https://raw.githubusercontent.com/XuZhuohao/picture/master/Algorithm/data-struct/3.stack-toRPN.png)





##### 1.5.2.2 后缀（逆波兰）表示法定义（Reverse Polish Notation,RPN）

使用后缀表达式计算公式结果

- 规则：
 - 从左到右遍历数字和符号
 - 遇到数字进栈
 - 遇到符号则将处于栈顶的两个数字出栈，计算结果，结果进栈

**举例：9 3 1 - 3 * + 10 2 / +**



![rpn result](https://raw.githubusercontent.com/XuZhuohao/picture/master/Algorithm/data-struct/3.2.stack-RPNResult.png)



## 2. 队列（queue）

**队列是只准许在一端进行插入操作，而在另一端进行删除操作的线性表**

First In First Out

- 允许插入的一端称为队尾
- 允许删除的一端称为队头

### 2.1 队列的抽象数据类型

```text
ADT 队列（Queue）
Data
	同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
	
Operation 
 InitQueue(*Q):初始化操作,建立一个空队列Q。
 DestroyQueue(*Q):若队列Q存在,则销毁它。
 ClearQueue(*Q):将队列Q清空。
 QueueEmpty(Q):若队列Q为空,返回true,否则返回false。
 GetHead(Q,*e):若队列Q存在且非空,用e返回队列Q的队头元素。
 EnQueue(*Q,e):若队列Q存在,插入新元素e到队列Q中并成为队尾元素。
 DeQueue(*Q,*e):删除队列Q中队头元素,并用e返回其值。
 QueueLength(Q):返回队列Q的元素个数
endADT
```



### 2.2 循环队列

- 我们把队列的这种头尾相接的顺序存储结构称为循环队列。

#### 2.2.1 队列顺序存储的不足

##### 2.2.1.1 第一种存储实现

使用数组来做队列存储，用下标 0 一端做队头，查入数据是直接往数组添加数据，所以时间复杂度是 O(1)，队头删除数据时，所有数据往前移动，时间复杂度为O(n);



##### 2.2.1.2 第二种存储实现

使用数组来做队列存储，front 指针指向队头下标， rear 指针指向队尾的下一个下标，当 front == rear 时为空队列，添加一个元素，rear 加 1，删除一个元素 front 加 1。这样删除和插入时间复杂度都为O(n)。

这种实现存在一个**假溢出**问题，当数组数据不满，但是队列不停插入和删除，导致 rear 超过了数组的 size ( front ！= 0)。



#### 2.2.2 循环队列

##### 2.2.2.1 定义

解决假溢出的问题就是，当后面满了重头开始，我们把队列的这种头尾相接的顺序存储结构称为循环队列。

- 循环队列出现一个问题就是 front == rear 是不知道是队满还是队空，解决这个问题有以下方法：
 - 设置一个 flag， 当 front == rear 且 flag == 0 时，为队空，当 front == rear 且 flag == 1 时，为队满
 - 队满预留一个单元，即 front == rear 为队空， **(rear+1)%QueueSize == front** 为队满
- 通用长度计算公式为 **（rear - front + QueueSize ) % QueueSize** 



### 2.3 队列的链式存储结构

其实就是线性表的单链表，只不过只准许尾进头出。

数据结构：栈(stack)与队列(queue)

**零个或多个数据元素的有限序列。**



## 1. 定义

### 1.1 定义

- 序列，即元素之间是有序的
- 第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱，有且只有一个后继
- 有限的



### 1.2 数学定义

$$
若将线性表记为 (a_1, ... , a_{i-1}, a_i, a_{i+1}, ..., a_n) \\
则表中 a_{i-1} 领先于 a_i, a_i 领先于 a_{i+1}, \\
称 a_{i-1} 为 a_i 的直接前驱元素， \\
a_{i+1} 为 a_i 的直接后继元素。 \\
线性表元素的个数 n(n>0) 定义为线性表的长度，当 n=0 时，称为空表。
$$



## 2. 线性表的抽象数据类型

```ADT
ADT 线性表（List）
Data
 若将线性表记为 （a1, a2, ... , an）,每个元素的类型均为 DataType 。其中，除第一个元素a1外，每个元素都有且只有一个直接前驱元素，除了最后一个元素 an 外，每一个元素都有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
	InitList(*L): 初始化操作,建立一个空的线性表L。
	ListEmpty(L): 若线性表为空,返回true,否则返回false。
	ClearList(*L): 将线性表清空。
	GetElem(L,i,*e): 将线性表工中的第i个位置元素值返回给e。
	LocateElem(L,e): 在线性表工中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功；否						 则,返回0表示失败。
	ListInsert(*L,i,e): 在线性表工中的第i个位置插入新元素e。
	ListDelete(*L,i,*e): 删除线性表工中第i个位置元素,并用e返回其值。
	ListLength(L): 返回线性表工的元素个数。
endADT
```



## 3. 线性表的顺序存取

### 3.1 顺序存储结构定义与存储方法

- **线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。**

- **存储方法：**
 - 初始化大小，占用固定的连续空间
 - 使用高级语言中（如C， java）使用一维数组表示
- 线性表长度和数据长度
 - 数据长度：指存储线性表的空间大小，初始化大小，固定大小（高级语言中可动态分配），
 - 线性表长度：指线性表的数据长度，随着数据的插入和删除变化，必须小于或等于数据长度



### 3.2 寻址计算方式

假设一个数据元素占用的是 c 个存储单元，那么线性表中第 i+1 个双据元素的存储位置和第 i 个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。

$$
由： LOC(a_{i+1}) = LOC(a_i)+1 \\
可得： LOC(a_i)=LOC(a_1)+(i-1)*c
$$


### 3.3 获取，插入和删除

#### 3.3.1 获取

直接通过寻址获取，时间复杂度为 O(1)



#### 3.3.2 插入和删除

变更相应节点，需要改节点以后所有节点进行变更（前进或者后退一步），时间复杂度为O(n)



### 3.4 顺序存取得优缺点

- 优点
 - 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
 - 可以快速地存取表中任一位置的元素
- 缺点
 - 插入和删除操作需要移动大量元素
 - 当线性表长度变化较大时，难以确定存储空间的容量
 - 造成存储空间的“碎片”



## 4. 线性表的链式存取

### 4.1 结构定义

- 每一个元素称之为节点（Node）
- 每一个节点由数据域和指针域组成
 - 数据域：存储数据元素信息
 - 指针域：存储直接后继位置的域
- n 个节点链节成一个链表，即称为链表
- 因为每个节点只有一个指针域，所以称之为单链表



### 4.2 头指针和头结点

- 头指针：
 - 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
 - 头指针具有标识作用，所以常用头指针冠以链表的名字
 - 无论链表是否为空，头指针均不为空。头指针是链表的必要元素
- 头节点：
 - 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
 - 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
 - 头结点不一定是链表必须要素



### 4.3 单链表的读取

**获得链表第i个数据的算法思路**：

1. 声明一个结点p指向链表第一个结点，初始化 j 从1开始；
2. 当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1；
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在；
4. 否则查找成功，返回结点 p 的数据。

最坏的情况**时间复杂度为O(n)**



### 4.4 单链表的插入和删除

- 单链表第 i 个数据插入结点的算法思路：：
 1. 声明一结点 p 指向链表第一个结点，初始化j从1开始；
 2. 当j < i时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加1；
 3. 若到链表末尾 p 为空，则说明第 i 个元素不存在；
 4. 否则查找成功，在系统中生成一个空结点s；
 5. 将数据元素e 赋值给 s->data；
 6. 单链表的插入标准语句 s->next=p->next; p->next=s；
- 单链表第i个数据删除结点的算法思路：
 1. 声明一结点p指向链表第一个结点，初始化 j 从 1 开始；
 2. 当 j next 赋值给 q；
 5. 单链表的删除标准语句p->next=q->next；
 6. 将q结点中的数据赋值给e，作为返回；
- **单链表插入和删除一个节点的时间复杂度也是 O(n)**
- 对于单个节点的操作来讲，单链表和顺序链表的时间复杂度并没有区别，但是如果**一次性插入或者删除多个元素，单链表需要的时间更低**



## 5. 顺序存取和链式存取得区别

- 存储分配方式
 - 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
 - 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
- 时间性能
 - 查找
 - 顺序存储结构O(1)
 - 单链表O(n)
 - 插入和删除
 - 顺序存储结构需要平均移动表长一半的元素，时间为 O(n)
 - 单链表在线出某位置的指针后，插入和删除时间仅为 O(1)
- 空间性能
 - 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
 - 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制



## 6 其他链表结构

### 6.1 静态链表

**静态链表是为了没有指针的高级编程语言实现单链表能力的方法**

- 思路：
 - 使用数据保存节点，节点需要包含数据和一个指向下个节点的数组下标（指针域）。



### 6.2 循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称**循环链表（circular linked list）**。





### 6.3 双向链表

双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针。