Redis为什么这么快？

本文 GitHub https://github.com/JavaFamily 已收录，有一线大厂面试完整考点、资料以及我的系列文章。

前言

说起当前主流NoSql数据库非 Redis 莫属。因为它读写速度极快，一般用于缓存热点数据加快查询速度，大家在工作里面也肯定和 Redis 打过交道，但是对于Redis 为什么快，除了对八股文的背诵，好像都还没特别深入的了解。

今天我们一起深入的了解下redis吧：

高效的数据结构

Redis 的底层数据结构一共有6种，分别是，简单动态字符串，双向链表，压缩列表，哈希表，跳表和整数数组，它们和数据类型的对应关系如下图所示：

本文暂时按下不表，后续会针对以上所有数据结构进行源码级深入分析

单线程vs多线程

在学习计算机操作系统时一定遇到过这个问题： 多线程一定比单线程快吗？ 相信各位看官们一定不会像上面的傻哪吒一样落入敖丙的圈套中。

多线程有时候确实比单线程快，但也有很多时候没有单线程那么快。首先用一张3岁小孩都能看懂的图解释并发与并行的区别：

• 并发(concurrency)：指在同一时刻只能有一条指令执行，但多个进程指令被快速的轮换执行，使得在宏观上具有多个进程同时执行的效果，但在微观上并不是同时执行的，只是把时间分成若干段，使多个进程快速交替的执行。
• 并行(parallel)：指在同一时刻，有多条指令在多个处理器上同时执行。所以无论从微观还是从宏观来看，二者都是一起执行的。

不难发现并发在同一时刻只有一条指令执行，只不过进程(线程)在CPU中快速切换，速度极快，给人看起来就是“同时运行”的印象，实际上同一时刻只有一条指令进行。但实际上如果我们在一个应用程序中使用了多线程，线程之间的轮换以及上下文切换是需要花费很多时间的。

Talk is cheap,Show me the code

如下代码演示了串行和并发执行并累加操作的时间：

public class ConcurrencyTest {
    private static final long count = 1000000000;

    public static void main(String[] args) {
        try {
            concurrency();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        serial();
    }

    private static void concurrency() throws InterruptedException {
        long start = System.currentTimeMillis();
        Thread thread = new Thread(new Runnable() {

            @Override
            public void run() {
                 int a = 0;
                 for (long i = 0; i < count; i++)
                 {
                     a += 5;
                 }
            }
        });
        thread.start();
        int b = 0;
        for (long i = 0; i < count; i++) {
            b--;
        }
        thread.join();
        long time = System.currentTimeMillis() - start;
        System.out.println("concurrency : " + time + "ms,b=" + b);
    }

    private static void serial() {
        long start = System.currentTimeMillis();
        int a = 0;
        for (long i = 0; i < count; i++)
        {
            a += 5;
        }
        int b = 0;
        for (long i = 0; i < count; i++) {
            b--;
        }
        long time = System.currentTimeMillis() - start;
        System.out.println("serial : " + time + "ms,b=" + b);
    }

}

执行时间如下表所示，不难发现，当并发执行累加操作不超过百万次时，速度会比串行执行累加操作要慢。

循环次数	串行执行耗时/ms	并发执行耗时	并发比串行快多少
1亿	130	77	约1倍
1千万	18	9	约1倍
1百万	5	5	相差无几
10万	4	3	相差无几
1万	0	1	慢

由于线程有创建和上下文切换的开销，导致并发执行的速度会比串行慢的情况出现。

上下文切换

多个线程可以执行在单核或多核CPU上，单核CPU也支持多线程执行代码，CPU通过给每个线程分配CPU时间片(机会)来实现这个机制。CPU为了执行多个线程，就需要不停的切换执行的线程，这样才能保证所有的线程在一段时间内都有被执行的机会。

此时，CPU分配给每个线程的执行时间段，称作它的时间片。CPU时间片一般为几十毫秒。CPU通过时间片分配算法来循环执行任务，当前任务执行一个时间片后切换到下一个任务。

但是，在切换前会保存上一个任务的状态，以便下次切换回这个任务时，可以再加载这个任务的状态。所以任务从保存到再加载的过程就是一次上下文切换。

根据多线程的运行状态来说明：多线程环境中，当一个线程的状态由Runnable转换为非Runnable(Blocked、Waiting、Timed_Waiting)时，相应线程的上下文信息(包括CPU的寄存器和程序计数器在某一时间点的内容等)需要被保存，以便相应线程稍后再次进入Runnable状态时能够在之前的执行进度的基础上继续前进。而一个线程从非Runnable状态进入Runnable状态可能涉及恢复之前保存的上下文信息。这个对线程的上下文进行保存和恢复的过程就被称为上下文切换。

基于内存

以MySQL为例，MySQL的数据和索引都是持久化保存在磁盘上的，因此当我们使用SQL语句执行一条查询命令时，如果目标数据库的索引还没被加载到内存中，那么首先要先把索引加载到内存，再通过若干寻址定位和磁盘I/O，把数据对应的磁盘块加载到内存中，最后再读取数据。

如果是机械硬盘，那么首先需要找到数据所在的位置，即需要读取的磁盘地址。可以看看这张示意图：

读取硬盘上的数据，第一步就是找到所需的磁道，磁道就是以中间轴为圆心的圆环，首先我们需要找到所需要对准的磁道，并将磁头移动到对应的磁道上，这个过程叫做寻道。

然后，我们需要等到磁盘转动，让磁头指向我们需要读取的数据开始的位置，这里耗费的时间称为旋转延迟，平时我们说的硬盘转速快慢，主要影响的就是耗费在这里的时间，而且这个转动的方向是单向的，如果错过了数据的开头位置，就必须等到盘片旋转到下一圈的时候才能开始读。

最后，磁头开始读取记录着磁盘上的数据，这个原理其实与光盘的读取原理类似，由于磁道上有一层磁性介质，当磁头扫过特定的位置，磁头感应不同位置的磁性状态就可以将磁信号转换为电信号。

可以看到，无论是磁头的移动还是磁盘的转动，本质上其实都是机械运动，这也是为什么这种硬盘被称为机械硬盘，而机械运动的效率就是磁盘读写的瓶颈。

扯得有点远了，我们说回redis，如果像Redis这样把数据存在内存中，读写都直接对数据库进行操作，天然地就比硬盘数据库少了到磁盘读取数据的这一步，而这一步恰恰是计算机处理I/O的瓶颈所在。

在内存中读取数据，本质上是电信号的传递，比机械运动传递信号要快得多。

因此，可以负责任地说，Redis这么快当然跟它基于内存运行有着很大的关系。但是，这还远远不是全部的原因。

Redis FAQ

面对单线程的 Redis 你也许又会有疑问：敖丙，我的多核CPU发挥不了作用了呀！别急，Redis 针对这个问题专门进行了解答。

CPU成为Redis性能瓶颈的情况并不常见，因为Redis通常会受到内存或网络的限制。例如，在 Linux 系统上使用流水线 Redis 每秒甚至可以提供 100 万个请求，所以如果你的应用程序主要使用O(N)或O(log(N))命令，它几乎不会占用太多的CPU。

然而，为了最大化CPU利用率，你可以在同一个节点中启动多个Redis实例，并将它们视为不同的Redis服务。在某些情况下，一个单独的节点可能是不够的，所以如果你想使用多个cpu，你可以开始考虑一些更早的分片方法。

你可以在Partitioning页面中找到更多关于使用多个Redis实例的信息。

然而，在Redis 4.0中，我们开始让Redis更加线程化。目前这仅限于在后台删除对象，以及阻塞通过Redis模块实现的命令。对于未来的版本，我们的计划是让Redis变得越来越多线程。

注意：我们一直说的 Redis 单线程，只是在处理我们的网络请求的时候只有一个线程来处理，一个正式的Redis Server运行的时候肯定是不止一个线程的！

例如Redis进行持久化的时候会 fork了一个子进程 执行持久化操作

四种IO模型

当一个网络IO发生(假设是read)时，它会涉及两个系统对象，一个是调用这个IO的进程，另一个是系统内核。

当一个read操作发生时，它会经历两个阶段：

​ ①等待数据准备；

​ ②将数据从内核拷贝到进程中。

为了解决网络IO中的问题，提出了4中网络IO模型：

• 阻塞IO模型
• 非阻塞IO模型
• 多路复用IO模型
• 异步IO模型

阻塞和非阻塞的概念描述的是用户线程调用内核IO操作的方式：阻塞时指IO操作需要彻底完成后才返回到用户空间；而非阻塞是指IO操作被调用后立即返回给用户一个状态值，不需要等到IO操作彻底完成。

阻塞IO模型

在Linux中，默认情况下所有socket都是阻塞的，一个典型的读操作如下图所示：

当应用进程调用了recvfrom这个系统调用后，系统内核就开始了IO的第一个阶段：准备数据。

对于网络IO来说，很多时候数据在一开始还没到达时(比如还没有收到一个完整的TCP包)，系统内核就要等待足够的数据到来。而在用户进程这边，整个进程会被阻塞。

当系统内核一直等到数据准备好了，它就会将数据从系统内核中拷贝到用户内存中，然后系统内核返回结果，用户进程才解除阻塞的状态，重新运行起来。所以，阻塞IO模型的特点就是在IO执行的两个阶段(等待数据和拷贝数据)都被阻塞了。

非阻塞IO模型

在Linux中，可以通过设置socket使IO变为非阻塞状态。当对一个非阻塞的socket执行read操作时，读操作流程如下图所示：

从图中可以看出，当用户进程发出 read 操作时，如果内核中的数据还没有准备好，那么它不会阻塞用户进程，而是立刻返回一个错误。

从用户进程角度讲，它发起一个read操作后，并不需要等待，而是马上就得到了一个结果。当用户进程判断结果是一个错误时，它就知道数据还没有准备好，于是它可以再次发送read操作。

一旦内核中的数据准备好了，并且又再次收到了用户进程的系统调用，那么它马上就将数据复制到了用户内存中，然后返回正确的返回值。

所以，在非阻塞式IO中，用户进程其实需要不断地主动询问kernel数据是否准备好。非阻塞的接口相比阻塞型接口的显著差异在于被调用之后立即返回。

多路复用IO模型

多路IO复用，有时也称为事件驱动IO（Reactor设计模式）。它的基本原理就是有个函数会不断地轮询所负责的所有socket，当某个socket有数据到达了，就通知用户进程，多路IO复用模型的流程如图所示：

当用户进程调用了select，那么整个进程会被阻塞，而同时，内核会"监视"所有select负责的socket，当任何一个socket中的数据准备好了，select就会返回。这个时候用户进程再调用read操作，将数据从内核拷贝到用户进程。

这个模型和阻塞IO的模型其实并没有太大的不同，事实上还更差一些。因为这里需要使用两个系统调用(select和recvfrom)，而阻塞IO只调用了一个系统调用(recvfrom)。但是，用select的优势在于它可以同时处理多个连接。所以，如果系统的连接数不是很高的话，使用select/epoll的web server不一定比使用多线程的阻塞IO的web server性能更好，可能延迟还更大；select/epoll的优势并不是对单个连接能处理得更快，而是在于能处理更多的连接。

如果select()发现某句柄捕捉到了"可读事件"，服务器程序应及时做recv()操作，并根据接收到的数据准备好待发送数据，并将对应的句柄值加入writefds，准备下一次的"可写事件"的select()检测。同样，如果select()发现某句柄捕捉到"可写事件"，则程序应及时做send()操作，并准备好下一次的"可读事件"检测准备。

如下图展示了基于事件驱动的工作模型，当不同的事件产生时handler将感应到并执行相应的事件，像一个多路开关似的。

IO多路复用是最常使用的IO模型，但是其异步程度还不够“彻底”，因为它使用了会阻塞线程的select系统调用。因此IO多路复用只能称为异步阻塞IO，而非真正的异步IO。

异步IO模型

“真正”的异步IO需要操作系统更强的支持。如下展示了异步 IO 模型的运行流程(Proactor设计模式)：

用户进程发起read操作之后，立刻就可以开始去做其他的事；而另一方面，从内核的角度，当它收到一个异步的read请求操作之后，首先会立刻返回，所以不会对用户进程产生任何阻塞。

然后，内核会等待数据准备完成，然后将数据拷贝到用户内存中，当这一切都完成之后，内核会给用户进程发送一个信号，返回read操作已完成的信息。

IO模型总结

调用阻塞IO会一直阻塞住对应的进程直到操作完成，而非阻塞IO在内核还在准备数据的情况下会立刻返回。

两者的区别就在于同步IO进行IO操作时会阻塞进程。按照这个定义，之前所述的阻塞IO、非阻塞IO及多路IO复用都属于同步IO。实际上，真实的IO操作，就是例子中的recvfrom这个系统调用。

非阻塞IO在执行recvfrom这个系统调用的时候，如果内核的数据没有准备好，这时候不会阻塞进程。但是当内核中数据准备好时，recvfrom会将数据从内核拷贝到用户内存中，这个时候进程则被阻塞。

而异步IO则不一样，当进程发起IO操作之后，就直接返回，直到内核发送一个信号，告诉进程IO已完成，则在这整个过程中，进程完全没有被阻塞。

各个IO模型的比较如下图所示：

Redis中的应用

Redis服务器是一个事件驱动程序，服务器需要处理以下两类事件：

• 文件事件：Redis服务端通过套接字与客户端(或其他Redis服务器)进行连接，而文件事件就是服务器对套接字操作的抽象。服务器与客户端(或者其他服务器)的通信会产生相应的文件事件，而服务器则通过监听并处理这些事件来完成一系列网络通信操作。
• 时间事件：Redis服务器中的一些操作(如serverCron)函数需要在给定的时间点执行，而时间事件就是服务器对这类定时操作的抽象。

I/O多路复用程序

Redis的 I/O 多路复用程序的所有功能都是通过包装常见的select、epoll、evport、kqueue这些多路复用函数库来实现的。

因为Redis 为每个 I/O 多路复用函数库都实现了相同的API，所以I/O多路复用程序的底层实现是可以互换的。

Redis 在 I/O 多路复用程序的实现源码中用 #include 宏定义了相应的规则，程序会在编译时自动选择系统中性能最高的 I/O 多路复用函数库来作为 Redis 的 I/O 多路复用程序的底层实现(ae.c文件)：

/* Include the best multiplexing layer supported by this system.
 * The following should be ordered by performances, descending. */
#ifdef HAVE_EVPORT
#include "ae_evport.c"
#else
    #ifdef HAVE_EPOLL
    #include "ae_epoll.c"
    #else
        #ifdef HAVE_KQUEUE
        #include "ae_kqueue.c"
        #else
        #include "ae_select.c"
        #endif
    #endif
#endif

文件事件处理器

Redis基于 Reactor 模式开发了自己的网络事件处理器：这个处理器被称为文件事件处理器：

• 文件事件处理器使用 I/O 多路复用程序来同时监听多个套接字，并根据套接字目前执行的任务来为套接字关联不同的事件处理器。
• 当被监听的套接字准备好执行连接应答(accept)、读取(read)、写入(write)、关闭(close)等操作时，与操作相对应的文件事件就会产生，这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。

下图展示了文件事件处理器的四个组成部分：套接字、I/O多路复用程序、文件事件分派器(dispatcher)、事件处理器。

文件事件是对套接字操作的抽象，每当一个套接字准备好执行连接应答、写入、读取、关闭等操作时，就会产生一个文件事件。因为一个服务器通常会连接多个套接字，所以多个文件事件有可能会并发地出现。I/O 多路复用程序负责监听多个套接字，并向文件事件分派器传送那些产生了事件的套接字。

哪吒问的问题很棒，联想一下，生活中一群人去食堂打饭，阿姨说的最多的一句话就是：排队啦！排队啦！一个都不会少！

没错，一切来源生活！Redis 的 I/O多路复用程序总是会将所有产生事件的套接字都放到一个队列里面，然后通过这个队列，以有序、同步、每次一个套接字的方式向文件事件分派器传送套接字。当上一个套接字产生的事件被处理完毕之后，I/O 多路复用程序才会继续向文件事件分派器传送下一个套接字。

Redis为文件事件处理器编写了多个处理器，这些事件处理器分别用于实现不同的网络通信需求：

• 为了对连接服务器的各个客户端进行应答，服务器要为监听套接字关联连接应答处理器；
• 为了接受客户端传来的命令请求，服务器要为客户端套接字关联命令请求处理器 ；
• 为了向客户端返回命令的执行结果，服务器要为客户端套接字关联命令回复处理器 ；
• 当主服务器和从服务器进行复制操作时，主从服务器都需要关联特别为复制功能编写的复制处理器。

连接应答处理器

networking.c/acceptTcpHandler函数是Redis的连接应答处理器，这个处理器用于对连接服务器监听套接字的客户端进行应答，具体实现为sys/socket.h/acccept函数的包装。

当Redis服务器进行初始化的时候，程序会将这个连接应答处理器和服务器监听套接字的AE_READABLE时间关联起来，当有客户端用sys/socket.h/connect函数连接服务器监听套接字的时候，套接字就会产生AE_READABLE事件，引发连接应答处理器执行，并执行相应的套接字应答操作。

命令请求处理器

networking.c/readQueryFromClient函数是Redis的命令请求处理器，这个处理器负责从套接字中读入客户端发送的命令请求内容，具体实现为unistd.h/read函数的包装。

当一个客户端通过连接应答处理器成功连接到服务器之后，服务器会将客户端套接字的AE_READABLE事件和命令请求处理器关联起来，当客户端向服务器发送命令请求的时候，套接字就会产生AE_READABLE事件，引发命令请求处理器执行，并执行相应的套接字读入操作。

在客户端连接服务器的整个过程中，服务器都会一直为客户端套接字AE_READABLE事件关联命令请求处理器。

命令回复处理器

networking.c/sendReplyToClient函数是Redis的命令回复处理器，这个处理器负责从服务器执行命令后得到的命令回复通过套接字返回给客户端，具体实现为unistd.h/write函数的包装。

当服务器有命令回复需要传送给客户端的时候，服务器会将客户端套接字的AE_WRITABLE事件和命令回复处理器关联起来，当客户端准备好接收服务器传回的命令回复时，就会产生AE_WRITABLE事件，引发命令回复处理器执行，并执行相应的套接字写入操作。

当命令回复发送完毕之后，服务器就会解除命令回复处理器与客户端套接字的AE_WRITABLE事件之间的关联。

小总结

一句话描述 IO 多路复用在 Redis 中的应用：Redis 将所有产生事件的套接字都放到一个队列里面，以有序、同步、每次一个套接字的方式向文件事件分派器传送套接字，文件事件分派器根据套接字对应的事件选择响应的处理器进行处理，从而实现了高效的网络请求。

Redis的自定义协议

Redis客户端使用RESP（Redis的序列化协议）协议与Redis的服务器端进行通信。 它实现简单，解析快速并且人类可读。

RESP 支持以下数据类型：简单字符串、错误、整数、批量字符串和数组。

RESP 在 Redis 中用作请求-响应协议的方式如下：

• 客户端将命令作为批量字符串的 RESP 数组发送到 Redis 服务器。
• 服务器根据命令实现以其中一种 RESP 类型进行回复。

在 RESP 中，某些数据的类型取决于第一个字节：

• 对于简单字符串，回复的第一个字节是“+”
• 对于错误，回复的第一个字节是“-”
• 对于整数，回复的第一个字节是“:”
• 对于批量字符串，回复的第一个字节是“$”
• 对于数组，回复的第一个字节是“*”

此外，RESP 能够使用稍后指定的批量字符串或数组的特殊变体来表示 Null 值。在 RESP 中，协议的不同部分总是以“\r\n”（CRLF）终止。

下面只简单介绍字符串的编码方式和错误的编码方式，详情可以查看 Redis 官网对 RESP 进行了详细的说明。

简单字符串

用如下方法编码：一个“+”号后面跟字符串，最后是“\r\n”，字符串里不能包含"\r\n"。简单字符串用来传输比较短的二进制安全的字符串。例如很多redis命令执行成功会返回“OK”，用RESP编码就是5个字节：

"+OK\r\n"

想要发送二进制安全的字符串，需要用RESP的块字符串。当redis返回了一个简单字符串的时候，客户端库需要给调用者返回“+”号（不含）之后CRLF之前（不含）的字符串。

RESP错误

RESP 有一种专门为错误设计的类型。实际上错误类型很像RESP简单字符串类型，但是第一个字符是“-”。简单字符串类型和错误类型的区别是客户端把错误类型当成一个异常，错误类型包含的字符串是异常信息。格式是：

"-Error message\r\n"

有错误发生的时候才会返回错误类型，例如你执行了一个对于某类型错误的操作，或者命令不存在等。当返回一个错误类型的时候客户端库应该发起一个异常。下面是一个错误类型的例子

-ERR unknown command 'foobar' -WRONGTYPE Operation against a key holding the wrong kind of value

“-”号之后空格或者换行符之前的字符串代表返回的错误类型，这只是惯例，并不是RESP要求的格式。例如ERR是一般错误，WRONGTYPE是更具体的错误表示客户端的试图在错误的类型上执行某个操作。这个称为错误前缀，能让客户端更方便的识别错误类型。

客户端可能为不同的错误返回不同的异常，也可能只提供一个一般的方法来捕捉错误并提供错误名。但是不能依赖客户端提供的这些特性，因为有的客户端仅仅返回一般错误，比如false。

高性能 Redis 协议分析器

尽管 Redis 的协议非常利于人类阅读， 定义也很简单， 但这个协议的实现性能仍然可以和二进制协议一样快。

因为 Redis 协议将数据的长度放在数据正文之前， 所以程序无须像 JSON 那样， 为了寻找某个特殊字符而扫描整个 payload ， 也无须对发送至服务器的 payload 进行转义（quote）。

程序可以在对协议文本中的各个字符进行处理的同时， 查找 CR 字符， 并计算出批量回复或多条批量回复的长度， 就像这样：

#include <stdio.h>

int main(void) {
    unsigned char *p = "$123\r\n";
    int len = 0;

    p++;
    while(*p != '\r') {
        len = (len*10)+(*p - '0');
        p++;
    }

    /* Now p points at '\r', and the len is in bulk_len. */
    printf("%d\n", len);
    return 0;
}

得到了批量回复或多条批量回复的长度之后， 程序只需调用一次 read 函数， 就可以将回复的正文数据全部读入到内存中， 而无须对这些数据做任何的处理。在回复最末尾的 CR 和 LF 不作处理，丢弃它们。

Redis 协议的实现性能可以和二进制协议的实现性能相媲美， 并且由于 Redis 协议的简单性， 大部分高级语言都可以轻易地实现这个协议， 这使得客户端软件的 bug 数量大大减少。

冷知识：redis到底有多快？

在成功安装了Redis之后，Redis自带一个可以用来进行性能测试的命令 redis-benchmark，通过运行这个命令，我们可以模拟N个客户端同时发送请求的场景，并监测Redis处理这些请求所需的时间。

根据官方的文档，Redis经过在60000多个连接中进行了基准测试，并且仍然能够在这些条件下维持50000 q/s的效率，同样的请求量如果打到MySQL上，那肯定扛不住，直接就崩掉了。也是因为这个原因，Redis经常作为缓存存在，能够起到对数据库的保护作用。

可以看出来啊，Redis号称十万吞吐量确实也没吹牛，以后大家面试的时候也可以假装不经意间提一嘴这个数量级，发现很多人对“十万级“、”百万级“这种量级经常乱用，能够比较精准的说出来也是一个加分项呢。

我是敖丙，你知道的越多，你不知道的越多，感谢各位人才的：点赞、收藏和评论，我们下期见！

---

文章持续更新，可以微信搜一搜「 三太子敖丙 」第一时间阅读，回复【资料】有我准备的一线大厂面试资料和简历模板，本文 GitHub https://github.com/JavaFamily 已经收录，有大厂面试完整考点，欢迎Star。

上次发操作系统笔记，很快浏览上万，这次数据结构比上次硬核的多哦，同样的会发超硬核代码，关注吧。

超硬核！操作系统学霸笔记，考试复习面试全靠它

 

---

 

---

 

第一次笔记（复习c，课程概述）

第一节课复习了c语言的一些知识，并简单介绍了数据结构这门课程。

 

1、引用和函数调用：

1.1引用：对一个数据建立一个“引用”，他的作用是为一个变量起一个别名。这是C++对C语言的一个重要补充。

用法很简单：

int a = 5;

int &b = a;

b是a别名，b与a代表的是同一个变量，占内存中同一个存储单元，具有同一地址。

注意事项：

1. 声明一个引用，同时必须初始化，及声明它代表哪一个变量。（作为函数参数时不需要初始化）
    
2. 在声明一个引用后，不能再作为另一变量的引用。

