第二章线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
华电计算机系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)当1
Len_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_la<>Len_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(i<1)or(i>n+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((i<1)||(i>n+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(i<1)or(i>n)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((i<1)||(i>n))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=1华电计算机系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.解决
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
(1)需要一片地址连续的存储空间;(2)插入和删除元素时不方便，大量的时间用在元素的搬家上;(1)对线性表的插入和删除运算进行限定(2)采用其它的存储结构(链式存储)(3)在预分配存储空间时，可能造成空间的浪费;(4)表的容量难以扩充。华电计算机系按照字典序比较两个线性表A和B的大小。(pascal实现)例1FunctionCompare(A:Linear_list;B:Linear_list):Integer;{若AB,则返回1}Beginj:=1;华电计算机系while(j<=Length(A))and(j<=Length(B))Do[ifGet(A,j)Get(B,j)thenReturn(1)elsej:=j+1;]if(Length(A)=Length(B)thenReturn(0)elseif(Length(A)B,则返回1}j=1；华电计算机系while((j<=LENGTH(A)&&(j<=Length(B)){if(Get(A,j)Get(B,j))return(1)；elsej=j+1；}if((Length(A)==Length(B))return(0)；elseif((Length(A)
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
P,它的解决依赖于两个子问题A和E的解决，而子问题A的解决又依赖于子问题B和C的解决，问题C的解决依赖于问题D的解决。PAEBC123456781011129解决问题的步骤如左图所示，红色的箭头表示进入这个问题（或者说子问题进栈），绿色的箭头表示问题已经解决（或子问题出栈）。栈一般用来容纳被接受了的而还没有进行处理的信息。华电计算机系二.栈的基本操作1.InitStack(S):初始化操作，设定一个空栈S。2.PushStack(S,x):将元素x压入到栈S中。3.PopStack(S):当栈S不空时弹出栈顶元素。4.TopStack(S):当栈S不空时返回栈顶元素。5.EmptyStack(S):若栈S为空，返回True,否则返回False三.栈的顺序存储结构S：表示栈S[1]:表示第一个进栈的元素S[2]:表示第2个进栈的元素S[i]:表示第i个进栈的元素S[top]:表示栈顶元素top=0:表示栈空top=maxsize:表示栈满S:topS[1]S[2]S[i]S[top]maxsize空闲空间……ai…a2a1华电计算机系…maxsizeSTop=0空栈…Top=1只有一个元素AS[1]…Top=3CBAS[3]S[2]S[1]栈中有三个元素三.栈的顺序存储华电计算机系ProcedurePushStack(S,x);{m为栈的最大容量}Beginiftop=mthenError(‘栈已满’)else[top:=top+1;S[top]:=x;]End;voidPushStack(StackS,ElemTypex){if(top==m)error(“上溢”)；else{top=top+1；S[top]=x；}}四、栈的基本运算在顺序存储结构上的实现：1)PushStack(S,x):将元素x压入到栈S中。Pascal实现C语言实现上面两个元素的时间复杂性均为常量阶华电计算机系ProcedurePopStack(S);{m为栈的最大容量}Beginiftop=0thenError(‘栈空’)else[y:=S[top];top:=top-1;]End;voidPopStack(StackS){if(top==0)error(“下溢”)；else{y=S[top];top=top-1；}}四、栈的基本运算在顺序存储结构上的实现：2)PopStack(S):将栈顶元素出栈Pascal实现C语言实现上面两个元素的时间复杂性均为常量阶华电计算机系（以两个堆栈共享一个数组为例）STACK[M]top[1]、top[2]分别为第1个和第2个栈的栈顶元素的指针。插入：当i=1时，将x插入第1个栈，当i=2时，将x插入第2个栈。可用空间123…M第1个栈第2个栈top[1]top[2]五.双重栈华电计算机系初始条件：top[1]=0top[2]=m+1栈满条件：top[1]+1=top[2]top[2]-1=top[1]123…M第1个栈第2个栈可用空间123…M第1个栈第2个栈top[1]top[2]top[1]top[2]栈满的条件是top[1]=top[2]–1top[1]=top[1]+1STACK[top[1]]=itemi=1top[2]=top[2]–1STACK[top[2]]=itemi=2华电计算机系算法六.双重栈的基本运算的实现（Pascal实现）1)PushStack(S,i,x):将元素x压入到第i个栈中。华电计算机系iftop[2]=top[1]+1thenError(‘栈已满’)End;ProcedurePushStack(S,i,x);{S为两个栈的共享空间}Beginelse[Caseiof1:[top[i]:=top[i]+1;S[top[i]]:=x;]2:[top[i]:=top[i]-1;S[top[i]]:=x;]EndCase;]算法六.双重栈的基本运算的实现(C语言实现)1)PushStack(S,i,x):将元素x压入到第i个栈中。华电计算机系iftop[2]==top[1]+1thenError(‘栈已满’)}voidPushStack(StackS,inti,ElemTypex)//S为两个栈的共享空间{else{switch(i){case1:{top[i]=top[i]+1；S[top[i]]=x；break；}case2:{top[i]=top[i]-1；S[top[i]]:=x；break}}}算法六.双重栈的基本运算的实现（Pascal实现）2)PopStack(S,i):当第i个栈不空时弹出其栈顶元素。华电计算机系算法六.双重栈的基本运算的实现(C语言实现)2)PopStack(S,i):当第i个栈不空时弹出其栈顶元素。华电计算机系voidPushStack(StackS，inti，ElemTypex)；//S为两个栈的共享空间{switch(i){case1:{if(top[i]==0)error(“栈空”)elsetop[i]=top[i]-1；break；}case2:{if(top[i]==m+1)error(“栈空”)elsetop[i]=top[i]+1；break；}}}栈的应用举例：num=391106078391/84876/806商除以8商余数已知一个无符号十进制整数num，写一算法，依次输出其对应的八进制数的各位数字。例170648/860华电计算机系procedurechange(num);begintop:=0;算法NorthChinaElectricPowerUniversitywhile(num0)do[top:=top+1;Stack[top]:=numMod8;//余数进栈//num:=numdiv8;];while(top0)do[write(Stack[top]);top:=top-1;//退栈//]End;华电计算机系Pascal实现voidchange(intnum);{top=0;算法NorthChinaElectricPowerUniversitywhile(num!=0){top=top+1;Stack[top]=num%8;//余数进栈//num=num/8;}while(top!=0){write(Stack[top]);top=top-1;//退栈//}}华电计算机系C语言实现例2.栈与过程调用voidA1(){…A2();r1:…}voidA2(){…A3();r2:…}voidA3(){……}程序的调用过程如下：A1A2A3r1r2①②③④栈的变化状态如下：华电计算机系调A2前r1调A2后r2r1调A3后r1返回A2后返回A1后栈的应用举例：例3递归和栈计算阶乘的递归算法如下：pascal实现functionf(n):integer;beginif(n=0)thenreturn(1)elsereturn(n*f(n-1));end;n!=1n=0n*(n-1)!n>0假设求华电计算机系计算阶乘的递归算法如下：C语言实现intf(n){if(n=0)return(1);elsereturn(n*f(n-1));}栈的应用举例：当n=3时，调用过程如下：f(3)f(2)f(1)2*f(1)①②⑤④f(0)62113*f(2)1*f(0)③⑥栈的变化过程如下：华电计算机系3r调f(2)前调f(2)后3r2r3r2r1r2r3r3r调f(1)后调f(0)后返回f(1)后返回f(2)后返回f(3)后2.3队列队列常用在操作系统中，最典型的例子是作业排队。在允许多道程序运行的系统中，输出通道就一个，而在计算机中运行的程序有多个，若多个程序的运行结果都需要输出，那就要按请求输出的先后次序排队，逐个输出。一.队列的逻辑结构a1,a2,a3…,,an进队出队队头队尾队列：所有的插入在表的一端进行，所有的删除在表的另一端进行的线性表。允许插入的一端称队尾，允许删除的一端称为队头。队列是一种先进先出的线性表。华电计算机系每当通道传输完毕可以接受新的传输任务时，队头的作业必需从队列中退出，做输出操作，凡是申请输出的作业都从队尾进入队列。二.队列的存储结构可用向量q[0..m-1]存储队列中的元素，队列所允许的最大容量是m,如图：0123…m-1向量q:表示队列头指针front:总是指向队头的前一个位置尾指针rear:总是指向队列的最后一个元素队空：front=rear(下溢)队满：rear=m-1(上溢)华电计算机系下面我们举一个例子实际做一下：m=5rearfront01234删除ABC元素ABC0123D4加入D元素rearfrontABC01234rear=fornt=初始状态01234rearfrontA加入A元素01234rearfrontAB加入B元素01234rearfrontABC加入C元素华电计算机系0123D4加入E元素rearfrontBCEA此时，再想加入一个元素也加不进去了，我们说队列已经满了，rear=m-1。这里存在一个问题，实际上在前页的图中，队列并不是真正的溢出，但rear=m-1，又说明队列满，新元素插不进去，这种情况称作假溢出，真正的队满是元素占满队列的所有空间,即rear-front=m。解决这种现象有两种
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
：1)当发生假溢出时，我们把队列中的所有元素向排头方向移动，腾出新元素的位置，将新元素加入。此种方法适宜于元素少时，当队列中元素较多时，则得不偿失。2)采用取模运算。我们把q[0]和q[m-1]捏在一起，就形成了一个环。初始状态：头指针：在顺时针方向上落后于队列中第一个元素一个位置。尾指针：指向最后加入的元素的位置。华电计算机系rearfront01234初态r=f,队空rear01234front加入AAq[0]q[m-1]rearABC01234front加入C华电计算机系rear01234frontAB加入BABC01234rearfront删除ABCfront01234rearfrontDEF加入FD01234rearfront加入D01234rearfrontDEFGH加入G、Hr=f队满华电计算机系rear01234DE加入E从以上分析可以看出，循环队列的队空与队满条件相同，都是front=rear,这样我们区分不出队列到底是空还是满，对此有两种解决方法:1)设一个标志位区分队列是空还是满。(队空置0，队满置1)。但这种方法，设标志位以及对标志位的判断都需要花费机器空间和时间。2)不设置标志位，而把尾指针从后面追上头指针，即(rear+1)Modm=front，看作队满。很明显，这种方法浪费一个工作单元，但它是以一个工作单元的损失而换来时间上的节约。1.其操作仅仅是一般线性表的操作的一个子集。2.插入和删除操作的位置受到限制。三.队列的基本操作1.InitQueue(Q):初始化队列Q为一空队。2.InQueue(Q,x):把元素x插入队列Q中。3.OutQeue(Q):删除队列Q的队首元素。4.GetHead(Q):取得队列Q的队首元素。5.EmptyQueue(Q):判定Q是否为一空队，如果为空，则返回真。华电计算机系1)循环队列的插入：队列的基本运算在顺序存储结构上的实现华电计算机系thenError(‘Overflow’){队列满上溢}else[rear:=(rear+1)modm;Q[rear]：=x；]End;ProcedureInQueue(Q,x);{在循环队列Q中插入元素x}Beginif(rear+1)modm=front{m为循环队列的最大容量}else{rear=(rear+1)%m；Q[rear]=x；return(TRUE)；}}boolInQueue(ElemTypeQ[],ElemTypex)//在循环队列Q中插入元素x}{if((rear+1)%m==front)return(FALSE)；//队满Pascal实现C语言实现2)循环队列的删除：队列的基本运算在顺序存储结构上的实现华电计算机系iffront=rearthenError(‘队列空返回’)若队头等于队尾，则队空返回。否则队头加1，取模运算，然后将队头所指的元素送往y单元。else[front:=(front+1)modm;y:=Q[front];]End;ProcedureOutQueue(Q);{在循环队列Q中删除队头元素}Beginiffront==rearError(‘队列空返回’)else{front=(front+1)modm;y=Q[front];}}voidOutQueue(ElemTypeQ[])//在循环队列Q中删除队头元素{Pascal实现C语言实现例:假设以一维数组sequ[m]存储循环队列的元素，若要使这m个分量都要得到应用，则另设一标志tag,以tag为0或1来区分头指针和尾指针相等时队列的状态为“空”或“满”,编写此队列的入队和出队算法。数据结构类型定义如下（Pascal实现）Constm=100;Typesequeue=Recordsequ:Array[0..m-1]ofElemType;front,reat:Integer;tag:Integer;End;华电计算机系C语言实现#definem100typedefstruct{ElemTypesequ[0..m-1]；intfront,reat；inttag；}Sequeue；插入算法：（Pascal实现）华电计算机系ProcedureInQueue(Q:sequeue;x:ElemType);Beginif(Q.front=Q.rear)and(Q.tag=1)then[Writeln(‘OverFlow’);Return;]Q.rear:=(Q.rear+1)modm;Q.sequ[Q.rear]:=x;ifQ.rear=Q.frontthenQ.tag:=1;End;插入算法：（C语言实现）华电计算机系voidInQueue(SequeueQ,ElemTypex){if(Q.front==Q.rear)&&(Q.tag==1){Writeln(“OverFlow”);Return;}Q.rear=(Q.rear+1)%m;Q.sequ[Q.rear]=x;if(Q.rear==Q.front)Q.tag=1;}删除算法：（Pascal实现）华电计算机系FunctionOutQueue(Q:sequeue):ElemType;Beginif(Q.front=Q.rear)and(Q.tag=0)then[Writeln(‘UnderFlow’);Return;]x:=Q.sequ[Q.front];Q.front:=(Q.front+1)modm;ifQ.rear=Q.frontthenQ.tag:=0;Return(x);End;删除算法：（C语言实现）华电计算机系ElemTypeOutQueue(SequeueQ:){if(Q.front==Q.rear)&&(Q.tag==0)then[Writeln(“UnderFlow”);Return;]x=Q.sequ[Q.front];Q.front=(Q.front+1)%m;if(Q.rear==Q.front)Q.tag=0;Return(x);}华电计算机系
浙公网安备 33021202002483