数据以文件的方式存储在外存,需要进行有效的管理。
数据项(item、field):数据文件中最小单位,反映实体某一方面的属性的数据表示。
记录(record):一个实体的所有数据项的集合,用来表示一个记录的数据项集合称为关键字项。
文件(file):大量性质相同的数据记录的集合。
逻辑结构:记录间在逻辑上的线性结构。
基本物理结构(在存储空间:外存上的组织方式):顺序结构、链接结构、索引结构
(1)按记录类型:
(2)按记录长度:
(1)检索记录:从文件中查找相应记录;
(2)插入记录:把给定的记录插入文件的指定位置。(先检索插入点位置,再插入)
(3)删除记录:删除给定记录。(条件/位置)
(4)修改记录:检索符合修改条件的记录,进行修改。
(5)记录排序:根据指定关键字,对文件中的记录按照关键字大小重新排列/存储。
记录的逻辑顺序和存储顺序是一致的,可分为连续/链接顺序文件,排序/一般顺序文件。
类似线性表的顺序存储结构。
由索引表、数据表构成。
数据表:存储实际数据记录。
索引表:存储记录的关键字和记录地址之间对照关系(关键字->地址->数据表)
顺序索引存取方法,采用静态索引结构,专门为磁盘设计。
有三个索引目录,磁道索引、柱面索引和主索引,类似于柱坐标系。
在每一个柱面上还有一个溢出区,存放溢出的记录。索引项有基本索引项和溢出索引项。
虚拟存取方法,利用虚拟存储器功能,基于B+树的动态索引结构。
由索引集、顺序集和数据集构成。
又称直接存取文件,类似散列表(哈希表),将记录散列存储到存储介质上。
记录成组存放,若干个记录形成一个存储单位:桶。同一个桶中的记录关键字相同。若存储了n个记录的桶要加入第n+1个记录,则发生了溢出。
数据库文件,可以对主关键字、次关键字都进行查询,需要对各个关键字都进行索引。
可以用多重表文件或倒排文件实现。
例: 开灯问题
有从1到n依次编号的n个同学和n盏灯。1号同学将所有的灯都关掉;2号同学将编号为2的倍数的灯都打开;3号同学则将编号为3的倍数的灯作相反处理(该号灯如打开的,则关掉;如关闭的,则打开);以后的同学都将自己编号的倍数的灯,作相反处理。
问:经 n个同学操作后,哪些灯是打开的?
算法思路:
用数组a[n]
表示灯,用1、0表示灯灯开与关;
可以用a[i] = 1 - a[i]
代替if(a[i] == 1)a[i] = 0
的判断操作。
flag = 1
例: 警察抓小偷
警察局抓了a,b,c,d四名偷窃嫌疑犯,其中只有一人是小偷。审问中:
现在已经知道四个人中三人说的是真话,一人说的是假话,问到底谁是小偷?
设小偷为x,四个人的话可以转化为表达式:x != 1
、x == 3
、x == 4
、x != 4
结果表达式为:(x != 1) + (x == 3) + (x == 4) + (x !=4) == 3
对于一个规模为n的问题P(n),可以把它分解为k个规模较小的子问题,这些子问题互相独立,且结构与原来问题的结构相同。在解这些子问题时,又对每一个子问题进行进一步的分解,直到某个阈值n0为止。递归地解这些子问题,再把各个子问题的解合并起来,就得到原问题的解。
适用条件:
步骤:
例:二进制大整数乘法
两个n位大整数x、y相乘:
x = a+b = a2^{n/2}+b,(a.size=b.size=n/2) y = c+d = c2^{n/2}+d,(c.size=d.size=n/2) xy = ac2^n+(ad+bc)2^{n/2}+bd
上述式子用了ac、ad、bc、bd四次乘法,可以优化为:
xy = ac2^n+((a-b)(d-c)+ac+bd)2^{n/2}+bd
只进行了ac、bd、(a-b)(d-c)三次乘法。
例:多项式乘积
计算两个n阶多项式的乘法:
p(x) = a_0x^0+a_1x^1+a_2x^2+\dots+a_nx^n q(x) = b_0x^0+b_1x^1+b_2x^2+\dots+b_nx^n
采用一般的方法计算,需要(n+1)2次乘法运算和n(n+1)次加法运算。
优化:
将一个多项式分为两个:
p(x) = p_0(x) + p_1(x)x^{n/2}
q(x) = q_0(x) + q_1(x)x^{n/2}
则:
p(x)q(x) = p_0(x)q_0(x)+[p_0(x)q_1(x)+p_1(x)q_0(x)]x^{n/2}+p_1(x)q_1(x)x^n
引入:
r_0(x) = p_0(x)q_0(x)
r_1(x) = p_1(x)q_1(x)
r_2(x) = [p_0(x)+p_1(x)][q_0(x)+q_1(x)]
则可以转化为:
p(x)q(x) = r_0(x)+[r_2(x)-r_1(x)-r_0(x)]x^{n/2}+r_1(x)x^n
减少了一次乘法运算。
例:棋盘覆盖
在一个2^k\times 2^k个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
划分:
将2^k\times 2^k棋盘分割为4个2^{k-1}\times 2^{k-1}子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如 (b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为2×2棋盘。
![](/assets/post_img/2019-12-24/3.png