     3。不能建立引用数组。

1.2函数调用：

其实还是通过函数来理解了一下引用

void Myswap1(int a,int b)
{
	int c = a;
	a = b;
	b = c;
}

void Myswap2(int &a,int &b)
{
	int c = a;
	a = b;
	b = c;
}

void Myswap3(int *pa,int *pb)
{
	int c = *pa;
	*pa = *pb;
	*pb = c;
}

这三个函数很简单，第一个只传了值进来，不改变全局变量；而第三个也很熟悉，就是传递了地址，方便操作。依旧是“值传递”的方式，只不过传递的是变量的地址而已；那二就彻底改变了这些东西，引用作为函数参数，传入的实参就是变量，而不是数值，真正意义上的“变量传递”。

 

2、数组和指针：

这一块讲得比较简单，就是基本知识。

主要内容：

1、函数传数组就是传了个指针，这个大家都知道，所以传的时候你写arr[],里面写多少，或者不写，都是没关系的，那你后面一定要放一个变量来把数组长度传进来。

2、还有就是，定义：int arr[5]，你访问越界是不会报错的，但是逻辑上肯定就没有道理了。那用typedef int INTARR[3];访问越界，在vs上会报错，要注意。

3、再说一下指针和数组名字到底有什么区别？这本来就是两个东西，可能大家没注意罢了。

第一：指针可以自增，数组名不行，因为是常量啊。

第二：地址不同，虽然名字[n]，都可以这样用，但是数组名地址就是第一个元素地址。指针地址就是那个指针的地址，指针里存的才是第一个元素地址。

第三：sizeof（），空间不一样，数组是占数组那么大空间。指针是四个字节。

本来就是俩东西，这么多不同都是本质不同的体现。

3、结构体：

也是讲的基本操作，基本就是这个东西：

typedef struct Date
{
	int Year;
	int Month;
	int Day;
	struct Date *pDate;
}Date, *pDate;

1、内部无指向自己的指针才可以第一行先不起名字。

2、内部不能定义自己的，如果能的话那空间不就无限了么。很简单的逻辑

 

指针我不习惯，还是写Date *比较顺眼

3、有同学没注意：访问结构体里的东西怎么访问？

Date.这种形式，或者有指向这个节点的指针p可以p->这种形式，别写错了。

 

4、还有就是结构体能直接这么赋值：

