3.3 栈
1,栈 stack的定义栈是特殊的线性表，仅在表的一端进行插入或删除操作
an
...
a2
a1
栈顶入栈 出栈栈底特点：（ 1）对栈内数据的操作总在栈顶进行
（ 2）数据进栈称为“压入” push
（ 3）数据出栈称为“弹出” pop
（ 4）遵循“后进先出”的原则 LIFO
3.3 栈输入顺序 A,B,C，输出顺序有几种？
an
...
a2
a1
栈顶入栈 出栈栈底
ABC,BAC,BCA,CBA
B
C
A
B
A
...
...
栈的顺序存储结构及运算用数组实现栈
a[max]
...
a[1]
a[0]
...
a[top] 栈顶
a[0]为栈底,top为栈顶
（ 1）定义
typedef struct stack_type{
elemtype data[MAXNUM];
int top;
}stack_type;
（ 2）进栈 push
当新元素 进 栈时，栈顶上移，新元素放在栈顶。
stack.top = stack.top + 1;
stack.data[stack.top] = new_one;
new_one
栈顶元素所在位置
a1
a2
栈的顺序存储结构及运算
...
（ 3）出栈 pop
从栈顶移出一个数据。 a[max]
...
a[1]
a[0] a1
a2
栈顶栈顶元素拷贝出栈，栈顶下移 out
out = stack.data[stack.top];
stack.top = stack.top - 1;
elemptype pop(stack_type *stack){
elemtype out;
if(stack->top <= 0) error(3);
else{
out = stack->data[stack->top];
stack->top = stack->top -1;
}
return out; }
a[top]
栈的顺序存储结构及运算
（ 4）栈空判断
stack.top = = 0
stack.top < 0
（ 5）置栈空
stack.top = -1;
栈满判断,stack.top >= MAXNUM - 1;
a[0]stack.top
栈顶元素所在位置用数组实现栈
（ 6）栈的应用例 程序的嵌套，中断的嵌套
proc A( )
......
call B( );
......
proc B( )
......
......
call C( )
......
proc C( )
......
......
......
程序 A
程序 B
程序 C
用数组实现栈
（ 6）栈的应用程序的嵌套，中断的嵌套
proc A( )
......
call B( );
......
proc B( )
......
......
call C( )
......
proc C( )
......
......
......
程序 A
程序 B
程序 C
程序 A
程序 B
程序 C
栈的链式存储结构及运算
用链表实现栈
a1 a2 an……
head
栈顶在 表头
（ 1）定义
typedef struct lstack_type{
node_type * top;
int length;
}lstack_type;
入栈出栈
top
栈的链式存储结构及运算
（ 2）压入 push
void push(stack,new_node){
new_node->next = stack->top;
stack->top = new_node;
stack->length ++;
}
（ 3）弹出 pop
node_type * pop(stack){
node_type* out;
out = stack->top;
stack->top = stack->top->next;
stack->length --;
return out;
}
a1
new
……stack->top
栈的链式存储结构及运算
（ 4）栈空判断
stack.top == NULL;
（ 5）置栈空能否简单的使用 stack.top = NULL?
如果栈中还有链点，必须逐个将链点占用的空间释放
void clean(stack){
node_type * temp;
while( ! empty(stack)){
temp = pop(stack);
free(temp); }
}
int empty(stack){
if(stack.top == NULL)
return YES;
else return NO;
}
1、逐个将链点弹出
2、释放链点空间
3.4 队列
1.队列定义
类似于排队机制的结构
队列是特殊的线性表，
节点的插入仅限于在表尾进行，
节点的删除仅限于在表头进行入队出队队头 队尾队列 特点
特点：
（ 1）对队列的操作在表的两端进行
（ 2）仅在队尾加入节点 —— 入队 enqueue
（ 3）仅在队首移出节点 —— 出队 dequeue
（ 4）遵循“先进先出”的原则 —— FIFO
入队出队队头 队尾队列的顺序存储结构及运算
2,用数组实现队列
（ 1）定义
a[0]
队首 队尾
a[1],..,..a[n] MAX
front rear
typedef struct queue_type{
elemtype data[MAXNUM];
int front;
int rear;
}queue_type;
队列的顺序存储结构及运算
（ 2）入队与出队移元素？ 移队首、尾指针
front rear
入队 出队 入队 出队入队 数组空间溢出而使操作出错循环队列的顺序存储结构及运算
3,用循环数组实现队列入队
rear = rear + 1( ) % MAXNUM
front rear
% 整除取余设 MAXNUM ＝ 5,rear＝ 4
则新元素加入队列后：
rear ＝（ 4＋ 1）％ 5＝ 0，新元素放在 a[0]内
A B C
用循环数组实现队列
front rear
frontrear
队列元素位置？
队长？
思考：
数组 Q[0,4]
1.front=1
rear=3
2.front=3
rear=1
用循环数组实现队列
队空条件
队满条件
front
rear
frontrear
front = = rear
(rear + 1) % MAXNUM = = front
如果 rear表示队尾节点的位置则有一个节点的队列的指针情况和队空时相同
front rear
用循环数组实现队列
队空条件
队满条件
front
rear
frontrear
front = = rear
(rear + 1) % MAXNUM = = front
定义,rear为指向队尾下一个可存放节点的位置队列满时还有一个空位置用循环数组实现队列
void enqueue(queue,new_one){
if( (queue->rear + 1) % MAXNUM = = queue->front )
error(1);
else{
queue->data[queue->rear] = new_one;
queue->rear = (queue->rear +1) % MAXNUM;
}
}
入队算法队列已满？
队列尾部放入新节点队尾指示向后移动一格
front rear
用循环数组实现队列
出队算法
frontrear
elemtype dequeue(queue){
elemtype out；
if( queue->rear = = queue->front )
error(2);
else{
out ＝ queue->data[queue->front];
queue->front = (queue->front +1) % MAXNUM;
}
return out；
}
用循环数组实现队列
front rear
frontrear
队列元素位置？
队长？
思考：
数组 Q[0,4]
=1 =3
=3=1
用链表实现队列
4,用链表实现队列
a1 a2 an……
front rear
（一）定义
typedef struct lqueue_type{
node_type * front;
node_type * rear;
int length;
}
用链表实现队列
（二） 入队
新链点插入到队尾
注意：队列为空时,rear和 front都要指向新元素
new_node->next = NULL;
list->rear ->next = new_node;
a1 a2 an……
front rear
new ∧→
用链表实现队列
（三） 出队
删除队首链点
注意：当队列被删空时,rear指针要置空
list->front = list->front->next;
temp = list->front;
a1 a2 an……
front rear
a2 a3 an……
front rear
3.5 二维数组（矩阵）
1.二维数组定义
行关系，列关系均是线性关系
2,二维数组的顺序存放
（一）行优先存放
计算 aij的存放位置：
a11 a12
aij
amn
a21,..
...
...
...
a11 a12..,a1na21 a22..,ai1 ai2,..ain..,am1 am2,.,amn
Loc(aij) = Loc(a11) + (( i - 1)*n + (j - 1))*S
设每个元素占据 S个存储单元计算前面有多少个元素
j
i
二维数组
（二）列优先存放
a11 a21..,am1a12 a22..,am2a1j a2j,..aii..,a1n a2n,.,amn
Loc(aij) = Loc(a11) + (( j - 1)*m + (i - 1))*S
a11 a12
aij
amn
a21
...
...
...
...
j
i
二维数组
3.矩阵的压缩存储
(1)对称矩阵，三角矩阵的压缩
对称矩阵,a[ i,j ] = a[ j,i ]
三角矩阵：上三角为 0，或下三角为 0
只存储上或下三角内的元素，节约近一半的存储空间
a11 a21a22a31a32a33a41… aii...an1 an2,.,ann
...1
3
5 6
3
4
2
7 42
1 55 3 6
0
二维数组
(1)对称矩阵，三角矩阵的压缩
i >= j 时，元素位于下三角
Loc(aij) = Loc(a11) + ( i ( i - 1) / 2 + ( j - 1))*S
i < j 时，元素位于上三角
Loc(aij) = Loc(a11) + ( j ( j - 1) / 2 + ( i - 1))*S
a11 a21a22a31a32a33a41… aii...an1 an2,.,ann
...1
3
5 6
3
4
2
7 42
1 55 3 6
0
1+2+3+…+(i -1)
二维数组
(2)稀疏矩阵
矩阵中的非零元素很少，分布没有规律
利用三元存储法
先形成三元矩阵
再按照行优先顺序方式存储。
aij 行值，列值，元素值
AMN =
行数 列数 非零元素个数行值 列值 元素值
...
第一行第一个非零元素
...
行值 列值 元素值 第二个非零元素二维数组
稀疏矩阵压缩存储例
1
0
0 6
3
0
0
0 00
0 01
0
0
X48 ＝
0
0 0
0
0
0000
4
1
2 4
3
1
1
2 6
1
34
A63 ＝
5
1
73
58
0
0
5
0
0
0
0
0
行数 列数 非零元素个数
a[18] = {4,8,5,1,1,1,2,4,1,3,2,6,3,7,5,4,1,3}
二维数组? 稀疏矩阵三元组定义
1)定义三元组元素
2)定义三元组
typedef struct tuple3tp{
int row_num; /*行号 */
int col_num; /*列号 */
elemtype value; /*元素值 */
} tuple3tp
typedef struct tuple3{
int row; /*行数 */
int col; /*列数 */
int num; /*非零元素个数 */
tuple3tp data[ MAXNUM];/* 三元组 */
}tuple3;
小结数据结构数据逻辑结构数据存储结构算法线性结构、栈、队列、数组用数组实现（顺序 XX）
用链表实现（链接 XX）
顺序表与线性链表（单链表、双链表）
顺序栈与链栈（应用－－回溯性）
顺序队列 循环队列二维数组的存储（行优先、列优先，定位）
数组的压缩（压缩定位，三元组法）
与 循环链表？与链队列作业
教材 P120 1— 6
1,栈 stack的定义栈是特殊的线性表，仅在表的一端进行插入或删除操作
an
...
a2
a1
栈顶入栈 出栈栈底特点：（ 1）对栈内数据的操作总在栈顶进行
（ 2）数据进栈称为“压入” push
（ 3）数据出栈称为“弹出” pop
（ 4）遵循“后进先出”的原则 LIFO
3.3 栈输入顺序 A,B,C，输出顺序有几种？
an
...
a2
a1
栈顶入栈 出栈栈底
ABC,BAC,BCA,CBA
B
C
A
B
A
...
...
栈的顺序存储结构及运算用数组实现栈
a[max]
...
a[1]
a[0]
...
a[top] 栈顶
a[0]为栈底,top为栈顶
（ 1）定义
typedef struct stack_type{
elemtype data[MAXNUM];
int top;
}stack_type;
（ 2）进栈 push
当新元素 进 栈时，栈顶上移，新元素放在栈顶。
stack.top = stack.top + 1;
stack.data[stack.top] = new_one;
new_one
栈顶元素所在位置
a1
a2
栈的顺序存储结构及运算
...
（ 3）出栈 pop
从栈顶移出一个数据。 a[max]
...
a[1]
a[0] a1
a2
栈顶栈顶元素拷贝出栈，栈顶下移 out
out = stack.data[stack.top];
stack.top = stack.top - 1;
elemptype pop(stack_type *stack){
elemtype out;
if(stack->top <= 0) error(3);
else{
out = stack->data[stack->top];
stack->top = stack->top -1;
}
return out; }
a[top]
栈的顺序存储结构及运算
（ 4）栈空判断
stack.top = = 0
stack.top < 0
（ 5）置栈空
stack.top = -1;
栈满判断,stack.top >= MAXNUM - 1;
a[0]stack.top
栈顶元素所在位置用数组实现栈
（ 6）栈的应用例 程序的嵌套，中断的嵌套
proc A( )
......
call B( );
......
proc B( )
......
......
call C( )
......
proc C( )
......
......
......
程序 A
程序 B
程序 C
用数组实现栈
（ 6）栈的应用程序的嵌套，中断的嵌套
proc A( )
......
call B( );
......
proc B( )
......
......
call C( )
......
proc C( )
......
......
......
程序 A
程序 B
程序 C
程序 A
程序 B
程序 C
栈的链式存储结构及运算
用链表实现栈
a1 a2 an……
head
栈顶在 表头
（ 1）定义
typedef struct lstack_type{
node_type * top;
int length;
}lstack_type;
入栈出栈
top
栈的链式存储结构及运算
（ 2）压入 push
void push(stack,new_node){
new_node->next = stack->top;
stack->top = new_node;
stack->length ++;
}
（ 3）弹出 pop
node_type * pop(stack){
node_type* out;
out = stack->top;
stack->top = stack->top->next;
stack->length --;
return out;
}
a1
new
……stack->top
栈的链式存储结构及运算
（ 4）栈空判断
stack.top == NULL;
（ 5）置栈空能否简单的使用 stack.top = NULL?
如果栈中还有链点，必须逐个将链点占用的空间释放
void clean(stack){
node_type * temp;
while( ! empty(stack)){
temp = pop(stack);
free(temp); }
}
int empty(stack){
if(stack.top == NULL)
return YES;
else return NO;
}
1、逐个将链点弹出
2、释放链点空间
3.4 队列
1.队列定义
类似于排队机制的结构
队列是特殊的线性表，
节点的插入仅限于在表尾进行，
节点的删除仅限于在表头进行入队出队队头 队尾队列 特点
特点：
（ 1）对队列的操作在表的两端进行
（ 2）仅在队尾加入节点 —— 入队 enqueue
（ 3）仅在队首移出节点 —— 出队 dequeue
（ 4）遵循“先进先出”的原则 —— FIFO
入队出队队头 队尾队列的顺序存储结构及运算
2,用数组实现队列
（ 1）定义
a[0]
队首 队尾
a[1],..,..a[n] MAX
front rear
typedef struct queue_type{
elemtype data[MAXNUM];
int front;
int rear;
}queue_type;
队列的顺序存储结构及运算
（ 2）入队与出队移元素？ 移队首、尾指针
front rear
入队 出队 入队 出队入队 数组空间溢出而使操作出错循环队列的顺序存储结构及运算
3,用循环数组实现队列入队
rear = rear + 1( ) % MAXNUM
front rear
% 整除取余设 MAXNUM ＝ 5,rear＝ 4
则新元素加入队列后：
rear ＝（ 4＋ 1）％ 5＝ 0，新元素放在 a[0]内
A B C
用循环数组实现队列
front rear
frontrear
队列元素位置？
队长？
思考：
数组 Q[0,4]
1.front=1
rear=3
2.front=3
rear=1
用循环数组实现队列
队空条件
队满条件
front
rear
frontrear
front = = rear
(rear + 1) % MAXNUM = = front
如果 rear表示队尾节点的位置则有一个节点的队列的指针情况和队空时相同
front rear
用循环数组实现队列
队空条件
队满条件
front
rear
frontrear
front = = rear
(rear + 1) % MAXNUM = = front
定义,rear为指向队尾下一个可存放节点的位置队列满时还有一个空位置用循环数组实现队列
void enqueue(queue,new_one){
if( (queue->rear + 1) % MAXNUM = = queue->front )
error(1);
else{
queue->data[queue->rear] = new_one;
queue->rear = (queue->rear +1) % MAXNUM;
}
}
入队算法队列已满？
队列尾部放入新节点队尾指示向后移动一格
front rear
用循环数组实现队列
出队算法
frontrear
elemtype dequeue(queue){
elemtype out；
if( queue->rear = = queue->front )
error(2);
else{
out ＝ queue->data[queue->front];
queue->front = (queue->front +1) % MAXNUM;
}
return out；
}
用循环数组实现队列
front rear
frontrear
队列元素位置？
队长？
思考：
数组 Q[0,4]
=1 =3
=3=1
用链表实现队列
4,用链表实现队列
a1 a2 an……
front rear
（一）定义
typedef struct lqueue_type{
node_type * front;
node_type * rear;
int length;
}
用链表实现队列
（二） 入队
新链点插入到队尾
注意：队列为空时,rear和 front都要指向新元素
new_node->next = NULL;
list->rear ->next = new_node;
a1 a2 an……
front rear
new ∧→
用链表实现队列
（三） 出队
删除队首链点
注意：当队列被删空时,rear指针要置空
list->front = list->front->next;
temp = list->front;
a1 a2 an……
front rear
a2 a3 an……
front rear
3.5 二维数组（矩阵）
1.二维数组定义
行关系，列关系均是线性关系
2,二维数组的顺序存放
（一）行优先存放
计算 aij的存放位置：
a11 a12
aij
amn
a21,..
...
...
...
a11 a12..,a1na21 a22..,ai1 ai2,..ain..,am1 am2,.,amn
Loc(aij) = Loc(a11) + (( i - 1)*n + (j - 1))*S
设每个元素占据 S个存储单元计算前面有多少个元素
j
i
二维数组
（二）列优先存放
a11 a21..,am1a12 a22..,am2a1j a2j,..aii..,a1n a2n,.,amn
Loc(aij) = Loc(a11) + (( j - 1)*m + (i - 1))*S
a11 a12
aij
amn
a21
...
...
...
...
j
i
二维数组
3.矩阵的压缩存储
(1)对称矩阵，三角矩阵的压缩
对称矩阵,a[ i,j ] = a[ j,i ]
三角矩阵：上三角为 0，或下三角为 0
只存储上或下三角内的元素，节约近一半的存储空间
a11 a21a22a31a32a33a41… aii...an1 an2,.,ann
...1
3
5 6
3
4
2
7 42
1 55 3 6
0
二维数组
(1)对称矩阵，三角矩阵的压缩
i >= j 时，元素位于下三角
Loc(aij) = Loc(a11) + ( i ( i - 1) / 2 + ( j - 1))*S
i < j 时，元素位于上三角
Loc(aij) = Loc(a11) + ( j ( j - 1) / 2 + ( i - 1))*S
a11 a21a22a31a32a33a41… aii...an1 an2,.,ann
...1
3
5 6
3
4
2
7 42
1 55 3 6
0
1+2+3+…+(i -1)
二维数组
(2)稀疏矩阵
矩阵中的非零元素很少，分布没有规律
利用三元存储法
先形成三元矩阵
再按照行优先顺序方式存储。
aij 行值，列值，元素值
AMN =
行数 列数 非零元素个数行值 列值 元素值
...
第一行第一个非零元素
...
行值 列值 元素值 第二个非零元素二维数组
稀疏矩阵压缩存储例
1
0
0 6
3
0
0
0 00
0 01
0
0
X48 ＝
0
0 0
0
0
0000
4
1
2 4
3
1
1
2 6
1
34
A63 ＝
5
1
73
58
0
0
5
0
0
0
0
0
行数 列数 非零元素个数
a[18] = {4,8,5,1,1,1,2,4,1,3,2,6,3,7,5,4,1,3}
二维数组? 稀疏矩阵三元组定义
1)定义三元组元素
2)定义三元组
typedef struct tuple3tp{
int row_num; /*行号 */
int col_num; /*列号 */
elemtype value; /*元素值 */
} tuple3tp
typedef struct tuple3{
int row; /*行数 */
int col; /*列数 */
int num; /*非零元素个数 */
tuple3tp data[ MAXNUM];/* 三元组 */
}tuple3;
小结数据结构数据逻辑结构数据存储结构算法线性结构、栈、队列、数组用数组实现（顺序 XX）
用链表实现（链接 XX）
顺序表与线性链表（单链表、双链表）
顺序栈与链栈（应用－－回溯性）
顺序队列 循环队列二维数组的存储（行优先、列优先，定位）
数组的压缩（压缩定位，三元组法）
与 循环链表？与链队列作业
教材 P120 1— 6
