-
2021-08-30 16:58:20
什么是PG流复制?
Streaming Replication是pg9.0开始提供的传递WAL日志的方式,只要primary库一产生日志,就会立马传递到standby库。
在pg9.0之前,pg只能一个个传送wal日志(log shipping),备库至少比主库落后一个wal日志
pg流复制进程
wal sender:wal sender存在于主库。wal sender进程将主库最新LSN到备库最新的LSN之间的wal 传递给备库
wal receiver:wal receiver存在于备库。wal receiver进程将备库最新的LSN号传递给主库。wal receiver接收wal sender传递过来的WAL数据并写入WAL日志
startup:备库实例恢复进程。将wal日志在备库上重放pg 16776 14632 0 13:33 ? 00:00:00 postgres: wal sender process lzl 172.17.100.150(13338) streaming 0/3002D30 pg 16775 15329 0 13:33 ? 00:00:00 postgres: wal receiver process streaming 0/3002D30 pg 15330 15329 0 10:26 ? 00:00:00 postgres: startup process recovering 000000010000000000000003
pg流复制原理
pg流复制主要分为2个阶段,实例恢复阶段和主备同步阶段。
实例恢复阶段:当pg库异常宕机后,数据库启动时,pg会重放宕机前的最后一个checkpoint之后的所有WAL日志(这跟oracle、mysql等关系型数据库实例恢复是同样的原理,目的就是把数据库置为一致性状态)。pg备库在搭建时,一般主库都是不停机的,此时备份主库出来的备份库处于不一致状态,在备库启动时statup进程将进行实例恢复操作
主备同步阶段:wal receiver进程将备库最新的LSN号传递给主库,wal sender将主库最新LSN到备库最新的LSN之间的wal 传递给wal receiver,wal receiver接收WAL并将WAL写入到磁盘上,startup进程根据磁盘上的WAL日志在备库上重放同步和异步
pg主从有5种模式,由synchronous_commit 参数控制。synchronous_commit 参数的本质就是控制主库什么时候提交。
remote_apply:所有备库上均已应用完WAL时,主库提交。所以这个模式是同步模式,主从是一致的,主库上能查到的数据备库上一定也可以查到,这种模式下主备没有延时,但对主库提交时间有影响,因为主库commit需要等待网络传输和备库应用时间
synchronous_commit的含义分2种情况,有从库和无从库时(synchronous_standby_name空或非空时)当synchronous_standby_name为非空时:
remote_apply:从库已应用了wal,主库才可以提交。这种模式主从是同步的
on:default。主从的wal都写到磁盘上时,主库提交。类似半同步,不会丢数据。
remote_write:备库接收到wal并将wal日志写到文件系统cache上时,主库提交。此时从库的接收到wal但是还没有落盘,如果操作系统crash,会丢失数据。
local:主库wal刷到磁盘时提交。这种模式是异步的,主库不需要确认备库状态就可以提交。
off:本机wal没有刷到磁盘就可以提交,存在数据丢失风险,不推荐。当synchronous_standby_name为空时:
(当synchronous_standby_name为空时,synchronous_commit只有on和off有效,如果是remote_apply, remote_write and local ,那么仍然被认为是on)
on:default。数据库wal写到磁盘上,事务才可以提交
off:本机wal没有刷到磁盘就可以提交,存在数据丢失风险,不推荐。主从同步关系
主从可靠性
Failover
当主库crush时,备库就需要启动failover,此时备库就成为新主库。pg没有提供可以识别failure的方法,但是pg提供了激活主库的方法。(一般三方工具会调用pg激活方法,而主备监控、主库宕机判断、连接切换等等,都不是pg本身来做)
pg提供了2种方法将备库激活为主库:trigger_file文件和pg_ctl promote命令。(pg 12以后trigger_file变成promote_trigger_file)
trigger_file和pg_ctl promote在激活时都是一条命令就可以完成激活备库的任务,区别在于trigger_file需要在recover_file提前写好trigger_file配置
使用trigger_file做主备切换(pg_ctl promote同样的效果,比较简单):
1.备库recovery.conf中配置trigger_file
2.关闭主库
3.touch trigger_file,将老备库启动为新主库
4.配置recovery.conf,将老主库启动为新备库
5.观察新老主备库failover示例:
环境:
主库 172.17.100.150 5432
备库 172.17.100.150 54331.备库recovery.conf中配置trigger_file
$ cat recovery.conf|grep trigger
trigger_file = ‘/pg/pg96data_sla/trigger.kenyon’
$ ll /pg/pg96data_sla/trigger.kenyon
ls: cannot access /pg/pg96data_sla/trigger.kenyon: No such file or directory
在recovery.conf中配置trigger文件路径就可以了,配置后不会出现trigger文件备库postgres.conf添加配置
max_wal_senders = 6 #max_wal_senders是sender进程的最大数量,默认是0,所以切换前备库必须配置
hot_standby=on #备库打开查询功能2.关闭主库
$ pg_ctl stop -D /pg/pg96data_pri -m fast
waiting for server to shut down… done
server stopped(判断主库WAL是否全部被备库应用:pg9.6- cd pg_xlog;pg 10+ cd pg_wal)
ls -ltr|tail -n 1 |awk ‘{print $NF}’|while read xlog;do pg_xlogdump $xlog;done
观察备库wal中有关键词shutdown)3.touch激活备库(或者 pg_ctl promote -D /pg/pg96data_sla
$ touch /pg/pg96data_sla/trigger.kenyon
此时recovery.conf变成recovery.done4.主库设置为备库
配置新备库recovery.conf文件,可以直接cp老备库的过来,修改IP和目录
vi $新备库/recover.conf
standby_mode = on
primary_conninfo = ‘host=172.17.100.150 port=5433 user=lzl password=lzl’
recovery_target_timeline = ‘latest’配置postgres.conf,将hot_standby = on写入conf,表示备库开启查询
vi $新备库/postgres.conf
hot_standby = on启动新备库
/pg/pg96/bin/pg_ctl -D /pg/pg96data_pri -l /pg/pg96data_pri/server.log start5.检查主备库
postgres=# \x
Expanded display is on.
postgres=# select * from pg_stat_replication ;
-[ RECORD 1 ]----±-----------------------------
pid | 24766
usesysid | 16384
usename | lzl
application_name | walreceiver
client_addr | 172.17.100.150
client_hostname |
client_port | 47345
backend_start | 2021-07-30 07:44:05.582546+00
backend_xmin |
state | streaming
sent_location | 0/4033790
write_location | 0/4033790
flush_location | 0/4033790
replay_location | 0/4033790
sync_priority | 0
sync_state | asyncpg_basebackup
pg_basebackup是pg自带的备份工具,它用来做pg的基础备份。pg_basebackup可以用作PITR,也可以用来构造log-shipping standby和stream standby。它是pg的物理备份工具。
https://liuzhilong.blog.csdn.net/article/details/119533506pg_rewind
pg_rewind可以用作pg主从的维护工具。当2个pg实例时间线(timeline)出现分叉时,pg_rewind可以做实例间的同步。(比如主库运行的情况下,备库failover后运行了一段时间,此时主备的时间线就出现了分叉)
https://liuzhilong.blog.csdn.net/article/details/119250794Replication Slots
什么是pg复制槽?
主从架构下,如果从库还没有收到wal日志,主库就把wal删除了,这样的lag就不能自动恢复。复制槽就是为了确保主库不会把那些还没有被传到从库的WAL日志给删除。
在没有使用复制槽的情况下,可能需要用 wal_keep_size/wal_keep_segment和 archive_command去确保wal日志不被删除,但这种方式总会保留过多的wal,且在延时较大时也不能保证wal一定不会被删除。所以复制槽就是为此而生。
但是复制槽可能会导致主库一直不删除wal(比如从库已宕机的情况)导致磁盘被撑满,这时就需要max_slot_wal_keep_size来设置wal文件的保留上限。复制槽参数:
max_slot_wal_keep_size:在有复制槽时,该参数定义pg_wal目录下wal文件的最大大小。默认值为-1,表示主库为从库保留wal文件的大小没有上限。
wal_keep_segments/wal_keep_size:pg12及以下为wal_keep_segments,pg13及以上为wal_keep_size。保证pg_wal下的wal文件不会被删除。在没有复制槽的情况下,wal文件超过该大小就可能被删除,可能导致从库不可追日志。如果调整的过大,可能导致目录被撑的很大。该参数默认为0,也就是不保留WAL文件。如果wal被删除,可能会出现如下报错
ERROR: requested WAL segment xxxx has already been removed
这时从库只能期待有归档,否则只要重搭。
primary_slot_name:设置slot的名字,表示pg主从开启复制槽。所以开启pg复制槽至少有类似下面的配置
primary_conninfo = ‘host=172.17.100.150 port=5433 user=lzl password=lzl’
primary_slot_name = ‘pg_slot_lzl’
max_replication_slots:复制槽的最大个数,重启生效。如果使用的复制槽不足,从库将启动失败。应将该值设置的较大。在pg9.6版本以下,默认值为0,pg10以上为10。创建pg复制槽
1.设置主库max_replication_slots参数
主库:(我的pg版本为9.6)
max_replication_slots=10
加入postgres.conf,并重启主库
2.创建复制槽
创建复制槽:
postgres=# SELECT * FROM pg_create_physical_replication_slot(‘pg_slot_lzl’);
slot_name | xlog_position
-------------±--------------
pg_slot_lzl |
查看复制槽
postgres=# SELECT slot_name, slot_type, active FROM pg_replication_slots;
slot_name | slot_type | active
-------------±----------±-------
pg_slot_lzl | physical | f3.设置从库primary_slot_name参数
primary_slot_name = ‘pg_slot_lzl’
加入recovery.conf,并重启从库4.查看复制槽
postgres=# select *,pg_xlogfile_name(restart_lsn)as current_xxlog from pg_replication_slots;
slot_name | plugin | slot_type | datoid | database | active | active_pid | xmin | catalog_xmin | restart_lsn | confirmed_flush_lsn | current_xxlog
-------------±-------±----------±-------±---------±-------±-----------±-----±-------------±------------±--------------------±-------------------------
pg_slot_lzl | | physical | | | t | 12802 | | | 0/A002340 | | 00000002000000000000000A
–pg_xlogfile_name(restart_lsn)查看当前wal日志信息查询冲突
什么是查询冲突?
备库在查询时可能会遇到如下错误
ERROR:canceling statement due to confilct with recovery。
为什么会产生冲突呢?我们细想一下,比如说备库正在执行基于某个表的查询(这个查询可能是应用产生的,也可能是手动连接进行的查询),这时主库执行了drop table操作,该操作写入wal日志后传至备库进行应用,为了保证数据一致性,postgresql必然会迅速回放数据,这时drop table和select就会形成冲突。如下图所示:
冲突场景:
上面只介绍了1种查询冲突的情况。总结一下有以下几种情况
1.主库排他锁(包括显示LOCK命令和各种DDL)
2.主库vacuum清理死元组,从库如果正在使用该元组,就会产生冲突
3.主库删除了从库查询正在使用的表空间
4.主库删除了从库正在使用的数据库
试想在仅有主库的情况下:
场景1:一个会话发起了drop table,此时发现有select语句正在执行,那么该会话只能等待select完成其事务。
场景2:一个会话发起vacuum或后台自动vacuum,不会与当前库查询发生冲突,因为vacuum不会清理正在使用的元组。从库的处理就不同。因为主库不知道从库的事务状态,而从库又需要与主库保持一致,所以才发生了“查询冲突”
查询冲突参数
hot_standby_feedback:
这个参数是查询冲突这个话题中提到最多的参数,下面我们详细探讨一下。我们假设在没有备库的情况下,会话1查询某行数据,会话2删除该数据,然后commit,此时会话2执行一次vacuum,我们知道这次vacuum并不会删除该行数据,因为会话1的事务还需要使用该元组,所以不会清理该元组。那么如果是主从呢?主库在准备进行vacuum时怎么知道从库还在进行查询,这就是设置该参数的意义,设置hot_standby_feedback参数之后备库会定期向主库通知最小活跃事务id(xmin)值,这样使得主库vacuum进程不会清理大于xmin值的事务。
这个参数有利于减少冲突的发生,但并不能完全避免冲突,其实细想一下,这个参数只是减少了由于主库vacuum死亡元组造成的冲突,并不能解决排他锁造成的冲突。或者由于网络中断造成的冲突,假如主备之间的网络中断后,备库就无法向主库正常发送xmin值,如果时间够长,主库在这段时间内还是会清理无用元组,这样网络恢复后就可能发生上面的vacuum造成的冲突。
值得注意的是hot_standby_feedback参数并不会覆盖主库上old_snapshot_threshold参数限定的值,old_snapshot_threshold参数限制了死亡元组的无限膨胀,当事务信息超过old_snapshot_threshold的限制时,依然会进行清理。max_standby_streaming_delay:
备机因为接收wal流日志产生查询冲突而取消查询之前的等待时间,设置该参数会在发生冲突时,备库查询不会立即取消,而是等待一个时间后如果还没结束再抛出报错。这个值的大小可以参考备库可能产生的长事务运行时间。max_standby_archive_delay:
备机因为处理归档的wal日志产生查询冲突而取消查询之前的等待时间,和上面的参数类似。vacuum_defer_cleanup_age:
指定vacuum延迟清理死亡元组的事务数,vacuum会延迟清除无效的记录,延迟的事务个数通过vacuum_defer_cleanup_age进行设置。即vacuum和vacuum full操作不会立即清理刚刚被删除元组可以根据pg_stat_database和pg_stat_database_conflicts视图查看冲突发生的情况
其他相关参数
传输参数
max_wal_senders:使用wal sender获取wal的服务最大个数,也就是从库+baseback客户端的最大个数。pg9.6默认为0,pg10以后默认为10。
wal_send_timeout:wal传输xx秒失败后中断复制。该参数在从库宕机或者网络长期中断时,wal不会再尝试传输。默认60。0表示永
不中断复制
track_commit_timestamp:记录事务的时间。默认是off。主库参数
synchronous_standby_names:
在主库上配置,备机的复制列表。有下面几种方式(s1,s2,s3代表备机的application_name,配置在recovery.conf中)
synchronous_standby_names=‘s1’ 代表s1备机返回就可以提交。
synchronous_standby_names=‘FIRST 2 (s1,s2,s3)’ 代表s1,s2,s3三个备机中前两个s1和s2返回主库就可以提交。
synchronous_standby_names=‘ANY 2 (s1,s2,s3)’ 代表s1,s2,s3三个备机中任意两个备机返回主库就可以提交。
synchronous_standby_names=’*’ 代表匹配任意主机,也就是任意主机返回就可以提交。
wal_level:
wal日志级别,这个参数决定了有多少信息写入wal日志,默认是replica,这种模式支持复制和wal归档,同时支持备库只读查询。
minimal:除了实例crash恢复需要的记录,其他不记录,比如CREATE TABLE AS,CREATE INDEX,CLUSTER,COPY可以跳过,该模式记录的日志信息不足以支持wal归档和流复制。
logic:在replica的基础上增加一些信息以支持逻辑解码,该模式会增大wal日志的数量,尤其是大量的update,delete操作的库。
在9.6之前还有archive和hot_standby模式,映射到现在的replica模式。
synchronous_commit:
前面已讲过,5种模式,各有优劣。
archive_mode :archive_mode =on表示打开归档
archive_command:归档命令,pg归档直接调用操作系统命令。可以是简单cp命令到备份端
listen_addresses:监听地址。’'表示所有IP都监听,默认为local从库参数
hot_standby:on表示打开从库只读
primary_conninfo:从库连接主库的连接串。如primary_conninfo = ‘host=172.17.100.150 port=5432 user=lzl password=lzl’
trigger_file/promote_trigger_file:激活备库的激活文件。pg 12以前叫trigger_file,pg12及以后为promote_trigger_file
trigger_file和pg_ctl promote在激活时都是一条命令就可以完成激活备库,前面已经具体演示过
wal_receiver_create_temp_slot:当没有slot时,临时起一个slot(命为primary_slot_name)。默认是off的。参考文档:
《PostgreSQL修炼之道》
https://www.postgresql.org/docs/current/warm-standby.html
https://www.postgresql.org/docs/13/high-availability.html
https://www.postgresql.org/docs/current/runtime-config-replication.html
https://www.postgresql.org/docs/13/runtime-config-wal.html
https://www.postgresql.org/docs/current/app-pgbasebackup.html
https://www.postgresql.org/docs/current/hot-standby.html#HOT-STANDBY-CONFLICT
https://cloud.tencent.com/developer/article/1555354
https://www.modb.pro/db/29737
https://wiki.postgresql.org/wiki/Streaming_Replication
https://www.percona.com/blog/2018/09/07/setting-up-streaming-replication-postgresql/
https://www.cybertec-postgresql.com/en/the-synchronous_commit-parameter/
https://blog.csdn.net/m15217321304/article/details/88850146
https://blog.51cto.com/lishiyan/2460518?source=dra更多相关内容 -
Redis为什么这么快?
2022-01-03 22:01:15Redis为什么这么快? 本文 GitHub https://github.com/JavaFamily 已收录,有一线大厂面试完整考点、资料以及我的系列文章。 前言 说起当前主流NoSql数据库非 Redis 莫属。因为它读写速度极快,一般用于缓存热点数据...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。
-
Elasticsearch 主从同步之跨集群复制
2021-12-01 00:18:231、什么是跨集群复制?跨集群复制(Cross-cluster replication,简称:CCR)指的是:索引数据从一个 Elasticsearch 集群复制到另一个 Elasticse...1、什么是跨集群复制?
跨集群复制(Cross-cluster replication,简称:CCR)指的是:索引数据从一个 Elasticsearch 集群复制到另一个 Elasticsearch 集群。
对于主集群的索引数据的任何修改都会直接复制同步到从索引集群。
2、跨集群复制最早发布版本
Elasticsearch 6.7 版本。
3、跨集群复制的好处?
3.1 支持灾难恢复(DR)、确保高可用性(HA)
跨集群复制确保了不间断的服务可用性,能够承受住数据中心或区域服务中断的影响,降低了复杂性、节省了成本。
3.2 降低延迟
将数据复制到更靠近应用程序用户的集群可以最大限度地减少查询延迟。
3.3 水平可扩展性
跨多个副本集群拆分查询繁重的工作负载可提高应用程序可用性。
3.4 集中式汇报
企业客户可以将属于不同业务线的较小集群(数百个分支银行中心)中的报告不断汇总到一个中央集群(大型全球银行)中,以用于整合报告、方便可视化呈现。
PS:关于高可用,读者可能会有疑惑?
● 副本的目的是高可用,集群的快照和恢复和功能是高可用,怎么又来个跨集群复制呢?
副本主要体现在分片层面,可以看做分片的复制,一般集群至少设置一个副本,当主副本故障时,副本分片会提升为主分片。
● 快照和恢复主要体现在:集群级别和索引层面,可以全量或者增量。但,做不到实时备份和恢复。也就是说,快照会设定一个时间间隔,比如每 5 分钟备份一次。
当集群出现故障需要恢复时,极有可能会少备份最近 5 分钟的数据,
综上,才会有了跨集群复制的概念。
4、跨集群复制的核心概念
图片来源:opster.com
跨集群复制使用主动-被动模型(active-passive model)。
数据索引到一个领导者索引(leader index),并且数据被复制到一个或多个只读跟随者索引(read-only follower indices)。在向集群添加跟随者索引之前,必须配置包含领导者索引的远程集群。
leader-follower 模式在 kafka、zookeeper等中都有涉及,我认为翻译为:主、从模型比较契合。
核心释义解读如下:
active-passive model:主动-被动模型。
leader index:主索引或领导者索引。
read-only follower indices:从索引或跟随者索引。
5、跨集群复制的设计原则
5.1 高安全性
跨集群复制应该为所有数据流和 API 提供强大的安全控制。
5.2 准确性
跟随者索引和领导者索引的预期内容之间必须没有差异。
5.3 高性能
复制不应影响领导集群的索引率(数据写入速率)。
5.4 最终一致性
领导者和跟随者集群之间的复制延迟应该在几秒钟之内。
5.5 资源使用率低
复制应该使用最少的资源。
6、跨集群复制的实战一把
6.1 必备前置条件
6.1.1 前置条件1:激活License
CCR 是白金版付费功能,需要激活 30 天的 License,如果仅学习了解功能,建议先试用。
6.1.2 前置条件2:备好至少 2 个集群
跨集群复制,核心是“跨”和“复制”。
“跨”体现在至少得两个集群,否则没有意义。
最简单模型如图所示,我们用一台宿主机搭建两套集群环境,如下所示:
图片来自:elastic官方文档
● 集群A:远端集群,remote cluster leader
Elasticsearch: 172.21.0.14:19203
kibana:172.21.0.14:5613● 集群B:本地集群,local cluster follower
Elasticsearch: 172.21.0.14:19202
kibana:172.21.0.14:56126.1.3前置配置:开启软删除
7.0+之后版本已默认开启,无需单独配置。
早期版本,需参考官方文档进行静态配置,需要修改配置文件实现。
index.soft_deletes.enabled:true
跨集群复制的工作原理是:重放对 leader 索引分片执行的单个写入操作的历史记录。
Elasticsearch 需要在 leader 分片上保留这些操作的历史记录,以便它们可以被 follower 分片任务拉取。用于保留这些操作的底层机制是软删除。
6.1.4 前置配置:xpack 设置true
因为需要配置角色、权限等,Elasitcsearch 设置了xpack,就意味着 kibana 端需要设置账号、密码。
在 elasticsearch.yml 文件中添加如下配置。
xpack.security.enabled: true
通过:./elasticsearch-setup-passwords 命令行工具实现用户名和密码的设置。
auto 自动设置的结果参考如下:
Changed password for user apm_system PASSWORD apm_system = m5ob2a8OvoKuYpPPsiRd Changed password for user kibana_system PASSWORD kibana_system = xwdrhpVPSsbxxY1l0b50 Changed password for user kibana PASSWORD kibana = xwdrhpVPSsbxxY1l0b50 Changed password for user logstash_system PASSWORD logstash_system = 1zweZhAVEnqwh1flHBkz Changed password for user beats_system PASSWORD beats_system = 7Fo3bvmLISshjvHXTqAY Changed password for user remote_monitoring_user PASSWORD remote_monitoring_user = EvB4FkFs88gsCP073YGt Changed password for user elastic PASSWORD elastic = c7KmLqGTm6cyl2ABJPBY
否则会报错如下:
{ "error" : { "root_cause" : [ { "type" : "exception", "reason" : "Security must be explicitly enabled when using a [trial] license. Enable security by setting [xpack.security.enabled] to [true] in the elasticsearch.yml file and restart the node." } ], "type" : "exception", "reason" : "Security must be explicitly enabled when using a [trial] license. Enable security by setting [xpack.security.enabled] to [true] in the elasticsearch.yml file and restart the node." }, "status" : 500 }
6.2 跨集群复制完整设置步骤
6.2.1 步骤1:从集群设置 remote cluster
在从集群上配置包含主索引的远程集群(remote cluster)
其实看到:remote cluster,第一时间要想到:跨集群检索(CCR)也需要配置它。
从集群配置主集群 leader,参考如下:
PUT /_cluster/settings { "persistent": { "cluster": { "remote": { "leader": { "seeds": [ "172.21.0.14:19303" ] } } } } }
从集群监测一下remote配置是否成功。
GET /_remote/info
检测是否配置成功。
6.2.2 步骤2:配置权限
为跨集群复制配置权限。
跨集群复制用户在远程集群和本地集群上需要不同的集群和索引权限。
使用以下请求在本地和远程集群上创建单独的角色,然后创建具有所需角色的用户。
6.2.2.1 remote 集群配置权限
前置条件:设置 xpack 为 true,kibana 端配置账号和密码。
POST /_security/role/remote-replication { "cluster": [ "read_ccr" ], "indices": [ { "names": [ "kibana_sample_data_logs" ], "privileges": [ "monitor", "read" ] } ] }
6.2.2.2 local 集群配置权限
在本地集群上创建从索引。
POST /_security/role/remote-replication { "cluster": [ "manage_ccr" ], "indices": [ { "names": [ "kibana_sample_data_logs_follower" ], "privileges": [ "monitor", "read", "write", "manage_follow_index" ] } ] }
6.2.3 步骤3:创建自动跟踪模式以自动跟踪在远程集群中创建的索引
可以使用 Kibana 图形化界面配置或者命令行配置。
位置:Stack Management->Data->Cross-Cluster Replication。
步骤1:创建 follower index。
步骤2:配置 follower index。
需要设置如下:
Remote cluster, 从集群对leader 的设置。
Leader index,主集群的索引。
Follower index,从集群的索引名称,与 Leader index 是一一对应的关系,是从 Leader 索引复制过来的数据。
执行成功后截图如下:
检查是否成功:
GET /kibana_sample_data_logs_from_leader/_ccr/stats
以上,跨集群同步设置成功之后,可以进一步做很多验证。
比如:主集群 leader 索引删除两条数据,从集群查看结果。对比发现,从集群也会跟着变化,这说明了跨集群复制已生效。
更多权限设置,推荐阅读:https://www.elastic.co/guide/en/elasticsearch/reference/current/security-privileges.html
7、跨集群复制常用命令清单
包含但不限于:检查复制进度、暂停和恢复复制、重新创建跟随者索引和终止复制。
7.1 检查复制进度
GET /kibana_sample_data_logs_from_leader/_ccr/stats
7.2 暂停和恢复复制
POST kibana_sample_data_logs_from_leader/_ccr/pause_follow POST kibana_sample_data_logs_from_leader/_ccr/resume_follow { }
7.3 重新创建跟随者索引
分三步骤:
#暂停 POST /follower_index/_ccr/pause_follow #关闭 POST /follower_index/_close?wait_for_active_shards=0 #重建 PUT /follower_index/_ccr/follow?wait_for_active_shards=1 { "remote_cluster" : "remote_cluster", "leader_index" : "leader_index" }
7.4 终止复制
需要先暂停、然后关闭,最后终止复制。
POST kibana_sample_data_logs_from_leader/_ccr/unfollow
8、小结
实战出真知,由于这部分是收费功能,可能会用的少。这块一直是新知盲点,实战一把,才知道究竟!
针对data stream 数据流的处理,跨集群也是支持的,限于篇幅原因,本文没有展开,更多内容推荐阅读官方文档。
耗时12小时+,希望对你有帮助!
参考
1、https://www.elastic.co/cn/blog/follow-the-leader-an-introduction-to-cross-cluster-replication-in-elasticsearch
2、https://opendistro.github.io/for-elasticsearch/blog/releases/2021/02/announcing-ccr/
3、https://www.elastic.co/guide/en/elasticsearch/reference/current/xpack-ccr.html
4、https://www.elastic.co/cn/blog/bi-directional-replication-with-elasticsearch-cross-cluster-replication-ccr
5、https://opster.com/blogs/elasticsearch-cross-cluster-replication-overview/
推荐
1、重磅 | 死磕 Elasticsearch 方法论认知清单(2021年国庆更新版)
2、Elasticsearch 7.X 进阶实战私训课(口碑不错)
更短时间更快习得更多干货!
已带领72位球友通过 Elastic 官方认证!
中国仅通过百余人
比同事抢先一步学习进阶干货!
-
超硬核!数据结构学霸笔记,考试面试吹牛就靠它
2021-03-26 11:11:21请看代码 def f0(n): if n==1 or n==2: return 1 return f(n-1)+f(n-2) 分析一下,为什么说递归效率很低呢?咱们来试着运行一下就知道了: 比如想求f(10),计算机里怎么运行的? 每次要计算的函数量都是指数型增长,...上次发操作系统笔记,很快浏览上万,这次数据结构比上次硬核的多哦,同样的会发超硬核代码,关注吧。
第一次笔记(复习c,课程概述)
第一节课复习了c语言的一些知识,并简单介绍了数据结构这门课程。
1、引用和函数调用:
1.1引用:对一个数据建立一个“引用”,他的作用是为一个变量起一个别名。这是C++对C语言的一个重要补充。
用法很简单:
int a = 5;
int &b = a;
b是a别名,b与a代表的是同一个变量,占内存中同一个存储单元,具有同一地址。
注意事项:
- 声明一个引用,同时必须初始化,及声明它代表哪一个变量。(作为函数参数时不需要初始化)
- 在声明一个引用后,不能再作为另一变量的引用。
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
算法:是对特定问题求解步骤的一种描述。
算法五个特性:
- 有穷性:有穷的时间内完成,或者可以说是可接受的时间完成
- 确定性:对于相同的输入只能得到相同的输出
- 可行性:描述的操作都可以执行基本操作有限次来实现
- 输入:零个或多个输入。取自于某个特定对象的集合
- 输出:一个或多个输出
设计要求:正确性、可读性、健壮性、效率与低存储量需求。
执行频度概念:是指通过统计算法的每一条指令的执行次数得到的。
执行频度=算法中每一条语句执行次数的和
一般认定每条语句执行一次所需时间为单位时间(常数时间)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条:证明循环的序列不是线性表
注意:
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
插入注意事项:
- 需要判断是否已满
- 要从后向前移动,否则会冲掉元素
删除注意事项:
- 需要先判断是否已空
- 需要把后方元素前移,要从前向后。
注意:线性表的顺序存储借用了一维数组,但是二者不同:
- 一维数组各非空结点可以不相继存放,但顺序表是相继存放的
- 顺序表长度是可变的,一维数组长度是确定的,一旦分配就不可变
- 一维数组只能按下标存取元素,顺序表可以有线性表的所有操作。
第四次笔记(链表概述)
介绍了链表和基本操作
用一组物理位置任意的存储单元来存放线性表的数据元素。 这组存储单元既可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。因此,链表中元素的逻辑次序和 物理次序不一定相同。
定义:
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.4、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)的排序方法:快速排序或堆排序
- 快速排序是目前基于比较的排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
- 堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
- 声明一个引用,同时必须初始化,及声明它代表哪一个变量。(作为函数参数时不需要初始化)
-
六、主从复制原来这么简单
2019-08-21 17:54:57文章目录什么是redis主从复制主从复制的作用 什么是redis主从复制 总所周知redis之所以火因为它有着读取速度快,可持久化的优点。redis的持久化保证了断电或重启数据不会丢失。但仅仅这样是不够的的,持久化是将数据... -
oracle高水位线,终于知道DELETE和TRUNCATE为什么不一样了
2017-12-26 15:48:53oracle高水位线,终于知道DELETE和TRUNCATE为什么不一样了 -
为什么我的word表格没了边框 - 卡饭网
2020-12-22 06:30:51word表格怎么去边框线 word表格去边框线的方法word表格怎么去边框线 word表格去边框线的方法 Word表格怎么去边框?表格制作一般选用Microsoft Excel表格来制作工作需要的表格,但是Excel表格难以处理.因此,涉及数据的... -
MySQL 8 复制(一)——异步复制
2019-05-10 18:25:10一、MySQL异步复制介绍 1. 复制的用途 2. 复制如何工作 3. 两阶段提交 二、复制实验环境 三、安装mysql-8.0.16 四、配置异步复制 1. 空库 2. 脱机 3. 联机 一、MySQL异步复制介绍 简单说,复制就是将... -
面试问:Kafka为什么速度那么快?
2019-06-02 09:30:00下面从数据写入和读取两方面分析,为什么Kafka速度这么快。 一、写入数据 Kafka会把收到的消息都写入到硬盘中,它绝对不会丢失数据。为了优化写入速度Kafka采用了两个技术, 顺序写入和MMFile 。 1、... -
超硬核十万字!全网最全 数据结构 代码,随便秒杀老师/面试官,我说的
2021-04-11 01:11:23(数组中保存起始位置就好了,结束位置一定是最后) AC自动机 数组缺失 二叉树遍历 前序 中序 后序 进一步思考 二叉树序列化/反序列化 先序中序后序两两结合重建二叉树 先序遍历 中序遍历 后序遍历 层次遍历 输入某... -
Eclipse颜色主题(Color Theme)与缩进线(Indent Guide)插件安装教程
2019-05-04 21:58:36摘要:这篇博文主要介绍Eclipse的颜色主题插件(Color Theme)的安装教程,以及如何使用缩进线插件(Indent Guide)为编辑器中代码添加类似Visual Studio中的缩进线,以对Eclipse编辑器界面进行美化,要点如下:... -
当年,学姐把这份Java总结给我,让我在22k的校招王者局乱杀
2021-04-22 08:41:36为什么要用判断双重: 因为可能有两个线程都执行完了第一个if语句,如果没有第二重判断,那么当其中有个线程执行完synchronized里面的语句之后,另外一个线程跟着也会执行,这样就达不到单例模式的效果 2.... -
很精辟的oracle高水位线,终于知道DELETE和TRUNCATE为什么不一样了
2014-04-17 10:48:52一、Oracle表段中的高水位线HWM ...在数据库表刚建立的时候,由于没有任何数据,所以这个时候水位线是空的,也就是说HWM为最低值。当插入了数据以后,高水位线就会上涨,但是这里也有一个特性,就是如 -
【超全汇总】学习数据结构与算法,计算机基础知识,看这篇就够了
2020-01-18 12:22:30不过公众号可以说是不支持修改文章,因为我决定每两三个月就整理一次,会非常详细着按照类别整理出来哦,并且也给出了目录哦。大家记得多看看哦,好多文章都是面试中常问滴 文章目录一、经验/经历/所... -
删除 commit 的三种方法
2021-01-13 00:46:36一、删除文件如果需要删除的 commit 是一个或多个文件,可以进行以下操作。被提交到仓库的某个文件需要删除,可以使用 git rm 命令:1. git rm // 从工作区和暂存区删除某个文件2. git commit -m "" // 再次提交到... -
windows里面没有FAT32格式化命令
2021-07-31 06:32:04而且每个盘的右键里都多出了一个"自动运行"的选项,双击盘显示"文件"copy.exe"找不到,请````",重装了以后c盘好了,其他的盘还是这种情况,将其中一个盘格式化了以后就好了,但我的盘里有好多重要的文件,还有什么办法可以... -
oracle 高水位线详解(删除大量数据后续处理)
2018-11-07 14:30:12一、oracle 高水位线详解 一、什么是水线(High Water Mark)? 所有的oracle段(segments,在此,为了理解方便,建议把segment作为表的一个同义词) 都有一个在段内容纳数据的上限,我们把这个上限称为"high water ... -
从C中的字符串中删除空格?
2021-05-19 10:39:44在C语言中从字符串中删除空格的最简单,最有效的方法是什么?Tyler Treat asked 2020-07-17T12:59:47Z12个解决方案76 votes最简单,最有效的方法通常不合用...这是一个可能的解决方案:void remove_spaces(char* s) ... -
牛逼!Java 从入门到精通,超全汇总版
2021-05-06 19:40:33有人问图中为什么没有并发或者 Java 虚拟机这些,这些属于中高级内容,刚开始学 Java 不用懂什么并发和 JVM!!!有一些人或者培训班都喜欢秀自己懂 xxx ,懂 xxx ,这不就是误导小白么。 那么话又说回来了,如何... -
使用MHA实现MySQL主从复制高可用
2018-07-31 16:37:101. 配置主从复制 2. 安装Perl等依赖模块 3. 配置SSH登录无密码验证 4. 安装MHA Node 5. 安装MHA Manager 6. 配置MHA 7. 创建相关脚本 四、检查MHA配置 1. 检查SSH配置 2. 检查整个复制环境状况 3. 检查MHA... -
Hadoop中止下线操作后大量剩余复制块的解决方案
2016-01-24 15:36:10前言如果说你是一名hadoop集群的日常维护者,那么你肯定经历过很多的节点上下线工作.例如,随着业务规模的高速扩张,集群的资源渐渐的不够使用的时候,一般正常的做法是通过增加机器来达到线性扩展的效果.当然,当这些... -
《三天给你聊清楚redis》第2天看看redis怎么被搞出来的(22036字)
2020-07-14 09:03:06在对这个键进行修改之后, 会将这个键记为脏(dirty),让事务程序知到这个键被修改 服务器每次修改一个键之后, 都会对脏(dirty)键计数器的值增一, 这个计数器会触发服务器的持久化以及复制操作执行 如果服务器... -
在业务高峰期拔掉服务器电源是一种怎样的体验?
2021-04-10 14:57:06不怕神一样的对手,就怕猪一样的队友,我经历了一次在业务高峰期毫无防备的情况下,被队友“拔”掉了服务器电源的“惨痛”经历。 -
ANSYS Mechanical APDL几何建模中线的编辑和修改命令汇总 | 坐倚北风
2020-12-19 11:00:58在文章《ANSYS mechanical APDL几何建模中线的创建命令汇总》中汇总了在ANSYS中创建线的命令,本文继续介绍下在ANSYS几何建模中编辑和修改线的命令。1 线的操作(Operate)①通过绕轴旋转关键点生成圆命令格式:LROTAT... -
RSD处理高分5号高光谱(GF5 AHSI)数据(二)——波段编辑复制和删除
2019-12-18 11:19:27接上篇《RSD处理高分5号高光谱(GF5 AHSI)数据(一)》,我们已经加载了一个GF 5 AHSI数据集全部330个波段数据并进行了大气校正,现在介绍波段数据的复制和对坏波段的删除等管理功能。 从上篇加载的数据开始,在层... -
用photoshop对两幅图无缝拼接后,怎么消除接口那条明显的线?
2021-01-14 17:57:342、首先打开photoshop图像处理软件,为了更为直观的演示,两幅图无缝拼接后如何消除接口明显的线,我们度加载两张图片并知进行拼接。3、拼接完成后,使用选框工具,选择两张图片的接口位置,在编辑菜单下...1、电脑... -
彻底删除hao123导航主页以及桌面快捷方式
2021-01-17 18:39:58总结来说:将以下代码(不包括双线)复制到一个新建的文件中,后缀改为.bat,双击执行,再打开IE就没有问题了。代码(不包括双线):=============================================[code=BatchFile]@echooffechoHKEY_... -
话说数据库主从复制,读写分离,数据一致性
2019-09-29 10:45:54这种一致性级别是最符合用户直觉的,它要求系统写入什么,读出来的也会是什么,用户体验好,但实现起来往往对系统的性能影响大 2.弱一致性 这种一致性级别约束了系统在写入成功后,不承诺立即可以读到写入的值,也... -
1小时赚300块,不打代码帮人做个吃鸡网页 [IVX实战第3篇]
2021-05-23 10:15:42小媛:吃鸡的网页,赚了300我就可以吃半个月了,下面就是一个示例。 ????1_bit:哈哈哈,我觉得一周你就用完了。 ????小媛:赶紧教我吧,用 IVX,不用打代码应该很快。 ????1_bit:你自己写不好吗? ????小媛:我不... -
大学四年,工作2年我总结了后端面试的所有知识点(持续更新)
2020-05-08 11:41:36Hystrix原理(待查) 通过维护一个自己的线程池,当线程池达到阈值的时候,就启动服务降级,返回fallback默认值 为什么需要hystrix熔断 防止雪崩,及时释放资源,防止系统发生更多的额级联故障,需要对故障和延迟...