   Date d1 = {2018,9,11};

我竟然不知道，以前还傻乎乎的一个一个赋值呢。

 

5、还有，想写一下结构体有什么优点。。

这一块可能写的就不好了，因为不是老师讲的。。

比如学生成绩，如果不用结构体，我们一个学生可能有十几个信息，那定义变量和操作就很烦琐了，数据结构有一种松散的感觉。用一个结构体来表示更好，无论是程序的可读性还是可移植性还是可维护性，都得到提升。还有就是函数调用的时候，传入相当多的参数，又想操作或者返回，那是很麻烦的事。现在只传入一个结构体就好了，操作极其简单。总结一下就是好操作，中看中用，有机地组织了对象的属性。以修改结构体成员变量的方法代替了函数(入口参数)的重新定义。

基本就这样吧。

6、还有就是它了：typedef int INTARR[3];这样直接定义了一个数据类型，长度为3的数组，然后直接这样用就可以了：

INTARR arr1;

 

回忆完C语言储备知识，然后讲了数据结构的基本概念

 

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。

数据：是对客观事物的符号表示，在计算机中指能输入到计算机中并被处理的符号总称。

数据元素：数据的基本单位

数据项：数据的不可分割的最小单位

数据对象：性质相同的数据元素的集合。

举例：动物是数据，某只动物是数据元素，猫狗是数据对象，颜色可以是数据项。

 

数据元素之间存在某种关系，这种关系成为结构。

四种基本结构：

集合：除了同属一个集合无其他关系。

线性结构：一对一的关系

树形结构：一对多的关系

图状结构：多对多的关系

 

第二次笔记（基本概念，时间空间复杂度）

今天继续说明了一些基本概念，讲解了时间空间复杂度。

（对于概念的掌握也很重要）

 

元素之间的关系在计算机中有两种表示方法：顺序映像和非顺序映像，由此得到两种不同的储存结构：

顺序存储结构和链式存储结构。

 

顺序：根据元素在存储器中的相对位置表示关系

链式：借助指针表示关系

 

数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。（仅仅取决于逻辑特性，与其在计算机内部如何表示和实现无关）

 

定义抽象数据类型的一种格式：

ADT name{

数据对象：<>

数据关系：<>

基本操作：<>

}ADT name

 

算法：是对特定问题求解步骤的一种描述。

算法五个特性：

1. 有穷性：有穷的时间内完成，或者可以说是可接受的时间完成
2. 确定性：对于相同的输入只能得到相同的输出
3. 可行性：描述的操作都可以执行基本操作有限次来实现
4. 输入：零个或多个输入。取自于某个特定对象的集合
5. 输出：一个或多个输出

 

设计要求：正确性、可读性、健壮性、效率与低存储量需求。

执行频度概念：是指通过统计算法的每一条指令的执行次数得到的。

执行频度=算法中每一条语句执行次数的和

一般认定每条语句执行一次所需时间为单位时间（常数时间）O(1)

 

几个小知识和小问题：

1）循环执行次数n+1次，不是n次。第一次执行i=1和判断i<=n以后执行n次判断和i++。所以该语句执行了n+1次。在他的控制下，循环体执行了n次。

2）四个并列程序段：分别为O(N),O(N^2),O(N^3),O(N*logN),整个程序时间复杂度为O(N^3)，因为随着N的增长，其它项都会忽略

3）算法分析的目的是分析算法的效率以求改进

4）对算法分析的前提是算法必须正确

5）原地工作指的不是不需要空间，而是空间复杂度O(1)，可能会需要有限几个变量。

实现统一功能两种算法：时间O(2^N),O(N^10)，假设计算机可以运行10^7秒，每秒可执行基本操作10^5次，问可解问题规模各为多少？选哪个更为合适？

计算机一共可执行10^7*10^5=10^12次

第一种：n=log2,(10^12)=12log(2,10)

第二种：n=（10^12）^0.1

显然1更适用。

虽然一般情况多项式算法比指数阶更优

 

时间空间复杂度概述

 

找个时间写一写时间复杂度和一些问题分类，也普及一下这方面知识。

如何衡量一个算法好坏

很显然，最重要的两个指标：需要多久可以解决问题、解决问题耗费了多少资源

那我们首先说第一个问题，要多长时间来解决某个问题。那我们可以在电脑上真实的测试一下嘛，多种方法比一比，用时最少的就是最优的啦。

但是没必要，我们可以通过分析计算来确定一个方法的好坏，用O()表示，括号内填入N、1，等式子。

这到底是什么意思呢？

简单来说，就是这个方法，时间随着数据规模变化而增加的快慢。时间可以当成Y，数据规模是X，y=f(x)，就这样而已。但是f(x)不是准确的，只是一个大致关系，y=10x,我们也视作x，因为他的增长速度还是n级别的。现在就可以理解了：一般O(N)就是对每个对象访问优先次数而已。请注意：O(1)它不是每个元素访问一次，而是Y=1的感觉，y不随x变化而变化，数据多大它的时间是不变的，有限的常数操作即可完成。

那我们就引入正规概念：

时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

注意：文中提到：不包括这个函数的低阶项和首项系数。什么意思呢？就是说10n,100n,哪怕1000000000n,还是算做O(N)，而低阶项是什么意思？不知大家有没有学高等数学1，里面有最高阶无穷大，就是这个意思。举个例子。比如y=n*n*n+n*n+n+1000

就算做o(n*n*n),因为增长速率最大，N*N及其它项增长速率慢，是低阶无穷大，n无限大时，忽略不计。

 

那接着写：o(n*n*n)的算法一定不如o(n)的算法吗？也不一定，因为之前说了，时间复杂度忽略了系数，什么意思？o(n)可以是10000000n，当n很小的时候，前者明显占优。

所以算法要视实际情况而定。

算法的时间 复杂度常见的有：
常数阶 O(1)，对数阶 O(log n)，线性阶 O(n)，
线性对数阶 O(nlog n)，平方阶 O(n^2)，立方阶 O(n^3)，…，
k 次方阶O(n^k)，指数阶 O(2^n)，阶乘阶 O(n!)。

常见的算法的时间 复杂度之间的关系为：
       O(1)<O(log n)<O(n)<O(nlog n)<O(n^2)<O(2^n)<O(n!)<O(n^n) 

 

我们在竞赛当中，看见一道题，第一件事就应该是根据数据量估计时间复杂度。

计算机计算速度可以视作10^9,如果数据量是10000，你的算法是O(N*N)，那就很玄，10000*10000=10000 0000，别忘了还有常数项，这种算法只有操作比较简单才可能通过。你可以想一想O(nlog n)的算法一般就比较稳了。那数据量1000，一般O(N*N)就差不多了，数据量更小就可以用复杂度更高的算法。大概就这样估算。

 

当 n 很大时，指数阶算法和多项式阶算法在所需时间上非常
悬殊。因此，只要有人能将现有指数阶算法中的任何一个算法化
简为多项式阶算法，那就取得了一个伟大的成就。

体会一下：

 

空间复杂度也是一样，用来描述占空间的多少。

注意时间空间都不能炸。

所以才发明了那么多算法。

符上排序算法的时间空间表，体会一下：

 

排序博客：加深对时间空间复杂度理解

https://blog.csdn.net/hebtu666/article/details/81434236

 

 

 

引入：算法优化

 

想写一系列文章，总结一些题目，看看解决问题、优化方法的过程到底是什么样子的。

 

系列问题一：斐波那契数列问题

在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）根据定义，前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55

问题一：

给定一个正整数n，求出斐波那契数列第n项（这时n较小）

解法一：最笨，效率最低，暴力递归，完全是抄定义。请看代码

def f0(n):
    if n==1 or n==2:
        return 1
    return f(n-1)+f(n-2)

 

分析一下，为什么说递归效率很低呢？咱们来试着运行一下就知道了：

 

比如想求f(10)，计算机里怎么运行的？

 

每次要计算的函数量都是指数型增长，时间复杂度O(2^(N/2))<=T(N)<=O(2^N),效率很低。效率低的原因是，进行了大量重复计算，比如图中的f(8),f(7).....等等，你会发现f(8)其实早就算过了，但是你后来又要算一遍。

如果我们把计算的结果全都保存下来，按照一定的顺序推出n项，就可以提升效率， 斐波那契（所有的一维）的顺序已经很明显了，就是依次往下求。。

优化1

def f1(n):
    if n==1 or n==2:
        return 1
    l=[0]*n
    l[0],l[1]=1,1
    for i in range(2,n):
        l[i]=l[i-1]+l[i-2]
    return l[-1]

 

时间复杂度o(n)，依次往下打表就行，空间o(n).

继续优化：既然只求第n项，而斐波那契又严格依赖前两项，那我们何必记录那么多值呢？记录前两项就行了

 

优化2

def f2(n):
    a,b=1,1
    for i in range(n-1):
        a,b=b,a+b
    return a

此次优化做到了时间o(n),空间o(1)

附：这道题掌握到这里就可以了，但是其实有时间o(log2n)的方法

 

优化三：

学习过线性代数的同学们能够理解：

 

结合快速幂算法，我们可以在o(log2n)内求出某个对象的n次幂。(在其它专题详细讲解)

注意：只有递归式不变，才可以用矩阵+快速幂的方法。

注：优化三可能只有在面试上或竞赛中用，当然，快速幂还是要掌握的。

 

经过这个最简单的斐波那契，大家有没有一点感觉了？

好，我们继续往下走

(补充：pat、蓝桥杯原题，让求到一万多位，结果模一个数。

可以每个结果都对这个数取模，否则爆内存，另：对于有多组输入并且所求结果类似的题，可以先求出所有结果存起来，然后直接接受每一个元素，在表中查找相应答案)

 

问题二：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

依旧是找递推关系，分析：跳一阶，就一种方法，跳两阶，它可以一次跳两个，也可以一个一个跳，所以有两种，三个及三个以上，假设为n阶，青蛙可以是跳一阶来到这里，或者跳两阶来到这里，只有这两种方法。它跳一阶来到这里，说明它上一次跳到n-1阶，同理，它也可以从n-2跳过来，f（n）为跳到n的方法数，所以，f(n)=f(n-1)+f(n-2)

和上题的优化二类似。

因为递推式没变过，所以可以用优化三

 

问题三：

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？提示，大矩形看做是长度吧

请读者自己先思考一下吧。。。仔细看题。。仔细思考

如果n是1，只有一种，竖着放呗；n是2，两种：

，

n等于3，三种：

 

题意应该理解了吧？

读到这里，你们应该能很快想到，依旧是斐波那契式递归啊。

对于n>=3:怎么能覆盖到三？只有两种办法，从n-1的地方竖着放了一块，或者从n-2的位置横着放了两块呗。

和问题二的代码都不用变。

 

问题四：

给定一个由0-9组成的字符串，1可以转化成A，2可以转化成B。依此类推。。25可以转化成Y，26可以转化成z，给一个字符串，返回能转化的字母串的有几种？

比如：123，可以转化成

1 2 3变成ABC，

12 3变成LC，

1 23变成AW，三种，返回三，

99999，就一种：iiiii，返回一。

分析：求i位置及之前字符能转化多少种。

两种转化方法，一，字符i自己转换成自己对应的字母，二，和前面那个数组成两位数，然后转换成对应的字母

假设遍历到i位置，判断i-1位置和i位置组成的两位数是否大于26，大于就没有第二种方法，f(i)=f(i-1),想反，等于f(i-1)+f(i-2)

注意：递归式不确定，不能用矩阵快速幂

 

(这几个题放到这里就是为了锻炼找递归关系的能力，不要只会那个烂大街的斐波那契)

 

'''
斐波那契问题：
斐波纳契数列以如下被以递归的方法定义：
F(1)=1
F(2)=1
F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
'''
#暴力抄定义,过多重复计算
def f0(n):
    if n==1 or n==2:
        return 1
    return f(n-1)+f(n-2)
#记录结果后依次递推的优化，时间O(N)
def f1(n):
    if n==1 or n==2:
        return 1
    l=[0]*n
    l[0],l[1]=1,1
    for i in range(2,n):
        l[i]=l[i-1]+l[i-2]
    return l[-1]
#既然严格依赖前两项，不必记录每一个结果，优化空间到O(1)
def f2(n):
    a,b=1,1
    for i in range(n-1):
        a,b=b,a+b
    return a

第三次笔记（线性表结构和顺序表示）

 

这节课介绍了线性表结构和顺序表示的一部分内容。

操作太多，而且书上有，就不一一介绍分析了。

线性表定义：n个数据元素的有限序列。

特点：

1. 存在唯一一个称作“第一个”的元素。
2. 存在唯一一个称作“最后一个”的元素
3. 除最后一个元素外，集合中每一个元素都只有一个直接前趋
4. 除最后一个元素外，集合中每一个元素都只有一个直接后继

注意1、2条：证明循环的序列不是线性表

 

注意：

1)线性表从1开始,线性表第一个元素对应到数组中下标是0.

2)函数通过引用对线性表的元素进行修改即可

3)数组比较特别，它即可视为逻辑结构，又可视为存储结构。

4)每一个表元素都是不可再分的原子数据。一维数组可以视为线性表，二维数组不可以，在逻辑上它最多可以有两个直接前趋和直接后继。

5)线性表具有逻辑上的顺序性，在序列中各元素有其先后次序，各个数据元素在线性表中的逻辑位置只取决于序号。

 

顺序表：是线性表的循序储存结构，以物理位置表示逻辑关系，任意元素可以随机存取。用一组地址连续的存储单元依次存储线性表中的元素。逻辑顺序和物理顺序是一致的。可以顺序访问，也可随机访问。

顺序表存储：

这些定式还是很重要的，比如define typedef等，真正实现时最好就这样写，不要自己规定个长度和数据类型，这样以后好维护、修改。

静态存储分配：

#define maxSize 100//显式定义表长

Typedef int DataType;//定义数据类型

Typedef struct{

DataType data[maxSize];//静态分配存储表元素向量

Int n;//实际表中个数

}SeqList;

 

动态存储分配：

#define maxSize 100//长度初始定义

Typedef int DataType;//定义数据类型

Typedef struct{

DataType *data;//动态分配数组指针

Int maxSize,n;//最大容量和当前个数

}SeqList;

 

初始动态分配：

Data=(DataType *)malloc(sizeof(DataType)* initSize);

C++:data=new DataType[initSize];

maxSize=initSize;n=0;

动态分配存储，向量的存储空间是在程序执行过程中通过动态存储分配来获取的。空间满了就另外分配一块新的更大的空间，用来代替原来的存储空间，从而达到扩充的目的。

 

插入：需要查找，移动元素，概率上1，2，3....n，平均O(N)

删除：同样需要移动元素。填充被空出来的存储单元。

在等概率下平均移动次数分别为n/2,(n-1)/2

 插入注意事项：

1. 需要判断是否已满
2. 要从后向前移动，否则会冲掉元素

删除注意事项：

1. 需要先判断是否已空
2. 需要把后方元素前移，要从前向后。

 

注意：线性表的顺序存储借用了一维数组，但是二者不同：

1. 一维数组各非空结点可以不相继存放，但顺序表是相继存放的
2. 顺序表长度是可变的，一维数组长度是确定的，一旦分配就不可变
3. 一维数组只能按下标存取元素，顺序表可以有线性表的所有操作。

 

 

第四次笔记（链表概述）

 

介绍了链表和基本操作

用一组物理位置任意的存储单元来存放线性表的数据元素。 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中元素的逻辑次序和 物理次序不一定相同。

 

定义：

typedef  struct  Lnode{  
        //声明结点的类型和指向结点的指针类型  
        ElemType         data;    //数据元素的类型 
        struct   Lnode  *next;   //指示结点地址的指针  
}Lnode, *LinkList;  

struct Student
{ char num[8];   //数据域
  char name[8];  //数据域
  int score;          //数据域
  struct Student *next;  // next 既是 struct Student 
                                       // 类型中的一个成员，又指 
                                       // 向 struct Student 类型的数据。 
}Stu_1, Stu_2, Stu_3, *LL;  

头结点：在单链表的第一个结点之前人为地附设的一个结点。

带头结点操作会方便很多。

带和不带的我都写过了

下面列出我见过的一些好题

1、

线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

• 正确

• 错误

 

错，线性表是逻辑结构概念，可以顺序存储或链式储，与元素数据类型无关。链表就是线性表的一种  前后矛盾

 

2、

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用(    )存储方式最节省运算时间。

• 单链表

• 仅有头指针的单循环链表

• 双链表

• 仅有尾指针的单循环链表

  对于A,B，C要想在尾端插入结点，需要遍历整个链表。

  对于D，要插入结点，只要改变一下指针即可，要删除头结点，只要删除指针.next的元素即可。

 

3、注意：线性表是具有n个数据元素的有限序列，而不是数据项

 

4、

以下关于单向链表说法正确的是

• 如果两个单向链表相交，那他们的尾结点一定相同

• 快慢指针是判断一个单向链表有没有环的一种方法

• 有环的单向链表跟无环的单向链表不可能相交

• 如果两个单向链表相交，那这两个链表都一定不存在环

自己多画画想想就明白了，关于快慢指针我以后会写总结。

 

5、

链接线性表是顺序存取的线性表 。 ( )

• 正确

• 错误

链接线性表可以理解为链表
线性表分为顺序表和链表
顺序表是顺序存储结构、随机存取结构
链表是随机存储结构、顺序存取结构

 

6、

