第2章(线性表)

数据结构NorthChinaElectricPowerUniversityDataStructure华北电力大学计算机科学与工程系Dept.ofComputerScience&EngineeringofNorthChinaElectricPowerUniversity第1章绪论第2章顺序表第3章链表第4章数组和广义表第5章串第6章树第7章图第8章查找表第9章内排序目录NorthChinaElectricPowerUniversity数据结构课程的起点：什么是线性结构？NorthChinaElectricPowerUniversity本章主要内容★线性表★栈★队列NorthChinaElectricPowerUniversity2.1线性表一、线性表的逻辑结构线性表举例：例1.一副扑克牌中同一花色的13张牌组成一个线性表(A,2,3,4,5,6,7,8,9,10,J,Q,K)例2.人民币面值的所有种类组成一个线性表(1角，2角，5角，1元，2元，5元，10元，20元，50元，100元)例3.一本书可以看成是一个线性表，每一页是一数据元素NorthChinaElectricPowerUniversity例4.学生的学籍档案构成一个线性表学号姓名入学总分数学分析程序设计离散数学…981201王国强435886582…981202赵济实429859078…981203刘晔512978895…981204叶桑林488939185……………………981250田华月501899587…数据元素数据项NorthChinaElectricPowerUniversity线性表是0个或多个元素的有穷序列，通常可表示成a1,a2,a3,…,ai,…,an(n≥0)n:线性表的表长n=0时称为空表n≥1时，a1称为第一个元素，an称为最后一个元素ai称为ai+1的前驱，ai+1称为ai的后继，i称为序号或索引NorthChinaElectricPowerUniversity线性表的定义（1）当1in时，ai的直接前驱为ai-1,ai的直接后继为ai+1。（2）除了第一个元素与最后一个元素,序列中任何一个元素有且仅有一个直接前驱元素,有且仅有一个直接后继元素。线性表的特性NorthChinaElectricPowerUniversity线性表的逻辑结构线性表的逻辑结构为线性结构二、线性表的基本运算1.Initial(L):初始化操作，设定一个空的线性表L。2.Length(L):返回线性表的表长。3.Get(L,i):若1≤i≤Length(L),返回线性表的第i个元素。5.Insert(L,i,x):在线性表的第i个位置插入一新元素x。6.Delete(L,i):删除线性表L的第i个元素。7.Empty(L):若线性表L为空返回True,否则返回False。4.Locate(L,x):若L中存在一个或多个值和x相等，运算结果为这些元素序号的最小值，否则返回0。NorthChinaElectricPowerUniversity线性表的其它运算：1.求任一元素的直接前驱或直接后继。2.按照一定的原则，将两个或两个以上的线性表合并成为一个线性表。4.按照一定的原则，将一个线性表分解为两个或两个以上的线性表。……3.复制线性表。线性表的基本运算示例NorthChinaElectricPowerUniversity例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);k:=0;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;}}}voidunion(Linear_listLa,Linear_ListLb)/*将所有在Lb中存在而在La中不存在的数据元素插入到La中*/{n=Length(La);//确定线性表La的长度例2.判断两个集合A和B是否相等。NorthChinaElectricPowerUniversityintCompare(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);}三、线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，数据元素之间的逻辑关系通过元素的存储位置直接反映。存储地址b=Loc(a1)b+cb+(i-1)*cb+(n-1)*cb+(max-1)*c顺序存储的线性表的寻址公式：Loc(ai)=Loc(a1)+(i-1)*c（1≤i≤n）内存状态元素在线性表中的次序12in空闲a1a2…ai…anLoc(a1)为线性表的第一个元素a1的存储地址，c为每个元素所占的存储单元。NorthChinaElectricPowerUniversity顺序存储的优点：1.可以随机存取2.空间利用率高3.结构简单NorthChinaElectricPowerUniversity线性表的顺序存储可以借用数组类型来实现Pascal语言：A[1..n]A[1],A[2],…A[i],…A[n]C语言：A[n]A[1],A[2],…A[i],…A[n],其中A[0]存放特殊数值。插入后：元素序号1234111425201)在长度为n的线性表L的第i个位置上插入一个新元素x插入前：元素序号12345678插入27主要操作：1.将第i到n个元素依次后移一个位置2.将新元素x放到线性表的第i个位置上3.将线性表的表长由n修改为n+12831437811142520678928314378527NorthChinaElectricPowerUniversity四、线性表的基本运算在线性表L的第i个位置上插入新元素x的算法NorthChinaElectricPowerUniversityfor(j=n；j=i；j--)L[j+1]=L[j]；{数据元素依次向后移动一个位置}L[i]=x;{n=n+1;}{线性表的长度加1}{if((i1)||(in+1))error(“插入的位置非法”)；elsevoidInsertSql(Linear_listL,int&n,inti,ElemTypex)}时间复杂度分析若设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=1NorthChinaElectricPowerUniversity删除后：元素序号123111420NorthChinaElectricPowerUniversity2)删除长度为n的线性表L的第i个元素删除主要操作：1.将第i+1到n个元素依次前移一个位置2.将线性表的表长由n修改为n-1删除前：元素序号123456782831437811142520456743782831NorthChinaElectricPowerUniversity删除线性表L的第i个元素的算法for(j:=i+1；j=n;j++）L[j-1]:=L[j];{数据元素依次向前移动一个位置}n:=n-1;{线性表的长度减1}{if(i1)||(in)ERROR(‘没有这个元素!’)else{{voidDeletesql(Linear_listV,int&n,inti)}若qi为删除线性表中第i个数据元素的概率(概率相等)，在长度为n的线性表中删除第i个数据元素需要移动元素的平均次数(期望值）为：qi=1/nTds=qi(n-i)=(n-i)/n=(n-1)/2称该算法的时间复杂度为O(n)。ni=1ni=1时间复杂度分析NorthChinaElectricPowerUniversity3)定位运算：求x在线性表L中的最小序号元素序号12345678283143781114252028xNorthChinaElectricPowerUniversity算法intLocatesql(Linear_listL,ElemTypeitem){i=1；while((i=n)&&(L[i]!=item))i=i+1；if(i=n)return(i)；//查找成功,返回信息i//elsereturn(0)；//查找失败,返回信息0//}NorthChinaElectricPowerUniversity4)顺序表的其他算法举例例1.按照字典序比较两个线性表A和B的大小intCompare(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(1)；}已知长度为n的线性表A采用顺序存储结构，并且数据元素按值大小非递减排列。写一算法，删除线性表中值相同的多余元素。例3voidDel(Linear_listA,int&n,inti){i:=1;while(in){if(A[i]A[i+1])i:=i+1else[for(j:=i+1;j=n;j++)A[j1]:=A[j];n:=n–1;]}}NorthChinaElectricPowerUniversity顺序存储的缺点：1.需要一片地址连续的存储空间;2.插入和删除元素时不方便，大量的时间用在元素的搬家上;3.在预分配存储空间时，可能造成空间的浪费;4.表的容量难以扩充。解决的方案：1.对线性表的插入和删除运算进行限定2.采用其它的存储结构(链式存储)NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity栈：所有的插入和删除都只能在表尾（栈顶）进行的线性表。允许进行插入和删除操作的一端叫栈顶，不允许插入和删除的一端叫栈底。没有元素的栈叫空栈。a1栈底栈顶插入删除若给定栈S=(a1,a2,…,an),则a1是栈底元素，an是栈顶元素，表中元素按a1,a2,…,an顺序进栈，按an,…,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出(FILO)。an…a2a12.2栈一、栈的逻辑结构NorthChinaElectricPowerUniversity栈的举例：1)装乒乓球的圆筒，装的时候是第一个装入的球放在最底下，第二在它的上面，一个个依次装入，取出时最后装入的那个球却被第一个取走。2)假定有一个问题P,它的解决依赖于两个子问题A和E的解决，而子问题A的解决又依赖于子问题B和C的解决，问题C