线性数据结构（二）
软件技术基础
主讲：仇国巍
西安交通大学计算机教学实验中心
2010年 5月 21日 2
教学内容及要求
内容,栈、队列、数组、串的
? 有关 概念
? 逻辑结构及特点
? 存储结构
? 有关 操作
要求,熟练 掌握上述内容及有关操作的算法
实现。
2010年 5月 21日 3
第 1章的
? 1.3 栈和队列 (P32 - P46)
? 1.4 串和数组 (P47 - P55)
本讲涉及课本内容
2010年 5月 21日 4
? 栈的定义
? 栈的顺序存储结构
? 栈的基本运算
? 多栈共享问题
? 栈的链式存储结构
? 栈的应用
一、栈结构
2010年 5月 21日 5
栈是只允许在同一端进行插入和删除操作
的特殊线性表。允许进行插入和删除操作的一
端称为 栈顶 (top)，另一端为 栈底 (bottom)；
栈底固定，而栈顶浮动；栈结构也称为后进先
出表（ LIFO）。
栈中元素个数为零时称为空栈。
1.1 栈的定义
2010年 5月 21日 6
1.2 栈的顺序存储结构
? 栈的顺序存储结构实际上是一维数组结构 。
? 这种栈又称为 —— 顺序栈 。
? 栈的操作只能在一端进行；即栈顶位置随进
栈和出栈而变化 。
? 顺序栈的 C语言描述为：
#define MAXSIZE 200
int stack[MAXSIZE];
int top = -1;
2010年 5月 21日 7
栈顶指针
? 栈顶指针,在栈操作过程中，有一个专
门的栈指针（习惯上称它为 TOP），指出
栈顶元素所在的位置。
? 栈空的条件,top = -1
? 栈满的条件,top = MAXSIZE-1
2010年 5月 21日 8
a1 a2 …… a n
栈底 栈顶
MAXSIZE
TOP
1.
top = -1
A B C2.
(空栈 ) top=3 (A,B,C进栈）
A B3.
top=2 (C出栈）
4,A B C D E F
top=MAXSIZE-1 (栈满）
1.3 栈操作举例
2010年 5月 21日 9
栈上溢, 栈空间是有限的，若栈已满，
在进行入栈操作时，就要产生上溢。
栈下溢,若栈空，再要执行出栈操作，
则会发生下溢。
栈溢出
2010年 5月 21日 10
? 进栈操作 (插入 ) Push（ Stack,x）
? 出栈操作 (删除 ） Pop（ Stack）
? 取栈顶元素 Gettop（ Stack）
? 置栈为空 Setnull（ Stack）
? 判定栈是否为空 Empty（ Stack）
1.4 栈的基本运算
2010年 5月 21日 11
例：进栈、出栈顺序问题
有 1,2,3三个元素依次入栈序 。 写出可
能的出栈序列 。
出栈序列 操作序列
1 2 3 s x s x s x
1 3 2 s x s s x x
2 1 3 s s x x s x
2 3 1 s s x s x x
3 2 1 s s s x x x
2010年 5月 21日 12
算法 1-8 进栈算法
? 算法步骤,
? step1
判别栈满否，若满，则显示栈溢出
信息，停止执行；否则，执行 step
2；
? Step2
栈顶指针 top上移 (加 1)；
? Step3
在 top所指的位置插入元素 x。
2010年 5月 21日 13
算法 1-8 进栈算法程序
push（ int x）
{ if（ top = = MAXSIZE -1）
{ printf（, 栈上溢 ！ \n”） ;
exit （ 1） ;
}
else
{
top + +； /* 栈指针加 1 */
stack [ top ] = x ； /* 元素 x进
栈 */
}
}
2010年 5月 21日 14
算法 1-9 出栈算法
? 算法步骤,
? step1 判别栈是否为空；若空，则
输出
栈下溢信息，并停止执行；
否则，
执行 step2；
? step2 弹出（删除）栈顶元素；
? step3 栈顶指针 top下移 (减 1)。
2010年 5月 21日 15
算法 1-9 出栈算法程序
pop（ ）
{ int x;
if( top = = -1）
{ printf(,栈下溢 \n”);
exit(1);
}
else
{ x = stack [ top ]；
top - - ； /* 栈顶指针 减
1*/
}
return x ；
}
2010年 5月 21日 16
4、多栈共享问题
? 如何充分利用栈空间，这是解决存储空间紧张
这样一个实际矛盾所要考虑的问题。
? 作为一种策略，就是多栈共享一个栈空间。具
体作法是：
? 对两栈共享情况来说，将两个栈底分别设
在两端,两个栈顶指针 top1和 top2相对中
间位置动态移动，两个栈之间的分界线是
不定的。
a.
b.
c.
top1 =0 top2=MAXSIZE
空栈
top1 top2
栈 1、栈 2均有若干元素
top1 top2
栈满的情况
2010年 5月 21日 17
5、栈的链式存储结构
? 由前面介绍的链表结构可知，链结
构操作灵活。对栈结构也是一样的。
? 顺序栈最多可用于 2个栈的共享，
对于更多的栈就难于表达了。
? 对于最大空间需要量事先不知的情
况，就不能使用顺序栈了。这时，
就需要采用链栈。
2010年 5月 21日 18
? 链栈存储结构的 C语言描述：
struct snode {
int data;
struct snode *link;
};
typedeef struct snode SNODE ;
? 链栈为空的条件,top = NULL
? 链栈为满的条件, t = NULL (t 为申请的
结点,为 NULL表示失败,)
链栈存储结构
2010年 5月 21日 19
链栈示意图
a1
a2
a3
^ 栈底
top 栈顶
…...
ai
2010年 5月 21日 20
算法 1-10 进栈操作
算法 1-10操作步骤,
? step1 申请一个链栈结点,若
t=NULL,则表示链满 ;否则,执行
step2 ;
? step2 在 top所指结点之前插入新
结点,并将 top指向新申请的结点 t。
2010年 5月 21日 21
算法 1-10 进栈操作程序
push(SNODE *top,int x)
{ SNODE *t;
t=(SNODE * )malloc(sizeof(SNODE));
if(t = = NULL )
{
pprintf(“内存中已无可用空间
\n”);
exit(1);
}
else
{ t -> data = x;
t -> link = top; top= t;
}
2010年 5月 21日 22
算法 1-11 出栈操作
算法 1-11操作步骤,
? step1 若链栈为空，则输出栈溢出信息；否
则，执行 step 2。
? step2 删除 top所指结点，并使 top 指向被
删除结点的后继结点。
? step 3 释放被删除结点的存储空间。
2010年 5月 21日 23
算法 1-11 出栈操作程序
pop (SNODE * top)
{ SNODE *p; int x;
if( top = = NULL )
{ printf(“栈溢出 \n”）；
exit(1);
}
else
{ p = top；
top = top-> link ；
x = p-> data ；
free(p) ;
}
}
2010年 5月 21日 24
6、栈的应用
? 表达式计算
? 子程序的嵌套调用
? 参数传递
? 键盘缓冲区
? 递归过程的实现
2010年 5月 21日 25
举例 1 表达式计算
? 计算表达式，首先要正确地定义运算规则：
? 先乘除、后加减
? 从左到右
? 先括号内，再括号外
? 为了让计算机能识别表达式，规定：
? 表达式由操作数（ Operand）和操作符
（ Operator）和定界符（ Delimiter）组成。
例如,#3*（ 7-2） #；
? 实际处理表达式是用两个栈结构 OPTR（算
符）和 OPND（操作数）加运算规则组成；
四
则
运
算
2010年 5月 21日 26
计算表达式算法步骤
? Step1 初始化，清空 OPTR和 OPND，将左
定界符压 OPTR栈；
? Step2 循环输入表达式中的每个字符
? 若输入操作数，则进 OPND栈
? 若是算符，则和 OPTR栈顶元素进行比较，按规
则进行相应操作
? 操作服从优先关系表
? Q1<Q2 Q1入 OPTR栈，再读入下一个元素
? Q1=Q2 Q1出 OPTR栈，脱括号，再读一个元素
? Q1>Q2 Q1出 OPTR栈，从 OPND中取两个数运算
? Step3 直到出现右定界符为止。
? 举例，计算,3*（ 7-2）
输入,3*（ 7-2） #
2010年 5月 21日 27
计算表达式的处理步骤
步骤 OPTR栈 OPND栈 输入字符 主要操作
1 # 3 PUSH（ OPND,3）
2 # 3 * PUSH（ OPTR，‘ *’）
3 # * 3 （ PUSH（ OPTR，‘（’）
4 #*（ 3 7 PUSH（ OPND,7）
5 #*（ 37 - PUSH（ OPTR，‘ -’）
6 #*（ - 37 2 PUSH（ OPND,2）
7 #*（ - 372 ） Operate（ 7，‘ -’,2）
8 #*（ 35 POP（ OPTR）
9 #* 35 # Operate（ 3，‘ *’,5）
10 # 15 RETURN（ GETTOP（ OPND））
2010年 5月 21日 28
举例 2（递归过程实现）
计算 5的阶乘（ 5！ =5X4X3X2X1）
{
if ( n = = 1) return (1);
else return ( n * f(n-1));
}
f(1)
f(2)
f(3)
f(4)
f(5)
top
1 f(1)=1
2*f(1) f(2)=2*f(1)
3*f(2) f(3)=3*f(2)
4*f(3) f(4)=4*f(3)
5*f(4) f(5)=5*f(4)
2010年 5月 21日 29
举例 3（子程序的嵌套调
用）
有一主程序 main（）调用子程序示意图
如下：
main sub1 sub2 sub3
end end end end
sub3
sub2
sub1
main
top
2010年 5月 21日 30
举例 4 N阶 Hanoi塔问题
? 假设有 X,Y,Z三座塔。在 X塔上插有 n个
直径大小不同、以小到大编号为 1,2,…,
n的圆盘。现要求将 X轴上的 n个圆盘移至 Z
塔上，并按同样顺序叠排。移动圆盘的规
则为：
1）每次只能移动一个圆盘；
2）圆盘可以插在 X,Y,Z的任意一个上；
3）任何时刻都不能将较大的圆盘压在较
小的圆盘之上。
注,这是一个递归问题,n阶问题可以
分解为 n圆盘和 n-1阶问题。
2010年 5月 21日 31
n=1的 Hanoi塔问题
X Y Z
2010年 5月 21日 32
n=2的 Hanoi塔问题
X Y Z
2010年 5月 21日 33
n=3的 Hanoi塔问题
X Y Z
变为 n-1问题
2010年 5月 21日 34
二、队列结构（ Queue）
? 队列的定义
? 队列的基本运算
? 队列的顺序存储结构
? 循环队列存储结构
? 队列的链式存储结构
? 队列的应用
2010年 5月 21日 35
1、队列定义
? 队列是一种特殊的线性表，它只允许在表的前
端（ front）进行删除操作，而在表的后端
（ rear）进行插入操作。
? 进行插入操作的端称为队尾，进行删除操作的
端称为队头。
? 队列中没有元素时，称为空队列。
? 队列具有先进先出（ FIFO）的特点。
? 队列空的条件,front = rear
? 队列满的条件,rear = MAXSIZE
a1 a2 … a n 入队插入出队删除
front rear
2010年 5月 21日 36
2、队列的操作
Setnull（ Q） 清空队列
Empty（ Q） 判别队列是否为空；空，
取,T.;
非空,取值为,F.。
Addqueue（ Q） 插入操作
Delqueue（ Q） 删除操作
Frontqueue（ Q）取队头元素
2010年 5月 21日 37
3、队列的顺序存储结构
C语言中顺序存储结构采用一维数组结构，
描述如下：
#define MAXSIZE n
int queue[MAXSIZ]；
int front,rear;
front为队头指针,指示队头元素的位
置 ;
rear 为队尾指针,指示队尾元素的位
置。
2010年 5月 21日 38
关于队列表示的约定
问题：
读第 1个元素时,front = front +1
x = queue[front]；
front = front +1；
读其它元素时,x = queue[front]；
front = front +1；
? 显然，对于第 1个元素和其它元素的读
操作，将出现不一致。
? 判别队列为空的条件也将复杂化。
2010年 5月 21日 39
关于队列表示的约定
为解决这个问题，约定如下：
? 队头指针 front总是指向队头元素的前
一个位置；
? 队尾指针 rear总是指向队尾元素的位置。
这样一来，无论对什么元素，出队操作
都是一样的。
front = front +1 ；
x = queue [front ]；front reara1 a2 … a n
2010年 5月 21日 40
举例：顺序队列的入队、出
队操作
（ A）空队列
（ B） A,B,C,D,E入队
（ C） A,B,C出队
A B C D E
front rear
front rear
D E
front rear
入队时,rear在变
出队时,front在变
2010年 5月 21日 41
举例、顺序队列的入队、出
队操作
（ D） F,G,H入队
(B） D,E,F,G,H出队，出现假
,溢出,
注,一方面队列中是空的，另一方面又出
现溢出。显然，这是逻辑设计上的问题。
front
front rear
D E F G H
rear
2010年 5月 21日 42
解决假溢出的方法
如果使当 rear = MAXSIZE+1 时，即超过队
列末端时，令 rear = 1；从而使队列的首
尾相连接，只有当队列中真正没有空位置
时，才产生溢出。
用表达式描述，
if （ rear > MAXSIZE ）
rear = 1 ;
else
rear = rear + 1 ;
这就是循环队列的处理思想。
2010年 5月 21日 43
4,循环队列
? 设定 queue[1]接在 queue[MAXSIZE]之后,
使得
if （ rear > MAXSIZE ）
rear = 1 ;
else
rear＝ rear + 1;
这样构成循环队列。
2010年 5月 21日 44
循环队列的指针移动
（ 1） 队头指针
front = front% MAXSIZE
+ 1；
等价于：
if（ front > MAXSIZE ）
front = 1 ;
else
front ＝ front +
1;
（ 2）队尾指针
rear = rear % MAXSIZE
+1 ；
等价于：
if （ rear > MAXSIZE ）
rear = 1;
else
rear＝ rear + 1;
循环队列在指针移动处理时与一般队列不同：
2010年 5月 21日 45
循环队列队空、队满条件
? 队空条件
front = rear ；
? 队满条件
front = rear % MAXSIZE +1
rear
front
1
2 3
MAXSIZE,..
1
2 3 4
...
i
reari+1front
...
MAXSIZE
a1
a2 a3
ai
ai+1
2010年 5月 21日 46
循环队列入队操作
算法 1-12描述,
step1 判别队列是否已满 ;
step2 队尾指针后移一个位置,将新结
点元素值存入当前结点单元。
数据结构定义：
#define MAXSIZE n
int queue[MAXSIZE]；
int front,rear；
2010年 5月 21日 47
循环队列入队操作程序
addqueue(int x)
{ if (front = = rear % MAXIZE
+1 )
{ printf(“循环队列已满 \n”);
exit(1);
}
else
{ rear = rear % MAXSIZE +1;
queue[rear] = x ;
}
}
2010年 5月 21日 48
循环队列出队操作
算法 1-13描述,
step1 判别队列是否为空 ;若空,
则显示队列 ‘ 下溢 ’ ;
step2 队头指针后移一个位置。
2010年 5月 21日 49
循环队列出队操作程序
delqueue( )
{ int y;
if ( front = = rear )
{ printf(, 循环队列已空
\n”) ;
y = -1 ；
}
else
{ front = front % MAXSIZE
+1 ；
y = queue[front] ；
}
return y ；
2010年 5月 21日 50
5、队列的链式存储结构
? 用带头结点的单链表作为队列的存储
结构，称为队列的链式存储结构。
? 存储结构的 C语言描述，
struct qnode {
int data ；
struct qnode * next；
} ；
typedef struct qnode QNODE ；
QNODE *front,*rear；
data next
数据域 指针域
2010年 5月 21日 51
链队列为空的表示
链队列为空，
Queue.front = Queue.rear
表示形式：
非空队列,
front
rear ^
front
rear ^..,ana2a1
2010年 5月 21日 52
链队列为满的条件
链满的条件为,
T = NULL
T 为新创建的结点,当没有
存储空间时,T为 NULL,表示链
队列已满。
2010年 5月 21日 53
链队列的入队操作
算法 1-14描述,
step1 申请建立一个新结点 T;
step2 判别 T是否为空 ;若空,表示
队列已满 ;
step3 非空,将 T插入链中,修改
rear指针。
2010年 5月 21日 54
链队列的入队操作
addqueue(int x)
{ QNODE *t;
t = (QNODE*)malloc(sizeof(QNODE));
if （ t = = NULL）
{ printf（, 内存无可用空间 \n”);
exit(1);
}
else
{ rear -> next = t; rear = t;
t ->data = x;
t ->next = NULL ;
}
}
2010年 5月 21日 55
链队列的出队操作
出队操作要考虑两种情况 ;
? 当队列长度为 1时,除了修改队头指针
外,还要修改队尾指针。
? 当队列长度大于 1时,只修改队头指针
即可。
an ^frontrearQueue
Queu
e
front
rear ^ an ^
T
Queue
Queue
front
rear
rear
front
a1 an ^
a1
a2,..
a2 ^,.,an ^
2010年 5月 21日 56
链队列的出队操作
算法 1-15描述,
step1 判别队列是否为空 ;若空,则显示
队列 ‘ 下溢 ’ ;
step2 非空,则判别队长度是否为 1;
step2.1 不为 1,修改头指针 ;
step2.2 为 1,则修改头、尾指针；
step3 释放 T。
2010年 5月 21日 57
链队列的出队操作的程序
delqueue( )
{ int x;
QNODE *t;
if ( front = = rear)
{ printf(“链队列已空 \n”);
exit(1) ; }
else
{ t = front->next; front->next = t-
>next;
if (t->next = = NULL ) rear =
fornt;
free(t);
}
2010年 5月 21日 58
6、队列的应用
? OS中的各种排队器
? 缓冲区中的循环使用技术
? 离散事件模拟
2010年 5月 21日 59
三、串（ String）
? 串的定义
? 串的存储结构
? 紧缩存储
? 非紧缩存储
? 串的操作
? 串的应用
2010年 5月 21日 60
1、串的定义
? 串是字符的有限序列，它是由单个字符
组成的特殊线性表；记为：
String=?a1 a2 a3 … an?
? n是串的长度,n?0,为 0表示空串。
? 串中任意个连续字符组成的字符子序列
称为子串。
? 当 2个串的长度相等，且各对应位置上的
字符都相同时，称两个子串是相等的。
2010年 5月 21日 61
2、串的基本操作
? LENGTH（ S） 求串 S的长度。
? SUBSTR（ S,start,len）
从串 S中的 start位置开始，求 len个字符的
子串。
DATE=?20?+SUBSTR（ ’ 03/07/00?,7,2） +?
年 ‘
? CONCAT（ S1,S2）联接 S1和 S2，组成一个
新串
S=CONCAT（ ’ Str?,’ ing?）
? INDEX（ S1,S2） 确定 S2在 S1中的位置。
? REPLACE（ S1,S2,S3）
用串 S3替换串 S1中所有与串 S2相等且不重
2010年 5月 21日 62
串操作举例
对串的操作可以用上述 5种基本操作来实
现。
例如，
已知 S=?（ XYZ） +*?
T=?（ X+Z） *Y?，
将 S转化为 T。
S = REPLACE（ S,’ （ XYZ） ‘, ’
（ X+Z） ‘ ）
S1 = SUBSTR(S,1,5)
S1 = CONCAT（ S1,SUBSTR（ S,7,1））
T = CONCAT（ S1,SUBSTR（ S,3,1））
2010年 5月 21日 63
3、串的存储结构
（ 1）顺序存储结构
? 紧缩存储
? 非紧缩存储
（ 2）链表存储结构
? 紧缩存储
? 非紧缩存储
（ 3）堆结构
2010年 5月 21日 64
串的顺序存储结构
有些计算机采用的字编址方式，即数组
元素的分量占 4个字节。由此产生紧缩和
非紧缩存储区别。
? 紧缩存储
一个字的存储单元中存放 4个字符；特点：
? 节省空间
? 需要二次寻址，牺牲了 CPU时间。
? 非紧缩存储
一个字的存储单元中只存放 1个字符。特
点：
? 寻址快
2010年 5月 21日 65
串的链表存储结构
与顺序存储结构类似也有紧缩和非紧缩
存储结构的区别。
? 插入、删除操作效率高；
? 存储空间的利用率低；
? 对于紧缩存储 存储利用率是 50%
（ data 域 4个字节，指针域也 4个字
节）；
? 对于非紧缩存储 存储利用率是 20%
（ 8个字节只存放一个字符）。
2010年 5月 21日 66
堆存储结构
? 串的顺序存储和链表存储各有利弊，在实
际应用中常采用一种动态存储结构，称其
为 堆结构 。
? 定义一个很大的连续空间和相应的指针结
构。指针用来指示串在堆中的位置；
? 例如，设有 a=?BEI?,b=? JING?,c=??，
d=?SHANGHAI?；
串名 串长 起始地址
a 3 1
b 5 4
c 0 9
d 8 9
B E I J I N G S H
A N G H A I
2010年 5月 21日 67
4、串的应用
? 文本编辑
? 建立关键字索引表
2010年 5月 21日 68
文本编辑
? 文本编辑操作实质上是修改字符数据的形式和
格式。
? 例如，利用换页符和换行符把文本划分为若干
页，每页若干行。文本可看成是一个串，页是
文本串的子串，行又是页的子串。
? 建立页表、行表的存储映象表。
? 文本编辑器中设有页指针、行指针和字符指针，
分别对应当前的页、行和字符。
? 修改操作时，随文本的页、行、字符的变化，
修改相应的页、行号、起始地址以及长度。
2010年 5月 21日 69
文本编辑 (一）
将下列程序看作是一个字符串。
100 PROCEDURE P； ?
110 VAR i,j,k,REAL； ?
120 BEGIN ?
130 READ（ i,j）； ?
140 IF i>j THEN k:=j?
150 ELSE k:=i?
160 END； ?
2010年 5月 21日 70
文本编辑（二）
201
221
241
261
281
P R O C E D U R E P ; ? V A R i,
j,k, R E A L ; ? B E G I N ?
R E A D ( i,j ) ; ? I F i >
j T H E N k, = j ; ?
E L S E k, = i ? E N D ; ?
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
2010年 5月 21日 71
文本编辑（三）
为了进行管理,建立页表和行表的存储映象表
如下,
行号 起始地址 长度
100 201 13
110 214 17
120 231 8
130 239 14
140 253 20
150 273 20
160 293 7
2010年 5月 21日 72
建立关键字索引表
? 信息检索是字符串的又一种应用。在
大量信息中，高效、快速检索出需要
的信息，是设计信息检索系统的主要
目标。其中关键技术，是设计一个索
引系统。
? 在实际系统中，按图书名检索并不实
用。因为内容相似的书籍不会同名，
因此，识别很困难。
? 建立书目检索的关键词索引表，就能
很容易地从关键词索引表中查到相关
的书目列表。
2010年 5月 21日 73
建立关键字索引表算法描述
? 从书目中读入一个书目表（字符
串）；
? 从书目串中提取所有关键词插入词
表；
? 对词表中的每一个关键词，建立索
引表（有序）；
? 随后即可检索查询。
2010年 5月 21日 74
建立关键字索引表
（ a） 书目如下 （ b）关键词索引
表
书号 书名 关键词 书号
索引
005 计算机数据结构 分析 034、
050,067
010 数据结构导论 基础 023
023 数据结构基础 结构 005、
010,023
034 计算机算法设计及分析 计算机 005、
034
050 数值分析简介 设计 034
067 数值分析 数据 005、
2010年 5月 21日 75
四、数组（ Array）
? 数组的定义
? 数组的存储结构
? 特殊矩阵的存储及管理
? 数组的操作
2010年 5月 21日 76
1、数组的定义
? 数组是相同类型数据元素的有限集
合；
? 数组中的各个分量称为数组元素；
? 每个数组元素值可以用数组名和一
个下标值唯一的确定；
2010年 5月 21日 77
2、数组的逻辑结构的形式
定义
? 二维数组
2_Array=(D,R)
D 是某种数据类型的有限元素集合,且
D={ aij|i=c1,d1,j=c2,d2,aij ?D0 }
R是行、列关系的有限集合，且
R={ ROW, COL }，又
ROW={ <aij,aij+1>|c1?i?d1,c2?j?d2-1,aij,aij+1 ?
D0 }
COL={ < aij,ai+1j>|c1?i?d1-1,c2?j?d2,aij,ai+1j ?
D0 }
ci 是第 i维的下界
dj 是第 j维的上界
两维数组的元素个数为, (d1-c1+1)*(d2-
2010年 5月 21日 78
N维数组的逻辑结构的形式
定义
? N维数组
n_Array=( D,R )
ji=ci,di,i=1,2,… n
D = aj1j2… jn| aj1… jn ? D0
R={ R1,R2,… Rn }，又
ck?jk?dk 1 ?k ?n,
i<>k
Ri= <aj1… jn,aj1,… ji+1… jn>| ci?ji?di-1
a j1… ji… jn ? D0
N维数组的元素个数为,
(d1-c1+1)*(d2-c2+1)*…,(dn-cn+1) = ? (di-
ci+1)
n
i =1
2010年 5月 21日 79
数组元素之间的关系
二维数组 m行 n列可以看作是 m个或 n个一维
数组,
Amxn = ((a11a12… a1n),(a21a22… a2n),..
(am1am2… amn))
或, a11 a12 a1n
a21 a22 a2n
Amxn =
am1 am2 amn
......,..,..
2010年 5月 21日 80
3、数组的操作
数组有两种基本的操作：
? 给定下标，存取相应的数组元
素；
? 给定下标，修改相应数组元素
的值。
2010年 5月 21日 81
4、数组的顺序存储结构
? 数组元素是连续存放的，因此
只能采用顺序存储结构。
? 无论几维数组,在计算机中都是
按一维数组来存放。数组存放
通常采用两种方式：
? 按行优先顺序
? 按列优先顺序
2010年 5月 21日 82
按行优先顺序 存储结构
按行优先顺序存放是将数组看作若干个行向量。
例如,二维数组 Amxn，可以看作 m个行向量，
每个行向量 n个元素。数组中的每个元素由
元素的两个下标表达式唯一的确定。
地址计算公式：
LOC（ aij） =LOC（ a11） +（（ i-1） *n+（ j-
1）） *L
其中,L 是每个元素所占的存储单元。
2010年 5月 21日 83
二维数组按行优先存储举
例
有二维数组如下：
a11 a12 a13 a14
A3x4 = a21 a22 a23 a24 =
a31 a32 a33 a34
1 2 3 4 5 6 7 8 9 10 11
12
（（ a11,a12,a13,a14），（ a21,a22,a23,a24），（ a31,a32,a33，
a34））
LOC（ a23） = LOC（ a11） +（ 2-1） x4+（ 3-1）
= 7
LOC（ a34） = 1 + （ 3-1） x 4 + （ 4-1）
= 12
2010年 5月 21日 84
按列优先顺序 存储结构
按列优先顺序存放是将数组看作若干个列向量。
例如,二维数组 Amxn，可以看作 n个列向量，
每个列向量 m个元素。数组中的每个元素由元
素的两个下标表达式唯一的确定。
地址计算公式：
LOC（ aij） =LOC（ a11） +（（ j-1） *m+（ i-1）） *L
其中,L 是每个元素所占的存储单元。
2010年 5月 21日 85
二维数组按列优先存储举
例
有二维数组如下：
a11 a12 a13 a14
A3x4 = a21 a22 a23 a24 =
a31 a32 a33 a34
1 2 3 4 5 6 7 8 9 10 11 12
（（ a11,a21,a31），（ a12,a22,a32），（ a13,a23,a33），（ a14,a24，
a34））
LOC（ a23） = LOC（ a11） +（ 3-1） x 3 +（ 2-1）
= 8
LOC（ a34） = 1 + （ 4-1） x 3 + （ 3-1） = 12
LOC（ a ） = 1 + （ 4-1） x 3 + （ 1-1） = 10
2010年 5月 21日 86
5、数组的压缩存储
实际工程问题中推导出的数组常常是
高阶、含大量零元素的矩阵，或者是些
有规律排列的元素。为了节省存储空间，
通常是对这类矩阵进行压缩存储。
压缩的含义是：
? 相同值的多个元素占用一个存储单元；
? 零元素不分配存储单元。
2010年 5月 21日 87
能够采用压缩存储的矩阵
? 对称矩阵 存储主对角线以上（下）的
元素；
? 上（下）三角矩阵 只存储三角阵元
素；
? 带状矩阵 只存储带状元素；
? 稀疏矩阵 只存储非零元素；
? 大量相同元素矩阵 存储某元素和重复
个数。
2010年 5月 21日 88
对称矩阵的压缩存储
对称矩阵的元素满足：
aij = aji 1 ? i, j ? n
因此将 n*n 个元素压缩存放到 n（ n+1）
/2 个单元的一维数组 S（（ n+1） *n/2）中。
aij的地址为：
i（ i-1） /2+j 当 i?j
LOC（ aij） =
j（ j-1） /2+i 当 i<j
2010年 5月 21日 89
对称矩阵的压缩存储举例
设有 A3x3矩阵,
a11
A3x3 = a21 a22
a31 a32 a33
存于一维数组 S[6]
S[6]=(a11,a21,a22,a31,a32,a33)
1 2 3 4 5 6
LOC(a31)=3(3-1)/2+1= 4
LOC(a22)=2(2-1)/2+2= 3
LOC(a21)=2(2-1)/2+1= 2
2010年 5月 21日 90
作业、思考题
1,思考题：
1) 试写出, 在带头结点的单循环链表中求表长的
算法, 。
2) 假设一单循环链表的长度大于 1，且表中即无
头结点也无头指针。已知 S为指向链表中某结
点的指针。试写出删除表中结点 S 的算法。
3) 假设以数组 sequ[m-1]存放循环队列的元素，
设变量 rear和 quelen分别为指示队尾元素位置
和队中元素个数，试写出入队和出队算法。
2,第 1章作业：
8,10,11,17
3,作业要求：
? 作业命名方式为：
学号,章数 _序号
2010年 5月 21日 91
结束语
? 欢迎对数字化教学法提出意见，以利改进。
? 计算机教学实验中心网址：
http,\\ctec,xjtu.edu.cn
? 数字化课件的路径,
jec254\user2\tools\lzq\软件基础
? 作业提交路径：
jec251\user\dataroom\homework\班
级编号
谢谢，再见！
软件技术基础
主讲：仇国巍
西安交通大学计算机教学实验中心
2010年 5月 21日 2
教学内容及要求
内容,栈、队列、数组、串的
? 有关 概念
? 逻辑结构及特点
? 存储结构
? 有关 操作
要求,熟练 掌握上述内容及有关操作的算法
实现。
2010年 5月 21日 3
第 1章的
? 1.3 栈和队列 (P32 - P46)
? 1.4 串和数组 (P47 - P55)
本讲涉及课本内容
2010年 5月 21日 4
? 栈的定义
? 栈的顺序存储结构
? 栈的基本运算
? 多栈共享问题
? 栈的链式存储结构
? 栈的应用
一、栈结构
2010年 5月 21日 5
栈是只允许在同一端进行插入和删除操作
的特殊线性表。允许进行插入和删除操作的一
端称为 栈顶 (top)，另一端为 栈底 (bottom)；
栈底固定，而栈顶浮动；栈结构也称为后进先
出表（ LIFO）。
栈中元素个数为零时称为空栈。
1.1 栈的定义
2010年 5月 21日 6
1.2 栈的顺序存储结构
? 栈的顺序存储结构实际上是一维数组结构 。
? 这种栈又称为 —— 顺序栈 。
? 栈的操作只能在一端进行；即栈顶位置随进
栈和出栈而变化 。
? 顺序栈的 C语言描述为：
#define MAXSIZE 200
int stack[MAXSIZE];
int top = -1;
2010年 5月 21日 7
栈顶指针
? 栈顶指针,在栈操作过程中，有一个专
门的栈指针（习惯上称它为 TOP），指出
栈顶元素所在的位置。
? 栈空的条件,top = -1
? 栈满的条件,top = MAXSIZE-1
2010年 5月 21日 8
a1 a2 …… a n
栈底 栈顶
MAXSIZE
TOP
1.
top = -1
A B C2.
(空栈 ) top=3 (A,B,C进栈）
A B3.
top=2 (C出栈）
4,A B C D E F
top=MAXSIZE-1 (栈满）
1.3 栈操作举例
2010年 5月 21日 9
栈上溢, 栈空间是有限的，若栈已满，
在进行入栈操作时，就要产生上溢。
栈下溢,若栈空，再要执行出栈操作，
则会发生下溢。
栈溢出
2010年 5月 21日 10
? 进栈操作 (插入 ) Push（ Stack,x）
? 出栈操作 (删除 ） Pop（ Stack）
? 取栈顶元素 Gettop（ Stack）
? 置栈为空 Setnull（ Stack）
? 判定栈是否为空 Empty（ Stack）
1.4 栈的基本运算
2010年 5月 21日 11
例：进栈、出栈顺序问题
有 1,2,3三个元素依次入栈序 。 写出可
能的出栈序列 。
出栈序列 操作序列
1 2 3 s x s x s x
1 3 2 s x s s x x
2 1 3 s s x x s x
2 3 1 s s x s x x
3 2 1 s s s x x x
2010年 5月 21日 12
算法 1-8 进栈算法
? 算法步骤,
? step1
判别栈满否，若满，则显示栈溢出
信息，停止执行；否则，执行 step
2；
? Step2
栈顶指针 top上移 (加 1)；
? Step3
在 top所指的位置插入元素 x。
2010年 5月 21日 13
算法 1-8 进栈算法程序
push（ int x）
{ if（ top = = MAXSIZE -1）
{ printf（, 栈上溢 ！ \n”） ;
exit （ 1） ;
}
else
{
top + +； /* 栈指针加 1 */
stack [ top ] = x ； /* 元素 x进
栈 */
}
}
2010年 5月 21日 14
算法 1-9 出栈算法
? 算法步骤,
? step1 判别栈是否为空；若空，则
输出
栈下溢信息，并停止执行；
否则，
执行 step2；
? step2 弹出（删除）栈顶元素；
? step3 栈顶指针 top下移 (减 1)。
2010年 5月 21日 15
算法 1-9 出栈算法程序
pop（ ）
{ int x;
if( top = = -1）
{ printf(,栈下溢 \n”);
exit(1);
}
else
{ x = stack [ top ]；
top - - ； /* 栈顶指针 减
1*/
}
return x ；
}
2010年 5月 21日 16
4、多栈共享问题
? 如何充分利用栈空间，这是解决存储空间紧张
这样一个实际矛盾所要考虑的问题。
? 作为一种策略，就是多栈共享一个栈空间。具
体作法是：
? 对两栈共享情况来说，将两个栈底分别设
在两端,两个栈顶指针 top1和 top2相对中
间位置动态移动，两个栈之间的分界线是
不定的。
a.
b.
c.
top1 =0 top2=MAXSIZE
空栈
top1 top2
栈 1、栈 2均有若干元素
top1 top2
栈满的情况
2010年 5月 21日 17
5、栈的链式存储结构
? 由前面介绍的链表结构可知，链结
构操作灵活。对栈结构也是一样的。
? 顺序栈最多可用于 2个栈的共享，
对于更多的栈就难于表达了。
? 对于最大空间需要量事先不知的情
况，就不能使用顺序栈了。这时，
就需要采用链栈。
2010年 5月 21日 18
? 链栈存储结构的 C语言描述：
struct snode {
int data;
struct snode *link;
};
typedeef struct snode SNODE ;
? 链栈为空的条件,top = NULL
? 链栈为满的条件, t = NULL (t 为申请的
结点,为 NULL表示失败,)
链栈存储结构
2010年 5月 21日 19
链栈示意图
a1
a2
a3
^ 栈底
top 栈顶
…...
ai
2010年 5月 21日 20
算法 1-10 进栈操作
算法 1-10操作步骤,
? step1 申请一个链栈结点,若
t=NULL,则表示链满 ;否则,执行
step2 ;
? step2 在 top所指结点之前插入新
结点,并将 top指向新申请的结点 t。
2010年 5月 21日 21
算法 1-10 进栈操作程序
push(SNODE *top,int x)
{ SNODE *t;
t=(SNODE * )malloc(sizeof(SNODE));
if(t = = NULL )
{
pprintf(“内存中已无可用空间
\n”);
exit(1);
}
else
{ t -> data = x;
t -> link = top; top= t;
}
2010年 5月 21日 22
算法 1-11 出栈操作
算法 1-11操作步骤,
? step1 若链栈为空，则输出栈溢出信息；否
则，执行 step 2。
? step2 删除 top所指结点，并使 top 指向被
删除结点的后继结点。
? step 3 释放被删除结点的存储空间。
2010年 5月 21日 23
算法 1-11 出栈操作程序
pop (SNODE * top)
{ SNODE *p; int x;
if( top = = NULL )
{ printf(“栈溢出 \n”）；
exit(1);
}
else
{ p = top；
top = top-> link ；
x = p-> data ；
free(p) ;
}
}
2010年 5月 21日 24
6、栈的应用
? 表达式计算
? 子程序的嵌套调用
? 参数传递
? 键盘缓冲区
? 递归过程的实现
2010年 5月 21日 25
举例 1 表达式计算
? 计算表达式，首先要正确地定义运算规则：
? 先乘除、后加减
? 从左到右
? 先括号内，再括号外
? 为了让计算机能识别表达式，规定：
? 表达式由操作数（ Operand）和操作符
（ Operator）和定界符（ Delimiter）组成。
例如,#3*（ 7-2） #；
? 实际处理表达式是用两个栈结构 OPTR（算
符）和 OPND（操作数）加运算规则组成；
四
则
运
算
2010年 5月 21日 26
计算表达式算法步骤
? Step1 初始化，清空 OPTR和 OPND，将左
定界符压 OPTR栈；
? Step2 循环输入表达式中的每个字符
? 若输入操作数，则进 OPND栈
? 若是算符，则和 OPTR栈顶元素进行比较，按规
则进行相应操作
? 操作服从优先关系表
? Q1<Q2 Q1入 OPTR栈，再读入下一个元素
? Q1=Q2 Q1出 OPTR栈，脱括号，再读一个元素
? Q1>Q2 Q1出 OPTR栈，从 OPND中取两个数运算
? Step3 直到出现右定界符为止。
? 举例，计算,3*（ 7-2）
输入,3*（ 7-2） #
2010年 5月 21日 27
计算表达式的处理步骤
步骤 OPTR栈 OPND栈 输入字符 主要操作
1 # 3 PUSH（ OPND,3）
2 # 3 * PUSH（ OPTR，‘ *’）
3 # * 3 （ PUSH（ OPTR，‘（’）
4 #*（ 3 7 PUSH（ OPND,7）
5 #*（ 37 - PUSH（ OPTR，‘ -’）
6 #*（ - 37 2 PUSH（ OPND,2）
7 #*（ - 372 ） Operate（ 7，‘ -’,2）
8 #*（ 35 POP（ OPTR）
9 #* 35 # Operate（ 3，‘ *’,5）
10 # 15 RETURN（ GETTOP（ OPND））
2010年 5月 21日 28
举例 2（递归过程实现）
计算 5的阶乘（ 5！ =5X4X3X2X1）
{
if ( n = = 1) return (1);
else return ( n * f(n-1));
}
f(1)
f(2)
f(3)
f(4)
f(5)
top
1 f(1)=1
2*f(1) f(2)=2*f(1)
3*f(2) f(3)=3*f(2)
4*f(3) f(4)=4*f(3)
5*f(4) f(5)=5*f(4)
2010年 5月 21日 29
举例 3（子程序的嵌套调
用）
有一主程序 main（）调用子程序示意图
如下：
main sub1 sub2 sub3
end end end end
sub3
sub2
sub1
main
top
2010年 5月 21日 30
举例 4 N阶 Hanoi塔问题
? 假设有 X,Y,Z三座塔。在 X塔上插有 n个
直径大小不同、以小到大编号为 1,2,…,
n的圆盘。现要求将 X轴上的 n个圆盘移至 Z
塔上，并按同样顺序叠排。移动圆盘的规
则为：
1）每次只能移动一个圆盘；
2）圆盘可以插在 X,Y,Z的任意一个上；
3）任何时刻都不能将较大的圆盘压在较
小的圆盘之上。
注,这是一个递归问题,n阶问题可以
分解为 n圆盘和 n-1阶问题。
2010年 5月 21日 31
n=1的 Hanoi塔问题
X Y Z
2010年 5月 21日 32
n=2的 Hanoi塔问题
X Y Z
2010年 5月 21日 33
n=3的 Hanoi塔问题
X Y Z
变为 n-1问题
2010年 5月 21日 34
二、队列结构（ Queue）
? 队列的定义
? 队列的基本运算
? 队列的顺序存储结构
? 循环队列存储结构
? 队列的链式存储结构
? 队列的应用
2010年 5月 21日 35
1、队列定义
? 队列是一种特殊的线性表，它只允许在表的前
端（ front）进行删除操作，而在表的后端
（ rear）进行插入操作。
? 进行插入操作的端称为队尾，进行删除操作的
端称为队头。
? 队列中没有元素时，称为空队列。
? 队列具有先进先出（ FIFO）的特点。
? 队列空的条件,front = rear
? 队列满的条件,rear = MAXSIZE
a1 a2 … a n 入队插入出队删除
front rear
2010年 5月 21日 36
2、队列的操作
Setnull（ Q） 清空队列
Empty（ Q） 判别队列是否为空；空，
取,T.;
非空,取值为,F.。
Addqueue（ Q） 插入操作
Delqueue（ Q） 删除操作
Frontqueue（ Q）取队头元素
2010年 5月 21日 37
3、队列的顺序存储结构
C语言中顺序存储结构采用一维数组结构，
描述如下：
#define MAXSIZE n
int queue[MAXSIZ]；
int front,rear;
front为队头指针,指示队头元素的位
置 ;
rear 为队尾指针,指示队尾元素的位
置。
2010年 5月 21日 38
关于队列表示的约定
问题：
读第 1个元素时,front = front +1
x = queue[front]；
front = front +1；
读其它元素时,x = queue[front]；
front = front +1；
? 显然，对于第 1个元素和其它元素的读
操作，将出现不一致。
? 判别队列为空的条件也将复杂化。
2010年 5月 21日 39
关于队列表示的约定
为解决这个问题，约定如下：
? 队头指针 front总是指向队头元素的前
一个位置；
? 队尾指针 rear总是指向队尾元素的位置。
这样一来，无论对什么元素，出队操作
都是一样的。
front = front +1 ；
x = queue [front ]；front reara1 a2 … a n
2010年 5月 21日 40
举例：顺序队列的入队、出
队操作
（ A）空队列
（ B） A,B,C,D,E入队
（ C） A,B,C出队
A B C D E
front rear
front rear
D E
front rear
入队时,rear在变
出队时,front在变
2010年 5月 21日 41
举例、顺序队列的入队、出
队操作
（ D） F,G,H入队
(B） D,E,F,G,H出队，出现假
,溢出,
注,一方面队列中是空的，另一方面又出
现溢出。显然，这是逻辑设计上的问题。
front
front rear
D E F G H
rear
2010年 5月 21日 42
解决假溢出的方法
如果使当 rear = MAXSIZE+1 时，即超过队
列末端时，令 rear = 1；从而使队列的首
尾相连接，只有当队列中真正没有空位置
时，才产生溢出。
用表达式描述，
if （ rear > MAXSIZE ）
rear = 1 ;
else
rear = rear + 1 ;
这就是循环队列的处理思想。
2010年 5月 21日 43
4,循环队列
? 设定 queue[1]接在 queue[MAXSIZE]之后,
使得
if （ rear > MAXSIZE ）
rear = 1 ;
else
rear＝ rear + 1;
这样构成循环队列。
2010年 5月 21日 44
循环队列的指针移动
（ 1） 队头指针
front = front% MAXSIZE
+ 1；
等价于：
if（ front > MAXSIZE ）
front = 1 ;
else
front ＝ front +
1;
（ 2）队尾指针
rear = rear % MAXSIZE
+1 ；
等价于：
if （ rear > MAXSIZE ）
rear = 1;
else
rear＝ rear + 1;
循环队列在指针移动处理时与一般队列不同：
2010年 5月 21日 45
循环队列队空、队满条件
? 队空条件
front = rear ；
? 队满条件
front = rear % MAXSIZE +1
rear
front
1
2 3
MAXSIZE,..
1
2 3 4
...
i
reari+1front
...
MAXSIZE
a1
a2 a3
ai
ai+1
2010年 5月 21日 46
循环队列入队操作
算法 1-12描述,
step1 判别队列是否已满 ;
step2 队尾指针后移一个位置,将新结
点元素值存入当前结点单元。
数据结构定义：
#define MAXSIZE n
int queue[MAXSIZE]；
int front,rear；
2010年 5月 21日 47
循环队列入队操作程序
addqueue(int x)
{ if (front = = rear % MAXIZE
+1 )
{ printf(“循环队列已满 \n”);
exit(1);
}
else
{ rear = rear % MAXSIZE +1;
queue[rear] = x ;
}
}
2010年 5月 21日 48
循环队列出队操作
算法 1-13描述,
step1 判别队列是否为空 ;若空,
则显示队列 ‘ 下溢 ’ ;
step2 队头指针后移一个位置。
2010年 5月 21日 49
循环队列出队操作程序
delqueue( )
{ int y;
if ( front = = rear )
{ printf(, 循环队列已空
\n”) ;
y = -1 ；
}
else
{ front = front % MAXSIZE
+1 ；
y = queue[front] ；
}
return y ；
2010年 5月 21日 50
5、队列的链式存储结构
? 用带头结点的单链表作为队列的存储
结构，称为队列的链式存储结构。
? 存储结构的 C语言描述，
struct qnode {
int data ；
struct qnode * next；
} ；
typedef struct qnode QNODE ；
QNODE *front,*rear；
data next
数据域 指针域
2010年 5月 21日 51
链队列为空的表示
链队列为空，
Queue.front = Queue.rear
表示形式：
非空队列,
front
rear ^
front
rear ^..,ana2a1
2010年 5月 21日 52
链队列为满的条件
链满的条件为,
T = NULL
T 为新创建的结点,当没有
存储空间时,T为 NULL,表示链
队列已满。
2010年 5月 21日 53
链队列的入队操作
算法 1-14描述,
step1 申请建立一个新结点 T;
step2 判别 T是否为空 ;若空,表示
队列已满 ;
step3 非空,将 T插入链中,修改
rear指针。
2010年 5月 21日 54
链队列的入队操作
addqueue(int x)
{ QNODE *t;
t = (QNODE*)malloc(sizeof(QNODE));
if （ t = = NULL）
{ printf（, 内存无可用空间 \n”);
exit(1);
}
else
{ rear -> next = t; rear = t;
t ->data = x;
t ->next = NULL ;
}
}
2010年 5月 21日 55
链队列的出队操作
出队操作要考虑两种情况 ;
? 当队列长度为 1时,除了修改队头指针
外,还要修改队尾指针。
? 当队列长度大于 1时,只修改队头指针
即可。
an ^frontrearQueue
Queu
e
front
rear ^ an ^
T
Queue
Queue
front
rear
rear
front
a1 an ^
a1
a2,..
a2 ^,.,an ^
2010年 5月 21日 56
链队列的出队操作
算法 1-15描述,
step1 判别队列是否为空 ;若空,则显示
队列 ‘ 下溢 ’ ;
step2 非空,则判别队长度是否为 1;
step2.1 不为 1,修改头指针 ;
step2.2 为 1,则修改头、尾指针；
step3 释放 T。
2010年 5月 21日 57
链队列的出队操作的程序
delqueue( )
{ int x;
QNODE *t;
if ( front = = rear)
{ printf(“链队列已空 \n”);
exit(1) ; }
else
{ t = front->next; front->next = t-
>next;
if (t->next = = NULL ) rear =
fornt;
free(t);
}
2010年 5月 21日 58
6、队列的应用
? OS中的各种排队器
? 缓冲区中的循环使用技术
? 离散事件模拟
2010年 5月 21日 59
三、串（ String）
? 串的定义
? 串的存储结构
? 紧缩存储
? 非紧缩存储
? 串的操作
? 串的应用
2010年 5月 21日 60
1、串的定义
? 串是字符的有限序列，它是由单个字符
组成的特殊线性表；记为：
String=?a1 a2 a3 … an?
? n是串的长度,n?0,为 0表示空串。
? 串中任意个连续字符组成的字符子序列
称为子串。
? 当 2个串的长度相等，且各对应位置上的
字符都相同时，称两个子串是相等的。
2010年 5月 21日 61
2、串的基本操作
? LENGTH（ S） 求串 S的长度。
? SUBSTR（ S,start,len）
从串 S中的 start位置开始，求 len个字符的
子串。
DATE=?20?+SUBSTR（ ’ 03/07/00?,7,2） +?
年 ‘
? CONCAT（ S1,S2）联接 S1和 S2，组成一个
新串
S=CONCAT（ ’ Str?,’ ing?）
? INDEX（ S1,S2） 确定 S2在 S1中的位置。
? REPLACE（ S1,S2,S3）
用串 S3替换串 S1中所有与串 S2相等且不重
2010年 5月 21日 62
串操作举例
对串的操作可以用上述 5种基本操作来实
现。
例如，
已知 S=?（ XYZ） +*?
T=?（ X+Z） *Y?，
将 S转化为 T。
S = REPLACE（ S,’ （ XYZ） ‘, ’
（ X+Z） ‘ ）
S1 = SUBSTR(S,1,5)
S1 = CONCAT（ S1,SUBSTR（ S,7,1））
T = CONCAT（ S1,SUBSTR（ S,3,1））
2010年 5月 21日 63
3、串的存储结构
（ 1）顺序存储结构
? 紧缩存储
? 非紧缩存储
（ 2）链表存储结构
? 紧缩存储
? 非紧缩存储
（ 3）堆结构
2010年 5月 21日 64
串的顺序存储结构
有些计算机采用的字编址方式，即数组
元素的分量占 4个字节。由此产生紧缩和
非紧缩存储区别。
? 紧缩存储
一个字的存储单元中存放 4个字符；特点：
? 节省空间
? 需要二次寻址，牺牲了 CPU时间。
? 非紧缩存储
一个字的存储单元中只存放 1个字符。特
点：
? 寻址快
2010年 5月 21日 65
串的链表存储结构
与顺序存储结构类似也有紧缩和非紧缩
存储结构的区别。
? 插入、删除操作效率高；
? 存储空间的利用率低；
? 对于紧缩存储 存储利用率是 50%
（ data 域 4个字节，指针域也 4个字
节）；
? 对于非紧缩存储 存储利用率是 20%
（ 8个字节只存放一个字符）。
2010年 5月 21日 66
堆存储结构
? 串的顺序存储和链表存储各有利弊，在实
际应用中常采用一种动态存储结构，称其
为 堆结构 。
? 定义一个很大的连续空间和相应的指针结
构。指针用来指示串在堆中的位置；
? 例如，设有 a=?BEI?,b=? JING?,c=??，
d=?SHANGHAI?；
串名 串长 起始地址
a 3 1
b 5 4
c 0 9
d 8 9
B E I J I N G S H
A N G H A I
2010年 5月 21日 67
4、串的应用
? 文本编辑
? 建立关键字索引表
2010年 5月 21日 68
文本编辑
? 文本编辑操作实质上是修改字符数据的形式和
格式。
? 例如，利用换页符和换行符把文本划分为若干
页，每页若干行。文本可看成是一个串，页是
文本串的子串，行又是页的子串。
? 建立页表、行表的存储映象表。
? 文本编辑器中设有页指针、行指针和字符指针，
分别对应当前的页、行和字符。
? 修改操作时，随文本的页、行、字符的变化，
修改相应的页、行号、起始地址以及长度。
2010年 5月 21日 69
文本编辑 (一）
将下列程序看作是一个字符串。
100 PROCEDURE P； ?
110 VAR i,j,k,REAL； ?
120 BEGIN ?
130 READ（ i,j）； ?
140 IF i>j THEN k:=j?
150 ELSE k:=i?
160 END； ?
2010年 5月 21日 70
文本编辑（二）
201
221
241
261
281
P R O C E D U R E P ; ? V A R i,
j,k, R E A L ; ? B E G I N ?
R E A D ( i,j ) ; ? I F i >
j T H E N k, = j ; ?
E L S E k, = i ? E N D ; ?
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
2010年 5月 21日 71
文本编辑（三）
为了进行管理,建立页表和行表的存储映象表
如下,
行号 起始地址 长度
100 201 13
110 214 17
120 231 8
130 239 14
140 253 20
150 273 20
160 293 7
2010年 5月 21日 72
建立关键字索引表
? 信息检索是字符串的又一种应用。在
大量信息中，高效、快速检索出需要
的信息，是设计信息检索系统的主要
目标。其中关键技术，是设计一个索
引系统。
? 在实际系统中，按图书名检索并不实
用。因为内容相似的书籍不会同名，
因此，识别很困难。
? 建立书目检索的关键词索引表，就能
很容易地从关键词索引表中查到相关
的书目列表。
2010年 5月 21日 73
建立关键字索引表算法描述
? 从书目中读入一个书目表（字符
串）；
? 从书目串中提取所有关键词插入词
表；
? 对词表中的每一个关键词，建立索
引表（有序）；
? 随后即可检索查询。
2010年 5月 21日 74
建立关键字索引表
（ a） 书目如下 （ b）关键词索引
表
书号 书名 关键词 书号
索引
005 计算机数据结构 分析 034、
050,067
010 数据结构导论 基础 023
023 数据结构基础 结构 005、
010,023
034 计算机算法设计及分析 计算机 005、
034
050 数值分析简介 设计 034
067 数值分析 数据 005、
2010年 5月 21日 75
四、数组（ Array）
? 数组的定义
? 数组的存储结构
? 特殊矩阵的存储及管理
? 数组的操作
2010年 5月 21日 76
1、数组的定义
? 数组是相同类型数据元素的有限集
合；
? 数组中的各个分量称为数组元素；
? 每个数组元素值可以用数组名和一
个下标值唯一的确定；
2010年 5月 21日 77
2、数组的逻辑结构的形式
定义
? 二维数组
2_Array=(D,R)
D 是某种数据类型的有限元素集合,且
D={ aij|i=c1,d1,j=c2,d2,aij ?D0 }
R是行、列关系的有限集合，且
R={ ROW, COL }，又
ROW={ <aij,aij+1>|c1?i?d1,c2?j?d2-1,aij,aij+1 ?
D0 }
COL={ < aij,ai+1j>|c1?i?d1-1,c2?j?d2,aij,ai+1j ?
D0 }
ci 是第 i维的下界
dj 是第 j维的上界
两维数组的元素个数为, (d1-c1+1)*(d2-
2010年 5月 21日 78
N维数组的逻辑结构的形式
定义
? N维数组
n_Array=( D,R )
ji=ci,di,i=1,2,… n
D = aj1j2… jn| aj1… jn ? D0
R={ R1,R2,… Rn }，又
ck?jk?dk 1 ?k ?n,
i<>k
Ri= <aj1… jn,aj1,… ji+1… jn>| ci?ji?di-1
a j1… ji… jn ? D0
N维数组的元素个数为,
(d1-c1+1)*(d2-c2+1)*…,(dn-cn+1) = ? (di-
ci+1)
n
i =1
2010年 5月 21日 79
数组元素之间的关系
二维数组 m行 n列可以看作是 m个或 n个一维
数组,
Amxn = ((a11a12… a1n),(a21a22… a2n),..
(am1am2… amn))
或, a11 a12 a1n
a21 a22 a2n
Amxn =
am1 am2 amn
......,..,..
2010年 5月 21日 80
3、数组的操作
数组有两种基本的操作：
? 给定下标，存取相应的数组元
素；
? 给定下标，修改相应数组元素
的值。
2010年 5月 21日 81
4、数组的顺序存储结构
? 数组元素是连续存放的，因此
只能采用顺序存储结构。
? 无论几维数组,在计算机中都是
按一维数组来存放。数组存放
通常采用两种方式：
? 按行优先顺序
? 按列优先顺序
2010年 5月 21日 82
按行优先顺序 存储结构
按行优先顺序存放是将数组看作若干个行向量。
例如,二维数组 Amxn，可以看作 m个行向量，
每个行向量 n个元素。数组中的每个元素由
元素的两个下标表达式唯一的确定。
地址计算公式：
LOC（ aij） =LOC（ a11） +（（ i-1） *n+（ j-
1）） *L
其中,L 是每个元素所占的存储单元。
2010年 5月 21日 83
二维数组按行优先存储举
例
有二维数组如下：
a11 a12 a13 a14
A3x4 = a21 a22 a23 a24 =
a31 a32 a33 a34
1 2 3 4 5 6 7 8 9 10 11
12
（（ a11,a12,a13,a14），（ a21,a22,a23,a24），（ a31,a32,a33，
a34））
LOC（ a23） = LOC（ a11） +（ 2-1） x4+（ 3-1）
= 7
LOC（ a34） = 1 + （ 3-1） x 4 + （ 4-1）
= 12
2010年 5月 21日 84
按列优先顺序 存储结构
按列优先顺序存放是将数组看作若干个列向量。
例如,二维数组 Amxn，可以看作 n个列向量，
每个列向量 m个元素。数组中的每个元素由元
素的两个下标表达式唯一的确定。
地址计算公式：
LOC（ aij） =LOC（ a11） +（（ j-1） *m+（ i-1）） *L
其中,L 是每个元素所占的存储单元。
2010年 5月 21日 85
二维数组按列优先存储举
例
有二维数组如下：
a11 a12 a13 a14
A3x4 = a21 a22 a23 a24 =
a31 a32 a33 a34
1 2 3 4 5 6 7 8 9 10 11 12
（（ a11,a21,a31），（ a12,a22,a32），（ a13,a23,a33），（ a14,a24，
a34））
LOC（ a23） = LOC（ a11） +（ 3-1） x 3 +（ 2-1）
= 8
LOC（ a34） = 1 + （ 4-1） x 3 + （ 3-1） = 12
LOC（ a ） = 1 + （ 4-1） x 3 + （ 1-1） = 10
2010年 5月 21日 86
5、数组的压缩存储
实际工程问题中推导出的数组常常是
高阶、含大量零元素的矩阵，或者是些
有规律排列的元素。为了节省存储空间，
通常是对这类矩阵进行压缩存储。
压缩的含义是：
? 相同值的多个元素占用一个存储单元；
? 零元素不分配存储单元。
2010年 5月 21日 87
能够采用压缩存储的矩阵
? 对称矩阵 存储主对角线以上（下）的
元素；
? 上（下）三角矩阵 只存储三角阵元
素；
? 带状矩阵 只存储带状元素；
? 稀疏矩阵 只存储非零元素；
? 大量相同元素矩阵 存储某元素和重复
个数。
2010年 5月 21日 88
对称矩阵的压缩存储
对称矩阵的元素满足：
aij = aji 1 ? i, j ? n
因此将 n*n 个元素压缩存放到 n（ n+1）
/2 个单元的一维数组 S（（ n+1） *n/2）中。
aij的地址为：
i（ i-1） /2+j 当 i?j
LOC（ aij） =
j（ j-1） /2+i 当 i<j
2010年 5月 21日 89
对称矩阵的压缩存储举例
设有 A3x3矩阵,
a11
A3x3 = a21 a22
a31 a32 a33
存于一维数组 S[6]
S[6]=(a11,a21,a22,a31,a32,a33)
1 2 3 4 5 6
LOC(a31)=3(3-1)/2+1= 4
LOC(a22)=2(2-1)/2+2= 3
LOC(a21)=2(2-1)/2+1= 2
2010年 5月 21日 90
作业、思考题
1,思考题：
1) 试写出, 在带头结点的单循环链表中求表长的
算法, 。
2) 假设一单循环链表的长度大于 1，且表中即无
头结点也无头指针。已知 S为指向链表中某结
点的指针。试写出删除表中结点 S 的算法。
3) 假设以数组 sequ[m-1]存放循环队列的元素，
设变量 rear和 quelen分别为指示队尾元素位置
和队中元素个数，试写出入队和出队算法。
2,第 1章作业：
8,10,11,17
3,作业要求：
? 作业命名方式为：
学号,章数 _序号
2010年 5月 21日 91
结束语
? 欢迎对数字化教学法提出意见，以利改进。
? 计算机教学实验中心网址：
http,\\ctec,xjtu.edu.cn
? 数字化课件的路径,
jec254\user2\tools\lzq\软件基础
? 作业提交路径：
jec251\user\dataroom\homework\班
级编号
谢谢，再见！
