《算法与数据》PPT课件.ppt

《《算法与数据》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章算法与数据结构理解算法的基本概念理解数据结构的基本概念掌握算法的表示方法了解常用的几种数据了解算法的设计目标和方法3.1算法的基本概念算法：找出解决问题需要执行的操作，并确定操作执行的顺序（1）确定性：算法的每一种运算必须有确切的定义。（2）有穷性：一个算法总是在执行了有穷步的运算后终止。（3）可行性：算法中有待实现的运算都是可执行的。（4）输入：一个算法有零个以上的输入。（5）输出：一个算法产生一个或多个输出。3.2算法的表示自然语言(少用）流程图伪码流程图常用符号流程图例1：求5！令p＝1令i＝2使p×i，乘积依然存入变量p中使i的值加1，表

2、示为：如果i<=5,返回步骤3，如果i>5,则算法结束。例2：P56，例3.3i1输入grade的值i1+1如果i>30,继续5，否则返回2i1，取学生成绩如果grade>=60,打印Passed，否则grade<60,打印failedi1+1如果i<=30,返回6，否则算法结束伪码非正式语言，采用文字和非图形符号表示算法。介于自然语言和计算机语言之间。通俗易懂，灵活方便可读性好，容易转换成计算机能识别和处理的程序例子：P57，583.3数据结构的基本概念数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识

3、别和处理的符号的集合。数值性数据非数值性数据数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象N={0,1,2,…}学生数据对象3.3数据结构的基本概念数据元素：基本数据单位，可由多个数据项组成数据结构：逻辑结构和存储结构逻辑结构：集合，线性结构，树形结构，图形结构存储结构：顺序存储结构，链式存储结构数据类型定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.C语言中的数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值例：“课程”表格顺序存储结构：按逻辑次序依次存放在一段地址

4、连续的内存存储单元中。特点：借助数据元素在存储器中的相对位置来表示数据间的逻辑关系）优点：便于实现查找操作缺点：执行插入或删除时需要移动大量数据元素链式存储结构：数据元素映像为一个节点，节点分为数据域（存放数据元素的数据项）和指针域（元素之间的逻辑关系）特点：借助数据存放节点存储地址的指针表示数据元素之间的逻辑关系优点：执行插入或删除操作方便，不需要移动数据元素缺点：无法通过计算得出指定数据元素的存储位置3.4线性表特点：表中的元素具有相同的特性表中元素有且只有一个直接前驱元素和一个直接后继元素（表头和表尾元素除外）顺序存储结构线性表数据元素间的逻辑关

5、系借助元素间的物理位置相邻来表示(插入前)(插入后)线性链表中的节点是数据元素及其逻辑关系在计算机中的映射3.5栈(Stack)只允许在一端插入和删除的顺序表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)进栈示例顺序栈退栈示例顺序栈链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作3.6队列定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)

6、队列的进队和出队进队时队尾指针先进一rear=rear+1，再将新元素按rear指示位置加入。出队时队头指针先进一front=front+1，再将下标为front的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。3.7树与图树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root)的结点没有直接前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以

7、有0个或多个直接后继。结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点子女(child)结点双亲(parent)结点兄弟(sibling)结点祖先(ancestor)结点子孙(descendant)结点结点所处层次(level)树的高度(depth)树的度(degree)二叉树(BinaryTree)二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。图图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：图的数据元

8、素之间的关系可以是任意的3.8算法的设计目标正确性可使用性可读性效率健壮性例：查找和排序查找：