《数据结构讲义Part》PPT课件.ppt

1、2020/9/13,1,数据结构及其应用,（用面向对象方法与C描述）,2020/9/13,2,第一章 概述,研究对象：信息的表示方法、数据的组织方法、操作算法设计 意义地位：数据结构算法程序 程序设计的基础 系统软件的核心 发展过程：数值计算 非数值计算 建立数学模型 客体及其关系的表示 设计数值计算方法 数据的组织 操作算法的设计 非数值计算应用的发展，促进了数据结构 的研究和发展以及其体系的完善。,2020/9/13,3,基本术语,数 据：描述客观事物的且能由计算机处理的数 值、字符等符号 数据元素：数据的基本单位，在计算机程序中通常 作为一个整体进行考虑和处理（记录、 结点、表目、元素）

2、 数 据 项：数据元素的某一属性。数据元素可以由 若干数据项组成，数据项可以由若干 更小的款项（组合项、原子项）组成。 数据项又称域、字段 关 键 码：能起唯一标识（数据元素）作用的数据项 数据结构：一组同类的数据元素、其间的关系及其上的 一组操作所构成的整体，称为一个数据结构,2020/9/13,4,数据结构的描述方式,逻辑结构：是对数据元素之间逻辑关系（抛开具体的关系含义以及存储方式等）的描述，它可以用一个数据元素的集合和定义在此集合上的几个关系来表示。通常可用图形表示，圆圈表示数据元素，箭头表示关系： 物理结构：数据结构在计算机中的具体表示和实现， 又称存储结构,E i,E i+1,数据

3、元素,数据元素,关系,2020/9/13,5,数据结构的分类,按逻辑结构分类： 纯集合型结构:数据元素之间除了“同属于一个集合”这一 关系外，别无其他关系 线性结构：数据元素之间存在“一个跟着一个”的序列关系 树型结构：数据元素之间存在“每个元素只能跟着一个元素 但可以有多个元素跟着它”的层次关系 图状结构：任意两个数据元素之间都可能存在关系 按存储结构分类： 顺序存储结构 链式存储结构 索引存贮结构,2020/9/13,6,基本操作：任一数据结构均有一组相应的基本操作， 有时操作不同，用途迥异（如栈和队列）,常用的基本操作有插入、 删除、查找、 更新、排序等 算 法：算法是为了解决给定的问题

4、而规定的一个 有限长的操作步骤序列，则重于解决问题 的方法和步骤。当算法由计算机语言表示 时称为程序（代码） 算法设计目标：可维护性 可靠性（正确性、健壮行） 可读性 高效率（时间、空间）,2020/9/13,7,第二章 线性表,2。1 线性表的逻辑结构 定义：由相同种类的数据元素组成的一个有穷序列称为一个线性表。“一个跟着一个” 符号表示法：L（e1,e2,en） 图形表示法：,e2,en,e1,2020/9/13,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）,2020/9/13,9,2.2 线性表的顺序存储结构,要实现在计算机内表示一个数据结构，要解决两种信息的存贮问题： 数据元素本身的存贮 数据元素之间关系的存贮 定义：利用内存物理结构上的邻接特点，实现线性表 的“一个跟着一个”这一序列关系的存贮方式， 称为线性表的顺序存贮结构，其上的线性表称 为顺序表。 顺序表的类定义：利用数组作为顺序表