typedef struct node_s{
    int item;
    struct node_s* next;
}node_t;
node_t* reverse_list(node_t* head)
{
    node_t* n=head;
    head=NULL;
    while(n){
    _________               
    }
    return head;
 }

空白处填入以下哪项能实现该函数的功能？

• node_t* m=head; head=n; head->next=m; n=n->next;

• node_t* m=n; n=n->next; m->next=head; head=m;

• node_t* m=n->next; n->next=head; n=m; head=n;

• head=n->next; head->next=n; n=n->next;

 

代码的功能是要实现链表的反转。为了方便阐述，每个结点用①②③④⑤⑥等来标示。

在执行while（n）循环之前，有两句代码：

node_t* n=head; head=NULL;

这两行代码的中：第一句的作用是用一个临时变量n来保存结点①，第二句是把head修改为NULL。

然后就开始遍历了，我们看到while循环里的那四句代码：

node_t* m=n; 
n=n->next; 
m->next=head; 
head=m；

先看前两句，用m来保存n，然后让n指向n的下一个结点，之所以复制 n 给 m ，是因为 n 的作用其实是  控制while循环次数  的作用，每循环一次它就要被修改为指向下一个结点。

再看后两句，变量head在这里像是一个临时变量，后两句让 m 指向了 head，然后 head 等于 m。

 

7、

若某表最常用的操作是在最后一个结点之后插入一个节点或删除最后一二个结点，则采用（）省运算时间。

• 单链表

• 双链表

• 单循环链表

• 带头结点的双循环链表

D

带头结点的双向循环链表，头结点的前驱即可找到最后一个结点，可以快速插入，再向前可以找到最后一二个结点快速删除

单链表找到链表尾部需要扫描整个链表

双链表找到链表尾部也需要扫描整个链表

单循环链表只有单向指针，找到链表尾部也需要扫描整个链表

 

8、

单链表的存储密度（  ）

• 大于1

• 等于1

• 小于1

• 不能确定

全麦白

存储密度 = 数据项所占空间 / 结点所占空间

 

9、完成在双循环链表结点p之后插入s的操作是

• s->prior=p; s->next=p->next; p->next->prior=s ; p->next=s;

 

10、用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时()

• 仅修改队头指针

• 仅修改队尾指针

• 队头、队尾指针都可能要修改

• 队头、队尾指针都要修改

 

当只有一个元素，出队列时，要将队头和队尾，指向-1.所以说队头和队尾都需要修改

 

 

链表刷了几百道吧，好题还有很多，以后接着更新

 

 

第六次笔记（链表选讲/静态链表）

 

本节课介绍了单链表的操作实现细节，介绍了静态链表。

 

链表带头的作用：对链表进行操作时，可以对空表、非空表的情况以及 对首元结点进行统一处理，编程更方便。

下面给出带头的单链表实现思路：

 

按下标查找：

判断非法输入，当 1 < =i <= n 时，i 的值是合法的。

p = L -> next; j = 1;

while ( p && j < i ) {  p = p ->next; ++j; }

return 

 

按值查找：

 p = L1 -> next;

 while ( p && p ->data!=key)          p = p -> next;

return;

 

插入：

判断

查找

创建

插入

 

删除：

查找

删除

释放内存

 

静态链表

对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。

这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。

 

表示：

#define MAXSIZE 1000      / /链表的最大长度

typedef  struct{      

    ElemType data；        

    int cur；

}component,  SLinkList[MAXSIZE]；

 

过程：

 

 

顺序存储线性表实现

 

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

 

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

优点：随机存取表中元素。缺点：插入和删除操作需要移动元素。

 

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

给出两种基本实现：

/*
静态顺序存储线性表的基本实现
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INITSIZE 100
#define ElemType int
#define Status int
#define OK     1
#define ERROR  0

typedef struct
{
	ElemType elem[LIST_INITSIZE];
	int length;
}SqList;

//函数介绍
Status InitList(SqList *L); //初始化
Status ListInsert(SqList *L, int i,ElemType e);//插入
Status ListDelete(SqList *L,int i,ElemType *e);//删除
void ListPrint(SqList L);//输出打印
void DisCreat(SqList A,SqList *B,SqList *C);//拆分(按正负)，也可以根据需求改
//虽然思想略简单，但是要写的没有错误，还是需要锻炼coding能力的

Status InitList(SqList *L)
{
    L->length = 0;//长度为0
    return OK;
}

Status ListInsert(SqList *L, int i,ElemType e)
{
    int j;
    if(i<1 || i>L->length+1)
        return ERROR;//判断非法输入
    if(L->length == LIST_INITSIZE)//判满
    {
        printf("表已满");//提示
        return ERROR;//返回失败
    }
    for(j = L->length;j > i-1;j--)//从后往前覆盖，注意i是从1开始
        L->elem[j] = L->elem[j-1];
    L->elem[i-1] = e;//在留出的位置赋值
    (L->length)++;//表长加1
    return OK;//反回成功
}

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int j;
    if(i<1 || i>L->length)//非法输入/表空
        return ERROR;
    *e = L->elem[i-1];//为了返回值
    for(j = i-1;j <= L->length;j++)//从前往后覆盖
        L->elem[j] = L->elem[j+1];
    (L->length)--;//长度减1
    return OK;//返回删除值
}

void ListPrint(SqList L)
{
    int i;
    for(i = 0;i < L.length;i++)
        printf("%d ",L.elem[i]);
    printf("\n");//为了美观
}

void DisCreat(SqList A,SqList *B,SqList *C)
{
    int i;
    for(i = 0;i < A.length;i++)//依次遍历A中元素
    {
        if(A.elem[i]<0)//判断
            ListInsert(B,B->length+1,A.elem[i]);//直接调用插入函数实现尾插
        else
            ListInsert(C,C->length+1,A.elem[i]);
    }
}

int main(void)
{
    //复制的
	SqList L;
	SqList B, C;
	int i;
	ElemType e;
	ElemType data[9] = {11,-22,33,-3,-88,21,77,0,-9};
	InitList(&L);
	InitList(&B);
	InitList(&C);
	for (i = 1; i <= 9; i++)
		ListInsert(&L,i,data[i-1]);
    printf("插入完成后L = : ");
	ListPrint(L);
    ListDelete(&L,1,&e);
	printf("删除第1个后L = : ");
	ListPrint(L);
    DisCreat(L , &B, &C);
	printf("拆分L后B = : ");
	ListPrint(B);
	printf("拆分L后C = : ");
	ListPrint(C);
	printf("拆分L后L = : ");
	ListPrint(L);
}

静态：长度固定

动态：不够存放可以加空间（搬家）

 

/*
子任务名任务:1_2 动态顺序存储线性表的基本实现
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define Status int
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define ElemType int

typedef struct
{
	ElemType * elem;
	int length;
	int listsize;
}SqList;
//函数介绍
Status InitList(SqList *L); //初始化
Status ListInsert(SqList *L, int i,ElemType e);//插入
Status ListDelete(SqList *L,int i,ElemType *e);//删除
void ListPrint(SqList L);//输出打印
void DeleteMin(SqList *L);//删除最小

Status InitList(SqList *L)
{
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//申请100空间
	if(!L->elem)//申请失败
		return ERROR;
	L->length = 0;//长度0
	L->listsize = LIST_INIT_SIZE;//容量100
	return OK;//申请成功
}

Status ListInsert(SqList *L,int i,ElemType e)
{
    int j;
    ElemType *newbase;
    if(i<1 || i>L->length+1)
        return ERROR;//非法输入
        
    if(L->length >= L->listsize)//存满了，需要更大空间
    {
        newbase = (ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));//大10的空间
        if(!newbase)//申请失败
            return ERROR;
        L->elem = newbase;//调指针
        L->listsize+= LISTINCREMENT;//新容量
    }
    
    for(j=L->length;j>i-1;j--)//从后往前覆盖
        L->elem[j] = L->elem[j-1];
    L->elem[i-1] = e;//在留出的位置赋值
    L->length++;//长度+1
    return OK;
}

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int j;
    if(i<1 || i>L->length)//非法输入/表空
        return ERROR;
    *e = L->elem[i-1];//为了返回值
    for(j = i-1;j <= L->length;j++)//从前往后覆盖
        L->elem[j] = L->elem[j+1];
    (L->length)--;//长度减1
    return OK;//返回删除值
}

void ListPrint(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        printf("%d ",L.elem[i]);
    printf("\n");//为了美观
}

void DeleteMin(SqList *L)
{
    //表空在Listdelete函数里判断
    int i;
    int j=0;//最小值下标
    ElemType *e;
    for(i=0;i<L->length;i++)//寻找最小
    {
        if(L->elem[i] < L->elem[j])
            j=i;
    }
    ListDelete(L,j+1,&e);//调用删除，注意j要+1
}

int main(void)
{
	SqList L;
	int i;
	ElemType e;
	ElemType data[9] = {11,-22,-33,3,-88,21,77,0,-9};
	InitList(&L);
	for (i = 1; i <= 9; i++)
	{
		ListInsert(&L,i,data[i-1]);
	}
	printf("插入完成后 L = : ");
	ListPrint(L);
    ListDelete(&L, 2, &e);
	printf("删除第 2 个后L = : ");
	ListPrint(L);
    DeleteMin(&L);
	printf("删除L中最小值后L = : ");
	ListPrint(L);
	DeleteMin(&L);
	printf("删除L中最小值后L = : ");
	ListPrint(L);
	DeleteMin(&L);
	printf("删除L中最小值后L = : ");
	ListPrint(L);
}

单链表，不带头实现

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

 

下面给出不带头的单链表标准实现：

定义节点：

typedef struct node 
{ 
    int data;
    struct node * next;
}Node;

尾插：

void pushBackList(Node ** list, int data) 
{ 
    Node * head = *list;
    Node * newNode = (Node *)malloc(sizeof(Node));//申请空间
    newNode->data = data; newNode->next = NULL;
    if(*list == NULL)//为空
        *list = newNode;
    else//非空
    {
        while(head ->next != NULL)
            head = head->next;
        head->next = newNode;
    }
}

插入：

int insertList(Node ** list, int index, int data) 
{
    int n;
    int size = sizeList(*list); 
    Node * head = *list; 
    Node * newNode, * temp;
    if(index<0 || index>size) return 0;//非法
    newNode = (Node *)malloc(sizeof(Node)); //创建新节点
    newNode->data = data; 
    newNode->next = NULL;
    if(index == 0) //头插
    {
        newNode->next = head; 
        *list = newNode; 
        return 1; 
    }
    for(n=1; n<index; n++) //非头插
        head = head->next;
    if(index != size) 
        newNode->next = head->next; 
    //链表尾部next不需指定
    head->next = newNode; 
    return 1;
}

按值删除：

void deleteList(Node ** list, int data) 
{ 
    Node * head = *list; Node * temp; 
    while(head->next!=NULL) 
    { 
        if(head->next->data != data) 
        { 
            head=head->next; 
            continue; 
        } 
        temp = head->next;
        if(head->next->next == NULL) //尾节点删除
            head->next = NULL; 
        else 
            head->next = temp->next; 
        free(temp);
    }    
    head = *list; 
    if(head->data == data) //头结点删除
    { 
        temp = head; 
        *list = head->next; 
        head = head->next; 
        free(temp); 
    }
}

打印：

void printList(Node * head) 
{ 
    Node * temp = head; 
    for(; temp != NULL; temp=temp->next) 
        printf("%d ", temp->data); 
    printf("\n"); 
}

清空：

void freeList(Node ** list) 
{ 
    Node * head = *list; 
    Node * temp = NULL; 
    while(head != NULL) //依次释放
    { 
        temp = head; 
        head = head->next; 
        free(temp); 
    } 
    *list = NULL; //置空
}

别的也没啥了，都是基本操作

有些代码要分情况，很麻烦，可读性较强吧

看我压缩代码：https://blog.csdn.net/hebtu666/article/details/81261043

 

双链表带头实现

以前写的不带头的单链表实现，当时也啥也没学，好多东西不知道，加上一心想压缩代码，减少情况，所以写得不太好。

请教了老师，首先是命名问题和代码紧凑性等的改进。还有可读性方面的改进，多写了一些注释。并且因为带头的比较好写，好操作，所以标准写法也不是很长，繁琐。

 

 

下面贴代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node{
    int key;//数据
    struct node * prev;//前驱
    struct node * next;//后继
}Node;

初始化（带头） 

Node * list;
//初始化，这里·我们list不再是NULL，而是指向了一个节点
//这个改进方便了很多操作，也不用借助二重指针把list和next统一表示了

void init(Node * list)//初始化
{
    list = (Node *)malloc(sizeof(Node));
    list->next = NULL;
    list->prev = NULL;
}

查找（不用再判断一下空不空）

Node * find(int key,Node * list)
{
    Node * head = list->next;//从头节点后面开始找
    while(head != NULL && head->key != key)//找到或空跳出
        head = head->next;
    return head;
}

打印

void printList(Node * list)//打印
{
    Node * temp = list->next;头节点下一个开始
    while(temp != NULL)
    {
        printf("%d ",temp->key);
        temp = temp->next;
    }
    printf("\n");
}

删除指定结点

void delete(Node * list)//删除指定结点
{
    list->prev->next = list->next;前面后面指针改了，再free自己即可
    list->next->prev = list->prev;
    free(list);
}

配合一下删除：

void deleteKey(int key,Node * list)
{
    delete(find(key,list));
}

头插：

void insertHead(int key,Node * list)//头插
{
    Node * newNode = (Node *)malloc(sizeof(Node));//初始化
    newNode->key = key;
    newNode->next = list->next;//赋值后继
    if(list->next != NULL)//如果有后继，赋值后继的前指针为新结点
        list->next->prev = newNode;
    list->next = newNode;//改头
    newNode->prev = list;//赋值新结点前指针
}

按下标插入

单链表都写了，我就不写长度函数和判断非法了，用的时候注意吧。

void insert(int key,Node * list,int index)
{
    Node * head=list;//最后指到要插位置的前一个即可
    Node * newNode = (Node *)malloc(sizeof(Node));//初始化
    newNode->key = key;
    while(index--)
        head = head->next;
    newNode->next = head->next;//修改指针
    newNode->prev = head;
    head->next = newNode;
}

指定某值后插入不写了，和这个修改指针逻辑一样，再传一个find配合一下就行了。

 

然后简单测试

int main()
{
    Node * list = NULL;
    init(list);
    insertHead(1,list);
    insertHead(2,list);
    insertHead(3,list);
    printList(list);
    deleteKey(2,list);
    printList(list);
    insert(10,list,0);
    printList(list);
}

 

第七次笔记（栈/队列）

 

介绍栈和队列基本概念和用法。

 

设输入序列1、2、3、4，则下述序列中（ ）不可能是出栈序列。【中科院中国科技大学2005】

A. 1、2、3、4                      B. 4、 3、2、1

C. 1、3、4、2                      D.４、1、2、3

选D

我是一个个模拟来做的。

 

描述栈的基本型性质：

1、集合性：栈是由若干个元素集合而成，没有元素（空集）成为空栈。

2、线性：除栈顶和栈底之外，任意元素均有唯一前趋和后继。

3、运算受限：只在一端插入删除的线性表即为栈

 

顺序存储和顺序存取：顺序存取是只能逐个存或取结构中的元素，例如栈。顺序存储是利用一个连续的空间相继存放，例如栈可基于一维数组存放元素。

 

一个较早入栈的元素能否在后面元素之前出栈？如果后面元素压在它上面，就不可以了。如果后面元素未压入，它可以弹出。在其他元素前面。

 

 

栈与递归：

  当在一个函数的运行期间调用另一个函数时，在运行 该被调用函数之前，需先完成三件事：  将实参等传递给被调用函数，保存返回地址（入栈）；  为被调用函数的局部变量分配存储区；    将控制转移到被调用函数的入口。  

从被调用函数返回调用函数之前，应该完成：  保存被调函数的计算结果；  释放被调函数的数据区；  按被调函数保存的返回地址（出栈）将控制转移到调        用函数。

多个函数嵌套调用的规则是：后调用先返回。

 此时的内存管理实行“栈式管理”

 

队列：

        在多用户计算机系统中，各个用户需要使用 CPU 运行自己的程序，它们分别向操作系统提出使用 CPU 的请求，操作系统按照每个请求在时间上的先后顺序， 将其排成一个队列，每次把CPU分配给队头用户使用， 当相应的程序运行结束，则令其出队，再把CPU分配 给新的队头用户，直到所有用户任务处理完毕。

 

以主机和打印机为例来说明，主机输出数据给打印 机打印，主机输出数据的速度比打印机打印的速度要快 得多，若直接把输出的数据送给打印机打印，由于速度 不匹配，显然不行。解决的方法是设置一个打印数据缓 冲区，主机把要打印的数据依此写到这个缓冲区中，写 满后就暂停输出，继而去做其它的事情，打印机就从缓 冲区中按照先进先出的原则依次取出数据并打印，打印 完后再向主机发出请求，主机接到请求后再向缓冲区写 入打印数据，这样利用队列既保证了打印数据的正确， 又使主机提高了效率。

 

双端队列：

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，若元素a,b,c,d,e依次入队列后，再进行出队操作，则不可能得到的顺序是（ ）。 

A. bacde                B. dbace              C. dbcae                D. ecbad

解析：出队只能一端，所以abcde一定是这个顺序。

反模拟入队，每次只能在两边出元素。

 

栈/队列 互相模拟实现

 

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路：大概这么想：用一个辅助栈把进第一个栈的元素倒一下就好了。

比如进栈1，2，3，4，5

第一个栈：

5

4

3

2

1

然后倒到第二个栈里

1

2

3

4

5

再倒出来，顺序为1，2，3，4，5

实现队列

然后要注意的事情：

1）栈2非空不能往里面倒数，顺序就错了。栈2没数再从栈1倒。

2）栈1要倒就一次倒完，不倒完的话，进新数也会循序不对。

import java.util.Stack;
 
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
     
    public void push(int node) {
        stack1.push(node);
    }
     
    public int pop() {
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

 

用两个队列实现栈，要求同上：

这其实意义不是很大，有些数据结构书上甚至说两个队列不能实现栈。

其实是可以的，只是时间复杂度较高，一个弹出操作时间为O(N)。

思路：两个队列，编号为1和2.

进栈操作：进1号队列

出栈操作：把1号队列全弄到2号队列里，剩最后一个别压入，而是返回。

最后还得把1和2号换一下，因为现在是2号有数，1号空。

 

仅仅有思考价值，不实用。

比如压入1，2，3

队列1：1，2，3

队列2：空

依次弹出1，2，3：

队列1里的23进入2号，3弹出

队列1：空

队列2：2，3

 

队列2中3压入1号，2弹出

队列1：3

队列2：空

 

队列1中只有一个元素，弹出。

 

上代码：

public class TwoQueueImplStack {
	Queue<Integer> queue1 = new ArrayDeque<Integer>();
	Queue<Integer> queue2 = new ArrayDeque<Integer>();
//压入
	public void push(Integer element){
		//都为空，优先1
		if(queue1.isEmpty() && queue2.isEmpty()){
			queue1.add(element);
			return;
		}
		//1为空，2有数据，放入2
		if(queue1.isEmpty()){
			queue2.add(element);
			return;
		}
		//2为空，1有数据，放入1
		if(queue2.isEmpty()){
			queue1.add(element);
			return;
		}
	}
//弹出
	public Integer pop(){
		//两个都空，异常
		if(queue1.isEmpty() && queue2.isEmpty()){
			try{
				throw new Exception("satck is empty!");
			}catch(Exception e){
				e.printStackTrace();
			}
		}	
		//1空，2有数据，将2中的数据依次放入1，最后一个元素弹出
		if(queue1.isEmpty()){
			while(queue2.size() > 1){
				queue1.add(queue2.poll());
			}
			return queue2.poll();
		}
		
		//2空，1有数据，将1中的数据依次放入2，最后一个元素弹出
		if(queue2.isEmpty()){
			while(queue1.size() > 1){
				queue2.add(queue1.poll());
			}
			return queue1.poll();
		}
		
		return (Integer)null;
	}
//测试
	public static void main(String[] args) {
		TwoQueueImplStack qs = new TwoQueueImplStack();
		qs.push(2);
		qs.push(4);
		qs.push(7);
		qs.push(5);
		System.out.println(qs.pop());
		System.out.println(qs.pop());
		
		qs.push(1);
		System.out.println(qs.pop());
	}
}

 

第八次笔记 （串）

串的概念：串（字符串）：是由 0 个或多个字符组成的有限序列。 通常记为：s =‘ a1 a2 a3 … ai …an  ’ ( n≥0 )。

串的逻辑结构和线性表极为相似。

 

一些串的类型：

 

空串：不含任何字符的串，长度 = 0。

空格串：仅由一个或多个空格组成的串。

子串：由串中任意个连续的字符组成的子序列。

主串：包含子串的串。

位置：字符在序列中的序号。

子串在主串中的位置：子串的首字符在主串中的位置。

 

空串是任意串的子串，任意串是其自身的子串。

串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。

 

实现：

 

因为串是特殊的线性表，故其存储结构与线性表的 存储结构类似，只不过组成串的结点是单个字符。

 

定长顺序存储表示

也称为静态存储分配的顺序串。 即用一组地址连续的存储单元依次存放串中的字符序列。

 

串长：可能首字符记录（显式）或\0结尾（隐式）

 

定长顺序存储表示时串操作的缺点 ：串的某些操作受限（截尾），如串的联接、插入、置换

 

堆分配存储表示  

 

存储空间在程序执行过程中动态分配，malloc() 分配一块实际串长所需要的存储空间（“堆”）

堆存储结构的优点：堆存储结构既有顺序存储 结构的特点，处理（随机取子串）方便，操作中对 串长又没有任何限制，更显灵活，因此在串处理的 应用程序中常被采用。

 

串的块链存储表示

为了提高空间利用率，可使每个结点存放多个字符 （这是顺序串和链串的综合 (折衷) ），称为块链结构。

 优点：便于插入和删除    缺点：空间利用率低 

 

串的定长表示

思想和代码都不难，和线性表也差不多，串本来就是数据受限的线性表。

串连接：

 

#include <stdio.h>
#include <string.h>
//串的定长顺序存储表示
#define MAXSTRLEN 255							//用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN + 1];	//0号单元存放串的长度

int Concat(SString *T,SString S1,SString S2)
	//用T返回S1和S2联接而成的新串。若未截断返回1，若截断返回0
{
	int i = 1,j,uncut = 0;
	if(S1[0] + S2[0] <= MAXSTRLEN)	//未截断
	{
		for (i = 1; i <= S1[0]; i++)//赋值时等号不可丢
			(*T)[i] = S1[i];
		for (j = 1; j <= S2[0]; j++)
			(*T)[S1[0]+j] = S2[j];	//(*T)[i+j] = S2[j]
		(*T)[0] = S1[0] + S2[0];
		uncut = 1;
	}
	else if(S1[0] < MAXSTRLEN)		//截断
	{
		for (i = 1; i <= S1[0]; i++)//赋值时等号不可丢
			(*T)[i] = S1[i];

		for (j = S1[0] + 1; j <= MAXSTRLEN; j++)
		{
			(*T)[j] = S2[j - S1[0] ];
			(*T)[0] = MAXSTRLEN;
			uncut = 0;
		}
	}
	else
	{
		for (i = 0; i <= MAXSTRLEN; i++)
			(*T)[i] = S1[i];
		/*或者分开赋值，先赋值内容，再赋值长度
		for (i = 1; i <= MAXSTRLEN; i++)
			(*T)[i] = S1[i];
		(*T)[0] = MAXSTRLEN;
		*/
		uncut = 0;
	}

	return uncut;
}

