数据结构chap2顺序表课件

第二章第二章线性表线性表第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列第第4 4章章 串串第第5 5章章 数组和广义表数组和广义表 线性结构线性结构若若结结构构是是非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a a1 1,a,a2 2 ,a,an n）线性结构的定义：线性结构的定义：线性结构的定义：线性结构的定义：（逻辑、存储（逻辑、存储和运算）和运算）*线性结构的特点：线性结构的特点：只有一个首结点和尾结点；只有一个首结点和尾结点；除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a a1 1,a,a2 2 ,a,an n）线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的 *第第2 2章章线性表线性表1.了解线性结构的特点了解线性结构的特点2.2.掌握顺序表的定义、查找、插入和删除掌握顺序表的定义、查找、插入和删除 3.3.掌握链表的定义、查找、插入和删除掌握链表的定义、查找、插入和删除 4.4.能够从时间和空间复杂度的角度比较两种能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合存储结构的不同特点及其适用场合 教学目标教学目标 *2.1线性表的类型定义线性表的类型定义2.2线性表的顺序表示和实现线性表的顺序表示和实现2.3线性表的链式表示和实现线性表的链式表示和实现2.4线性表的应用线性表的应用教学内容教学内容 *（a1,a2,ai-1，ai,ai1，,an）线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0n=0时称为时称为数据元素数据元素线性起点线性起点a ai i的直接前趋的直接前趋a ai i的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点2.1 2.1 线性表的类型定义线性表的类型定义 *例例例例11分析分析分析分析2626个英文字母组成的字母表个英文字母组成的字母表个英文字母组成的字母表个英文字母组成的字母表 （A,B,C,D,Z）例例例例22分析学生情况登记表分析学生情况登记表分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录;元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母;元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性 *抽象数据类型抽象数据类型抽象数据类型抽象数据类型线性表线性表的定义为：的定义为：的定义为：的定义为：ADTList 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 称 n 为线性表的表长表长;称 n=0 时的线性表为空表空表。数据关系数据关系：R1|ai-1,aiD,i=2,.,n 设线性表为(a1，a2,.，ai，.，an),称 i 为 ai 在线性表中的位序位序。*线性表的基本操作线性表的基本操作1.1.初始化线性表初始化线性表L L InitList(LInitList(L)2.2.销毁线性表销毁线性表L L DestoryList(LDestoryList(L)3.3.清空线性表清空线性表L L ClearList(LClearList(L)4.4.求线性表求线性表L L的长度的长度 ListLength(LListLength(L)5.5.判断线性表判断线性表L L是否为空是否为空 IsEmpty(LIsEmpty(L)6.6.获取线性表获取线性表L L中的某个数据元素内容中的某个数据元素内容 GetElem(L,i,eGetElem(L,i,e)7.7.检索值为检索值为e e的数据元素的数据元素 LocateELem(L,eLocateELem(L,e)8.8.在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(L,i,eListInsert(L,i,e)9.9.删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDelete(L,i,eListDelete(L,i,e)ADT List *2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻顺序存储方法：顺序存储方法：用用一组地址连续一组地址连续的存储单元依次存储的存储单元依次存储线性表的元素，可通过线性表的元素，可通过数组数组VnVn 来实现。来实现。顺序存储定义：顺序存储定义：把逻辑上相邻的数据元素存储在物理把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。上相邻的存储单元中的存储结构。*元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储随机存取随机存取的存储结构的存储结构 *顺序表的类型定义顺序表的类型定义数据结构基本运算操作有：数据结构基本运算操作有：查找、插入、删除查找、插入、删除typedefstruct SqList;/俗称 顺序表顺序表#define LIST_INIT_SIZE 80 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量ElemType*elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量 /(以sizeof(ElemType)为单位)*malloc(malloc(m m)：开辟：开辟m m字节长度的地址空间，字节长度的地址空间，并返回这段空间的首地址并返回这段空间的首地址sizeof(sizeof(x x)：计算变量：计算变量x x的的字节字节长度长度free(free(p p)：释放指针：释放指针p p所指变量的存储空间，所指变量的存储空间，即彻底删除一个变量即彻底删除一个变量补充：补充：C C语言的动态分配函数（语言的动态分配函数（）*n函数调用时传送给形参表的实参必须与形参在类型、函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致个数、顺序上保持一致n参数传递有两种方式参数传递有两种方式n传值方式传值方式（参数为整型、实型、字符型等）（参数为整型、实型、字符型等）n传地址传地址参数为指针变量参数为指针变量参数为引用类型参数为引用类型参数为数组名参数为数组名补充：补充：C+C+中的参数传递中的参数传递 *voidmain()floata,b;cinab;swap(a,b);coutaendlbendl;#includevoidswap(floatm,floatn)floattemp;temp=m;m=n;n=temp;传值传值方式方式把实参的值传送给函数的形参中把实参的值传送给函数的形参中，函数使用，函数使用这个形参执行必要的功能。函数修改的是这个形参执行必要的功能。函数修改的是形形参的值参的值，实参的值不变实参的值不变 *传地址传地址方式方式指针变量作参数指针变量作参数voidmain()floata,b,*p1,*p2;cinab;p1=&a;p2=&b;swap(p1,p2);coutaendlbendl;#includevoidswap(float*m,float*n)floatt;t=*m;*m=*n;*n=t;形参变化影响实参形参变化影响实参 *传地址传地址方式方式指针变量作参数指针变量作参数voidmain()floata,b,*p1,*p2;cinab;p1=&a;p2=&b;swap(p1,p2);coutaendlbendl;#includevoidswap(float*m,float*n)float*t;t=m;m=n;n=t;形参变化不影响实参？形参变化不影响实参？*传地址传地址方式方式引用类型作参数引用类型作参数引用：它用来给一个对象提供一个替代的名字。引用：它用来给一个对象提供一个替代的名字。#includevoidmain()inti=5;int&j=i;i=7;couti=ij=ab;swap(a,b);coutaendlbendl;#includevoidswap(floatm,floatn)floattemp;temp=m;m=n;n=temp;传地址传地址方式方式引用类型作参数引用类型作参数 *（1 1）传递引用给函数与传递指针的效果是一）传递引用给函数与传递指针的效果是一样的，样的，形参变化实参也发生变化形参变化实参也发生变化。（2 2）引用类型作形参，在内存中并没有产生）引用类型作形参，在内存中并没有产生实参的副本，它实参的副本，它直接对实参操作直接对实参操作；而一般变；而一般变量作参数，形参与实参就占用不同的存储单量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。元，所以形参变量的值是实参变量的副本。因此，当因此，当参数传递的数据量较大参数传递的数据量较大时，用引用时，用引用比用一般变量传递参数的时间和空间效率都比用一般变量传递参数的时间和空间效率都好。好。引用类型作形参的三点说明引用类型作形参的三点说明 *（3）指针参数虽然也能达到与使用引用的效）指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用果，但在被调函数中需要重复使用“*指针指针变量名变量名”的形式进行运算，这很容易产生错的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用函数的调用点处，必须用变量的地址作为实变量的地址作为实参参。引用类型作形参的三点说明引用类型作形参的三点说明 *线性表的基本操作线性表的基本操作1.1.初始化线性表初始化线性表L L InitList(LInitList(L)2.2.销毁线性表销毁线性表L L DestoryList(LDestoryList(L)3.3.清空线性表清空线性表L L ClearList(LClearList(L)4.4.求线性表求线性表L L的长度的长度 ListLength(LListLength(L)5.5.判断线性表判断线性表L L是否为空是否为空 IsEmpty(LIsEmpty(L)6.6.获取线性表获取线性表L L中的某个数据元素内容中的某个数据元素内容 GetElem(L,i,eGetElem(L,i,e)7.7.检索值为检索值为e e的数据元素的数据元素 LocateELem(L,eLocateELem(L,e)8.8.在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(L,i,eListInsert(L,i,e)9.9.删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDelete(L,i,eListDelete(L,i,e)*典型操作的算法实现典型操作的算法实现1.1.初始化线性表初始化线性表L L（参数用引用）（参数用引用）StatusInitList_Sq(SqList&L)/构造一个空的线性表构造一个空的线性表/InitList_Sq算法时间复杂度：算法时间复杂度：O(1)L.elem=(ElemType*)malloc(LIST_INIT_SIZE sizeof(ElemType