数据结构：面向对象语言描述Appt.ppt

1,版权所有, 1997 (c) Dale Carnegie & Associates, Inc.,数 据 结 构 面 向 对 象 语 言 描 述,朱振元,2,课程的形成背景,应用领域： 科学计算,管理、人工智能、文字处理,加工对象： 数 值,字符、表格、图像或其他具有一定结构的数据,3,实例,1.员工信息检索系统（图1.1） 2.八皇后问题（图1.2） 3.交通咨询系统（图1.3）,4,研究对象,主要是研究： 非数值计算的程序设计问题中所出现的 计算机操作对象以及它们之间的关系和操作,5,学习的目的,了解计算机处理对象的特性，将现实世界中实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。 与此同时，通过算法训练提高计算机思维的能力，通过程序设计的技能训练来促进综合应用能力和专业素质的提高。,6,课程的性质,综合性的专业基础课程 是计算机专业课程体系中的核心课程,7,基本术语,数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。例如： 数值计算中的整数和实数， 编译程序或文本编辑程序中的字符串。 多媒体技术中所涉及的视频和音频信号，经采集转换后都能形成被计算机所接受的数据。,8,基本术语,数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录。 数据元素类（Data Element Class）是具有相同性质的数据元素的集合 。例如： 整数数据对象N0，1-1,2,-2 字母数据对象Ca ,b ,c,9,数据结构的概念,数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。 四类基本的结构： （图1.4） （1）集合 数据元素间的关系是属于同一个集合 。 （2）线性结构 数据元素之间存在一对一的关系。 （3）树形结构 数据元素之间存在一对多的关系。 （4）图状结构 数据元素之间存在多对多的关系，图状结构也称网状结构。,10,数据的逻辑结构,数据的逻辑结构可以看作是从具体问题中抽象出来的数学模型，它与数据的存储无关,逻辑结构,线性： 线性表、栈、队列、数组、串,非线性： 广义表、树、图,11,数据的物理结构,数据结构在计算机中的表示（又称映象）称为数据的物理结构，或称存储结构。 它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。,物理结构,顺序 使用一组连续的存储单元,非顺序,链式,索引存储、散列存储,12,数据结构形式定义,Data structrue=(D,R) 其中，D是数据元素的有限集，R是D上关系的有限集 按员工的编号来建立元素间的线性关系 Linear-List =(D,R) 其中： D=01,02,03,04,05,06,07,08,09,10 R,13,按行政分组来建立树形的数据结构 Tree =(D,R)其中： D=01,02,03,04,05,06,07,08,09,10 R, 按员工的爱好来建立图状的数据结构 Graph =(D,R) 其中： D=01,02,03,04,05,06,07,08,09,10, 网，羽，乒 R,14,数据类型的概念,数据类型（Data Type）是一个值的集合和定义在这个值集上的一组操作的总称。 例如：整数类型， 其取值的范围为-maxint,maxint上的整数 定义在其上的一组操作为加、减、乘、除及取模等。,15,抽象数据类型,抽象数据类型（Abstruct Data Type 简称 ADT） 是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。,16,抽象数据类型的定义,抽象数据类型的定义可以由 （元素、关系、操作）三种要素来进行定义 （由于 数据类型数据结构操作， 而数据结构数据元素元素间的关系） 例如栈的ADT定义： 元素 属于同一个数据元素类。 关系 数据元素间呈线性关系。 操作 PUSH（S，X）进栈操作、POP（S）出栈操作等等,17,实现方法的比较,面向过程的方法 在数据与操作二者之间并没有建立必然的联系 顺序执行 面向对象的方法 相关的数据及操作被统一在一个整体对象之中 程序简洁有利于数据保护和代码重用,18,栈演示程序,面向过程的方法 Node *top; char ch; void push(char ch); char pop( ); top=NULL; ch=a; while (ch!= E ) 输入一个字符存入ch; 对ch进行判别并进行相应的处理； 输出栈中的当前元素 ;,面向对象的方法 class LinkStack private: Node *top; public: LinkStack (); void init(); void prnt(); char pop(); void push (char el); ; LinkStack lz1; lz1.init( ); lz1.push(el); lz1.prnt( );,19,面向对象的概念,对象 是指应用问题中所出现的各种实体，它是由一组属性值和在这组值上的一组操作（方法）构成，其中，属性值确定了对象的状态。例如，在程序中常用的字符串、线性表、栈、队列等或在WINDOWS应用程序中常见的窗体、组合框、编辑框、无线按钮等。对于一个编辑框对象，由它的TOP、LEFT属性确定了它在窗体中的位置，由它的TEXT属性确定了显示在该编辑框中的字符串，可以使用GetTextLen方法来求得该字符串的长度，也可用Clear方法来清除这个字符串 类和实例 对象在语言中是用类来定义的，类中定义了与某一种对象相关联的一组数据以及施与该数据中的一组基本操作。在面向对象的程序设计中，如果某一个变量被定义成属于某一个类，那么该变量即可成为这种对象中的一个实例。 例如，在一个窗体中可以设置多个编辑框，尽管其位置及外观都不相同，但它们都是属于编辑框组件（类）所派生的对象实体。,20,面向对象的概念,数据封装（信息隐蔽）是指在面向对象的程序设计中，对象的实现过程（包括数据的存储方式、操作的执行过程）作为私有部分被封装在类结构中，使用者不能看到，也不能直接操作该类型所存储的数据，而只能根据对象提供的外部接口来访问或操作这些数据 继承与派生 继承机制是在面向对象方法中最有特色的方面。在面向对象的方法中，类与类之间存在着继承关系，这种继承关系与客观世界中存在的一般与特殊的关系相类似。例如：在Windows的界面设计中，可将窗体分为一般窗体和对话框，而对话框又可分为打开对话框、确认对话框等，这些窗体都有窗体的共同特征，但不同的窗体又有自身的不同特征。我们可以将窗体定义成基类，建立它的派生类，如对话框、打开对话框等。,21,互动环节:面向对象程序设计,使用面向对象的方法求矩形的面积与周长。 1 将矩形定义成类Rect : 数据成员 w、h分别表示矩形的宽与高。 构造函数 Rect(int w0,int h0) 函数成员getarea()求矩形的面积 getperi() 求矩形的周长 2 创建一个矩形rect1其宽和高分别为8、6 然后显示该矩形的面积与周长,22,算法及算法分析,算法的概念： 算法是对特定问题求解步骤的一种描述 算法的特性： 有穷性、确定性 、可行性、输入、输出 算法的描述 自然语言。 使用流程图、NS图等用于算法描述的工具， 直接用某种高级程序设计语言来描述算法。 使用伪码语言 算法设计的要求 正确 、可读、 健壮、 高效,23,算法分析：时间的复杂性,表示形式： 一个算法是由控制结构和原操作构成的。从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间量度。一般情况下，算法中原操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作： T(n) = o( f (n) ) 该式表示算法中原操作的执行次数与问题规模n的某个函数同阶。,24,常数阶、线性阶、平方阶 o(1) o(n) o(n2),x= x+1; for (i=1;i=n;i+) x= x+1; for (i=1;i=n;i+) for (j=1;j=n;j+) x= x+1; for(i=1;i=n;i+) for (j=1;j=n;j+) s=0; for (k=1;k=n;k+) s=s+aik*bkj; cij=s; ;,25,n阶矩阵相乘运算算法的时间复杂度,for(i=1;i=n;i+) for (j=1;j=n;j+) s=0; /基本语句(1) for (k=1;k=n;k+) s=s+aik*bkj; /基本语句(2) cij=s; /基本语句(3) ; 在通常情况下算法的时间复杂度是指基本语句重复执行的次数及频度。在上述算法中主要语句的频度分别是： 基本语句(1)n2 ，基本语句(2)n3 ，基本语句(3)n2 。该算法的时间复杂度所有语句的频度之和T(n) = n2+ n3+ n2 = o( n3 )。因此该算法时间复杂度为o(n3),称之为立方阶。,26,对数阶时间复杂度,i=1; /语句(1) while(i=n) i=i*2; /语句(2) 其中语句(1)的频度是1，设语句(2)的频度是f(n)，则有 2 f(n)=n，即： f(n)=log2n，取最大值f(n)=log2n，因此该算法时间复杂度为: T(n) =1+ log2n = o(log2n),27,互动环节：算法及其算法分析,试写一个算法，实现将数组an中的n个整数循环后移一个位置，并给出它的时间复杂度和辅助空间的大小。,28,互动环节：算法及其算法分析,int i,temp; temp=an-1; for(i=n-1;i=1;i-) ai=ai-1; a0=temp; 时间复杂度 T(n) = 1+ (n-1)+1 = o( n ) 线性阶 空间复杂度 S(n) = 2 = o( 1 ) 常数阶,29,算法分析：空间的复杂性,表示形式： S(n) = o( f (n) ) 实例：将存放在一维数组a中的n个整数反向存放，即将a1存放在原an存放的位置中，将a2存放在原an1存放的位置中，依次类推，直至将an存放在原a1存放的位置中。 1. 使用一组工作单元bn ： for (i=1; i=n; i+ ) bn-i+1= ai; for (i=1; i=n; i+ ) ai= bi; 2. 只使用工作单元i与w： for (i=1; i=n/2; i+ ) w= ai; ai= bn-i+1; bn-i+1= w; ;,30,演示,结束,31,版权所有, 1997 (c) Dale Carnegie & Associates, Inc.,线 性 表,32,线性表的初步认识,线性表是相同类型数据元素的有限序列 数据元素可以是字符、整数、记录等。例如： (a,b,c,z); (6,17,50,28,90); 特点：数据元素之间存在前后相邻的关系,33,一般表示及相应的术语,L=(a1,a2,ai-1,ai,ai+1,An) （直接）前驱 （直接）后继 最先元素 最后元素 位序 长度 空表,34,线性表的特点,线性表是由具有相同特性的n个元素所组成的有限序列 相邻元素之间存在着序偶关系。 对线性表的数据元素不仅可以访问，还可以对线性表进行插入和删除等,35,线性表抽象数据类型,数据元素：ai同属于一个数据元素类，i=1,2,n n0。 结构关系：对所有的数据元素ai（i=1,2,n1）存在次序关系, a1无前驱，an无后继。基本操作：对线性表可执行以下的基本操作,Initiate(L) 构造一个空的线性表L。 Length(L) 求长度。 Empty(L) 判空表。 Full(L) 判表满。 Clear(L) 清空操作。 Get(L,i) 取元素。 Locate(L,x) 定位操作。 Prior(L,elem) 求前驱。 Next(L,elem) 求后继。 Insert(L,i,b) 插入操作（前插）。 Delete(L,i) 删除操作。,36,线性表抽象类,template class List public: virtual void init()=0; /初始化 virtual int leng()=0; /求长度 virtual Telem gete(int i)=0; /返回第i个元素 virtual int loct (Telem,37,线性表的存储方式,线性表在计算机中的存储方式（又称映象）可分为顺序存储方式和链式存储方式二种。,线性表的存储方式,动态链表,顺序 顺序表,链式 线性链表,静态链表,38,顺序表类 采用顺序的存储方式存储的线性表称为顺序表, 由此建立一个实现类,实现线性表抽象类中定义的各接口函数的功能, 该实现类称为顺序表类。 顺序存储结构及特点,用一组地址连续的存储单元来依次存储线性表的各个元素。 用存储单元物理位置的相邻来表示相邻元素间的逻辑关系。 L=(a1,a2,ai-1,ai,ai+1,An) （图2.2 ）,39,顺序表元素的地址计算,由于在顺序表中的元素是顺序排列的，所以可以下列公式进行地址计算(设第一个元素的地址为a1，每个元素占用L个单元) LOC(ai) LOC(a1) (i-1)* L LOC(ai+1) LOC(ai) L LOC(an) LOC(a1) (n-1)* L,40,类型描述,const int maxlen=线性表可能达到的最大长度； struct TsqList Telem elemmaxlen; int curlen; ; TsqList La,Lb; La.elem0表示线性表的第一个元素， La.curlen 则表示线性表的当前长度,Elem0max-1,max,curlen,41,顺序表的类定义,template class SqList :public List private: Telem *elem; int curlen; int maxlen; public: SqList(int maxsz=100); SqList(Telem a,int n,int maxsz=100); SqList()delete elem; void init() curlen=0; Telem gete(int i); int leng()return curlen; int loct (Telem,42,顺序表类定义中的构造函数,SqList(int maxsz=100):maxlen(maxsz) curlen=0; elem=new Telemmaxlen; ; SqList(Telem a,int n,int maxsz=100):maxlen(maxsz) curlen=n; elem=new Telemmaxlen; for(int i=0;in;i+)elemi=ai; ;,43,顺序表类定义的实现：查找函数,含义：在指定的顺序表L中查找指定的元素el。若L中存在其值与el相等的数据元素，则函数值为该数据元素在线性表中的位序，否则为0。,Sxb.curlen,Sxb.elem,el,44,顺序表的操作实现：查找函数,函数表示形式： int loct (Telem& el) 功能：在顺序表中查找数据元素el，若线性表中存在与el相等的数据元素，则返回该数据元素在线性表中的序号，否则返回0。,45,查找函数,处理过程： 从第一个元素（序号为0）起，依次将实例中的元素与el进行比较， 直至与某一个元素比较相等返回该元素的序号， 或与curlen个元素全比较都不相等，则返回0。,Curlen-1,elem,比较对象 el 与 elem i i ：从0 到 curlen-1,0,46,查找函数,程序： template int SqList:loct(Telem 在上述程序中while循环的条件是必须同时满足 (icurlen)与 (elemi！el) 其中第1个条件表示还没有比较完，第2个条件表示还没有查到。,47,查找函数,执行实例： 假设线性表为 （a,c,e,g,i,k,m） 1.若给定的值ele,则当i2时比较相等，while循环结束返回值为3； 2.若给定的值elw,则当i7时while循环才结束，此时由于i的值已超过了表长-1因此返回值为0。,48,顺序表的插入操作：,含义：在顺序表的第i-1个数据元素与第i个数据元素之间插入一个新的元素。,Curlen-1,elem,i,插入位置,49,顺序表的插入操作：,插入操作由成员函数 bool inst (int loc,Telem& el) 表示，其功能为：将数据元素el插入在顺序表中的第loc个位置处，其中， 1 = loc = curlen + 1 若插入成功返回true,否则返回false。 该操作的处理过程为： (1)检查插入位置loc是否合法；若不合法返回false，否则： (2)长度加1并将第loc号到第curlen号元素向后移动一个位置； (3)将元素el在位置loc插入到线性表中并返回true。,50,插入操作,处理过程： （1）检查插入位置loc是否合法；若不合法返回false，否则： （2）长度加1并将第loc号到第curlen号元素向后移动一个位置； （3）将元素el在位置loc插入到线性表中并返回true。,Curlen-1,elem,后移元素 逻辑序号从 loc 到 curlen 物理序号从 loc-1 到 curlen-1 由于循环控制变量是以目的位置为准 所以 i 应从 loc 到 curlen 程序中 curlen先加了1 所以 i 应从 loc 到 curlen-1 注意:元素后移时应该从最后一个元素开始移动,loc,插入位置,0,51,插入操作,程序： template bool SqList:inst (int loc,Telem,52,插入操作,执行实例： 假设线性表为 （a,c,e,g,i,k,m） 1.若给定的参数值 elx, loc3 则正确插入，结果为：（a,c,x, e,g,i,k,m） 2.若给定的值loc8 则正确插入，结果为：（a,c,e,g,i,k,m,x） 3.若给定的值loc9 则输出出错信息,53,顺序表的删除操作：,含义：线性表的删除操作是指在线性表中删除其中的第i个数据元素,elem,i,删除元素,i1,i1,54,顺序表的删除操作：,删除操作由成员函数 Telem dele(int loc) 表示，其功能为：在顺序表中删除第loc号元素并返回该元素，其中， 1 = loc = curlen。该操作的处理过程为： (1)检查插入位置loc是否合法，若不合法返回NULL； (2)将第loc+1号到第curlen号元素向前移动一个位置； (3)长度减1并返回删除元素。,55,删除操作,处理过程： (1)检查插入位置loc是否合法； (2)将第loc+1号到第curlen号元素向前移动一个位置； (3)线性表长度减1并返回删除元素。,elem,loc,删除元素,Loc1,逐个上移传送： 逻辑序号： i 从 loc 1到 curlen 物理序号： i 从 loc 到 curlen-1 最后将 loc 位置的元素删除,56,删除操作,程序： template Telem SqList:dele(int loc) int i; Telem el; if (loccurlen) return NULL; else el=elemloc-1; for (i=loc; icurlen; i+)elemi-1=elemi; curlen-; return(el); ; ;,逐个上移传送： 逻辑序号： i 从 loc 1到 curlen 物理序号： i 从 loc 到 curlen-1 最后将 loc 位置的元素删除,57,删除操作,执行实例： 假设线性表为 （a,c,e,g,i,k,m） 1.若给定的参数值 loc3 则正确删除，返回结果为： e； 线性表成为（a,c,g,i,k,m） 2.若给定的值loc8 则输出出错信息,58,互动环节：顺序表的逆置操作,设计一个函数，其功能为对顺序表中的所有元素进行逆置，同时编制一个主程序，对该函数的功能进行测试。 设计思想：将该函数设置成类中的成员函数。由于是类中的成员函数，执行操作的对象是当前对象，因此该函数无须设置参数。另外该函数也无须设置返回值，因此其形式可设置如下： void inver (); 其处理过程为：将整个元素序列分为前后两部分，然后将这两部分中所有对应的元素进行交换。,59,逆置操作,处理过程： (1) 将整个元素序列分为前后两部分， (2)然后将这两部分中所有对应的元素进行交换。,Curlen-1,elem,交换对象： elem i 与 Sxb.elem n-1 -i i ： 从0 到 n / 2 - 1,0,60,逆置操作,程序： template void SqList:inver ( ) int i,m,n; Telem temp; n=curlen; m= n / 2; for (i= 0;im; i+ ) temp=elemi; elemi=elemn-1-i; elemn-1-i=temp; ; ;,逐个交换： elem i elem n-1-i i ： 从0 到 curlen / 2 - 1,61,逆置操作,在主函数中设置如下的测试代码： void main() char a='a','b','c','d','e' SqList sql1(a,5); for(int i=1;i=5;i+) coutsql1.gete(i)“ “; coutendl; sql1.inver(); for(int i=1;i=5;i+) coutsql1.gete(i)“ “; 程序的运行结果如下： a b c d e e d c b a,62,作业：顺序表合并操作,设计一个函数，其功能为将两个顺序表中的数据元素进行合并，同时编制一个主程序，对该成员函数的功能进行测试。 设计思想：将合并操作设计成顺序表类中的成员函数。由于是成员函数，操作的一方是当前对象，而在参数中只要指定另一个顺序表。合并的结果使当前对象发生了改变，同时作为函数的返回值返回。因此合并操作可设计成如下的形式： SqList& merg(SqList& l2) 处理过程：将参数中指定的顺序表中的元素依次追加到当前顺序表之后,使其长度为两者之和并返回当前对象。,63,作业：顺序表合并操作,template SqList ,64,后记,结束,65,版权所有, 1997 (c) Dale Carnegie & Associates, Inc.,线性表（二）,朱振元,66,单链表类,采用单向链式的存储方式存储的线性表称为单链表, 由此建立一个实现类,实现线性表抽象类中定义的各接口函数的功能, 该实现类称为单链表类。 顺序结构的不足之处: 难以为它确定适当的存储空间的大小 在作插入或删除时需移动大量元素 链式结构的特点: 存储单元的位置是任意的,由指针相连 完全避免了顺序存储结构所具有的弱点,67,链式存储结构的分类,按节点的分配方式,动态链表,单链表 循环链表,双向链表 双向循环链表,静态链表,按链的类别,68,单链表的结构形式及特点,由节点组成 n个结点（ai （1in）的存储映象）链结成一个链表，即为线性表(a1,a2,an)的链式存储结构 数据元素之间的逻辑关系是由结点中的指针指示的,NULL,NULL,69,相关的类型定义,struct Tnode Telem data; Tnode *next; ; Tnode * head； 链表定义 head = new nodetp; 生成链头节点 head-next= NULL;,70,单链表结点类的定义,template class LinkList; template class Node friend class LinkList ; Telem data; Node *next; public: Node(Telem d=0,Node *n=NULL) :data(d),next(n); ;,71,单链表类的定义,template class LinkList :public List private: Node *head; public: LinkList()head=new Node (); LinkList(Telem a,int n); LinkList()delete head; void init() delete head; head=new Node (); Telem gete(int i); int leng(); int loct (Telem,72,单链表建表操作,含义：指由一个一维数组a中的n个元素的值，建立一个长度为n的线性链表， （图2.11）,head,a1,a2,an,数组a,73,建表操作表示形式,LinkList(Telem a,int n) 其功能为：建立一个由head指向的长度为n的单链表（带头结点），并使其n个数据元素的值依次等于一维数组a中的n个元素的值。 该操作的处理过程为： (1)建立一个空表； (2)生成一个结点，按从下到上的次序从数组a中取出元素作为结点中的元素值，然后从链头插入该结点； (3)重复执行过程(2)直至生成n个结点。,74,建表操作处理过程,处理过程： （1）建立一个空表； （2）生成一个结点，按从下到上的次序从数组a中取出元素作为结点中的元素值，然后从链头插入该结点； （3）重复执行过程2直至生成n个结点。,head,head,head,75,建表操作程序代码,template LinkList:LinkList(Telem a,int n) Node *p; int i; head=new Node (); head-next=NULL; for (i=n-1;i=0;i- ) p=new Node (); p-data=ai; p-next= head-next; head-next=p; ; ;,76,单链表取元素操作,Telem gete(int i) 功能：取带头结点的单链表中的第i个数据元素。若1i表长,则返回表中的第i个数据元素，否则返回空元素NULL。 处理过程： (1)初始化，使指针p指向第一个元素的结点； (2)顺指针逐个后移直至指针指向第i个元素结点或指针为空； (3)若i个元素结点存在则返回该元素否则返回空元素NULL。,NIL,i,el,77,取元素操作程序代码,template Telem LinkList:gete(int i) Node *p; int j; p= head; j=0; while (p!=NULL ) 特殊情形： 1. 当 i表长时,p=NULL,返回NULL；,78,求长度操作,int leng(); 功能：求单链表的长度。其处理过程为： (1)使指针p指向第一个元素的结点，计数值初态。 (2)顺指针逐个后移并逐个计数直至指针为空。 (3)返回计数值。 实现代码： template int LinkList:leng() Node *p;int j; p= head-next; j=0; while (p!=NULL ) p=p-next; j=j+1; ; return j; ;,79,定位操作,int loct(Telem,80,单链表插入操作,含义：在线性表L的第i个节点前插入一个指定元素值的新结点。,i-1,i,81,插入操作表示形式,bool inst (int loc,Telem& el) 表示，参数loc、el分别表示插入的位置与插入的元素。该函数的功能为：在带头结点的单链表中的第loc号结点之前插入数据元素值为el的新结点，该操作的处理过程为： (1)寻找第loc1个结点，使指针p指向该结点。 (2)若由于loc不合理而找不到相应的结点，则输出信息，否则： (3)生成一个新结点s，并将s插入到结点p之后。,82,插入操作,处理过程： （1）寻找第loc1个结点，使指针p指向该结点； （2）若由于loc不合理而找不到相应的结点，则输出信息，否则： （3）生成一个新结点s，并将s插入到结点p之后。,NIL,Loc-1,el,83,插入操作程序代码,template bool LinkList:inst(int loc,Telem是等价的； 2.当 locloc-1,在程序中会输出出错信息； 3.当 loc表长时,循环结束后p=NULL，在程序中会输出出错信息；,84,单链表删除操作,含义：线性链表的删除操作是指删除线性链表中的第i号结点。,i,i-1,p,P-next:=p-next -next；,85,删除操作表示形式,Telem dele(int i) 表示，其功能为在单链表中删除第i个结点并返回该结点中的元素值，该操作的处理过程为： (1)寻找第i号结点，使指针p指向该结点的前驱结点。 (2)若由于i不合理而找不到相应的结点，则返回NULL，否则： (3)改变p的指针域，使得第i号结点从链表中被删除，释放该结点并返回该结点中的元素值。,86,删除操作程序代码,template Telem LinkList:dele(int i) Node *p,*q; int j;char el; p= head; j=0; while (p-next!=NULL ) ,87,删除操作说明,1.p=head;j=0; 与 p=head-next; j=1;是等价的 2.程序中的while 循环是查找loc-1号节点，且该节点必须存在后继节点，（p-next!=nil表示存在后继节点） 3. 当循环结束后p-next=NULL，说明给出的loc大于表长，当循环结束后 jloc-1时表示给出的 loc太小（=0）, 在程序中会输出出错信息,88,互动环节：单链表逆置操作,含义：单链表的逆置操作是指对一个用带头结点的链表表示的线性表进行逆置。,head,head,89,逆置操作处理过程,处理过程： （1）建立一个新的链表作为逆置后的链表（使用原带头结点），其初始状态为空表； （2）依次从原链表中取下一个结点，并将该结点从链头插入到新的链表中; （3）重复执行过程2直至原链表中的结点全部取完。,p,head,head,90,逆置操作程序代码,template void LinkList: inver() Tnode *p,*s; p= head-next; head-next=NULL; while (p!=NULL ) s=p; p=p-next; s-next= head-next; head-next=s; ; ;,91,上机实习（将类定义固定为字符形）,struct Tnode char data; Tnode *next; ; class LinkList private: Tnode *head; public: LinkList(char a,int n); void prnt(); void inver(); ; LinkList:LinkList(char a,int n) Tnode *p; int i; head=new Tnode; head-next=NULL; for (i=n-1;i=0;i- ) p=new Tnode; p-data=ai; p-next= head-next; head-next=p; ; ;,92,void LinkList: prnt() Tnode *p; p= head-next; while (p!=NULL ) coutdatanext; ; coutnext; head-next=NULL; while (p!=NULL ) s=p; p=p-next; s-next= head-next; head-next=s; ; ; void main( ) char a1='a','d','b','e','c' LinkList l1(a1,5); l1.prnt(); l1.inver(); l1.prnt(); ,93,排序操作程序代码,template void LinkList:orderinst(Tnode *ip) Tnode *p,*q; int data; data=ip-data; if (head-next=NULL)|(datanext-data) ip-next=head-next; head-next=ip; else p=head-next;q=NULL; while (p!=NULL),94,排序操作程序代码,template void LinkList:sort() Tnode *p,*s; p= head-next; head-next=NULL; while (p!=NULL ) s=p; p=p-next; orderinst(s); ; ; void main() char a1='a','d','b','e','c' LinkList l1(a1,5); l1.sort(); for(int i=1;i=5;i+) coutl1.gete(i)“ “; 程序的运行结果如下： a b c d e,95,静态链表类,采用静态链式的存储方式存储的线性表称为静态链表, 由此建立一个实现类,实现线性表抽象类中定义的各接口函数的功能, 该实现类称为静态链表类。,96,静态链表,结构形式 Sl=(a1,a4,a3,a2) 用一个一维数组来存储线性链表 数组中每一个元素表示线性链表中的一个结点。 这种结点由data与cur二个字域组成，data部分存 放数据元素，而cur部分存放指示下一个结点在 数组中位置的整型指示器 链头由sl表示，链末由-1表示。,Data Cur,97,静态链表的类型定义,const int maxlen=链表可能的最大长度； struct Tcomp Telem data; int cur; ; typedef Tcomp TstList maxlen; TstList stl; int sl; slssl.data; slssl.cur;,Data Cur,0,Max-1,98,静态链表的类定义,template class StList :public List struct Tcomp Telem data; int cur; Tcomp *sls; int av,sl; int maxlen; public: StList(int maxsz=100); StList()delete sls; void init(); Telem gete(int i); int leng(); int loct (Telem,Data Cur,99,静态链表类的构造函数,StList(int maxsz) 其功能是创建一个长度为maxsz的空表。即分配空间并将所分配的空间链成一个备用链表，链头由av指向，链末由-1表示，而将表示静态链表表头的sl设置为-1。 实现代码： template StList:StList(int maxsz):maxlen(maxsz) sls=new Tcomp maxlen; sl=-1; for(int i=0;imaxlen;i+)slsi.cur=i+1; slsmaxlen-1.cur=-1; av=0; ;,100,取元素操作,Telem gete(int i); 功能：取由sl指向的静态链表中的第i个数据元素。若1i表长,则返回表中的第i个数据元素，否则返回空元素NULL。 处理过程：顺静态链sl指针逐个后移并计数直至达到第i个结点返回结点元素或指针等于-1返回NULL； 实现代码： template Telem StList:gete(int i) int k,j=0; k=sl; while (ji ,101,定位操作,int loct(Telem ,102,静态链表的插入操作,bool inst (int loc,Telem& el) 功能：在静态链表sl中的第loc号结点之前插入数据元素值为el的新结点。 处理过程：对于在空表中插入或插入在链头两种特殊情形可直接进行相应的处理；对于一般的情形，则先要确定前驱结点k的位置，然后从自由链表av中取出一个空结点，填入元素值el，并将该结点插入到静态链表中下标为k的结点之后。,103,template bool StList:inst (int loc,Telem,104,静态链表的删除操作,Telem dele (int loc) 功能：删除静态链表中第loc个元素。 处理过程：若sl为空表则返回NULL；若删除sl链中的第一个元素，则将其链头结点取出挂在av链中并返回结点中的元素；对于一般的情形则先找前驱结点k，从sl链中取出K结点的后继结点挂入av链中，并返回该结点中的元素值。若给出的参数不合法，则返回NULL。,105,template Telem StList:dele (int loc) int i,j=0,k; if(sl=-1) /在空表中删除 return NULL; else if(loc = 1) /删除链头 i=sl; sl=slssl.cur; slsi.cur=av; av=i; /空结点插入av链 return slsi.data; else k=sl; /找前驱结点k，删除K结点后的结点 while (jloc-1 ,106,双向循环链表类,采用双向循环链式的存储方式存储的线性表称为双向循环链表, 由此建立一个实现类,实现线性表抽象类中定义的各接口函数的功能, 该实现类称为双向循环链表类。,107,循环链表,最后一个结点的指针域指向头结点，整个链表就形成一个环，因此称为循环链表。 可以从链表中的任一点出发找到链表中所有的其它结点 算法中判别当前指针P是否达到链尾的条件不是判P是否等于NULL，而是要判别P是否等于头指针,108,双向循环链表,在循环链表的基础上，再在结点中增加一个指向前驱结点的指针域 ，因此称为双向循环链表。 可以从链表中的任一点出发找到链表中所有的其它结点 既可以由前向后地对数据元素进行访问又可以由后向前地进行访问,109,双向循环链表类型定义,struct Tdnode Telem data; Tdnode *priou,*next; ; Tdnode *dl=new Tdnode； dl-data=a; dl-prior=NULL; dl-next=NULL;,110,双向循环链表结点类的定义,template class DlList; template class Dnode friend class DlList ; Telem data; Dnode *prior,*next; public: Dnode(Telem d=0,Dnode *p=NULL, Dnode *n=NULL) :prior(p),data(d),next(n); ;,111,双向循环链表的类定义,template class DlList :public List private: Dnode *dl; public: DlList()dl=new Dnode ();dl-prior=dl;dl-next=dl; DlList(Telem a,int n); DlList()delete dl; void init() delete dl; dl=new Dnode (); dl-prior=dl;dl-next=dl; Telem gete(int i); int leng(); int loct (Telem,112,双向循环链表构造函数,DlList(Telem a,int n) 该函数为类的构造函数。其功能为：生成一个长度为n的双向循环链表，且其n个结点中的数据初始值由数组参数a中的n个元素来确定。 处理过程：先创建一个仅含表头结点的空表，然后逐次生成一个新的结点，从数组a中取出元素作为结点中的元素值，并将该结点从链头插入到链表中，重复执行直至n个结点全插入完成。 实现代码： template DlList:DlList(Telem a,int n) Dnode *p; int i; dl=new Dnode ();dl-prior=dl;dl-next=dl; for (i=n-1;i=0;i-) p=new Dnode (); p-data=ai; p-next= dl-next; p-prior= dl; dl-next-prior=p; dl-next=p; ; ;,113,双向循环链表取元素操作,Telem gete(int i) 功能：取双向循环链表中的第i个结点的元素值，若第i个结点不存在则返回NULL。 处理过程：从头结点开始顺后继链指针逐个后移直至指向第i个结点或指针为空，并分别返回该结点的元素值或返回NULL。,i,p,dl,114,双向循环链表取元素操作程序代码,template Telem DlList:gete(int i) Dnode *p; int j; p=dl-next; j=1; while (p!=dl ) ,115,双向循环链表插入操作,bool inst(int loc,Telem& el) 功能：在双向循环链表dl中的第loc个结点之后插入元素值为el的结点。 处理过程： (1)由参数loc求得结点的指针p。 (2)若容许插入则生成一个元素值为el的新结点s，将由s所指向的结点插入到双向循环链表中的由p所指向的结点之后并返回true，否则返回false。,i,p,s,116,双向循环链表插入操作程序代码,template bool DlList:inst(int loc,Telem,117,双向循环链表删除操作,Telem dele(int i) 功能：删除双向循环链表中的第i个结点并返回该结点中的元素值。 处理过程： (1)由参数i求得结点的指针p。 (2)若第i个结点存在，则删除双向循环链表中的由p所指向的结点，释放该结点并返回该结点中的元素值否则返回NULL。,i,p,118,双向循环链表删除操作程序代码,template Telem DlList:dele(int i) Dnode *p; int j; Telem el; p=dl-next; j=1; while (p!=dl ) ,119,线性表功能演示程序,1. 问题说明 编制一个GUI教学演示程序，演示线性表的插入删除等操作的执行过程。 要求在演示窗体中显示线性表的当前状态，即显示线性表中当前的所有数据元素，数据元素可以用一个园或一个矩形来表示。设置清空、插入、删除、退出等四个操作按钮用于执行线性表的相应操作。 当按清空按钮时，使线性表成为一个空表； 当按插入按钮时，将指定的元素按指定的位序插入到线性表中； 当按删除按钮时，删除线性表中指定位序的元素； 当按退出按钮时，终止演示程序的执行。,120,线性表功能演示程序,2. 组件设置 操作界面中所涉及的组件包括绘图板、编辑框、数字增减器及按钮等，组件的类别及名称如下： TPaintBox *PaintBox1;/ 绘图板显示线性表的当前元素。 TComboBox *Comb1;/ 组合框用于指定插入元素或显示删除元素。 TCSpinEdit *Sp1;/ 数字增减器用于指定元素的序号。 TButton *Button1; / 清空按钮用于执行相应的操作。 TButton *Button2 / 插入按钮用于执行相应的操作。 TButton *Button3; / 删除按钮用于执行相应的操作。 TButton *Button4; / 退出按钮用于执行相应的操作。,121,线性表功能演示程序,3. 实现要点 1 创建线性表对象。线性表的实现类有顺序表、单链表、静态链表、双向链表等。可创建不同实现方式的线性表对象，并通过线性表抽象类的引用变量进行引用，如： char a=“abcdefg“; SqList sxb1(a,7,20); LinkList dlb1(a,7); StList jtlb1(100); DlList xhlb1(a,7); List ,122,void PaintList(List ,123,4. 事件处理程序的设置 1绘图板的OnPaint事件。在该处理程序中调用显示程序显示当前的线性表。 void _fastcall TAp21Form:PaintBox1Paint(TObject *Sender) PaintList(sqs1,PaintBox1); 2插入按钮单击事件。通过对线性表对象施行插入操作来实现程序的功能。 void _fastcall TAp21Form:Button2Click(TObject *Sender) char el; int loc; el=Comb1-Text1; loc=Sp1-Value; if(xxb1.inst(loc,el)PaintList(xxb1,PaintBox1); ,124,演示,结束,125,版权所有, 1997 (c) Dale Carnegie & Associates, Inc.,数据结构栈,朱振元,126,栈的初步认识,栈是限定只能在表的一端进行操作的线性表。 特点： 后进先出，栈又称作后进先出表（LIFO，即Last In First Out）。,入栈 出栈,栈顶,栈底,127,一般表示及基本