int SubString(SString *Sub,SString S,int pos,int len)
	//用Sub返回串S的第pos个字符起长度为len的子串
	//其中，1 ≤ pos ≤ StrLength(S)且0 ≤ len ≤ StrLength(S) - pos + 1(从pos开始到最后有多少字符)
	//第1个字符的下标为1,因为第0个字符存放字符长度
{
	int i;
	if(pos < 1 || pos > S[0] || len < 0 || len > S[0] - pos + 1)
		return 0;
	for (i = 1; i <= len; i++)
	{
		//S中的[pos,len]的元素 -> *Sub中的[1,len]
		(*Sub)[i] = S[pos + i - 1];//下标运算符 > 寻址运算符的优先级
	}
	(*Sub)[0] = len;
	return 1;
}
void PrintStr(SString S)
{
	int i;
	for (i = 1; i <= S[0]; i++)
		printf("%c",S[i]);
	printf("\n");
}


int main(void)
{
	/*定长顺序存储初始化和打印的方法
	SString s = {4,'a','b','c','d'};
	int i;
	//s = "abc";	//不可直接赋值
	for (i = 1; i <= s[0]; i++)
		printf("%c",s[i]);
	*/
	SString s1 = {4,'a','b','c','d'};
	SString s2 = {4,'e','f','g','h'},s3;
	SString T,Sub;
	int i;
	
	for (i = 1; i <= 255; i++)
	{
		s3[i] = 'a';
		if(i >= 248)
			s3[i] = 'K';
	}
	s3[0] = 255;
	SubString(&Sub,s3,247,8);
	PrintStr(Sub);
	



	return 0;
}

第九次笔记（数组，广义表）

数组：按一定格式排列起来的具有相同类型的数据元素的集合。

 

二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组。 

同理，推广到多维数组。若 n -1 维数组中的元素又是一个一维数组结构，则称作 n 维数组。 

声明格式：数据类型   变量名称[行数] [列数] ；

 

实现：一般都是采用顺序存储结构来表示数组。

 

二维数组两种顺序存储方式：以行序为主序 (低下标优先) 、以列序为主序 (高下标优先)

一个二维数组 A，行下标的范围是 1 到 6，列下标的范围是 0 到 7，每个数组元素用相邻的6 个字节存储，存储器按字节编址。那么，这个数组的体积是288个字节。

 

 广义表（又称列表 Lists）是n≥0个元素 a1, a2, …, an 的有限序列，其中每一个ai 或者是原子，或者是一个子表。

 

表头：若 LS 非空 (n≥1 )，则其第一个元素 a1 就是表头。

 表尾：除表头之外的其它元素组成的表。记作  tail(LS) = (a2, ..., an)。 

 

(( )) 长度为 1，表头、表尾均为 ( )

(a, (b, c))长度为 2，由原子 a 和子表 (b, c) 构成。表头为 a ；表尾为 ((b, c))。

 

广义表的长度定义为最外层所包含元素的个数

广义表的深度定义为该广义表展开后所含括号的重数。

“原子”的深度为 0 ;  “空表”的深度为 1 。

 

取表头运算 GetHead  和取表尾运算 GetTail

GetHead(LS) = a1        GetTail(LS) = (a2, …, an)。

 

广义表可看成是线性表的推广，线性表是广义表的特例。

 

广义表的结构相当灵活，在某种前提下，它可以兼容线 性表、数组、树和有向图等各种常用的数据结构。

由于广义表不仅集中了线性表、数组、树和有向图等常 见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。 

 

 

第十次笔记（树和二叉树）

树

 

树的定义：树(Tree)是 n(n≥0)个结点的有限集。若 n=0，称为空树；若 n > 0，则它满足如下两个条件：  

(1)  有且仅有一个特定的称为根 (Root) 的结点；  

(2)  其余结点可分为 m (m≥0) 个互不相交的有限集 T1, T2, T3, …, Tm， 其中每一个集合本身又是一棵树，并称为根的子树 (SubTree)。

显然，树的定义是一个递归的定义。

树的一些术语：

• 结点的度（Degree）：结点的子树个数；
• 树的度：树的所有结点中最大的度数；
• 叶结点（Leaf）：度为0的结点；
• 父结点（Parent）：有子树的结点是其子树的根节点的父结点；
• 子结点/孩子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；
• 兄弟结点（Sibling）：具有同一个父结点的各结点彼此是兄弟结点；
• 路径和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，...，nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度；
• 祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点；
• 子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙；
• 结点的层次（Level）：规定根结点在1层，其他任一结点的层数是其父结点的层数加1；
• 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度；

将树中节点的各子树看成从左至右是有次序的（即不能互换），则称为该树是有序树，否则称为无序树。

森林(forest)是 m (m≥0) 棵互不相交的树的集合。

 

二叉树

 

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

 

虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。

 

二叉树结点的子树要区分左子树和右子树，即使只有一 棵子树也要进行区分，说明它是左子树，还是右子树。树当 结点只有一个孩子时，就无须区分它是左还是右。

 

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

一些性质：

在二叉树的第 i 层上至多有  个结点 (i ≥1)。

证明：每个节点至多两个孩子，每一层至多比上一层多一倍的结点，根为1.

 

深度为 k 的二叉树至多有 个结点（k ≥1)。

证明：把每一层最大节点加起来即可

 

对任何一棵二叉树 T，如果其叶子数为 n0，度为 2的结点数为 n2，则 n0 = n2 + 1。

证明：对于一个只有根的树，n0 = n2 + 1成立。1=0+1

我们把一个叶子节点换成度为2的结点：

黑色节点原来为叶子节点

我们发现，度为2的结点数加1（黑色节点）；叶子节点数加1（原来的去掉，新增两个）；对于式子n0 = n2 + 1没影响，还是成立。

 

我们把叶子节点换成度为1的结点，比如没有右孩子。

我们发现，度为2的结点数没变。叶子节点数没变（减了一个加了一个）

所以，不管你怎么换，公式都成立。（佛系证明）

 

 

二叉树概述

 

各种实现和应用以后放链接

一、二叉树的基本概念

二叉树：二叉树是每个节点最多有两个子树的树结构。

根节点：一棵树最上面的节点称为根节点。

父节点、子节点：如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子 节点。

叶子节点：没有任何子节点的节点称为叶子节点。

兄弟节点：具有相同父节点的节点互称为兄弟节点。

节点度：节点拥有的子树数。上图中，13的度为2，46的度为1，28的度为0。

树的深度：从根节点开始（其深度为0）自顶向下逐层累加的。上图中，13的深度是1，30的深度是2，28的深度是3。

树的高度：从叶子节点开始（其高度为0）自底向上逐层累加的。54的高度是2，根节点23的高度是3。

对于树中相同深度的每个节点来说，它们的高度不一定相同，这取决于每个节点下面的叶子节点的深度。上图中，13和54的深度都是1，但是13的高度是1，54的高度是2。

二、二叉树的类型

类型	定义	图示
满二叉树 Full Binary Tree	除最后一层无任何子节点外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。满足下列性质： 1）一颗树深度为h，最大层数为k，深度与最大层数相同，k=h； 2）叶子节点数（最后一层）为2k−1； 3）第 i 层的节点数是：2i−1； 4）总节点数是：2k−1，且总节点数一定是奇数。
完全二叉树 Complete Binary Tree	若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。满足下列性质： 1）只允许最后一层有空缺结点且空缺在右边，即叶子节点只能在层次最大的两层上出现； 2）对任一节点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个； 3）除最后一层，第 i 层的节点数是：2i−1； 4）有n个节点的完全二叉树，其深度为：log2n+1或为log2n+1； 5）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
平衡二叉树 Balanced Binary Tree	又被称为AVL树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
二叉搜索树 Binary Search Tree	又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树： 1）若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值； 2）若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值； 3）左、右子树也分别为二叉排序树。
红黑树 Red Black Tree	是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质： 1）节点是红色或黑色； 2）根节点是黑色； 3）所有叶子节点都是黑色； 4）每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。) 5）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

 

 

 

 

 

 

 

 

 

啦啦啦

 

 

第十一次笔记（满二叉树，完全二叉树）

因为图片丢失，内容不全，我尽量找一下图

满二叉树 (Full binary tree)

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

国外(国际)定义:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.

大意为：如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立，因为完全二叉树也满足这个要求，但不是满二叉树)

从图形形态上看，满二叉树外观上是一个三角形。

这里缺失公式

完全二叉树

 

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则 ：

①n= n0+n1+n2 （其中n为完全二叉树的结点总数）；又因为一个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点，

②n= 1+n1+2*n2 ；由①、②两式把n2消去得：n= 2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。

简便来算，就是 n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。

 

重点：出于简便起见,完全二叉树通常采用数组而不是链表存储

 

对于tree[i]，有如下特点：

（1）若i为奇数且i>1，那么tree的左兄弟为tree[i-1]；

（2）若i为偶数且i<n，那么tree的右兄弟为tree[i+1]；

（3）若i>1，tree的父亲节点为tree[i div 2]；

（4）若2*i<=n，那么tree的左孩子为tree[2*i]；若2*i+1<=n，那么tree的右孩子为tree[2*i+1]；

（5）若i>n div 2,那么tree[i]为叶子结点（对应于（3））；

（6）若i<(n-1) div 2.那么tree[i]必有两个孩子（对应于（4））。

（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

完全二叉树第i层至多有2^（i-1）个节点，共i层的完全二叉树最多有2^i-1个节点。

特点：

1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；

2）对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个

 

第十二次笔记（二叉树的存储和遍历）

 

顺序存储结构

 

完全二叉树：用一组地址连续的 存储单元依次自上而下、自左至右存 储结点元素，即将编号为 i  的结点元 素存储在一维数组中下标为 i –1 的分量中。

一般二叉树：将其每个结点与完 全二叉树上的结点相对照，存储在一 维数组的相应分量中。

 

最坏情况：树退化为线性后：

我们要把它“变”成这个大家伙来存了：

深度为 k 的且只 有 k 个结点的右单支树需要 长度为2^k-1 的一维数组。 

 

链式存储结构

lchild和rchild都是指向相同结构的指针

在 n 个结点的二叉链表中有 n + 1 个空指针域。

typedef struct BiTNode { // 结点结构
    TElemType data;
    struct BiTNode *lchild,*rchild;// 左右孩子指针
} BiTNode, *BiTree;

可以多一条指向父的指针。

 

遍历二叉树

 

顺着某一条搜索路径巡访二叉树中的结点，使   得每个结点均被访问一次，而且仅被访问一次

 “访问”的含义很广，可以是对结点作各种处理， 如：输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构。

（所以有些题目比如morris遍历、链表后半段反转判断回文等等必须进行完，解题时就算已经得出答案也要遍历完，因为我们不能改变原来的数据结构。）

 

具体遍历的介绍

https://blog.csdn.net/hebtu666/article/details/82853988

 

深入理解二叉树遍历

二叉树：二叉树是每个节点最多有两个子树的树结构。

 

本文介绍二叉树的遍历相关知识。

我们学过的基本遍历方法，无非那么几个：前序，中序，后序，还有按层遍历等等。

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

首先我们定义一颗二叉树

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

前序

首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树

思路：

就是利用函数，先打印本个节点，然后对左右子树重复此过程即可。

void PreorderTraversal( BinTree BT )
{
    if(BT==NULL)return ;
    printf(" %c", BT->Data);
    PreorderTraversal(BT->Left);
    PreorderTraversal(BT->Right);
}

 

中序

首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树

思路：

还是利用函数，先对左边重复此过程，然后打印根，然后对右子树重复。

void InorderTraversal( BinTree BT )
{
    if(BT==NULL)return ;
    InorderTraversal(BT->Left);
    printf(" %c", BT->Data);
    InorderTraversal(BT->Right);
}

后序

首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根

思路：

先分别对左右子树重复此过程，然后打印根

void PostorderTraversal(BinTree BT)
{
    if(BT==NULL)return ;
    PostorderTraversal(BT->Left);
    PostorderTraversal(BT->Right);
    printf(" %c", BT->Data);
}

进一步思考

看似好像很容易地写出了三种遍历。。。。。

 

但是你真的理解为什么这么写吗？

比如前序遍历，我们真的是按照定义里所讲的，首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树。这种过程来遍历了一遍二叉树吗？

仔细想想，其实有一丝不对劲的。。。

再看代码：

void Traversal(BinTree BT)//遍历
{
//1111111111111
    Traversal(BT->Left);
//22222222222222
    Traversal(BT->Right);
//33333333333333
}

为了叙述清楚，我给三个位置编了号 1，2，3

我们凭什么能前序遍历，或者中序遍历，后序遍历？

我们看，前序中序后序遍历，实现的代码其实是类似的，都是上面这种格式，只是我们分别在位置1，2，3打印出了当前节点而已啊。我们凭什么认为，在1打印，就是前序，在2打印，就是中序，在3打印，就是后序呢？不管在位置1，2，3哪里操作，做什么操作，我们利用函数遍历树的顺序变过吗？当然没有啊。。。

都是三次返回到当前节点的过程：先到本个节点，也就是位置1，然后调用了其他函数，最后调用完了，我们开到了位置2。然后又调用别的函数，调用完了，我们来到了位置3.。然后，最后操作完了，这个函数才结束。代码里的三个位置，每个节点都被访问了三次。

而且不管位置1，2，3打印了没有，操作了没有，这个顺序是永远存在的，不会因为你在位置1打印了，顺序就改为前序，你在位置2打印了，顺序就成了中序。

 

为了有更直观的印象，我们做个试验：在位置1，2，3全都放入打印操作；

我们会发现，每个节点都被打印了三次。而把每个数第一次出现拿出来，就组成了前序遍历的序列；所有数字第二次出现拿出来，就组成了中序遍历的序列。。。。

 

其实，遍历是利用了一种数据结构：栈

而我们这种写法，只是通过函数，来让系统帮我们压了栈而已。为什么能实现遍历？为什么我们访问完了左子树，能返回到当前节点？这都是栈的功劳啊。我们把当前节点（对于函数就是当时的现场信息）存到了栈里，记录下来，后来才能把它拿了出来，能回到以前的节点。

 

想到这里，可能就有更深刻的理解了。

我们能否不用函数，不用系统帮我们压栈，而是自己做一个栈，来实现遍历呢？

先序实现思路：拿到一个节点的指针，先判断是否为空，不为空就先访问（打印）该结点，然后直接进栈，接着遍历左子树；为空则要从栈中弹出一个节点来，这个时候弹出的结点就是其父亲，然后访问其父亲的右子树，直到当前节点为空且栈为空时，结束。

核心思路代码实现：

*p=root;
while(p || !st.empty())
{
    if(p)//非空
    {
        //visit(p);进行操作
        st.push(p);//入栈
        p = p->lchild;左
    } 
    else//空
    {
        p = st.top();//取出
        st.pop();
        p = p->rchild;//右
    }
}

中序实现思路：和前序遍历一样，只不过在访问节点的时候顺序不一样，访问节点的时机是从栈中弹出元素时访问，如果从栈中弹出元素，就意味着当前节点父亲的左子树已经遍历完成，这时候访问父亲，就是中序遍历.

（对应递归是第二次遇到）

核心代码实现：

*p=root;
while(p || !st.empty())
{
    if(p)//非空
    {
        st.push(p);//压入
        p = p->lchild;
    }
    else//空
    {
        p = st.top();//取出
        //visit(p);操作
        st.pop();
        p = p->rchild;
    }
}

后序遍历是最难的。因为要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难点。

因为我们原来说了，后序是第三次遇到才进行操作的，所以我们很容易有这种和递归函数类似的思路：对于任一结点，将其入栈，然后沿其左子树一直往下走，一直走到没有左孩子的结点，此时该结点在栈顶，但是不能出栈访问， 因此右孩子还没访问。所以接下来按照相同的规则对其右子树进行相同的处理。访问完右孩子，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

第二种思路：对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，或者左孩子和右孩子都已被访问过了，就可以直接访问该结点。如果有孩子未访问，将P的右孩子和左孩子依次入栈。

网上的思路大多是第一种，所以我在这里给出第二种的大概实现吧

首先初始化cur，pre两个指针，代表访问的当前节点和之前访问的节点。把根放入，开始执行。

s.push(root);
while(!s.empty())
{
    cur=s.top();
    if((cur->lchild==NULL && cur->rchild==NULL)||(pre!=NULL && (pre==cur->lchild||pre==cur->rchild)))
    {
        //visit(cur);  如果当前结点没有孩子结点或者孩子节点都已被访问过 
        s.pop();//弹出
        pre=cur; //记录
    }
    else//分别放入右左孩子
    {
        if(cur->rchild!=NULL)
            s.push(cur->rchild);
        if(cur->lchild!=NULL)    
            s.push(cur->lchild);
    }
}

这两种方法，都是利用栈结构来实现的遍历，需要一定的栈空间，而其实存在一种时间O(N),空间O(1)的遍历方式，下次写了我再放链接。

 

斗个小机灵：后序是LRD，我们其实已经知道先序是DLR，那其实我们可以用先序来实现后序啊，我们只要先序的时候把左右子树换一下：DRL（这一步很好做到），然后倒过来不就是DRL了嘛。。。。。就把先序代码改的左右反过来，然后放栈里倒过来就好了，不需要上面介绍的那些复杂的方法。。。。

第十四次笔记（树的存储）

 

 

父节点表示法

 

数据域：存放结点本身信息。

双亲域：指示本结点的双亲结点在数组中的位置。

对应的树：

/* 树节点的定义 */
#define MAX_TREE_SIZE 100
 
typedef struct{
    TElemType data;
    int parent; /* 父节点位置域 */
} PTNode;
 
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int n; /* 节点数 */
} PTree;

特点：找双亲容易，找孩子难。

孩子表示法（树的链式存储结构）

 

childi指向一个结点

可以加上parent。

在有 n 个结点、度为  d 的树的 d 叉链表中，有  n×(d－1)＋1 个空链域

 

我们可以用degree记录有几个孩子，省掉空间，但是结点的指针个数不相等，为该结点的度 degree。

 

孩子链表：

 

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则 n 个结点有 n 个孩子链表（叶子的孩子链表为空表）。而 n 个头指针又组成一个线性表，用顺序表（含 n 个元素的结构数组）存储。

孩子兄弟表示法（二叉树表示法）

用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

typedef struct CSNode{
     ElemType data;
     struct CSNode *firstchild, *nextsibling;  
} CSNode, *CSTree;

第十五次笔记（图基础）

 

图是一种：   数据元素间存在多对多关系的数据结构   加上一组基本操作构成的抽象数据类型。

图 (Graph) 是一种复杂的非线性数据结构，由顶点集合及顶点间的关系（也称弧或边）集合组成。可以表示为： G＝(V, VR)  

其中 V 是顶点的有穷非空集合；

VR 是顶点之间   关系的有穷集合，也叫做弧或边集合。

弧是顶点的有序对，边是顶点的无序对。

 

特点：（相对于线性结构）

顶点之间的关系是任意的 

图中任意两个顶点之间都可能相关

顶点的前驱和后继个数无限制

 

相关概念：

 

顶点(Vertex)：图中的数据元素。线性表中我们把数据元素叫元素，树中将数据元素叫结点。

边：顶点之间的逻辑关系用边来表示，边集可以是空的。

 

无向边(Edge)：若顶点V1到V2之间的边没有方向，则称这条边为无向边。

无向图(Undirected graphs)：图中任意两个顶点之间的边都是无向边。（A,D）=（D,A）

无向图中边的取值范围：0≤e≤n(n-1)/2

有向边：若从顶点V1到V2的边有方向，则称这条边为有向边，也称弧(Arc)。用<V1,V2>表示，V1为狐尾(Tail)，V2为弧头(Head)。（V1，V2）≠（V2，V1）。

有向图(Directed graphs)：图中任意两个顶点之间的边都是有向边。

有向图中弧的取值范围：0≤e≤n(n-1)

   注意：无向边用“（）”，而有向边用“< >”表示。

 

简单图：图中不存在顶点到其自身的边，且同一条边不重复出现。

无向完全图：无向图中，任意两个顶点之间都存在边。

有向完全图：有向图中，任意两个顶点之间都存在方向互为相反的两条弧。

稀疏图：有很少条边。

稠密图：有很多条边。

 

邻接点：若 (v, v´) 是一条边，则称顶点 v 和 v´互为 邻接点，或称 v 和 v´相邻接；称边 (v, v´) 依附于顶点 v 和 v´，或称 (v, v´) 与顶点 v 和 v´ 相关联。

 

权（Weight）：与图的边或弧相关的数。

网（Network）：带权的图。

子图（Subgraph）：假设G=（V,{E}）和G‘=（V',{E'}），如果V'包含于V且E'包含于E，则称G'为G的子图。

 

 入度：有向图中以顶点 v 为头的弧的数目称为 v 的入度，记为：ID(v)。  

