精华内容
下载资源
问答
  • //集合:hash分布,元素间没关系,动态增加容量 去重 //统计用户IP;...Console.WriteLine("***************HashSet<string>******************"); HashSet<string> hashSet = new HashSet<...
  • /// 树结构帮助类 /// </summary> public class TreeHelper { #region 外部接口 /// <summary> /// 建造树结构 /// </summary> /// <param name="allNodes">所有的节点</param...
  • //装箱 int i = 1; object obj = (object)i; //拆箱 int j = (int)obj;
  • /// <summary> /// 基数排序 /// </summary> public class Program { public static void Main(string[] args) { int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };...
  • public class Program { public static void Main(string[] args) { int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 }; BinaryTreeSort(array); Console.ReadKey();... public static void ...
  • int kmp(char str[],char temp[])//这个是查找 { int i = 0;//这个是主字符串的位置 int j = 0;//这个是子字符串的位置 int length1 = strlen(str); int length2 = strlen(temp); while (i<...}
  • public class Program { public static void Main(string[] args) { int[] array = { 8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 }; Console.WriteLine(BinarySearch(array, 80)); Console.WriteLine...
  • typedef struct zskiplistNode { //节点对应成员的对象,一般是SDS robj *obj; //分数,跳跃表的顺序按照分值进行排列 double score; //存储后继节点的指针 struct zskiplistNode *backward;...
  • 数据结构 Hash表(哈希表)

    万次阅读 多人点赞 2018-05-20 01:23:34
    参考链接:数据结构(严蔚敏) 什么是Hash表 要想知道什么是哈希表,那得先了解哈希函数 哈希函数 对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出...

    参考链接:数据结构(严蔚敏)
    文章发布很久了,具体细节已经不清晰了,不再回复各种问题
    文章整理自严蔚敏公开课视频
    可以参考
    https://www.bilibili.com/video/av22258871/
    如果链接失效 可以自行搜索 数据结构严蔚敏视频
    @2021/07/12

    一、什么是Hash表

    要想知道什么是哈希表,那得先了解哈希函数
    哈希函数

    对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出数据或索引与查找值进行比较。那么,有没有一种函数H,根据这个函数和查找关键字key,可以直接确定查找值所在位置,而不需要一个个比较。这样就**“预先知道”**key所在的位置,直接找到数据,提升效率。

    地址index=H(key)
    说白了,hash函数就是根据key计算出应该存储地址的位置,而哈希表是基于哈希函数建立的一种查找表

    二、哈希函数的构造方法

    根据前人经验,统计出如下几种常用hash函数的构造方法:
    直接定制法
    哈希函数为关键字的线性函数如 H(key)=a*key+b
    这种构造方法比较简便,均匀,但是有很大限制,仅限于地址大小=关键字集合的情况
    使用举例:
    假设需要统计中国人口的年龄分布,以10为最小单元。今年是2018年,那么10岁以内的分布在2008-2018,20岁以内的分布在1998-2008……假设2018代表2018-2008直接的数据,那么关键字应该是2018,2008,1998……
    那么可以构造哈希函数H(key)=(2018-key)/10=201-key/10
    那么hash表建立如下

    index key 年龄 人数(假设数据)
    0 2018 0-10 200W
    1 2008 10-20 250W
    2 1998 20-30 253W
    3 1988 30-40 300W
    ……

    数字分析法
    假设关键字集合中的每个关键字key都是由s位数字组成(k1,k2,,knk_1,k_2,……,k_n),分析key中的全体数据,并从中提取分布均匀的若干位或他们的组合构成全体

    使用举例
    我们知道身份证号是有规律的,现在我们要存储一个班级学生的身份证号码,假设这个班级的学生都出生在同一个地区,同一年,那么他们的身份证的前面数位都是相同的,那么我们可以截取后面不同的几位存储,假设有5位不同,那么就用这五位代表地址。
    H(key)=key%100000
    此种方法通常用于数字位数较长的情况,必须数字存在一定规律,其必须知道数字的分布情况,比如上面的例子,我们事先知道这个班级的学生出生在同一年,同一个地区。
    平方取中法
    如果关键字的每一位都有某些数字重复出现频率很高的现象,可以先求关键字的平方值,通过平方扩大差异,而后取中间数位作为最终存储地址。
    使用举例
    比如key=1234 1234^2=1522756 取227作hash地址
    比如key=4321 4321^2=18671041 取671作hash地址
    这种方法适合事先不知道数据并且数据长度较小的情况
    折叠法
    如果数字的位数很多,可以将数字分割为几个部分,取他们的叠加和作为hash地址
    使用举例
    比如key=123 456 789
    我们可以存储在61524,取末三位,存在524的位置
    该方法适用于数字位数较多且事先不知道数据分布的情况
    除留余数法用的较多
    H(key)=key MOD p (p<=m m为表长)
    很明显,如何选取p是个关键问题。

    使用举例
    比如我们存储3 6 9,那么p就不能取3
    因为 3 MOD 3 == 6 MOD 3 == 9 MOD 3
    p应为不大于m的质数或是不含20以下的质因子的合数,这样可以减少地址的重复(冲突)

    比如key = 7,39,18,24,33,21时取表长m为9 p为7 那么存储如下

    index 0 1 2 3 4 5 6 7 8
    key 7 21(冲突后移) 24 *39* 18(冲突后移) 33冲突后移)
    **随机数法** H(key) =Random(key) 取关键字的随机函数值为它的散列地址

    hash函数设计的考虑因素

    1.计算散列地址所需要的时间(即hash函数本身不要太复杂)
    2.关键字的长度
    3.表长
    4.关键字分布是否均匀,是否有规律可循
    5.设计的hash函数在满足以上条件的情况下尽量减少冲突

    三、哈希冲突

    即不同key值产生相同的地址,H(key1)=H(key2)
    比如我们上面说的存储3 6 9,p取3是
    3 MOD 3 == 6 MOD 3 == 9 MOD 3
    此时3 6 9都发生了hash冲突

    哈希冲突的解决方案

    不管hash函数设计的如何巧妙,总会有特殊的key导致hash冲突,特别是对动态查找表来说。
    hash函数解决冲突的方法有以下几个常用的方法
    1.开放定制法
    2.链地址法
    3.公共溢出区法
    建立一个特殊存储空间,专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。
    4.再散列法
    准备若干个hash函数,如果使用第一个hash函数发生了冲突,就使用第二个hash函数,第二个也冲突,使用第三个……
    重点了解一下开放定制法和链地址法

    开放定制法

    首先有一个H(key)的哈希函数
    如果H(key1)=H(keyi)
    那么keyi存储位置Hi=(H(key)+di)MODmH_i=(H(key)+d_i)MOD mm为表长
    did_i有三种取法
    1)线性探测再散列
    di=cid_i=c*i
    2)平方探测再散列
    di=12,12,22,22d_i=1^2,-1^2,2^2,-2^2……
    3)随机探测在散列(双探测再散列)
    did_i是一组伪随机数列
    注意
    增量di应该具有以下特点(完备性):产生的Hi(地址)均不相同,且所产生的s(m-1)个Hi能覆盖hash表中的所有地址

    • 平方探测时表长m必须为4j+3的质数(平方探测表长有限制)
    • 随机探测时m和di没有公因子(随机探测di有限制)
      三种开放定址法解决冲突方案的例子

    废话不多说,上例子就明白了
    有一组数据
    19 01 23 14 55 68 11 86 37要存储在表长11的数组中,其中H(key)=key MOD 11
    那么按照上面三种解决冲突的方法,存储过程如下:
    (表格解释:从前向后插入数据,如果插入位置已经占用,发生冲突,冲突的另起一行,计算地址,直到地址可用,后面冲突的继续向下另起一行。最终结果取最上面的数据(因为是最“占座”的数据))
    线性探测再散列
    我们取di=1,即冲突后存储在冲突后一个位置,如果仍然冲突继续向后

    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 14 19 86
    23冲突 23
    68冲突 68冲突 68
    11冲突 11冲突 11冲突 11冲突 11冲突 11
    37冲突 37冲突 37
    最终存储结果 55 1 23 14 68 11 37 19 86
    **平方探测再散列**
    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 14 37 19 86
    23冲突 H(23)+1
    H(68)-1冲突 68冲突 H(68)+1冲突 H(68)+4
    11冲突 H(11)+1冲突 H(11)-1
    最终存储结果 55 1 23 14 37 68 19 86 11
    **随机探测在散列(双探测再散列)** 发生冲突后 H(key)‘=(H(key)+di)MOD m 在该例子中 H(key)=key MOD 11 我们取di=key MOD 10 +1 则有如下结果:
    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 68 14 19 86
    23冲突 H(23)+3+1
    11冲突 H(11)+1+1冲突 H(11)+1+1+1+1
    (H(37)+8)模11冲突 37冲突 (H(37)+8+8+8)模11 (H(37)+8+8)模11冲突
    最终存储结果 55 1 68 14 23 11 37 19 86

    链地址法

    产生hash冲突后在存储数据后面加一个指针,指向后面冲突的数据
    上面的例子,用链地址法则是下面这样:

    这里写图片描述
    四、hash表的查找

    查找过程和造表过程一致,假设采用开放定址法处理冲突,则查找过程为:
    对于给定的key,计算hash地址index = H(key)
    如果数组arr【index】的值为空 则查找不成功
    如果数组arr【index】== key 则查找成功
    否则 使用冲突解决方法求下一个地址,直到arr【index】== key或者 arr【index】==null

    hash表的查找效率

    决定hash表查找的ASL因素:
    1)选用的hash函数
    2)选用的处理冲突的方法
    3)hash表的饱和度,装载因子 α=n/m(n表示实际装载数据长度 m为表长)
    一般情况,假设hash函数是均匀的,则在讨论ASL时可以不考虑它的因素
    hash表的ASL是处理冲突方法和装载因子的函数
    前人已经证明,查找成功时如下结果:

    这里写图片描述
    可以看到无论哪个函数,装载因子越大,平均查找长度越大,那么装载因子α越小越好?也不是,就像100的表长只存一个数据,α是小了,但是空间利用率不高啊,这里就是时间空间的取舍问题了。通常情况下,认为α=0.75是时间空间综合利用效率最高的情况。

    上面的这个表可是特别有用的。假设我现在有10个数据,想使用链地址法解决冲突,并要求平均查找长度<2
    那么有1+α/2 <2
    α<2
    即 n/m<2 (n=10)
    m>10/2
    m>5 即采用链地址法,使得平均查找长度< 2 那么m>5

    之前我的博客讨论过各种树的平均查找长度,他们都是基于存储数据n的函数,而hash表不同,他是基于装载因子的函数,也就是说,当数据n增加时,我可以通过增加表长m,以维持装载因子不变,确保ASL不变。
    那么hash表的构造应该是这样的:

    这里写图片描述
    五、hash表的删除

    首先链地址法是可以直接删除元素的,但是开放定址法是不行的,拿前面的双探测再散列来说,假如我们删除了元素1,将其位置置空,那 23就永远找不到了。正确做法应该是删除之后置入一个原来不存在的数据,比如-1

    展开全文
  • 数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为计算机专业的专业基础课程,是计算机考研的必考科目之一,如果打算报考计算机专业的研究生,你...

    系列文章

    第一章:基础知识

    第二章:线性表

    第三章:栈和队列 

    第四章:字符串和数组

    第五章:树和二叉树

    第六章:图

    第七章:排序算法


    前言

    数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分

    为什么要学数据结构?

    首先,因为数据结构作为计算机专业的专业基础课程,是计算机考研的必考科目之一,如果打算报考计算机专业的研究生,你必须学好它;其次,数据结构是计算机软考、计算机等级考试等相关考试的必考内容之一,想要顺利通过这些考试,你也必须学好它;最后,数据结构还是你打算今后学习计算专业其他课程的基础,如操作系统、编辑原理、数据库管理系统、软件工程、人工智能等。总而言之,你既然已经与计算机接轨就必须掌握好它。

    如何学习数据结构?

    对于初学者来说,数据结构是门概念上比较抽象的课程,不是太容易掌握,需要构思和理解。万事开头难,只要你掌握了学习这门课的方法和技巧,就会变得很容易了。不管学什么,首先应该做好充分的心理准备,建立好自信心,拥有一颗战胜困难的决心,才能不畏惧、不退缩,直至胜利归来。其次,就是最好有C语言基础,这样学起来事半功倍,当然没有C语言基础也行,可以一边学数据结构一边巩固C语言知识。最后,就是多动手!多动手!多动手!重要的事情说三遍!只有亲自动手上机操作或用笔在纸上画画写写才能加深映像,方便理解记忆。?


    第一章:基础知识

    第1节:数据结构概述

      1.1 概念术语

      1.2数据的逻辑结构

      1.3数据的存储(物理)结构

      1.4抽象数据类型

      1.5算法

    1.6时间复杂度

    1.7空间复杂度

    第2节:C语言基础

    2.1 开发环境

    2.2 递归与非递归(重点)

    2.3参数传递

    2.4 结构体和联合体

    2.5 链表

    2.6 内存的分配与释放


     

    第1节:数据结构概述

    数据结构的主要任务是通过分析数据对象的结构特征,包括逻辑结构及数据对象之间的关系,然后把逻辑结构表示成计算机课实现的物理结构,从而便于计算机处理。

     

      1.1 概念术语

    (1)数据(Data)是能被计算机处理的符号或符号集合,含义广泛,可理解为“原材料”。如字符、图片、音视频等。

    (2)数据元素(data element)是数据的基本单位。例如一张学生统计表。

    (3)数据项(data item)组成数据元素的最小单位。例如一张学生统计表,有编号、姓名、性别、籍贯等数据项。

    (4)数据对象(data object)是性质相同的数据元素的集合,是数据的一个子集。例如正整数N={1,2,3,····}。

    (5)数据结构(data structure)是数据的组织形式,数据元素之间存在的一种或多种特定关系的数据元素集合。

    (6)数据类型(data type)是按照数据值的不同进行划分的可操作性。在C语言中还可以分为原子类型和结构类型。原字类型是不可以再分解的基本类型,包括整型、实型、字符型等。结构类型是由若干个类型组合而成,是可以再分解的。

     

      1.2数据的逻辑结构

    逻辑结构(logical structure)是指在数据中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型。

    (1)集合结构:集合的数据元素没有其他关系,仅仅是因为他们挤在一个被称作“集合”的盒子里。

    (2)线性结构:线性的数据元素结构关系是一对一的,并且是一种先后的次序,就像a-b-c-d-e-f-g·····被一根线穿连起来。

    (3)树形结构:树形的数据元素结构关系是一对多的,这就像公司的部门级别,董事长-CEO\CTO-技术部\人事部\市场部.....。

    (4)图结构:图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图,一个城市有很多线路连接不同城市。

     

      1.3数据的存储(物理)结构

    存储结构(storage structure)也称为物理结构(physical structure),指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构一般可以反映数据元素之间的逻辑关系。分为顺序存储结构和链式存储结构。

    (1)顺序存储结构:是把数据元素存放在一组存储地址连续的存储单元里,其数据元素间的逻辑关系和物理关系是一致的。

    (2)链式存储结果:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的,数据元素的存储关系并不能反映其逻辑关系,因此需要借助指针来表示数据元素之间的逻辑关系。

     

    小结:数据的逻辑结构和物理结构是密切相关的,在学习数据的过程中会发现,任何一个算法的设计取决于选定的数据逻辑结构,而算法的实现依赖于所采用的存储结构。

     

      1.4抽象数据类型

    抽象数据类型(abstract data type,ADT)是描述具有某种逻辑关系的数据模型,并对在数学模型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性,与在计算机内部表示无关,计算机中的整数数据类型是一个抽象数据类型,不同处理器可能实现方法不同,但其逻辑特性相同,即加、减、乘、除等运算是一致的。“抽象”的意思是数据类型的数学抽象特性而不是指它们的实现方法。抽象数据类型体现了程序设计中的问题分解、抽象、信息隐藏等特性,可以把现实中的大问题分解为多个规模小且容易处理的小问题,然后建立起一个能被计算机处理的数据,并把每个功能模块的实现细节作为一个独立的单元,从而使具体实现过程隐藏起来。就类似建一栋房子,分成若干个小任务,如地皮规划、图纸设计、施工、装修等,整个过程与抽象数据类型中的问题分解类似。而搬砖人不需要了解图纸设计如何,设计图纸人员不需要了解施工的地基、砌墙的具体细节,装修工人不用关系图纸和搬砖过程,这就是抽象类型中的信息隐藏。

    抽象数据类型的概念可能让初学者不太容易理解。例如线性表的抽象数据类型的描述数据对象集合:线性表的数据对象集合为{a1,a2,a3,····,an},每个元素的类型均为DataType。其中,除了第一个元素a1外,每一个元素有且只有一个直接前驱元素;除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的。

     

      1.5算法

    算法(algorithm)是解决特定问题求解步骤的描述,在计算机中表现为有限的操作序列。在数据类型建立起来之后,就要对这些数据类型进行操作,建立起运算的集合即程序。运算的建立、方法好坏直接决定着计算机程序原型效率的高低。

    (1)数据结构和算法的关系

    两者基友联系又有区别。联系是程序=算法+数据结构。数据结构是算法实现的基础,算法总是要依赖某种数据结构来实现的。算法的操作对象是数据结构。区别是数据结构关注的是数据的逻辑结构、存储结构有一集基本操作,而算法更多的是关注如何在数据结构的基本上解决实际问题。算法是编程思想,数据结构则是这些思想的基础。

    (2)算法的五大特性

    有穷性,是指算法在执行有限的步骤之后,自动结束而不是出现无限循环,并且每一个步骤在可接受的时间内完成。

    确定性,是指算法执行的每一步骤在一定条件下只有一条执行路径,也就是相同输入只能有一个唯一的输出结果。

    可行性,是指算法每一步骤都必须可行,能够通过有限的执行次数完成。

    输入,是指算法具有零个或多个输入。

    输出,是指算法至少有一个或多个输出。

     

    1.6时间复杂度

    在进行算法分析时,语句总是执行次数 T(n) 是关于问题规模 n 的函数。进而分析次数T(n)随规模n的变化情况并确定T(n)的数量级。算法的时间复杂度就是算法的时间度量,记作T(n) = O(f(n))。它表示随问题规模n的增大,算法的执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中,f(n)是问题规模n的某个函数。

    算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下,随着规模n的增大,次数T(n)的增长较慢的算法为最优算法。常见时间复杂度从小到大依次排列:O(1) < O(log2n) < O(n) < O(n²)<O(n³) ····<O(n!)

    例如:

    (a) 1;      // 时间复杂度为O(1)

    (b)for(i =1 ; i<=n ;i++){  x= x+1;}    // 时间复杂度为O(n),称为线性阶

    (c)for(i =1 ; i<=n ; i++){for(j=1;j<=n;j++){  x=x+1 } }  // 时间复杂度为O(n²),称为平方阶

     

    1.7空间复杂度

    空间复杂度(space complexity)作为算法所需存储空间的量度,记做S(n) = O (f(n))。其中,n为问题的规模;f(n)为语句关于n的所占存储空间的函数。

    一般情况下,一个程序在机器上运行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单位。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常量,则称此算法为原地工作,空间复杂度为O(1)。

     

    第2节:C语言基础

    C语言作为数据结构的算法描述语言,广泛应用于系统软件和应用软件的开发。在真正开发学习数据结构知识之前,先复习一下C语言基础,为数据结构的学习扫清障碍。本节主要针对重点和难点部分详细讲解,包括开发环境、函数与递归、指针、参数传递、动态内存分配及结构体、联合体。

     

    2.1 开发环境

    C语言常见的开发环境有很多种,如LCC、Turbo C2.0、Visual C++、Borland C++,本章主要介绍使用最多的Turbo C 2.0和Visual C++ 6.0。

    (1)Turbo C 2.0 :1989年,美国Borland公司推出,简称TC。它集编辑、编译、连接和运行一体的C程序集成开发环境。界面简单、上手容易、使用方便,通过一个简单的主界面可以很容易编辑、编译和链接程序,也是初学者广发使用的开发工具。

    (2)Visual C++6.0:是强大的C/C++软件开发工具,使用非常广泛,已经成为首选的开发工具。利用它可以开发Windows SDK、MFC等应用程序。

     

    2.2 递归与非递归(重点)

    在数据结构与算法实践过程中,经常会遇到利用递归实现算法的情况。递归是一种分而治之、将复杂问题转换成简单问题的求解方法。使用递归可以使编写的程序简洁、结构清晰,程序的正确性很容易证明,不需要了解递归调用的具体细节。

    (1)函数的递归:就是函数自己调用自己,即一个函数在调用其他函数的过程中,又出现对自身的调用,这种函数称为递归函数。函数的递归调用就是自己调用自己,可以直接调用自己也可以间接调用。其中,在函数中直接调用自己称为函数的直接递归调用;如果函数f1调用了函数f2又再次调用了函数f1,这种调用的方式我们称之为间接递归调用。

    例1:利用递归求n! :有两种情况,当n=0递归结束,返回值为1 ;当n !=0时,继续递归。

    //递归求n!函数实现
    
    int factorial (int  n){
    
        if(n ==0 )
            return 1;
    
        else
            return n*factorial(n-1);
    }
    

      例2:已知有数组a[] ,要求利用递归实现求n个数中的最大值。

    a[] ={0,···,n-1};
    
    int findMax(int a[] ,int n){
    
        int  m ;
    
        if (n<=1)
            return a[0];
    
        else
        {
            m = findMax(a,n-1);
            return a[n-1] >= m ?a[n-1] : m ;//找到最大值
        }
    }

     

    (2)迭代与递归

    迭代与递归是程序设计中最常用的两种结构。任何能使用递归解决的问题都能使用迭代的方法解决。迭代和递归的区别是,迭代使用的是循环结构,递归使用的是选择结构。大量的递归会耗费大量的时间和内存,每次递归调用都会建立函数的一个备份,会占用大量的内存空间。迭代则不需要反复调用函数和占用额外的内存。对于较为简单的递归问题,可以利用简单的迭代将其转化为非递归。而对于较为复杂的递归问题,需要通过利用数据结构中的栈来消除递归。

    (3)指针

    是C语言中一个重要概念,也是最不容易掌握的内容。指针常常用在函数的参数传递和动态内存分配中。指针与数组相结合,使引用数组成分的形式更加多样化,访问数组元素的手段更加灵活;指针与结构体结合,利用系统提供的动态存储手段,能构造出各种复杂的动态数据结构;利用指针形参,使函数能实现传递地址形参和函数形参的要求。接下里会介绍指针变量的概念、指针与数组、函数指针与指针函数。

    指针是一种变量,也称之为指针变量,它的值不少整数、浮点数和字符,而是内存地址。指针的值就是变量的地址,而变量又拥有一个具体的值。因此,可以理解为变量名直接引用了一个值,指针间接地引用了一个值。

    指针可以与变量结合,也可以与数组结合使用。指针数组是一种存放一组变量的地址。数组指针是一个指针,表示该指针指向数组的指针。数组指针可以进行自增或自减运算,但是数组名则不能进行自增或自减运算,这是因为数组名是一个常量指针,它是一个常量,常量值是不能改变的。函数指针与指针函数同理。

     

    2.3参数传递

    (1)传值调用:分为实际参数和形式参数。例如:

    int GCD(int m ,int n);
    
    void main(){
        int a,b,v,
        v = GCD(a,b);  //实际参数
    }
    
    int GCD(int m ,int n){ //形式参数
        int r;
        r = m;
        do{
            m=n;
            n=r;
            r=m&n;
          }while(r);
    
        return n;
    }

    上面的函数参数传递属于参数的单向传递,即a和b可以把值传递给m和n,而不是可以把m和n传递给a和b。实际参数和形式参数的值的改变都不会互相收到影响。

    (2)传指针地址参数:略

     

    2.4 结构体和联合体

    也称共用体,是自定义的数据类型,用于构造非数值数据类型,在处理实际问题中应用非常广泛。数据结构中的链表、队列、树、图等结构都需要用到结构体。教师表结构体如下所示。

    //结构体类型
    struct teacher{
        //数据项
        int no;
        char name[20];
        char sex[4];
        char headship[8];
        char degree[6];
        long int phone;
    }

    与结构体一样,联合体也是一种派生的数据类型。但是与结构体不同的是,联合体的成员共享同一个存储空间。定义联合体一般形式如下所示。

    union 共用体名{
    
        成员列表;
    }
    变量列表;
    
    ——————————————————————————
    union data{
    
        int a ;
        float b;
        char c;
        double d;
    }abc;
    
    //或写成
    union data{
        int a;
        float b;
        char c;
        double d;
    };
    union data abc;
    
    

     

    2.5 链表

    在C语言中,处理已知数据可以使用数组。如果事先并不知道要处理的数据的个数,则需要使用链表结构。链表需要动态分配内存,链表的长度随时可以发生变化。链表有一个指针类型的成员指向自身,该指针指向与结构体一样的类型。例如如下语句:

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

    自引用结构体类型为struct node,该结构体类型有两个成员:整数成员data,指针成员next。成员next是指向结构体为struct node类型的指针。通过这种形式定义的结构体通过next指针把两个结构体变量连在一起。这种自引用结构体单元称为结点,结点之间通过箭头连接起来,构成一张表,称为链表。

    链表中第一个结点的指针称为头指针且可以访问链表的每一个结点。为了方便操作,在链表的第一个结点之前增加一个头结点。

    2.6 内存的分配与释放

    (1)malloc函数主要作用是分配一块长度为size的内存空间。void *malloc(unsigned int size);其中,size就是要分配的内存空间大小字节。使用时最好先检查一下是否分配成功,否则返回null,可以保证程序的正确运行。使用完分配后的空间要利用free函数及时释放。

    (2)free函数主要作用是将内存空间释放。void free (void *p); 其中,参数p指向要释放的内存空间。不能使用已经被free函数释放的内存空间。

     


    下一章:

    数据结构与算法——从零开始学习(二)线性表

     

     

    欢迎,😆大家关注公众号:(推送数据结构+算法+Java+人生感悟+理财知识+互联网事件等)

    展开全文
  • 数据结构:图结构的实现

    万次阅读 多人点赞 2018-02-07 19:44:45
    图是一种很重要的数据结构,不解释。

    数据结构:图结构的实现

    图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中,图是最灵活的数据结构之一,很多问题都可以使用图模型进行建模求解。例如:生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等等。

    额,我都不研究这些问题。之所以重新回顾数据结构,仅仅是为了好玩。图(Graph)通常会放在树(Tree)后面介绍,树可以说只是图的特例,但是我觉得就基础算法而言,树比图复杂很多,而且听起来也没什么好玩的(左左旋、左右旋、右右旋、右左旋,好无聊~)。因此,我写的第一篇数据结构的笔记就从图开始。

    1 图的概念

    1.1 图的基础概念串讲

    图的结构很简单,就是由顶点 VVV 集和边 EEE 集构成,因此图可以表示成 G=(V,E)G=(V, E)G=(V,E)
    图1-1:无向图
    图1-1:无向图1

    图1-1就是无向图,我们可以说这张图中,有点集 V={1,2,3,4,5,6}V=\{1, 2, 3, 4, 5, 6\}V={1,2,3,4,5,6},边集E={(1,2),(1,5),(2,3),(2,5),(3,4),(4,5),(4,6)}E=\{(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)\}E={(1,2),(1,5),(2,3),(2,5),(3,4),(4,5),(4,6)} 。在无向图中,边(u,v)(u, v)(u,v)和边(v,u)(v, u)(v,u)是一样的,因此只要记录一个就行了。简而言之,对称。
    图1-2:有向图
    图1-2:有向图 2
    有向图也很好理解,就是加上了方向性,顶点(u,v)(u, v)(u,v)之间的关系和顶点(v,u)(v,u)(v,u)之间的关系不同,后者或许不存在。例如,地图应用中必须存储单行道的信息,避免给出错误的方向。

    加权图:与加权图对应的就是无权图,如果觉得不好听,那就叫等权图。如果一张图不含权重信息,我们就认为边与边之间没有差别。不过,具体建模的时候,很多时候都需要有权重,比如对中国重要城市间道路联系的建模,总不能认为从北京去上海和从北京去广州一样远(等权)。

    还有很多细化的概念,有兴趣的自己了解咯。我觉得就没必要单独拎出来写,比如:无向图中,任意两个顶点间都有边,称为无向完全图;加权图起一个新名字,叫网(network)……然而,如无必要,毋增实体。

    两个重要关系:

    • 邻接(adjacency):邻接是两个顶点之间的一种关系。如果图包含(u,v)(u,v)(u,v),则称顶点vvv与顶点uuu邻接。当然,在无向图中,这也意味着顶点uuu与顶点vvv邻接。
    • 关联(incidence):关联是边和顶点之间的关系。在有向图中,边(u,v)(u,v)(u,v)从顶点uuu开始关联到vvv,或者相反,从vvv关联到uuu。注意,有向图中,边不一定是对称的,有去无回是完全有可能的。

    细化关联这个概念,就有了顶点的入度(in-degree)出度(out-degree)。无向图中,顶点的度就是与顶点相关联的边的数目,没有入度和出度。在有向图中,我们以图1-2为例,顶点10有2个入度,3→103\rightarrow1031011→1011\rightarrow101110,但是没有从10指向其它顶点的边,因此顶点10的出度为0。

    路径(path):依次遍历顶点序列之间的边所形成的轨迹。注意,依次就意味着有序,先1后2和先2后1不一样。

    简单路径:没有重复顶点的路径称为简单路径。说白了,这一趟路里没有出现绕了一圈回到同一点的情况,也就是没有
    图1-3:四顶点的有向带环图
    图1-3:四顶点的有向带环图3

    :包含相同的顶点两次或者两次以上。图1-3中的顶点序列&lt;1,2,4,3,1&gt;&lt;1,2,4,3,1&gt;<1,2,4,3,1>,1出现了两次,当然还有其它的环,比如&lt;1,4,3,1&gt;&lt;1,4,3,1&gt;<1,4,3,1>

    无环图:没有环的图,其中,有向无环图有特殊的名称,叫做DAG(Directed Acyline Graph)(最好记住,DAG具有一些很好性质,比如很多动态规划的问题都可以转化成DAG中的最长路径、最短路径或者路径计数的问题)。
    下面这个概念很重要:
    图1-4:两个连通分支
    图1-4:两个连通分支

    连通的:无向图中每一对不同的顶点之间都有路径。如果这个条件在有向图里也成立,那么就是强连通的。图1-4中的图不是连通的,我丝毫没有侮辱你智商的意思,我只是想和你说,这图是我画的,顶点标签有点小,应该看到a和d之间没有通路。

    • 连通分支:不连通的图是由2个或者2个以上的连通分支的并。这些不相交的连通子图称为图的连通分支
      图1-5:有向图的连通分支
      图1-5:有向图的连通分支

    • 有向图的连通分支:将有向图的方向忽略后,任何两个顶点之间总是存在路径,则该有向图是弱连通的有向图的子图是强连通的,且不包含在更大的连通子图中,则可以称为图的强连通分支

    图1-5中,aaaeee没有到{b,c,d}\{b,c,d\}{b,c,d}中的顶点的路径,所以各自是独立的连通分支。因此,图1-5中的图有三个强连通分支,用集合写出来就是:{{a},{e},{b,c,d}}\{\{a\}, \{e\}, \{b, c, d\}\}{{a},{e},{b,c,d}}(已经用不同颜色标出)。

    图1-6:关节点
    图1-6:关节点

    关节点(割点):某些特定的顶点对于保持图或连通分支的连通性有特殊的重要意义。如果移除某个顶点将使图或者分支失去连通性,则称该顶点为关节点。如图1-6中的c。

    双连通图:不含任何关节点的图。
    关节点的重要性不言而喻。如果你想要破坏互联网,你就应该找到它的关节点。同样,要防范敌人的攻击,首要保护的也应该是关节点。在资源总量有限的前提下,找出关节点并给予特别保障,是提高系统整体稳定性和鲁棒性的基本策略。

    桥(割边):和关节点类似,删除一条边,就产生比原图更多的连通分支的子图,这条边就称为割边或者

    1.2 一些有趣的图概念

    这一部分属于图论的内容,基础图算法不会用到,但是我觉得挺有意思的,小记如下。
    同构4:图看起来结构不一样,但它是一样的。假定有G1G_1G1G2G_2G2,那么你只要确认对于G1G_1G1中的所有的两个相邻点aaabbb,可以通过某种方式fff映射到G2G_2G2,映射后的两个点f(a)f(a)f(a)f(b)f(b)f(b)也是相邻的。换句话说,当两个简单图同构时,两个图的顶点之间保持相邻关系的一一对应。
    图1-7:图的同构
    图1-7:图的同构

    图1-7就展示了图的同构,这里顶点个数很少判断图的同构很简单。我们可以把v1看成u1,自然我们会把u3看出v3。用数学的语言就是f(u1)=v1f(u_1)=v_1f(u1)=v1f(u3)=v3f(u_3)=v_3f(u3)=v3。u1的另外一个连接是到u2,v1的另外一个连接是到v4,不难从相邻顶点的关系验证f(u2)=v4f(u_2)=v_4f(u2)=v4f(u4)=v2f(u_4)=v_2f(u4)=v2

    欧拉回路(Euler Circuit):小学数学课本上的哥尼斯堡七桥问题,能不能从镇里的某个位置出发不重复的经过所有桥(边)并且返回出发点。这也就小学的一笔画问题,欧拉大神解决里这个问题,开创了图论。

    结论很简单:至少2个顶点的连通多重图存在欧拉回路的充要条件是每个顶点的度都是偶数。证明也很容易,大家有兴趣可以阅读相关资料。结论也很好理解,从某个起点出发,最后要回起点,中间无论路过多少次起点,都会再次离开,进、出的数目必然相等,故一定是偶数。

    哈密顿回路(Hamilton Circuit):哈密顿回路条件就比欧拉回路严格一点,不能重复经过点。你可能会感到意外,对于欧拉回路,我们可以轻而易举地回答,但是我们却很难解决哈密顿回路问题,实际上它是一个NP完全问题

    这个术语源自1857年爱尔兰数学家威廉·罗万·哈密顿爵士发明的智力题。哈密顿的智力题用到了木质十二面体(如图1-8(a)所示,十二面体有12个正五边形表面)、十二面体每个顶点上的钉子、以及细线。十二面体的20个顶点用世界上的不同城市标记。智力题要求从一个城市开始,沿十二面体的边旅行,访问其他19个城市,每个恰好一次,最终回到第一个城市。
    图1-8:哈密顿回路问题
    图1-8:哈密顿回路问题
    因为作者不可能向每位读者提供带钉子和细线的木质十二面体,所以考虑了一个等价的问题:对图1-8(b)的图是否具有恰好经过每个顶点一次的回路?它就是对原题的解,因为这个平面图同构于十二面体顶点和边。

    著名的**旅行商问题(TSP)**要求旅行商访问一组城市所应当选取的最短路线。这个问题可以归结为求完全图的哈密顿回路,使这个回路的边的权重和尽可能的小。同样,因为这是个NP完全问题,最直截了当的方法就检查所有可能的哈密顿回路,然后选择权重和最小的。当然这样效率几乎难以忍受,时间复杂度高达O(n!)O(n!)O(n!)

    在实际应用中,我们使用的启发式搜索等近似算法,可以完全求解城市数量上万的实例,并且甚至能在误差1%范围内估计上百万个城市的问题。

    关于旅行商问题目前的研究进展,可以到http://www.math.uwaterloo.ca/tsp/进一步了解。

    1.3 小结

    以为可以一带而过,结果写了那么多。也没什么好总结的了,当然这些也至是图论概念的一小部分,还有一些图可能我们以后也会见到,比如顺着图到网络流,就会涉及二分图,不过都很好理解,毕竟有图。

    2 图的表示

    2.1 邻接链表与邻接矩阵

    图最常见的表示形式为邻接链表邻接矩阵。邻接链接在表示稀疏图时非常紧凑而成为了通常的选择,相比之下,如果在稀疏图表示时使用邻接矩阵,会浪费很多内存空间,遍历的时候也会增加开销。但是,这不是绝对的。如果图是稠密图,邻接链表的优势就不明显了,那么就可以选择更加方便的邻接矩阵。

    还有,顶点之间有多种关系的时候,也不适合使用矩阵。因为表示的时候,矩阵中的每一个元素都会被当作一个表。

    2.1.1 存储问题

    如果使用邻接矩阵还要注意存储问题。矩阵需要n2n^2n2个元素的存储空间,声明的又是连续的空间地址。由于计算机内存的限制,存储的顶点数目也是有限的,例如:Java的虚拟机的堆的默认大小是物理内存的1/4,或者1G。以1G计算,那么创建一个二维的int[16384][16384]的邻接矩阵就已经超出内存限制了。含有上百万个顶点的图是很常见的,V2V^2V2的空间是不能满足的。
    因此,偷个懒,如果对邻接矩阵感兴趣,可以自己找点资料。很容易理解的。

    2.1.2 邻接链表的实现

    邻接链表的实现会比邻接矩阵麻烦一点,但是邻接链表的综合能力,包括鲁棒性、拓展性都比邻接矩阵强很多。没办法,只能忍了。
    图1-9:邻接链表示意图
    图1-9:邻接链表示意图

    从图1-9不能看出邻接链表可以用线性表构成。顶点可以保持在数组或者向量(vector)中,邻接关系则用链表实现,利用链表高效的插入和删除,实现内存的充分利用。有利必有弊,邻接矩阵可以高效的判定两个顶点之间是否有邻接关系,邻接链表无疑要遍历一次链表。

    邻接链表的瓶颈在于链表的查找上,如果换成高效的查找结构,就可以进一步地提高性能。例如,把保存顶点邻接关系的链表换成通常以红黑树为基础set。如果一定要名副其实,就要叫成邻接集。类似的,顶点的保存也有“改进”方案。比如,使用vector通常用int表示顶点,也无法高效地进行顶点的插入删除。如果把顶点的保存换成链表,无疑可以高效地进行顶点的插入和删除,但是访问能力又会大打折扣。没错,我们可以使用set或者map来保存顶点信息。

    C++11中引入了以散列表为基础unordered_setunordered_map,就查找和插入而言,统计性能可能会高于红黑树,然而,散列表会带来额外的内存开销,这是值得注意的。

    具体问题,具体分析,图的结构不同,实现图的结构也应该随之不同。大概也是这个原因,像C++、Java、Python等语言,都不提供具体的Graph。举个例子,直接使用vector保存顶点信息,list保存邻接关系,使用的顶点id连续5。那么在添加边O(1)O(1)O(1),遍历顶点的邻接关系O(V)O(V)O(V)还有空间消耗O(V+E)O(V+E)O(V+E)上都是最优的。当然,类似频繁删除边,添加边(不允许平行边),删除顶点,添加顶点,那么这种比较简易的结构就不太适合了。

    2.3 量化选择

    我们稍微量化一下稀疏图和稠密图的标准。当我们声称图的是稀疏的,我们近似地认为边的数量∣E∣|E|E大致等于顶点的个数∣V∣|V|V,在稠密图中,我们可以不难得到∣E∣|E|E近似为∣V2∣|V^2|V2。在此,我们不妨定义均衡图是边的数量为∣V2∣/log⁡∣V∣|V^2|/\log |V|V2/logV的图。

    图算法中,根据图的结构,经常会有两个算法变种,时间复杂度也不尽相同。可能有一个是O((V+E)log⁡V)O((V+E)\log V)O((V+E)logV),另一个是O(V2+E)O(V^2+E)O(V2+E)。选择哪个算法更为高效取决于图是否是稀疏的。

    图类型 O((V+E)log⁡V)O((V+E)\log V)O((V+E)logV) 比较关系 O(V2+E)O(V^2+E)O(V2+E)
    稀疏图:EEEO(V)O(V)O(V) O(Vlog⁡V)O(V\log V)O(VlogV) < O(V2)O(V^2)O(V2)
    均衡图:EEEO(V2/log⁡V)O(V^2/\log V)O(V2/logV) O(V2+Vlog⁡V)=O(V2)O(V^2+V\log V)=O(V^2)O(V2+VlogV)=O(V2) = O(V2+V2/log⁡V)=O(V2)O(V^2+V^2/\log V)=O(V^2)O(V2+V2/logV)=O(V2)
    稠密图:EEEO(V2)O(V^2)O(V2) O(V2log⁡V)O(V^2\log V)O(V2logV) > O(V2)O(V^2)O(V2)

    3 图的实现

    3.1 代码约定

    因为用Markdown,所以我怕有时候排版的时候空格出现问题,4空格调整太麻烦,加上可能4空格有时候不是特别紧凑,所以代码全部是2空格缩进。另外,我就不打算像教科书一样写那种一本正经的代码,拆成头文件加源文件。还有很多偷懒和不负责的地方,不过,换来了性能。还有,auto还是挺好用的,因此代码会用到少量C++11。

    3.2 想想需要什么功能

    3.2.1 图的数据结构

    就学习算法的目的而言,频繁添加和删除顶点是不需要的,因此代码实现时,为方便起见顶点仍然使用vector保存,边的话进阶点,使用set,这样就防止出现平行边了。还有,我比较放心自己,很多方法不加检查。还是那句话,具体问题,具体分析,具体实现。

    3.2.2 图的操作

    既然选择用vector+set,我们来考虑一下基本操作,至于那些后来算法用到的,后面再补充实现。

    数据成员:

    • 边的数量
    • 顶点的数量
    • vectorset构成的图结构

    功能:

    • 添加边
    • 删除边
    • 添加顶点
    • 删除顶点
    • 判断是否有邻接关系
    • 返回顶点的邻接集:不推荐直接使用这个,建议用迭代器
    • 迭代器begincbegin
    • 迭代器endcend

    其它

    • 构造:初始化n个顶点
    • 构造:从字符串读取文件中的图信息,便于加载图信息
    • 析构函数:都是使用STL和动态变量,不用我们操心
    • 数据成员的取值方法
    • 辅助方法:打印图

    3.3.3 声明与内联实现

    #include <iostream>
    #include <vector>
    #include <set>
    #include <list>
    #include <fstream>
    #include <limits>
    #include <queue>
    
    // 邻接集合
    typedef std::set<int> AdjSet;
    // 邻接集
    class Graph {
     protected:
      // 邻接表向量
      std::vector<AdjSet> vertices_;
      // 顶点数量
      int vcount_;
      // 边的数量
      int ecount_;
      bool directed_;
     public:
      Graph(bool directed = false)
        : ecount_(0), vcount_(0),
          vertices_(0), directed_(directed) {};
      Graph(int n, bool directed)
        : ecount_(0), vcount_(n),
          vertices_(n), directed_(directed) {};
      // 从文件中初始化
      Graph(const char *filename, bool directed);
      virtual ~Graph() {
        vertices_.clear();
        vcount_ = 0;
        ecount_ = 0;
      }
      // 取值函数
      virtual int vcount() const { return vcount_; };
      virtual int ecount() const { return ecount_; };
      virtual bool directed() const { return directed_; };
      // 某条边是否存在
      virtual bool IsAdjacent(const int &u, const int &v);
      // 约定:成功返回 0,不存在 -1,已存在 1
      // 添加边
      virtual int AddEdge(const int &u, const int &v);
      // 添加顶点
      virtual int AddVertex();
      // 删除边
      virtual int RemoveEdge(const int &u, const int &v);
      // 删除顶点
      virtual int RemoveVertex(const int &u);
      // 返回顶点的邻接集
      virtual std::set<int>& Adj(const int &u) { return vertices_[u]; }
      // 迭代器
      virtual AdjSet::const_iterator begin(const int u) { return vertices_[u].begin(); };
      virtual AdjSet::const_iterator end(const int u) { return vertices_[u].end(); };
      virtual AdjSet::const_iterator cbegin(const int u) const { return vertices_[u].cbegin(); };
      virtual AdjSet::const_iterator cend(const int u) const { return vertices_[u].cend(); };
    }; // class Graph
    

    3.3 开工

    因为图结构实现还是比较简单的,代码都很短。

    3.3.1 从文件中构造图

    文件格式,先顶点数量、边数量,然后顶点对表示边。缺省bool值默认无向
    例如

    6
    8
    0 1
    0 2
    0 5
    2 3
    2 4
    2 1
    3 5
    3 4
    

    代码实现:

    Graph::Graph(const char *filename, bool directed = false) {
      directed_ = directed;
      int a, b;
      // 默认能打开,如果想安全,使用if (!infile.is_open())作进一步处理
      std::ifstream infile(filename, std::ios_base::in);
      // 节点和边数量
      infile >> a >> b;
      vcount_ = a;
      ecount_ = b;
      vertices_.resize(vcount_);
      // 读取边
      for (int i = 0; i < ecount_; ++i) {
        infile >> a >> b;
        int v = a;
        int w = b;
        vertices_[v].insert(w);
        if (!directed_) {
          vertices_[w].insert(v);
        }
      }
      infile.close();
    }
    

    3.3.2 添加和删除顶点

    // 添加顶点
    int Graph::AddVertex() {
      std::set<int> temp;
      vertices_.push_back(temp);
      ++vcount_;
      return 0;
    }
    
    // 删除顶点
    int Graph::RemoveVertex(const int &u) {
      if (u > vertices_.size()) {
        return -1;
      }
      // 遍历图,寻找与顶点的相关的边
      // 无向图,有关的边一定在该顶点的邻接关系中
      if (!directed_) {
        int e = vertices_[u].size();
        vertices_.erase(vertices_.begin() + u);
        ecount_ -= e;
        --vcount_;
        return 0;
      } else {
        // 遍历图
        for (int i = 0; i < vertices_.size(); ++i) {
          RemoveEdge(i, u);
        }
        vertices_.erase(vertices_.begin() + u);
        --vcount_;
        return 0;
      }
      return -1;
    }
    

    3.3.3 添加和删除边

    // 添加边
    int Graph::AddEdge(const int &u, const int &v) {
      // 不绑安全带,使用需谨慎
      vertices_[u].insert(v);
      if (!directed_) {
        vertices_[v].insert(u);
      }
      ++ecount_;
      return 0;
    }
    
    // 删除边
    int Graph::RemoveEdge(const int &u, const int &v) {
      auto it_find = vertices_[u].find(v);
      if (it_find != vertices_[u].end()) {
        vertices_[u].erase(v);
        --ecount_;
      } else {
        return -1;
      }
      if (directed_) { return 0; }
      // 无向图删除反向边
      it_find = vertices_[v].find(u);
      if (it_find != vertices_[u].end()) {
        vertices_[v].erase(u);
      } else {
        // 人和人之间的信任呢?
        return -1;
      }
      return 0;
    }
    

    3.3.4 是否有邻接关系

    // 检查两个顶点之间是否有邻接关系
    bool Graph::IsAdjacent(const int &u, const int &v) {
      if (vertices_[u].count(v) == 1) {
        return true;
      }
      return false;
    }
    

    3.3.5 其它:打印图

    这个用到了cout,又考虑到非功能性方法,不建议放在类中。

    // 打印图
    void PrintGraph(const Graph &graph) {
      for (int i = 0; i < graph.vcount(); i++) {
        std::cout << i << " -->";
        for (auto it = graph.cbegin(i); it != graph.cend(i); ++it) {
          std::cout << " " << *it;
        }
        std::cout << std::endl;
      }
    }
    

    3.5 小结

    图是相当灵活的,我想这也是为什么STL库不提供Graph的原因。我们可以发现,利用STL的基础设施,我们可以很快的搭建Graph。至于选择什么基础设施,没有标准答案。对于不同的问题会有不同的最佳答案。我们只是演示,不对特定问题进行进行建模,可以不管什么性能,也没打算泛化(不造库,谢谢),不过分考虑实现和图操作分离问题。嗯,就这样咯,还是赶紧进入更加激动人心的图算法吧。

    后记

    我水平有限,错误难免,还望各位加以指正。

    参考资料

    1. Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest,等. 算法导论(原书第3版).
    2. Robert Sedgewick, Kevin Wayne. 算法(原书第4版).
    3. 邓俊辉. 数据结构(C++语言版)(第3版).
    4. Kenneth H.Rosen. Discrete Mathematics and Its Applications(Seventh Edition).
    5. 维基百科相关词条

    1. https://en.wikipedia.org/wiki/Graph_(discrete_mathematics) ↩︎

    2. https://en.wikipedia.org/wiki/Directed_graph ↩︎

    3. https://en.wikipedia.org/wiki/Directed_graph ↩︎

    4. 同构(isomorphism)这个词来自希腊语字根:“isos”表示相等;“morphe”表示形式。 ↩︎

    5. 注意这通常是可以做到的,这意味着我们只关注图的拓扑结构,不关心顶点id的意义。如果你非要在图中保存额外的信息,那么就应该使用树结构或者随机化的hash方案。 ↩︎

    展开全文
  • 2018攻读硕士学位研究生入学考试 数据结构试题 一、选择题 1.判断哪个表结构是逻辑结构( ) A.顺序表 B.哈希表 C.有序表 D.单链表 答案:C 2.关于算法的优越性判断,以下正确的是( ) A.算法原地工作是指不需要...

    南京邮电大学
    2018年攻读硕士学位研究生入学考试
    数据结构试题
    一、选择题
    1.判断哪个表结构是逻辑结构( )
    A.顺序表 B.哈希表 C.有序表 D.单链表

    答案:C

    2.关于算法的优越性判断,以下正确的是( )
    A.算法原地工作是指不需要额外的辅助空间
    B.健壮性是指程序不因为奇怪的输出而产生奇怪的状态
    C.若算法的时间复杂度是0(n2),表示它的问题规模n2
    D.算法的输入是指至少要有一个输入,这些输入取自于某个特定对象的集合

    答案:B
    A.原地工作是指需要常数量个存储空间
    C.时间复杂度是由问题规模以及处理数据初态决定的
    D.算法的输入是零个或多个输入

    3.如果要在最后一个元素之后插入一个元素和删除第一个元素,那么哪种存储方式最省时间( )
    A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表

    4.顺序表的1个是占2个存储的单元,若第一元素a0的地址100,则a5在内存中的存储地址是( )
    A.105 B.110 C.115 D.120

    答案:B

    5.6 5 4 5 3 2 1顺序进栈判断不合法的出栈的序列( )
    A.1235456 B.6545321 C.6545123 D.2545631

    答案:D

    6.根据一个式子a*(b+c)-d写出后缀表达式( )
    A.abcd*+= B.abc+*d- C.abc+d- D.-+*abcd

    答案:B

    7.100*90的稀疏矩阵有非0元素10个每个类型占2个字节求用三元组存储该矩阵时所需要字节数( )
    A.60 B.66 C.20 D.10

    答案:三元组有一行存放稀疏矩阵的行和列以及非零元素个数。其他行用来存储非零元素。所以该三元组有11行,3列

    8.对稀疏矩阵进行的压缩的目的是( )
    A.表达变得简单
    B.对矩阵元素的存取变得更加简单
    C.去掉矩阵中的多余元素
    D.减少不必要的存储空间

    9.先序,中序和后序中,叶子节点的顺序是否相同( )
    A.都不相同 B.完全相同
    C.先序和中序相同 D.中序和后序相同,而与前序不同

    10.n个结点线素求二叉树含有的线索( )
    A.2n B.n-1 C.n+1 D.n

    11.长度为n的有序单链表,若查找每个元素的概率相同,则顺序查找表中任一元素的查找成功的平均查找长度为( )
    A.n/2 B.(n+1)/2 C.(n-1)/2 D.n/4

    12.对序列11、14、21、25、34、46、56,78进行折半查找,查找元素78,顺序是( )
    A.25 46 56 78 B.25 56 46 78 C.25 46 78 D.25 46 56

    13.二叉平衡树中任意节点的平衡因子的判断( )
    A.左边-右边=1 B.左边-右边<=1 C.|左边-右边|=1 D.|左边-右边|<=1

    14.除根节点外的m阶B树的每个非叶子节点有几个孩子( )
    A [m/2] B.[(m/2)-1] C.[(m/2)]-1 D.[(m/2)]+1 ([]为上取整)

    15.有向图G对拓扑序列中,若顶点vi在vj之前,则下列情形不能出现的是( )
    A.G中有弧<vi,vj>
    B.G中有一条vi到vj得到路径
    C.G中没有弧<vi,vj>
    D.中有一条vj到vi的路径

    16.邻接表存储最小生成树prime算法的时间复杂度( )
    A.O(n2) B.O(n3) C.O(n+e) D.O(log2n)

    17.从以下选出稳定的排序()
    A.快速排序 B希尔排序 C.简单选择排序 D.冒泡排序

    18.对包含n个元素的散列表进行查找,平均查找长度( )
    A.为0(log2n) B.为0(1)
    C. 不直接依赖于n D.直接依赖于表长m

    散列表的平均查找长度依赖于散列表的填装因子,而不直接依赖于n,m

    19.用直接插入排序对下列四个序列进行递增排序,比较次数最少的是( )
    A.94、2、40、90、80、46、21、69
    B.32、40、21、46、69、94、90、80
    C.21、32、46、40、80、69、90、94
    D.90、69、80、46、21、32、94、40

    20.对序列40、30、50、60、70、10、20、80用简单选择排序要交换几次完成递增排序( )
    A.8 B.7 C.6 D.5
    二、综合题
    1.1000个元素关键字是0-9999将数据存入长度为200拉链法散列中,设计散列函数解决此问题并说明散列函数的好处。

    1.散列函数H(key)=key%199(除留余数法)
    优点:1.简单,计算速度快
    2.分布均匀。1000个元素接关键字的值均匀的方布在散列表中散列地址为0—198的单链表中。除散列地址为0一4的单链表长度为6其余均为5
    3.散列表填充因子(装填密度)x<=n/m=1000/199≈5
    成功搜索平均长度:1+x/2<4
    失败搜索平均长度:x≈5
    4.只有散列地址为199的单链表为空,即只浪费1个空间.故利用空间效率高.

    2.①非空二叉树先序和后序相反是什么形态。
    ②非空二叉树先序和后序相同是什么形态。

    (1)1.只有一个根结点的二叉树
    2.所有结点只有左子树或只有右子树的二叉树
    (2)只有一个根结点的二叉树

    3.ABCDEF表分别有10,35,40,50,60和200个元素各个表中都升序求通过5次两两合6个表合成一个升序表,并在最坏情况下比较总次数与合并过程并求最坏情况下比较的次数是多少。

    合并过程:
    (1)A,B合并,生成45个元素的表AB
    (2)A,B与C合并,生成85个元素的表ABC
    (3)D,E合并,生成110个元素的表DE
    (4)ABC与DE合并,生成195个元素的表ABCDE
    (5)ABCDE与F合并,生成395个元素的表ABCDEF
    且两个长度为m,n的表合并,至少需要min{m,n},最多需要m+n-1次,故第一次合并最多需要10+35-1=44次,第二次45+40-1=84次,第三次50+60-1=109次,第四次85+110-1=194次,第五次195+200-1=394次,故共需要44+84+109+194+394=825次

    4.证明满m叉树上叶子节点数n0和非叶子结点数N之间满足以下关系n0=(m-1)*N+1

    4.证明:首先,在满m叉树中存在度为0与m的结点,且分支=结点-1,令分支为F,结点总数为P,即满足F=P-1,所以F=mN,
    P=n0+N,
    P=F+1=m
    N+1,
    n0+N=m*N+1,
    n0=(m-1)*N+1

    5.有序10、12、21、23、30、39、43、50、60有一串对下标从0开始标记进行对半搜索。
    ①搜索10,描述对半搜索的过程
    ②求对半搜索成功的平均查找长度
    二叉搜索树

    搜索10过程:30,12,10
    ASLSUCCESS=(1+22+34+4*2)/9=25/9

    6.有序列15、25、70、38、50、80、75,请画出AVL树。
    在这里插入图片描述
    在这里插入图片描述

    7.根据图画出所有拓扑排序序列。

    在这里插入图片描述

    1)1,2,3,5,4,6
    2)1,2,5,3,4,6
    3)1,3,2,5,4,6

    8.根据给定的先序序列,画出二叉搜索树
    先序序列:28、25、36、33、35、34、43
    在这里插入图片描述

    三、算法题
    1.对一个排序去重,要求;有重复的关键字,保留后一个,删除前一个。

       void DeleteRepeat(int &A[],int i,j,k[],t)//k[]用来存放删除的记录
       {  if(A[]==null)
            break;
             else
             { for(i=0,j=A.length-1;i<j;i++) 
               if(A[i]!=A[j])
                     j--;
                else
                   {k[t]=A[i];
    				t++;
    				A[i]=A[i+1];
                   }
    }
    }
    
    

    2.二叉存储结构的二叉树,求二叉树高度。

    int getdepth(BTnode *t)
    { 
      int L,R;
    	if(p==null)    
    	return 0;
    else
    {
          L=getdepth(p->lchild);
          R=getdepth(p->rchild);
    		return(L>R?L:R)+1;
    }
    }
    
    

    3.有向图用邻接表法表示,求每个顶点的出度。

    void BFS(AGraph *G,int v,int visit[])
    { 
    	ArcNode *p;int B[];int c, count=0;
    	int que[maxsize],front=0,rear=0;int j;
    	visit(v);
    	Visit(v)=1;
    	rear=(rear+1)%maxsize;
    	que[rear]=v;
    	while(front!=rear){
    		front=(front+1)%maxsize;
    		j=que[front];
    		p=G->adjlist[j].firstarc;
    		while(p!=null){
    			if(visit[p->adjvex]=0){ 
    				count++;
    				visit(p->adjvex);
    				visit[p->adjvex]=1;
    				rear=(rear+1)%maxsize;
    				que[rear]=p->adjvex;
    			}
    			p=p->nextarc;
    		}
    		B[c++]=count;
    		}
    }
    
    
    
    展开全文
  • 这一讲我会告诉你,怎么设计出优美的演讲结构。 演讲结构的本质是三个关键词: 关键内容、提炼抽象、排列组合 。 但是这样说有点抽象,今天我就给你四个非常简单好记,又经典实用的结构。它们分别是:1. 黄金圈法则...
  • 电池包结构是指将多个电芯,电池保护板,电池辅料,电池连接件,电池盒外壳通过空间想象做出来或者通过3D软件绘图设计出来,最终实现和想象中一样的PACK电池包结构,PACK电池包结构包括新能源动力电池包结构设计,EV...
  • 学习编程,数据结构是你必须要掌握的基础知识,那么数据结构到底是什么呢? 根据百度百科的介绍,数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,178,272
精华内容 471,308
关键字:

年的结构