文档介绍：3A_算法与数据结构KANG
算法与数据结构康金辉
网络信息中心电气工程系
一什么是算法计算机解决问题的步骤 1问题分析解决什么问题 2算法设计重点算法的设计和数据结构的设计 3程序设计编程 4程序测试和维护排除错误修正 1什么是算法algorithm 解决某一特定问题的具体步骤的描述是指令的有限序列事后统计根据算法运行后的状态统计分析而得必须先运行依据算法编制的程序所得时间统计量依赖于硬件软件等环境因素掩盖算法本身的优劣 3算法表示流程图略伪代码略 4算法的复杂度 A 时间复杂度基本操作重复执行的次数的阶数不好理解时间频度一个算法中的语句执行次数称为语句频度或时间频度记为T n n称为问题的规模当n不断变化时时间频度T n 也会不断变化但有时我们想知道它变化时呈现什么规律为此我们引入时间复杂度概念一般情况下算法中基本操作重复执行的次数是问题规模n的某个函数用T n 表示若有某个辅助函数f n 使得当n趋近于无穷大时 Tn f n 的极限值为不等于零的常数则称f n 是T n 的同数量级函数记作 T n O f n 称O f n 为算法的渐进时间复杂度简称时间复杂度常见的时间复杂度有常数阶O 1 对数阶O log2n 线性阶O n 线性对数阶O nlog2n 平方阶O n2 立方阶O n3 k次方阶O nk 指数阶O 2n 随着问题规模n的不断增大上述时间复杂度不断增大算法的执行效率越低空间复杂度指算法所需存储空间方法1用三重循环 for I 0 I 100 I for j 0 j 100 j for k 0 k 100k if k3 0 Ijk 100 5I3jk3 100 printf ddd\n Ijk 5常见算法枚举法列出所有可能性如刚才的三重循环问题长度为6位的密码有多少 a-zA-Z0-9 z 11个共73个共有3 个车牌陕A-12345 个迭代法 x3-x 1 化简为x x1 开立方给初值求x0在继续迭代直到 xn-xn-1 e 即可递归法分治法分而治之二数据结构线性表链表堆栈队列树与二叉树图排序和查找文件三线性表线性表由一组数据元素构成 a1a2aian 其中ai i 12n 是属于数据对象的元素通常也称其为线性表中的一个结点
①线性表中所有元素所占的存储空间是连续的②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的线性表的插入运算 if i>n–1 i n1 在线性表的最后插入 if i<1 i 1 在线性表的第1个元素之前插入 for j nj< ij––插入位置以后的元素依次往后移动一个位置 v[j] v[j–1] v[i–1] X 插入元素X n n1 线性表长度加1 return 线性表的删除运算 if i<1 i>n 线性表中没有这种下标的元素返回 printf Not this element in the list \n return for j ij< n–1j 第i个以后的元素依次往前移动一个位置 v[j–1] v[j] n n–1 线性表长度减1 return 四栈栈 stack 是按照先进后出的规则进行运算的数据结构往栈中插入一个元素称为入栈运算从栈中删除一个元素即删除栈顶元素称为退栈运算四队列队列equeue是指允许在一端进行插入而在另一端进行删除的线性表允许插入的一端称为队尾允许删除的一端称