0%

树的基本概念

树的定义

  • 树是n($n\geq 0$)个结点的有限集
  • n=0为空树
  • 有且只有一个称为根的结点
  • n>1时,其余结点可分为m($m>0$)个互不相交的有限集$T_1,\cdots,T_m$,每个集合也是树,称为根的子树。

树的特点

  • 根没有前驱,其他点有且只有一个前驱
  • 所有点都可以有零或任意多个后继
  • n个点的树有n-1条边(数学归纳法易证)
阅读全文 »

串定义

  • 字符串简称串
  • 由零个或多个字符组成的有限序列,记为$S=’a_1a_2\cdots a_n’$,$n\geq 0$
  • 空串用空集$\emptyset$表示
  • 串中任意多个连续字符子序列称作子串,包含子串的叫主串
  • 子串的位置指子串第一个字符在主串中的位置
  • 两个串相等,指长度相等且对应位置字符相等
  • 串的逻辑结构和线性表类似,但串的数据对象仅为字符,且串的操作对象一般是子串。

串的存储结构

  • 定长顺序存储:一般利用定长数组实现
  • 堆分配动态存储:利用malloc和free函数
  • 块链存储:每个结点可以放一个字符,也可以放多个。例如结点大小可以是4,最后一个结点如果不满4个字符用#补齐。

串的模式匹配

阅读全文 »

定义

  • 只能在栈顶进行插入和删除的线性表
  • 后进先出结构
  • 重要的数学结论:n个不同的元素进栈,出栈元素不同的排列有$\frac{C_{2n}^{n}}{n+1}$

顺序存储

  • 利用连续存储单元存放元素,同时附设一个栈顶指针top
  • top可以表示栈顶元素的下标(非空情况从0开始),也可以表示栈顶元素的位序(数值上等于栈大小,非空情况从1开始)
  • 前者空栈时,top为-1;后者空栈时top为0
  • 前者进栈为$S.data[++S.top]$,后者进栈为$S.data[S.top++]$
  • 前者出栈为$S.data[S.top-\ -]$,后者进栈为$S.data[-\ -S.top]$
  • 共享栈
    • 将两个栈的栈底设置在一维数组的两端,栈顶向内延申共享空间。
    • 以top表示栈顶元素下标为例
      • $top1=-1$时1栈为空
      • $top2=Maxsize$时2栈为空
      • $top1=top2-1$时栈满
阅读全文 »

