下一页
计算机软件基础
The software basic
of computer
主讲：赵英良
西安交通大学
计算机教学实验中心
第 3单元
线性数据结构
（二）
下一页
上一页
停止放映
第 2 页
第 2单元内容概要（一）
一、数据结构
1。基本概念：数据、数据元素、数据项、数据结构、
数据结构的形式化描述方法。
2。数据的逻辑结构：
逻辑结构的类别（集合、线性、树、图）
3。数据的物理结构及类别（顺序、链式、索引、散
列）
4。算法的描述及评价
（ 1）算法的概念：
（ 2）算法的特性：有限、确定、可行、输入、输出
（ 3）设计算法的要求：正确、可读、健壮、效率
（ 4）算法的评价：时间复杂性、空间复杂性
下一页
上一页
停止放映
第 3 页
第 2单元内容概要（二）
? 二、顺序表
1。线性表及相关概念和特征
线性表、长度、空表、前驱、后继、
均匀性、有序性、形式化定义
2。顺序表
概念、特征、描述（数组,last）
3。顺序表的操作
（ 1）判空、判满、判合法 （ 2）插入（ 3）删除
? 4。顺序表的优缺点及适用场合
– 数据连续存放、随机存取
– 逻辑上相邻，物理上也相邻
– 存储结构简单、易实现
– 插入、删除操作不便
– 存储密度大，空间利用率高
下一页
上一页
停止放映
第 4 页
第 2单元内容概要（三）
? 三、链表
? 1。单链表
? 结点、指针域、数据域、头指针、头结点。
? 2。单链表的描述
? 3。单链表的操作
? （ 1）指针操作、
? 指针说明、分配存储空间、判空、判满、释放
空间
? （ 2）查找操作 （ 3）插入 （ 4）删除
? 4。单链表的特点及适用场合
? 5。单循环链表、双向链表、双向循环链表
描述、建立、判空、查找、插入、删除
下一页
上一页
停止放映
第 5 页
本单元内容
? 栈、队列、数组、串 的,
– 有关 概念
– 逻辑结构及特点
– 存储结构
– 有关 操作
? 涉及章节,第 1章的
1.3 栈和队列 (P32~P46)
1.4 串和数组 (P47~P55)
下一页
上一页
停止放映
第 6 页
一、栈
1。栈及相关概念
堆栈 (Stack)
– 栈是允许在同一端进行插入和删除操作的
特殊线性表。
– 允许进行插入和删除操作的一端称为 栈顶
(top)，另一端为 栈底 (bottom)； 栈底固定，
而栈顶浮动 ；
– 栈中元素个数为零时称为 空栈 。
– 栈结构也称为后进先出表（ LIFO）。
栈、栈顶、栈底、空栈
后进先出表 栈底固定，而栈顶浮动
下一页
上一页
停止放映
第 7 页
栈有关概念
栈顶指针
在栈操作过程中，有一个专门的栈指针（习惯
上称它为 TOP），指出栈顶元素所在的位置。
栈空的条件,top = -1
栈满的条件,top = MAXSIZE-1
栈上溢
栈空间是有限的，若栈已满，再进行入栈操作
时，就要产生上溢。
栈下溢
若栈空，再要执行出栈操作，则会发生下溢。
下一页
上一页
停止放映
第 8 页
2、栈的基本运算
? Setnull（ Stack） 置栈为空；
? Empty（ Stack） 判定栈是否为空；
? Push（ Stack,x） 进栈操作，在栈顶插入元素；
? Pop（ Stack） 出栈操作，删除栈顶元素；
? Gettop（ Stack） 取栈顶元素
下一页
上一页
停止放映
第 9 页
例 1-10
有三个元素的进栈序列是 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
下一页
上一页
停止放映
第 10 页
3、栈的顺序存储结构
? （ 1） 栈的顺序存储结构, 实际上是一维
数组 。
? （ 2） 顺序栈, 栈的顺序存储结构称为顺
序栈 。
? 栈的操作只能在一端进行；即栈顶位置随
进栈和出栈而变化 。
? （ 3） 顺序栈的 C语言描述 (初始化, 定义 )：
#define MAXSIZE n
int stack[MAXSIZE];
int top = -1;
下一页
上一页
停止放映
第 11 页
栈操作举例
a1 a2 …… a n
栈底 栈顶
MAXSIZE
TOP
1.
top=-1
A B C2.
(空栈 ) top=2 (A,B,C进栈）
A B3.
top=1 (C出栈）
4,A B C D E F
top=MAXSIZE-1
(栈满）
下一页
上一页
停止放映
第 12 页
(4) 算法 1-8 进栈算法
? 算法步骤,
– step1
判别栈满否，若满，则显示栈溢
出信息，停止执行；否则，执行
step 2；
– Step2
栈顶指针 top上移 (加 1)；
– Step3
在 top所指的位置插入元素 x。
下一页
上一页
停止放映
第 13 页
算法 1-8 进栈算法程序
push（ int x）
{ if（ top = = MAXSIZE -1） /* 判满? */
{ printf（, 栈上溢 ！ \n”） ;
exit （ 1） ;
}
else /* 不满，则可以进栈 */
{
top + +； /* 栈指针加 1 */
stack [ top ] = x ； /* 元素 x进栈 */
}
}
示例
下一页
上一页
停止放映
第 14 页
(5) 算法 1-9 出栈算法
? 算法步骤,
– step1 判别栈是否为空；若空，则输出
栈下溢信息，并停止执行；否则，
执行 step2；
– step2 弹出（删除）栈顶元素；
– step3 栈顶指针 top下移 (减 1)。
– step4 返回出栈元素
下一页
上一页
停止放映
第 15 页
算法 1-9 出栈算法程序
pop（ ）
{ int x;
if( top = = -1） /* 判空 */
{ printf(,栈下溢 \n”);
exit(1);
}
else /* 出栈 */
{ x = stack [ top ]；
top - - ； /* 栈顶指针 减 1*/
}
return x ；
} 示例
int
下一页
上一页
停止放映
第 16 页
4、多栈共享问题
? 如何充分利用栈空间，这是解决存储空间紧张这样一个
实际矛盾所要考虑的问题。
? 作为一种策略，就是多栈共享一个栈空间。具体作法是：
– 对两栈共享情况来说,将两个栈底分别设在两端，
两个栈顶指针 top1和 top2相对中间位置动态移动，
两个栈之间的分界线是不定的。
a.
b.
c.
top1 =-1 top2=MAXSIZE
空栈
top1 top2
栈 1、栈 2均有若干元素
top1 top2
栈满的情况
下一页
上一页
停止放映
第 17 页
5、栈的链式存储结构
? 由前面介绍的链表结构可知，链结构
操作灵活。对栈结构也是一样的。
? 顺序栈最多可用于 2个栈的共享，对
于更多的栈就难于表达了。
? 对于最大空间需要量事先不知的情况，
就不能使用顺序栈了。这时，就需要
采用链栈。
链栈：栈的链式存储结构
下一页
上一页
停止放映
第 18 页
链栈存储结构
? (1) 链栈存储结构的 C语言描述：
struct snode {
int data;
struct snode *link;
};
typedeef struct snode SNODE ;
? 链栈为空的条件：
top = NULL
? 链栈为满的条件,
t = NULL
t 为申请的结点,为 NULL表示失败,
下一页
上一页
停止放映
第 19 页
链栈示意图
a1
a2
a3
^ 栈底
top 栈顶
…...
ai
下一页
上一页
停止放映
第 20 页
(2) 算法 1-10 进栈操作
算法 1-10操作步骤,
? step1 申请一个链栈结点,若
t=NULL,则表示链满 ;否则,执行
step2 ;
? step2 在 top所指结点之前插入
新结点,并将 top指向新申请的结
点 t。
下一页
上一页
停止放映
第 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;
}
}
下一页
上一页
停止放映
第 22 页
(3) 算法 1-11 出栈操作
算法 1-11操作步骤,
? step1 若链栈为空，则输出栈溢出信息；
否则，执行 step 2。
? step2 (保存 top)并使 top 指向被删除结点
的后继结点,删除 top所指结点，。
? step 3 释放被删除结点的存储空间。 返回
出栈元素值
下一页
上一页
停止放映
第 23 页
算法 1-11 出栈操作程序
int 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) ;
}
return x;
}
下一页
上一页
停止放映
第 24 页
6.栈的应用
? （ 1） 举例 1 表达式计算
? 计算表达式，首先要正确地定义运算规则：
– 先乘除、后加减
– 从左到右
– 先括号内，再括号外
? 为了让计算机能识别表达式，规定：
– 表达式由操作数（ Operand）和操作符
（ Operator）和定界符（ Delimiter）组成。
例如,#3*（ 7-2） #；
– 实际处理表达式是用两个栈结构 OPTR（算符）
和 OPND（操作数）加运算规则组成；
四
则
运
算
下一页
上一页
停止放映
第 25 页
计算表达式算法步骤
? Step1 初始化，清空 OPTR和 OPND，将左定界符
压 OPTR栈；
? Step2 循环输入表达式中的每个字符
– 若输入操作数，则进 OPND栈
– 若是算符，则和 OPTR栈顶元素进行比较，按规则进行
相应操作
– 操作服从优先关系表
? Q1<Q2 Q2入 OPTR栈，再读入下一个元素
? Q1=Q2 Q1出 OPTR栈，脱括号，再读一个元素
? Q1>Q2 Q1出 OPTR栈，从 OPND中取两个数运算
? 结果入栈 OPND
? Step3 直到出现右定界符为止。
? 举例，计算,3*（ 7-2）
输入,3*（ 7-2） #
下一页
上一页
停止放映
第 26 页
计算表达式的处理步骤
步骤 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））
下一页
上一页
停止放映
第 27 页
举例 2（递归过程实现）
（ 2）递归规程的实现
计算 5的阶乘（ 5！ =5X4X3X2X1）
int f(n){
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)
下一页
上一页
停止放映
第 28 页
（３）举例３ N阶 Hanoi塔问题
? 假设有 A,B,C三座塔。在 X塔上插有 n个直
径大小不同、以小到大编号为 1,2,…, n
的圆盘。现要求将 A轴上的 n个圆盘移至 C塔
上，并按同样顺序叠排。移动圆盘的规则为：
1）每次只能移动一个圆盘；
2）圆盘可以插在 A,B,C的任意一个上；
3）任何时刻都不能将较大的圆盘压在较小
的圆盘之上。
移动方法：先将 (n-1)个圆盘从Ａ移到Ｂ，将
第 n个原盘从Ａ移到Ｃ，再将（ n-1）个圆盘
从Ｂ移到Ｃ
下一页
上一页
停止放映
第 29 页
Hanoi问题的实现程序 (主要部分 )
void f(int n,int a1,int b1,int c1)
{
if(n==1) /* there is only one element,a1->c1 */
{
pop(a1); push(c1);
}
else
{ f(n-1,a1,c1,b1); /* (n-1) from a1 to b1 */
pop(a1); /* the last one from a1 to c1 */
push(c1);
f(n-1,b1,a1,c1); /* last, (n-1) from b1 to c1 */
}
下一页
上一页
停止放映
第 30 页
二、队列
? １。队列的基本概念
? 队列 是一种特殊的线性表，它只允许在表的前
端（ front）进行删除操作，而在表的后端
（ rear）进行插入操作。
? 进行插入操作的端称为 队尾,进行删除操作的
端称为 队头 。
? 队列中没有元素时，称为 空队列 。
? 队列具有先进先出（ FIFO）的 特点 。
a1 a2 … a n 入队插入出队删除
front rear
传送带
下一页
上一页
停止放映
第 31 页
2、队列的操作
Setnull（ Q） 清空队列
Empty（ Q） 判别队列是否为空；空，取,T.;
非空,取值为,F.。
Addqueue（ Q） 插入操作
Delqueue（ Q） 删除操作
Frontqueue（ Q）取队头元素
下一页
上一页
停止放映
第 32 页
3、队列的顺序存储结构
(1)描述
C语言中顺序存储结构采用一维数组结构，
描述如下：
#define MAXSIZE n
int queue[MAXSIZE]；
int front,rear;
（２）约定
front为 队头指针,指示队头元素的的前
一个位置 ;
rear 为 队尾指针,指示队尾元素的位置。
下一页
上一页
停止放映
第 33 页
（３）基本操作
初 始 时, front=-1; rear=-1;
front= =rear 队空
X入队操作, rear=rear+1;
queue[rear]=x;
出队操作, front=front+1;
x=queue[front];
return x;
队 空, front= =rear;
队 满,rear= =(MAXSIZE-1);?
初始化、入队、出队、队空？、队满？
下一页
上一页
停止放映
第 34 页
举例：顺序队列的入队、出队操作
（ 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在变
下一页
上一页
停止放映
第 35 页
举例、顺序队列的入队、出队操作
（ D） F,G,H入队
(B） D,E,F,G,H出队，出现假, 溢出,
注,一方面队列中是空的，另一方面又出现溢出。
显然，这是逻辑设计上的问题。
front
front rear
D E F G H
rear
下一页
上一页
停止放映
第 36 页
4,循环队列
? （１）循环队列的概念
? 如果使当 rear = MAXSIZE 时，即超过队列末端时，
令 rear = 0；从而使队列的首尾相连接，只有当
队列中真正没有空位置时，才产生溢出。
? 设定 queue[0]接在 queue[MAXSIZE-1]之后,使得
if （ rear > MAXSIZE-1 ）
rear = 0 ;
else
rear＝ rear + 1;
这样构成循环队列。
下一页
上一页
停止放映
第 37 页
(2)循环队列的指针移动
（ 1） 队头指针
front = (front+1)% MAXSIZE；
等价于,
if（ (front+1) >=MAXSIZE）
front = 0 ;
else
front ＝ front + 1;
（ 2）队尾指针
rear = (rear+1) % MAXSIZE ；
等价于,
if （ (rear+1) >=MAXSIZE ）
rear = 0;
else
rear＝ rear + 1;
循环队列在指针移动处理时与一般队列不同：
？ （ front+1） %MAXSIZE 与 front%MAXSIZE+1
相同吗？
下一页
上一页
停止放映
第 38 页
(3)循环队列队空、队满条件
? 队空条件
front ＝ = rear ；
? 队满条件
? (队头和队尾间有一空闲
? 单元时认为已满 )
front ＝ = （ rear＋１） % MAXSIZE
rear
front
1
2 3
MAXSIZE,..
1
2 3 4
...
i
reari+1front
...
MAXSIZE
a1
a2 a3
ai
ai+1
下一页
上一页
停止放映
第 39 页
（４） 循环队列入队操作
数据结构定义,
#define MAXSIZE n
int queue[MAXSIZE]；
int front,rear；
算法 1-12描述,
step1 判别队列是否已满 ;
step2 队尾指针后移一个位置,将新
结点元素值存入当前结点单元。
下一页
上一页
停止放映
第 40 页
循环队列入队操作程序
addqueue(int x)
{ if (front = = （ rear＋１） % MAXIZE)
{ printf(“循环队列已满 \n”);
exit(1);
}
else
{ rear = （ rear＋１） % MAXSIZE;
queue[rear] = x ;
}
}
下一页
上一页
停止放映
第 41 页
（５）循环队列出队操作
循环队列出队操作
算法 1-13描述,
step1 判别队列是否为空 ;若空,
则显示队列 ‘ 下溢 ’ ;
step2 队头指针后移一个位置。
Step3 返回该位置上的元素,
下一页
上一页
停止放映
第 42 页
循环队列出队操作程序
Int delqueue( )
{ int y;
if ( front = = rear )
{ printf(, 循环队列已空 \n”) ;
y = -1 ；
}
else
{ front = (front+1) % MAXSIZE；
y = queue[front] ；
}
return y ；
}
下一页
上一页
停止放映
第 43 页
5、队列的链式存储结构
? (1)概念
? 用 带头结点 的单链表作为队列的存储结构，称
为队列的链式存储结构。
? （２）存储结构的 C语言描述，
struct qnode {
int data ；
struct qnode * next；
} ；
typedef struct qnode QNODE ；
QNODE *front,*rear； ／＊队头队尾＊／
data next
数据域 指针域
下一页
上一页
停止放映
第 44 页
（３）链队列为空的表示
链队列为空,
Queue.front = Queue.rear
表示形式：
非空队列,
front
rear ^
front
rear ^..,ana2a1
链队满的条件为,T = NULL。 T 为新创建的结点,
下一页
上一页
停止放映
第 45 页
（４）链队列的入队操作
算法 1-14描述,
step1 申请建立一个新结点 T;
step2 判别 T是否为空 ;若空,表示
队列已满 ;
step3 非空,将 T插入链中,修改
rear指针。
下一页
上一页
停止放映
第 46 页
链队列的入队操作
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 ;
}
}
下一页
上一页
停止放映
第 47 页
（５）链队列的出队操作
出队操作要考虑两种情况 ;
? 当队列长度为 1时,除了修改队头指针外,还要
修改队尾指针。
? 当队列长度大于 1时,只修改队头指针即可。
an ^frontrearQueue
Queu
e
front
rear ^ an ^
T
Queue
Queue
front
rear
rear
front
a1 an ^
a1
a2,..
a2 ^,.,an ^
下一页
上一页
停止放映
第 48 页
链队列的出队操作
算法 1-15描述,
step1 判别队列是否为空 ;若空,则显示
队列 ‘ 下溢 ’ ;
step2 非空,则判别队长度是否为 1;
step2.1 不为 1,修改头指针 ;
step2.2 为 1,则修改头、尾指针；
step3 释放 T。
下一页
上一页
停止放映
第 49 页
链队列的出队操作的程序
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 = front;
free(t);
}
}
下一页
上一页
停止放映
第 50 页
6、队列的应用
?OS(Operating System)中
的各种排队器,
? 缓冲区中的循环使用技术,
? 离散事件模拟,
下一页
上一页
停止放映
第 51 页
三、串
? １。什么是串
? 串是字符的有限序列，它是由单个字符
组成的特殊线性表；记为：
String=?a1 a2 a3 … an?
? n是 串的长度,n?0; n为 0表示 空串 。
? 串中任意个连续字符组成的字符子序列
称为 子串 。
? 当 2个串的长度相等，且各对应位置上
的字符都相同时，称 两个子串是相等的 。
下一页
上一页
停止放映
第 52 页
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相等且不重叠的
子串。
下一页
上一页
停止放映
第 53 页
3.串的存储结构
(1)串的顺序存储结构
有些计算机采用的 字编址方式,即数组元素的分量
占 4个字节。由此产生紧缩和非紧缩存储区别。
? 紧缩存储
一个字的存储单元中存放 4个字符；特点：
– 节省空间
– 需要二次寻址，牺牲了 CPU时间。
? 非紧缩存储
一个字的存储单元中只存放 1个字符。特点：
– 寻址快
– 浪费空间，存储密度低。
下一页
上一页
停止放映
第 54 页
(2)串的链表存储结构
链式存储结构的特点：
? 插入、删除操作效率高；
? 存储空间的利用率低；
– 对于紧缩存储 存储利用率是 50%
（ data 域 4个字节，指针域也 4个字节）；
– 对于非紧缩存储 存储利用率是 12.5%
（ 8个字节只存放一个字符）。
（ 与顺序存储结构类似也有紧缩和非紧缩存
储结构的区别） 。
下一页
上一页
停止放映
第 55 页
字符串的链式存储举例
程序
下一页
上一页
停止放映
第 56 页
指针链接情况
变量与指针
内存映像
下一页
上一页
停止放映
第 57 页
（３）堆存储结构
? 串的顺序存储和链表存储各有利弊，在实际应用
中常采用一种动态存储结构，称其为 堆结构 。
? 定义一个很大的连续空间和相应的指针结构。指
针用来指示串在堆中的位置；
? 例如，设有 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
下一页
上一页
停止放映
第 58 页
四、数组（ Array）
? 1.数组的定义
? 数组是相同类型数据元素的有限集合；
? 数组中的各个分量称为 数组元素 ；
? 每个数组元素值可以用数组名和一个下
标值唯一的确定；
数组是有限个数组元素的集合。
数组中所有元素有相同的特性。
每个数组元素由数组名和下标组成。
每组有定义的下标值有一个与该下标值对应的
数组元素值。
下一页
上一页
停止放映
第 59 页
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-c2+1)
下一页
上一页
停止放映
第 60 页
3.数组元素之间的关系
二维数组 m行 n列可以看作是 m个或 n个一维数组,
Amxn = ((a11a12… a1n),(a21a22… a2n),..
(am1am2… amn))
或, a11 a12 a1n
a21 a22 a2n
Amxn =
am1 am2 amn
......,..,..
下一页
上一页
停止放映
第 61 页
4、数组的操作
数组有两种基本的操作：
– 给定下标，存取相应的数组元素；
– 给定下标，修改相应数组元素的值。
下一页
上一页
停止放映
第 62 页
5、数组的顺序存储结构
? 数组元素是连续存放的，因此 只
能采用顺序存储结构 。
? 无论几维数组,在计算机中都是
按一维数组来存放。数组存放通
常采用两种方式：
– 按行优先顺序 (pascal C)
– 按列优先顺序 (Fortran)
下一页
上一页
停止放映
第 63 页
按行优先顺序 存储结构
按行优先顺序存放是将数组看作若干个行向量 。
例如,二维数组 Amxn，可以看作 m个行向量，每个行
向量 n个元素。数组中的每个元素由元素的两个下
标表达式唯一的确定。
地址计算公式,
LOC（ aij） =LOC（ a11） +（（ i-1） *n+（ j-1）） *L
其中,L 是每个元素所占的存储单元。
下一页
上一页
停止放映
第 64 页
二维数组按行优先存储举例
有二维数组如下：
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
LOC（ a14） = 1 + （ 1-1） x 4 + （ 4-1） = 4
下一页
上一页
停止放映
第 65 页
按列优先顺序 存储结构
按列优先顺序存放是将数组看作若干个列向量 。
例如,二维数组 Amxn，可以看作 n个列向量，
每个列向量 m个元素。数组中的每个元素由元
素的两个下标表达式唯一的确定。
地址计算公式：
LOC（ aij） =LOC（ a11） +（（ j-1） *m+（ i-1）） *L
其中,L 是每个元素所占的存储单元。
下一页
上一页
停止放映
第 66 页
二维数组按列优先存储举例
有二维数组如下：
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（ a14） = 1 + （ 4-1） x 3 + （ 1-1） = 10
下一页
上一页
停止放映
第 67 页
６、数组的压缩存储
实际工程问题中推导出的数组常常是高阶、
含大量零元素的矩阵,或者是些有规律
排列的元素。为了节省存储空间，通常
是对这类矩阵进行压缩存储。
压缩的含义是,
– 相同值的多个元素占用一个存储单元；
– 零元素不分配存储单元。
下一页
上一页
停止放映
第 68 页
能够采用压缩存储的矩阵
? 对称矩阵 存储主对角线以上（下）的元素；
? 上（下）三角矩阵 只存储三角阵元素；
? 带状矩阵 只存储带状元素；
? 稀疏矩阵 只存储非零元素；
? 大量相同元素矩阵 存储某元素和重复个数。
下一页
上一页
停止放映
第 69 页
对称矩阵的压缩存储
对称矩阵的元素满足：
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
下一页
上一页
停止放映
第 70 页
对称矩阵的压缩存储举例
设有 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-2)/2+2= 3
LOC(a21)=2(2-1)/2+1= 2
下一页
上一页
停止放映
第 71 页
作业、思考题
1,思考题：
1) 试写出“在带头结点的单循环链表中求表长的算法”。
2) 假设一单循环链表的长度大于 1，且表中即无头结点也
无头指针。已知 S为指向链表中某结点的指针。试写出
删除表中结点 S 的算法。
3) 假设以数组 sequ[m-1]存放循环队列的元素，设变量
rear和 quelen分别为指示队尾元素位置和队中元素个
数，试写出入队和出队算法。
2,第 1章作业：
8,10,11,16
3,作业要求：
– 作业命名方式为,学号,章数 _序号
00103001_ch01.doc
答疑时间：周五晚,7:00— 9:00
网上答疑,http://202.117.35.170/bbs/bbs.asp
计算机软件基础
The software basic
of computer
主讲：赵英良
西安交通大学
计算机教学实验中心
第 3单元
线性数据结构
（二）
下一页
上一页
停止放映
第 2 页
第 2单元内容概要（一）
一、数据结构
1。基本概念：数据、数据元素、数据项、数据结构、
数据结构的形式化描述方法。
2。数据的逻辑结构：
逻辑结构的类别（集合、线性、树、图）
3。数据的物理结构及类别（顺序、链式、索引、散
列）
4。算法的描述及评价
（ 1）算法的概念：
（ 2）算法的特性：有限、确定、可行、输入、输出
（ 3）设计算法的要求：正确、可读、健壮、效率
（ 4）算法的评价：时间复杂性、空间复杂性
下一页
上一页
停止放映
第 3 页
第 2单元内容概要（二）
? 二、顺序表
1。线性表及相关概念和特征
线性表、长度、空表、前驱、后继、
均匀性、有序性、形式化定义
2。顺序表
概念、特征、描述（数组,last）
3。顺序表的操作
（ 1）判空、判满、判合法 （ 2）插入（ 3）删除
? 4。顺序表的优缺点及适用场合
– 数据连续存放、随机存取
– 逻辑上相邻，物理上也相邻
– 存储结构简单、易实现
– 插入、删除操作不便
– 存储密度大，空间利用率高
下一页
上一页
停止放映
第 4 页
第 2单元内容概要（三）
? 三、链表
? 1。单链表
? 结点、指针域、数据域、头指针、头结点。
? 2。单链表的描述
? 3。单链表的操作
? （ 1）指针操作、
? 指针说明、分配存储空间、判空、判满、释放
空间
? （ 2）查找操作 （ 3）插入 （ 4）删除
? 4。单链表的特点及适用场合
? 5。单循环链表、双向链表、双向循环链表
描述、建立、判空、查找、插入、删除
下一页
上一页
停止放映
第 5 页
本单元内容
? 栈、队列、数组、串 的,
– 有关 概念
– 逻辑结构及特点
– 存储结构
– 有关 操作
? 涉及章节,第 1章的
1.3 栈和队列 (P32~P46)
1.4 串和数组 (P47~P55)
下一页
上一页
停止放映
第 6 页
一、栈
1。栈及相关概念
堆栈 (Stack)
– 栈是允许在同一端进行插入和删除操作的
特殊线性表。
– 允许进行插入和删除操作的一端称为 栈顶
(top)，另一端为 栈底 (bottom)； 栈底固定，
而栈顶浮动 ；
– 栈中元素个数为零时称为 空栈 。
– 栈结构也称为后进先出表（ LIFO）。
栈、栈顶、栈底、空栈
后进先出表 栈底固定，而栈顶浮动
下一页
上一页
停止放映
第 7 页
栈有关概念
栈顶指针
在栈操作过程中，有一个专门的栈指针（习惯
上称它为 TOP），指出栈顶元素所在的位置。
栈空的条件,top = -1
栈满的条件,top = MAXSIZE-1
栈上溢
栈空间是有限的，若栈已满，再进行入栈操作
时，就要产生上溢。
栈下溢
若栈空，再要执行出栈操作，则会发生下溢。
下一页
上一页
停止放映
第 8 页
2、栈的基本运算
? Setnull（ Stack） 置栈为空；
? Empty（ Stack） 判定栈是否为空；
? Push（ Stack,x） 进栈操作，在栈顶插入元素；
? Pop（ Stack） 出栈操作，删除栈顶元素；
? Gettop（ Stack） 取栈顶元素
下一页
上一页
停止放映
第 9 页
例 1-10
有三个元素的进栈序列是 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
下一页
上一页
停止放映
第 10 页
3、栈的顺序存储结构
? （ 1） 栈的顺序存储结构, 实际上是一维
数组 。
? （ 2） 顺序栈, 栈的顺序存储结构称为顺
序栈 。
? 栈的操作只能在一端进行；即栈顶位置随
进栈和出栈而变化 。
? （ 3） 顺序栈的 C语言描述 (初始化, 定义 )：
#define MAXSIZE n
int stack[MAXSIZE];
int top = -1;
下一页
上一页
停止放映
第 11 页
栈操作举例
a1 a2 …… a n
栈底 栈顶
MAXSIZE
TOP
1.
top=-1
A B C2.
(空栈 ) top=2 (A,B,C进栈）
A B3.
top=1 (C出栈）
4,A B C D E F
top=MAXSIZE-1
(栈满）
下一页
上一页
停止放映
第 12 页
(4) 算法 1-8 进栈算法
? 算法步骤,
– step1
判别栈满否，若满，则显示栈溢
出信息，停止执行；否则，执行
step 2；
– Step2
栈顶指针 top上移 (加 1)；
– Step3
在 top所指的位置插入元素 x。
下一页
上一页
停止放映
第 13 页
算法 1-8 进栈算法程序
push（ int x）
{ if（ top = = MAXSIZE -1） /* 判满? */
{ printf（, 栈上溢 ！ \n”） ;
exit （ 1） ;
}
else /* 不满，则可以进栈 */
{
top + +； /* 栈指针加 1 */
stack [ top ] = x ； /* 元素 x进栈 */
}
}
示例
下一页
上一页
停止放映
第 14 页
(5) 算法 1-9 出栈算法
? 算法步骤,
– step1 判别栈是否为空；若空，则输出
栈下溢信息，并停止执行；否则，
执行 step2；
– step2 弹出（删除）栈顶元素；
– step3 栈顶指针 top下移 (减 1)。
– step4 返回出栈元素
下一页
上一页
停止放映
第 15 页
算法 1-9 出栈算法程序
pop（ ）
{ int x;
if( top = = -1） /* 判空 */
{ printf(,栈下溢 \n”);
exit(1);
}
else /* 出栈 */
{ x = stack [ top ]；
top - - ； /* 栈顶指针 减 1*/
}
return x ；
} 示例
int
下一页
上一页
停止放映
第 16 页
4、多栈共享问题
? 如何充分利用栈空间，这是解决存储空间紧张这样一个
实际矛盾所要考虑的问题。
? 作为一种策略，就是多栈共享一个栈空间。具体作法是：
– 对两栈共享情况来说,将两个栈底分别设在两端，
两个栈顶指针 top1和 top2相对中间位置动态移动，
两个栈之间的分界线是不定的。
a.
b.
c.
top1 =-1 top2=MAXSIZE
空栈
top1 top2
栈 1、栈 2均有若干元素
top1 top2
栈满的情况
下一页
上一页
停止放映
第 17 页
5、栈的链式存储结构
? 由前面介绍的链表结构可知，链结构
操作灵活。对栈结构也是一样的。
? 顺序栈最多可用于 2个栈的共享，对
于更多的栈就难于表达了。
? 对于最大空间需要量事先不知的情况，
就不能使用顺序栈了。这时，就需要
采用链栈。
链栈：栈的链式存储结构
下一页
上一页
停止放映
第 18 页
链栈存储结构
? (1) 链栈存储结构的 C语言描述：
struct snode {
int data;
struct snode *link;
};
typedeef struct snode SNODE ;
? 链栈为空的条件：
top = NULL
? 链栈为满的条件,
t = NULL
t 为申请的结点,为 NULL表示失败,
下一页
上一页
停止放映
第 19 页
链栈示意图
a1
a2
a3
^ 栈底
top 栈顶
…...
ai
下一页
上一页
停止放映
第 20 页
(2) 算法 1-10 进栈操作
算法 1-10操作步骤,
? step1 申请一个链栈结点,若
t=NULL,则表示链满 ;否则,执行
step2 ;
? step2 在 top所指结点之前插入
新结点,并将 top指向新申请的结
点 t。
下一页
上一页
停止放映
第 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;
}
}
下一页
上一页
停止放映
第 22 页
(3) 算法 1-11 出栈操作
算法 1-11操作步骤,
? step1 若链栈为空，则输出栈溢出信息；
否则，执行 step 2。
? step2 (保存 top)并使 top 指向被删除结点
的后继结点,删除 top所指结点，。
? step 3 释放被删除结点的存储空间。 返回
出栈元素值
下一页
上一页
停止放映
第 23 页
算法 1-11 出栈操作程序
int 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) ;
}
return x;
}
下一页
上一页
停止放映
第 24 页
6.栈的应用
? （ 1） 举例 1 表达式计算
? 计算表达式，首先要正确地定义运算规则：
– 先乘除、后加减
– 从左到右
– 先括号内，再括号外
? 为了让计算机能识别表达式，规定：
– 表达式由操作数（ Operand）和操作符
（ Operator）和定界符（ Delimiter）组成。
例如,#3*（ 7-2） #；
– 实际处理表达式是用两个栈结构 OPTR（算符）
和 OPND（操作数）加运算规则组成；
四
则
运
算
下一页
上一页
停止放映
第 25 页
计算表达式算法步骤
? Step1 初始化，清空 OPTR和 OPND，将左定界符
压 OPTR栈；
? Step2 循环输入表达式中的每个字符
– 若输入操作数，则进 OPND栈
– 若是算符，则和 OPTR栈顶元素进行比较，按规则进行
相应操作
– 操作服从优先关系表
? Q1<Q2 Q2入 OPTR栈，再读入下一个元素
? Q1=Q2 Q1出 OPTR栈，脱括号，再读一个元素
? Q1>Q2 Q1出 OPTR栈，从 OPND中取两个数运算
? 结果入栈 OPND
? Step3 直到出现右定界符为止。
? 举例，计算,3*（ 7-2）
输入,3*（ 7-2） #
下一页
上一页
停止放映
第 26 页
计算表达式的处理步骤
步骤 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））
下一页
上一页
停止放映
第 27 页
举例 2（递归过程实现）
（ 2）递归规程的实现
计算 5的阶乘（ 5！ =5X4X3X2X1）
int f(n){
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)
下一页
上一页
停止放映
第 28 页
（３）举例３ N阶 Hanoi塔问题
? 假设有 A,B,C三座塔。在 X塔上插有 n个直
径大小不同、以小到大编号为 1,2,…, n
的圆盘。现要求将 A轴上的 n个圆盘移至 C塔
上，并按同样顺序叠排。移动圆盘的规则为：
1）每次只能移动一个圆盘；
2）圆盘可以插在 A,B,C的任意一个上；
3）任何时刻都不能将较大的圆盘压在较小
的圆盘之上。
移动方法：先将 (n-1)个圆盘从Ａ移到Ｂ，将
第 n个原盘从Ａ移到Ｃ，再将（ n-1）个圆盘
从Ｂ移到Ｃ
下一页
上一页
停止放映
第 29 页
Hanoi问题的实现程序 (主要部分 )
void f(int n,int a1,int b1,int c1)
{
if(n==1) /* there is only one element,a1->c1 */
{
pop(a1); push(c1);
}
else
{ f(n-1,a1,c1,b1); /* (n-1) from a1 to b1 */
pop(a1); /* the last one from a1 to c1 */
push(c1);
f(n-1,b1,a1,c1); /* last, (n-1) from b1 to c1 */
}
下一页
上一页
停止放映
第 30 页
二、队列
? １。队列的基本概念
? 队列 是一种特殊的线性表，它只允许在表的前
端（ front）进行删除操作，而在表的后端
（ rear）进行插入操作。
? 进行插入操作的端称为 队尾,进行删除操作的
端称为 队头 。
? 队列中没有元素时，称为 空队列 。
? 队列具有先进先出（ FIFO）的 特点 。
a1 a2 … a n 入队插入出队删除
front rear
传送带
下一页
上一页
停止放映
第 31 页
2、队列的操作
Setnull（ Q） 清空队列
Empty（ Q） 判别队列是否为空；空，取,T.;
非空,取值为,F.。
Addqueue（ Q） 插入操作
Delqueue（ Q） 删除操作
Frontqueue（ Q）取队头元素
下一页
上一页
停止放映
第 32 页
3、队列的顺序存储结构
(1)描述
C语言中顺序存储结构采用一维数组结构，
描述如下：
#define MAXSIZE n
int queue[MAXSIZE]；
int front,rear;
（２）约定
front为 队头指针,指示队头元素的的前
一个位置 ;
rear 为 队尾指针,指示队尾元素的位置。
下一页
上一页
停止放映
第 33 页
（３）基本操作
初 始 时, front=-1; rear=-1;
front= =rear 队空
X入队操作, rear=rear+1;
queue[rear]=x;
出队操作, front=front+1;
x=queue[front];
return x;
队 空, front= =rear;
队 满,rear= =(MAXSIZE-1);?
初始化、入队、出队、队空？、队满？
下一页
上一页
停止放映
第 34 页
举例：顺序队列的入队、出队操作
（ 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在变
下一页
上一页
停止放映
第 35 页
举例、顺序队列的入队、出队操作
（ D） F,G,H入队
(B） D,E,F,G,H出队，出现假, 溢出,
注,一方面队列中是空的，另一方面又出现溢出。
显然，这是逻辑设计上的问题。
front
front rear
D E F G H
rear
下一页
上一页
停止放映
第 36 页
4,循环队列
? （１）循环队列的概念
? 如果使当 rear = MAXSIZE 时，即超过队列末端时，
令 rear = 0；从而使队列的首尾相连接，只有当
队列中真正没有空位置时，才产生溢出。
? 设定 queue[0]接在 queue[MAXSIZE-1]之后,使得
if （ rear > MAXSIZE-1 ）
rear = 0 ;
else
rear＝ rear + 1;
这样构成循环队列。
下一页
上一页
停止放映
第 37 页
(2)循环队列的指针移动
（ 1） 队头指针
front = (front+1)% MAXSIZE；
等价于,
if（ (front+1) >=MAXSIZE）
front = 0 ;
else
front ＝ front + 1;
（ 2）队尾指针
rear = (rear+1) % MAXSIZE ；
等价于,
if （ (rear+1) >=MAXSIZE ）
rear = 0;
else
rear＝ rear + 1;
循环队列在指针移动处理时与一般队列不同：
？ （ front+1） %MAXSIZE 与 front%MAXSIZE+1
相同吗？
下一页
上一页
停止放映
第 38 页
(3)循环队列队空、队满条件
? 队空条件
front ＝ = rear ；
? 队满条件
? (队头和队尾间有一空闲
? 单元时认为已满 )
front ＝ = （ rear＋１） % MAXSIZE
rear
front
1
2 3
MAXSIZE,..
1
2 3 4
...
i
reari+1front
...
MAXSIZE
a1
a2 a3
ai
ai+1
下一页
上一页
停止放映
第 39 页
（４） 循环队列入队操作
数据结构定义,
#define MAXSIZE n
int queue[MAXSIZE]；
int front,rear；
算法 1-12描述,
step1 判别队列是否已满 ;
step2 队尾指针后移一个位置,将新
结点元素值存入当前结点单元。
下一页
上一页
停止放映
第 40 页
循环队列入队操作程序
addqueue(int x)
{ if (front = = （ rear＋１） % MAXIZE)
{ printf(“循环队列已满 \n”);
exit(1);
}
else
{ rear = （ rear＋１） % MAXSIZE;
queue[rear] = x ;
}
}
下一页
上一页
停止放映
第 41 页
（５）循环队列出队操作
循环队列出队操作
算法 1-13描述,
step1 判别队列是否为空 ;若空,
则显示队列 ‘ 下溢 ’ ;
step2 队头指针后移一个位置。
Step3 返回该位置上的元素,
下一页
上一页
停止放映
第 42 页
循环队列出队操作程序
Int delqueue( )
{ int y;
if ( front = = rear )
{ printf(, 循环队列已空 \n”) ;
y = -1 ；
}
else
{ front = (front+1) % MAXSIZE；
y = queue[front] ；
}
return y ；
}
下一页
上一页
停止放映
第 43 页
5、队列的链式存储结构
? (1)概念
? 用 带头结点 的单链表作为队列的存储结构，称
为队列的链式存储结构。
? （２）存储结构的 C语言描述，
struct qnode {
int data ；
struct qnode * next；
} ；
typedef struct qnode QNODE ；
QNODE *front,*rear； ／＊队头队尾＊／
data next
数据域 指针域
下一页
上一页
停止放映
第 44 页
（３）链队列为空的表示
链队列为空,
Queue.front = Queue.rear
表示形式：
非空队列,
front
rear ^
front
rear ^..,ana2a1
链队满的条件为,T = NULL。 T 为新创建的结点,
下一页
上一页
停止放映
第 45 页
（４）链队列的入队操作
算法 1-14描述,
step1 申请建立一个新结点 T;
step2 判别 T是否为空 ;若空,表示
队列已满 ;
step3 非空,将 T插入链中,修改
rear指针。
下一页
上一页
停止放映
第 46 页
链队列的入队操作
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 ;
}
}
下一页
上一页
停止放映
第 47 页
（５）链队列的出队操作
出队操作要考虑两种情况 ;
? 当队列长度为 1时,除了修改队头指针外,还要
修改队尾指针。
? 当队列长度大于 1时,只修改队头指针即可。
an ^frontrearQueue
Queu
e
front
rear ^ an ^
T
Queue
Queue
front
rear
rear
front
a1 an ^
a1
a2,..
a2 ^,.,an ^
下一页
上一页
停止放映
第 48 页
链队列的出队操作
算法 1-15描述,
step1 判别队列是否为空 ;若空,则显示
队列 ‘ 下溢 ’ ;
step2 非空,则判别队长度是否为 1;
step2.1 不为 1,修改头指针 ;
step2.2 为 1,则修改头、尾指针；
step3 释放 T。
下一页
上一页
停止放映
第 49 页
链队列的出队操作的程序
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 = front;
free(t);
}
}
下一页
上一页
停止放映
第 50 页
6、队列的应用
?OS(Operating System)中
的各种排队器,
? 缓冲区中的循环使用技术,
? 离散事件模拟,
下一页
上一页
停止放映
第 51 页
三、串
? １。什么是串
? 串是字符的有限序列，它是由单个字符
组成的特殊线性表；记为：
String=?a1 a2 a3 … an?
? n是 串的长度,n?0; n为 0表示 空串 。
? 串中任意个连续字符组成的字符子序列
称为 子串 。
? 当 2个串的长度相等，且各对应位置上
的字符都相同时，称 两个子串是相等的 。
下一页
上一页
停止放映
第 52 页
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相等且不重叠的
子串。
下一页
上一页
停止放映
第 53 页
3.串的存储结构
(1)串的顺序存储结构
有些计算机采用的 字编址方式,即数组元素的分量
占 4个字节。由此产生紧缩和非紧缩存储区别。
? 紧缩存储
一个字的存储单元中存放 4个字符；特点：
– 节省空间
– 需要二次寻址，牺牲了 CPU时间。
? 非紧缩存储
一个字的存储单元中只存放 1个字符。特点：
– 寻址快
– 浪费空间，存储密度低。
下一页
上一页
停止放映
第 54 页
(2)串的链表存储结构
链式存储结构的特点：
? 插入、删除操作效率高；
? 存储空间的利用率低；
– 对于紧缩存储 存储利用率是 50%
（ data 域 4个字节，指针域也 4个字节）；
– 对于非紧缩存储 存储利用率是 12.5%
（ 8个字节只存放一个字符）。
（ 与顺序存储结构类似也有紧缩和非紧缩存
储结构的区别） 。
下一页
上一页
停止放映
第 55 页
字符串的链式存储举例
程序
下一页
上一页
停止放映
第 56 页
指针链接情况
变量与指针
内存映像
下一页
上一页
停止放映
第 57 页
（３）堆存储结构
? 串的顺序存储和链表存储各有利弊，在实际应用
中常采用一种动态存储结构，称其为 堆结构 。
? 定义一个很大的连续空间和相应的指针结构。指
针用来指示串在堆中的位置；
? 例如，设有 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
下一页
上一页
停止放映
第 58 页
四、数组（ Array）
? 1.数组的定义
? 数组是相同类型数据元素的有限集合；
? 数组中的各个分量称为 数组元素 ；
? 每个数组元素值可以用数组名和一个下
标值唯一的确定；
数组是有限个数组元素的集合。
数组中所有元素有相同的特性。
每个数组元素由数组名和下标组成。
每组有定义的下标值有一个与该下标值对应的
数组元素值。
下一页
上一页
停止放映
第 59 页
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-c2+1)
下一页
上一页
停止放映
第 60 页
3.数组元素之间的关系
二维数组 m行 n列可以看作是 m个或 n个一维数组,
Amxn = ((a11a12… a1n),(a21a22… a2n),..
(am1am2… amn))
或, a11 a12 a1n
a21 a22 a2n
Amxn =
am1 am2 amn
......,..,..
下一页
上一页
停止放映
第 61 页
4、数组的操作
数组有两种基本的操作：
– 给定下标，存取相应的数组元素；
– 给定下标，修改相应数组元素的值。
下一页
上一页
停止放映
第 62 页
5、数组的顺序存储结构
? 数组元素是连续存放的，因此 只
能采用顺序存储结构 。
? 无论几维数组,在计算机中都是
按一维数组来存放。数组存放通
常采用两种方式：
– 按行优先顺序 (pascal C)
– 按列优先顺序 (Fortran)
下一页
上一页
停止放映
第 63 页
按行优先顺序 存储结构
按行优先顺序存放是将数组看作若干个行向量 。
例如,二维数组 Amxn，可以看作 m个行向量，每个行
向量 n个元素。数组中的每个元素由元素的两个下
标表达式唯一的确定。
地址计算公式,
LOC（ aij） =LOC（ a11） +（（ i-1） *n+（ j-1）） *L
其中,L 是每个元素所占的存储单元。
下一页
上一页
停止放映
第 64 页
二维数组按行优先存储举例
有二维数组如下：
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
LOC（ a14） = 1 + （ 1-1） x 4 + （ 4-1） = 4
下一页
上一页
停止放映
第 65 页
按列优先顺序 存储结构
按列优先顺序存放是将数组看作若干个列向量 。
例如,二维数组 Amxn，可以看作 n个列向量，
每个列向量 m个元素。数组中的每个元素由元
素的两个下标表达式唯一的确定。
地址计算公式：
LOC（ aij） =LOC（ a11） +（（ j-1） *m+（ i-1）） *L
其中,L 是每个元素所占的存储单元。
下一页
上一页
停止放映
第 66 页
二维数组按列优先存储举例
有二维数组如下：
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（ a14） = 1 + （ 4-1） x 3 + （ 1-1） = 10
下一页
上一页
停止放映
第 67 页
６、数组的压缩存储
实际工程问题中推导出的数组常常是高阶、
含大量零元素的矩阵,或者是些有规律
排列的元素。为了节省存储空间，通常
是对这类矩阵进行压缩存储。
压缩的含义是,
– 相同值的多个元素占用一个存储单元；
– 零元素不分配存储单元。
下一页
上一页
停止放映
第 68 页
能够采用压缩存储的矩阵
? 对称矩阵 存储主对角线以上（下）的元素；
? 上（下）三角矩阵 只存储三角阵元素；
? 带状矩阵 只存储带状元素；
? 稀疏矩阵 只存储非零元素；
? 大量相同元素矩阵 存储某元素和重复个数。
下一页
上一页
停止放映
第 69 页
对称矩阵的压缩存储
对称矩阵的元素满足：
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
下一页
上一页
停止放映
第 70 页
对称矩阵的压缩存储举例
设有 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-2)/2+2= 3
LOC(a21)=2(2-1)/2+1= 2
下一页
上一页
停止放映
第 71 页
作业、思考题
1,思考题：
1) 试写出“在带头结点的单循环链表中求表长的算法”。
2) 假设一单循环链表的长度大于 1，且表中即无头结点也
无头指针。已知 S为指向链表中某结点的指针。试写出
删除表中结点 S 的算法。
3) 假设以数组 sequ[m-1]存放循环队列的元素，设变量
rear和 quelen分别为指示队尾元素位置和队中元素个
数，试写出入队和出队算法。
2,第 1章作业：
8,10,11,16
3,作业要求：
– 作业命名方式为,学号,章数 _序号
00103001_ch01.doc
答疑时间：周五晚,7:00— 9:00
网上答疑,http://202.117.35.170/bbs/bbs.asp
