精华内容
下载资源
问答
  • 2019-08-13 18:51:04

    什么是栈

    在这里插入图片描述
    百度百科上,栈是这么定义的:

    • 栈(stack)又名堆栈,它是一种运算受限线性表。限定仅在表尾进行插入删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

    稍微介绍一下关键名词:

    • 运算受限:也就是这个表你不能随便的删除插入。只能按照它的规则进行插入删除。比如栈就只能在一端就行插入和删除。同样,队列也是运算受限,只能在两天操作。
    • 线性表:栈也是一种线性表,前面详细介绍过线性表,它表达的是一种数据的逻辑关系。也就是在栈内各个元素是相邻的。当然在具体实现上也分数组和链表实现,他们的物理存储结构不同。但是逻辑结构(实现的目的)相同。
    • 栈顶栈底: 这个描述是偏向于逻辑上的内容,因为大家知道数组在末尾插入删除更容易,而单链表通常在头插入删除更容易。所以数组可以用末尾做栈顶,而链表可以头做栈顶。

    在这里插入图片描述

    栈的应用:

    • 栈的应用广泛,比如你的程序执行查看调用堆栈、加减运算、甚至在搜索算法中dfs,替代递归等等。所以栈也是必须掌握的一门数据结构。很多规范也是栈,比如上图放书拿书一样!

    设计与介绍

    这里我们介绍数组实现的栈和链表实现的栈。

    数组实现

    结构设计

    • 对于数组来说,我们模拟栈的过程很简单,因为栈是后进先出,我们很容易在数组的末尾进行插入和删除。所以我们选定末尾为栈顶。所以对于一个栈所需要的基础元素是 一个data数组和一个top(int)表示栈顶位置。
    • 那么初始话以及构造的函数代码为:
    private T data[];
    private int top;
    public seqStack() {
    	data=(T[]) new Object[10];
    	top=-1;
    }
    public seqStack(int maxsize)
    {
    	data=(T[]) new Object[maxsize];
    	top=-1;
    }
    

    push插入

    栈的核心操作之一push:入栈操作。

    • 如果top<数组长度-1。入栈。top++;a[top]=value;
    • 如果top==数组长度-1;栈满。
      在这里插入图片描述

    pop弹出并返回首位

    • 如果top>=0,栈不为空,可以弹出。return data[top--];
    • 如下图,本来栈为1,2,3,4(栈顶),执行pop操作。top变为3的位置并且返回4;
      在这里插入图片描述

    其他操作

    • 其他例如peek操作时返回栈顶不弹出.所以只需满足题意时候return data[top]即可。

    链表实现

    有数组实现,链表当然也能实现。对于栈的运算。大致可以分为两种思路:

    • 像数组那样在尾部插入删除。大家都知道链表效率低在查询。而查询到尾部效率很低。而我们就算用了尾指针,可以解决尾部插入效率。但是依然无法解决删除效率(删除需要找到前节点).还需要双向链表。前面虽然详细介绍过双向链表,但是这样未免太复杂
    • 所以我们采用带头节点的单链表在头部插入删除,把头部当中栈顶,这样精了很多。插入直接在头节点后插入。而删除也直接删除头节点后第一个元素即可。

    结构设计

    长话短说,短话不说。直接上代码就懂。
    链表的节点

    static class node<T>
    {
    	T data;
    	node next;
    	public node() {    
    	}
    	public node(T value)
    	{
    		this.data=value;
    	}
    }
    

    基本结构:

    public class lisStack <T>{
    	int length;
        node<T> head;//头节点
        public lisStack() {
    		head=new node<>();
    		length=0;
    	}
    	//其他方法
    }
    

    push插入

    与单链表头插入一致,如果不太了解请先看笔者队线性表介绍的。

    和数组形成的栈有个区别。就是理论上栈没有大小限制(不突破内存系统限制)。不需要考虑是否越界。

    • 节点team入栈
    • 空链表入栈head.next=team;
    • 非空入栈team.next=head.next;head.next=team;
      在这里插入图片描述

    pop弹出

    与单链表头删除一致,如果不太了解请先看笔者队线性表介绍的。

    和数组同样需要判断是否为空。

    • 节点team出栈
    • head指向team后驱节点。不需要考虑链表是否为1个节点。如果为1个节点,team.next=null.执行完毕head.next=null。变为空,满足条件。
      在这里插入图片描述

    其他操作

    • 其他例如peek操作时返回栈顶不弹出.所以只需判空满足题意时候return head.next.data即可。而length你可以遍历链表返回长度,也可以动态设置(本文采取)跟随栈长变化。其他操作直接看api。

    实现代码

    数组实现

    package 队栈;
    
    public class seqStack<T> {
    	
    	private T data[];
    	private int top;
    	public seqStack() {
    		data=(T[]) new Object[10];
    		top=-1;
    	}
    	public seqStack(int maxsize)
    	{
    		data=(T[]) new Object[maxsize];
    		top=-1;
    	}
    	boolean isEmpty()
    	{
    		return top==-1;
    	}
    	int length()
    	{
    		return top+1;
    	}
    	
    	boolean push(T value) throws Exception//压入栈
    	{
    		if(top+1>data.length-1)
    		{
    			throw new Exception("栈已满");
    		}
    		else {
    			data[++top]=value;
    			return true;
    		}
    	}
    	T peek() throws Exception//返回栈顶元素不移除
    	{
    		if(!isEmpty())
    		{
    			return data[top];
    		}
    		else {
    			throw new Exception("栈为空");
    		}
    	}
    	T pop() throws Exception
    	{
    		if(isEmpty())
    		{
    			throw new Exception("栈为空");
    		}
    		else {
    		   return data[top--];
    		}
    	}
    	public String toString()
    	{
    		if(top==-1)
    		{
    			return "";
    		}
    		else {
    			String va="";
    			for(int i=top;i>=0;i--)
    			{
    				va+=data[i]+"  ";
    			}
    			return va;
    		}
    	}
    }
    
    

    链表实现

    package 队栈;
    
    public class lisStack <T>{
    	static class node<T>
    	{
    		T data;
    		node next;
    		public node() {    
    		}
    		public node(T value)
    		{
    			this.data=value;
    		}
    	}
    	int length;
        node<T> head;//头节点
        public lisStack() {
    		head=new node<>();
    		length=0;
    	}
        boolean isEmpty()
    	{
    		return head.next==null;
    	}
    	int length()
    	{
    		return length;
    	}
        public void push(T value) {//近栈
           node<T> team=new node<T>(value);
           if(length==0)
           {
        	   head.next=team;
           }
           else {
    		team.next=head.next;
    		head.next=team;}
           length++;
        }
        public T peek() throws Exception {
            if(length==0) {throw new Exception("链表为空");}
            else {//删除
    			return (T) head.next.data;
    		}
      }
        public T pop() throws Exception {//出栈
              if(length==0) {throw new Exception("链表为空");}
              else {//删除
            	T value=(T) head.next.data;
    			head.next=head.next.next;//va.next
    			length--;
    			return value;
    			
    			
    		}
        }
        public String toString(){
        	if(length==0) {return "";}
        	else {
    			String va="";
    		    node team=head.next;
    		    while(team!=null)
    		    {
    		    	va+=team.data+" ";
    		    	team=team.next;
    		    }
    		    return va;
    		}
           
        }
    }
    

    测试

    在这里插入图片描述

    总结

    • 栈的逻辑比较简单。很容易理解,实现起来也相对容易。但是要注意数组情况的界限问题。
    • 后面将介绍队列,相比栈,队列内容更丰富一些。难度也稍大一些。
    • 如果有不好需要改进还请指出
    • 最后,喜欢的话可以关注公众号:bigsai 持续分享(回复 数据结构 获得精心准备资料一份!)

    在这里插入图片描述

    更多相关内容
  • 5种Redis数据结构详解

    万次阅读 多人点赞 2018-08-25 14:51:52
    本文我们主要和大家分享 5种Redis数据结构详解,希望文中的案例和代码,能帮助到大家。 2.1.1 全局命令 1 查看所有键 key* 2 键总数 dbsize (dbsize命令在计算键总数的时候不会遍历所有键,而是直接获取Redis内置...

    http://www.php.cn/php-weizijiaocheng-388126.html

    本文我们主要和大家分享 5种Redis数据结构详解,希望文中的案例和代码,能帮助到大家。

    2.1.1 全局命令

    1 查看所有键 key*

    2 键总数 dbsize (dbsize命令在计算键总数的时候不会遍历所有键,而是直接获取Redis内置的键总数变量,时间复杂度为O(1),而keys命令会遍历所有键,时间复杂度为O(n),当Redis保存了大量键时,线上环境禁止使用)

    3 检查键是否存在 exists key 存在返回1,不存在返回0

    4 删除键 del key 返回成功删除键的个数,不存在的返回0

    5 键过期 expire key seconds ttl 命令会返回剩余过期时间 -1 键没设置过期时间 -2 键不存在

    6 键的数据类型结构 type key 返回类型,不存在返回none 

    2.1.2 数据结构和内部编码

    每种数据结构都有自己的底层的内部编码实现,而且是多种实现,这样Redis会在合适的场景选择合适的内部编码

    每种数据结构都有两种以上的内部编码实现,例如list数据结构包含了linkedlist和ziplist两种内部编码,可以通过object encoding命令查询内部编码

     

     

    Redis这样设计有两个好处:第一:可以改进内部编码,而对外的数据结构和命令没有影响。第二 多种内部编码实现可以在不同的场景下发挥各自的优势。比如,ziplist比较节省内存,但是列表元素比较多的情况下,性能有所下降,这时候Redis会根据配置选项将列表类型的内部实现转换为linkedlist

    2.1.3 单线程架构

    Redis使用了单线程架构和I/O多路复用模型来实现高性能的内存数据库服务

    1 引出单线程模型

    调用客户端的过程:发送命令,执行命令,返回结果

    所有的命令在一个队列里排队等待被执行,不存在多个命令被同时执行的情况

    2 为什么单线程还能跑这么快

    第一,纯内存访问,Redis将所有数据放在内存中,内存的响应时间长约100纳秒,这是Redis达到每秒万级别访问的重要基础

    第二,非阻塞I/O,Redis使用epoll作为I/O多路复用技术的实现,再加上Redis自身的事件处理模型将epoll中的连接、读写、关闭都转换为事件,不在网络I/O上浪费过多的时间

    第三 单线程避免了线程切换和竟态产生的消耗

    单线程带来几个好处:第一,单线程简化数据结构和算法的实现。第二,单线程避免了线程切换和竟态产生的消耗。但是对于每个命令的执行命令是有要求的,如果某个命令执行时间过长,就会造成其他命令的阻塞,Redis是面向快速执行场景的数据库,单线程是理解Redis的核心

    2.2 字符串

    Redis的字符串类型是其他几种的基础,值可以是字符串(简单,复杂的json,xml),数字(整型,浮点),二进制(图片,音频,视频),最大值不能超过512MB

     

    2.2.1 命令

    1 常用命令

    1 设置值 set key value 秒级过期时间 毫秒级过期时间 nx|xx

    setnx setxx同上

    应用场景:由于Redis是单线程命令处理机制,如果多个客户端同时执行setnx key value,根据特性,只有一个客户端能设置成功,可以作为分布式锁的一种实现方案

    2 获取值 get key 不存在返回nil

    3 批量设置值 mset key value 

    4 批量获取值 mget key

    学会使用批量操作,有助于提高业务处理效率,但要注意每次批量操作所发送的命令不是无节制的,数量过多造成Redis阻塞或网络拥塞

    5 计数 incr key

    返回结果有三种情况

    值不是整数 返回错误

    值是整数,返回自增后的结果

    键不存在,按照值为0自增,返回结果为1

    还有decr(自减),incrby(自增指定数字),decrby(自减指定数字),incrbyfloat(自增浮点数)

    2 不常用命令

    1 追加值 append key value

    2 字符串长度 strlen key

    3 设置并返回原值 getset key value

    4 设定指定位置的字符 setrange key offset value

    5 获取部分字符串 getrange key start end

    2.2.2 内部编码

    字符串内部编码有3种:int 8个字节的长整型 embstr 小于等于39个字节的字符串 raw 大于39个字节的字符串。Redis会根据当前值的类型和长度决定使用哪种内部编码实现

    2.2.3 典型使用场景

    1 缓存功能

    Redis作为缓存层,Mysql作为存储层,绝大部分的请求的数据都是从Redis中获取。由于Redis具有支持并发的特性,所以缓存通常能起到加速读写和降低后段压力的作用

     

    开发提示:键名命名方式:业务名:对象名:id:[属性]作为键名

    伪代码实现:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    UserInfo getUserInfo(long id){

        userRedisKey="user:info:"+id

        value=redis.get(userRedisKey);

        UserInfo userInfo;

        if(value!=null){

            userInfo=deserialize(value)

        }else{

            userInfo=mysql.get(id)

            if(userInfo!=null)

            redis.setex(userRedisKey,3600,serizelize(userInfo))

            }

    return userInfo

    1

    }

    2 计数

    1

    2

    3

    4

    long incrVideoCounter(long id){

    key="video:playCount:"+id;

    return redis.incr(key)

    }

    开发提示:防作弊,按照不同维度计数,数据持久化到底层数据源

    3 共享Session

     

    4 限速

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    phoneNum="13800000000";

    key="shortMsg:limit:"+phoneNum;

     

    isExists=redis.set(key,1,"EX 60",NX);

    if(isExists !=null ||redis.incr(key)<=5){

    通过

    }else{

    限速

    }

    某一些网站限制一个ip地址不能在一秒钟之内访问超过n次也可以采用类似的思路

    2.3 哈希

    哈希类型是指键值本身又是一个键值对结构

    2.3.1 命令

    1 设置值

    hset key field value

    2 获取值 hget key field

    3 删除field hdel key field

    4 计算field的个数 hlen key

    5 批量设置或获取field-value hmget key field hmset key field value 

    6 判断field是否存在 hexists key field

    7 获取所有field hkeys key 

    8 获取所有的value hvals key

    9 获取所有的field-value hgetall key

    开发提示:如果一定要获取全部的field-value,可以使用hscan命令,该命令会渐进式遍历哈希类型

    10 hincrby hincrby float

    11 计算value的字符串长度 hstrlen key field

    2.3.2 内部编码

    内部编码有两种:

    ziplist(压缩列表) 哈希元素个数<hash-max-ziplist-entries,所有值<hash-max-ziplist-value配置时,Redis会使用ziplist作为hash的内部实现,ziplist使用更加紧凑的结构实现多个元素存储,节省内存方面比hashtable更加优秀

    hashtable(哈希表) 当hash类型无法满足ziplist 条件时,选择,因为hashtable的读写时间度为O(1)

    2.3.3 使用场景

     

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    UserInfo getUserInfo(long id){

    userRedisKey="user:info:"+id;

    userInfoMap=redis.hgetAll(userRedisKey);

    userInfoMap userInfo;

     

    if(userInfoMap!=null){

    userInfo=transferMapToUserInfo(userInfoMap);

    }else{

    userInfo=mysql.get(id);

    redis.hmset(userRedisKey,tranferUserInfoToMap(userInfo));

    redis.expire(userRedisKey,3600);

    }

    return userInfo;

    }

    哈希类型和关系型数据库两点不同:

    1 哈希类型是稀疏的,而关系型数据库是完全结构化的

    2 关系型数据库可以做复杂的查询,而Redis去模拟关系型复杂查询开发困难,维护成本高

    三种方法缓存用户信息

    1 原声字符串类型:每个属性一个键

     

    优点:简单直观,每个属性都支持更新操作

    缺点:占用过多的键,内存占用量较大,同时用户信息内聚性比较差,所以一般不会在生产环境用

    2 序列化字符串类型:将用户信息序列化后用一个键保存

     

    优点:简化编程,如果合理的使用序列化可以提高内存的使用效率

    缺点:序列化和反序列化有一定的开销,同时每次更新属性,都需要把数据取出来反序列化,更新后再序列化到Redis中

    3 哈希类型:每个用户属性使用一对field-value,但是只用一个键保存

    优点:简单直观,如果使用合理,可以减少内存空间的使用

    缺点:要控制哈希在ziplist和hashtable两种内部编码的转换,hashtable会消耗更多的内存

    2.4 列表

    列表类型用来存储多个有序的字符串,一个列表最多存储2的32次方-1个元素,列表是一种比较灵活的数据结构,它可以灵活的充当栈和队列的角色,在实际开发上有很多应用场景

    列表有两个特点:第一、列表中的元素是有序的,这就意味着可以通过索引下标获取某个元素或者某个范围内的元素列表。第二、列表中的元素可以是重复的

    2.4.1 命令

    1 添加操作

    1.1 从右边往左插入元素 rpush key value

    1.2 从左往右插入元素 lpush key value

    1.3 向某个元素前或者后插入元素 linsert key before|after pivot value

     

    2 查找

    1 获取指定范围内的元素列表 lrange key start end 

    索引下标有两个特点:第一,索引下标从左到右分别是0-n-1,从右到左是-1--n,第二,lrange的end选项包含了自身,这个和很多编程语言不包含end不太相同

    2 获取列表指定索引下标的元素 lindex key index

    3 获取列表长度 llen key

    3 删除

    1 从列表左侧弹出元素 lpop key

    2 从列表右侧弹出 rpop key

    3 删除指定元素 lrem key count value

    4 按照索引范围修剪列表 ltrim key start end

    4 修改

    修改指定索引下标的元素 lset key index newValue

    5 阻塞操作 brpop blpop key timeout

    1 列表为空:如果timeout=3,那么客户端要等到3s后返回,如果timeout=0,客户端则阻塞等下去,如果添加了数据,客户端立刻返回

    2 列表不为空:客户端立即返回

    2.4.2 内部编码

    列表类型的内部编码有两种

    ziplist(压缩列表):当列表元素个数<list-max-ziplist-entries,同时list-max-ziplist-value(64字节),Redis会选用列表的内部实现来减少内存的使用

    linkedlist(链表) 当列表类型无法满足ziplist的条件时,Redis会使用linkedlist作为列表的内部实现

    2.4.3 使用场景

    1 消息队列 

    Redis的lpush+brpop命令组合即可实现阻塞队列

     

    2 文章列表 

    两个问题:第一,如果每次分页获取的文章个数较多,需要执行多次hgetall操作,此时考虑使用pipeline批量获取,或者考虑将文章数据序列化为字符串类型,使用mget批量获取。第二,分页获取文章列表时,lrange命令在列表两端性能较好,但是如果列表较大,获取列表中间范围元素的性能会变差,此时可以考虑二级拆分

    开发提示:

    lpush+lpop=Stack(栈)

    lpush+rpop=Queue(队列)

    lpsh+ltrim=Capped Collection(有限集合)

    lpush+brpop=Message Queue(消息队列)

    2.5 集合

    集合用来保存多个字符串元素,和列表不同的是不允许有重复元素,并且集合中元素是无序的

    2.5.1 命令

    1 集合内操作

    1.1 添加元素 sadd key element 

    1.2 删除元素 srem key element

    1.3 计算元素个数 scard key 

    1.4 判断元素是否在集合中 sismember key element

    1.5 随机从集合返回指定个数元素 srandmember key 

    1.6 从集合随机弹出元素 spop key

    1.7 获取所有元素 smembers key

    2 集合间操作

    1 求多个集合的交集 sinter key ...

    2 求多个集合的并集 suinon key..

    3 求多个集合的差集 sdiff key ..

    4 将交集、差集、并集结果保存

    sinterstore destination key 

    sdiffstore destination key 

    suionstore destionation key

     

    2.5.2 内部编码

    集合类型的内部有两种:

    intset(整数集合):当集合中的元素都是整数且元素个数小于set-max-intset-entries配置(默认512个)时,Redis会选用intset来作为集合内部的实现,从而减少内存的使用

    hashtable(哈希表) 当集合类型无法满足intset的条件时,Redis会使用hashtable作为集合的内部实现

    2.5.3 使用场景

    集合类型比较典型的应用场景是标签。

    1 给用户添加标签

    sadd user:1:tags tag1 tag2

    2 给标签添加用户 

    sadd tag1:users user:1 user:3

    开发提示:用户和标签的关系维护应该在一个事务内执行,防止部分命令失败造成的数据不一致

    3 删除用户下的标签

    srem user:1:tags tag1 tag5

    4 删除标签下的用户

    srem tag1:users user:1

    5 计算用户共同感兴趣的标签

    sinter user:1 tags user:2 tags

    开发提示:sadd=Tagging(标签) spop/srandmember=Random item(生成随机数,比如抽奖)

    spop/srandmember=Random item(生成随机数,比如抽奖) sadd+sinter=Social Graph(社交需求)

    2.6 有序集合

    有序集合就是在集合之上加了个score作为排序的依据 

     

    2.6.1 命令

    1 集合内

    1添加成员 zadd key score memeber

    nx xx ch 返回此次操作后,有序集合元素和分数发生变化的个数,incr:对score做增加

    有序集合相比集合提供了排序字段,但是也产生了代价,zadd的时间复杂度为O(log(n)),sadd的时间复杂度为O(1)

    2 计算成员个数

    scard key

    3 计算某个成员的分数 zscore key member

    4 计算成员的排名 zrank key member

    5 删除成员 zrem key member

    6 增加成员的分数 zincrby key increment member

    7 返回指定排名范围的成员 zrange key start end

    8 返回指定分数范围的成员 zrangebysore key min max 

    9 返回指定分数范围成员个数 zcount key min max

    10 删除指定排名内的升序元素 zremrangebyrank key start end

    11 删除指定分数范围的成员 zremrangebyscore key min max

    2 集合间的操作

    1 交集 zinterstore destination numkeys key 

    2 并集 zunionstore destionation numkeys key

    2.6.2 内部编码

    有序集合类型的内部编码有两种:

    ziplist(压缩列表) 当有序集合的元素个数小于zset-max-ziplist-entries配置,同时每个元素的值都小于zset-max-ziplist-value配置时,Redis会用ziplist来作为有序集合的内部实现,ziplist可以有效的减少内存的使用

    skiplist(跳跃表) 当ziplist条件不满足时,有序集合会使用skiplist作为内部实现,因此此时ziplist的读写效率会下降

    2.6.3 使用场景

    有序集合比较典型的使用场景是排行榜系统。例如视频网站需要对用户上传的视频做排行榜榜

    1 添加用户赞数 zdd user:ranking:2016_03_15 mike 3

    之后 zincrby user:ranking:2016_03_15 mike 1

    2 取消用户赞数

    zrem user:rank:2016_03_15 mike

    3 展示获取赞数最多的十个用户

    zrevrangebyrank user:ranking:2016_03_15 0 9

    4 展示用户信息以及用户分数

    此功能可以将用户名作为键后缀,将用户信息保存在哈希类型中,至于用户的分数和排名可以使用zcore和zrank两个功能 

     

    2.7 键管理

    2.7.1 单个键管理

    1 键重命名 rename key newkey

    2 随机返回一个键 randomkey

    3 键过期 -1 键没有设置过期时间 -2 键不存在

    expire key seconds:键在seconds秒后过期

    expire key itmestamp 键在秒级时间戳timestamp后过期

    1 如果expire key的键不存在,返回结果为0

    2 如果过期时间为负值,键会立即被删除,就如使用使用del命令一样

    3 persist 命令可以将键的过期时间清除

    4 对于字符串类型键,执行set命令会去掉过期时间,这个问题很容易在开发中被忽视

    5 Redis不支持二级数据结构内部元素的过期功能,例如不能这列表类型的一个元素做过期时间设置

    6 setex命令作为set+expire组合,不但原子执行,同时减少了网络通讯的时间

    4 迁移键

    迁移键功能非常重要,有move、dump+restore、migrate三组迁移键的方法,它们的实现方式以及使用场景不太相同

    1 move 用于在Redis内部进行数据迁移

    2 dump+restore 实现在不同的Redis实例之间进行数据迁移的功能,这个迁移分两步

    1 在源Redis上,dump命令会将键值序列化,格式采用的是RDB格式

    2 在目标Redis上,restore命令将上面的序列化的值进行复原,其中ttl参数代表过期时间

    3 migrate 命令用于在Redis实例间进行数据迁移的

    2.7.2 遍历键

    Redis提供了两个命令遍历所有的键分别是keys和scan

    1 全量遍历键 keys pattern

    * 代表匹配任意字符

    .代表匹配一个字符

    [] 代表匹配一个字符

    \x用来转义,例如要匹配星号,问号需要进行转义

    大量容易造成阻塞

    2 渐进式遍历

     

    scan可以想象成只扫描一个字典中的一部分键,直到将字典中所有键遍历完毕

    对应的命令还有hsan、sscan、zcan

    渐进式遍历可以有效解决keys命令可能产生的阻塞问题,在有增删的时候,新来的键无法保证遍历到

    2.7.3 数据库管理

    1 切换数据库 select dbIndex

    2 flushdb/flushall 用于清除数据库 数据多的时候会出现阻塞

    2.8 本章终点回顾

    相关推荐:

    Redis数据结构

    以上就是 5种Redis数据结构详解的详细内容,更多请关注php中文网其它相关文章!

    展开全文
  • 数据结构:图(Graph)【详解

    万次阅读 多人点赞 2021-02-26 17:03:48
    图 【知识框架】 【考纲内容】 图的基本概念 图的存储及基本操作 邻接矩阵法;邻接表法;邻接多重表;十字表 ...在线性表中,数据元素之间是被串起来的,仅有线性关系,每个...图是一种较线性表和树更加复杂的数据结构

    友情链接:数据结构专栏

    【知识框架】

    在这里插入图片描述

    图的基本概念

    线性表中,数据元素之间是被串起来的,仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继。在形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素相关,但只能和上一层中一个元素相关。图是一种较线性表和树更加复杂的数据结构。在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。

    一、图的定义

    图(Graph)是由顶点的有穷非空集合 V ( G ) V(G) V(G)和顶点之间边的集合 E ( G ) E(G) E(G)组成,通常表示为: G = ( V , E ) G=(V,E) G=(V,E),其中, G G G表示个图, V V V是图 G G G中顶点的集合, E E E是图 G G G中边的集合。若 V = { v 1 , v 2 , . . . , v n } V= \{v_1, v_2,...,v_n\} V={v1,v2,...,vn},则用 ∣ V ∣ |V| V表示图 G G G中顶点的个数,也称图 G G G的阶, E = { ( u , v ) ∣ u ∈ V , v ∈ V } E= \{(u, v) |u∈V, v∈V\} E={(u,v)uV,vV},用 ∣ E ∣ |E| E表示图 G G G中边的条数。

    注意:线性表可以是空表,树可以是空树,但图不可以是空图。就是说,图中不能一个顶点也没有,图的顶点集V一定非空,但边集E可以为空,此时图中只有顶点而没有边。

    二、图的基本概念和术语

    1、有向图

    若E是有向边(也称弧)的有限集合时,则图G为有向图。弧是顶点的有序对,记为<v, w>,其中v,w是顶点,v称为弧尾,w称为弧头,<v,w>称为从顶点v到顶点w的弧,也称v邻接到w,或w邻接自v。
    在这里插入图片描述
    图(a)所示的有向图 G 1 G_1 G1可表示为 G 1 = ( V 1 , E 1 ) G_1 = (V_1,E_1) G1=(V1,E1) V 1 = { 1 , 2 , 3 } V_1=\{1,2,3\} V1={1,2,3} E 1 = { < 1 , 2 > , < 2 , 1 > , < 2 , 3 > } E_1=\{<1,2>,<2,1>,<2,3>\} E1={<1,2>,<2,1>,<2,3>}

    2、无向图

    若E是无向边(简称边)的有限集合时,则图G为无向图。边是顶点的无序对,记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v,或者说边(v, w)和顶点v, w相关联。
    在这里插入图片描述

    图(b)所示的无向图G2可表示为 G 2 = ( V 2 , E 2 ) G_2=(V_2,E_2) G2=(V2,E2) V 2 = { 1 , 2 , 3 , 4 } V_2=\{1,2,3,4\} V2={1,2,3,4} E 2 = { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } E_2=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\} E2={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

    3、简单图

    一个图 G G G若满足:①不存在重复边;②不存在顶点到自身的边,则称图 G G G为简单图。上图中 G 1 G_1 G1 G 2 G_2 G2均为简单图。数据结构中仅讨论简单图。

    4、多重图

    若图 G G G中某两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联,则 G G G为多重图。多重图的定义和简单图是相对的。

    5、完全图(也称简单完全图)

    对于无向图, ∣ E ∣ |E| E的取值范围是 0 0 0 n ( n − 1 ) / 2 n(n-1)/2 n(n1)/2,有 n ( n − 1 ) / 2 n(n -1)/2 n(n1)/2条边的无向图称为完全图,在完全图中任意两个顶点之间都存在边。对于有向图, ∣ E ∣ |E| E的取值范围是 0 0 0 n ( n − 1 ) n(n-1) n(n1),有 n ( n − 1 ) n(n-1) n(n1)条弧的有向图称为有向完全图,在有向完全图中任意两个顶点之间都存在方向相反的两条弧。上图中 G 2 G_2 G2为无向完全图,而 G 3 G_3 G3为有向完全图。
    在这里插入图片描述

    6、子图

    设有两个图 G = ( V , E ) G=(V, E) G=(V,E) G ′ = ( V ′ , E ′ ) G'=(V', E') G=(V,E), 若 V ′ V' V V V V的子集,且 E ′ E' E E E E的子集,则称 G ′ G' G G G G的子图。若有满足 V ( G ′ ) = V ( G ) V(G')= V(G) V(G)=V(G)的子图 G ′ G' G,则称其为 G G G生成子图。上图中 G 3 G_3 G3 G 1 G_1 G1的子图。

    注意:并非V和E的任何子集都能构成G的子图,因为这样的子集可能不是图,即E的子集中的某些边关联的顶点可能不在这个V的子集中。

    7、连通、连通图和连通分量

    在无向图中,若从顶点 v v v到顶点 w w w有路径存在,则称 v v v w w w是连通的。若图 G G G中任意两个顶点都是连通的,则称图 G G G连通图,否则称为非连通图。无向图中的极大连通子图称为连通分量。若一个图有 n n n个顶点,并且边数小于 n − 1 n-1 n1,则此图必是非连通图。如下图(a)所示, 图 G 4 G_4 G4有3个连通分量,如图(b)所示。
    在这里插入图片描述

    注意:弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图,极大连通子图是无向图的连通分量,极大即要求该连通子图包含其所有的边;极小连通子图是既要保持图连通又要使得边数最少的子图。

    8、强连通图、强连通分量

    在有向图中,若从顶点 v v v到顶点 w w w和从顶点 w w w到项点 v v v之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的,则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量,图 G 1 G_1 G1的强连通分量如下图所示。
    在这里插入图片描述

    注意:强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性,在有向图中考虑强连通性。

    9、生成树、生成森林

    连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n n n,则它的生成树含有 n − 1 n-1 n1条边。对生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。在非连通图中,连通分量的生成树构成了非连通图的生成森林。图 G 2 G_2 G2的一个生成树如下图所示。
    在这里插入图片描述

    注意:包含无向图中全部顶点的极小连通子图,只有生成树满足条件,因为砍去生成树的任一条边,图将不再连通。

    10、顶点的度、入度和出度

    图中每个顶点的度定义为以该项点为一个端点的边的数目。
    对于无向图,顶点v的度是指依附于该顶点的边的条数,记为 T D ( v ) TD(v) TD(v)
    在具有 n n n个顶点、 e e e条边的无向图中, ∑ i = 1 n T D ( v i ) = 2 e \displaystyle\sum_{i=1}^{n}TD(v_i)= 2e i=1nTD(vi)=2e,即无向图的全部顶点的度的和等于边数的2倍,因为每条边和两个顶点相关联。
    对于有向图,顶点 v v v的度分为入度出度,入度是以顶点 v v v为终点的有向边的数目,记为 I D ( v ) ID(v) ID(v); 而出度是以顶点 v v v为起点的有向边的数目,记为 O D ( v ) OD(v) OD(v)。顶点 v v v的度等于其入度和出度之和,即 T D ( v ) = I D ( v ) + O D ( v ) 。 TD(v) = ID(v) + OD(v)。 TD(v)=ID(v)+OD(v)
    在具有 n n n个顶点、 e e e条边的有向图中, ∑ i = 1 n I D ( v i ) = ∑ i = 1 n O D ( v i ) = e \displaystyle\sum_{i=1}^{n}ID(v_i)=\displaystyle\sum_{i=1}^{n}OD(v_i)=e i=1nID(vi)=i=1nOD(vi)=e,即有向图的全部顶点的入度之和与出度之和相等,并且等于边数。这是因为每条有向边都有一个起点和终点。

    11、边的权和网

    在一个图中,每条边都可以标上具有某种含义的数值,该数值称为该边的权值。这种边上带有权值的图称为带权图,也称

    12、稠密图、稀疏图

    边数很少的图称为稀疏图,反之称为稠密图。稀疏和稠密本身是模糊的概念,稀疏图和稠密图常常是相对而言的。一般当图G满足 ∣ E ∣ < ∣ V ∣ l o g ∣ V ∣ |E| < |V|log|V| E<VlogV时,可以将 G G G视为稀疏图。

    13、路径、路径长度和回路

    顶点 v p v_p vp到顶点 v q v_q vq之间的一条路径是指顶点序列 v p , v i 1 , v i 2 , . . . , v i m , v q v_p,v_{i_1},v_{i_2},...,v_{i_m},v_q vp,vi1,vi2,...,vim,vq,当然关联的边也可以理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路。若一个图有 n n n个顶点,并且有大于 n − 1 n-1 n1条边,则此图一定有环。

    14、 简单路径、简单回路

    在路径序列中,顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路。

    15、距离

    从顶点 u u u出发到顶点 v v v的最短路径若存在,则此路径的长度称为从 u u u v v v的距离。若从 u u u v v v根本不存在路径,则记该距离为无穷 ( ∞ ) (∞) ()

    16、有向树

    一个顶点的入度为0、其余顶点的入度均为1的有向图,称为有向树。

    图的存储结构

    由于图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在内存中的物理位置来表示元素之间的关系,也就是说,图不可能用简单的顺序存储结构来表示。而多重链表的方式,要么会造成很多存储单元的浪费,要么又带来操作的不便。因此,对于图来说,如何对它实现物理存储是个难题,接下来我们介绍五种不同的存储结构。

    一、邻接矩阵

    图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
    设图 G G G n n n个顶点,则邻接矩阵 A A A是一个 n ∗ n n*n nn的方阵,定义为:
    在这里插入图片描述
    下图是一个无向图和它的邻接矩阵:
    在这里插入图片描述
    可以看出:

    1. 无向图的邻接矩阵一定是一个对称矩阵(即从矩阵的左上角到右下角的主对角线为轴,右上角的元与左下角相对应的元全都是相等的)。 因此,在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
    2. 对于无向图,邻接矩阵的第 i i i行(或第 i i i列)非零元素(或非 ∞ ∞ 元素)的个数正好是第 i i i个顶点的度 T D ( v i ) TD(v_i) TD(vi)。比如顶点 v 1 v_1 v1的度就是 1 + 0 + 1 + 0 = 2 1+0+1+0=2 1+0+1+0=2
    3. 求顶点 v i v_i vi的所有邻接点就是将矩阵中第i行元素扫描一遍, A [ i ] [ j ] A[i][j] A[i][j]为 1就是邻接点。

    下图是有向图和它的邻接矩阵:
    在这里插入图片描述
    可以看出:

    1. 主对角线上数值依然为0。但因为是有向图,所以此矩阵并不对称。
    2. 有向图讲究入度与出度,顶点 v 1 v_1 v1的入度为1,正好是第 v 1 v_1 v1列各数之和。顶点 v 1 v_1 v1的出度为2,即第 v 1 v_1 v1行的各数之和。
    3. 与无向图同样的办法,判断顶点 v i v_i vi v j v_j vj是否存在弧,只需要查找矩阵中 A [ i ] [ j ] A[i][j] A[i][j] 是否为1即可。

    对于带权图而言,若顶点 v i v_i vi v j v_j vj之间有边相连,则邻接矩阵中对应项存放着该边对应的权值
    在这里插入图片描述
    下图是有向网图和它的邻接矩阵:
    在这里插入图片描述


    通过以上对无向图、有向图和网的描述,可定义出邻接矩阵的存储结构:

    #define MaxVertexNum 100	//顶点数目的最大值
    typedef char VertexType;	//顶点的数据类型
    typedef int EdgeType;	//带权图中边上权值的数据类型
    typedef struct{
    	VertexType Vex[MaxVertexNum];	//顶点表
    	EdgeType Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵,边表
    	int vexnum, arcnum;	//图的当前顶点数和弧树
    }MGraph;
    

    注意:
    ①在简单应用中,可直接用二维数组作为图的邻接矩阵(顶点信息等均可省略)。
    ②当邻接矩阵中的元素仅表示相应的边是否存在时,EdgeType可定义为值为0和1的枚举类型。
    ③无向图的邻接矩阵是对称矩阵,对规模特大的邻接矩阵可采用压缩存储。
    ④邻接矩阵表示法的空间复杂度为 O ( n 2 ) O(n^2) O(n2), 其中n为图的顶点数 ∣ V ∣ |V| V
    ⑤ 用邻接矩阵法存储图,很容易确定图中任意两个顶点之间是否有边相连。但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所花费的时间代价很大。
    ⑥ 稠密图适合使用邻接矩阵的存储表示。

    二、邻接表

    当一个图为稀疏图时(边数相对顶点较少),使用邻接矩阵法显然要浪费大量的存储空间,如下图所示:
    在这里插入图片描述
    而图的邻接表法结合了顺序存储和链式存储方法,大大减少了这种不必要的浪费。
    所谓邻接表,是指对图 G G G中的每个顶点 v i v_i vi建立一个单链表,第 i i i个单链表中的结点表示依附于顶点 v i v_i vi 的边(对于有向图则是以顶点 v i v_i vi为尾的弧),这个单链表就称为顶点 v i v_i vi的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表),所以在邻接表中存在两种结点:顶点表结点和边表结点,如下图所示。
    在这里插入图片描述
    顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc) 构成,边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc) 构成。
    无向图的邻接表的实例如下图所示。
    在这里插入图片描述
    有向图的邻接表的实例如下图所示。
    在这里插入图片描述
    此时我们很容易就可以算出某个顶点的入度或出度是多少,判断两顶点是否存在弧也很容易实现。
    对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可。

    图的邻接表存储结构定义如下:

    #define MAXVEX 100	//图中顶点数目的最大值
    type char VertexType;	//顶点类型应由用户定义
    typedef int EdgeType;	//边上的权值类型应由用户定义
    /*边表结点*/
    typedef struct EdgeNode{
    	int adjvex;	//该弧所指向的顶点的下标或者位置
    	EdgeType weight;	//权值,对于非网图可以不需要
    	struct EdgeNode *next;	//指向下一个邻接点
    }EdgeNode;
    
    /*顶点表结点*/
    typedef struct VertexNode{
    	Vertex data;	//顶点域,存储顶点信息
    	EdgeNode *firstedge	//边表头指针
    }VertexNode, AdjList[MAXVEX];
    
    /*邻接表*/
    typedef struct{
    	AdjList adjList;
    	int numVertexes, numEdges;	//图中当前顶点数和边数
    }
    

    图的邻接表存储方法具有以下特点

    1. G G G为无向图,则所需的存储空间为 O ( ∣ V ∣ + 2 ∣ E ∣ ) O(|V|+2|E|) O(V+2E);若 G G G为有向图,则所需的存储空间为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(V+E)。前者的倍数2是由于无向图中,每条边在邻接表中出现了两次
    2. 对于稀疏图,采用邻接表表示将极大地节省存储空间。
    3. 在邻接表中,给定一顶点,能很容易地找出它的所有邻边,因为只需要读取它的邻接表。在邻接矩阵中,相同的操作则需要扫描一行,花费的时间为 O ( n ) O(n) O(n)。但是,若要确定给定的两个顶点间是否存在边,则在邻接矩阵中可以立刻查到,而在邻接表中则需要在相应结点对应的边表中查找另一结点,效率较低。
    4. 在有向图的邻接表表示中,求一个给定顶点的出度只需计算其邻接表中的结点个数;但求其顶点的入度则需要遍历全部的邻接表。因此,也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然,这实际上与邻接表存储方式是类似的。
    5. 图的邻接表表示并不唯一,因为在每个顶点对应的单链表中,各边结点的链接次序可以是任意的,它取决于建立邻接表的算法及边的输入次序。

    三、十字链表

    十字链表是有向图的一种链式存储结构。
    对于有向图来说,邻接表是有缺陷的。关心了出度问题,想了解入度就必须要遍历整个图才能知道,反之,逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢?答案是肯定的,就是把它们整合在一起。这就是我们现在要介绍的有向图的一种存储方法:十字链表(Orthogonal List)
    我们重新定义顶点表结点结构如下表所示。
    在这里插入图片描述
    其中firstin表示入边表头指针,指向该顶点的入边表中第一个结点,firstout 表示出边表头指针,指向该顶点的出边表中的第一个结点。
    重新定义的边表结点结构如下表所示。
    在这里插入图片描述
    其中tailvex 是指弧起点在顶点表的下标,headvex 是指弧终点在顶点表中的下标,headlink是指入边表指针域,指向终点相同的下一条边,taillink是指边表指针域,指向起点相同的下一条边。如果是网,还可以再增加一个weight域来存储权值。

    接下来通过一个例子详细介绍十字链表的结构。
    如下图所示,顶点依然是存入一个一维数组 { V 0 , V 1 , V 2 , V 3 } \{V_0,V_1,V_2,V_3\} {V0,V1,V2,V3}实线箭头指针的图示完全与的邻接表的结构相同。就以顶点 V 0 V_0 V0来说,firstout 指向的是出边表中的第一个结点 V 3 V_3 V3。所以 V 0 V_0 V0边表结点的 h e a d v e x = 3 headvex=3 headvex=3,而tailvex就是当前顶点 V 0 V_0 V0的下标0,由于 V 0 V_0 V0只有一个出边顶点,所以headlink和taillink都是空。
    在这里插入图片描述
    我们重点需要来解释虚线箭头的含义,它其实就是此图的逆邻接表的表示。对于 V 0 V_0 V0来说,它有两个顶点 V 1 V_1 V1 V 2 V_2 V2的入边。因此 V 0 V_0 V0的firstin指向顶点 V 1 V_1 V1的边表结点中headvex为0的结点,如上图右图中的①。接着由入边结点的headlink指向下一个入边顶点 V 2 V_2 V2,如图中的②。对于顶点 V 1 V_1 V1,它有一个入边顶点 V 2 V_2 V2,所以它的firstin指向顶点 V 2 V_2 V2的边表结点中headvex为1的结点,如图中的③。顶点 V 2 V_2 V2 V 3 V_3 V3也是同样有一个入边顶点,如图中④和⑤。

    十字链表的好处就是因为把邻接表和逆邻接表整合在了一起, 这样既容易找到以 V 1 V_1 V1为尾的弧,也容易找到以 V 1 V_1 V1为头的弧,因而容易求得顶点的出度和入度。而且它除了结构复杂一点外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图的应用中,十字链表是非常好的数据结构模型。

    四、邻接多重表

    邻接多重表是无向图的另一种链式存储结构。
    在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。比如下图中,若要删除左图的 ( V 0 , V 2 ) (V_0,V_2) (V0,V2) 这条边,需要对邻接表结构中右边表的阴影两个结点进行删除操作,显然这是比较烦琐的。
    在这里插入图片描述
    重新定义的边表结点结构如下表所示。
    在这里插入图片描述
    其中ivex和jvex是与某条边依附的两个顶点在顶点表中下标。ilink 指向依附顶点ivex的下一条边,jlink 指向依附顶点jvex的下一条边。这就是邻接多重表结构。

    每个顶点也用一一个结点表示,它由如下所示的两个域组成。
    在这里插入图片描述
    其中,data 域存储该顶点的相关信息,firstedge 域指示第一条依附于该顶点的边。

    我们来看结构示意图的绘制过程,理解了它是如何连线的,也就理解邻接多重表构造原理了。如下图7所示,左图告诉我们它有4个顶点和5条边,显然,我们就应该先将4个顶点和5条边的边表结点画出来。
    在这里插入图片描述
    我们开始连线,如图,首先连线的①②③④就是将顶点的firstedge指向一条边,顶点下标要与ivex的值相同,这很好理解。接着,由于顶点 V 0 V_0 V0 ( V 0 , V 1 ) (V_0,V_1) (V0,V1) 边的邻边有 ( V 0 , V 3 ) (V_0,V_3) (V0,V3) ( V 0 , V 2 ) (V_0,V_2) (V0,V2)。 因此⑤⑥的连线就是满足指向下一条依附于顶点 V 0 V_0 V0的边的目标,注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。同样的道理,连线⑦就是指 ( V 1 , V 0 ) (V_1,V_0) (V1,V0) 这条边,它是相当于顶点 V 1 V_1 V1指向 ( V 1 , V 2 ) (V_1,V_2) (V1,V2) 边后的下一条。 V 2 V_2 V2有三条边依附,所以在③之后就有了⑧⑨。连线④的就是顶点 V 3 V_3 V3在连线④之后的下一条边。 左图一共有5条边,所以右图有10条连线,完全符合预期。


    到这里,可以明显的看出,邻接多重表与邻接表的差别,仅仅是在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。 这样对边的操作就方便多了,若要删除左图的 ( V 0 , V 2 ) (V_0,V_2) (V0,V2) 这条边,只需要将右图的⑥⑨的链接指向改为NULL即可。

    五、边集数组

    边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin)、 终点下标(end)和权(weight)组成,如下图所示。显然边集数组关注的是边的集合,在边集数组中要查找一个顶点的度需要扫描整个边数组,效率并不高。因此它更适合对边依次进行处理的操作,而不适合对顶点相关的操作。
    在这里插入图片描述

    图的遍历

    图的遍历是和树的遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次, 这一过程就叫做图的遍历(Traversing Graph)。
    对于图的遍历来,通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。

    一、深度优先遍历

    深度优先遍历(Depth First Search),也有称为深度优先搜索,简称为DFS

    1、DFS算法

    深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样,这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点v,然后由v出发,访问与v邻接且未被访问的任一顶点 w 1 w_1 w1,再访问与 w 1 w_1 w1邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直至图中所有顶点均被访问过为止。
    般情况下,其递归形式的算法十分简洁,算法过程如下:

    bool visited[MAX_VERTEX_NUM];	//访问标记数组
    /*从顶点出发,深度优先遍历图G*/
    void DFS(Graph G, int v){
    	int w;
    	visit(v);	//访问顶点
    	visited[v] = TRUE;	//设已访问标记
    	//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。
    	//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点v
    	for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
    		if(!visited[w]){	//w为u的尚未访问的邻接顶点
    			DFS(G, w);
    		}
    	}
    }
    /*对图进行深度优先遍历*/
    void DFSTraverse(MGraph G){
    	int v; 
    	for(v=0; v<G.vexnum; ++v){
    		visited[v] = FALSE;	//初始化已访问标记数据
    	}
    	for(v=0; v<G.vexnum; ++v){	//从v=0开始遍历
    		if(!visited[v]){
    			DFS(G, v);
    		}
    	}
    }
    

    以下面这个无向图为例
    在这里插入图片描述
    其深度优先遍历的结果为 a b d e h c f g abdehcfg abdehcfg

    2、DFS算法的性能分析

    DFS算法是一个递归算法,需要借助一个递归工作栈,故其空间复杂度为 O ( V ) O(V) O(V)
    对于n个顶点e条边的图来说,邻接矩阵由于是二维数组,要查找每个顶点的邻接点需要访问矩阵中的所有元素,因此都需要 O ( V 2 ) O(V^2) O(V2)的时间。而邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是 O ( V + E ) O(V+E) O(V+E)。 显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。
    对于有向图而言,由于它只是对通道存在可行或不可行,算法上没有变化,是完全可以通用的。

    3、深度优先的生成树和生成森林

    深度优先搜索会产生一棵深度优先生成树。 当然,这是有条件的,即对连通图调用DFS才能产生深度优先生成树,否则产生的将是深度优先生成森林,如下图所示。基于邻接表存储的深度优先生成树是不唯一的 。
    在这里插入图片描述

    二、广度优先遍历

    广度优先遍历(Breadth First Search),又称为广度优先搜索,简称BFS。

    1、BFS算法

    如果说图的深度优先遍历类似树的前序遍历,那么图的广度优先遍历就类似于树的层序遍历了。
    广度优先搜索是一种分层的查找过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况,因此它不是一个递归的算法。为了实现逐层的访问,算法必须借助一个辅助队列,以记忆正在访问的顶点的下一层顶点。
    以下是广度优先遍历的代码:

    /*邻接矩阵的广度遍历算法*/
    void BFSTraverse(MGraph G){
    	int i, j;
    	Queue Q;
    	for(i = 0; i<G,numVertexes; i++){
    		visited[i] = FALSE;
    	}
    	InitQueue(&Q);	//初始化一辅助用的队列
    	for(i=0; i<G.numVertexes; i++){
    		//若是未访问过就处理
    		if(!visited[i]){
    			vivited[i] = TRUE;	//设置当前访问过
    			visit(i);	//访问顶点
    			EnQueue(&Q, i);	//将此顶点入队列
    			//若当前队列不为空
    			while(!QueueEmpty(Q)){
    				DeQueue(&Q, &i);	//顶点i出队列
    				//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。
    				//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点v
    				for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){
    					//检验i的所有邻接点
    					if(!visited[j]){
    						visit(j);	//访问顶点j
    						visited[j] = TRUE;	//访问标记
    						EnQueue(Q, j);	//顶点j入队列
    					}
    				}
    			}
    		}
    	}
    }
    

    以下面这个无向图为例
    在这里插入图片描述
    其广度优先遍历的结果为 a b c d e f g h abcdefgh abcdefgh

    2、BFS算法性能分析

    无论是邻接表还是邻接矩阵的存储方式,BFS 算法都需要借助一个辅助队列Q, n个顶点均需入队一次,在最坏的情况下,空间复杂度为 O ( V ) O(V) O(V)
    采用邻接表存储方式时,每个顶点均需搜索一次(或入队一次), 在搜索任一顶点的邻接点时,每条边至少访问一次,算法总的时间复杂度为 O ( V + E ) O(V + E) O(V+E)。采用邻接矩阵存储方式时,查找每个顶点的邻接点所需的时间为 O ( V ) O(V) O(V),故算法总的时间复杂度为 O ( V 2 ) O(V^2) O(V2)

    注意:图的邻接矩阵表示是唯一的,但对于邻接表来说,若边的输入次序不同,生成的邻接表也不同。因此,对于同样一个图,基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的,基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

    三、图的遍历与图的连通性

    图的遍历算法可以用来判断图的连通性。
    对于无向图来说,若无向图是连通的,则从任一结点出发, 仅需一次遍历就能够访问图中的所有顶点;若无向图是非连通的,则从某一个顶点出发,一次遍历只能访问到该顶点所在连通分量的所有顶点,而对于图中其他连通分量的顶点,则无法通过这次遍历访问。对于有向图来说,若从初始点到图中的每个顶点都有路径,则能够访问到图中的所有顶点,否则不能访问到所有顶点。
    故在BFSTraverse ()或DFSTraverse ()中添加了第二个for循环,再选取初始点,继续进行遍历,以防止一次无法遍历图的所有顶点。对于无向图,上述两个函数调用BFS (G,i)或DFS(G,i)的次数等于该图的连通分量数;而对于有向图则不是这样,因为一个连通的有向图分为强连通的和非强连通的,它的连通子图也分为强连通分量和非强连通分量,非强连通分量一次调用BFS (G, i)或DFS (G, i)无法访问到该连通分量的所有顶点。
    如下图所示为有向图的非强连通分量。
    在这里插入图片描述

    最小生成树

    一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的 n − 1 n-1 n1条边,若砍去它的一条边,则会使生成树变成非连通图;若给它增加一条边,则会形成图中的一条回路。对于一个带权连通无向图 G = ( V , E ) G=(V, E) G=(V,E),生成树不同,其中边的权值之和最小的那棵生成树(构造连通网的最小代价生成树),称为G的最小生成树(Minimum-Spanning-Tree, MST)

    构造最小生成树有多种算法,但大多数算法都利用了最小生成树的下列性质:假设 G = ( V , E ) G=(V, E) G=(V,E)是一个带权连通无向图, U U U是顶点集 V V V的一个非空子集。若 ( u , v ) (u,v) (u,v)是一条具有最小权值的边,其中 u ∈ U , v ∈ V − U u∈U,v∈V-U uU,vVU,则必存在一棵包含边 ( u , v ) (u, v) (u,v)的最小生成树。
    基于该性质的最小生成树算法主要有Prim算法和Kruskal算法,它们都基于贪心算法的策略。
    下面介绍一个通用的最小生成树算法:

    GENERIC_MST(G){
    	T=NULL;
    	while T 未形成一棵生成树;
    		do 找到一条最小代价边(u, v)并且加入T后不会产生回路;
    			T=T U (u, v);
    }
    

    通用算法每次加入一条边以逐渐形成一棵生成树,下面介绍两种实现上述通用算法的途径。

    一、普里姆(Prim)算法

    Prim算法构造最小生成树的过程如下图所示。初始时从图中任取一顶点(如顶点加入树T,此时树中只含有一个顶点,之后选择一个与当前T中顶点集合距离最近的顶点,并将该顶点和相应的边加入T,每次操作后T中的顶点数和边数都增1。以此类推,直至图中所有的顶点都并入T,得到的T就是最小生成树。此时T中必然有n-1条边。
    通俗点说就是:从一个顶点出发,在保证不形成回路的前提下,每找到并添加一条最短的边,就把当前形成的连通分量当做一个整体或者一个点看待,然后重复“找最短的边并添加”的操作。
    在这里插入图片描述
    Prim算法的步骤如下:
    假设 G = { V , E } G= \{V, E\} G={V,E}是连通图,其最小生成树 T = ( U , E T ) T=(U, E_T) T=(U,ET) E T E_T ET是最小生成树中边的集合。
    初始化:向空树 T = ( U , E T ) T=(U, E_T) T=(U,ET)中添加图 G = ( V , E ) G=(V, E) G=(V,E)的任一顶点 u 0 u_0 u0,使 U = { u 0 } U=\{u_0\} U={u0} E T = N U L L E_T=NULL ET=NULL
    循环(重复下列操作直至 U = V U=V U=V):从图 G G G中选择满足 { ( u , v ) ∣ u ∈ U , v ∈ V − U } \{(u, v)|u∈U, v∈V-U\} {(u,v)uU,vVU}且具有最小权值的边 ( u , v ) (u,v) (u,v),加入树 T T T,置 U = U ∪ { v } U=U∪\{v\} U=U{v} E T = E T U { ( u , v ) } E_T= E_TU\{(u, v)\} ET=ETU{(u,v)}

    额,不得不说这样理解起来有点抽象,为了能描述这个算法,我们先构造一个邻接矩阵,如下图的右图所示。
    在这里插入图片描述

    于是普里姆(Prim) 算法代码如下,左侧数字为行号。其中INFINITY为权值极大值,不妨设65535,MAXVEX 为顶点个数最大值,此处大于等于9即可。

    /*Prim算法生成最小生成树*/
    void MiniSpanTree_Prim(G){
    	int min, i, j, k;
    	int adjvex[MAXVEX];	//保存相关顶点下标
    	int lowcost[MAXVEX];	//保存相关顶点间边的权值
    	lowcost[0] = 0;	//初始化第一个权值为0,即v0加入生成树
    	//lowcost的值为0,在这里就是此下标的顶点已经加入生成树
    	adjvex[0] = 0;	//初始化第一个顶点下标为0
    	for(i=1; i<G.numVertexes; i++){
    		lowcost[i] = G.arc[0][i];	//将v0顶点与之组成边的权值存入数组
    		adjvex[i] = 0;	//初始化都为v0的下标
    	}
    	for(i=1; i<G.numVertexes; i++){
    		min = INFINITY;	//初始化最下权值为∞,通常设置一个不可能的很大的数字
    		j = 1; k = 0;
    		//循环全部顶点
    		while(j < G.numVertexes){
    			//如果权值不为0且权值小于min
    			if(lowcost[j] != 0 && lowcost[j] < min){
    				min = lowcost[j];	//则让当前权值成为最小值
    				k = j;	//将当前最小值的下标存入k
    			}
    			j++;
    		}
    		print("(%d, %d)", adjvex[k], k);	//打印当前顶点边中权值的最小边
    		for(j=1; j<G.numvertexes; j++){
    			//若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
    			if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){
    				lowcost[j] = G.arc[k][j];	//将较小权值存入lowcost
    				adjvex[j] = k;	//将下标为k的顶点存入adjvex
    			}
    		}
    	}
    }
    

    由算法代码中的循环嵌套可得知此算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

    二、克鲁斯卡尔(Kruskal)算法

    与Prim算法从顶点开始扩展最小生成树不同,Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

    Kruskal算法构造最小生成树的过程如下图所示。初始时为只有n个顶点而无边的非连通图 T = V , T= {V, {}} T=V,,每个顶点自成一个连通分量,然后按照边的权值由小到大的顺序,不断选取当前未被选取过且权值最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入 T T T,否则舍弃此边而选择下一条权值最小的边。以此类推,直至 T T T中所有顶点都在一个连通分量上。
    在这里插入图片描述
    算法思路:
    我们可以直接就以边为目标去构建,因为权值是在边上,直接去找最小权值的边来构建生成树也是很自然的想法,只不过构建时要考虑是否会形成环路而已。此时我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码:

    /*对边集数组Edge结构的定义*/
    typedef struct{
    	int begin;
    	int end;
    	int weight;
    }Edge;
    

    我们将下面左图的邻接矩阵通过程序转化为右图的边集数组,并且对它们按权值从小到大排序。
    在这里插入图片描述
    于是Kruskal算法代码如下,左侧数字为行号。其中MAXEDGE为边数量的极大值,此处大于等于15即可,MAXVEX为顶点个数最大值,此处大于等于9即可。

    /*Kruskar算法生成最小生成树*/
    void MiniSpanTree_Kruskal(MGraph G){
    	int i, n, m;
    	Edge edges[MAXEDGE];	//定义边集数组
    	int parent[MAXVEX];	//定义一数组用来判断边与边是否形成环路
    	/*此处省略将邻接矩阵G转化为边集数组edges并按照权由小到大排序的代码*/
    	for(i=0; i<G.numVertexes; i++){
    		parent[i] = 0;	//初始化数组为0
    	}
    	for(i=0; i<G.numVertexes; i++){
    		n = Find(parent, edges[i].begin);
    		m = Find(parent, edge[i],end);
    		/*假如n与m不等,说明此边没有与现有生成树形成环路*/
    		if(n != m){
    		/*将此边的结尾顶点放入下标为起点的parent中
    		表示此顶点已经在生成树集合中*/
    		parent[n] = m;
    		printf("(%d, %d, %d)", edges[i].begin, 
    						edges[i].end, edges[i].weight);
    		}
    	}
    }
    
    /*查找连线顶点的尾部下标*/
    int Find(int *parent, int f){
    	while(parent[f] > 0){
    		f = parent[f];
    	}
    	return f;
    }
    

    此算法的Find函数由边数e决定,时间复杂度为 O ( l o g e ) O(loge) O(loge),而外面有一个for循环e次。所以克鲁斯卡尔算法的时间复杂度为 O ( e l o g e ) O(eloge) O(eloge)
    对比两个算法,克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势;而普里姆算法对于稠密图,即边数非常多的情况会更好一些。

    最短路径

    在网图和非网图中,最短路径的含义是不同的。由于非网图它没有边上的权值,所谓的最短路径,其实就是指两顶点之间经过的边数最少的路径;而对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点是源点,最后一个顶点是终点。

    一、迪杰斯特拉( Dijkstra )算法

    Dijkstra算法用于构建单源点的最短路径—,即图中某个点到任何其他点的距离都是最短的。例如,构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图,但是不能存在负权值。
    在这里插入图片描述

    我们以上图为例,通俗点说,这个迪杰斯特拉(Dijkstra) 算法,它并不是一下子求出了 v 0 v_0 v0 v 8 v_8 v8的最短路径,而是一步步求出它们之间顶点的最短路径,过程中都是基于已经求出的最短路径的基础上,求得更远顶点的最短路径,最终得到你要的结果

    Dijkstra算法设置一个集合S记录已求得的最短路径的顶点。
    在构造的过程中还设置了个辅助数组:
    dist[]:记录从源点 v 0 v_0 v0到其他各顶点当前的最短路径长度,它的初态为:若从 v 0 v_0 v0 v i v_i vi;有弧,则dist[i]为弧上的权值;否则置dist[i]为 ∞ ∞
    在这里插入图片描述
    例如,对图6.17中的图应用 Dijkstra算法求从顶点1出发至其余顶点的最短路径的过程,如表6.1所示。算法执行过程的说明如下。

    • 初始化:集合S初始为 v 1 {v_1} v1 v 1 v_1 v1可达 v 2 v_2 v2 v 5 v_5 v5 v 1 v_1 v1不可达 v 3 v_3 v3 v 4 v_4 v4,因此dist[]数组各元素的初值依次设置为dist[2]=10,dist[3]= ∞ ∞ ,dist[4]= ∞ ∞ ,dist[5]=5。
    • 第一轮:选出最小值dist[5],将顶点 v 5 v_5 v5并入集合 S S S,即此时已找到 v 1 v_1 v1 ν 5 ν_5 ν5的最短路径。当 v 5 v_5 v5加入 S S S后,从 v 1 v_1 v1到集合 S S S中可达顶点的最短路径长度可能会产生变化。因此需要更新dist[]数组。 v 5 v_5 v5可达 v 2 v_2 v2,因 v 1 → v 5 → v 2 v_1→v_5→v_2 v1v5v2的距离8比dist[2]=10小,更新dist[2]=8; v 5 v_5 v5可达 v 3 v_3 v3 v 1 → v 5 → v 3 v_1→v_5→v_3 v1v5v3的距离14,更新dist[3]=14; v 5 v_5 v5可达 v 4 v_4 v4 v 1 → v 5 → v 4 v_1→v_5→v_4 v1v5v4的距离7,更新dist[4]=7。
    • 第二轮:选出最小值dist[4],将顶点 ν 4 ν_4 ν4并入集合 S S S。继续更新dist[]数组。 ν 4 ν_4 ν4不可达 v 2 v_2 v2,dist[2]不变; v 4 v_4 v4可达 v 3 v_3 v3 v 1 → v 5 → v 4 → v 3 v_1→v_5→v_4→v_3 v1v5v4v3的距离13比dist[3]小,故更新dist[3]=13。
    • 笫三轮:选出最小值dist[2],将顶点 ν 2 ν_2 ν2并入集合 S S S。继续更新dist[]数组。 v 2 v_2 v2可达 ν 3 ν_3 ν3 v 1 → v 5 → v 2 → v 3 v_1→v_5→v_2→v_3 v1v5v2v3的距离9比dist[3]小,更新dist[3]=9。
    • 第四轮:选出唯一最小值dist[3],将顶点 v 3 v_3 v3并入集合 S S S,此时全部顶点都已包含在 S S S中。

    显然,Dijkstra 算法也是基于贪心策略的。使用邻接矩阵或者带权的邻接表表示时,时间复杂度为 O ( V 2 ) O(V^2) O(V2)
    人们可能只希望找到从源点到某个特定顶点的最短路径,但这个问题和求解源点到其他所有顶点的最短路径一样复杂,时间复杂度也为 O ( V 2 ) O(V^2) O(V2)

    二、弗洛伊德( Floyd )算法

    定义一个n阶方阵序列 A ( − 1 ) , A ( 0 ) , . . . , A ( n − 1 ) A^{(-1)},A^{(0)},...,A^{(n-1)} A(1),A(0),...,A(n1),其中, A ( − 1 ) [ i ] [ j ] = a r c s [ i ] [ j ] A^{(-1)}[i][j] = arcs[i][j] A(1)[i][j]=arcs[i][j] A ( k ) [ i ] [ j ] = M i n { A ( k − 1 ) [ i ] [ j ] , A ( k − 1 ) [ i ] [ k ] + A ( k − 1 ) [ k ] [ j ] , k = 0 , 1 , . . . , n − 1 } A^{(k)}[i][j] = Min\{A^{(k-1)}[i][j],A^{(k-1)}[i][k]+A^{(k-1)}[k][j],k=0,1,...,n-1\} A(k)[i][j]=Min{A(k1)[i][j],A(k1)[i][k]+A(k1)[k][j],k=0,1,...,n1}式中, A ( 0 ) [ i ] [ j ] A^{(0)}[i][j] A(0)[i][j]是从顶点 v i v_i vi v j v_j vj、中间顶点的序号不大于k的最短路径的长度。Floyd算法是一个迭代的过程,每迭代一次,在从 v i v_i vi v j v_j vj的最短路径上就多考虑了一个顶点;经过 n n n次迭代后,所得到的 A ( n − 1 ) [ i ] [ j ] A^{(n-1)}[i][j] A(n1)[i][j]就是 v i v_i vi v j v_j vj的最短路径长度,即方阵 A ( n − 1 ) A^{(n-1)} A(n1)中就保存了任意一对顶点之间的最短路径长度。
    在这里插入图片描述
    上图所示为带权有向图 G G G及其邻接矩阵。算法执行过程的说明如下。

    • 初始化:方阵 A ( − 1 ) [ i ] [ j ] = a r c s [ i ] [ j ] A^{(-1)}[i][j] = arcs[i][j] A(1)[i][j]=arcs[i][j]
    • 第一轮:将 v 0 v_0 v0作为中间顶点,对于所有顶点 { i , j } \{i, j\} {i,j},如果有 A − 1 [ i ] [ j ] > A − 1 [ i ] [ 0 ] + A − 1 [ 0 ] [ j ] A^{-1}[i][j] > A^{-1}[i][0] + A^{-1}[0][j] A1[i][j]>A1[i][0]+A1[0][j],则将 A − 1 [ i ] [ j ] A^{-1}[i][j] A1[i][j]更新为 A − 1 [ i ] [ 0 ] + A − 1 [ 0 ] [ j ] A^{-1}[i][0] + A^{-1}[0][j] A1[i][0]+A1[0][j]。有 A − 1 [ 2 ] [ 1 ] > A − 1 [ 2 ] [ 0 ] + A − 1 [ 0 ] [ 1 ] = 11 A^{-1}[2][1] > A^{-1}[2][0] + A^{-1}[0][1] = 11 A1[2][1]>A1[2][0]+A1[0][1]=11,更新 A − 1 [ 2 ] [ 1 ] = 11 A^{-1}[2][1] = 11 A1[2][1]=11,更新后的方阵标记为 A 0 A^0 A0
    • 第二轮:将 v 1 v_1 v1作为中间顶点,继续监测全部顶点对 { i , j } \{i, j\} {i,j}。有 A 0 [ 0 ] [ 2 ] > A 0 [ 0 ] [ 1 ] + A 0 [ 1 ] [ 2 ] = 10 A^{0}[0][2] > A^{0}[0][1] + A^{0}[1][2] = 10 A0[0][2]>A0[0][1]+A0[1][2]=10,更新后的方阵标记为 A 1 A^1 A1
    • 第三轮:将 v 2 v_2 v2作为中间顶点,继续监测全部顶点对 { i , j } \{i, j\} {i,j}。有 A 1 [ 1 ] [ 0 ] > A 1 [ 1 ] [ 2 ] + A 1 [ 2 ] [ 0 ] = 9 A^{1}[1][0] > A^{1}[1][2] + A^{1}[2][0] = 9 A1[1][0]>A1[1][2]+A1[2][0]=9,更新后的方阵标记为 A 2 A^2 A2。此时 A 2 A^2 A2中保存的就是任意顶点对的最短路径长度。

    应用Floyd算法求所有顶点之间的最短路径长度的过程如下表所示。
    在这里插入图片描述
    从这个表中,可以发下一些规律:
    在这里插入图片描述
    可以看出,矩阵中,每一步中红线划掉的部分都不用考虑计算,只需要计算红线外的部分,节省了计算量。

    Floyd算法的时间复杂度为 O ( V 3 ) O(V^3) O(V3)。不过由于其代码很紧凑,且并不包含 其他复杂的数据结构,因此隐含的常数系数是很小的,即使对于中等规模的输入来说,它仍然是相当有效的。
    Floyd算法允许图中有带负权值的边,但不允许有包含带负权值的边组成的回路。Floyd 算法同样适用于带权无向图,因为带权无向图可视为权值相同往返二重边的有向图。
    也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点,并且在所有边权值均非负时,运行一次 Dijkstra算法,其时间复杂度为 O ( V 3 ) ∗ V = O ( V 3 ) O(V^3)*V = O(V^3) O(V3)V=O(V3)

    在这里插入图片描述


    拓扑排序

    一、定义

    在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网( Activity On VertexNetwork)。
    若用DAG图(有向无环图)表示一个工程,其顶点表示活动,用有向边 < V i , V j > <V_i, V_j> <Vi,Vj>表示活动 V i V_i Vi必须先于活动 V j V_j Vj进行的这样一种关系。在AOV网中,活动 V i V_i Vi是活动 V j V_j Vj的直接前驱,活动 V j V_j Vj是活动 V i V_i Vi的直接后继,这种前驱和后继关系具有传递性,且任何活动 V i V_i Vi不能以它自己作为自己的前驱或后继。
    G = ( V , E ) G=(V,E) G=(V,E)是一个具有n个顶点的有向图, V V V中的顶点序列 V 1 , V 2 , . . . V n V_1, V_2, ... V_n V1,V2,...Vn,满足若从顶点 V i V_i Vi V j V_j Vj有一条路径,则在顶点序列中顶点 V i V_i Vi必在顶点 V j V_j Vj之前。则我们称这样的顶点序列为一个拓扑序列。

    所谓拓扑排序,其实就是对一个有向图构造拓扑序列的过程。每个AOV网都有一个或多个拓扑排序序列。

    二、算法

    对一个AOV网进行拓扑排序的算法有很多,下面介绍比较常用的一种方法的步骤:

    • ①从AOV网中选择一个没有前驱的顶点并输出。
    • ②从网中删除该顶点和所有以它为起点的有向边。
    • ③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了,哪怕是少了一个,也说明这个网存在环(回路),不是AOV网。

    在这里插入图片描述
    上图所示为拓扑排序过程的示例。每一轮选择一个入度为0的顶点并输出,然后删除该顶点和所有以它为起点的有向边,最后得到拓扑排序的结果为 { 1 , 2 , 4 , 3 , 5 } \{1,2, 4, 3,5\} {1,2,4,3,5}
    拓扑排序算法的实现如下:

    bool TopologicalSort(Graph G){
    	InitStack(S);	//初始化栈,存储入度为0的顶点
    	for(int i=0; i<G.vexnum; i++){
    		if(indegree[i] == 0){
    			Push(S, i);	//将所有入度为0的顶点进栈
    		}
    	}
    	int count = 0;	//计数,记录当前已经输出的顶点数
    	while(!IsEmpty(S)){	//栈不空,则存在入度为0的顶点
    		Pop(S, i);	//顶点元素出栈
    		printf("%d ", i);	//输出顶点i
    		count++;
    		for(p=G.vertices[i].finstarc; p; p=p->nextarc){
    			//将所有i指向的顶点的入度减1,并且将入度减为0的顶点压入栈S
    			v = p->adjvex;
    			if(!--indegree[v]){
    				Push(S, v);	//入度为0,则入栈
    			}
    		}
    	}
    	if(count < G.vexnum){
    		return false;	//输出顶点少了,有向图中有回路,排序失败
    	}else{
    		return true;	//拓扑排序成功
    	}
    }
    

    由于输出每个顶点的同时还要删除以它为起点的边,故拓扑排序的时间复杂度为 O ( V + E ) O(V+E) O(V+E)
    此外,利用深度优先遍历也可实现拓扑排序。

    用拓扑排序算法处理AOV网时,应注意以下问题:
    ①入度为零的顶点,即没有前驱活动的或前驱活动都已经完成的顶点,工程可以从这个顶点所代表的活动开始或继续。
    ②若一个顶点有多个直接后继,则拓扑排序的结果通常不唯一;但若各个顶点已经排在一个线性有序的序列中,每个顶点有唯一的前驱后继关系,则拓扑排序的结果是唯一的。
    ③由于AOV网中各顶点的地位平等,每个顶点编号是人为的,因此可以按拓扑排序的结果重新编号,生成AOV网的新的邻接存储矩阵,这种邻接矩阵可以是三角矩阵;但对于一般的图来说,若其邻接矩阵是三角矩阵,则存在拓扑序列;反之则不一定成立。


    关键路径

    一、定义

    拓扑排序主要是为解决一个工程能否顺序进行的问题,但有时我们还需要解决工程完成需要的最短时间问题。
    在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为用边表示活动的网络,简称AOE网。AOE网和AOV网都是有向无环图,不同之处在于它们的边和顶点所代表的含义是不同的,AOE网中的边有权值;而AOV网中的边无权值,仅表示顶点之间的前后关系。
    AOE网具有以下两个性质:

    • ①只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始;
    • ②只有在进入某顶点的各有向边所代表的活动都已结束时,该顶点所代表的事件才能发生。

    在这里插入图片描述
    如上图的AOE网,在AOE网中仅有一个入度为0的顶点,称为开始顶点(源点),它表示整个工程的开始;网中也仅存在一个出度为0的顶点,称为结束顶点(汇点),它表示整个工程的结束。我们把路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最大长度的路径叫关键路径,在关键路径上的活动叫关键活动
    完成整个工程的最短时间就是关键路径的长度,即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间,即若关键活动不能按时完成,则整个工程的完成时间就会延长。因此,只要找到了关键活动,就找到了关键路径,也就可以得出最短完成时间。

    二、算法

    在这里插入图片描述

    在分析算法之前,需要了解几个重要的参数:

    1.事件的最早发生时间 v e ve ve:即顶点 V k V_k Vk的最早发生时期。
    2.事件的最晚发生时间 v l vl vl:即顶点 V k V_k Vk的最晚发生时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期。
    3.活动的最早开始时间 e e e:即弧 a i a_i ai的最早发生时间。
    4.活动的最晚开始时间 l l l:即弧 a i a_i ai的最晚发生时间,也就是不推迟工期的最晚开工时间。
    5.一个活动 a i a_i ai的最迟开始时间 l ( i ) l(i) l(i)和其最早开始时间 e ( i ) e(i) e(i)的差额 d ( i ) = l ( i ) − e ( i ) d(i) =l(i)- e(i) d(i)=l(i)e(i):它是指该活动完成的时间余量,即在不增加完成整个工程所需总时间的情况下,活动 a i a_i ai可以拖延的时间。若一个活动的时间余量为零,则说明该活动必须要如期完成,否则就会拖延整个工程的进度,所以称 l ( i ) − e ( i ) = 0 l(i)- e(i) = 0 l(i)e(i)=0 l ( i ) = e ( i ) l(i)=e(i) l(i)=e(i)的活动 a i a_i ai是关键活动。

    求关键路径的算法步骤如下:

    1. 从源点出发,令 v e ( 源 点 ) = 0 ve(源点)=0 ve()=0, 按拓扑排序求其余顶点的最早发生时间 v e ( ) ve() ve()
    2. 从汇点出发,令 v l ( 汇 点 ) = v e ( 汇 点 ) vl(汇点)= ve(汇点) vl()=ve(),按逆拓扑排序求其余顶点的最迟发生时间 v l ( ) vl() vl()
    3. 根据各顶点的 v e ( ) ve() ve()值求所有弧的最早开始时间 e ( ) e() e()
    4. 根据各顶点的 v l ( ) vl() vl()值求所有弧的最迟开始时间 l ( ) l() l()
    5. 求AOE网中所有活动的差额 d ( ) d() d(), 找出所有 d ( ) = 0 d()=0 d()=0的活动构成关键路径

    在这里插入图片描述
    上图所示为求解关键路径的过程,简单说明如下:

    1. v e ( ) ve() ve():初始 v e ( 1 ) = 0 ve(1)=0 ve(1)=0,在拓扑排序输出顶点的过程中,求得 v e ( 2 ) = 3 ve(2)=3 ve(2)=3 v e ( 3 ) = 2 ve(3)=2 ve(3)=2 v e ( 4 ) = m a x { v e ( 2 ) + 2 , v e ( 3 ) + 4 } = m a x { 5 , 6 } = 6 ve(4)=max\{ve(2)+2, ve(3)+4\} = max\{5, 6\} = 6 ve(4)=max{ve(2)+2,ve(3)+4}=max{5,6}=6 v e ( 5 ) = 6 ve(5) = 6 ve(5)=6 v e ( 6 ) = m a x { v e ( 5 ) + 1 , v e ( 4 ) + 0 , v e ( 3 ) + 3 } = m a x { 7 , 8 , 5 } = 8 ve(6) = max\{ve(5)+1, ve(4)+0, ve(3)+3\} = max\{7, 8, 5\} = 8 ve(6)=max{ve(5)+1,ve(4)+0,ve(3)+3}=max{7,8,5}=8
    2. v l ( ) vl() vl():初始 v l ( 6 ) = 8 vl(6)=8 vl(6)=8,在逆拓扑排序出栈过程之中,求得 v l ( 5 ) = 7 vl(5)=7 vl(5)=7 v l ( 4 ) = 6 vl(4)=6 vl(4)=6 v l ( 3 ) = m i n { v l ( 4 ) − 4 , v l ( 6 ) − 3 } = m i n { 2 , 5 } = 2 vl(3)=min\{vl(4)-4, vl(6)-3\} = min\{2, 5\}=2 vl(3)=min{vl(4)4,vl(6)3}=min{2,5}=2 v l ( 2 ) = m i n { v l ( 5 ) − 3 , v l ( 4 ) − 2 } = m i n { 4 , 4 } = 4 vl(2)=min\{vl(5)-3,vl(4)-2\}=min\{4,4\}=4 vl(2)=min{vl(5)3,vl(4)2}=min{4,4}=4 v l ( 1 ) vl(1) vl(1)必然为 0 0 0而无需再求。
    3. 弧的最早开始时间 e ( ) e() e()等于该弧的起点的顶点的 v e ( ) ve() ve(),求得结果如上表所示。
    4. 弧的最迟开始时间 l ( i ) l(i) l(i)等于该弧的终点的顶点的 v l ( ) vl() vl()减去该弧持续的时间,求得结果如上表所示。
    5. 根据 l ( i ) − e ( i ) = 0 l(i)-e(i)=0 l(i)e(i)=0的关键活动,得到的关键路径为 ( v 1 , v 3 , v 4 , v 6 ) (v_1,v_3,v_4,v_6) (v1,v3,v4,v6)

    对于关键路径,需要注意以下几点:
    ①关键路径上的所有活动都是关键活动,它是决定整个工程的关键因素,因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动,因为一旦缩短到一定的程度,该关键活动就可能会变成非关键活动。
    ②网中的关键路径并不唯一,
    且对于有几条关键路径的网,只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

    总结

    图是计算机科学中非常常用的一类数据结构,同时也是最复杂的数据结构了,对它的学习,涉及到顺序表、链表、栈、队列、树等之前学的几乎所有数据结构,所以学习图之前要对这几种数据结构都要有所了解才行。


    附录

    上文链接

    数据结构:树

    下文链接

    数据结构:查找

    专栏

    数据结构专栏

    参考资料

    1、严蔚敏、吴伟民:《数据结构(C语言版)》
    2、程杰:《大话数据结构》
    3、王道论坛:《数据结构考研复习指导》
    4、托马斯·科尔曼等人:《算法导论》

    展开全文
  • 数据结构:树(Tree)【详解

    万次阅读 多人点赞 2021-02-22 10:22:25
    二叉树的顺序存储结构和链式存储结构;二叉树的遍历;线索二叉树的基本概念和构造 树、森林 树的存储结构;森林与二叉树的转换;树和森林的遍历 树与二叉树的应用 二叉排序树;平衡二叉树;哈夫曼树和哈弗编码...

    友情链接:数据结构专栏

    目录

    【知识框架】

    在这里插入图片描述

    一、树的基本概念

    1、树的定义

    树是n(n>=0)个结点的有限集。当n = 0时,称为空树。在任意一棵非空树中应满足:

    1. 有且仅有一个特定的称为根的结点。
    2. 当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,并且称为根的子树。

    显然,树的定义是递归的,即在树的定义中又用到了自身,树是一种递归的数据结构。树作为一种逻辑结构,同时也是一种分层结构,具有以下两个特点:

    1. 树的根结点没有前驱,除根结点外的所有结点有且只有一个前驱。
    2. 树中所有结点可以有零个或多个后继。

    因此n个结点的树中有n-1条边。

    2、基本术语

    下面结合图示来说明一下树的一些基本术语和概念。
    在这里插入图片描述

    1. 考虑结点K。根A到结点K的唯一路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲,而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟。
    2. 树中一个结点的孩子个数称为该结点的度,树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3,树的度为3。
    3. 度大于0的结点称为分支结点(又称非终端结点);度为0(没有子女结点)的结点称为叶子结点(又称终端结点)。在分支结点中,每个结点的分支数就是该结点的度。
    4. 结点的深度、高度和层次。
      结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。双亲在同一层的结点互为堂兄弟,图中结点G与E,F,H,I,J互为堂兄弟。
      结点的深度是从根结点开始自顶向下逐层累加的。
      结点的高度是从叶结点开始自底向上逐层累加的。
      树的高度(或深度)是树中结点的最大层数。图中树的高度为4。
    5. 有序树和无序树。树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。假设图为有序树,若将子结点位置互换,则变成一棵不同的树。
    6. 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。
      注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。
    7. 森林。森林是m (m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给m棵独立的树加上一个结点,并把这m棵树作为该结点的子树,则森林就变成了树。

    注意:上述概念无须刻意记忆, 根据实例理解即可。

    3、树的性质

    树具有如下最基本的性质:

    1. 树中的结点数等于所有结点的度数加1.
    2. 度为 m m m的树中第 i i i层上至多有 m i − 1 m^{i-1} mi1个结点( i > = 1 i>=1 i>=1
    3. 高度为 h h h m m m叉树至多有 ( m h − 1 ) / ( m − 1 ) (m^h-1)/(m-1) (mh1)/(m1)个结点。
    4. 具有 n n n个结点的 m m m叉树的最小高度为 [ l o g m ( n ( m − 1 ) + 1 ) ] [log_m(n(m-1)+1)] [logm(n(m1)+1)]

    二、树的存储结构

    在介绍以下三种存储结构的过程中,我们都以下面这个树为例子。
    在这里插入图片描述

    1、双亲表示法

    我们假设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。也就是说,每个结点除了知道自已是谁以外,还知道它的双亲在哪里。
    在这里插入图片描述
    其中data是数据域,存储结点的数据信息。而parent是指针域,存储该结点的双亲在数组中的下标。
    以下是我们的双亲表示法的结点结构定义代码。

    /*树的双亲表示法结点结构定义*/
    #define MAX_TREE_SIZE 100
    typedef int TElemType;	//树结点的数据类型,目前暂定为整型
    /*结点结构*/
    typedef struct PTNode{
    	TElemType data;	//结点数据
    	int parent;	//双亲位置
    }PTNode;
    /*树结构*/
    typedef struct{
    	PTNode nodes[MAX_TREE_SIZE];	//结点数组
    	int r, n;	//根的位置和结点数
    }PTree;
    

    这样的存储结构,我们可以根据结点的parent 指针很容易找到它的双亲结点,所用的时间复杂度为0(1),直到parent为-1时,表示找到了树结点的根。可如果我们要知道结点的孩子是什么,对不起,请遍历整个结构才行。

    2、孩子表示法

    具体办法是,把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针又组成-一个线性表,采用顺序存储结构,存放进一个一维数组中,如图所示。
    在这里插入图片描述
    为此,设计两种结点结构,一个是孩子链表的孩子结点。
    在这里插入图片描述
    其中child是数据域,用来存储某个结点在表头数组中的下标。next 是指针域,用来存储指向某结点的下一个孩子结点的指针。

    另一个是表头数组的表头结点。
    在这里插入图片描述
    其中data是数据域,存储某结点的数据信息。firstchild 是头指针域,存储该结点的孩子链表的头指针。

    以下是我们的孩子表示法的结构定义代码。

    /*树的孩子表示法结构定义*/
    #define MAX_TREE_SIZE 100
    /*孩子结点*/
    typedef struct CTNode{
    	int child;
    	struct CTNode *next;
    }*ChildPtr;
    /*表头结点*/
    typedef struct{
    	TElemType data;
    	ChildPtr firstchild;
    }CTBox;
    /*树结构*/
    typedef struct{
    	CTBox nodes[MAX_TREE_SIZE];	//结点数组
    	int r, n;	//根的位置和结点数
    }
    

    这样的结构对于我们要查找某个结点的某个孩子,或者找某个结点的兄弟,只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的,对头结点的数组循环即可。
    但是,这也存在着问题,我如何知道某个结点的双亲是谁呢?比较麻烦,需要整棵树遍历才行,难道就不可以把双亲表示法和孩子表示法综合一下吗? 当然是可以,这个读者可自己尝试结合一下,在次不做赘述。

    3、孩子兄弟表示法

    刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构,如果我们从树结点的兄弟的角度又会如何呢?当然,对于树这样的层级结构来说,只研究结点的兄弟是不行的,我们观察后发现,任意一棵树, 它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。 因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟
    结点的结构如下:
    在这里插入图片描述
    其中data是数据域,firstchild 为指针域,存储该结点的第一个孩子结点的存储地址,rightsib 是指针域,存储该结点的右兄弟结点的存储地址。
    这种表示法,给查找某个结点的某个孩子带来了方便。
    结构定义代码如下。

    /*树的孩子兄弟表示法结构定义*/
    typedef struct CSNode{
    	TElemtype data;
    	struct CSNode *firstchild, *rightsib;
    } CSNode, *CSTree;
    

    于是通过这种结构,我们就把原来的树变成了这个样子:
    在这里插入图片描述

    这不就是个二叉树么?
    没错,其实这个表示法的最大好处就是它把一棵复杂的树变成了一棵二叉树
    接下来,我们详细介绍二叉树。

    二叉树

    一、二叉树的概念

    1、二叉树的定义

    二叉树是另一种树形结构,其特点是每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点),并且二叉树的子树有左右之分,其次序不能任意颠倒。
    与树相似,二叉树也以递归的形式定义。二叉树是n (n≥0) 个结点的有限集合:

    1. 或者为空二叉树,即n=0。
    2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

    二叉树是有序树,若将其左、右子树颠倒,则成为另一棵不同的二叉树。即使树中结点只有一棵子树,也要区分它是左子树还是右子树。二叉树的5种基本形态如图所示。
    在这里插入图片描述

    2、几个特殊的二叉树

    (1)斜树

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

    (2)满二叉树

    一棵高度为 h h h,且含有 2 h − 1 2^h-1 2h1个结点的二叉树称为满二叉树,即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层,并且除叶子结点之外的每个结点度数均为 2 2 2。可以对满二叉树按层序编号:约定编号从根结点(根结点编号为 1 1 1)起,自上而下,自左向右。这样,每个结点对应一个编号,对于编号为i的结点,若有双亲,则其双亲为 i / 2 i/2 i/2,若有左孩子,则左孩子为 2 i 2i 2i;若有右孩子,则右孩子为 2 i + 1 2i+1 2i+1
    在这里插入图片描述

    (3)完全二叉树

    高度为 h h h、有 n n n个结点的二叉树,当且仅当其每个结点都与高度为 h h h的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树,如图所示。其特点如下:
    在这里插入图片描述

    1. i ≤ n / 2 i≤n/2 in/2, 则结点 i i i为分支结点,否则为叶子结点。
    2. 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点,都依次排列在该层最左边的位置上。
    3. 若有度为 1 1 1的结点,则只可能有一个,且该结点只有左孩子而无右孩子(重要特征)。
    4. 按层序编号后,一旦出现某结点(编号为 i i i)为叶子结点或只有左孩子,则编号大于 i i i的结点均为叶子结点。
    5. n n n为奇数,则每个分支结点都有左孩子和右孩子;若 n n n为偶数,则编号最大的分支结点(编号为 n / 2 n/2 n/2)只有左孩子,没有右孩子,其余分支结点左、右孩子都有。

    (4)二叉排序树

    左子树上所有结点的关键字均小于根结点的关键字;右子树上的所有结点的关键字均大于根结点的关键字;左子树和右子树又各是一棵二叉排序树。

    (5)平衡二叉树

    树上任一结点的左子树和右子树的深度之差不超过1。

    3、二叉树的性质

    1. 任意一棵树,若结点数量为 n n n,则边的数量为 n − 1 n-1 n1
    2. 非空二叉树上的叶子结点数等于度为 2 2 2的结点数加 1 1 1,即 n o = n 2 + 1 n_o=n_2+ 1 no=n2+1
    3. 非空二叉树上第 k k k层上至多有 2 k − 1 2^{k-1} 2k1个结点 ( k ≥ 1 ) (k≥1) (k1)
    4. 高度为 h h h的二叉树至多有 2 h − 1 2^h-1 2h1个结点 ( h ≥ 1 ) (h≥1) (h1)
    5. 对完全二叉树按从上到下、从左到右的顺序依次编号 1 , 2.. ∗ , n 1,2..*,n 1,2..,n,则有以下关系:
      • i > 1 i>1 i>1时,结点 i i i的双亲的编号为 i / 2 i/2 i/2,即当 i i i为偶数时, 它是双亲的左孩子;当i为奇数时,它是双亲的右孩子。
      • 2 i ≤ n 2i≤n 2in时,结点 i i i的左孩子编号为 2 i 2i 2i, 否则无左孩子。
      • 2 i + 1 ≤ n 2i+1≤n 2i+1n时,结点 i i i的右孩子编号为 2 i + 1 2i+1 2i+1,否则无右孩子。
      • 结点 i i i所在层次(深度)为 { l o g 2 i } + 1 \{log_2i\}+ 1 {log2i}+1
    6. 具有 n n n ( n > 0 ) (n>0) (n>0)结点的完全二叉树的高度为 { l o g 2 n } + 1 \{log_2n\}+1 {log2n}+1

    4、二叉树的存储结构

    (1)顺序存储结构

    二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为 i i i的结点元素存储在一维数组下标为 i − 1 i-1 i1的分量中。
    依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适,树中结点的序号可以唯一地反映结点之间的逻辑关系,这样既能最大可能地节省存储空间,又能利用数组元素的下标值确定结点在二叉树中的位置,以及结点之间的关系。
    但对于一般的二叉树,为了让数组下标能反映二叉树中结点之间的逻辑关系,只能添加一些并不存在的空结点,让其每个结点与完全二叉树上的结点相对照,再存储到一维数组的相应分量中。然而,在最坏情况下,一个高度为 h h h且只有 h h h个结点的单支树却需要占据近 2 h − 1 2h-1 2h1个存储单元。二叉树的顺序存储结构如图所示,其中0表示并不存在的空结点。
    在这里插入图片描述

    (2)链式存储结构

    既然顺序存储适用性不强,我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域是比较自然的想法,我们称这样的链表叫做二叉链表
    在这里插入图片描述
    其中data是数据域,lchild 和rchild都是指针域,分别存放指向左孩子和右孩子的指针。
    以下是我们的二叉链表的结点结构定义代码。

    /*二叉树的二叉链表结点构造定义*/
    /*结点结构*/
    typedef struct BiTNode{
    	TElemType data;	//结点数据
    	struct BiTNode *lchild, *rchild;	//左右孩子指针
    } BiTNode, *BiTree;
    

    在这里插入图片描述
    容易验证,在含有 n n n个结点的二叉链表中,含有 n + 1 n + 1 n+1个空链域


    二、遍历二叉树

    二叉树的遍历( traversing binary tree )是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

    1、先序遍历

    先序遍历(PreOrder) 的操作过程如下:
    若二叉树为空,则什么也不做,否则,
    1)访问根结点;
    2)先序遍历左子树;
    3)先序遍历右子树。

    在这里插入图片描述
    对应的递归算法如下:

    void PreOrder(BiTree T){
    	if(T != NULL){
    		visit(T);	//访问根节点
    		PreOrder(T->lchild);	//递归遍历左子树
    		PreOrder(T->rchild);	//递归遍历右子树
    	}
    }
    

    2、中序遍历

    中序遍历( InOrder)的操作过程如下:
    若二叉树为空,则什么也不做,否则,
    1)中序遍历左子树;
    2)访问根结点;
    3)中序遍历右子树。

    在这里插入图片描述
    对应的递归算法如下:

    void InOrder(BiTree T){
    	if(T != NULL){
    		InOrder(T->lchild);	//递归遍历左子树
    		visit(T);	//访问根结点
    		InOrder(T->rchild);	//递归遍历右子树
    	}
    }
    

    3、后序遍历

    后序遍历(PostOrder) 的操作过程如下:
    若二叉树为空,则什么也不做,否则,
    1)后序遍历左子树;
    2)后序遍历右子树;
    3)访问根结点。

    在这里插入图片描述
    对应的递归算法如下:

    void PostOrder(BiTree T){
    	if(T != NULL){
    		PostOrder(T->lchild);	//递归遍历左子树
    		PostOrder(T->rchild);	//递归遍历右子树
    		visit(T);	//访问根结点
    	}
    }
    

    三种遍历算法中,递归遍历左、右子树的顺序都是固定的,只是访问根结点的顺序不同。不管采用哪种遍历算法,每个结点都访问一次且仅访问一次,故时间复杂度都是O(n)。在递归遍历中,递归工作栈的栈深恰好为树的深度,所以在最坏情况下,二叉树是有n个结点且深度为n的单支树,遍历算法的空间复杂度为O(n)。

    4、递归算法和非递归算法的转换

    我们以下图的树为例子。
    在这里插入图片描述

    (1)中序遍历的非递归算法

    借助栈,我们来分析中序遍历的访问过程:

    1. 沿着根的左孩子,依次入栈,直到左孩子为空,说明已找到可以输出的结点,此时栈内元素依次为ABD。
    2. 栈顶元素出栈并访问:若其右孩子为空,继续执行步骤2;若其右孩子不空,将右子树转执行步骤1。

    栈顶D出栈并访问,它是中序序列的第一个结点; D右孩子为空,栈顶B出栈并访问; B右孩子不空,将其右孩子E入栈,E左孩子为空,栈顶E出栈并访问; E右孩子为空,栈顶A出栈并访问; A右孩子不空,将其右孩子C入栈,C左孩子为空,栈顶C出栈并访问。由此得到中序序列DBEAC。
    根据分析可以写出中序遍历的非递归算法如下:

    void InOrder2(BiTree T){
    	InitStack(S);	//初始化栈S
    	BiTree p = T;	//p是遍历指针
    	while(p || !IsEmpty(S)){	//栈不空或p不空时循环
    		if(p){
    			Push(S, p);	//当前节点入栈
    			p = p->lchild;	//左孩子不空,一直向左走
    		}else{
    			Pop(S, p);	//栈顶元素出栈
    			visit(p);	//访问出栈结点
    			p = p->rchild;	//向右子树走,p赋值为当前结点的右孩子
    		}
    	}
    }
    

    (2)先序遍历的非递归算法

    先序遍历和中序遍历的基本思想是类似的,只需把访问结点操作放在入栈操作的前面。先序遍历的非递归算法如下:

    void PreOrder2(BiTree T){
    	InitStack(S);	//初始化栈S
    	BiTree p = T;	//p是遍历指针
    	while(p || !IsEmpty(S)){	//栈不空或p不空时循环
    		if(p){
    			visit(p);	//访问出栈结点
    			Push(S, p);	//当前节点入栈
    			p = p->lchild;	//左孩子不空,一直向左走
    		}else{
    			Pop(S, p);	//栈顶元素出栈
    			p = p->rchild;	//向右子树走,p赋值为当前结点的右孩子
    		}
    	}
    }
    

    (3)后序遍历的非递归算法

    后序遍历的非递归实现是三种遍历方法中最难的。因为在后序遍历中,要保证左孩了和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点,这就为流程的控制带来了难题。

    算法思想:后序非递归遍历二叉树是先访问左子树,再访问右子树,最后访问根结点。

    1. 沿着根的左孩子,依次入栈,直到左孩子为空。此时栈内元素依次为ABD。
    2. 读栈顶元素:若其右孩子不空且未被访问过,将右子树转执行①;否则,栈顶元素出栈并访问。

    栈顶D的右孩子为空,出栈并访问,它是后序序列的第一个结点;栈顶B的右孩子不空且未被访问过,E入栈,栈顶E的左右孩子均为空,出栈并访问;栈顶B的右孩子不空但已被访问,B出栈并访问;栈项A的右孩子不空且未被访问过,C入栈,栈项C的左右孩子均为空,出栈并访问;栈顶A的右孩子不空但已被访问,A出栈并访问。由此得到后序序列DEBCA。
    在上述思想的第②步中,必须分清返回时是从左子树返回的还是从右子树返回的,因此设定一个辅助指针r,指向最近访问过的结点。也可在结点中增加一个标志域,记录是否已被访问。

    后序遍历的非递归算法如下:

    void PostOrder2(BiTree T){
    	InitStack(S);
    	p = T;
    	r = NULL;
    	while(p || !IsEmpty(S)){
    		if(p){	//走到最左边
    			push(S, p);
    			p = p->lchild;
    		}else{	//向右
    			GetTop(S, p);	//读栈顶元素(非出栈)
    			//若右子树存在,且未被访问过
    			if(p->rchild && p->rchild != r){
    				p = p->rchild;	//转向右
    				push(S, p);	//压入栈
    				p = p->lchild;	//再走到最左
    			}else{	//否则,弹出结点并访问
    				pop(S, p);	//将结点弹出
    				visit(p->data);	//访问该结点
    				r = p;	//记录最近访问过的结点
    				p = NULL;
    			}
    		}
    	}
    }
    

    5、层次遍历

    下图为二叉树的层次遍历,即按照箭头所指方向,按照1,2,3, 4的层次顺序,对二叉树中的各个结点进行访问。
    在这里插入图片描述

    要进行层次遍历,需要借助一个队列。先将二叉树根结点入队,然后出队,访问出队结点,若它有左子树,则将左子树根结点入队;若它有右子树,则将右子树根结点入队。然后出队,访问出队结…如此反复,直至队列为空。
    二叉树的层次遍历算法如下:

    void LevelOrder(BiTree T){
    	InitQueue(Q);	//初始化辅助队列
    	BiTree p;
    	EnQueue(Q, T);	//将根节点入队
    	while(!IsEmpty(Q)){	//队列不空则循环
    		DeQueue(Q, p);	//队头结点出队
    		visit(p);	//访问出队结点
    		if(p->lchild != NULL){
    			EnQueue(Q, p->lchild);	//左子树不空,则左子树根节点入队
    		}
    		if(p->rchild != NULL){
    			EnQueue(Q, p->rchild);	//右子树不空,则右子树根节点入队
    		}
    	}
    }
    

    6、由遍历序列构造二叉树

    由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。
    在先序遍历序列中,第一个结点一定是二叉树的根结点;而在中序遍历中,根结点必然将中序序列分割成两个子序列,前一个子序列是根结点的左子树的中序序列,后一个子序列是根结点的右子树的中序序列。根据这两个子序列,在先序序列中找到对应的左子序列和右子序列。在先序序列中,左子序列的第一个结点是左子树的根结点,右子序列的第一个结点是右子树的根结点。
    如此递归地进行下去,便能唯一地确定这棵二叉树
    同理,由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。
    因为后序序列的最后一个结点就如同先序序列的第一个结点,可以将中序序列分割成两个子序列,然后采用类似的方法递归地进行划分,进而得到一棵二叉树。
    由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。
    要注意的是,若只知道二叉树的先序序列和后序序列,则无法唯一确定一棵二叉树。
    例如,求先序序列( ABCDEFGH)和中序序列( BCAEDGHFI)所确定的二叉树
    首先,由先序序列可知A为二叉树的根结点。中序序列中A之前的BC为左子树的中序序列,EDGHFI为右子树的中序序列。然后由先序序列可知B是左子树的根结点,D是右子树的根结点。以此类推,就能将剩下的结点继续分解下去,最后得到的二叉树如图©所示。
    在这里插入图片描述

    三、线索二叉树

    1、线索二叉树原理

    遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列,从而得到几种遍历序列,使得该序列中的每个结点(第一个和最后一个结点除外)都有一个直接前驱和直接后继。
    传统的二叉链表存储仅能体现一种父子关系,不能直接得到结点在遍历中的前驱或后继。
    在这里插入图片描述
    首先我们要来看看这空指针有多少个呢?对于一个有n个结点的二叉链表,每个结点有指向左右孩子的两个指针域,所以一共是2n个指针域。而n个结点的二叉树一共有n-1 条分支线数,也就是说,其实是存在2n- (n-1) =n+1个空指针域。

    由此设想能否利用这些空指针来存放指向其前驱或后继的指针?这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。
    我们把这种指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树(Threaded Binary Tree)。

    其结点结构如下所示:
    在这里插入图片描述
    其中

    • ltag为0时指向该结点的左孩子,为1时指向该结点的前驱。
    • rtag为0时指向该结点的右孩子,为1时指向该结点的后继。

    因此对于上图的二叉链表图可以修改为下图的样子。
    在这里插入图片描述

    2、线索二叉树的结构实现

    二叉树的线索存储结构代码如下:

    typedef struct ThreadNode{
    	ElemType data;	//数据元素
    	struct ThreadNode *lchild, *rchild;	//左、右孩子指针
    	int ltag, rtag;	//左、右线索标志
    }ThreadNode, *ThreadTree;
    

    3、二叉树的线索化

    二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到,因此线索化的实质就是遍历一次二叉树,线索化的过程就是在遍历的过程中修改空指针的过程。

    (1)中序线索二叉树

    以中序线索二叉树的建立为例。附设指针pre指向刚刚访问过的结点,指针p指向正在访问的结点,即pre指向p的前驱。在中序遍历的过程中,检查p的左指针是否为空,若为空就将它指向pre;检查pre的右指针是否为空,若为空就将它指向p,如下图所示。
    在这里插入图片描述
    通过中序遍历对二叉树线索化的递归算法如下:

    void InThread(ThreadTree p, ThreadTree pre){
    	if(p != NULL){
    		InThread(p->lchild, pre);	//递归,线索化左子树
    		if(p->lchild == NULL){	//左子树为空,建立前驱线索
    			p->lchild = pre;
    			p->ltag = 1;
    		}
    		if(pre != NULL && pre->rchild == NULL){
    			pre->rchild = p;	//建立前驱结点的后继线索
    			pre->rtag = 1;
    		}
    		pre = p;	//标记当前结点成为刚刚访问过的结点
    		InThread(p->rchild, pre);	//递归,线索化右子树
    	}
    }
    

    你会发现,除了中间的代码,和二叉树中序遍历的递归代码几乎完全一样。只不过将本是访问结点的功能改成了线索化的功能。

    通过中序遍历建立中序线索二叉树的主过程算法如下:

    void CreateInThread(ThreadTree T){
    	ThreadTree pre = NULL;
    	if(T != NULL){
    		InThread(T, pre);	//线索化二叉树
    		pre->rchild = NULL;	//处理遍历的最后一个结点
    		pre->rtag = 1;
    	}
    }
    

    为了方便,可以在二叉树的线索链表上也添加一个头结点,令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域指针均指向头结点。这好比为二叉树建立了一个双向线索链表,方便从前往后或从后往前对线索二叉树进行遍历,如下图所示。
    在这里插入图片描述
    遍历的代码如下:

    /*T指向头结点,头结点左链lchild指向根结点,头结点右链rchild指向中序遍
    的最后一个结点。中序遍历二叉线索链表表示的二叉树T*/
    void InOrderTraverse_Thr(BiThrTree T){
    	BiThrTree p;
    	p = T->lchild;	//p指向根结点
    	//空树或遍历结束时,p==T(最后一个结点指向根结点)
    	while(p != T){	
    		//当ltag==0时循环到中序序列第一个结点
    		while(p->ltag == 0){	
    			p = p->lchild;	//p指向p的左子树
    		}
    		visit(p);	//访问该结点
    		//后继线索为1且不是指向头指针
    		while(p->rtag == 1 && p->rchild != T){	
    			p = p->rchild;	//p指向p的后继
    			visit(p);	//访问该节点
    		}
    		//p进至其右子树根,开始对右子树根进行遍历
    		p = p->rchild;	
    	}
    }
    

    从这段代码也可以看出,它等于是一个链表的扫描,所以时间复杂度为0(n)。
    由于它充分利用了空指针域的空间(这等于节省了空间),又保证了创建时的一次遍历就可以终生受用前驱后继的信息(这意味着节省了时间)。所以在实际问题中,如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表的存储结构就是非常不错的选择。

    (2)先序和后序线索二叉树

    上面给出了建立中序线索二叉树的代码,建立先序线索二叉树和后序线索二叉树的代码类似,只需变动线索化改造的代码段与调用线索化左右子树递归函数的位置。
    以图(a)的二叉树为例,其先序序列为ABCDF,后序序列为CDBFA,可得出其先序和后序线索二叉树分别如图(b)和( c)所示:
    在这里插入图片描述
    如何在先序线索二叉树中找结点的后继?如果有左孩子,则左孩子就是其后继;如果无左孩子但有右孩子,则右孩子就是其后继;如果为叶结点,则右链域直接指示了结点的后继。
    在后序线索二叉树中找结点的后继较为复杂,可分3种情况:①若结点x是二叉树的根,则其后继为空;②若结点x是其双亲的右孩子,或是其双亲的左孩子且其双亲没有右子树,则其后继即为双亲;③若结点x是其双亲的左孩子,且其双亲有右子树,则其后继为双亲的右子树上按后序遍历列出的第一个结点。图( c)中找结点B的后继无法通过链域找到,可见在后序线索二叉树上找后继时需知道结点双亲,即需采用带标志域的三叉链表作为存储结构。

    四、树、森林与二叉树的转化

    在讲树的存储结构时,我们提到了树的孩子兄弟法可以将一棵树用二叉链表进行存储,所以借助二叉链表,树和二叉树可以相互进行转换。从物理结构来看,它们的二叉链表也是相同的,只是解释不太一样而已。 因此,只要我们设定一定的规则,用二叉树来表示树,甚至表示森林都是可以的,森林与二叉树也可以互相进行转换。

    1、树转换为二叉树

    树转换为二义树的规则:每个结点左指针指向它的第一个孩子,右指针指向它在树中的相邻右兄弟,这个规则又称“左孩子右兄弟”。由于根结点没有兄弟,所以对应的二叉树没有右子树。

    树转换成二叉树的画法:

    1. 在兄弟结点之间加一连线;
    2. 对每个结点,只保留它与第一个孩子的连线,而与其他孩子的连线全部抹掉;
    3. 以树根为轴心,顺时针旋转45°。
      在这里插入图片描述

    2、森林转化为二叉树

    森林是由若干棵树组成的,所以完全可以理解为,森林中的每一棵树都是兄弟,可以按照兄弟的处理办法来操作。
    森林转换成二叉树的画法:

    1. 将森林中的每棵树转换成相应的二叉树;
    2. 每棵树的根也可视为兄弟关系,在每棵树的根之间加一根连线;
    3. 以第一棵树的根为轴心顺时针旋转45°。
      在这里插入图片描述

    至于二叉树转换为树或者二叉树转换为森林只不过是上面步骤的逆过程,在此不做赘述。

    五、树和森林的遍历

    1、树的遍历

    树的遍历是指用某种方式访问树中的每个结点,且仅访问一次。主要有两种方式:

    1. 先根遍历。若树非空,先访问根结点,再依次遍历根结点的每棵子树,遍历子树时仍遵循先根后子树的规则。其遍历序列与这棵树相应二叉树的先序序列相同。
    2. 后根遍历。若树非空,先依次遍历根结点的每棵子树,再访问根结点,遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同。

    下图的树的先根遍历序列为ABEFCDG,后根遍历序列为EFBCGDA。
    在这里插入图片描述
    另外,树也有层次遍历,与二叉树的层次遍历思想基本相同,即按层序依次访问各结点。

    2、森林的遍历

    按照森林和树相互递归的定义,可得到森林的两种遍历方法。

    1. 先序遍历森林。若森林为非空,则按如下规则进行遍历:
      ●访问森林中第一棵树的根结点。
      ●先序遍历第一棵树中根结点的子树森林。
      ●先序遍历除去第一棵树之后剩余的树构成的森林。
    2. 后序遍历森林。森林为非空时,按如下规则进行遍历:
      ●后序遍历森林中第一棵树的根结点的子树森林。
      ●访问第一棵树的根结点。
      ●后序遍历除去第一棵树之后剩余的树构成的森林。

    图5.17的森林的先序遍历序列为ABCDEFGHI,后序遍历序列为BCDAFEHIG。
    在这里插入图片描述
    当森林转换成二叉树时,其第一棵树的子树森林转换成左子树,剩余树的森林转换成右子树,可知森林的先序和后序遍历即为其对应二叉树的先序和中序遍历。

    树与二叉树的应用

    一、二叉排序树

    1、定义

    二叉排序树(也称二叉查找树)或者是一棵空树,或者是具有下列特性的二叉树:

    1. 若左子树非空,则左子树上所有结点的值均小于根结点的值。
    2. 若右子树非空,则右子树上所有结点的值均大于根结点的值。
    3. 左、右子树也分别是一棵二叉排序树。

    根据二叉排序树的定义,左子树结点值<根结点值<右子树结点值,所以对二叉排序树进行中序遍历,可以得到一个递增的有序序列。例如,下图所示二叉排序树的中序遍历序列为123468。
    在这里插入图片描述

    2、二叉排序树的常见操作

    构造一个二叉树的结构:

    /*二叉树的二叉链表结点结构定义*/
    typedef struct BiTNode
    {
    	int data;	//结点数据
    	struct BiTNode *lchild, *rchild;	//左右孩子指针
    } BiTNode, *BiTree;
    

    (1)查找操作

    /*
    递归查找二叉排序树T中是否存在key
    指针f指向T的双亲,其初始调用值为NULL
    若查找成功,则指针p指向该数据元素结点,并返回TRUE
    否则指针p指向查找路径上访问的最后一个结点并返回FALSE
    */
    bool SearchBST(BiTree T, int key, BiTree f, BiTree *p){
    	if(!T){
    		*p = f;
    		return FALSE;
    	}else if(key == T->data){
    		//查找成功
    		*p = T;
    		return TRUE;
    	}else if(key < T->data){
    		return SearchBST(T->lchild, key, T, p);	//在左子树继续查找
    	}else{
    		return SearchBST(T->rchild, key, T, p);	//在右子树继续查找
    	}
    }
    

    (2)插入操作

    有了二叉排序树的查找函数,那么所谓的二叉排序树的插入,其实也就是将关键字放到树中的合适位置而已。

    /*
    当二叉排序树T中不存在关键字等于key的数据元素时
    插入key并返回TRUE,否则返回FALSE
    */
    bool InsertBST(BiTree *T, int key){
    	BiTree p, s;
    	if(!SearchBST(*T, key, NULL, &p)){
    		//查找不成功
    		s = (BiTree)malloc(sizeof(BiTNode));
    		s->data = key;
    		s->lchild = s->rchild = NULL;
    		if(!p){
    			*T = s;	//插入s为新的根节点
    		}else if(key < p->data){
    			p->lchild = s;	//插入s为左孩子
    		}else{
    			p->rchild = s;	//插入s为右孩子
    		}
    		return TRUE;
    		}else{
    			return FALSE;	//树种已有关键字相同的结点,不再插入
    		}
    }
    

    有了二叉排序树的插入代码,我们要实现二叉排序树的构建就非常容易了,几个例子:

    int i;
    int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
    BiTree T = NULL;
    for(i = 0; i<10; i++){
    	InsertBST(&T, a[i]);
    }
    

    上面的代码就可以创建一棵下图这样的树。
    在这里插入图片描述

    (3)删除操作

    二叉排序树的查找和插入都很简单,但是删除操作就要复杂一些,此时要删除的结点有三种情况:

    1. 叶子结点;
    2. 仅有左或右子树的结点;
    3. 左右子树都有的结点;

    前两种情况都很简单,第一种只需删除该结点不需要做其他操作;第二种删除后需让被删除结点的直接后继接替它的位置;复杂就复杂在第三种,此时我们需要遍历得到被删除结点的直接前驱或者直接后继来接替它的位置,然后再删除
    第三种情况如下图所示:
    在这里插入图片描述

    代码如下:

    /*
    若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点,
    并返回TRUE;否则返回FALSE
    */
    bool DeleteBST(BiTree *T, int key){
    	if(!*T){
    		return FALSE; 
    	}else{
    		if(key == (*T)->data){
    			//找到关键字等于key的数据元素
    			return Delete(T);
    		}else if(key < (*T) -> data){
    			return DeleteBST((*T) -> lchild, key);
    		}else{
    			return DeleteBST((*T) -> rchild, key);
    		}
    	}
    }
    

    下面是Delete()方法:

    /*从二叉排序树中删除结点p,并重接它的左或右子树。*/
    bool Delete(BiTree *p){
    	BiTree q, s;
    	if(p->rchild == NULL){
    		//右子树为空则只需重接它的左子树
    		q = *p;
    		*p = (*p)->lchild;
    		free(q);
    	}else if((*p)->lchild == NULL){
    		//左子树为空则只需重接它的右子树
    		q = *p;
    		*p = (*p)->rchild;
    		free(q);
    	}else{
    		//左右子树均不空
    		q = *p;
    		s = (*p)->lchild;	//先转左
    		while(s->rchild){//然后向右到尽头,找待删结点的前驱
    			q = s;
    			s = s->rchild;
    		}
    		//此时s指向被删结点的直接前驱,p指向s的父母节点
    		p->data = s->data;	//被删除结点的值替换成它的直接前驱的值
    		if(q != *p){
    			q->rchild = s->lchild;	//重接q的右子树
    		}else{
    			q->lchild = s->lchild;	//重接q的左子树
    		}
    		pree(s);
    	}
    	return TRUE;
    }
    

    3、小结(引申出平衡二叉树)

    二叉排序树的优点明显,插入删除的时间性能比较好。而对于二叉排序树的查找,走的就是从根结点到要查找的结点的路径,其比较次数等于给定值的结点在二叉排序树的层数。极端情况,最少为1次,即根结点就是要找的结点,最多也不会超过树的深度。也就是说,二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于,二叉排序树的形状是不确定的。
    例如 { 62 , 88 , 58 , 47 , 35 , 73 , 51 , 99 , 37 , 93 } \{62,88,58,47,35,73,51,99,37,93\} {62,88,58,47,35,73,51,99,37,93}这样的数组,我们可以构建如下左图的二叉排序树。但如果数组元素的次序是从小到大有序,如{35,37,47,51,58,62,73,88,93,99},则二叉排序树就成了极端的右斜树,如下面右图的二叉排序树:
    在这里插入图片描述
    也就是说,我们希望二叉排序树是比较平衡的,即其深度与完全二叉树相同,那么查找的时间复杂也就为 O ( l o g n ) O(logn) O(logn),近似于折半查找。
    不平衡的最坏情况就是像上面右图的斜树,查找时间复杂度为 O ( n ) O(n) O(n),这等同于顺序查找。
    因此,如果我们希望对一个集合按二叉排序树查找,最好是把它构建成一棵平衡的二叉排序树


    二、平衡二叉树

    1、定义

    平衡二叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1。
    它是一种高度平衡的二叉排序树。它要么是一棵空树, 要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor) , 那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。
    在这里插入图片描述

    2、平衡二叉树的查找

    在平衡二叉树上进行查找的过程与二叉排序树的相同。因此,在查找过程中,与给定值进行比较的关键字个数不超过树的深度。假设以 n h n_h nh表示深度为 h h h的平衡树中含有的最少结点数。显然,有 n 0 = 0 , n 1 = 1 , n 2 = 2 n_0=0,n_1=1,n_2=2 n0=0,n1=1,n2=2,并且有 n h = n h − 1 + n h − 2 + 1 n_h=n_{h-1}+n_{h-2}+1 nh=nh1+nh2+1。可以证明,含有 n n n个结点的平衡二叉树的最大深度为 O ( l o g 2 n ) O(log2n) O(log2n),因此平衡二叉树的平均查找长度为 O ( l o g 2 n ) O(log2n) O(log2n) 如下图所示。
    在这里插入图片描述

    3、平衡二叉树的插入

    二叉排序树保证平衡的基本思想如下:每当在二叉排序树中插入(或删除)一个结点时,首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡,则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A,再对以A为根的子树,在保持二叉排序树特性的前提下,调整各结点的位置关系,使之重新达到平衡。
    注意:每次调整的对象都是最小不平衡子树,即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。下图中的虚线框内为最小不平衡子树。
    在这里插入图片描述
    平衡二叉树的插入过程的前半部分与二叉排序树相同,但在新结点插入后,若造成查找路径上的某个结点不再平衡,则需要做出相应的调整。可将调整的规律归纳为下列4种情况:

    1. LL平衡旋转(右单旋转)。由于在结点A的左孩子(L)的左子树(L)上插入了新结点,A的平衡因子由1增至2,导致以A为根的子树失去平衡,需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点,将A结点向右下旋转成为B的右子树的根结点,而B的原右子树则作为A结点的左子树。
      如下图所示,结点旁的数值代表结点的平衡因子,而用方块表示相应结点的子树,下方数值代表该子树的高度。
      在这里插入图片描述
    2. RR平衡旋转(左单旋转)。由于在结点A的右孩子®的右子树®上插入了 新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点,将A结点向左下旋转成为B的左子树的根结点,而B的原左子树则作为A结点的右子树。
      在这里插入图片描述
    3. LR平衡旋转(先左后右双旋转)。由于在A的左孩子(L)的右子树®上插入新结点,A的平衡因子由1增至2,导致以A为根的子树失去平衡,需要进行两次旋转操作,先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置(即进行一次RR平衡旋转(左单旋转)),然后再把该C结点向右上旋转提升到A结点的位置(即进行一次LL平衡旋转(右单旋转))。在这里插入图片描述
    4. RL平衡旋转(先右后左双旋转)。由于在A的右孩子®的左子树(L)上插入新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要进行两次旋转操作,先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置(即进行一次LL平衡旋转(右单旋转)),然后再把该C结点向左上旋转提升到A结点的位置(即进行一次RR平衡旋转(左单旋转))。在这里插入图片描述
      注意: LR和RL旋转时,新结点究竟是插入C的左子树还是插入C的右子树不影响旋转过程,而上图中是以插入C的左子树中为例。

    举个例子:
    假设关键字序列为 15 , 3 , 7 , 10 , 9 , 8 {15,3, 7, 10, 9, 8} 15,3,7,10,9,8,通过该序列生成平衡二叉树的过程如下图所示。
    在这里插入图片描述

    二叉排序树还有另外的平衡算法,如红黑树(Red Black Tree)等,与平衡二叉树(AVL树)相比各有优势。


    三、哈夫曼树和哈夫曼编码

    1、哈夫曼树的定义和原理

    在许多应用中,树中结点常常被赋予一个表示某种意义的数值,称为该结点的。从树的根到任意结点的路径长度(经过的边数)与该结点上权值的乘积,称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度,记为 W P L = ∑ i = 1 n w i l i WPL = \displaystyle\sum_{i=1}^{n} w_il_i WPL=i=1nwili式中, w i w_i wi是第i个叶结点所带的权值, l i l_i li是该叶结点到根结点的路径长度。
    在含有n个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树。例如,下图中的3棵二叉树都有4个叶子结点a, b,c,d,分别带权7,5,2,4,它们的带权路径长度分别为
    在这里插入图片描述
    a. WPL = 7x2 + 5x2 + 2x2 + 4x2 = 36。
    b. WPL = 4x2 + 7x3 + 5x3 + 2x1 = 46。
    c. WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35。
    其中,图c树的WPL最小。可以验证,它恰好为哈夫曼树。

    2、哈夫曼树的构造

    步骤:

    1. 先把有权值的叶子结点按照从大到小(从小到大也可以)的顺序排列成一个有序序列。
    2. 取最后两个最小权值的结点作为一个新节点的两个子结点,注意相对较小的是左孩子。
    3. 用第2步构造的新结点替掉它的两个子节点,插入有序序列中,保持从大到小排列。
    4. 重复步骤2到步骤3,直到根节点出现。

    看图就清晰了,如下图所示:
    在这里插入图片描述

    3、哈夫曼编码

    赫夫曼当前研究这种最优树的目的是为了解决当年远距离通信(主要是电报)的数据传输的最优化问题。
    哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。
    比如我们有一段文字内容为“ BADCADFEED”要网络传输给别人,显然用二进制的数字(0和1)来表示是很自然的想法。我们现在这段文字只有六个字母ABCDEF,那么我们可以用相应的二进制数据表示,如下表所示:
    在这里插入图片描述
    这样按照固定长度编码编码后就是“001000011010000011101100100011”,对方接收时可以按照3位一分来译码。如果一篇文章很长,这样的二进制串也将非常的可怕。而且事实上,不管是英文、中文或是其他语言,字母或汉字的出现频率是不相同的。
    假设六个字母的频率为A 27,B 8,C 15,D 15,E 30,F 5,合起来正好是
    100%。那就意味着,我们完全可以重新按照赫夫曼树来规划它们。
    下图左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0,右分支改为1后的赫夫曼树。
    在这里插入图片描述
    这棵哈夫曼树的WPL为:
    W P L = 2 ∗ ( 15 + 27 + 30 ) + 3 ∗ 15 + 4 ∗ ( 5 + 8 ) = 241 WPL=2*(15+27+30) + 3*15 + 4*(5+8)=241 WPL=2(15+27+30)+315+4(5+8)=241
    此时,我们对这六个字母用其从树根到叶子所经过路径的0或1来编码,可以得到如下表所示这样的定义。
    在这里插入图片描述
    若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。
    我们将文字内容为“ BADCADFEED”再次编码,对比可以看到结果串变小了。

    • 原编码二进制串: 000011000011101100100011 (共 30个字符)
    • 新编码二进制串: 10100101010111100(共25个字符)

    也就是说,我们的数据被压缩了,节约了大约17%的存储或传输成本。

    注意:
    0和1究竟是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的,所以构造出的哈夫曼树并不唯一,但各哈夫曼树的带权路径长度WPL相同且为最优。此外,如有若干权值相同的结点,则构造出的哈夫曼树更可能不同,但WPL必然相同且是最优的。


    附录

    上文链接

    数据结构:串

    下文链接

    数据结构:图

    专栏

    数据结构专栏

    参考资料

    1、严蔚敏、吴伟民:《数据结构(C语言版)》
    2、程杰:《大话数据结构》
    3、王道论坛:《数据结构考研复习指导》
    4、托马斯·科尔曼等人:《算法导论》

    展开全文
  • 数据结构与算法—队列详解

    千次阅读 2019-08-16 01:18:41
    栈和队列是一对好兄弟,前面我们介绍过数据结构与算法—栈详解,那么栈的机制相对简单,后入先出,就像进入一个狭小的山洞,山洞只有一个出口,只能后进先出(在外面的先出去)。而队列就好比是一个隧道,后面的人跟着...
  • 数据结构:栈和队列(Stack & Queue)【详解

    万次阅读 多人点赞 2021-02-18 19:52:33
    栈和队列知识框架 栈 一、栈的基本概念 1、栈的定义 ...栈又称为先进先出(Last In First Out)的线性表,简称LIFO结构 2、栈的基本操作 InitStack(&S):初始化一个空栈S。 StackEmpty(S):
  • 《算法和数据结构》学习路线指引

    万次阅读 多人点赞 2021-07-01 11:16:15
    本文已收录于专栏 《画解数据结构》 饭不食,水不饮,题必须刷 C语言免费动漫教程,和我一起打卡! 《光天化日学C语言》 LeetCode 太难?先看简单题! 《C语言入门100例》 数据结构难?不存在的! 《画解数据结构》 ...
  • Redis内部数据结构详解(1)

    千次阅读 2018-01-10 10:36:37
    Redis内部数据结构详解(1)——dict 如果你使用过Redis,一定会像我一样对它的内部实现产生兴趣。《Redis内部数据结构详解》是我准备写的一个系列,也是我个人对于之前研究Redis的一个阶段性总结,着重讲解Redis在...
  • 图结构 非常得类似我们之前讲到过的树结构,但前者没有很多的...在数学的概念中,后者是前者的一种,不过在数据结构中我们还是认为两者有所区别,尽管如此,我们在学习图结构的时候仍可以稍微借鉴一下树结构的思想。
  • 数据结构入门】顺序表(SeqList)详解(初始化、增、删、查、改) 【数据结构入门】无头单向非循环链表(SList)详解(定义、增、删、查、改) | 图解链表,超生动详细哦~ 【数据结构入门】带头双向循环链表(List...
  • 《算法和数据结构》题海战术篇

    万次阅读 多人点赞 2021-07-15 06:13:43
    文章目录 1️⃣前言:追忆我的刷题经历 2️⃣算法和数据结构的重要性 1、适用人群 2、有何作用 3、算法简介 4、数据结构 3️⃣如何开始持续的刷题 1、立军令状 ‍❤️‍2、培养兴趣 3、狂切水题 4、养成习惯 5、一周...
  • 其实树结构是平日里我们常见的一种数据结构,例如家族族谱、公司管理层级结构图等,这样的数据结构的存在一定有一定的道理。因此,在计算机领域中,树结构也是会被广泛用到的,例如数据库系统中就有用到。那么本文就...
  • 递归调用详解(图文并茂)

    千次阅读 2019-04-07 14:33:26
    本文主要依据C程序设计(第四版) 谭浩强著,这本书Hanoi的实例,详细讲解递归调用。 代码如下 #include<stdio.h> void move(int x, int y) { printf("%c--->%c\n", x, y); } void hanoi(int n, ...
  • 根据此书所做随笔笔记。 一、绪论 1.1、数据机构的研究内容 ...由于数据必须在计算机中处理,因此不能局限于数据本身的数学问题的研究,还必须考虑数据的物理结构,即数据在计算机中的存储结构。 1.
  • 数据结构(C语言版)(第2版) 课后习题答案 李冬梅 2015.3 目 录 第1章 绪论 1 第2章 线性表 5 第3章 栈和队列 13 第4章 串、数组和广义表 26 第5章 树和二叉树 33 第6章 图 43 第7章 查找 54 第8章 排序 65 第1章 ...
  • 好进行增容3、顺序表尾插4、顺序表尾删5、顺序表头插6、顺序表头删7、打印顺序表8、在顺序表中查找指定值9、在顺序表指定下标位置插入数据10、在顺序表中删除指定下标位置的数据11、查看顺序表中有效数据个数12、...
  • 本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接 https://github.com/Lpyexplore/structureAndAlgorithm-JS 数组是我们...
  • 数据结构:关于AVL树的平衡旋转详解

    万次阅读 多人点赞 2015-12-28 12:49:20
    如果你还是小白,可以参考我之前的博客:《数据结构:二叉搜索树(BST)的基本操作》。所以,在本文中不会再出现关于BST树的基本知识。 版权说明 著作权归作者所有。 商业转载请联系作者获得授权,非商业转载请...
  • JVM之内存结构详解

    万次阅读 多人点赞 2019-10-18 12:49:05
    对于开发人员来说,如果不了解Java的JVM,那真的是很难写得一手好代码,很难查得一手好bug。同时,JVM也是面试环节的中重灾区。...下面,开启我们的第一篇文章《JVM之内存结构详解》。 学习也是要讲究方式方法...
  • 【图解数据结构】栈全面总结

    千次阅读 多人点赞 2021-12-18 15:32:49
    掌握栈这种抽象数据类型的特点,在相应的实际问题中正确应用 掌握栈类型的两种实现方法 二、基本概念 定义:只允许在一端进行插入或删除的线性表 栈顶(top):允许进行插入或删除的一端 栈底(bottom):与...
  • 栈帧结构详解

    千次阅读 2021-03-25 22:53:40
    Java虚拟机以方法作为基本的执行单位,“栈帧”是用于支持虚拟机进行方法调用和执行的数据结构,每一个方法从调用开始到执行结束,都对应着一个栈帧在虚拟机栈里面从入栈到出栈的过程,栈帧也是虚拟机运行时数据区中...
  • 数据结构--链表的排序详解

    万次阅读 多人点赞 2016-11-18 22:18:26
    1、前言 前面两篇博客,我已经把线性表的两种基本的...2、链表排序—最简单、直接的方式(直接采用冒泡或者选择排序,而且不是交换结点,只交换数据域)//线性表的排序,采用冒泡排序,直接遍历链表 void Listsort(Nod
  • 数据结构:一元多项式计算器(详解

    万次阅读 多人点赞 2020-04-21 22:04:03
    不管会不会,输入是必须的,先把数据读入再说。既然选用了链表存储,用链表来实现,那么我们肯定要考虑到链表的两种形式:带头结点的链表和不带头结点的链表,这两种有什么区别呢? 同时我们还需要了解下面三个概念...
  • MyBatis 调用存储过程(详解)

    万次阅读 多人点赞 2018-08-31 16:20:35
    项目结构 数据表t_user 创建User package com.po; public class User { private Integer id; private String name; private String sex; private Integer age; public Integer getId() { return id; ...
  • 数据结构----BFS和DFS详解

    万次阅读 多人点赞 2017-02-28 19:38:52
    //一个图的结构 struct Graph_List { int vexnum; //图的顶点数 int edge; //图的边数 Vnode * node; //邻接表 int kind; //0,为有向图,1,为无向图 }; //建立邻接表 void createGraph_...
  • Redis内部数据结构详解(4)——ziplist

    万次阅读 多人点赞 2018-01-10 10:49:04
    本文是《Redis内部数据结构详解》系列的第四篇。在本文中,我们首先介绍一个新的Redis内部数据结构——ziplist,然后在文章后半部分我们会讨论一下在robj, dict和ziplist的基础上,Redis对外暴露的hash结构是怎样...
  • 数据结构---拓扑排序详解

    万次阅读 多人点赞 2017-03-06 19:54:41
    一个AOV网应该是一个有向无环图,即不应该带有回路,因为若带有回路,则回路上的所有活动都无法进行(对于数据流来说就是死循环)。在AOV网中,若不存在回路,则所有活动可排列成一个线性序列,使得每个活动的所有...
  • 数据结构之链栈基本操作的实现详解(C语言描述)

    万次阅读 多人点赞 2019-02-01 21:44:31
    1.链栈:就是栈的链式存储结构,简称链栈。 2.首先我们要考虑的就是链栈的存储结构,由于栈只是在栈顶进行插入和删除操作,而且单链表也存在头指针,栈也存在栈顶指针,那么我们能不能想办法让这二者合为一体呢,...
  • Redis的五种数据结构的底层实现原理

    万次阅读 2021-01-31 02:49:22
    Redis的五种数据结构的底层实现原理: 1、String底层实现方式:动态字符串sds 或者 long; 2、Hash底层实现方式:压缩列表ziplist 或者 字典dict; 3、List在Redis3.2之前的底层实现方式:压缩列表ziplist 或者 双向...
  • 单链表尾插法详解

    千次阅读 多人点赞 2020-09-18 19:14:44
    单链表尾插法详解 首先,我们知道单链表的存储结构为: typedef struct LNode{ ElemType data;//数据域 struct LNode *next;//指针域,指向下一个结点 }LNode,*Linklist; //*LinkList是指向LNode这个结构的一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 161,952
精华内容 64,780
关键字:

调用链数据结构详解

数据结构 订阅