第二章-顺序表

第二章线性表华电计算机系2.1线性表2.2栈2.3队列华电计算机系2.1线性表一.线性表的逻辑结构1、一幅扑克牌的点数(2，3，4，5，6，7，8，9，10，J、Q、K、A)2、美国在第二次世界大战中参战的年份(1941,1942,1943,1944,1945)线性表举例：华电计算机系3、学生成绩登记表一个数据元素是一个数据记录华电计算机系华电计算机系线性表的定义线性表是0个或多个元素的有穷序列，通常可表示成a1,a2,a3,…,ai,…,an(n≥0)n:线性表的表长n=0时称为空表数逻网络99001张华7889788099002李军6756767699003王小明9087888999050刘末866778学号姓名程设数结……99001张华788999002李军6756767699003王小明9087888999050刘末866778学号姓名程设数结……87(2)除了第一个元素与最后一个元素,序列中任何一个元素有且仅有一个直接前驱元素,有且仅有一个直接后继元素。线性表的逻辑结构为线性结构(1)当1in时，ai的直接前驱为ai-1,ai的直接后继为ai+1。华电计算机系线性表的特性线性表的逻辑结构1.Initial(L):初始化操作，设定一个空的线性表L。2.Length(L):求长度函数，返回线性表的表长。3.Get(L,i):取元素函数，若1≤i≤Length(L),返回线性表的第i个元素。4.Locate(L,x):定位函数，若L中存在一个或多个值和x相等，运算结果为这些元素序号的最小值，否则返回0。5.Insert(L,i,x):在线性表的第i个位置插入一新元素x。6.Delete(L,i):删除线性表L的第i个元素。7.Empty(L):判空表函数，若线性表L为空返回True,否则返回False。二.线性表的基本操作华电计算机系1.求任一元素的直接前驱或直接后继2.按照一定的原则，将两个或两个以上的线性表合并成为一个线性表。4.按照一定的原则，将一个线性表分解为两个或两个以上的线性表。……线性表的其他操作3.复制线性表华电计算机系例1.设有两个线性表La和Lb，现将La和Lb合并成一个新表存于La中。Pascal实现C语言实现线性表的基本运算示例华电计算机系Fori:=1toLength(Lb)Do[x:=Get(Lb,i);k:=Locate(La,x);ifk=0then[Insert(La,n+1,x);n:=n+1;]]End;ProcedureUnion(VarLa:Linear_list;Lb:Linear_list);{将所有在Lb中存在而在La中不存在的数据元素插入到La中}Beginn:=Length(La);for(i=1;i=Length(Lb);i++){x=Get(Lb,i);k=Locate(La,x);if(k==0){Insert(La,n+1,x);n=n+1;}]End;voidunion(Linear_listLa,Linear_ListLb){将所有在Lb中存在而在La中不存在的数据元素插入到La中}n=Length(La);//确定线性表La的长度例2.判断两个集合A和B是否相等。线性表的基本运算示例FunctionCompare(La:Linear_list;Lb:Linear_list):Boolean;{若La和Lb不仅长度相等，而且所含元素也相同则返回True}BeginLen_la:=Length(La);Len_lb:=Length(Lb);ifLen_laLen_lbthenReturn(False)else[Fork:=1toLen_laDo[x:=Get(La,k);m:=Locate(Lb,x);ifm=0thenReturn(False);]]Return(True);End;Pasal语言实现华电计算机系intCompare(Linear_listLa,Linear_ListLb{若La和Lb不仅长度相等，而且所含元素也相同则返回0,否则返回-1}{Len_la=Length(La);Len_lb=Length(Lb);ifLen_laLen_lbReturn(-1)else{for(k=1;k=Len_lb;k++){x=Get(La,k);m=Locate(Lb,x);ifm=0thenReturn(-1);}}Return(0);}C语言实现三、线性表的顺序存储结构顺序存储的线性表的寻址公式：Loc(ai)=Loc(a1)+(i-1)*c1≤i≤nLoc(a1)为线性表的第一个元素a1的存储地址c为每个元素所占的存储单元个数用一组地址连续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过元素的存储位置直接反映。内存状态存储地址元素在线性表中的次序b=Loc(a1)b+cb+(i-1)*cb+(n-1)*cb+(max-1)*c12in空闲a1a2…ai…an华电计算机系线性表的顺序存储可以借用数组类型来实现Pascal语言：A[1..n]A[1],A[2],…A[i],…A[n]顺序存储的优点1.可以随机存取2.空间利用率高3.结构简单华电计算机系C语言：A[n+1]A[1],A[2],…A[i],…A[n],其中A[0]存放特殊数值。1.在长度为n的线性表L的第i个位置上插入一个新的数据元素X四、线性表基本运算的实现插入前：元素序号12345678插入27插入后：元素序号1234567892831437811142520283143781114252027主要操作1.将第i到n个元素依次后移一个位置2.将新元素x放到线性表的第i个位置3.将线性表的表长由n修改为n+1华电计算机系forj:=ndowntoidoL[j+1]:=L[j]；{数据元素依次向后移动一个位置}L[i]:=X;{将item插入线性表的第i个位置}n:=n+1][{线性表的长度加1}beginif(i1)or(in+1)thenError(‘插入的位置非法’)elseprodecureInsert(VarL:Linear_list;X:ElemType);End;华电计算机系类PASCAL实现for(j=n；j=i；j--)V[j+1]=V[j]；{数据元素依次向后移动一个位置}V[j]=X；{将X插入线性表的第i个位置}n=n+1}{{线性表的长度加1}{if((i1)||(in+1))error(“插入的位置非法”)；elsevoidInsertSql(Linear_listV,int&n,inti,ElemTypex)}华电计算机系类C语言实现时间复杂度分析若设pi为插入一个元素于线性表第i个位置的概率(概率相等)，则在长度为n的线性表中插入一个元素需要移动元素的平均次数（期望值）为：Pi(i=1,2,…,n,n+1)(其中pi=1/(n+1)）Tis=Pi(n-i+1)=(n-i+1)/(n+1)=n/2称该算法的时间复杂度是O(n)。n+1i=1n+1i=1华电计算机系2.删除长度为n的线性表L的第i个数据元素删除前：元素序号12345678删除删除后：元素序号1234567283143781114252043781114282031主要操作1.将第i+1到n个元素依次前移一个位置2.将线性表的表长由n修改为n-1华电计算机系forj:=i+1tondoL[j-1]:=L[j];//数据元素依次向前移动一个位置//n:=n-1;//线性表的长度减1//beginif(i1)or(in)thencallERROR(‘没有这个元素!’)else[]ProcedureDelete(VarL:Linear_list;i:Integer);end；华电计算机系类PASCAL实现for(j=i+1；j=n；j++)V[j-1]=V[j]；//数据元素依次向前移动一个位置//n=n-1;//线性表的长度减1//{if((i1)||(in))error(“Nothisnode”)；else{}voidDeletesql(Linear_listV,int&n,inti)}华电计算机系类C语言实现时间复杂度的分析若qi为删除线性表中第i个数据元素的概率(概率相等)，在长度为n的线性表中删除第i个数据元素需要移动元素的平均次数(期望值）为：qi=1/nTds=qi(n-i)=(n-i)/n=(n-1)/2称该算法的时间复杂度为O(n)。ni=1ni=1MacIIScanner华电计算机系3.确定元素item在长度为n的线性表L中的位置算法Pascal实现FunctionLocate(L:Linear_list;item:ElemType):Integer;beginfori:=1tondoif(L[i]=item)thenreturn(i)；//查找成功,返回信息i//return(0)；//查找失败,返回信息0//end；序号12345678元素283143781114252028x华电计算机系算法C语言实现intLocatesql(Linear_listV,ElemTypeitem){i=1；while((i=n)&&(V[i]!=item))i=i+1；if(i=n)return(i)；elsereturn(0)；}线性表的顺序存储结构的缺点1.缺点：2.解决方案(1)需要一片地址连续的存储空间;(2)插入和删除元素时不方便，大量的时间用在元素的搬家上;(1)对线性表的插入和删除运算进行限定(2)采用其它的存储结构(链式存储)(3)在预分配存储空间时，可能造成空间的浪费;(4)表的容量难以扩充。华电计算机系按照字典序比较两个线性表A和B的大小。(pascal实现)例1FunctionCompare(A:Linear_list;B:Linear_list):Integer;{若AB,则返回-1;若A=B,则返回0;若AB,则返回1}Beginj:=1;华电计算机系while(j=Length(A))and(j=Length(B))Do[ifGet(A,j)Get(B,j)thenReturn(-1)elseifGet(A,j)Get(B,j)thenReturn(1)elsej:=j+1;]if(Length(A)=Length(B)thenReturn(0)elseif(Length(A)Length(B)thenReturn(-1)elseReturn(0);End;按照字典序比较两个线性表A和B的大小。(C语言实现)例1intCompare(Linear_listA,Linear_listB){//若AB,则返回-1；若A=B,则返回0；若AB,则返回1}j=1；华电计算机系while((j=LENGTH(A)&&(j=Length(B)){if(Get(A,j)Get(B,j))return(-1)；elseif(Get(A,j)Get(B,j))return(1)；elsej=j+1；}if((Length(A)==Length(B))return(0)；elseif((Length(A)Length(B))return(-1)；elsereturn(0)；}2.2栈栈：所有的插入和删除都只能在表尾（栈顶）进行的线性表。允许进行插入和删除操作的一端叫栈顶，不允许插入和删除的一端叫栈底。没有元素的栈叫空栈。一.栈的逻辑结构栈底栈顶a1插入删除an…a2a1若给定栈S=(a1,a2,…,an),则a1是栈底元素，an是栈顶元素，表中元素按a1,a2,…,an顺序进栈，按an,…,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出(FILO)。华电计算机系栈的举例1)装乒乓球的圆筒，装的时候是第一个装入的球放在最底下，第二在它的上面，一个个依次装入，取出时最后装入的那个球却被第一