《程序设计数据结构ppt演示文稿》由会员分享，可在线阅读，更多相关《程序设计数据结构ppt演示文稿（50页珍藏版）》请在金锄头文库上搜索。
1、2,语言是人们交流思想、传达信息的工具。如汉语和英语等，通常称为自然语言。 另一方面，人们为了某种专门用途，创造出种种不同的语言，例如旗语和哑语等，通常称为人工语言。 专门用于人与计算机之间交流信息的各种人工语言称为计算机语言或程序设计语言。,第二节 程序设计基础,3,用计算机解决一个问题，必须事先设计好计算机处理信息的步骤，把这些步骤用计算机能够识别的指令编写出来并送入计算机执行，计算机才能按照人的意图完成指定的工作。,4,软件和程序并不是同一个概念（软件 程序）。 软件是程序、数据和相关的文档资料的总和。软件=程序+数据+相关文档资料 编制程序的工作就是程序设计（Programming），
2、而软件开发（Software development）包括需求文档、设计概要、详细设计、编码、测试、发布，而程序设计则主要是指程序代码的编写，是软件开发的一部分。,5,程序设计也不是简单的编写程序代码，它反映了利用计算机解决问题的全过程。 先要对问题进行分析并建立数学模型或提出对数据处理的需求，然后进行算法设计，并用某一种程序设计语言编写程序，最后调试程序，使之运行后能产生预期的结果，这个过程称为程序设计。,程序设计要经过以下4个基本步骤：,（1）分析问题，确定数学模型。弄清问题的要求，输什么数据、得什么结果、输出什么。把实际问题简化，用数学语言来描述它，建立数学模型。选择计算方法（用计算机求
3、解该数学模型的近似方法）。,（2）设计算法（Algorithm），画出流程图。把问题的数学模型或处理需求转化为计算机解题的步骤。解决一个问题，可能有多种算法。通过分析、比较，挑选一种最优的算法。算法设计后，要用流程图把算法形象地表示出来。,步骤1: 1*2=2 步骤2: 2*3=6 步骤3: 6*4=24 步骤4: 24*5=120,S1：n=1 S2：i=2 S3：n*in S4：i+1i S5：如果i的值不大于5，重新执行S3和S4，否则，算法结束。,Y,开始,n=1,i=2,n*in,i+1i,i5,结束,N,流程图,当今计算机数据处理的特点： 所处理的数据量大且具有一定的关系； 对其操
4、作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。,11,数据结构主要研究和讨论以下三个方面的问题： 1.数据集合中各数据元素之间所固有的逻辑关系- 逻辑结构。,12,处理大量数据时，要找到这些数据之间的固有关系。 如学生成绩处理：每一个元数据包含学号、姓名、分数等，查询分数时常常按学号值的次序查找，学号决定该数据元素在集合中的位置，位置的前后次序就是我们要找的固有关系，称之为数据的“逻辑结构”。,数据结构主要研究和讨论以下三个方面的问题： 2.数据处理时，数据元素在计算机中的存储关系- 存储结构。,13,处理数据时，要将这些数据存入计算机的存储器中，存储数据时要保留数据元素的固
5、有关系，不能随意存储。 存储数据的方式称之为数据的“存储结构”。常用的“存储结构”有：顺序存储和链式存储。,数据结构主要研究和讨论以下三个方面的问题： 3.对各种数据结构进行的运算。,14,“存储结构”确定后，程序员通过“存储结构”可以推导出数据的“逻辑结构”从而对数据实现： 插入、删除、修改、查找、排序等操作。,描述数据结构 大量具有固有逻辑关系数据集是数据结构，其中包含的个体称为数据元素。 在数据处理领域中，通常把数据元素之间的这种固有的关系简单地用前后件关系来描述。 数据元素的逻辑结构常用图形表示。,15,线性 有且只有一个根结点（没有前件的结点）。 每一个结点最多只有一个前件，也最多只
6、有一个后件。 线性结构任意删除一个元素后，仍然是线性结构。,16,非线性 如果数据结构不满足线性结构的条件，则称之为非线性结构。,17,18,全校学生档案管理的组织方式,非线性结构树形结构,19,线性表的定义线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2， ，ai， ，an 其中n称作表的长度，当n=0时，称作空表。,20,线性表结点间是以线性关系联结,21,线性表的特点： 1.线性表中所有元素的性质相同。 2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前件和一个后件。第一个数据元素无前件，最后一个数据元素无后件。 3.数据元素在表中的位置只取决于它自
7、身的序号。 在线性表上常用的运算有： 初始化、求长度、取元素、修改、前插、删除、检索、排序。,22,线性表的顺序存储结构,线性表顺序存储结构的特点：1、线性表所有元素所占的存储空间是连续的。2、线性表各数据元素在存储空间中是按逻辑顺序依次存放的。,在计算机中存放线性表，采用顺序存储是一种简单方便的方法。,首地址 ADR(a1),23,元素an,元素ai,元素a2,元素a1,存储地址,内存状态,顺序存储结构示意图(顺序表)：,每个元素所占用 的存储单元个数,ADR(ai) =ADR(a1) + (i-1)* k,n-1,线性表的插入和删除运算示意图,ai-1,a2,a1,an,ai+1,ai,2
8、5,线性表顺序存储,线性表的链式存储结构,将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。 数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。,26,27,线性链表表示法:,0,链式存储结构的特点,插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。 适合于线性表是动态变化的,不进行频繁查找操作、但经常进行插入删除时使用。 链表的查找只能从头指针开始顺序查找。,28,29,线性链表的插入运算,在H所指向的结点之后插入新的结点,线性链表的运算,30,H,线性链表的删除运算,在H所指向
9、的结点之后删除新的结点,线性链表的运算,H,31,H,线性链表的删除运算,在H所指向的结点之后删除新的结点,线性链表的运算,H,32,线性表链式存储,1.缺点：比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成)。 定位时必须按顺序进行。 2.优点：逻辑上相邻的节点物理上不必相邻。 插入、删除灵活 (不必移动节点，只要改变节点中的指针)。,链接存储结构特点：,顺序查找（线性查找）,查找过程：对给定的关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。 可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上
10、元素进行比较，效率较低。平均查找长度较大。最坏情况为n。,34,顺序查找（线性查找）,在下面两种情况下只能采取顺序查找：a. 线性表为无序表（元素排列是无序的）。b. 即使是有序线性表，但采用的是链式存储结构。,35,二分法查找（折半查找）,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 三种情况： 1）若中间项的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找效率高。最坏的情况下，需要比较 log2n次。,36,
11、查找23的过程如下图：,mid=(low+high)/2不进位取整,( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),37,栈和队列,栈和队列的定义栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。,栈的定义 栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为先进后出(FILO)或后进先出(LIFO) 设栈s=（a1，a2，. . . ,ai，. . . ，a
12、n） 其中a1是栈底元素， an是栈顶元素。栈顶（top)：允许插入和删除的一端； 栈底（bottom):不允许插入和删除的一端。 约定用指针top始终指向栈顶的位置， 用指针bottom指向栈底。,39,栈的顺序存储结构及其基本运算,用顺序存储结构表示的栈顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向栈顶元素的位置。,基本运算： 压(进)栈：PUSH 出 栈：POP 读栈顶元素,空栈,A进栈,B进栈,K进栈,L进栈溢出,栈满：栈顶指针指向存储空间的最后一个位置,进栈示例,K出栈,E出栈,D出栈,A出栈,空栈,出栈示例,42,
13、队列( Queue )的定义 定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。,队列示意图,队列只允许在队尾插入，在队头删除。 队头指针：front：指向排头元素的前一个位置 队尾指针：rear：指向队尾元素 此种结构称为先进先出（FIFO）或后进后出(LILO)。,插入,插入,43,队列的主要运算,（1）插入一个新的队尾元素，称为进队； （2）删除队头元素，称为出队； （3）读取队中元素（检索）；,当有新元素入队时，尾指针加1， 当有元素出队时，头指针加1。 故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置。,空队,A进队
14、,B进队,CD进队,A出队,队列的进队和出队示例,EF进队,进队时队尾指针先进：rear = rear + 1，再将新元素按 rear 指示位置加入。出队时队头指针先进：front = front + 1，再将下标为 front 的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。,队满：队尾指针指向存储空间的最后一个位置,45,树与二叉树,全校学生档案管理的组织方式,46,树的定义 由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。 在树结构中，每一个节点只有一个前件，称为它的父节点，每一个节点可以有多个后件，称为它的子节点。没有前件只有后件的节点只有一个，
15、称为树的根节点，简称树的根。没有后件只有前件的节点称为叶子节点。,47,结点(node) 结点的度(degree) 叶子(leaf)结点子(child)结点 父 (parent)结点 兄弟(sibling)结点结点所处层次(level) 树的高度(depth) 树的度(degree),树的性质,48,二叉树 （Binary Tree）,二叉树的定义： 二叉树是每个结点最多有两个子树的有序树。,二叉树的五种基本形态,二叉树与树结构类似，树的术语都可用在二叉树上。 二叉树的特点是：1.非空二叉树至少有一个结点；2.每个结点最多有两棵子树，且子树有左右之分，次序不能颠倒。,二叉树的遍历,查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。 遍历定义及遍历算法遍历：按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。 按先左后右的原则，一般使用三种遍历： 先序遍历(D L R): 访问根结点，按先序遍历左子树，按先序遍历右子树。 中序遍历(L D R):按中序遍历左子树，访问根结点，按中序遍历右子树。 后序遍历(L R D):按后序遍历左子树，按后序遍历右子树，访问根结点。,49,50,先序遍历(D L R):ABCDEF 中序遍历(L D R):CBDAEF 后序遍历(L R D):CDBFEA,
