A2(线性表顺序存储)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,教学目标及要求,线性表的顺序存储,顺序表的操作,教学重点及难点,线性表的顺序存储,线性表的插入操作,线性表的删除操作,教学方法,多媒体演示,提问式,教学时数,2,复习,数据类型,算法定义及特点,时间复杂度,线性结构特点：,在数据元素的非空有限集中,存在,唯一,的一个被称作“,第一个,”的数据元素,存在,唯一,的一个被称作“,最后一个,”的数据元素,除第一个外，集合中的每个数据元素均,只有一,个前驱,除最后一个外，集合中的每个数据元素均,只有,一个后继,线性表,注意：,线性表是最常用且最简单的一种,线性,数据结构,线性表定义：,由,n,（,n=0,）,个数据元素,组成,的,有限序,列,。其中每个元素，除首元素和尾元素,外，有且仅有一个,直接前趋,和,直接后继,。,表中的元素个数定义为,线性表的长度,。,n=0,称为空表。例如：,a,i,是第,i,个数据元素，,i,为数据元素,a,i,在线性表中的位置,称,i,为,a,i,在线性表中的位序,实例,例 英文字母表（,A,B,C,.Z),是一个线性表,例,数据元素,线性表的操作,例 英文字母表（,A,B,C,.Z),是一个线性表,插入：,在下标为,K,的结点前（或后）插入一个新结点,删除：,删除下标为,K,的结点。,查找：,寻找下标为,K,的结点，或寻找域值的结点。,线性表的抽象数据类型,ADT List,数据对象：,D,a,i,|,a,i,ElemSet,i=1,2,.,n,n0,数据关系：,R1,|a,i-1,ai,D,i=2,.,n,基本操作：,InitList,(,&,L),操作结果：构造一个空的线性表,L,。,DestroyList,(,&,L),初始条件：线性表,L,已存在。操作结果：销毁线性表,L,。,ListEmpty,(L),初始条件：线性表,L,已存在。操作结果：若,L,为空表，则返回,TRUE,，,否则返回,FALSE,。,ListLength,(L),初始条件：线性表,L,已存在。操作结果：返回,L,中元素个数。,GetElem,(L,i,&,e),初始条件：线性表,L,已存在，,1iLengthList(L),。,操作结果：用,e,返回,L,中第,i,个元素的值。,ADT List,线性表的存储,线性表的顺序存储结构,顺序表：,定义：用一组地址连续的存储单元存放一个线性表叫,元素地址计算方法：,LOC(a,i,)=LOC(a,0,)+(i-1)*L,LOC(a,i+1,)=,LOC(a,i,)+L,其中：,L,一个元素占用的存储单元个数,LOC(a,i,),线性表第,i,个元素的地址,n-1,i,3,2,1,a,n-1,.,a,i,.,a,3,a,2,a,1,2004,2002,2000,线性表的顺序存储结构,顺序表：,定义：用一组地址连续的存储单元存放一个线性表叫,元素地址计算方法：,LOC(a,i,)=LOC(a,1,)+(i-1)*L,LOC(a,i+1,)=,LOC(a,i,)+L,其中：,L,一个元素占用的存储单元个数,LOC(a,i,),线性表第,i,个元素的地址,特点：,逻辑顺序和物理顺序相同,实现,随机存取,实现：,可用,C,语言的一维数组实现,A，,B，,C，,D，,E，,E，,F,（）,线性表,typedef,int,DATATYPE;#define M 1000,DATATYPE dataM;,F,E,E,D,C,B,A,5,6,4,3,2,1,0,数组下标,5,6,4,3,2,1,0,元素序号,顺序表,20,男,张军,.,.,.,18,女,李娟,年龄,性别,姓名,线性表,20,男,张军,18,女,李娟,1,0,数组下标,顺序表,typedef,struct,student,char name20;,char sex;,int,age;,DATATYPE;,DATATYPE,suM,;,顺序表的实现的运算,插入,删除,查找,插入,在顺序表（,12,13,21,24,30,77,）中，插入元素,25,。,77,30,24,21,13,12,6,5,4,3,2,1,0,25,插入前,77,30,25,24,21,13,12,6,5,4,3,2,1,0,插入后,顺序表插入实现,int,a5=12,13,21,24,30,77,插入算法,被插入的元素,2.,该元素被插入的,位置,3.,移动元素,4.,插入,scanf(“%d”,&a,);,scanf(“%d”,&n,);,for(i=length-1;i=n;i-),ai+1=ai;,an=a;,删除,在顺序表（,12,13,21,24,30,77,）中，删除下标为,3,的元素。,77,30,24,21,13,12,5,4,3,2,1,0,77,30,21,13,12,4,3,2,1,0,删除后,顺序表插入实现,int,a5=12,13,21,24,30,77,删除算法,被删除元素的,位置,2.,移动元素,scanf(“%d”,&n,);,for(i=n;i=,L.Listsize,),newbase,=(,ElemType,*),realloc,(,L.elem,(L.listsize,+LISTINCREMENT),*,sizeof(ElemType,);,L.elem,=,newbase,;,L.listsize,+=LISTINCREMENT;,q=,for(p,=p=,q;-p,),*(p+1)=*p;,*q=e;,+,L.length,;,return,ok;,realloc,函数,函数原型：,void,realloc(elemtype,*,ptr,int,newsize,),说明：,realloc,(),函数原型在,stdlib.h,和,alloc.h,功能：函数,realloc,(),把由,ptr,所指向的已分配的内存大小变成由,newsize,所确定的新的大小。,newsize,值可以大于或小于原先的值。由于,realloc,(),为了增加它的大小需要移动块，所以内存块的指针必须返回。如果出现这种情况，原先块的内容要被拷贝到新块中去，信息不会丢失，如果没有足够的内存来分配给,newsize,字节，函数将返回空指针，原先的内存也会被丢失,删除算法,Status,ListDelete_Sq(LinkList,&,L,int,i,ElemType,&e),if(i,L.length,),return Error;,p=,e=*p;,q=L.elem+L.length-1;,for(+p;p,=,q;+p,),*(p-1)=*p;,-,L.length,;,return OK:,查找算法,int,LocateElem_sq(sqlist,L,ElemType,e,status,(*,compare)(ElemType,ElemType,),i=1;,p=,L.elem,;,while(i,=,L.length,&!(*compare)(*,p+,e,),+i;,if(i,=,L.length,),return i;,else,return 0;,小结,线性表的特点,线性表的定义,线性表的顺序存储,作业,实现查找的算法,作业,顺序表的插入算法,顺序表的删除算法,