算法基本概念介绍

数据 能够被计算机输入 存储 处理 输出的一切信息 数据元素 是一个数据整体中相对独立的单位 记录文件 字符字符串 下标变量数组 数据记录 由一个或若干个数据项组成 一 几个概念 关键数据项 能唯一标识一个记录的数据项 关键字 关键项中的每一个值 数据结构的基本知识 数据的逻辑结构 数据以及数据之间的联系 如哪个元素是第一个元素 哪个元素是第二个元素 哪些元素在给定的元素之前或之后 数据的物理结构 数据在计算机中的存储方式 数据的存放方式有顺序 链接 索引 散列等 数据的处理 查找 插入 删除 合并 排序 统计 简单计算 输入 输出等 二 数据结构的研究内容 1 一般用二元组描述 B K R B代表一种数据结构K代表数据元素的集合R代表K上的二元关系的集合 1 数据的逻辑结构 2 常用的三种结构 线性结构 K 1 2 3 4 5 6 7 8 9 10 R r 表示只包含一种关系r 举例 10个学生按学号排列示意图 特点 每个数据只有一个前驱 一个后继 第一个元素无前驱 最后一个元素无后继 是1 1的关系 树型结构 举例 一个领导与被领导的关系 14人 单向 示意图 K 1 2 3 4 5 6 7 8 9 10 11 12 13 14 R r r 特点 除第一个结点外 都有一个前驱 可有多个后继 最下一层只有前驱无后继 是1 N的关系 图型结构 举例 人与人之间互相认识的关系 双向的 示意图 K 1 2 3 4 5 6 7 8 9 10 R r r 6 7 双向 特点 每个结点都可有多个前驱和多个后继 M N的关系 顺序存储把逻辑上相邻的结点存储在物理上相邻的存储单元 链接存储给结点加上指针域 每个结点的存储单元由数据域和指针域两部分组成 2 数据的存储结构 索引存储用结点的索引号来确定结点的存储地址 散列存储根据结点的值来确定结点的存储地址 查找 插入 删除 合并 排序 统计 简单计算 输入 输出等 算法实质上是针对所处理问题的需要 在数据的逻辑结构和存储结构的基础上所施加的一种运算 如何设计数据的逻辑结构如何选择数据的物理结构如何优化设计思想和技巧 学习数据结构的目的优化算法 3 数据的处理 1 算法的描述采用 类Pascal语言 一般以过程和函数的形式书写 2 算法的特点确定性有穷性可行性有0个或多个输入有输出 3 算法的评价时间复杂性 T n 依赖于问题的规模空间复杂性 S n 所占用的存储空间 一般采取事前分析估算法来评价算法 算法常见的数量级有 O 1 问题规模的变化对复杂性影响小 这类算法是十分优秀的 O n 算法复杂性是问题规模的线性函数 这类算法是很好的 O nlog2n 虽比O n 差 但仍属不错O nk 尽可能改进 使k值愈小愈好 O 2n n较大时 复杂性会变得很大 例 求Y anxn an 1xn 1 an 2xn 2 a1x a0分析 次数n是问题的规模 算法 y a 0 fork 1tondobegint a k fori 1tokdot t x 计算ak xk y y tend writeln y y 内循环计算ak xk用了k次乘法 计算y共用乘法的次数为1 2 3 n 即n n 1 2 时间复杂度为n2 空间复杂度为n 算法 b 0 1 fork 1tondob k b k 1 x y a 0 fork 1tondoy y a k b k writeln y y 增加数组b 0 至b n 用于存放x0 x1 x2 xn 则该算法的时间复杂度和空间复杂度均为2n 算法 将y的计算公式改写为y an x an 1 x an 2 a1 x a0如y 7x5 4x4 8x3 6x 2 可改写为y 7x 4 x 8 x 6 x 2 其中a5 7 a4 4 a3 8 a2 0 a1 6 a0 2 y a n fori n 1to0doy y x a i writeln y y 算法的时间复杂度为n 空间复杂度也为n 是三个算法中效果最好的 三个算法的复杂性比较如下 当n 100时 三种算法的复杂性 1 请估计下面算法的时间复杂性 以乘法作为估计时间的基础 beginfori 1tondoforj 1tondobeginc i j 0 fork 1tondoc i j c i j a i k b k j end end 2 请估计下面算法的时间复杂性 以加法作为估计时间的基础 beginx 0 y 1 fori 1tondoforj 1toidofork 1tojdox x yend 时间复杂性和空间复杂性在一定条件下是可以相互转化的 由于目前计算机硬件发展很快 内存空间比较充分 因此在算法设计时 常会采用用空间换时间的作法 以优化程序的设计 线性表 linear list 是最常用 最简单的一种数据结构 一 顺序存储1 定义constlmaxlen 最大长度 typeelemtype 元素的数据类型 list recorddata array 1 lmaxlen ofelemtype last 0 lmaxlenend 线性表 初始化initial a 设置一个空的线性表a 求长度length a 求数据元素的个数 获取元素getlist a i x 取第i个元素 定位loclist a x 搜索第一个值为x的数据元素的序号 若不存在 则返回0 插入inslist a i x 把给定元素x插入到线性表的第i个位置 删除dellist a i 删除第i个数据元素 判断线性表是否满fulllist a 判断线性表是否空emplist a 2 基本操作 1 单链表定义typeelemtype 单链表中结点的数据类型 link node node recorddata elemtype next linkend 二 链接存储 2 单链表基本操作 初始化intlkst head 为单链表建立头元素 建立单链表crtlkst head 求单链表的长度lenlkst head 求出元素个数 求单链表中第i个元素的位置getlkst head i 取第i个元素的指针 函数值为link类型 插入元素inslkst head i x 在第i个元素之前 删除第i个元素dllkst head i 查找元素loclkst head x 返回该元素在链表中第一次出现的结点指针 否则返回空指针 判断链表是否为空 emplkst head 3 双向链表基本操作 在单链表中 从某个结点出发只能顺指针往后查找结点 若要寻找某个结点的前驱 只有从表头指针出发 双向链表 在每个结点中设置两个指针域 分别用以指向其前驱结点和后继结点 第一个结点无前驱 最后一个结点无后继 3 循环链表基本操作 附加表头结点 在第一个结点之前增加一个结点 并让头指针指向这个结点 带附加表头结点的单链表和双向链表 带附加表头结点的循环单链表和循环双向链表 栈 stack 限定只能在表尾进行插入 删除数据元素的线性表 后进先出表LIFO 栈顶 top 允许插入和删除数据元素的一端 栈底 bottom 固定的一端 空栈 不含任何元素 进栈 压栈 插入元素 出栈 退栈 删除元素 一 栈的概念 栈 二 顺序存储1 定义用一组连续的存储单元依此存放自栈底到栈顶的数据元素 同时设立指针top 称为栈顶指针 以指示栈顶元素的当前位置 1 设栈S的初始状态为空 现有序列1 2 3 4 5 对该序列在栈S上依次进行如下操作 从序列中的1开始 进栈 进栈 进栈 出栈 进栈 出栈 进栈 问出栈的元素序列是 3 4 2 若进栈的序列是1 2 3 4 5 问能否得到出栈序列4 3 5 1 2 1 2 3 出栈的元素 3 3 4 4 4 5 出栈的元素 1 2 3 4 4 4 3 3 5 5 5 此时能出栈的只能是2 不能 constsmaxsize 栈的最大长度 typeelemtype 栈中元素的数据类型 stack recorddata array 1 smaxsize ofelemtype top 0 smaxsizeend vars stack 2 基本操作 栈的初始化setnull s 将s设为空栈proceduresetnull vars stack begins top 0end 判断栈空sempty s true或false functionsempty s stack boolean beginsempty s top 0 end 入栈push s x 若栈S不满 把元素x插入到栈顶 否则返回信息overflow 上溢 procedurepush vars stack x elemtype beginifs top smaxsizethenwriteln overflow elsebegins top s top 1 s data s top xendend 出栈pop s x 若栈s不空 把栈顶元素赋给x 栈顶指针下移 否则返回信息underflow 下溢 procedurepop vars stack varx elemtype beginifs top 0thenwriteln underflow elsebeginx s data s top s top s top 1 endend 出栈也可用函数来实现 functionpop vars stack elemtype beginifs top 0thenwriteln underflow elsebeginpop s data s top s top s top 1 endend 出栈操作之后 原栈顶元素依然存在 只是栈顶指针下移 不再指向它 取栈顶元素readtop s 若栈s不空 返回栈顶元素的值 否则返回信息underflow functiongettop s stack elemtype beginifs top 0thenwriteln underflow elsereadtop s data s top end 提醒 这个算法中栈顶指针保持不变 注意与pop s 的区别 当应用中需设立两个栈时 元素类型一致 可以使它们共享一维数组空间s 1 max 两个栈的栈底分别设在数组两端 让两个栈彼此迎面 增长 仅当两个栈的栈顶指针在中间相遇时才发生 上溢 栈1 栈2 3 双栈操作 constt 可用空间大小 typeelemtype 栈中元素的数据类型 bothstack recorddata array 1 t ofelemtype top1 top2 0 t 1end varbs stack k 1 2 k 1表示栈1 k 2表示栈2 栈满 上溢 下溢条件各是什么 置空栈算法插入算法删除算法 例1 程序员输入程序 出现差错时可以采取以下的补救措施 敲错了一个键时 可以补敲一个退格符 以表示前一个字符无效 发现当前一行有错 可以敲入一个退行符 以表示 与前一个换行符之间的字符全部无效 如 在终端上输入了这样两行字符PRKJ OGRAN MLX VAR CONSTN 10 则实际有效的是 PROGRAMLX CONSTN 10 三 栈的应用 分析 可在程序中设一个栈来逐行处理从终端输入的字符串 每次从终端接受一个字符后作如下判别 既不是退格符 也不是退行符 则将该字符插入栈顶 是退格符 则从栈顶删去一个字符 是退行符 就把字符栈清为空栈 请看 COM N89 ST C O M M出栈 M N 8 9 9出栈 8出栈 9 8 S T programp 1 input output typestack recorddata array 1 100 ofchar top 0 100 end vars stack ch char i integer 程序 proceduresetnull vars stack 置栈为空 begins top 0end procedurepop vars stack 出栈 beginifs top 0thenwriteln underflow elses top s top 1 end procedurepush vars stack x char 入栈 beginifs top 100thenwriteln overflow elsebegins top s top 1 s data s top xendend Begin 主程序 whilenoteofdo eof为全文结束符 beginsetnull s whilenoteolndo eoln为行结束符 beginread ch casechof pop s 出栈 setnull s 置栈为空 elsepush s ch 入栈 end end fori 1tos topdowrite s data i 输出 writeln read ch endEnd 后缀表达式 把每个运算符移到它的两个运算对象的后面 删除所有括号 分析 栈S用来存放原始数据 中间结果和最终结果 将后缀表达式以 结束存入字符数组 且每个数据后面加一个空格 扫描中 数据入栈 遇到运算符 就依次弹出两个操作数进行运算 运算结果入栈 遇到字符 结束 栈顶的值就是算式的结果 例2 后缀表达式的求值 后缀表达式16943 在字符数组A中的形式为 栈中的变化情况 运行结果 47 programp2 input output typestack recorddata array 1 100 ofreal 存放实型数 top 0 100 end vars stack ch char i integer x real a array 1 30 ofchar functionpop vars stack real 出栈 beginpop s data s top s top s top 1 end 程序 procedurepush vars stack x real 入栈 begins top s top 1 s data s top xend begin 主程序 i 0 repeati i 1 read a i 将表达式存入数组a untila i s top 0 清空栈 i 1 i为a数组的下标 ch a i whilech dobegincasechof 0 9 begin 产生完整的数 x 0 whilech dobeginx x 10 ord ch ord 0 i i 1 ch a i end end x pop s pop s beginx pop s x pop s x end x pop s pop s beginx pop s x pop s x end end push s x 将上面得到的x入栈 i i 1 ch a i 继续扫描a数组 end writeln pop s end 分析 9 6 8 5 2 字符数组E 9 6 8 5 用以存放算符 2 结果数组A 后缀 入栈 入栈 入栈 入栈 出栈 出栈 出栈 入栈 出栈 出栈 结束 例3 中缀表达式转化为后缀表达式 算法描述 procedurechange beginsetnull s push s 清空栈 进栈 i 1 j 1 ch e i i是e的下标 j是a的下标 whilech dobeginifchinop1thenbegin op1为数字字符集合 whilechinop1thenbegina i ch j j 1 i i 1 ch e i end 处理数字 a j j j 1 数字后加空格 end ifchinopthenbegin op为算符集合 w readtop s 取栈顶元素 whileprecede w ch dobegina j w j j 1 pop s w readtop s end ifprecede w ch thenpush s ch ifprecede w ch thenpop s 左右括号相遇 end I I 1 ch e i end a j end constcha array 1 7 ofstring typestack array 1 100 ofchar vartop i j integer ch w char a s stack 程序 procedurepush vars stack ch char begininc top s top ch end procedurepop vars stack begindec top end functionreadtop s stack char beginreadtop s top end functiont p1 p2 char char varx1 x2 1 7 begincasep1of x1 1 x1 2 x1 3 x1 4 x1 5 x1 6 x1 7 end casep2of x2 1 x2 2 x2 3 x2 4 x2 5 x2 6 x2 7 end t cha x1 x2 end beginpush s i 1 j 1 read ch whilechchr 13 dobeginifchin 0 9 thenbeginwhilechin 0 9 dobegina j ch inc j inc i read ch end a j inc j end ifchin thenbeginw readtop s whilet w ch dobegina j w inc j pop s w readtop s end ift w ch thenpush s ch elsepop s end inc i read ch end w readtop s pop s whilew dobegina j w inc j w readtop s pop s end forj 1toidowrite a j writeln end 9 6 8 5 2 9 6 3 2 9 2 2 9 4 5算符优先算法中把运算符和左右括号统称为运算符 在运算的每一步中 任意两个相继出现的算符P1和P2之间的优先关系为下面三种关系之一 E可认为出错 P1P2表示P1的优先权高于P2 例4 中缀表达式的求值 在表达式的开始和结束各设置一个 构成整个表达式的一对括号 当 与 相遇时 表示整个表达式运算结束 9 6 8 5 2 使用算符优先算法计算表达式时 需要设立两个工作栈 一个是算符栈 fu 用以存储算符 包括 另一个是操作数栈 shu 用于存储操作数 中间结果和最终结果 算法的主要思路如下 初始化栈fu和shu 读入第一个算符 入栈fu 则 为栈底元素 读入下一个字符x 若x 且fu栈顶元素为 时 转 若x为数字 则将x入栈shu 转 若x为算符 则将x作为P2 fu栈顶元素作为P1 比较P1与P2的优先权 若P1P2 则弹出fu栈顶元素赋给OP变量 连续弹出shu栈顶元素分别赋给b a 并计算aOPb 将结果压入栈shu 转 取shu栈顶元素输出 即运算结果 结束 9 6 8 5 2 9 6 8 5 此时 X为 即P2为 P1是 P1 P2 则从fu中弹出 从shu中弹出5 8分别给b a 算出8 5 3 将3入栈shu 5 8 3 此时 X为 即P2为 P1是 P1 P2 则从fu中弹出 从shu中弹出5 8分别给b a 算出8 5 3 将3入栈shu 此时 P2仍为 P1为 则P1 P2 出栈 此时 P1仍为 P2为 则P1 P2 出栈 重读X为 P2为 P1为 则P1 P2 3 6出栈 出栈 6 3 2 则2入栈shu 3 6 2 P2为 P1为 则P1 P2 进栈 2 重读X为 P2为 P1为 则P1 P2 2 2出栈 出栈 2 2 4 则4入栈shu 2 2 4 P2为 P1为 则P1 P2 4 9出栈 出栈 9 4 5 则5入栈shu 4 9 5 此时 X为 fu的栈顶元素为 结束 结果在栈shu中 算法描述 procedurebds beginsetnull fu setnull shu push fu 将 压栈 作为fu栈的栈底元素 read x 读入算式的第一个字符 while x and readtop fu doifxnotinopthenpush shu x elsecaseprecede readtop fu x of 比较fu栈顶元素与x的优先权 beginm pop fu b pop shu a pop shu push shu operate a m b end p1 p2 就弹出fu的栈顶运算符 弹出shu的两个运算数 求出的运算结果入栈shu end writeln readtop shu 最终保留在栈shu中的就是整个算式的运算结果 end 四 链接存储的栈 只允许在表头进行插入和删除运算的单链表 HS为栈顶指针 也是单链表的表头变量 typeelemtype 结点的数据类型 link node node recorddata elemtype next linkend 1 置空栈的算法setnull hs 不回收结点的算法 proceduresetnull hs link beginhs nil end 回收结点的算法 proceduresetnull hs link beginwhilehsnildobeginp hs hs hs next dispose p end end 2 进栈算法push hs x procedurepush hs link x elemtype beginnew p p data x p next hs hs p end 3 出栈算法pop hs functionpop hs link elemtype beginifhs nilthenwriteln underflow pop hs data p hs hs hs next dispose p end 4 读取栈顶元素readtop hs functionreadtop hs link elemtype beginifhs nilthenwriteln underflow elsereadtop hs dataend 5 判断栈空sempty hs functionsempty hs link elemtype beginsempty hs nil end 五 栈与递归 pascal语言中 如果在一个函数 过程等的定义或说明内部又直接或间接地出现有对自身的引用 则称它们是递归的或者是递归定义的 例如 在数学上 所有偶数的集合可递归地定义为 0是一个偶数 一个偶数和2的和是一个偶数 可见 仅需两句话就能定义一个由无穷多个元素组成的集合 在程序中 递归是通过函数或过程的调用来实现的 函数或过程直接调用其自身 称为直接递归 函数或过程间接调用其自身 称为间接递归 例1 用递归计算n n 可以由下列公式表示 这是递归定义简单而典型的例子 程序 programp1 input output varn integer s integer functionfac a integer integer beginifa 0thenfac 1elsefac a fac a 1 end beginreadln n s fac n writeln n s end a 5 fac 5 a 4 fac 4 a 3 fac 3 a 2 fac 2 a 1 fac 1 a 0 fac 0 栈用于存放递归调用中不断产生的新的局部变量 a 0 fac 0 a 1 fac 1 a 2 fac 2 a 3 fac 3 a 4 fac 4 a 5 fac 5 1 1 2 2 1 1 6 6 24 24 120 在调用过程或函数之前 系统需完成三件事 将所有的实在参数 返回地址等信息传递给被调用过程保存 为被调用过程的局部变量分配存储区 将控制转移到被调过程的入口 从被调用过程返回调用过程之前 系统也应完成三件工作 保存被调过程的计算结果 释放被调过程的数据区 依照被调过程保存的返回地址将控制转移到调用过程 当有多个过程构成嵌套调用时 按照 后调用先返回 的原则 例2 用递归方法求两个数m和n的最大公约数 m 0 n 0 求两个数的最大公约数可以用辗转相除法 即求m与n的最大公约数等价于求 mmodn 的值与n的最大公约数 此时的n可以当作新的m 而 mmodn 的值当作新的n 所以原问题的求解又变成求新的m与n的最大公约数问题 继续下去 直至 mmodn 为0 最大公约数就是最终存放在n中的值 递归公式 programp input output varm n g integer functiongcd m n integer integer varr integer beginr mmodn ifr 0thengcd nelsegcd gcd n r 递归调用 end begin 主程序 read m n g gcd m n writeln m m n n gcd g end 例3 汉诺塔 towerofHanoi 问题 有n个大小不等的中空圆盘 按照从小到大的顺序迭套在立柱A上 另有两根立柱B和C 现要求把全部圆盘从A柱 源柱 移到C柱 目标柱 移动过程中可借助B柱 中间柱 移动时有如下的要求 一次只移动一个盘 不允许把大盘放在小盘上边 可使用任意一根立柱暂存圆盘 先以三个盘的移动为例 看一下移动过程 分析 首先将A柱上方的n 1个盘子从A柱移到B柱 此过程中C柱为中间柱 接着将A柱剩下的一个盘子移到C柱 最后再将B柱上的n 1个盘子移到C柱 此过程中A柱为中间柱 这就变成了移动n 1个盘子的问题了 定义过程move 实现这一递归算法 若n 1 则A C若n 2 则move n 1 A C B A Cmove n 1 B A C 运行结果 EnterthenumberofdisksinHanoitower 3A CA BC BA CB AB CA C 程序 1programch720 input output 2var3total integer 4proceduremove n integer z1 z2 z3 char 5begin6ifn 1thenwriteln z1 z3 7elsebegin8move n 1 z1 z3 z2 9writeln z1 z3 10move n 1 z2 z1 z3 11end12end 13begin 主程序 14write Enterthenumberofdisks 15readln total 16move total A B C 17end 上面程序中的语句move 3 A B C 在执行过程中 递归工作栈要为每一层的递归保留数据 由于递归过程move只含有四个值参数 也无其它局部变量 因而每一层递归需记录五个数据项 返回地址和四个值参 栈中内容为返回的程序行号 参数n 参数z1 参数z2 参数z3 栈中内容为返回的程序行号 参数n 参数z1 参数z2 参数z3 六 栈与回溯 例 自然数的拆分 任何一个大于1的自然数总可以拆分成若干个自然数之和 4 1 1 1 14 1 1 24 1 3