线性表的定义

  • 线性表是具有相同数据类型的n个($n\geq 0$)数据元素的有限序列
  • $n$为表长
  • 用$L$命名,则表示为$L=(a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n)$,注意从1开始
  • 特点
    • 元素有限
    • 逻辑上有顺序性(注:这里指先后次序而不是物理的顺序存储
    • 表中元素为数据元素,类型相同,存储空间大小相同
    • 不考虑存储结构,属于逻辑结构

线性表的顺序表示

定义

  • 线性表的顺序存储称作顺序表
  • 线性表位序从1开始,数组下标从0开始
  • 特点:逻辑结构和物理结构相同(插入删除要移动大量元素),可随机存取、存储密度高
阅读全文 »

数据结构基本概念

基本概念和术语

  • 数据:信息的载体,描述客观事物属性,如数字、字符、所有能输入计算机中识别处理的符号集合
  • 数据元素:数据基本单位(数据表中的一行),由数据项组成
  • 数据项:数据元素不可分割的最小单位(理解成属性)
  • 数据对象:数据元素的集合,数据的子集
  • 数据类型:值的集合和定义在此集合上的一组操作的总称
    • 原子类型:值不可再分
    • 结构类型:值可以再分
    • 抽象数据类型:抽象数据组织和操作(即结构和运算)
  • 数据结构:存在关系的数据元素的集合
    • 数据指数据元素
    • 结构指数据元素之间的关系
    • 定义数据结构需要数据对象、结构关系、操作运算

数据结构的三要素

  • 逻辑结构:独立于计算机(物理存储),从逻辑上描述数据的关系,分为线性结构和非线性结构
    • 线性结构(一对一的关系)
      • 一般线性表
      • 受限线性表:栈、队列、串
      • 线性表推广:数组
    • 非线性结构
      • 集合(属于同集合的关系)
      • 树形结构(一对多的关系):一般树、二叉树
      • 图状结构(多对多的关系):有向图、无向图
  • 存储结构:计算机中对数据和关系的表示
    • 顺序存储:逻辑相邻的元素在物理上也相邻存储
      • 优点:可随机存取、节约空间
      • 缺点:只能使用相邻的整块存储单元,容易产生碎片
    • 链式存储:逻辑相邻的元素在物理上可不相邻
      • 优点:不会出现碎片,充分利用所有存储单元
      • 缺点:引入额外指针空间开销、只能顺序存取
    • 索引存储:存储信息的同时,维护一个索引表(表的每个索引项包含关键字和地址)
      • 优点:搜索速度快
      • 缺点:索引表占用额外的存储空间,增删元素时维护索引表需要额外的开销
    • 散列存储:根据关键字直接算出存储地址,又叫哈希(Hash)存储
      • 优点:检索增删操作快
      • 缺点:如果散列函数不好,可能出现大量的冲突,从而增加时间空间开销
  • 数据元素:包括运算定义和运算实现
    • 定义:针对逻辑结构,指出运算的功能效果
    • 实现:针对存储结构,指出运算的操作步骤
阅读全文 »

宇宙大爆炸

  • 宇宙可观测的范围:直径约930亿光年
  • 奥伯斯佯谬:如果宇宙是无限稳态的,夜晚的天空会像白天一样明亮
    • 解释1:因为宇宙有黑暗星体、尘埃和气体阻隔;但这些最终会加热并发出自己的光
    • 解释2:宇宙是有限的;但这样宇宙会坍塌,边缘星体会被拉向内部
    • 猜想:宇宙大爆炸模型:模型是有限的,正在膨胀的;可以解释奥伯斯佯谬
  • 电磁辐射——波粒二象性
    • 电磁波的能量传输:波有特定波长,与频率成反比
    • 辐射表现为光子流:能量是$E=hf$,短波能量高
  • 元素的特征谱线
    • 元素电子跃迁会吸收或释放特定波长的光
    • 恒星会发出不同的(连续)波长的电磁辐射
    • 恒星外层大气中低温气体吸收特定光子,导致光谱产生吸收谱线(暗谱线)
    • 通过特征谱线,可以判定是什么元素
    • 通过光的强度,可以计算出该元素的浓度
    • 通过太阳光可以探测太阳光球层的成分
  • 红移
    • 其他星系的光谱也有暗谱线
    • 这些光谱的暗线的相对分布类似,说明各星系含有的元素一样
    • 越远的星系,暗线整体红移,说明越远的星系以越大的速度远离我们(多普勒效应)
    • 证明了宇宙正在膨胀
  • 测量星体和地球的距离
    • 三角测量法:只适合测量星系中近距离的天体,不适合确定宇宙的膨胀
    • 标准烛光法:距离越远,能力越分散,亮度越低
    • 大小和亮度法:测量最遥远的天体
  • 哈勃定律:$v=HL$
    • H是哈勃常数,也是宇宙年龄的倒数。因为宇宙大爆炸时速度快的星体,现在离我们会更远。
    • 所有的星体都在远离不代表我们是宇宙的中心,因为远离是相对的位置关系
    • 速度可以由红移确定,距离由标准烛光法和星系大小确定
    • 计算出哈勃常数,从而得到宇宙的年龄为137亿年
  • 宇宙大爆炸的证据
    • 星系的光谱红移
    • 宇宙背景辐射(黑体辐射)
    • 宇宙中的H/He比值
  • 黑体辐射
    • 黑体指的是入射电磁波吸收率100%,但仍要对外辐射
    • 宇宙各方向有强度不变的背景微波辐射,大约是3K
  • 宇宙的组成:73%的暗能量、23%的暗物质、4%的原子

元素起源

  • 地球陆壳元素丰度排序:O、Si、Al、Fe、Ca
  • 地球上元素丰度排序:Fe、O、Si、Mg、S、Ni、Ca、Al
  • 太阳中元素丰度排序:H、He、O(Fe含量不低)
  • 原子结构:原子核、质子、中子、电子
    • 质量看原子核
    • 大小看电子云大小
    • 上标质量数,下标质子数
  • 四种基本力: 引力、电磁力、弱力、强力。
    • 强力和电磁力使原子稳定。
    • 核素表的稳定带:强力可以把原子核的质子和中子稳定结合在一起
    • 核素表不稳定的区域会发生核反应,例如电子捕获把质子变中子、$\beta$衰变把中子转化为质子和电子、$\alpha$衰变放出He、裂变等
  • 同位素:质子数相同
  • 同重核素:质量数相同
  • 质能方程:$E=mc^2$
  • 质量陷阱:没有质量数是5和8的核素
    • 宇宙大爆炸形成了大部分氢氦,和少量锂铍硼
    • 宇宙中的H/He质量比约为2.5
    • H和He占宇宙物质质量的99%以上
  • 核聚变只能到56Fe
    • 结合能最高点,在此前放热,此后吸热
    • 更重的核素形成靠的是超新星爆发
    • 星系中元素的分布也受超新星爆发影响
  • 恒星越大,合成元素越多,恒星寿命越短;太阳是质量小的恒星,可以由很多元素组成但不形成重元素。
  • r-过程:快中子捕获
  • s-过程:慢中子捕获
  • p-过程:如质子捕获
  • 这些过程的证据
    • 恒星燃烧的唯一能量来源
    • 超新星爆发已被观测
    • 元素相对丰度计算与观测结果相对应
    • 超新星爆发遗迹中观察到锝的吸收线
    • 太阳系物质中短寿期放射性核素证据

矿物和有机分子形成

阅读全文 »