数据结构线性表教案资料.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,-,线性表,齐 恒,hengqi,大黑楼,B0912,什么是云计算,?,云计算定义,云计算（,Cloud Computing,）：是分布式处理,(Distributed Computing),、并行处理,(Parallel Computing),和网格计算,(Grid Computing),的发展，或者说是这些计算机科学概念的商业实现。是指基于,互联网,的超级计算模式,-,即把存储于,个人电脑,、,移动电话,和其他设备上的大量信息和,处理器,资源集中在一起，协同工作。在极大规模上可扩展的信息技术能力向外部客户作为服务来提供的一种计算方式。,40,多亿的移动电话,一,2010,年,数据来源,:Nokia,个人电脑和,笔记本电脑,企业电脑,和服务器,PDA,云计算综述,数据在云端：不怕丢失,不必备份,可以任意点的恢复；,软件在云端：不必下载自动升级；,无所不在的计算：在任何时间，任意地点，任何设备登录后就可以进行计算服务；,无限强大的计算：具有无限空间的，无限速度。,硬件为中心,软件为中心,服务为中心,PC,C/S,云计算,云计算体系特点,通过,Internet,接入,不需要自身具有,IT,技术来实施,第三方提供,资源共享,无多余功能开发,无多余费用,系统延续性好,Cloud,Applications,(“Software-as-a-Service”),Cloud,Platforms,(“Platform-as-a-Service”),Cloud,Storage,Cloud,Servers,(“Infrastructure-as-a-Service”),云计算三种服务方式,SAAS,（,Software as a Service,）,PAAS,（,Platform as a Service,）,IAAS,（,Infrastructure as a Service,）,1.1,什么是数据结构,1.2,基本概念和术语,1.3,抽象数据类型的表示与实现,1.4,算法的描述和算法分析,第一章回顾,什么是数据结构,描述,非数值计算问题,的数学模型不是数学方程，而是,树、表和图,之类的,数据结构,。,数据结构描述现实世界实体的,数学模型,及其上的,操作,在计算机中的,表示和实现,。,基本概念和术语,数据,（,Data),数据元素,（,Data element,）,数据项,（,Data item,）,数据对象,（,Data Object,）,数据结构,（,Data Structure,）,-,带,结构,的数据元素的集合。包括数据的逻辑结构和数据的存储结构。,数据的逻辑结构,数据的存储结构,数据的运算：检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面：,抽象数据类型,(Abstract Data Type,简称,ADT),是指一个,数学模型,以及定义在此数学模型上的一组,操作,。,e.g.,矩阵（求转置、加、乘、逆、特征值）,算法的描述和算法分析,一、算法（,algorithm,）,解决某一特定问题的,具体步骤的描述,，,是,指令的有限序列,。,有穷性、确定性、可行性、有输入、有输出,二、算法设计的原则,设计算法时，通常应考虑达到以下目标：,1,正确性,2,.,可读性,3,健壮性,4,高效率与低存储量需求,三、算法分析,算法,=,控制结构,+,原操作,（固有数据类型的操作）,算法的执行时间,=,原操作,(i),的执行次数,原操作,(i),的执行时间,第二章,线性表,线性结构的,基本特征,为,:,1,集合中必存在唯一的一个,“第一元素”,；,2,集合中必存在唯一的一个,“最后元素”,；,3,除最后元素在外，均有,唯一的后继,；,4,除第一元素之外，均有,唯一的前驱,。,是一个数据元素的,有序（次序）集,2.1,线性表的类型定义,2.3,线性表类型的实现,链式映象,2.4,一元多项式的表示,2.2,线性表类型的实现,顺序映象,2.1,线性表的类型定义,抽象数据类型,线性表,的定义如下：,ADT List,数据对象,：,D,a,i,|a,i,ElemSet,i=1,2,.,n,n0,称,n,为线性表的,表长,;,称,n=0,时的线性表为,空表,。,数据关系,：,R1,|a,i-1,a,i,D,i=2,.,n,/,设线性表为,(a,1,，,a,2,.,，,a,i,，,.,，,a,n,),/,称,i,为,a,i,在线性表中的,位序,。,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,ADT,List,InitList(&L),操作结果：,构造一个空的线性表,L,。,初始化操作,结构销毁操作,DestroyList(&L),初始条件：,操作结果：,线性表,L,已存在。,销毁线性表,L,。,ListEmpty(L),ListLength(L),PriorElem(L,cur_e,&pre_e),NextElem(L,cur_e,&next_e),GetElem(L,i,&e),LocateElem(L,e,compare(),ListTraverse(L,visit(),引用型操作,:,ListEmpty(L),初始条件：,操作结果：,线性表,L,已存在。,若,L,为空表，则返回,TRUE,，否则,FALSE,。,（判断线性表是否为空）,ListLength(L),初始条件：,操作结果：,线性表,L,已存在。,返回,L,中元素个数。,（求线性表的长度）,PriorElem(L,cur_e,&pre_e),初始条件：,操作结果：,线性表,L,已存在。,若,cur_e,是,L,的元素，但不是第一个，则用,pre_e,返回它的前驱，否则操作失败，,pre_e,无定义。,（求数据元素的前驱）,NextElem(L,cur_e,&next_e),初始条件：,操作结果：,线性表,L,已存在。,若,cur_e,是,L,的元素，但不是最后一个，则用,next_e,返回它的后继，否则操作失败，,next_e,无定义。,（求数据元素的后继）,GetElem(L,i,&e),初始条件：,操作结果：,线性表,L,已存在，,且,1iLengthList(L),。,用,e,返回,L,中第,i,个元素的值。,（求线性表中某个数据元素）,LocateElem(L,e,compare(),初始条件：,操作结果：,线性表,L,已存在，,e,为给定值，,compare(),是元素判定函数。,返回,L,中第,1,个与,e,满足关系,compare(),的元素的位序。,若这样的元素不存在，,则返回值为,0,。,（定位函数）,ListTraverse(L,visit(),初始条件：,操作结果：,线性表,L,已存在，,Visit(),为某个访问函数。,依次对,L,的每个元素调用函数,visit(),。,一旦,visit(),失败，则操作失败。,（遍历线性表）,加工型操作,ClearList(&L),PutElem(&L,i,&e),ListInsert(&L,i,e),ListDelete(&L,i,&e),ClearList(&L),初始条件：,操作结果：,线性表,L,已存在。,将,L,重置为空表。,（线性表置空）,PutElem(&L,i,&e),初始条件：,操作结果：,线性表,L,已存在，,且,1iLengthList(L),。,L,中第,i,个元素赋值为,e,的值。,（改变数据元素的值）,ListInsert(&L,i,e),初始条件：,操作结果：,线性表,L,已存在,，,且,1iLengthList(L)+1,。,在,L,的第,i,个元素之前插入,新的元素,e,，,L,的长度增,1,。,（插入数据元素）,ListDelete(&L,i,&e),初始条件：,操作结果：,线性表,L,已存在且非空，,1iLengthList(L),。,删除,L,的第,i,个元素，,并用,e,返回其值，,L,的长度减,1,。,（删除数据元素）,利用上述定义的,线性表操作,可以实现其它更复杂的操作,假设,:,有两个,集合,A,和,B,，,分别用两个,线性表,LA,和,LB,表示，即：线性表中的数据元素即为集合中的成员。,现要求一个新的集合,A,AB,。,例,2-1,要求对线性表作如下操作：,扩大线性表,LA,，将,存在于,LB,中,而,不存在于,LA,中,的数据元素逐个,插入,到,LA,中,去。,上述问题可演绎为：,1,从线性表,LB,中依次察看每个数据元素,;,2,依值在线性表,LA,中进行查访,;,3,若不存在，则插入之。,GetElem(LB,i)e,LocateElem(LA,e,equal(),ListInsert(LA,n+1,e),操作步骤：,GetElem(Lb,i,&e),;/,取,Lb,中第,i,个元素赋给,e,if,(,!,LocateElem(La,e,equal(),),ListInsert(La,+La_len,e),;,/,La,中不存在和,e,相同的数据元素，则插入之,void,union(List,&,La,List Lb),La_len=,ListLength(La),;/,求线性表的长度,Lb_len=,ListLength(Lb),;,for,(i=1;i=Lb_len;i+),/union,已知,一个允许,包含重复元素的集合,B,，试,构造,一个,不允许包含重复元素的集合,A,，,使,A,中只包含,B,中所有值各不相 同的数据元素,。,仍选用,线性表,表示集合。,例,2-2,从集合,B,取出物件放入集合,A,要求集合,A,中,同样物件不能有两件以上,因此，,算法的策略应该和例,2-1,相同,上述问题可演绎为：,void,union(List,&,La,List Lb),/union,GetElem(Lb,i,&e),;/,取,Lb,中第,i,个元素赋给,e,if,(,!,LocateElem(La,e,equal(),),ListInsert(La,+La_len,e),;,/,La,中不存在和,e,相同的数据元素，则插入之,for,(i=1;i=Lb_len;i+),InitList(La);,/,构造,(,空的,),线性表,LA,La_len=,ListLength(La),;Lb_len=,ListLength(Lb),;,若线性表中的数据元素相互之间可以,比较,，并且数据元素在线性表中,依值,非递减或非递增有序,排列,，即,a,i,a,i-1,或,a,i,a,i-1,(i=2,3,n),，则称该线性表为,有序表,(Ordered List),。,试改变结构，以,有序表,表示集合。,例如,：,（,2,，,3,，,3,，,5,，,6,，,6,，,6,，,8,，,12,）,对集合,B,而言，,值相同的数据元素必定相邻；,对集合,A,而言，,数据元素依值从小至大的顺序插入。,因此，,数据结构改变了，,解决问题的策略也相应要改变。,void,purge(List,&,La,List Lb),InitList(LA),;,La_len=ListLength(La);,Lb_len=ListLength(Lb);/,求线性表的长度,for,(i=1;i=Lb_len;i+),/purge,GetElem(Lb,i,/,取,Lb,中第,i,个元素赋给,e,If,(ListEmpty(La)|!equal(en,e),ListInsert(La,+La_len,e);,en=e,;,/La,中不存在和,e,相同的数据元素，则插入之,例2-3,将,A,、,B,两个有序表合并成有序表,C,仍采用线性表表示,void,MergeList(List La,List Lb,List,&,Lc),/,本算法将非递减的有序表,La,和,Lb,归并为,Lc,/merge_list,while,(,i=La_len,),&,(,j=Lb_len,),/La,和,Lb,均不空,while,(,i=La_len,),/,若,La,不空,while,(,j=Lb_len,),/,若,Lb,不空,InitList(Lc);/,构造空的线性表,Lc,i=j=1;k=0;,La_len=ListLength(La);,Lb_len=ListLength(Lb);,/La,和,Lb,均非空，,i=j=1,k=0,GetElem(La,i,ai);,GetElem(Lb,j,bj);,if,(ai=bj),/,将,ai,插入到,Lc,中,ListInsert(Lc,+,k,ai);,+,i;,else,/,将,bj,插入到,Lc,中,ListInsert(Lc,+,k,bj);,+,j;,while,(i=La_len),/,当,La,不空时,GetElem(La,i+,ai);,ListInsert(Lc,+k,ai);,/,插入,La,表中剩余元素,while,(j=Lb_len),/,当,Lb,不空时,GetElem(Lb,j+,bj);,ListInsert(Lc,+k,bj);,/,插入,Lb,表中剩余元素,2.2,线性表类型的实现,顺序映像,最简单的一种顺序映象方法是：,令,y,的存储位置和,x,的存储位置相邻,。,顺序映象,以,x,的存储位置和,y,的存储位置之间某种关系表示逻辑关系,。,用一组,地址连续,的存储单元,依次存放,线性表中的数据元素,a,1,a,2,a,i-1,a,i,a,n,线性表的,起始地址,称作线性表的,基地址,以“,存储位置相邻,”表示有序对,即：,LOC(a,i,)=LOC(a,i-1,)+C,C,为,一个数据元素所占存储量,所有数据元素的存储位置均取决于,第一个数据元素的存储位置,LOC(a,i,)=,LOC(a,1,),+(i-1),C,基地址,顺序映像的,C,语言描述,typedef struct,SqList;/,俗称,顺序表,#define,LIST_INIT_SIZE 80,/,线性表存储空间的初始分配量,#define,LISTINCREMENT 10,/,线性表存储空间的分配增量,ElemType,*elem,;/,存储空间基址,int,length,;/,当前长度,int,listsize,;/,当前分配的存储容量,/(,以,sizeof(ElemType),为单位,),线性表的基本操作在顺序表中的实现,InitList(&L)/,结构初始化,LocateElem(L,e,compare()/,查找,ListInsert(&L,i,e)/,插入元素,ListDelete(&L,i)/,删除元素,Status,InitList_Sq(SqList,&,L),/,构造一个空的线性表,/InitList_Sq,算法,时间复杂度,：,O(1),L.elem=(ElemType*),malloc,(LIST_INIT_SIZE,sizeof,(ElemType);,If,(,!,L.elem),exit,(OVERFLOW);,L.length=0;,L.listsize=LIST_INIT_SIZE;,return,OK;,int,LocateElem_Sq(SqList L,ElemType e,Status,(*compare)(ElemType,ElemType),/,在顺序表中查询第一个满足判定条件的数据元素，,/,若存在，则返回它的位序，否则返回 0,/LocateElem_Sq,O(ListLength(L),算法的,时间复杂度,为：,i=1;,/,i,的初值为第,1,个元素的位序,p=L.elem;,/,p,的初值为第,1,个元素的存储位置,while,(i=L.length,&!,(*compare)(*p+,e),+i;,if,(i=q;-p),*,(p+1)=,*,p;/,插入位置及之后的,元素右移,*,q=e;/,插入,e,+L.length;/,表长增,1,return,OK;,if,(L.length=L.listsize),/,当前存储空间已满，增加分配,newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);,if,(!newbase),exit,(OVERFLOW);/,存储分配失败,L.elem=newbase;/,新基址,L.listsize+=LISTINCREMENT;/,增加存储容量,if,(i L.length+1),return,ERROR;,/,插入位置不合法,21 18 30 75 42 56 87,21 18 30 75,例如：,ListInsert_Sq(L,5,66),L.length,1,p,p,p,q,87,56,42,66,q=,&,(L.elemi);/q,指示插入位置,for,(p=,&,(L.elemL.length);p=q;-p),*,(p+1)=,*,p;,p,考虑移动元素的平均情况,:,假设在第,i,个元素之前插入的概率为 ，,则在长度为,n,的线性表中,插入一个元素所需移动元素次数的期望值,为：,若,假定,在线性表中任何一个位置上进行,插入的概率,都是,相等,的，则,移动元素的期望值,为,：,线性表操作,ListDelete,(&L,i,&e),的实现,：,首先分析：,删除元素时，,线性表的逻辑结构发生什么变化？,(a,1,a,i-1,a,i,a,i+1,a,n,),改变为,(a,1,a,i-1,a,i+1,a,n,),a,i+1,a,n,表的长度减,1,a,1,a,2,a,i-1,a,i,a,i+1,a,n,a,1,a,2,a,i-1,Status,ListDelete_Sq,(SqList,&,L,int,i),/ListDelete_Sq,for,(p=,&,(L.elemi+1,;p=q;+p),*(p-1)=*p;,/,被删除元素之后的元素左移,-L.length;/,表长减,1,return,OK;,算法时间复杂度,为,:,O(ListLength(L),q=L.elem+L.length-1;,/,表尾元素的位置,if,(i L.length),return,ERROR;,/,删除位置不合法,21 18 30 75 42 56 87,21 18 30 75,L.length,1,p,p,p,q,87,56,p=,q=L.elem+L.length-1;,for,(+p;p next=NULL;,/,先建立一个带头结点的单链表,for,(i=n;i 0;-i),p=(LinkList),malloc,(,sizeof,(LNode);,scanf,(,&,p-data);/,输入元素值,p-next=L-next;L-next=p;,/,插入,L,线性表的操作,GetElem(L,i,&e),在单链表中的实现,例,:,21,18,30,75,42,56,p,p,p,j,1,2,3,因此，查找第,i,个数据元素的基本操作为：,移动指针,p,，比较,j,和,i,。,单链表是一种顺序存取的结构，为找第,i,个数据元素，必须先找到其前趋结点,-,第,i-1,个数据元素。,编程实现时，令指针,p,始终,指向,线性表中第,j,个数据元素。,Status,GetElem_L(LinkList L,int,i,ElemType,&,e),/L,是带头结点的链表的头指针，以,e,返回第,i,个元素,/GetElem_L,算法,时间复杂度,为,:,O(ListLength(L),p=L-next;j=1;,/,p,指向第一个结点，,j,为计数器,while(p ,/,顺指针向后查找，直到,p,指向第,i,个元素,/,或,p,为空,if,(,!,p|ji),return,ERROR;,/,第,i,个元素不存在,e=p-data;,/,取得第,i,个元素的值,return,OK;,a,i-1,线性表操作,ListInsert(&L,i,e),在单链表中的实现,：,有序对,改变为,和,e,a,i,a,i-1,因此，在单链表中第,i,个结点之前进行插入的基本操作为,:,找到线性表中第,i-1,个结点，然后修改其指向后继的指针。,可见，在链表中插入结点只需要修改指针。但若要在第,i,个结点之前插入元素，修改的是第,i-1,个结点的指针。,Status,ListInsert_L(LinkList L,int,i,ElemType e),/,L,为带头结点的单链表的头指针，本算法,/,在链表中第,i,个结点,之前,插入新的元素,e,/LinstInsert_L,算法的,时间复杂度,为,:,O(ListLength(L),p=L;j=0;,while,(p,&,j next;+j;,/,寻找第,i-1,个结点,if,(,!,p,|,j i-1),return,ERROR;,/,i,大于表长或者小于,1,s=(LinkList),malloc,(,sizeof,(LNode);,/,生成新结点,s,-,data=e;,s-next=p-next;p,-,next=s;,/,插入,return,OK;,e,a,i-1,a,i,a,i-1,s,p,线性表,的操作,ListDelete(&L,i,&e),在链表中的实现,:,有序对,和,改变为,a,i-1,a,i,a,i+1,a,i-1,在单链表中,删除第,i,个结点,的,基本操作,为,:,找到线性表中第,i-1,个结点,p,，修改其指向后继的指针。,a,i-1,a,i,a,i+1,a,i-1,q=p-next;p-next=q-next;,e=q-data;,free(q);,p,q,Status,ListDelete_L(,LinkList L,int,i,ElemType,&,e),/,删除以,L,为头指针,(,带头结点,),的单链表中第,i,个结点,/ListDelete_L,算法的,时间复杂度,为,:,O(ListLength(L),p=L;j=0;,while,(p-next,&,j next;+j;,/,寻找第,i,个结点，并令,p,指向其前趋,if,(,!,(p-next)|j i-1),return,ERROR;,/,删除位置不合理,q=p-next;p-next=q-next;,/,删除并释放结点,e=q-data;,free(q);,return,OK;,操作,ClearList(&L),在链表中的实现,:,void,ClearList(,&,L),/,将单链表重新置为一个空表,while,(L-next),p=L-next;L-next=p-next;,/ClearList,free(p);,算法,时间复杂度,：,O(ListLength(L),四、一个带头结点的线性链表类型,typedef struct LNode /,结点类型,ElemType data;,struct LNode *next;,*Link,*Position;,Status MakeNode(Link,/,分配由,p,指向的值为,e,的结点，并返回,OK,，,/,若分配失败，则返回,ERROR,void FreeNode(Link,/,释放,p,所指结点,typedef struct,/,链表类型,Link head,tail,current;,/,分别指向链表头结点、最后一个结点和当前,/,访问结点的指针,int,len;,/,指示链表长度,LinkList;,链表的基本操作,:,结构初始化和销毁,Status,InitList(LinkList,&,L);,/,构造一个空的线性链表,L,，其头指针、,/,尾指针和当前指针均指向头结点，,/,表长为零。,Status,DestroyList(LinkList,&,L);,/,销毁线性链表,L,，,L,不再存在。,O(1),O(n),引用型操作,Status,ListEmpty(LinkList L);,/,判表空,int,ListLength(LinkList L);,/,求表长,Status,Prior(LinkList L);,/,改变当前指针，指向其前驱,Status,Next(LinkList L);,/,改变当前指针，指向其后继,ElemType,GetCurElem(LinkList L);,/,返回当前指针所指数据元素,O(1),O(1),O(n),O(1),O(1),Status,LocatePos(LinkList L,int i);,/,改变当前指针，指向第,i,个结点,Status,LocateElem(LinkList L,ElemType e,);,/,若存在与,e,相同的元素，则移动当前指针,/,指向满足条件的,元素的,前驱,，,/,并返回,OK;,否则返回,ERROR,Status,ListTraverse(LinkList L,Status,(,*,visit)();,/,依次对,L,的每个元素调用函数,visit(),O(n),O(n),O(n),加工型操作,Status,ClearList(LinkList,&,L);,/,重置,L,为空表,Status,SetCurElem(LinkList,&,L,ElemType e);,/,更新当前指针所指数据元素,Status,Append(LinkList,&,L,Link s);,/,将表,S,链接,在表,L,之后,Status,InsAfter(LinkList,&,L,Elemtype e);,/,在当前指针所指结点之后链接一个新结点,Status,DelAfter(LinkList,&,L,ElemType,&,e);,/,删除当前指针之后的结点,O(1),O(n),O(s),O(1),O(1),Status,InsAfter(LinkList&L,ElemType e),/,将数据元素,e,插入在线性链表,L,中当前指针所指结点,/,之后,并返回,OK;,否则返,回,ERROR,。,/InsAfter,if,(!L.current),return,ERROR;,if,(!MakeNode(s,e),return,ERROR;,s-next=L.current-next;,L.current-next=s;,if,(L.tail=L.current)L.tail=s;,L.current=s;,return,OK;,Status,DelAfter(LinkList,&,L,ElemType,&,e),/,若当前指针及其后继在链表中，则删除线性链表,L,中当前,/,指针所指结点之后的结点，并返回,OK;,否则返回,ERROR,。,/DelAfter,if,(,!,(L.current,&,L.current-next),return,ERROR;,q=L.current-next;e=q-data;,L.current-next=q-next;,if,(L.tail=q)L.tail=L.current;,FreeNode(q);,return,OK;,1.,双向链表,五、其它形式的链表,typedef struct,DuLNode,ElemType data;,/,数据域,struct,DuLNode,*,prior;,/,指向前驱的指针域,struct,DuLNode *next;,/,指向后继的指针域,DuLNode,*,DuLinkList,;,最后一个结点的指针域的指针又指回第一个结点的链表,a,1,a,2,.a,n,2.,循环链表,和单链表的差别仅在于，,判别,链表中最后一个结点的,条件,不再是,“后继是否为空”,，而是,“,后继是否为头结点,”,。,双向循环链表,空表,非空表,a,1,a,2,.a,n,双向链表的操作特点：,“,查询”和单链表相同。,“,插入”和“删除”时需要同时修改,两个方向上,的指针。,a,i-1,a,i,e,s-next=p-next;p-next=s;,s-next-prior=s;s-prior=p;,p,s,a,i-1,a,i,插入,a,i-1,删除,a,i,a,i+1,p-next=p-next-next;,p-next-prior=p;,p,a,i-1,六、有序表类型,ADT,Ordered_List,数据对象,:,S=x,i,|x,i,OrderedSet,，,i=1,2,n,n,0,集合中,任意两个,元素之间,均可以,进行比较,数据关系,:,R=|x,i-1,x,i,S,x,i-1,x,i,i=2,3,n,2.4,一元多项式的表示和相加,在计算机中，可以用一个线性表来表示,:,P=(p,0,p,1,，,p,n,),一元多项式,但是对于形如,S(x)=1+3x,10000,2x,20000,的多项式，上述表示方法是否合适？,一般情况下的,一元稀疏多项式,可写成,P,n,(x)=p,1,x,e1,+p,2,x,e2,+,+p,m,x,em,其中,：,p,i,是指数为,e,i,的项的非零系数,，,且,0 e,1,e,2,e,m,=n,可用下列线性表表示：,（,p,1,e,1,）,(p,2,e,2,),(p,m,e,m,),）,P,999,(x)=7x,3,-2x,12,-8x,999,例如,:,可用线性表,(7,3),(-2,12),(-8,999),表示,ADT Polynomial,数据对象,：,数据关系,：,抽象数据类型,一元多项式,的定义如下：,D,a,i,|a,i,TermSet,i=1,2,.,m,m0,TermSet,中的,每个元素包含一个,表示系数的实数和表示指数的整数,R1,|a,i-1,a,i,D,i=2,.,n,且,a,i-1,中的指数值,a,i,中的指数值,CreatPolyn(&P,m),DestroyPolyn(&P),PrintPolyn(&P),基本操作,：,操作结果,：,输入,m,项的系数和指数，,建立一元多项式,P,。,初始条件,：,一元多项式,P,已存在,。,操作结果,：,销毁一元多项式,P,。,初始条件,：,一元多项式,P,已存在,。,操作结果,：,打印输出一元多项式,P,。,PolynLength(P),AddPolyn(&Pa,&Pb),SubtractPolyn(&Pa,&Pb),ADT Polynomial,初始条件,：,一元多项式,P,已存在,。,操作结果,：,返回一元多项式,P,中的项数,。,初始条件,：,一元多项式,Pa,和,Pb,已存在,。,操作结果,：,完成多项式相加,/,相减,运算，即：,Pa=Pa,Pb,或,Pa=Pa-Pb,一元