6、的存储结构， 它被封装在类的私有域中,2020/9/13,10,template class SeqList Public: SeqList(int MaxSize=defaultSize); SeqList( ) delete data; int Length( ) const return last+1; int Find(Type / last 为表中最后元素的下标，last=-1 时表示空表,2020/9/13,11,上述顺序表定义中的数据成员 Maxsize 是为判断顺序 表是否为满而设，last 是为便于判断顺序表是否为空、求 表长、置空表而设： last=Maxsize 1表示顺

7、序表已满，此时再进行插入操作会导致上溢错误； last=-1 表示顺序表为空表，此时再进行删除操作会导致下溢错误； last+1 代表顺序表的表长； 将 last 赋值为 1 可实现置空表操作。 由上可知：合理地设置数据成员可大大简化算法的设计及提高算法的效率。顺序表不仅仅包含存放其数据元素的数组，它还应包括一些有用的数据成员，以及相应的操作，它们是一个整体：,2020/9/13,12,顺序表之整体概念：,data,0,1,last,Maxsize,last,数组下标,数组,变量,操作算法,Maxsize-1,初始化操作,插入操作,删除操作,查找操作,排序操作,. . . . . .,. .

8、.,. . .,. . .,2020/9/13,13,顺序表的基本操作（算法）,（1）顺序表初始化操作算法 template Seqlist:Seqlist(int sz) /构造函数，通过指定参数 sz 定义数组的长度，并将 last 置为 1 /即置空表 if(sz0) Maxsize=sz; last=-1; / last+1=0 , 表明表中无元素，空表 data=new TypeMaxsize; ,2020/9/13,14,（2）顺序表查找操作,template int Seqlist:Find(Type ,2020/9/13,15,（3）顺序表插入操作,为了把新元素 x 插入到 i

9、 处，必须把从 i 到 last 的所有元素成块向后移动一个元素位置，以空出第 i 个位置供 x 插入：,x,2,3,1,先移动后面元素,0,i-1,i,i+1,last,. . .,. . .,. . .,. . .,. . .,. . .,2020/9/13,16,template int Seqlist:Insert(Type ,2020/9/13,17,（4）顺序表删除操作,为了删除第 i 个元素，必须把从 i1 到 last 的所有元素向前移动一个元素位置，把第 i 个元素覆盖掉：,1,2,. . .,0,i-1,i,i+1,last-1,last,1,. . .,. . .,. .

10、 .,. . .,. . .,2020/9/13,18,template int Seqlist:Remove(Type ,2020/9/13,19,顺序存储结构的优缺点,优点： （1）算法简单、可读性好、开发代价低 缺点： （1）插入、删除操作时需要移动大量元素， 效率较低； （2）最大表长难以估计，太大了浪费空间， 太小了容易溢出。,2020/9/13,20,顺序表应用举例,当将两个顺序表作集合考虑时的“并”与“交”操作算法 template void Union(Seqlist ,2020/9/13,21,template void Intersection( Seqlist ,2020

11、/9/13,22,多项式及其运算,A(x)=a0 x + a1x +a2x +an-1x + anx = B(x)=b0 x + 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,202

12、0/9/13,23,多项式的表示,对于稀疏多项式，采用二元组表示法可以大大节省存储 空间： （1）将稀疏多项式的每一项用二元组表示 客体的表示方法 （2）用一顺序表（一维数组）来存放上述的二元组 数据的组织方法,c0,c1,ci,cn,e0,e1,ei,en,系数,指数,. . .,. . .,. . .,. .,. . .,2020/9/13,24,多项式二元组的类定义客体的表示方法,class Polynomial; / 多项式类的前视声明 class term / 多项式中项（二元组）的类定义 friend Polynomial; / 定义 Polynomial 类为 term 类的友元

13、类 private : float coef; / 系数 int exp; / 指数 ,2020/9/13,25,多项式的类定义数据的表示方法,class Polynomial public : . . . / 成员函数声明（构造、释构、相加等函数） private : int MaxTerms ; /共享空间（顺序表）的最大项数 static term termArrayMaxTerms; /存放二元组的数组，存放多个多项式的共享空间 static int free ; / 共享空间中自由空间之起始下标 int start , finish ; / 多项式在共享空间中的首、尾下标 ,2020

14、/9/13,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,2020/9/13,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 中,2020/9/13,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 , termA

16、rrayb.exp); b+ ; break ; case : NewTerm( termArraya.coef , termArraya.exp); a+ ; for ( ; a = finish ; a+ ) NewTerm( termArraya.coef , termArraya.exp); for ( ; b = B.finish ; b+ ) NewTerm( termArrayb.coef , termArrayb.exp); C.finish=free-1; return C ; ,2020/9/13,29,void Polynomial : NewTerm( float c

17、, int e ) / 把一个新的项（二元组 ）追加到多项式 C(x) 中 if ( free = MaxTerms ) cout “Too many terms in polynomials” endl ; return ; termArray free . coef = c ; termArray free . exp = e ; free + ; ,2020/9/13,30,作业：,定义多项式类的求表长、查找、插入、删除、判空 表判满表、读取（第 i 个元素）等成员函数，并用这些 函数实现前述的两个多项式的相加操作。 提示： （1）定义查找指数相等的元素的成员函数 （2）仿照前述的顺序表

18、合并操作算法，先从多项式 B 中 读取一元素，在 A 中查找有无指数相等元素： 若无，则有序插入 A 中； 若有，则系数相加： 若和为零，则从 A 中删除相应元素； 否则用新系数构造新元素，并插入 A 中相应位置,2020/9/13,31,稀疏矩阵（Sparse Matrix）数值计算中的顺序表设计,000220015 011000170 A=000-6000 00000390 91000000 00280000 矩阵 A 是一个 6 行 7 列的稀疏矩阵，只有 8 个非零元素，其他均为零。因此用二维数组来存储稀疏矩阵的空间利用率较低，必须考虑对稀疏矩阵的压缩存储表示。,2020/9/13,3

19、2,稀疏矩阵的三元组表示法： （1）将稀疏矩阵的非零元素用三元组 表示（ 表示稀疏矩阵的 第 row 行、第 column 列的值为 value） 客体的表示方法 （2）用一顺序表（一维数组）来存放上述三元组 （每一个三元组即为顺序表的一个数据元素） 并按行优先顺序存放 数据的组织方法 template class Trituple private : int row, col; Type value; ,2020/9/13,33,矩阵A的三元组表示：,表下标行(row) 列(col) 值(value) 0 0322 1 0615 2 1111 3 1517 4 23-6 5 3539 6 4

20、091 7 5228,2020/9/13,34,稀疏矩阵的类声明：,template class SparseMatrix public: SparseMatrix(int MaxTerms=defaultSize); SparseMatrix() delete smArray; SparseMatrix Compression(smData); SparseMatrix Transpose(); SparseMatrix Add(SparseMatrix b); SparseMatrix Multiply(SparseMatrix b); private: int Rows, Cols, T

21、erms,MaxTerms; Trituple smArrayMaxTerms; ,2020/9/13,35,说明： （1）压缩前的稀疏矩阵为 Rows 行, Cols 列的矩阵 smData ，压缩后的稀疏矩阵存放在一维数组 smArray 中，其中的元素为 Trituple 类型的对象。 声明中的 Terms 对应于顺序表定义中的 last， MaxTerms 对应于顺序表定义中的 Maxsize， smArray 对应于顺序表定义中的 data （2）为稀疏矩阵声明了四种操作： 压缩（Compression） 转置（Transpose） 相加（Add） 相乘（Multiply） 根据实际

22、需要还可以声明其他操作。 （3）数值计算与非数值计算的数据结构中所定义的基 本操作有很大的不同,2020/9/13,36,稀疏矩阵的转置操作,快速转置算法思路： （1）引入两个辅助数组 rowSize 和 rowStart rowSize i 表示稀疏矩阵第 i 列的非零元素个数 rowStart i 表示稀疏矩阵第 i 列的第一个（行号最小） 非零元素在转置矩阵的三元组表中的位置。 显然应有： rowStart i + rowSize i = rowStart i+1 ,. . .,. . .,. . .,共有 rowSize i 个元素,2020/9/13,37,上述公式表示，若已知稀疏矩

23、阵第 i 列的第一个非零元素在转置 矩阵的三元组表中的位置 rowStart i , 以及稀疏矩阵第 i 列的非零 元素个数 rowSize i , 就可以算出第 i+1 列非零元素在转置矩阵的 三元组表中的位置 rowStart i+1 另外，根据转置矩阵的定义可知： rowStart 0 = 0 因此： rowStart 1 = rowSize 0 + rowStart 0 = rowSize 0 rowStart 2 = rowSize 1 + rowStart 1 . . . . . . 因此，只要预先统计得到 rowSize i ( i = 0 , 1 , 2 , . . .) 就可

24、以得到第 i + 1 列非零元素在转置矩阵的三元组表中的位置,2020/9/13,38,template SparseMatrix SparseMatrix: FastTranspos( )/ int *rowSize = new intCols; int *rowStart = new intCols; SparseMatrix b; b.Rows = Cols; b.Cols = Rows; b.Terms = Terms; if (Terms 0 ) for (int i = 0; iCols; i +) rowSizei = 0; for (i=0;iTerms;i+) rowSize

25、smArrayi.col+; rowStart0=0; for (i=1;iCols;i+) rowStarti=rowStarti-1+rowSizei-1; for (i=0;iTerms;i+) int j=rowStartsmArrayi.col; b.smArrayj.row=smArrayi.col; b.smArrayj.col=smArrayi.row; b.smArrayj.value=smArrayi.value; rowStartsmArrayi.col+; delete rowSize; delete rowStart; return b; ,2020/9/13,39,

26、2。5 字符串,定义： 字符串（简称为串） 是 n ( n = 0 ) 个字符的有限序列 通常可记为： S = a0 a1 a2 an-1 其中： 串名S 串值引号中的内容 n串长，即串中的字符个数（不包括串结束符 0 ） 空串 n = 0 的串（但包含串结束符） 空白串仅由若干个空格字符组成的串，其长度不为零 子串从非空串中连续取出的若干个字符组成的串 子串的位置子串的第0个字符在原串中的位置 可以认为：串是限制数据元素为字符的顺序表,2020/9/13,40,2.5.1 字符串抽象数据类型和类定义,class String public: String(const String ,2020

27、/9/13,41,有了上述的串类定义，就可以进行下列操作：,String s1; String s2 ( “ Hello World ” ); s1 = s2; String s3 ( “ ; nice to here ! ” ); s1 + = s3; int len=s1.length(); String s4; s4=s1(6,5); If (s1=s2) If (s1!=s2) If (! s1) Char c=s16; s16=w;,2020/9/13,42,文本编辑,计算机应用中要涉及大量的文本文件，文本文件由大量的串 （行）组成，在某些文本文件（如源程序）中，串（行）长差异 很大

28、，若每行都用等长的串来存贮，则会浪费存贮空间 解决的办法之一是建立一个很大的字符数组作为所有串的共享空间串值共享空间，再为每个串建立一个描述子，用于描述该串的长度以及该串在串值共享空间中的位置等信息，并将这些描述子存入一顺序表中，参见下图：,2020/9/13,43,行表(linelist) 串值共享空间（space） MaxSize-1,.,.,.,.,free,行号,0 1 2 3,行长 位置,行2,行3,行0,行1,. . .,. . . .,. . . .,自由空间起始地址,0,串值共享空间String（串） 行表Seqlist（顺序表） 设计行内字符插入、删除操作算法 设计整行插入、

29、删除操作算法,2020/9/13,44,第三章 链表,顺序表有下列缺点： （1）插入、删除操作时需要移动大量元素， 效率较低； （2）最大表长难以估计，太大了浪费空间， 太小了容易溢出。 因此，在插入和删除操作是经常性操作的应用场合 选用顺序存储结构不太合适，此时可以选用链式存储结 构。 定义：用指针来表示数据元素之间关系的存储结构 称之为链式存储结构。,2020/9/13,45,定义：用由指针连接起来的一串结点来存储一个线性表 的存储结构称为线性链式存储结构，简称链表。 当每一结点中只有一个指针，并用来表示一个数 据元素到其后继元素之间的接续关系，则称这种 存储结构为单链表。 注：此处的结点

30、是指通过指针型变量动态索取到的存储空间,. . .,first,first头指针 指针域 (link) last last 尾指针 数据元素域 (data) 空指针,结点1,头结点,结点0,结点n-1,e0,e1,en-1,2020/9/13,46,上述的单链表表头设置了一头结点，头结点的数据 域中可以为空，或者存放一些辅助数据。 设置头结点的目的是为了简化对空表的特殊处理， 使得算法更简单、更有效。 对于带头结点的单链表，可以很容易地表示空链表： 头指针 头结点,first,last,尾指针,2020/9/13,47,用模板定义的单链表类,template class List; /单链表类

31、的前视声明 template class ListNode /链表结点类的定义 friend class List ; /将 List 类定义为 ListNode 类的友元 public: ListNode( ); ListNode(const Type ,data,link,2020/9/13,48,template class List/单链表类的定义 public: List( ) last=first=new ListNode (value,NULL); /构造函数，建立一个空链表 List( ); void MakeEmpty( );/删除所有元素结点，将链表置为空链表 int Le

32、ngth( ) const; /求单链表表长 ListNode *Find(Type value); /查找值为 value 的结点 ListNode *Find(int i); /查找结点 i , 返回结点 i 的指针 int Insert(Type value,int i); /将值为 value 的新结点插入结点 i 之前 Type *Remove(int i);/删除结点 i Type Get(int i);/读取结点 i 的值 private: ListNode *first, *last;/头指针，尾指针 ,2020/9/13,49,ListNode类（链表结点类）的成员函数的实现

33、,template void ListNode: ListNode( ):link(NULL) template void ListNode: ListNode(const Type ,2020/9/13,50,InsertAfter( ) 函数 template void ListNode: InsertAfter(ListNode *p) 将 p 所指的结点（*p）链接成为当前结点（*this）的后继结点 p-link=link; /(1) link=p; /(2) ,this,data,link,data,link,data,link,p,p-link=link,link=p,(1),(

34、2),当前结点,2020/9/13,51,RemoveAfter( ),data,link,data,link,data,link,当前结点 要删除的结点 template ListNode *ListNode: RemoveAfter()/删除当前结点 ( *this ) 的后继结点,并返回该结点的指针 ListNode *tempptr=link; /(1) if (link=NULL) return NULL; link=tempptr-link; /(2) return tempptr; ：,(1)tempptr=link,(2) link=tempptr-link,this,2020

35、/9/13,52,List类（链表类）的成员函数的实现,template void List:MakeEmpty( ) / 将当前链表置为空表 ListNode *q ; while (first -link != NULL) / 循环删除头结点的后继结点，直到无后继结点为止 q=first -link ; first -link=q -link ; delete q ; last=first;/ 最后让 last 指向头结点，完成置空表操作 ,first,(1) q=first-link,(2) first-link=q-link,(最后) last,头结点,2020/9/13,53,tem

36、plate int List:Insert(Type value,int i); / 将值为 value 的新数据元素插入到链表中结点 i 之前 ListNode *p = Find(i-1);/ 查找结点 i-1 if (p=NULL) return 0;/ 结点 i-1 不存在，插入失败 ListNode *newnode=GetNode(value,p-link);/ 创建新结点 / 并使新结点指向结点 i (1) if (p-link=NULL) last=newnode;/ 若结点 i 不存在，则新结点将 / 是表尾结点 p-link=newnode;/ 让结点 i-1 指向新结点，

37、实现插入 (2) return 1; ,结点 i-1,结点 i,新结点,p,newnode,(1),(2),2020/9/13,54,template Type *List : Remove( int i ) / 删除结点 i ,若成功，则返回该结点的数据元素（地址）， / 否则返回NULL ListNode *p= Find(i-1) , *q ; / 查找结点 i-1 if ( p=NULL | p-link=NULL) return NULL;/ 若结点 i-1 或者 / 结点 i 不存在，则返回 NULL , 删除失败 q=p-link; / (1) p-link=q-link;/ (

38、2) Type value=q-data; if (q=last) last=p; delete q; return ,结点 i-1 结点 i 结点 i+1,p q,(1),(2),2020/9/13,55,template ListNode *List:Find( int i ) / 查找结点 i , 若找到，则返回该结点的指针，否则返回NULL if ( i *p=first-link;/ p 指向结点0 int j=0; while(p!= NULL ,2020/9/13,56,3.1.6 单链表的游标(Iterator)类,在实际应用中经常要对单链表进行打印、统计、检 索等需要向后搜索

39、整个链表的操作，因此设计具有光标 功能的，能够记住当前位置并能得到其后继结点的游标 类是有意义的。 单链表的位置概念：current 是结点 i+1的位置 有了单链表结点 i+1 的位置 current ，删除结点 i+1 或在 结点 i+1 前插入新结点就会简单得多，无需查找过程。,current,结点 i,结点 i+1,2020/9/13,57,单链表游标类声明,Template class ListIterator public: ListIterator(const List /游标（指针） ,2020/9/13,58,单链表游标类成员函数的定义,template Boolean Li

40、stIterator:NotNull( ) / 检查游标结点（ current 所指的结点）是否为不空（注： /此处结点不空是指该结点的指针不空）。若不空，则返回真， / 否则返回假 if ( current != NULL ) return True; else return False; template Boolean ListIterator:NextNotNull( ) / 检查游标结点（游标所指的结点）的后继结点是否为不空。 / 若不空，则返回真；否则返回假 if ( current != NULL ,2020/9/13,59,template ListNode * ListIte

41、rator:First( ) / 使游标指向头结点 if ( list.first-link != NULL ）current = list.first; / 若头结点的指针 /域不空，即链表为非空表,则使游标指向头结点 else current = NULL; / 否则置空游标 return current; template ListNode * ListIterator:Next( ) / 使游标指向后继结点 if ( current != NULL ,2020/9/13,60,游标类应用举例： int sum ( const List 课堂作业： 使用游标类求 int 型单链表的最大结

42、点。若单链表为空则返回NULL， 否则返回最大结点的位置。,2020/9/13,61,3.2 循环链表（Circular List）,e0,e1,en-1,循环链表的定义： （ P82P83） 循环链表与单链表不同的是链表中表尾结点的 link 域不是NULL，而 是链表头结点的指针（链表指针）,first,last,表头结点,first,last,空表,2020/9/13,62,循环链表（带头结点）的类定义：,enum Boolean False,True template class CircList;/循环链表类的前视声明 template class CircListNode /循环链表结点的类定义 public: CircListNode (Type d=0, CircListNode * next=NULL): data ( d ), link ( next ) /构造函数，创建一个循环 /链表结点，并初始化数据域为 d , 指针域为 NULL private: Type data; CircListNode * link; ,data,link,2020/9/13,63,template class CircList public: CircList ( Type value ); CircList ( ); int L