数据结构-合肥工业大学 2(合肥工大)

第二章

线性表华电计算机系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张华

7889

788099002李军

6756

767699003王小明

9087

888999050刘末

86

6778

学号

姓名程设数结

…

…99001张华

7889

99002李军

6756

767699003王小明

9087

888999050刘末

86

6778

学号

姓名程设数结

…

…

87

(2)除了第一个元素与最后一个元素,序列中任何一个元素有且仅有一个直接前驱元素,有且仅有一个直接后继元素。

线性表的逻辑结构为线性结构

(1)当1<i<n时，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(Var

La: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_la<>Len_lbthenReturn(False)else[Fork:=1toLen_laDo[x:=Get(La,k);m:=Locate(Lb,x);ifm=0thenReturn(False);]]Return(True);End;Pasal语言实现

华电计算机系int

Compare

(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空闲

a1

a2

…

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

}begin

if(i<1)or(i>n+1)thenError(‘插入的位置非法’)elseprodecureInsert(Var

L: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

//begin

if(i<1)or(i>n)then

callERROR(‘没有这个元素!’)else[

]

ProcedureDelete(Var

L: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/n

Tds=

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;begin

fori:=1tondoif(L[i]=item)thenreturn(i)；//查找成功,

返回信息i//return(0)；//查找失败,

返回信息0//

end；序号12345678元素283143781114252028x华电计算机系算法C语言实现

int

Locatesql(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;{若A<B,则返回-1;若A=B,则返回0;若A>B,则返回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语言实现)例1int

Compare(Linear_listA,Linear_listB){//若A<B,则返回-1；若A=B,则返回0；若A>B,则返回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

…

a2

a1

若给定栈S=(a1,a2,…,an),则a1是栈底元素，an是栈顶元素，表中元素按a1,a2,…,an顺序进栈，按an,…,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出(FILO)。华电计算机系栈的举例1)装乒乓球的圆筒，装的时候是第一个装入的球放在最底下，第二在它的上面，一个个依次装入，取出时最后装入的那个球却被第一个取走。2)假定有一个问题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

…

a2

a1华电计算机系…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为栈的最大容量}Begin

iftop=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为两个栈的共享空间}Begin

else[Caseiof

1:[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/8

48

76/8

0

6商除以8商余数已知一个无符号十进制整数num，写一算法，依次输出其对应的八进制数的各位数字。例170648/8

6

0华电计算机系

procedurechange(num);begintop:=0;算法NorthChinaElectricPowerUniversitywhile(num

0)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后

r2

r1

调A3后

r1

返回A2后

返回A1后

栈的应用举例：

例3递归和栈

计算阶乘的递归算法如下：pascal实现

functionf(n):integer;begin

if(n=0)thenreturn(1)elsereturn(n*f(n-1));end;n!=1n=0n*(n-1)!n>0

假设求华电计算机系

计算阶乘的递归算法如下：C语言实现

int

f(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。解决这种现象有两种方法：

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)；}}bool

InQueue(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语言实现

例: