算法与数据结构基础.ppt
《算法与数据结构基础.ppt》由会员分享,可在线阅读,更多相关《算法与数据结构基础.ppt(87页珍藏版)》请在三一办公上搜索。
1、1,第六章 算法与数据结构基础,计算机程序主要对数据进行加工和处理。程序中需要说明,数据结构:数据的组织形式和存储方式,算法:操作数据的步骤和方法,数据结构,算法,2,6.1 数据结构基本概念,随着计算机技术的发展,其应用领域越来越广。计算机应用已不在局限于数值计算,更多地用于数据处理和信息管理等非数值计算。,例如:学生、图书、财务和人事等信息管理系统。,每个学生对应一个数据,由学号、姓名、性别和出生日期等多个数据项构成,通常对学生信息进行插入、删除或查找等操作。,3,数据结构的定义,数据结构是指具有相同特征、相互之间有关联的数据集合。现实世界中每个对象都可以映像成数据元素。数据元素可以由一个
2、数、一个字符或一个名字等单个数据项组成,也可以由多个数据项组成。,数据元素、结点,数据结构中数据元素都具有某种共同特征数据结构中数据元素之间存在着某种关系,4,向量2,43,68,45,32是数据结构,每个数据元素由一个数据项组成数据元素之间有位置上的前后关系,每个数据元素由一个数据项组成数据元素之间有位置上的前后关系,季度名称组成的集合是数据结构:春,夏,秋,冬,家庭成员祖父、父亲、儿子是数据结构,每个数据元素由一个数据项组成数据元素之间有层次上的高低关系,5,数据结构是指带有结构特性的数据元素集合。主要研究:数据集合中数据元素之间所固有的关系,即数据逻辑结构;数据处理时数据在计算机中的存储
3、关系,即数据存储结构(物理结构);对数据所进行的操作,即算法。,6,数据逻辑结构,数据结构中数据元素之间所固有的关系描述成前后件(前驱与后继)关系。数据之间前后件关系是它们之间的逻辑关系,与它们在计算机中的存储位置无关,因此将这种关系称为逻辑结构。,7,一个数据结构可以表示为 S=(D,R),季节数据结构可以定义成 S=(D,R)其中:D=春,秋,冬,夏 R=(春,夏),(夏,秋),(秋,冬),S表示数据结构,D数据元素集合,向量数据结构可以定义成 S=(D,R)其中:D=2,43,68,45,32 R=(2,43),(43,68),(68,45),(45,32),8,线性结构:,一般来说,数
4、据之间有集合,线性,树型和图形 4 种基本逻辑结构。,数据元素之间是一对一的关系除第一个结点无前件外,其他结点都 只有一个前件除最后一个结点无后件外,其他结点都只有一个后件,9,数据之间存在一对多的关系一个结点最多有一个前件,可以有多个后件前件与后件之间有层次关系,一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。,树型结构:,10,数据元素之间存在多对多的关系一个结点可以有多个前件和多个后件,一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。,图形结构:,11,一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。,集合:是一种松散结构,数据元素之间的关
5、系只是同属于一个集合,可以用其他结构来表示。,12,数据物理结构,数据在计算机存储器中的存储方式称为数据物理结构(数据存储结构)。在数据存储结构中,不仅要存放各个数据元素信息,还要存放数据元素之间前后件关系信息。数据元素在计算机中通常有四种存储方式:顺序、链式、索引和散列。,13,顺序存储结构,顺序存储结构是在内存中开辟一块连续内存单元用于存放数据,逻辑上相邻的结点在物理位置上也相邻。即:结点之间的逻辑关系由存储单元的相邻关系来体现。,14,有如下顺序关系 a,b,c,d,例如:,a,地址,2000H,2001H,c,2002H,2003H,d,数据,顺序存储结构,如果在b和c之间增加新数据x
6、构成 a,b,x,c,d的顺序关系,应该如何存储?,b,15,链式存储结构,链式存储结构中,结点由两部分组成:用于存放数据元素(数据域)用于存放前件或后件的存储地址(指针域)即:通过指针反映数据元素之间的逻辑关系,16,链式存储结构,有如下顺序关系 a,b,c,例如:,a,2000,b,c,3001,1003,3001,1003,17,顺序存储结构与链式存储结构比较,顺序存储结构:优点:每个结点占用存储空间最少 缺点:如果数据元素很多,则可能找不到一块足够大的连续存储单元 不能很好利用存储单元,容易产生碎片,链式存储结构:优点:充分利用所有存储单元缺点:每个结点占用较多存储单元,18,链式存储
7、的插入,J,L,U,在J,L之间插入接点S,链式存储的删除,J,L,U,删除接点L,显然,链式存储的插入和删除操作比较简单、方便,19,6.2 算法基本概念,程序包含两方面的内容:对数据的描述 对操作的描述 算法就是操作步骤,是解决“做什么”和“怎么做”的问题。算法是程序的灵魂,广义来说,为解决一个问题而采取的方法和步骤就称为算法。,20,计算机算法分为:数值算法 非数值算法,各种数学问题的解法,常用于事物管理领域,如排序、查询,算法是定义在逻辑结构上的操作,独立于计算机,但算法的实现依赖于数据的存储结构。,21,算法的特征,可行性确定性有穷性输入输出,采取的方法和步骤可行,结果另人满意。,算
8、法中的每一个步骤都必须确定,不能产生歧义。,执行算法时从外界取得必要的信息。一个算法可以有零或多个输入。,算法得到的结果就是输出,没有输出的算法是没有意义的,一个算法应该有一个或多个输出。,算法必须由有限步组成,并能在有效时间内完成。,22,算法描述方法,计算,写出其算法。,分析:,1、展开上面算式 S=1+2+3+99+100,23,计算,写出其算法。,main()int s=0;s=1;s=s+2;s=s+3;s=s+99;s=s+100;printf(“s=%d/n”,s);,利用程序设计中的顺序结构,很不理想算法,24,用于描述算法的工具很多,通常有流程图、N-S图、自然语言和伪代码等
9、工具。,自然语言:带序号的人类语言描述方法。,将变量s清0;将变量n置1;把s+n的值赋给s;把n+1的值赋给n;判断 n 100?是否成立,若成立,转3;否则转66.输出s的值;,S=1+2+3+99+100,特点:易懂却不直观,对复杂算法描述很困难,易产生歧义。,若成立,25,伪代码法:是一种假的代码不能被计算机所理解,但可以用你熟悉的计算机语言的语句加上自然语言构成。,26,用于描述算法的工具很多,通常有流程图、N-S图、自然语言和伪代码等工具。,流程图法:用一些图框、线条以及文字说明 来形象地、直观地描述算法。,符号说明:,27,开始,0 S,1 n,Sn S,n1 n,输出S,结束,
10、T,F,n 100,S=1+2+3+99+100,优点:直观形象缺点:算法复杂时,篇幅 较多,费时且不方便修改。,28,N-S图:完全去掉了带箭头的流程线、算法的所有处理步骤都写在一个大矩形框内,框内还可以包含一些从属于它的小矩形框,适于结构化程序设计。,29,算法评价,在计算机程序设计中,某一任务的算法设计得优与劣,将直接影响程序的运行效率、稳定性和可维护性。通常从以下4个方面评价一个算法。,正确性可读性健壮性执行效率,算法本身没有语法错误,执行时输入正确数据能够得到正确结果.,算法要容易理解和阅读,容易实现,同时也要便于程序维护和完善。,指算法执行的时间性能和空间性能。,算法能够对输入的各
11、种数据给予适当的提示和处理。,30,算法复杂度,算法复杂度是对算法效率的度量,是评价算法优劣的重要依据。一个算法复杂度高低体现在运行该算法所需要资源的多少。,时间资源空间(即存储器)资源,因而,算法复杂度包含时间复杂度和空间复杂度。,时间复杂度指执行算法所需时间:执行时间=语句执行时间语句执行次数,空间复杂度指在算法执行过程中,所占用附加空间数量,31,6.3 典型数据结构,数据逻辑结构分为:线性结构 非线性结构,有且只有一个开始结点和一个终端结点,并且每个结点最多只有一个前件和一个后件,线性结构也称为线性表。栈、队列、数组和串等是特殊线性表,非线性结构包括树和图,32,6.3.1 线性表,线
12、性表是一组特征相同数据的有限序列,表示为 L=(a1,a2,a3 an)。,非空线性表的特征:除a1无前件外,其它任意数据元素ai有且只有一个前件ai-1。除了an无后件外,其它任意数据元素ai有且只有一个后件ai+1。,线性表中数据元素个数n(n0)称为线性表长度。当n=0时,称为空表。在非空线性表中,每个数据元素都有一个确定位置,其位置取决于它的序号。,a1是第一个元素,a2 是第二个元素,an是最后一个元素。,33,向量2,43,68,45,32是线性表。,季度名称 春,夏,秋,冬是线性表。,学生基本信息:(20040001,刘强,男,1984/02/13,14001,机械制造),(20
13、040002,王晓红,女,1986/05/06,14001,机械制造),(20040003,李明,男,1984/10/25,14001,机械制造)是线性表。,34,线性表顺序存储结构具有以下两个基本特点:线性表中所有元素所占的存储空间是连续的。线性表中各元素在存储空间中按逻辑顺序依次存放,即线性表的逻辑结构与存储结构相一致。,线性表通常采用顺序存储结构或链式存储结构。,由此可以看出:,在线性表的顺序存储结构中,其前后两个元素在存储空间中是紧邻的,前件元素一定存放在后件元素的前面。,35,例如:线性结构 a1,a2,a3,其中每个数据元素占2个存储空间,假设存储a1的首地址为2000。,2000
14、,a1,占2个字节,a2,a3,2004,2002,占2个字节,占2个字节,存储地址:,结论:假设一个数据元素占用d个字节,线性表的首地址Addr(a1)为K,则存储任意一个数据元素ai的首地址为:Addr(ai)=Addr(a1)+(i-1)d=K+(i-1)d 其中 1 i n,优点:可以方便地随机读取表中任意元素缺点:插入和删除运算需要移动大量元素,浪费大 量时间,时间效率较低。,36,线性表的链式存储,用一组存储单元(可以连续,也可以不连续)存储线性表中数据元素。为了反映数据元素之间的逻辑关系,每个数据元素由两部分组成:1用于存放数据元素(数据域)2用于存放前件或后件的存储地 址(指针
15、域),结点之间逻辑关系由指针域来确定,37,单链表,定义:每个结点只有一个指针域的链表,head,每个单链表都有一个头指针,存放表中第一个结点的存储地址。每个结点指针域存放后件结点的存储地址,最后一个结点无后件结点,指针域为空,用NULL或 表示。,38,循环链表,循环链表中增设一个表头结点,其数据域的值可以任意或根据情况来设置,指针域指向第一个结点。,将单链表最后一个结点的空指针域改为指向该链表的第一个结点,即首尾相连。,空循环链表,非空循环链表,注意头指针和表头结点的区别,39,循环链表特点:从表中任一结点出发,均可以找到其它所有结点;在任何情况下,带有表头结点的循环链表中至少有一个结点存
16、在,从而使空表和非空表运算统一。循环链表运算与单链表区别:对单链表进行操作时,要判断是否是表尾,即指针是否为NULL;而对循环链表操作时,要判断是否是头指针。,40,栈,定义:栈是只能在表的一端进行插入和删除运算的线性表。,通常将允许插入和删除运算的一端称为栈顶(top),另一端称为栈底(bottom),不含元素的栈称为空栈。向栈中插入元素称为入栈。从栈中删除元素称为出栈。,41,设有一个栈S=a1,a2,an,入栈顺序是a1、a2最后是an。栈的状态如图所示:,a1,a2,an,栈底bottom,栈顶top,入栈,出栈,栈特点:后进先出。,故也称为“先进后出”表或“后进先出”表,42,栈的基
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 数据结构 基础
链接地址:https://www.31ppt.com/p-6596842.html