出度：有向图中以顶点 v 为尾的弧的数目称为 v 的出度，记为：OD(v)。

度（Degree）：无向图中，与顶点V相关联的边的数目。有向图中，入度表示指向自己的边的数目，出度表示指向其他边的数目，该顶点的度等于入度与出度的和。

 

回路（环）：第一个顶点和最后一个顶点相同的路径。

简单路径：序列中顶点（两端点除外）不重复出现的路径。 

简单回路（简单环）：前后两端点相同的简单路径。

路径的长度：一条路径上边或弧的数量。

 

连通：从顶点 v 到 v´ 有路径，则说 v  和 v´ 是连通的。

连通图：图中任意两个顶点都是连通的。

连通分量：无向图的极大连通子图（不存在包含它的 更大的连通子图）；

任何连通图的连通分量只有一个，即其本身；非连通图有多个连通分量（非连通图的每一个连通部分）。

强连通图： 任意两个顶点都连通的有向图。 

强连通分量：有向图的极大强连通子图；任何强连通 图的强连通分量只有一个，即其本身；非强连通图有多个 强连通分量。

 

生成树：所有顶点均由边连接在一起但不存在回路的图。（n个顶点n-1条边）

 

 

 

 

图的存储

 

多重链表：完全模拟图的样子，每个节点内的指针都指向该指向的节点。

节点结构内指针数为度

缺点：浪费空间、不容易操作

 

数组表示法（邻接矩阵表示法）

可用两个数组存储。其中一个 一维数组存储数据元素（顶点）的信息，另一个二维数组 （邻接矩阵）存储数据元素之间的关系（边或弧）的信息

有向图：

有向网：

缺点：用于稀疏图时空间浪费严重

优点：操作较容易

 

邻接表

指针数组存放每个结点，每个结点后接所有能到达的节点。

 

图的遍历

 

从图的任意指定顶点出发，依照某种规则去访问图中所有顶 点，且每个顶点仅被访问一次，这一过程叫做图的遍历。

图的遍历按照深度优先和广度优先规则去实施，通常有深度 优先遍历法（Depth_First Search——DFS ）和  广度优先遍历法 （ Breadth_Frist Search——BFS）两种。

简单棋盘搜索https://blog.csdn.net/hebtu666/article/details/81483407

别的实现以后再贴

如何判别V的邻接点是否被访问？

为每个顶点设立一个“访问标志”。

 

最小生成树

问题提出：
    要在n个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。
问题分析：
    答案只能从生成树中找，因为要做到任何两个城市之间有线路可达，通信网必须是连通的；但对长度最小的要求可以知道网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。
结论：
    希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 —— 最小代价生成树。
    构造最小生成树的算法很多，其中多数算法都利用了一种称之为 MST 的性质。
    MST 性质：设 N = (V, E)  是一个连通网，U是顶点集 V的一个非空子集。若边 (u, v) 是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u, v) 的最小生成树。

（1）普里姆 (Prim) 算法

算法思想： 
    ①设 N=(V, E)是连通网，TE是N上最小生成树中边的集合。
    ②初始令 U={u_0}, (u_0∈V), TE={ }。
    ③在所有u∈U，u∈U-V的边(u,v)∈E中，找一条代价最小的边(u_0,v_0 )。
    ④将(u_0,v_0 )并入集合TE，同时v_0并入U。
    ⑤重复上述操作直至U = V为止，则 T=(V,TE)为N的最小生成树。

 
代码实现：

void MiniSpanTree_PRIM(MGraph G,VertexType u)
    //用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。
    //记录从顶点集U到V-U的代价最小的边的辅助数组定义；
    //closedge[j].lowcost表示在集合U中顶点与第j个顶点对应最小权值
{
    int k, j, i;
    k = LocateVex(G,u);
    for (j = 0; j < G.vexnum; ++j)    //辅助数组的初始化
        if(j != k)
        {
            closedge[j].adjvex = u;
            closedge[j].lowcost = G.arcs[k][j].adj;    
//获取邻接矩阵第k行所有元素赋给closedge[j!= k].lowcost
        }
    closedge[k].lowcost = 0;        
//初始，U = {u};  
    PrintClosedge(closedge,G.vexnum);
    for (i = 1; i < G.vexnum; ++i)    \
//选择其余G.vexnum-1个顶点，因此i从1开始循环
    {
        k = minimum(G.vexnum,closedge);        
//求出最小生成树的下一个结点：第k顶点
        PrintMiniTree_PRIM(G, closedge, k);     //输出生成树的边
        closedge[k].lowcost = 0;                //第k顶点并入U集
        PrintClosedge(closedge,G.vexnum);
        for(j = 0;j < G.vexnum; ++j)
        {                                           
            if(G.arcs[k][j].adj < closedge[j].lowcost)    
//比较第k个顶点和第j个顶点权值是否小于closedge[j].lowcost
            {
                closedge[j].adjvex = G.vexs[k];//替换closedge[j]
                closedge[j].lowcost = G.arcs[k][j].adj;
                PrintClosedge(closedge,G.vexnum);
            }
        }
    }
}

（2）克鲁斯卡尔 (Kruskal) 算法

算法思想： 
    ①设连通网  N = (V, E )，令最小生成树初始状态为只有n个顶点而无边的非连通图，T=(V, { })，每个顶点自成一个连通分量。
    ②在 E 中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。
③依此类推，直至 T 中所有顶点都在同一连通分量上为止。
      
    最小生成树可能不惟一！

 

拓扑排序

（1）有向无环图

    无环的有向图，简称 DAG (Directed Acycline Graph) 图。
 
有向无环图在工程计划和管理方面的应用：除最简单的情况之外，几乎所有的工程都可分为若干个称作“活动”的子工程，并且这些子工程之间通常受着一定条件的约束，例如：其中某些子工程必须在另一些子工程完成之后才能开始。
对整个工程和系统，人们关心的是两方面的问题： 
①工程能否顺利进行； 
②完成整个工程所必须的最短时间。
对应到有向图即为进行拓扑排序和求关键路径。 
AOV网： 
    用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网(Activity On Vertex network)。
例如：排课表
      
AOV网的特点：
①若从i到j有一条有向路径，则i是j的前驱；j是i的后继。
②若< i , j >是网中有向边，则i是j的直接前驱；j是i的直接后继。
③AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。

问题：    
    问题：如何判别 AOV 网中是否存在回路？
    检测 AOV 网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

拓扑排序的方法：
    ①在有向图中选一个没有前驱的顶点且输出之。
    ②从图中删除该顶点和所有以它为尾的弧。
    ③重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。
        
    一个AOV网的拓扑序列不是唯一的！
代码实现：

Status TopologicalSort(ALGraph G)
    //有向图G采用邻接表存储结构。
    //若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR.
    //输出次序按照栈的后进先出原则，删除顶点，输出遍历
{
    SqStack S;
    int i, count;
    int *indegree1 = (int *)malloc(sizeof(int) * G.vexnum);
    int indegree[12] = {0};
    FindInDegree(G, indegree);    //求个顶点的入度下标从0开始
    InitStack(&S);
    PrintStack(S);
    for(i = 0; i < G.vexnum; ++i)
        if(!indegree[i])        //建0入度顶点栈S
            push(&S,i);        //入度为0者进栈
    count = 0;                //对输出顶点计数
    while (S.base != S.top)
    {
        ArcNode* p;
        pop(&S,&i);
        VisitFunc(G,i);//第i个输出栈顶元素对应的顶点，也就是最后进来的顶点    
        ++count;          //输出i号顶点并计数
        for(p = G.vertices[i].firstarc; p; p = p->nextarc)
        {    //通过循环遍历第i个顶点的表结点，将表结点中入度都减1
            int k = p->adjvex;    //对i号顶点的每个邻接点的入度减1
            if(!(--indegree[k]))
                push(&S,k);        //若入度减为0，则入栈
        }//for
    }//while
    if(count < G.vexnum)
    {
        printf("\n该有向图有回路!\n");
        return ERROR;    //该有向图有回路
    }
    else
    {
        printf("\n该有向图没有回路!\n");
        return OK;
    }
}

关键路径

    把工程计划表示为有向图，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。称这种有向图为边表示活动的网，简称为 AOE网 (Activity On Edge)。
例如：
设一个工程有11项活动，9个事件。
事件v_1——表示整个工程开始（源点） 
事件v_9——表示整个工程结束（汇点）

 
对AOE网，我们关心两个问题：  
①完成整项工程至少需要多少时间？ 
②哪些活动是影响工程进度的关键？
关键路径——路径长度最长的路径。
路径长度——路径上各活动持续时间之和。
v_i——表示事件v_i的最早发生时间。假设开始点是v_1，从v_1到〖v�i〗的最长路径长度。ⅇ(ⅈ)——表示活动a_i的最早发生时间。
l(ⅈ)——表示活动a_i最迟发生时间。在不推迟整个工程完成的前提下，活动a_i最迟必须开始进行的时间。
l(ⅈ)-ⅇ(ⅈ)意味着完成活动a_i的时间余量。
我们把l(ⅈ)=ⅇ(ⅈ)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程进度。
    例如上图中网，从从v_1到v_9的最长路径是(v_1,v_2,v_5,v_8,ν_9 )，路径长度是18，即ν_9的最迟发生时间是18。而活动a_6的最早开始时间是5，最迟开始时间是8，这意味着：如果a_6推迟3天或者延迟3天完成，都不会影响整个工程的完成。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。
    由上面介绍可知：辨别关键活动是要找l(ⅈ)=ⅇ(ⅈ)的活动。为了求ⅇ(ⅈ)和l(ⅈ)，首先应求得事件的最早发生时间vⅇ(j)和最迟发生时间vl(j)。如果活动a_i由弧〈j,k〉表示，其持续时间记为dut(〈j,k〉),则有如下关系：
ⅇ(ⅈ)= vⅇ(j)
l(ⅈ)=vl(k)-dut(〈j,k〉)
    求vⅇ(j)和vl(j)需分两步进行：
第一步：从vⅇ(0)=0开始向前递推
vⅇ(j)=Max{vⅇ(i)+dut(〈j,k〉)}   〈i,j〉∈T,j=1,2,…,n-1
其中，T是所有以第j个顶点为头的弧的集合。
第二步：从vl(n-1)=vⅇ(n-1)起向后递推
vl(i)=Min{vl(j)-dut(〈i,j〉)}  〈i,j〉∈S,i=n-2,…,0
其中，S是所有以第i个顶点为尾的弧的集合。
下面我们以上图AOE网为例，先求每个事件v_i的最早发生时间，再逆向求每个事件对应的最晚发生时间。再求每个活动的最早发生时间和最晚发生时间，如下面表格：
          
在活动的统计表中，活动的最早发生时间和最晚发生时间相等的，就是关键活动

关键路径的讨论：

①若网中有几条关键路径，则需加快同时在几条关键路径上的关键活动。      如：a11、a10、a8、a7。 
②如果一个活动处于所有的关键路径上，则提高这个活动的速度，就能缩短整个工程的完成时间。如：a1、a4。
③处于所有关键路径上的活动完成时间不能缩短太多，否则会使原关键路径变成非关键路径。这时必须重新寻找关键路径。如：a1由6天变成3天，就会改变关键路径。

关键路径算法实现：

int CriticalPath(ALGraph G)
{    //因为G是有向网，输出G的各项关键活动
    SqStack T;
    int i, j;    ArcNode* p;
    int k , dut;
    if(!TopologicalOrder(G,T))
        return 0;
    int vl[VexNum];
    for (i = 0; i < VexNum; i++)
        vl[i] = ve[VexNum - 1];        //初始化顶点事件的最迟发生时间
    while (T.base != T.top)            //按拓扑逆序求各顶点的vl值
    {
 
        for(pop(&T, &j), p = G.vertices[j].firstarc; p; p = p->nextarc)
        {
            k = p->adjvex;    dut = *(p->info);    //dut<j, k>
            if(vl[k] - dut < vl[j])
                vl[j] = vl[k] - dut;
        }//for
    }//while
    for(j = 0; j < G.vexnum; ++j)    //求ee,el和关键活动
    {
        for (p = G.vertices[j].firstarc; p; p = p->nextarc)
        {
            int ee, el;        char tag;
            k = p->adjvex;    dut = *(p->info);
            ee = ve[j];    el = vl[k] - dut;
            tag = (ee == el) ? '*' : ' ';
            PrintCriticalActivity(G,j,k,dut,ee,el,tag);
        }
    }
    return 1;
}

 

最短路 

最短路

    典型用途：交通网络的问题——从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？
 
    交通网络用有向网来表示：顶点——表示城市，弧——表示两个城市有路连通，弧上的权值——表示两城市之间的距离、交通费或途中所花费的时间等。
    如何能够使一个城市到另一个城市的运输时间最短或运费最省？这就是一个求两座城市间的最短路径问题。
    问题抽象：在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n - 1条边。
   常见最短路径问题：单源点最短路径、所有顶点间的最短路径
（1）如何求得单源点最短路径？
    穷举法：将源点到终点的所有路径都列出来，然后在其中选最短的一条。但是，当路径特别多时，特别麻烦；没有规律可循。
    迪杰斯特拉（Dijkstra）算法：按路径长度递增次序产生各顶点的最短路径。
路径长度最短的最短路径的特点：
    在此路径上，必定只含一条弧 <v_0, v_1>，且其权值最小。由此，只要在所有从源点出发的弧中查找权值最小者。
下一条路径长度次短的最短路径的特点：
①、直接从源点到v_2<v_0, v_2>（只含一条弧）；
②、从源点经过顶点v_1，再到达v_2<v_0, v_1>,<v_1, v_2>（由两条弧组成）
再下一条路径长度次短的最短路径的特点：
    有以下四种情况：
    ①、直接从源点到v_3<v_0, v_3>（由一条弧组成）；
    ②、从源点经过顶点v_1，再到达v_3<v_0, v_1>,<v_1, v_3>（由两条弧组成）；
    ③、从源点经过顶点v_2，再到达v_3<v_0, v_2>,<v_2, v_3>（由两条弧组成）；
    ④、从源点经过顶点v_1  ,v_2，再到达v_3<v_0, v_1>,<v_1, v_2>,<v_2, v_3>（由三条弧组成）；
其余最短路径的特点:    
    ①、直接从源点到v_i<v_0, v_i>（只含一条弧）；
    ②、从源点经过已求得的最短路径上的顶点，再到达v_i（含有多条弧）。
Dijkstra算法步骤：
    初始时令S={v_0},  T={其余顶点}。T中顶点对应的距离值用辅助数组D存放。
    D[i]初值：若<v_0, v_i>存在，则为其权值；否则为∞。 
    从T中选取一个其距离值最小的顶点v_j，加入S。对T中顶点的距离值进行修改：若加进v_j作中间顶点，从v_0到v_i的距离值比不加 vj 的路径要短，则修改此距离值。
    重复上述步骤，直到 S = V 为止。

