数据结构
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
第二章 线性表
★ 线性表
★ 栈
★ 队列
North China Electric Power University
线性表的逻辑结构：
线性表是 0个或多个元素的有穷序列，通常可表示成 a1,a2,a3,…,ai,…,an(n≥0)
★ 线性表
n:线性表的表长
n=0时称为空表
n≥ 1时,a1称为第一个元素,an称为最后一个元素
ai称为 ai+1的前驱,ai+1称为 ai的后继,i称为序号或索引特点,除第一个和最后一个元素外，每个元素有且只有一个直接前驱和一个直接后继。
North China Electric Power University
North China Electric Power University
线性表的例子：
例 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.一本书可以看成是一个线性表，每一页是一数据元素例 4.学生的学籍档案构成一个线性表学号 姓名 入学总分 数学分析 程序设计 离散数学 …
981201 王国强 435 88 65 82 …
981202 赵济实 429 85 90 78 …
981203 刘晔 512 97 88 95 …
981204 叶桑林 488 93 91 85 …
… … … … … … …
981250 田华月 501 89 95 87 …
数据元素数据项线性表的基本运算：
North China Electric Power University
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。
线性表的其它运算,
如求任一元素的直接前驱或直接后继；合并两个线性表；
线性表的拆分；线性表的复制；对线性表按照值的大小进行排序等操作。
North China Electric Power University
线性表基本运算的应用示例,
例 1.设有两个线性表 La和 Lb，现将 La 和 Lb合并成一个新表存于 La中。
Procedure Union(Var La:Linear_list ; Lb:Linear_list);
{将所有在 Lb中存在而在 La中不存在的数据元素插入到 La中 }
Begin
n:=Length(La);
For i:=1 to Length(Lb) Do
[ x:=Get(Lb,i);
k:=Locate(La,x);
if k=0 then
[ Insert(La,n+1,x);
n:=n+1;
]
]
End;
例 2.判断两个集合 A和 B是否相等。
Function Compare(La:Linear_list ; Lb:Linear_list):Boolean;
{若 La和 Lb不仅长度相等，而且所含元素也相同则返回 True}
Begin
Len_la:=Length(La);
Len_lb:=Length(Lb);
if Len_la< >Len_lb then Return(False)
else
[ For k:=1 to Len_la Do
[ x:=Get(La,k);
m:=Locate(Lb,x);
if m=0 then Return(False);
]
]
Return(True);
End;
North China Electric Power University
North China Electric Power University
线性表的顺序存储,用一块连续的存储单元依次存放线性表的各个元素。
内存状态存储地址 元素在线性表中的次序
b=Loc(a1)
b+c
b+(i-1)*c
b+ (n-1)*c
b+(max-1)*c
1
2
i
n
空闲
a1
a2
…
ai
…
an
顺序存储的线性表的寻址公式：
顺序存储的优点：
1.可以随机存取
2.空间利用率高
3.结构简单
Loc(ai)=Loc(a1)+(i-1)*c 1≤i≤n
Loc(a1)为线性表的第一个元素 a1的存储地址
c为每个元素所占的存储单元线性表的顺序存储可以借用数组类型来实现
North China Electric Power University
线性表的基本运算的实现：
1)在线性表 L的第 i个位置上插入一个新元素 x
插入前,元素序号 1 2 3 4 5 6 7 8
插入 27
插入后,元素序号 1 2 3 4 5 6 7 8 9
主要操作,1.将第 i到 n个元素依次后移一个位置
2.将新元素 x放到线性表的第 i个位置上
3.将线性表的表长由 n修改为 n+1
28 31 43 7811 14 2520
28 31 43 7811 14 2520 27
North China Electric Power University
在线性表 L的第 i个位置上插入新元素 x的算法
Procedure Insert(Var L:Linear_list ; x:ElemType);
Begin
if (i<1) or (i>n+1) then Error(‘插入的位置非法’ )
else
[ For j:=n DownTo i Do
L[j+1]:=L[j];
L[i]:=x;
n:=n+1;
]
End;
在一个长度为 n的线性表中插入一元素时需移动元素的平均次数为
Ein = Σ Pj *(n-j+1)=n/2 (当 Pj =1/(n+1) j=1,2,… n,n+1)
1
n+1
算法的时间复杂性为 O(n)
North China Electric Power University
North China Electric Power University
2)删除线性表 L的第 i个元素删除前,元素序号 1 2 3 4 5 6 7 8
删除插入后,元素序号 1 2 3 4 5 6 7
主要操作,1.将第 i+1到 n个元素依次前移一个位置
3.将线性表的表长由 n修改为 n-1
28 31 43 7811 14 2520
43 7811 14 2820 31
North China Electric Power University
删除线性表 L的第 i个元素的算法
Procedure Delete(Var L:Linear_list ; i:Integer);
Begin
if (i<1) or (i>n) then Error(‘没有这个元素’ )
else
[ For j:=i+1 To n Do
L[j-1]:=L[j];
n:=n-1;
]
End;
在一个长度为 n的线性表中删除一元素时需移动元素的平均次数为
Ede = Σ Pj *(n-j)=(n-1)/2 (当 Pj =1/n j=1,2,… n)
算法的时间复杂性为 O(n)
3)定位运算：求 x在线性表 L中的最小序号元素序号 1 2 3 4 5 6 7 8
28 31 43 7811 14 2520
28x
Function Locate(L:Linear_list ; x:ElemType):Integer;
{在 L中查找第一个值和 x相等的元素，若存在，返回该元素 L中的序号，否则返回 0}
Begin
i:=1;
while (i≤n) and (L[i]< >x) Do
i:=i+1;
if (i<n) then Return(i)
else Return(0);
End;
North China Electric Power University
North China Electric Power University
4)顺序表的其他算法举例例 1.按照字典序比较两个线性表 A和 B的大小
Function Compare(A:Linear_list ;B:Linear_list):Integer;
{若 A<B,则返回 -1;若 A=B,则返回 0;若 A>B,则返回 1}
Begin
j:=1;
while (j<=Length(A)) and (j<=Length(B)) Do
[ if Get(A,j)<Get(B,j) then Return(-1)
else if Get(A,j)>Get(B,j) then Return(1)
else j:=j+1;
]
if (Length(A)=Length(B) then Return(0)
else if (Length(A)<Length(B) then Return(-1)
else Return(1);
End;
North China Electric Power University
例 2.归并两个“其数据元素按值非递减有序”的线性表 La,
Lb,使求得的线性表 Lc也具有同样的特性。
Procedure Merge(La,Lb:Linear_list ;Var Lc:Linear_list);
Begin
Initial(Lc); i:=1 ;j:=1 ;k:=0;
Len_la:=Length(La); Len_lb:=Length(Lb);
while (i<=Len_la) and (j<=Len_lb) Do
[ if (Get(La,i)<=Get(Lb,j))
then [k:=k+1;Insert(Lc,k,Get(La,i));i:=i+1;]
else [k:=k+1;Insert(Lc,k,Get(Lb,j));j:=j+1;]
]
while (i<=Len_la) Do
[k:=k+1;Insert(Lc,k,Get(La,i));i:=i+1;]
while (j<=Len_lb) Do
[k:=k+1;Insert(Lc,k,Get(Lb,j));j:=j+1;]
End;
已知长度为 n 的线性表 A采用顺序存储结构，并且数据元素按值大小非递减排列。 写一算法，删除线性表中值相同的多余元素。
例 3
procedure Del( A,n );
Begin
i:=1;
while (i<n) do
[ if (A[i]?A[i+1]) then
i:=i+1
else
[ for j:=i+1 to n do
A[j?1]:=A[j]
n:=n–1; ]
]
End;
North China Electric Power University
顺序存储的缺点：
1.需要一片地址连续的存储空间 ;
2.插入和删除元素时不方便，大量的时间用在元素的搬家上 ;
3.在预分配存储空间时，可能造成空间的浪费 ;
4.表的容量难以扩充。
North China Electric Power University
解决的方案：
1.对线性表的插入和删除运算进行限定
2.采用其它的存储结构 (链式存储 )
★ 栈
North China Electric Power University
栈的逻辑结构栈：所有的插入和删除都只能在表尾（栈顶）进行的线性表。允许进行插入和删除操作的一端叫栈顶，不允许插入和删除的一端叫栈底。
没有元素的栈叫空栈。
a1栈底栈顶插入 删除若给定栈 S=(a1,a2,…,an),则 a1
是栈底元素,an是栈顶元素，表中元素按 a1,a2,…,an顺序进栈，按
an,…,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出
(FILO)。
an
…
a2
a1
North China Electric Power University
栈的举例,
1)装乒乓球的圆筒，装的时候是第一个装入的球放在最底下，第二在它的上面，一个个依次装入，取出时最后装入的那个球却被第一个取走 。
2)假定有一个问题 P,它的解决依赖于两个子问题 A和 E
的解决，而子问题 A的解决又依赖于子问题 B和 C的解决，问题 C的解决依赖于问题 D的解决。
P
A E
B C
D
1
2
3
4 5
6 7
8
10
11
12
9
解决问题的步骤如左图所示，红色的箭头表示进入这个问题（或者说子问题进栈），
绿色的箭头表示问题已经解决
（或子问题出栈）。
栈一般用来容纳被接受了的而还没有进行处理的信息。
North China Electric Power University
栈的基本运算：
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:
top
S[1]
S[2]
S[i]
S[top]
maxsize
S：表示栈
S[1]:表示第 1个进栈的元素
S[2]:表示第 2个进栈的元素
S[i]:表示第 i个进栈的元素
S[top]:表示栈顶元素
top=0:表示栈空
top=maxsize:表示栈满空闲空间
…
…
ai
…
a2
a1
North China Electric Power University
栈的基本运算在顺序存储结构上的实现：
1)PushStack(S,x):将元素 x压入到栈 S中。
Procedure PushStack(S,x);{m为栈的最大容量 }
Begin
if top=m then Error(‘栈已满’ )
else [top:=top+1;S[top]:=x;]
End;
2)PopStack(S):当栈 S不空时弹出栈顶元素。
Procedure PopStack(S);{m为栈的最大容量 }
Begin
if top=0 then Error(‘栈空’ )
else [y:=S[top]; top:=top-1;]
End;
上面两个元素的时间复杂性均为 O(1)，压栈和退栈时不需移动元素
North China Electric Power University
双重栈
STACK[1,M]
top[1],top[2] 分别为第 1个与第 2个栈的栈顶元素的指针。
插入：
当 i=1时，将 item 插入第 1个栈，
当 i=2时，将 item 插入第 2个栈。
可用空间
1 2 3 … M
第 1 个栈 第 2 个栈
top[1] top[2]
初始条件：
top[1]=0 top[2]=m+1
1 2 3 … M
第 1 个栈 第 2 个栈可用空间
1 2 3 … M
第 1 个栈 第 2 个栈
top[1] top[2]
top[1] top[2]
栈满的条件是
top[1]=top[2]–1
top[1]:=top[1]+1
STACK[top[1]]:=item
i=1
top[2]:=top[2]–1
STACK[top[2]]:=item
i=2
North China Electric Power University
North China Electric Power University
双重栈的基本运算的实现：
1)PushStack(S,i,x):将元素 x压入到第 i个栈中。
Procedure PushStack(S,i,x);{S为两个栈的共享空间 }
Begin
if top[2]=top[1]+1 then Error(‘栈已满’ )
else [ Case i of
1:[ top[i]:=top[i]+1; S[top[i]]:=x;]
2:[ top[i]:=top[i]-1; S[top[i]]:=x;]
EndCase; ]
End;
2)PopStack(S,i):当第 i个栈不空时弹出其栈顶元素。
Procedure PopStack(S,i);{S为两个栈的共享空间 }
Begin
Case i of
1:[ if top[i]=0 then Error(‘栈空’ ) else top[i]=top[i]-1;]
2:[ if top[i]=m+1 then Error(‘栈空’ ) else top[i]=top[i]+1;]
EndCase;
End;
North China Electric Power University
栈的应用举例：
num = 39110 6078
391/8 48 7
6/8 0 6
商除以 8 商 余数已知一个无符号十进制整数 num，写一算法，依次输出其对应的八进制数的各位数字。
例 1
7
0
6
48/8 6 0
procedure change( num );
begin
top:=0
while (num? 0) do
[ top:=top+1;
Stack[top]:=num Mod 8; // 余数进栈 //
num:= num div 8;
]
while (top? 0) do
[ print( Stack[top] );
top:=top-1; // 退栈 //
]
End
算法顺序存储结构的堆栈
North China Electric Power University
North China Electric Power University
例 2.扩号匹配问题：假设表达式中有两种扩号,圆括号和方括号,即 ([]())或 [([][])]为正确的格式,[())等为不正确的格式，写一个算法检验表达式中的扩号是否匹配。
分析：检验扩号是否匹配可以用,期待的紧迫程度,
这个概念来描述。例如考虑下面的扩号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
分析可能出现的不匹配的情况：
1)到来的右扩号并非所期待的；
2)到来的是,不速之客,;
3)直到结束，也没有到来所,期待,的；
Function matching(exp:String):Boolean;
{检验表达式中的扩号是否匹配,若匹配返回 True,否则为 False}
Begin
State:=1;InitStack(S);
while (i<=Length(exp)) and ( State=1) Do
[ Case exp[i] of
‘[’,‘(’,[ PushStack(S,exp[i];]
‘)’,[ if Not(EmptyStack(S) and TopStack(S)= ‘(’
then PopStack(S) else State:=0; ]
‘]’,[ if Not(StackEmpty(S) and TopStack(S)= ‘[’
then PopStack(S) else State:=0; ]
EndCase;
i:=i+1;
]
if (State=1) and (EmptyStack(S)) then Return(True)
else Return(False);
End;
North China Electric Power University
North China Electric Power University
★ 队列队列：所有的插入在表的一端进行，所有的删除在表的另一端进行的线性表。允许插入的一端称队尾，
允许删除的一端称为队头。不允许插入和删除的一端叫栈底。没有元素的对叫空队。队列是一种先进先出的线性表。
a1,a2,a3…,,an 进队出队队头 队尾队列常用在操作系统中，最典型的例子是作业排队。在允许多道程序运行的系统中，输出通道就一个，而在计算机中运行的程序有多个，若多个程序的运行结果都需要输出，那就要按请求输出的先后次序排队，逐个输出。
队列的逻辑结构
North China Electric Power University
输出输出通道
… … 作业排队每当通道传输完毕可以接受新的传输任务时，队头的作业必需从队列中退出，做输出操作，凡是申请输出的作业都从队尾进入队列。
队列的顺序存储结构可用向量 q[0..m-1]存储队列中的元素，队列所允许的最大容量是 m,如图：
0
1
2
3
…
m-1 向量 q:表示队列头指针 front:总是指向队头的前一个位置尾指针 rear:总是指向队列的最后一个元素队空,front=rear (下溢 )
队满,rear=m-1 (上溢 )
North China Electric Power University
下面我们举一个例子实际做一下,m=5
0
1
2
3
4
初始状态
rear=fornt=
0
1
2
3
4
加入 A元素
rear
front
A 0
1
2
3
4
加入 B元素
rear
front
A
B
0
1
2
3 D
4
加入 E元素
rear
front
B
C
E
A0
1
2
3 D
4
加入 D元素
rear
front
A
B
C
0
1
2
3
4
删除 ABC元素
rear
front
A
B
C
0
1
2
3
4
加入 C元素
rear
front
A
B
C
North China Electric Power University
此时，再想加入一个元素也加不进去了，我们说队列已经满了,rear=m-1。这里存在一个问题，实际上在前页的图中，队列并不是真正的溢出，但 rear=m-1，又说明队列满，新元素插不进去，这种情况称作假溢出，真正的队满是元素占满队列的所有空间。
解决这种现象有两种方法：
1)当发生假溢出时，我们把队列中的所有元素向排头方向移动，腾出新元素的位置，将新元素加入。此种方法适宜于元素少时，当队列中元素较多时，则得不偿失。
2)采用取模运算。我们把 q[0]和 q[m-1]捏在一起，就形成了一个环。
初始状态：
头指针,在顺时针方向上落后于队列中第一个元素一个位置。
尾指针,指向最后加入的元素的位置。
North China Electric Power University
q[0] q[m-1]
rear
front
0
12
3
4
初态 r=f,队空
0
12
3
4 rear
front
加入 A
A
0
12
3
4
rear
front
A
B
A
BC
0
12
3
4
rear
front
加入 B加入 C
North China Electric Power University
A
BC
0
12
3
4
rear
front
删除 ABC
D 0
12
3
4rear
front
加入 D
front
rear
0
12
3
4D
E
加入 E
0
12
3
4 rear
front
D
E
F
加入 F
0
12
3
4
rearfront
D
E
F
GH
加入 G,H
r=f 队满
North China Electric Power University
从以上分析可以看出，循环队列的队空与队满条件相同，都是 front=rear,这样我们区分不出队列到底是空还是满，对此有两种解决方法。
1)设一个标志位区分队列是空还是满。 (队空置 0，队满置 1)。但这种方法，这标志位以及对标志位的判断都需要花费机器空间和时间。
2)不设置标志位，而把尾指针从后面追上头指针，即 (rear+1)
Mod m=front，看作队满。很明显，这种方法浪费一个工作单元，
但它是以一个工作单元的损失而换来时间上的节约。
队列基本运算
1.InitQueue(Q):初始化队列 Q为一空队。
2.InQueue(Q,x):把元素 x插入队列 Q中。
3.OutQeue(Q):删除队列 Q的队首元素。
4.GetHead(Q):取得队列 Q的队首元素。
5.EmptyQueue(Q):判定 Q是否为一空队，如果为空，则返回真。
North China Electric Power University
1)循环队列的插入,
Procedure InQueue(Q,x); {在循环队列中 q插入元素 x}
Begin
if (rear+1) mod m=front
{m为循环队列的最大容量 }
then Error(‘Overflow’)
{ 队列满上溢 }
else [ rear:=(rear+1) mod m;
Q[rear],=x；
]
End;
队列的基本运算在顺序存储结构上的实现
2)循环队列的删除：
若队头等于队尾，则队空返回。否则队头加 1，
取模运算，然后将队头所指的元素送往 y单元。
Procedure OutQueue(Q);
{在循环队列 Q中删除队头元素 }
Begin
if front=rear then Error(‘队列空返回’ )
else
[ front:=(front+1) mod m;
y:= Q[front];
]
End;
North China Electric Power University
例 假设以一维数组 sequ[0..m-1]存储循环队列的元素，若要使这
m个分量都要得到应用，则另设一标志 tag,以 tag为 0或 1来区分头指针和尾指针相等时队列的状态为“空”或“满”,编写此队列的入队和出队算法。
数据结构类型定义如下：
Const m=100;
Type sequeue=Record
sequ:Array[0..m-1] of ElemType;
front,reat:Integer;
tag:Integer;
End;
插入算法：
Procedure InQueue(Q:sequeue;x:ElemType);
Begin
if(Q.front=Q.rear) and (Q.tag=1)
[ Writeln(‘OverFlow’);Return;]
North China Electric Power University
Q.rear:=(Q.rear+1) mod m;
Q.sequ[Q.rear]:=x;
if Q.rear=Q.front then Q.tag:=1;
End;
删除算法：
Function OutQueue(Q:sequeue):ElemType;
Begin
if (Q.front=Q.rear) and (Q.tag=0)
then [Writeln(‘UnderFlow’);Return;]
x:=Q.sequ[Q.front];
Q.front:=(Q.front+1) mod m;
if Q.rear=Q.front then Q.tag:=0;
Return(x);
End;
North China Electric Power University
North China Electric Power University
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
第二章 线性表
★ 线性表
★ 栈
★ 队列
North China Electric Power University
线性表的逻辑结构：
线性表是 0个或多个元素的有穷序列，通常可表示成 a1,a2,a3,…,ai,…,an(n≥0)
★ 线性表
n:线性表的表长
n=0时称为空表
n≥ 1时,a1称为第一个元素,an称为最后一个元素
ai称为 ai+1的前驱,ai+1称为 ai的后继,i称为序号或索引特点,除第一个和最后一个元素外，每个元素有且只有一个直接前驱和一个直接后继。
North China Electric Power University
North China Electric Power University
线性表的例子：
例 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.一本书可以看成是一个线性表，每一页是一数据元素例 4.学生的学籍档案构成一个线性表学号 姓名 入学总分 数学分析 程序设计 离散数学 …
981201 王国强 435 88 65 82 …
981202 赵济实 429 85 90 78 …
981203 刘晔 512 97 88 95 …
981204 叶桑林 488 93 91 85 …
… … … … … … …
981250 田华月 501 89 95 87 …
数据元素数据项线性表的基本运算：
North China Electric Power University
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。
线性表的其它运算,
如求任一元素的直接前驱或直接后继；合并两个线性表；
线性表的拆分；线性表的复制；对线性表按照值的大小进行排序等操作。
North China Electric Power University
线性表基本运算的应用示例,
例 1.设有两个线性表 La和 Lb，现将 La 和 Lb合并成一个新表存于 La中。
Procedure Union(Var La:Linear_list ; Lb:Linear_list);
{将所有在 Lb中存在而在 La中不存在的数据元素插入到 La中 }
Begin
n:=Length(La);
For i:=1 to Length(Lb) Do
[ x:=Get(Lb,i);
k:=Locate(La,x);
if k=0 then
[ Insert(La,n+1,x);
n:=n+1;
]
]
End;
例 2.判断两个集合 A和 B是否相等。
Function Compare(La:Linear_list ; Lb:Linear_list):Boolean;
{若 La和 Lb不仅长度相等，而且所含元素也相同则返回 True}
Begin
Len_la:=Length(La);
Len_lb:=Length(Lb);
if Len_la< >Len_lb then Return(False)
else
[ For k:=1 to Len_la Do
[ x:=Get(La,k);
m:=Locate(Lb,x);
if m=0 then Return(False);
]
]
Return(True);
End;
North China Electric Power University
North China Electric Power University
线性表的顺序存储,用一块连续的存储单元依次存放线性表的各个元素。
内存状态存储地址 元素在线性表中的次序
b=Loc(a1)
b+c
b+(i-1)*c
b+ (n-1)*c
b+(max-1)*c
1
2
i
n
空闲
a1
a2
…
ai
…
an
顺序存储的线性表的寻址公式：
顺序存储的优点：
1.可以随机存取
2.空间利用率高
3.结构简单
Loc(ai)=Loc(a1)+(i-1)*c 1≤i≤n
Loc(a1)为线性表的第一个元素 a1的存储地址
c为每个元素所占的存储单元线性表的顺序存储可以借用数组类型来实现
North China Electric Power University
线性表的基本运算的实现：
1)在线性表 L的第 i个位置上插入一个新元素 x
插入前,元素序号 1 2 3 4 5 6 7 8
插入 27
插入后,元素序号 1 2 3 4 5 6 7 8 9
主要操作,1.将第 i到 n个元素依次后移一个位置
2.将新元素 x放到线性表的第 i个位置上
3.将线性表的表长由 n修改为 n+1
28 31 43 7811 14 2520
28 31 43 7811 14 2520 27
North China Electric Power University
在线性表 L的第 i个位置上插入新元素 x的算法
Procedure Insert(Var L:Linear_list ; x:ElemType);
Begin
if (i<1) or (i>n+1) then Error(‘插入的位置非法’ )
else
[ For j:=n DownTo i Do
L[j+1]:=L[j];
L[i]:=x;
n:=n+1;
]
End;
在一个长度为 n的线性表中插入一元素时需移动元素的平均次数为
Ein = Σ Pj *(n-j+1)=n/2 (当 Pj =1/(n+1) j=1,2,… n,n+1)
1
n+1
算法的时间复杂性为 O(n)
North China Electric Power University
North China Electric Power University
2)删除线性表 L的第 i个元素删除前,元素序号 1 2 3 4 5 6 7 8
删除插入后,元素序号 1 2 3 4 5 6 7
主要操作,1.将第 i+1到 n个元素依次前移一个位置
3.将线性表的表长由 n修改为 n-1
28 31 43 7811 14 2520
43 7811 14 2820 31
North China Electric Power University
删除线性表 L的第 i个元素的算法
Procedure Delete(Var L:Linear_list ; i:Integer);
Begin
if (i<1) or (i>n) then Error(‘没有这个元素’ )
else
[ For j:=i+1 To n Do
L[j-1]:=L[j];
n:=n-1;
]
End;
在一个长度为 n的线性表中删除一元素时需移动元素的平均次数为
Ede = Σ Pj *(n-j)=(n-1)/2 (当 Pj =1/n j=1,2,… n)
算法的时间复杂性为 O(n)
3)定位运算：求 x在线性表 L中的最小序号元素序号 1 2 3 4 5 6 7 8
28 31 43 7811 14 2520
28x
Function Locate(L:Linear_list ; x:ElemType):Integer;
{在 L中查找第一个值和 x相等的元素，若存在，返回该元素 L中的序号，否则返回 0}
Begin
i:=1;
while (i≤n) and (L[i]< >x) Do
i:=i+1;
if (i<n) then Return(i)
else Return(0);
End;
North China Electric Power University
North China Electric Power University
4)顺序表的其他算法举例例 1.按照字典序比较两个线性表 A和 B的大小
Function Compare(A:Linear_list ;B:Linear_list):Integer;
{若 A<B,则返回 -1;若 A=B,则返回 0;若 A>B,则返回 1}
Begin
j:=1;
while (j<=Length(A)) and (j<=Length(B)) Do
[ if Get(A,j)<Get(B,j) then Return(-1)
else if Get(A,j)>Get(B,j) then Return(1)
else j:=j+1;
]
if (Length(A)=Length(B) then Return(0)
else if (Length(A)<Length(B) then Return(-1)
else Return(1);
End;
North China Electric Power University
例 2.归并两个“其数据元素按值非递减有序”的线性表 La,
Lb,使求得的线性表 Lc也具有同样的特性。
Procedure Merge(La,Lb:Linear_list ;Var Lc:Linear_list);
Begin
Initial(Lc); i:=1 ;j:=1 ;k:=0;
Len_la:=Length(La); Len_lb:=Length(Lb);
while (i<=Len_la) and (j<=Len_lb) Do
[ if (Get(La,i)<=Get(Lb,j))
then [k:=k+1;Insert(Lc,k,Get(La,i));i:=i+1;]
else [k:=k+1;Insert(Lc,k,Get(Lb,j));j:=j+1;]
]
while (i<=Len_la) Do
[k:=k+1;Insert(Lc,k,Get(La,i));i:=i+1;]
while (j<=Len_lb) Do
[k:=k+1;Insert(Lc,k,Get(Lb,j));j:=j+1;]
End;
已知长度为 n 的线性表 A采用顺序存储结构，并且数据元素按值大小非递减排列。 写一算法，删除线性表中值相同的多余元素。
例 3
procedure Del( A,n );
Begin
i:=1;
while (i<n) do
[ if (A[i]?A[i+1]) then
i:=i+1
else
[ for j:=i+1 to n do
A[j?1]:=A[j]
n:=n–1; ]
]
End;
North China Electric Power University
顺序存储的缺点：
1.需要一片地址连续的存储空间 ;
2.插入和删除元素时不方便，大量的时间用在元素的搬家上 ;
3.在预分配存储空间时，可能造成空间的浪费 ;
4.表的容量难以扩充。
North China Electric Power University
解决的方案：
1.对线性表的插入和删除运算进行限定
2.采用其它的存储结构 (链式存储 )
★ 栈
North China Electric Power University
栈的逻辑结构栈：所有的插入和删除都只能在表尾（栈顶）进行的线性表。允许进行插入和删除操作的一端叫栈顶，不允许插入和删除的一端叫栈底。
没有元素的栈叫空栈。
a1栈底栈顶插入 删除若给定栈 S=(a1,a2,…,an),则 a1
是栈底元素,an是栈顶元素，表中元素按 a1,a2,…,an顺序进栈，按
an,…,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出
(FILO)。
an
…
a2
a1
North China Electric Power University
栈的举例,
1)装乒乓球的圆筒，装的时候是第一个装入的球放在最底下，第二在它的上面，一个个依次装入，取出时最后装入的那个球却被第一个取走 。
2)假定有一个问题 P,它的解决依赖于两个子问题 A和 E
的解决，而子问题 A的解决又依赖于子问题 B和 C的解决，问题 C的解决依赖于问题 D的解决。
P
A E
B C
D
1
2
3
4 5
6 7
8
10
11
12
9
解决问题的步骤如左图所示，红色的箭头表示进入这个问题（或者说子问题进栈），
绿色的箭头表示问题已经解决
（或子问题出栈）。
栈一般用来容纳被接受了的而还没有进行处理的信息。
North China Electric Power University
栈的基本运算：
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:
top
S[1]
S[2]
S[i]
S[top]
maxsize
S：表示栈
S[1]:表示第 1个进栈的元素
S[2]:表示第 2个进栈的元素
S[i]:表示第 i个进栈的元素
S[top]:表示栈顶元素
top=0:表示栈空
top=maxsize:表示栈满空闲空间
…
…
ai
…
a2
a1
North China Electric Power University
栈的基本运算在顺序存储结构上的实现：
1)PushStack(S,x):将元素 x压入到栈 S中。
Procedure PushStack(S,x);{m为栈的最大容量 }
Begin
if top=m then Error(‘栈已满’ )
else [top:=top+1;S[top]:=x;]
End;
2)PopStack(S):当栈 S不空时弹出栈顶元素。
Procedure PopStack(S);{m为栈的最大容量 }
Begin
if top=0 then Error(‘栈空’ )
else [y:=S[top]; top:=top-1;]
End;
上面两个元素的时间复杂性均为 O(1)，压栈和退栈时不需移动元素
North China Electric Power University
双重栈
STACK[1,M]
top[1],top[2] 分别为第 1个与第 2个栈的栈顶元素的指针。
插入：
当 i=1时，将 item 插入第 1个栈，
当 i=2时，将 item 插入第 2个栈。
可用空间
1 2 3 … M
第 1 个栈 第 2 个栈
top[1] top[2]
初始条件：
top[1]=0 top[2]=m+1
1 2 3 … M
第 1 个栈 第 2 个栈可用空间
1 2 3 … M
第 1 个栈 第 2 个栈
top[1] top[2]
top[1] top[2]
栈满的条件是
top[1]=top[2]–1
top[1]:=top[1]+1
STACK[top[1]]:=item
i=1
top[2]:=top[2]–1
STACK[top[2]]:=item
i=2
North China Electric Power University
North China Electric Power University
双重栈的基本运算的实现：
1)PushStack(S,i,x):将元素 x压入到第 i个栈中。
Procedure PushStack(S,i,x);{S为两个栈的共享空间 }
Begin
if top[2]=top[1]+1 then Error(‘栈已满’ )
else [ Case i of
1:[ top[i]:=top[i]+1; S[top[i]]:=x;]
2:[ top[i]:=top[i]-1; S[top[i]]:=x;]
EndCase; ]
End;
2)PopStack(S,i):当第 i个栈不空时弹出其栈顶元素。
Procedure PopStack(S,i);{S为两个栈的共享空间 }
Begin
Case i of
1:[ if top[i]=0 then Error(‘栈空’ ) else top[i]=top[i]-1;]
2:[ if top[i]=m+1 then Error(‘栈空’ ) else top[i]=top[i]+1;]
EndCase;
End;
North China Electric Power University
栈的应用举例：
num = 39110 6078
391/8 48 7
6/8 0 6
商除以 8 商 余数已知一个无符号十进制整数 num，写一算法，依次输出其对应的八进制数的各位数字。
例 1
7
0
6
48/8 6 0
procedure change( num );
begin
top:=0
while (num? 0) do
[ top:=top+1;
Stack[top]:=num Mod 8; // 余数进栈 //
num:= num div 8;
]
while (top? 0) do
[ print( Stack[top] );
top:=top-1; // 退栈 //
]
End
算法顺序存储结构的堆栈
North China Electric Power University
North China Electric Power University
例 2.扩号匹配问题：假设表达式中有两种扩号,圆括号和方括号,即 ([]())或 [([][])]为正确的格式,[())等为不正确的格式，写一个算法检验表达式中的扩号是否匹配。
分析：检验扩号是否匹配可以用,期待的紧迫程度,
这个概念来描述。例如考虑下面的扩号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
分析可能出现的不匹配的情况：
1)到来的右扩号并非所期待的；
2)到来的是,不速之客,;
3)直到结束，也没有到来所,期待,的；
Function matching(exp:String):Boolean;
{检验表达式中的扩号是否匹配,若匹配返回 True,否则为 False}
Begin
State:=1;InitStack(S);
while (i<=Length(exp)) and ( State=1) Do
[ Case exp[i] of
‘[’,‘(’,[ PushStack(S,exp[i];]
‘)’,[ if Not(EmptyStack(S) and TopStack(S)= ‘(’
then PopStack(S) else State:=0; ]
‘]’,[ if Not(StackEmpty(S) and TopStack(S)= ‘[’
then PopStack(S) else State:=0; ]
EndCase;
i:=i+1;
]
if (State=1) and (EmptyStack(S)) then Return(True)
else Return(False);
End;
North China Electric Power University
North China Electric Power University
★ 队列队列：所有的插入在表的一端进行，所有的删除在表的另一端进行的线性表。允许插入的一端称队尾，
允许删除的一端称为队头。不允许插入和删除的一端叫栈底。没有元素的对叫空队。队列是一种先进先出的线性表。
a1,a2,a3…,,an 进队出队队头 队尾队列常用在操作系统中，最典型的例子是作业排队。在允许多道程序运行的系统中，输出通道就一个，而在计算机中运行的程序有多个，若多个程序的运行结果都需要输出，那就要按请求输出的先后次序排队，逐个输出。
队列的逻辑结构
North China Electric Power University
输出输出通道
… … 作业排队每当通道传输完毕可以接受新的传输任务时，队头的作业必需从队列中退出，做输出操作，凡是申请输出的作业都从队尾进入队列。
队列的顺序存储结构可用向量 q[0..m-1]存储队列中的元素，队列所允许的最大容量是 m,如图：
0
1
2
3
…
m-1 向量 q:表示队列头指针 front:总是指向队头的前一个位置尾指针 rear:总是指向队列的最后一个元素队空,front=rear (下溢 )
队满,rear=m-1 (上溢 )
North China Electric Power University
下面我们举一个例子实际做一下,m=5
0
1
2
3
4
初始状态
rear=fornt=
0
1
2
3
4
加入 A元素
rear
front
A 0
1
2
3
4
加入 B元素
rear
front
A
B
0
1
2
3 D
4
加入 E元素
rear
front
B
C
E
A0
1
2
3 D
4
加入 D元素
rear
front
A
B
C
0
1
2
3
4
删除 ABC元素
rear
front
A
B
C
0
1
2
3
4
加入 C元素
rear
front
A
B
C
North China Electric Power University
此时，再想加入一个元素也加不进去了，我们说队列已经满了,rear=m-1。这里存在一个问题，实际上在前页的图中，队列并不是真正的溢出，但 rear=m-1，又说明队列满，新元素插不进去，这种情况称作假溢出，真正的队满是元素占满队列的所有空间。
解决这种现象有两种方法：
1)当发生假溢出时，我们把队列中的所有元素向排头方向移动，腾出新元素的位置，将新元素加入。此种方法适宜于元素少时，当队列中元素较多时，则得不偿失。
2)采用取模运算。我们把 q[0]和 q[m-1]捏在一起，就形成了一个环。
初始状态：
头指针,在顺时针方向上落后于队列中第一个元素一个位置。
尾指针,指向最后加入的元素的位置。
North China Electric Power University
q[0] q[m-1]
rear
front
0
12
3
4
初态 r=f,队空
0
12
3
4 rear
front
加入 A
A
0
12
3
4
rear
front
A
B
A
BC
0
12
3
4
rear
front
加入 B加入 C
North China Electric Power University
A
BC
0
12
3
4
rear
front
删除 ABC
D 0
12
3
4rear
front
加入 D
front
rear
0
12
3
4D
E
加入 E
0
12
3
4 rear
front
D
E
F
加入 F
0
12
3
4
rearfront
D
E
F
GH
加入 G,H
r=f 队满
North China Electric Power University
从以上分析可以看出，循环队列的队空与队满条件相同，都是 front=rear,这样我们区分不出队列到底是空还是满，对此有两种解决方法。
1)设一个标志位区分队列是空还是满。 (队空置 0，队满置 1)。但这种方法，这标志位以及对标志位的判断都需要花费机器空间和时间。
2)不设置标志位，而把尾指针从后面追上头指针，即 (rear+1)
Mod m=front，看作队满。很明显，这种方法浪费一个工作单元，
但它是以一个工作单元的损失而换来时间上的节约。
队列基本运算
1.InitQueue(Q):初始化队列 Q为一空队。
2.InQueue(Q,x):把元素 x插入队列 Q中。
3.OutQeue(Q):删除队列 Q的队首元素。
4.GetHead(Q):取得队列 Q的队首元素。
5.EmptyQueue(Q):判定 Q是否为一空队，如果为空，则返回真。
North China Electric Power University
1)循环队列的插入,
Procedure InQueue(Q,x); {在循环队列中 q插入元素 x}
Begin
if (rear+1) mod m=front
{m为循环队列的最大容量 }
then Error(‘Overflow’)
{ 队列满上溢 }
else [ rear:=(rear+1) mod m;
Q[rear],=x；
]
End;
队列的基本运算在顺序存储结构上的实现
2)循环队列的删除：
若队头等于队尾，则队空返回。否则队头加 1，
取模运算，然后将队头所指的元素送往 y单元。
Procedure OutQueue(Q);
{在循环队列 Q中删除队头元素 }
Begin
if front=rear then Error(‘队列空返回’ )
else
[ front:=(front+1) mod m;
y:= Q[front];
]
End;
North China Electric Power University
例 假设以一维数组 sequ[0..m-1]存储循环队列的元素，若要使这
m个分量都要得到应用，则另设一标志 tag,以 tag为 0或 1来区分头指针和尾指针相等时队列的状态为“空”或“满”,编写此队列的入队和出队算法。
数据结构类型定义如下：
Const m=100;
Type sequeue=Record
sequ:Array[0..m-1] of ElemType;
front,reat:Integer;
tag:Integer;
End;
插入算法：
Procedure InQueue(Q:sequeue;x:ElemType);
Begin
if(Q.front=Q.rear) and (Q.tag=1)
[ Writeln(‘OverFlow’);Return;]
North China Electric Power University
Q.rear:=(Q.rear+1) mod m;
Q.sequ[Q.rear]:=x;
if Q.rear=Q.front then Q.tag:=1;
End;
删除算法：
Function OutQueue(Q:sequeue):ElemType;
Begin
if (Q.front=Q.rear) and (Q.tag=0)
then [Writeln(‘UnderFlow’);Return;]
x:=Q.sequ[Q.front];
Q.front:=(Q.front+1) mod m;
if Q.rear=Q.front then Q.tag:=0;
Return(x);
End;
North China Electric Power University
North China Electric Power University
