《《数据结构讲义part》ppt课件》由会员分享，可在线阅读，更多相关《《数据结构讲义part》ppt课件（116页珍藏版）》请在金锄头文库上搜索。
1、2019/1/17,1,数据结构及其应用,（用面向对象方法与C描述）,2019/1/17,2,第一章 概述,研究对象：信息的表示方法、数据的组织方法、操作算法设计 意义地位：数据结构算法程序 程序设计的基础 系统软件的核心 发展过程：数值计算 非数值计算 建立数学模型 客体及其关系的表示 设计数值计算方法 数据的组织 操作算法的设计 非数值计算应用的发展，促进了数据结构 的研究和发展以及其体系的完善。,2019/1/17,3,基本术语,数 据：描述客观事物的且能由计算机处理的数 值、字符等符号 数据元素：数据的基本单位，在计算机程序中通常 作为一个整体进行考虑和处理（记录、 结点、表目、元素）
2、 数 据 项：数据元素的某一属性。数据元素可以由 若干数据项组成，数据项可以由若干 更小的款项（组合项、原子项）组成。 数据项又称域、字段 关 键 码：能起唯一标识（数据元素）作用的数据项 数据结构：一组同类的数据元素、其间的关系及其上的 一组操作所构成的整体，称为一个数据结构,2019/1/17,4,数据结构的描述方式,逻辑结构：是对数据元素之间逻辑关系（抛开具体的关系含义以及存储方式等）的描述，它可以用一个数据元素的集合和定义在此集合上的几个关系来表示。通常可用图形表示，圆圈表示数据元素，箭头表示关系： 物理结构：数据结构在计算机中的具体表示和实现， 又称存储结构,E i,E i+1,数据
3、元素,数据元素,关系,2019/1/17,5,数据结构的分类,按逻辑结构分类： 纯集合型结构:数据元素之间除了“同属于一个集合”这一 关系外，别无其他关系 线性结构：数据元素之间存在“一个跟着一个”的序列关系 树型结构：数据元素之间存在“每个元素只能跟着一个元素 但可以有多个元素跟着它”的层次关系 图状结构：任意两个数据元素之间都可能存在关系 按存储结构分类： 顺序存储结构 链式存储结构 索引存贮结构,2019/1/17,6,基本操作：任一数据结构均有一组相应的基本操作， 有时操作不同，用途迥异（如栈和队列）,常用的基本操作有插入、 删除、查找、 更新、排序等 算 法：算法是为了解决给定的问题
4、而规定的一个 有限长的操作步骤序列，则重于解决问题 的方法和步骤。当算法由计算机语言表示 时称为程序（代码） 算法设计目标：可维护性 可靠性（正确性、健壮行） 可读性 高效率（时间、空间）,2019/1/17,7,第二章 线性表,2。1 线性表的逻辑结构 定义：由相同种类的数据元素组成的一个有穷序列称为一个线性表。“一个跟着一个” 符号表示法：L（e1,e2,en） 图形表示法：,e2,en,e1,2019/1/17,8,其中： ei -表示线性表 L 的第 i 个数据元素 n -表示线性表 L 的表长（n=0） n=0 时的线性表称为空表 ei-1 称为 ei 的前驱，ei+1 称为 ei
5、的后继 线性表的基本操作： （1）初始化（置空表）可由构造函数实现 （2）求表长（ Length ） （3）查找或定位（ Find ） （4）插入（ Insert ） （5）删除（ Remove ） （6）排序（ Sort ） （7）判空（ IsEmpty）,2019/1/17,9,2.2 线性表的顺序存储结构,要实现在计算机内表示一个数据结构，要解决两种信息的存贮问题： 数据元素本身的存贮 数据元素之间关系的存贮 定义：利用内存物理结构上的邻接特点，实现线性表 的“一个跟着一个”这一序列关系的存贮方式， 称为线性表的顺序存贮结构，其上的线性表称 为顺序表。 顺序表的类定义：利用数组作为顺序表
6、的存储结构， 它被封装在类的私有域中,2019/1/17,10,template class SeqList Public: SeqList(int MaxSize=defaultSize); SeqList( ) delete data; int Length( ) const return last+1; int Find(Type / last 为表中最后元素的下标，last=-1 时表示空表,2019/1/17,11,上述顺序表定义中的数据成员 Maxsize 是为判断顺序 表是否为满而设，last 是为便于判断顺序表是否为空、求 表长、置空表而设： last=Maxsize 1表示顺
7、序表已满，此时再进行插入操作会导致上溢错误； last=-1 表示顺序表为空表，此时再进行删除操作会导致下溢错误； last+1 代表顺序表的表长； 将 last 赋值为 1 可实现置空表操作。 由上可知：合理地设置数据成员可大大简化算法的设计及提高算法的效率。顺序表不仅仅包含存放其数据元素的数组，它还应包括一些有用的数据成员，以及相应的操作，它们是一个整体：,2019/1/17,12,顺序表之整体概念：,data,0,1,last,Maxsize,last,数组下标,数组,变量,操作算法,Maxsize-1,初始化操作,插入操作,删除操作,查找操作,排序操作,. . . . . .,. .
8、.,. . .,. . .,2019/1/17,13,顺序表的基本操作（算法）,（1）顺序表初始化操作算法 template Seqlist:Seqlist(int sz) /构造函数，通过指定参数 sz 定义数组的长度，并将 last 置为 1 /即置空表 if(sz0) Maxsize=sz; last=-1; / last+1=0 , 表明表中无元素，空表 data=new TypeMaxsize; ,2019/1/17,14,（2）顺序表查找操作,template int Seqlist:Find(Type ,2019/1/17,15,（3）顺序表插入操作,为了把新元素 x 插入到 i
9、 处，必须把从 i 到 last 的所有元素成块向后移动一个元素位置，以空出第 i 个位置供 x 插入：,x,2,3,1,先移动后面元素,0,i-1,i,i+1,last,. . .,. . .,. . .,. . .,. . .,. . .,2019/1/17,16,template int Seqlist:Insert(Type ,2019/1/17,17,（4）顺序表删除操作,为了删除第 i 个元素，必须把从 i1 到 last 的所有元素向前移动一个元素位置，把第 i 个元素覆盖掉：,1,2,. . .,0,i-1,i,i+1,last-1,last,1,. . .,. . .,. .
10、 .,. . .,. . .,2019/1/17,18,template int Seqlist:Remove(Type ,2019/1/17,19,顺序存储结构的优缺点,优点： （1）算法简单、可读性好、开发代价低 缺点： （1）插入、删除操作时需要移动大量元素， 效率较低； （2）最大表长难以估计，太大了浪费空间， 太小了容易溢出。,2019/1/17,20,顺序表应用举例,当将两个顺序表作集合考虑时的“并”与“交”操作算法 template void Union(Seqlist ,2019/1/17,21,template void Intersection( Seqlist ,2019
11、/1/17,22,多项式及其运算,A(x)=a0x + a1x +a2x +an-1x + anx = B(x)=b0x + b1x +b2x +bn-1x +bnx = A(x)+B(x)= 实际应用中，上述一元多项式中的很多系数有可能为零， 即为稀疏多项式，如下式所示：, aix,i=0,n,i,0,1,2,n-1,n,0,1,2,n-1,n, bix,i,i=0, (ai+bi)x,n,i=0,i,P (x)=1.2+51.3x +3.7x,50,50,101,P(x)=ci x,i=0,n,ei,c0=1.2 e0=0,c1=51.3 e1=50,c2=3.7 e2=101,2019/
12、1/17,23,多项式的表示,对于稀疏多项式，采用二元组表示法可以大大节省存储 空间： （1）将稀疏多项式的每一项用二元组表示 客体的表示方法 （2）用一顺序表（一维数组）来存放上述的二元组 数据的组织方法,c0,c1,ci,cn,e0,e1,ei,en,系数,指数,. . .,. . .,. . .,. .,. . .,2019/1/17,24,多项式二元组的类定义客体的表示方法,class Polynomial; / 多项式类的前视声明 class term / 多项式中项（二元组）的类定义 friend Polynomial; / 定义 Polynomial 类为 term 类的友元类
13、private : float coef; / 系数 int exp; / 指数 ,2019/1/17,25,多项式的类定义数据的表示方法,class Polynomial public : . . . / 成员函数声明（构造、释构、相加等函数） private : int MaxTerms ; /共享空间（顺序表）的最大项数 static term termArrayMaxTerms; /存放二元组的数组，存放多个多项式的共享空间 static int free ; / 共享空间中自由空间之起始下标 int start , finish ; / 多项式在共享空间中的首、尾下标 ,2019/1
14、/17,26,多项式的相加,A(x)=aix B(x)=bjx C(x)=A(x)+B(x),n,m,i=0,j=0,e i,e j,A . Start A . finish,B . Start B . finish,free MaxTerm-1,2019/1/17,27,多项式AB算法思路：,（1）保留A、B两个多项式，将AB放人C中； （2）开始时 C.start = free； （3）设置两个指针 a 和 b 分别作为 A 与 B 的检测指针，开始时 分别指向 A 与 B 的首项，即： a = A . start ; b = B . start； （4）当两个指针都未超出相应多项式的最末
15、位置时，比较它们所 指示的对应项的指数： 若指数相等，则对应项系数相加，若相加结果不为零，则在 C 中加入一个新项 若指数不等，则把指数小者拷贝到 C 中 （5）当两个指针中有一个超出了相应多项式的最末位置，则将另 一个多项式的剩余部分拷贝到 C 中,2019/1/17,28,Polynomial Polynomial : Add ( Polynomial B ) Polynomial C; int a = start; int b =B.start; C.start = free; float c; while ( a : NewTerm( termArrayb.coef , termArrayb.exp); b+ ; break ; case : NewTerm( termArraya.coef , termArraya.exp); a+ ; for ( ; a = finish ; a+ ) NewTerm( termArraya.coef , termArraya.exp);