算法实现：

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{ // 用Dijkstra算法求有向网 G 的 v0 顶点到其余顶点v的最短路径P[v]及带权长度D[v]。
    // 若P[v][w]为TRUE,则 w 是从 v0 到 v 当前求得最短路径上的顶点。  P是存放最短路径的矩阵，经过顶点变成TRUE
    // final[v]为TRUE当且仅当 v∈S,即已经求得从v0到v的最短路径。
    int v,w,i,j,min;
    Status final[MAX_VERTEX_NUM];
    for(v = 0 ;v < G.vexnum ;++v)
    {
        final[v] = FALSE;
        D[v] = G.arcs[v0][v].adj;        //将顶点数组中下标对应是 v0 和 v的距离给了D[v]
        for(w = 0;w < G.vexnum; ++w)
            P[v][w] = FALSE;            //设空路径
        if(D[v] < INFINITY)
        {
            P[v][v0] = TRUE;
            P[v][v] = TRUE;
        }
    }
    D[v0]=0;
    final[v0]= TRUE; /* 初始化,v0顶点属于S集 */
    for(i = 1;i < G.vexnum; ++i) /* 其余G.vexnum-1个顶点 */
    { /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */
        min = INFINITY; /* 当前所知离v0顶点的最近距离 */
        for(w = 0;w < G.vexnum; ++w)
            if(!final[w]) /* w顶点在V-S中 */
                if(D[w] < min)
                {
                    v = w;
                    min = D[w];
                } /* w顶点离v0顶点更近 */
                final[v] = TRUE; /* 离v0顶点最近的v加入S集 */
                for(w = 0;w < G.vexnum; ++w) /* 更新当前最短路径及距离 */
                {
                    if(!final[w] && min < INFINITY && G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w]))
                    { /* 修改D[w]和P[w],w∈V-S */
                        D[w] = min + G.arcs[v][w].adj;
                        for(j = 0;j < G.vexnum;++j)
                            P[w][j] = P[v][j];
                        P[w][w] = TRUE;
                    }
                }
    }
}

 

经典二分问题

经典二分问题：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  。

写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9。输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2。输出: -1
解释: 2 不存在 nums 中因此返回 -1

思路1：我们当然可以一个数一个数的遍历，但是毫无疑问要被大妈鄙视，这可怎么办呢？

思路2：二分查找
二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

如果目标值等于中间元素，则找到目标值。
如果目标值较小，证明目标值小于中间元素及右边的元素，继续在左侧搜索。
如果目标值较大，证明目标值大于中间元素及左边的元素，继续在右侧搜索。

算法代码描述：

初始化指针 left = 0, right = n - 1。
当 left <= right：
比较中间元素 nums[pivot] 和目标值 target 。
如果 target = nums[pivot]，返回 pivot。
如果 target < nums[pivot]，则在左侧继续搜索 right = pivot - 1。
如果 target > nums[pivot]，则在右侧继续搜索 left = pivot + 1。

算法实现：照例贴出三种语言的实现，在Java实现中给出了详细注释

class Solution {
  public int search(int[] nums, int target) {
	//分别准备好左右端点
    int left = 0, right = nums.length - 1;
	//循环二分
    while (left <= right) {
	//取中点
      int pivot = left + (right - left) / 2;
	  //找到答案并返回
      if (nums[pivot] == target) return pivot;
	  //向左继续找
      if (target < nums[pivot]) right = pivot - 1;
	  //向右继续找
      else left = pivot + 1;
    }
	//未找到，返回-1
    return -1;
  }
}

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot = left + (right - left) // 2
            if nums[pivot] == target:
                return pivot
            if target < nums[pivot]:
                right = pivot - 1
            else:
                left = pivot + 1
        return -1

class Solution {
  public:
  int search(vector<int>& nums, int target) {
    int pivot, left = 0, right = nums.size() - 1;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (nums[pivot] == target) return pivot;
      if (target < nums[pivot]) right = pivot - 1;
      else left = pivot + 1;
    }
    return -1;
  }
};

 

 

 

二叉搜索树实现

本文给出二叉搜索树介绍和实现

 

首先说它的性质：所有的节点都满足，左子树上所有的节点都比自己小，右边的都比自己大。

 

那这个结构有什么有用呢？

首先可以快速二分查找。还可以中序遍历得到升序序列，等等。。。

基本操作：

1、插入某个数值

2、查询是否包含某个数值

3、删除某个数值

 

根据实现不同，还可以实现其他很多种操作。

 

实现思路思路：

前两个操作很好想，就是不断比较，大了往左走，小了往右走。到空了插入，或者到空都没找到。

而删除稍微复杂一些，有下面这几种情况：

1、需要删除的节点没有左儿子，那就把右儿子提上去就好了。

2、需要删除的节点有左儿子，这个左儿子没有右儿子，那么就把左儿子提上去

3、以上都不满足，就把左儿子子孙中最大节点提上来。

 

当然，反过来也是成立的，比如右儿子子孙中最小的节点。

 

下面来叙述为什么可以这么做。

下图中A为待删除节点。

第一种情况：

 

1、去掉A，把c提上来，c也是小于x的没问题。

2、根据定义可知，x左边的所有点都小于它，把c提上来不影响规则。

 

第二种情况

 

3、B<A<C,所以B<C,根据刚才的叙述，B可以提上去，c可以放在b右边，不影响规则

4、同理

 

第三种情况

 

5、注意：是把黑色的提升上来，不是所谓的最右边的那个，因为当初向左拐了，他一定小。

因为黑色是最大，比B以及B所有的孩子都大，所以让B当左孩子没问题

而黑点小于A，也就小于c，所以可以让c当右孩子

大概证明就这样。。

下面我们用代码实现并通过注释理解

上次链表之类的用的c，循环来写的。这次就c++函数递归吧，不同方式练习。

定义

struct node
{
    int val;//数据
    node *lch,*rch;//左右孩子
};

插入

 node *insert(node *p,int x)
 {
     if(p==NULL)//直到空就创建节点
     {
         node *q=new node;
         q->val=x;
         q->lch=q->rch=NULL;
         return p;
     }
     if(x<p->val)p->lch=insert(p->lch,x);
     else p->lch=insert(p->rch,x);
     return p;//依次返回自己，让上一个函数执行。
 }

查找

 bool find(node *p,int x)
 {
     if(p==NULL)return false;
     else if(x==p->val)return true;
     else if(x<p->val)return find(p->lch,x);
     else return find(p->rch,x);
 }

删除

 node *remove(node *p,int x)
 {
      if(p==NULL)return NULL;
      else if(x<p->val)p->lch=remove(p->lch,x);
      else if(x>p->val)p->lch=remove(p->rch,x);
      //以下为找到了之后
      else if(p->lch==NULL)//情况1
      {
          node *q=p->rch;
          delete p;
          return q;
      }
      else if(p->lch->rch)//情况2
      {
          node *q=p->lch;
          q->rch=p->rch;
          delete p;
          return q;
      }
      else
      {
          node *q;
          for(q=p->lch;q->rch->rch!=NULL;q=q->rch);//找到最大节点的前一个
          node *r=q->rch;//最大节点
          q->rch=r->lch;//最大节点左孩子提到最大节点位置
          r->lch=p->lch;//调整黑点左孩子为B
          r->rch=p->rch;//调整黑点右孩子为c
          delete p;//删除
          return r;//返回给父
      }
      return p;
 }

 

对数组排序可以说是编程基础中的基础，本文对八种排序方法做简要介绍并用python实现。

代码中注释很全，适合复习和萌新学习。这是刚入学自己写的，可能难免比不上标准的写法，但是懒得改了。

文末会放和排序相关的基本拓展总结链接。

看不明白可以看群里视频

注意排序实现的具体方式，不要用局部变量，否则占空间太多，和空间复杂度不符。

好，我们开始。

• 选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在待排序序列的起始位置，直到全部待排序的数据元素排完。时间复杂度O(N^2)

for i in range(len(l)):#意义是第i个位置开始挑第i大（小）的元素
    for j in range(i,len(l)):#和其他待排序的元素比较
	if l[j]<l[i]:#更大就交换
	    l[j],l[i]=l[i],l[j]

• 冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换(一般进行n次即可，第n次一定会把第n小的元素放到正确位置）。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。时间复杂度O(N^2)

for i in range(len(l)-1):#下标和i无关，代表的只是第i次排序，最多需要len（l）-1次排序即可
    for j in range(len(l)-1):#遍历每一个元素
	if l[j]<l[j+1]:#本元素比下一个元素小，就交换
		l[j],l[j+1]=l[j+1],l[j]

 分析一下其实每次排序都会多一个元素已经确定了位置，不需要再次遍历。

所以j循环可以改成len(l)-i-1

时间复杂度没变。

 

• 插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

for i in range(1,len(l)):#意义是第i个元素开始插入i之前的序列（已经有序）
    for j in range(i,0,-1):#只要比它之前的元素小就交换
	if l[j]<l[j-1]:
	    l[j],l[j-1]=l[j-1],l[j]
	else:
            break#直到比前一个元素大

 

• 归并排序

速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列

试想：假设已经有两个有序数列，分别存放在两个数组s，r中，我们如何把他们有序的合并在一起？

归并排序就是在重复这样的过程，首先单个元素合并为含有两个元素的数组（有序），然后这种数组再和同类数组合并为四元素数组，以此类推，直到整个数组合并完毕。

def gg(l,ll):#合并函数
    a,b=0,0
    k=[]#用来合并的列表
    while a<len(l) and b<len(ll):#两边都非空
        if l[a]<ll[b]:
            k.append(l[a])
            a=a+1
        elif l[a]==ll[b]:a=a+1#实现去重
        else:
            k.append(ll[b])
            b=b+1
    k=k+l[a:]+ll[b:]#加上剩下的
    return k

def kk(p):#分到只剩一个元素就开始合并
    if len(p)<=1:
        return p
    a=kk(p[0:len(p)//2])#不止一个元素就切片
    b=kk(p[len(p)//2:])
    return gg(a,b)#返回排好序的一部分
l=list(map(int,input().split(" ")))
print(kk(l))

• 快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

• 随机化快排

快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。比如1 2 3 4 5，每次取第一个元素，就退化为了O(N^2)。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。

这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。

进一步提升可以分割为三部分，即小于区，等于区，大于区，减小了递归规模，并克服了多元素相同的退化。

def gg(a,b):
    global l
    if a>=b:#注意停止条件，我以前没加>卡了半小时
        return
    x,y=a,b
    import random#为了避免遇到基本有序序列退化，随机选点
    g=random.randint(a,b)
    l[g],l[y]=l[y],l[g]#交换选中元素和末尾元素
    while a<b:
        if l[a]>l[y]:#比目标元素大
            l[a],l[b-1]=l[b-1],l[a]#交换
            b=b-1#大于区扩大
            #注意：换过以后a不要加，因为新换过来的元素并没有判断过
        else:a=a+1#小于区扩大
    l[y],l[a]=l[a],l[y]#这时a=b
    #现在解释a和b：a的意义是小于区下一个元素
    #b是大于区的第一个元素
    gg(x,a-1)#左右分别递归
    gg(a+1,y)

l=list(map(int,input().split(" ")))
gg(0,len(l)-1)
print(l)

• 堆排序

堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1).

它是不稳定的排序方法。

主要思想：维持一个大根堆（根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆（Binary Heap），类似地可定义k叉堆。）

第一步：通过调整原地建立大根堆

第二步：每次交换堆顶和边界元素，并减枝，然后调整堆顶下沉到正确位置。

def down(i,k):#在表l里的第i元素调整，k为边界

#优先队列也是通过这种方式实现的
    global l
    while 2*i+2<k:#右孩子不越界
        lift,right=2*i+1,2*i+2
        m=max(l[i],l[lift],l[right])
        if m==l[i]:#不需要调
            break
        if m==l[lift]:#把最大的换上来
            l[i],l[lift]=l[lift],l[i]
            i=lift#目的节点下标更新
        else:#把最大的换上来
            l[i],l[right]=l[right],l[i]
            i=right#目的节点下标更新
    if 2*i+1<k:#判断左孩子
        if l[2*i+1]>l[i]:
            l[i],l[2*i+1]=l[2*i+1],l[i]

def main():
    global l
    for j in range(1,len(l)+1):#调大根堆
        i=len(l)-j
        down(i,len(l))
    for i in range(len(l)-1,-1,-1):#排序
        l[i],l[0]=l[0],l[i]#最大和边界交换，剪枝
        down(0,i)
    print(l)
    
l=list(map(int,input().split(" ")))
main()

        
    

        

• 桶排序

桶排序不是基于比较的排序方法，只需对号入座。将相应的数字放进相应编号的桶即可。

当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间o（n）

对于海量有范围数据十分适合，比如全国高考成绩排序，公司年龄排序等等。

l=list(map(int,input().split(" ")))
n=max(l)-min(l)
p=[0]*(n+1)#为了省空间
for i in l:
    p[i-min(l)]=1#去重排序，做标记即可
for i in range(n):
    if p[i]==1:#判断是否出现过
        print(i+min(l),end=" ")

• 希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

通过缩小有序步长来实现。

 

def shell(arr):
 n=len(arr)#初始化步长
 h=1
 while h<n/3:
  h=3*h+1
 while h>=1:#判断，退出后就有序了。
  for i in range(h,n):
   j=i
   while j>=h and arr[j]<arr[j-h]:#判断是否交换
    arr[j], arr[j-h] = arr[j-h], arr[j]
    j-=h
  h=h//3#逐渐缩小步长
 print arr

稳定性及时间复杂度

排序稳定性概念：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

时间复杂度：时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。可以理解为和常数操作所成的一种关系（常数操作为O(1))

空间复杂度类似。

下面给出各类排序的对比图：

 

 

 

• 基数排序

因为桶排序是稳定的，基数排序就是很多次桶排序而已，按位进行桶排序即可。

（个人认为桶排序名字不恰当，因为桶是先进后出，和稳定的算法正好反了，）

 

 

 

 

总：

比较排序和非比较排序

      常见的排序算法都是比较排序，非比较排序包括计数排序、桶排序和基数排序，非比较排序对数据有要求，因为数据本身包含了定位特征，所有才能不通过比较来确定元素的位置。

      比较排序的时间复杂度通常为O(n2)或者O(nlogn)，比较排序的时间复杂度下界就是O(nlogn)，而非比较排序的时间复杂度可以达到O(n)，但是都需要额外的空间开销。

• 若n较小（数据规模较小），插入排序或选择排序较好
• 若数据初始状态基本有序（正序），插入、冒泡或随机快速排序为宜
• 若n较大，则采用时间复杂度为O(nlogn)的排序方法：快速排序或堆排序
• 快速排序是目前基于比较的排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
• 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。