lixuejun@swust.edu.cn
顺序存储结构的表、堆栈和队列
3.1 顺序存储结构
3.2 表和顺序表
3.3 堆栈和顺序堆栈
3.4 队列和顺序队列
3.5 优先级队列和顺序优先级队列
3.6 顺序存储结构的特点计算机学院信息教研室
DS
lixuejun@swust.edu.cn
线性结构线性 结构的特点：线形元素之间的逻辑关系为除第一个元素和最后一个元素之外，每个数据元素都只有一个前驱元素和一个后继元素。
表、堆栈和队列都属于线形结构计算机学院信息教研室
DS
lixuejun@swust.edu.cn
线性结构常见三种线性结构的区别：
表可以在任何位置进行插入和删除堆栈只可以表头位置插入和删除队列是只可在表尾位置插入、在表头位置删除计算机学院信息教研室
DS
lixuejun@swust.edu.cn
存储结构存储结构：数据元素在计算机中的存储方式。
顺序存储结构链式存储结构间接地址仿真指针计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序存储结构用户向系统申请一块地址连续的空间用于存储数据元素集合，这样，任意两个在逻辑上相邻的数据元素在物理上也相邻。
C++中，使用数组向系统申请连续空间。
有动态数组和静态数组两种。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序存储结构使用静态数组申请连续空间使用数组定义语句 []
当程序运行超出该静态数组定义的范围时，系统自动回收该静态数组的地址空间。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序存储结构
#include<stdio.h>
Const int MaxSize =
100;
Void main(void)
{
int I;
int temp[MaxSize];
For(I=o;I<6;I++)
{
Temp[I] = I+1;
Printf(“temp[%d]=
%d\n”,I,temp[i]);
}
}
计算机学院信息教研室
DS
程序退出主函数时,系统自动回收分配给 temp的地址空间静态数组
lixuejun@swust.edu.cn
顺序存储结构动态数组 申请 连续空间使用 动态存储分配运算符 (new).
动态数组存储空间的 回收 方法,当不在需要该动态数组时,使用 动态存储释放运算符 (delete).
计算机学院信息教研室
DS 动态数组
lixuejun@swust.edu.cn
顺序存储结构
#include<iostream.h>
#include<stdlib.h>
Void main(void)
{
int I,*temp;
const int MaxSize=100;
temp=new int[MaxSize];
For(I=0;I<6;I++)
{
Temp[I] = I+1;
cout<<“I=”<<I<<
“temp[i]=“<<temp[i]<<
endl”;
}
delete[ ]temp;
}
计算机学院信息教研室
DS 动态数组申请和释放由用户通过调用 new和 delete运算符完成
lixuejun@swust.edu.cn
表和顺序表表 (List)：可以在 任何位置 进行插入和删除 操作的有 n个 相同类型数据元素 组成的线性结构,N是表的长度。 n=0的表称为空表。
表的逻辑关系表的存储结构
顺序表（ Sequent List）,用顺序存储结构存储的表。
链式表计算机学院信息教研室
DS
lixuejun@swust.edu.cn
把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
假设线性表的每个元素需占用 l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第 i+1个数据元素的存储位置 LOC( a i+1)和第 i个数据元素的存储位置 LOC(a i )之间满足下列关系：
LOC(a i+1)=LOC(a i)+l
线性表的第 i个数据元素 ai的存储位置为：
LOC(ai)=LOC(a1)+(i-1)*l
顺序表
lixuejun@swust.edu.cn
顺序表的类定义数据成员包括,1.数组 2.数组的最大元素个数 3.当前数组元素的个数。
操作,初始化构造表 在表的某一位置插入一个元素 在表的某一位置删除一个元素 定位某个数据元素在表中的存储位置 取表的某个存储位置的数据元素 判表是否为空计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
#include <iostream.h>
#include <stdlib.h>
const int MaxListSize
= 100;
class SeqList
{
private:
DataType
data[MaxListSize];
int size;
public,
SeqList(void); // constructor
~SeqList (void)；
int ListSize(void) const;
int ListEmpty(void) const;
int Find (DataType& item) const;
DataType GetData(int pos) const;
void Insert(const DataType&
item,int pos);
DataType Delete(const int pos);
void ClearList(void);
};
计算机学院信息教研室
DS
//SeqList.h
lixuejun@swust.edu.cn
表和顺序表
#include "seqlist.h"
//构造函数。置顺序表的数据元素个素为 0
SeqList::SeqList (void),size(0){}
//析构函数。
SeqList::~SeqList (void){}
//返回顺序表的元素个数 size
int SeqList::ListSize(void) const
{
return size;
}
计算机学院信息教研室
DS
Seqlist.cpp
lixuejun@swust.edu.cn
表和顺序表
//判顺序表空否，为空返回 1，不空返回 0
int SeqList::ListEmpty(void) const
{
if (size == 0) return 1;
else return 0;
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
//定位元素 item的位置，返回值为 item在顺序表中的位置；返回值为 -1表示不存在
int SeqList::Find(DataType& item) const
{
if(size == 0) return -1;
int i = 0;
while (i < size && item != data[i])
i++; //寻找 item
if (i < size)
return i; // return True
else
return -1; // return False
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
//返回顺序表中位置 pos上的元素。参数出错时退出
DataType SeqList::GetData(int pos) const
{
//取的元素序号必须在 0至 size-1之间
if (pos < 0 || pos > size-1)
{
cerr << "参数 pos越界出错 !" << endl;
exit(1);
}
return data[pos];
}
计算机学院信息教研室
DS
线性表的插入和删除
1、线性表的插入操作
（ a1,a2,… ai-1,ai,… an)----->(a1,a2,… ai-1,b,ai,… an)
一般地，在第 i个数据元素之前插入一个元素时，需要将第 n至第 i个元素向后移动一个位置。此时，需移动位置的元素个数为 n-i+1个。
lixuejun@swust.edu.cn
算法思想：
① 进行合法性检查,1<=i<=n+1；
② 判断线性表是否已满；
③ 将第 n个至第 i个元素逐一后移一个单元；
④ 在第 i个位置处插入新元素；
⑤ 将表的长度加 1。
lixuejun@swust.edu.cn
表和顺序表
//在指定位置 pos处插入一个数据元素 item
void SeqList::Insert(const DataType& item,int pos)
{
if (size==MaxListSize)
{
cerr<<"顺序表已满无法插入 !"<<endl;
exit(1);
}
if (pos<0||pos>size)//当 pos等于 size时表示插入在最后
{
cout<<"参数 pos越界出错 !";
exit(1);
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
//从后向前把前一个元素迁移到后一个元素位置直到存储位置 pos为止
for(int i=size;i>pos;i--)
data[i]=data[i-1];
data[pos] = item; //在 pos位置插入 item
size++; //数据元素个数 size加 1
}
计算机学院信息教研室
DS
2、线性表的删除操作
（ a1,a2,… ai-1,ai,ai+1,… an)----->(a1,a2,… ai-1,ai+1,… an)
一般地，删除第 I个元素时需将第 I+1至第 n个元素依次向前移动一个位置，此时，元素移动的个数为 n-I个。
lixuejun@swust.edu.cn
算法思想：
① 进行合法性检查,I是否满足 1<=I<=n；
② 判线性表是否已空,L.length=0；
③ 将第 I+1至第 n个元素逐一向前移一个位置；
④ 将表的长度减 1。
lixuejun@swust.edu.cn
表和顺序表
//删除指定位置 pos上的数据元素并返回
DataType SeqList::Delete(const int pos)
{
if(size==0)
{
cerr<<"顺序表已空无元素可删 !"<<endl;
exit(1);
}
//删除元素序号必须在 0至 size-1之间
if(pos<0||pos>size-1)
{
cerr<<"参数 pos越界出错 !"<<endl;
exit(1);
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
DataType temp=data[pos];
//从 pos至 size-2逐个元素左移,data[size-1]移入
data[size-2]中
for(int i = pos;i<size-1;i++)
data[i] = data[i+1];
size--; // 数据元素个数 size减 1
return temp;
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
//置顺序表为空
void SeqList::ClearList(void)
{
size = 0; //数据元素个数 size置为初始化值
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
typedef int DataType; //具体应用时定义的数据类型 Datatype
#include "seqlist.h" //类 Seqlist的定义和实现头文件
void main(void)
{
SeqList myList; //插入 5个整型元素
for(int i=0;i<5;i++)
myList.Insert(i+10,i);
cout<<"测试 GetData()成员函数结果如下,"<<endl;
for(i=0;i<5;i++)
cout<<"测试 Delete()成员函数结果如下,"<<endl;
for(i=0;i<5;i++)
cout<<myList.Delete(0)<<" ";
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
typedef char Datatype; //具体应用时定义的数据类型
Datatype
#include "seqlist.h" //类 Seqlist的定义和实现头文件
void main(void)
{
SeqList list;
//插入 5个字符型元素
for(int i=0;i<5;i++)
list.Insert('A'+i,i);
for(i=0;i<5;i++)
cout<<list.Delete(0)<<" ";
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序表上插入、删除算法的效率分析平均次数如果保持原来的数据元素序列时插入、删除算法的时间复杂度均为 O(n).定位一个数据元素的时间复杂度为 O(n),其余的 算法的时间复杂度均为 O(1)
如果不必保持原来的数据元素序列时插入、删除算法为 O(1),定位一个数据元素的时间复杂度为 O(n),其余的 算法的时间复杂度均为 O(1)
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
3.3 堆栈和顺序堆栈
3.3.1 顺序堆栈类定义
3.3.2 顺序堆栈应用计算机学院信息教研室
DS
lixuejun@swust.edu.cn
堆栈概念堆栈（ Stack）
1,特殊的线性表,只可以表头位置插入和删除
2,允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。
计算机学院信息教研室
DS
进栈或入栈出栈或退栈空 栈特点：后进先出
lixuejun@swust.edu.cn
1 顺序栈用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设指针 top指示栈顶元素在顺序栈中的位置,
top
base Abase
top
A
B
C
D
E
base
top
top
base A
B
lixuejun@swust.edu.cn
顺 序 栈 举 例例：如果进站的车厢序列为 1 2 3 4 5 6，
则能否得到下列出站序列，并说明为什么不能得到或者如何得到
4 3 5 6 1 2
1 3 5 4 2 6
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈类定义
#include <iostream.h>
#include <stdlib.h>
const int MaxStackSize = 100;
class SeqStack
{
private:
Datatype
data[MaxStackSize];
int top;
public:
SeqStack(void){top=0;}
~SeqStack(void){};
void Push(const
DataType& item); //元素
item入栈
DataType Pop(void);
//出栈元素并返回
DataType Peek(void) const;
//读栈顶元素并返回
int StackEmpty(void) const
{
return(top==0);
};
int GetSize(void) const
{
return top;
};
void ClearStack(void)
{top=0};
};
计算机学院信息教研室
DS
//SeqStack0.h
lixuejun@swust.edu.cn
顺序堆栈类实现
#include "SeqStack.h"
//把元素 item入栈,堆栈满时出错退出
void SeqStack::Push(const DataType& item)
{
if(top == MaxListSize)//基类的 ListSize()返回基类的 size值
{
cerr<<"堆栈已满 !"<<endl;
exit(1);
}
//top的初始值为 0是有效存储单元,所以先存储 item
data[top] = item;
top++;
}
计算机学院信息教研室
DS
//SeqStack0.cpp
lixuejun@swust.edu.cn
顺序堆栈类实现
//出栈并返回栈顶元素,栈空时出错退出
DataType SeqStack::Pop()
{
if(top == 0)
{
cerr<<"堆栈已空 !"<<endl;
exit(1);
}
top--;
return data[top];
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈类实现
//取栈顶元素
DataType SeqStack::Peek(void) const
{
if(top == 0)
{
cerr<<"堆栈空 !"<<endl;
exit(1);
}
//top指在栈顶的下一个位置,取 top-1上的元素返回
return data[top-1];
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈继承类堆栈可以说是一种操作受限制的线形表顺序堆栈继承类不定义私有数据，而是通过基类 Seqlist提供的方法使用了基类
Seqlist中的私有数据成员。
顺序堆栈继承类中所有成员函数都是通过调用顺序表中的成员函数来实现的。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈继承类类定义
#include "seqlist.h"
class SeqStack:private SeqList
{
public:
SeqStack(void){SeqList();}
~SeqStack(void){};
void Push(const DataType& item); //元素 item入栈
DataType Pop(void); //出栈元素并返回
DataType Peek(void) const; //读栈顶元素并返回
int StackEmpty(void) const;
int GetSize(void) const;
void ClearStack(void);
};
计算机学院信息教研室
DS
//SeqStack.h
lixuejun@swust.edu.cn
顺序堆栈继承类类实现
#include "SeqStack.h"
#include "seqlist.h"
//把元素 item入栈,堆栈满时出错退出
void SeqStack::Push(const DataType& item)
{
if(ListSize()==MaxListSize) //基类的 ListSize()返回基类的 size值
{
cerr<<"堆栈已满 !"<<endl;
exit(1);
}
Insert(item,ListSize());
}
计算机学院信息教研室
DS
//SeqStack.cpp
lixuejun@swust.edu.cn
顺序堆栈继承类类实现
//出栈并返回栈顶元素,栈空时出错退出
DataType SeqStack::Pop(void)
{
if(0==ListSize())
{
cerr<<"堆栈已空 !"<<endl;
exit(1);
}
return Delete(ListSize()-1); //删除最后存入的元素返回
}
计算机学院信息教研室
DS
//SeqStack.cpp
lixuejun@swust.edu.cn
顺序堆栈继承类类实现取栈顶元素并返回
DataType SeqStack::Peek(void) const
{
return GetData(ListSize()-1); //取最后存入的元素返回
}
//判堆栈空否,空返回 1;非空返回 0
int SeqStack::StackEmpty(void) const
{
return ListEmpty();
}
计算机学院信息教研室
DS
//SeqStack.cpp
lixuejun@swust.edu.cn
顺序堆栈继承类类实现
//读栈元素个数 size
int SeqStack::GetSize(void) const
{
return ListSize();
}
//清空堆栈使之为初始化状态
void SeqStack::ClearStack(void)
{
ClearList();
}
计算机学院信息教研室
DS
//SeqStack.cpp
lixuejun@swust.edu.cn
顺序堆栈应用 —转换为 8进制
#include "SeqStack.h"
void main(void)
{
int n;
SeqStack mystack;
cout<<"输入一个数,准备转换为 8进制 "<<endl;
cin>>n;
while(n)
{
mystack.Push(n%8);
n=n/8;
}
while(!mystack.StackEmpty())
{
cout<<mystack.Pop();
}
cout<<endl;
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算问题,在编译系统中，要把便于人们理解的的表达式翻译成能正确值的机器指令序列，通常需要先把表达式变换为机器便于理解的形式 ——这就要求变换表达式的序列。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算在计算机内部，任何一个表达式都是由操作数，运算符，分界符（标志了一个表达式的结束）组成。
中缀表达式：运算符总是出现在两个操作数之间（单目运算符除外）
比如,A+(B-C/D)*E
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算编译系统对中缀形式的算术表达式处理的方法
A+(B-C/D)*E ABCD/-*+
计算机学院信息教研室
DS
中缀表达式 后缀表达式转换转换
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算后缀表达式 的特点：
1.后缀表达式 与 中缀表达式的操作数先后次序相同，只是运算符的先后次序改变。
2.后缀表达式中没有括号，后缀表达式的运算符顺序就是其执行顺序。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算所以编译系统在处理后缀表达式表达式时 不用考虑运算符的优先关系,只要 从左到右 依次扫描后缀表达式的各个单词,当读到一个单词为运算符时,就对该运算符前边的两个操作数做给运算符所代表的 运算,然后将结果 存入一个临时变量 中，并作为一个新的操作数接着进行上述过程，直到表达式处理完毕为止。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算综上所述：
编译系统中表达式计算的两个步骤
（ 1）把中缀表达式转换为后缀表达式；
（ 2）根据后缀表达式计算表达式的值本节主要讨论第一个问题计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算前面讨论知道,后缀表达式 与 中缀表达式的操作数先后次序相同，只是运算符的先后次序改变。
编译系统设置一个存放运算符的堆栈，
初始时栈顶置一分界符 #，编译系统从左到右依次扫描中缀表达式。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算读到一个操作数，即作为一个后缀表达式的一部分输出。
读到一个运算符（分界符也看作一个运算符）就将其优先级同栈顶优先级作比较，
以决定是把所读到的运算符进栈还是作为后缀表达式的一部分输出。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算令 x1为当前栈顶运算符的变量,x2为当前扫描读到的运算符的变量。
若 x1的优先级高于 x2的优先级，将 x1退栈并作为后缀表达式的一个单词输出,然后接着比较新的栈顶运算符 X1与 X2的优先级；
若 x1的优先级低于 x2的优先级，将 x2进栈若 x1的优先级等于于 x2的优先级，且 x1为
,（,,x2为,）,,将 x1退栈若 x1的优先级等于 x2的优先级，且且 x1为
,#”,x2为,#”,算法结束。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算计算机学院信息教研室
DS 步骤 中缀表达式 STACK 后 缀表达式
9 ） *E# #+（ -/ ABCD
10 ） *E# #+（ - ABCD/
11 ） *E# #+（ ABCD/-
12 *E# #+ ABCD/-
13 E# #+* ABCD/-
14 # #+ * ABCD/-E
15 # #+ ABCD/-E*
16 # # ABCD/-E*+
X2 X1
lixuejun@swust.edu.cn
3.4队列和循环队列
3.4.1 顺序循环队列
3.4.2 顺序循环队列类的定义和实现
3.4.3 顺序循环队列的应用
lixuejun@swust.edu.cn
队列 概念允许一端插入另一端删除的线性表队尾 插入端队头 取出端
← a1 a2 a3 a4 a5 ←
← a2 a3 a4 a5 a6 ←
特点：先进先出队 尾队 头顺序队列：用顺序存储结构存储的队列
lixuejun@swust.edu.cn
顺序循环队列假溢出,并不是由于存储空间得不够引起的。
所以一般的顺序队列很少在实际的软件系统中使用。
解决的方法是,把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。
当 rear和 front达到 MaxQueueSize-1后，再前进一个位置就自动到 0，可以利用求模运算来实现。
lixuejun@swust.edu.cn
顺序循环队列的表示和实现循环队列结构把队列视为一个循环表，即 cq.data[maxsize-1]之后是数组的第一个元素 cq.data[0] 。
可采用 mod运算 （ 取余数 ） 来实行循环队列的运算,
入队时 操作,cq.data[cq.rear]=x;
cq.rear =(cq.rear+1)% maxsize;
出队时 操作,x=cq.data[cq,front];
cq.front =(cq.front+1) % maxsize;
回忆：堆栈的入栈和出栈的操作呢？
lixuejun@swust.edu.cn
此时,队空,有
cq.front=cq.rear
此时,队满,有
cq.front=cq.rear
例,maxsize=6,初始状态和操作过程如下,
顺序循环队列的表示和实现
B
C
D
F
E
cq.front
cq.rear
A
将 F入队连续 4次出队
cq.frontcq.rear
再出队
B
C
D
E
cq.front
cq.rear
A
cq.front
cq.rear
E
lixuejun@swust.edu.cn
队满和队空时，均有 cq.front=cq.rear。
因此，只凭 cq.front=cq.rear还无法区分是满还是空。
如何判定队满还是空？是循环队列要解决的新问题。
顺序循环队列的表示和实现方法一,用一个计数变量来记载队列中的元素个数。
初始化队列时 c=0;
当入队时，计数变量＋ 1（ c=c+1 ）
当出队时，计数变量－ 1 （ c=c-1）
当计数变量＝ maxsize时，队满
当计数变量＝ 0时，队空
lixuejun@swust.edu.cn
方法二,设一个标志位用来区别队列是空还是满。
初始化队列时,cq.front==cq.rear，标志位为
false
入队后，使 cq.front==cq.rear，则置标志位为 true
出队后，将标志位置为 false
当 cq.front==cq.rear,且标志位为 true时,队满 。
当 cq.front==cq.rear,但标志位为 false时,队空 。
其他为非空非满。
顺序循环队列的表示和实现
lixuejun@swust.edu.cn
方法三,牺牲一个元素空间，来区别队空或队满。
入队前，先判 (cq.rear+1)% maxsize是否等于
cq.front，若是则为队满。
而当 cq.front==cq.rear时，为队空。
前例：当 E入队后,就认为队已满,
而当 F再要入队时,就拒绝入队 。
顺序循环队列的表示和实现
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
#include <iostream.h>
#include <stdlib.h>
const int MaxQueueSize = 100;
class SeqQueue
{
private:
Datatype data[MaxQueueSize];
int front;
int rear;
int count;
SeqQueue.h 采用方法一实现，方法三见书，方法二自己实现
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
public:
SeqQueue (void) // 构造函数
{
front = rear = 0;
cout =0
};
~SeqQueue (void){}; //析构函数
void QInsert(const Datatype& item); //入队列
Datatype QDelete(void); //出队列
Datatype QFront(void) const; //读队头元素值
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
int QEmpty(void) const //判队列是否为空
{
return front == rear;
};
void ClearSeqQueue(void) //清空队列
{
front = rear = 0;
cout =0
};
int GetSize(void) const //取队列元素个数
{
return count;
};
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
// 把元素 item入队列
void SeqQueue::QInsert (const Datatype& item)
{
if (count == MaxQueueSize)
{
cout << "SeqQueue overflow!" << endl;
exit(1);
}
data[rear] = item;
rear = (rear+1) % MaxQueueSize;
count++;
}
SeqQueue.cpp
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
// 出队列
Datatype SeqQueue::QDelete(void)
{
Datatype temp;
if (count == 0)
{
cout << "Deleting from an empty SeqQueue!" << endl;
exit(1);
}
temp = data[front]; //保存队头元素值
front = (front+1) % MaxQueueSize;
count--;
return temp;
}
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
Datatype SeqQueue::QFront(void) const
{
if(count == 0)
{
cout<<"队列空 !"<<endl;
exit(1);
}
return data[front];
}
lixuejun@swust.edu.cn
顺序循环队列 的应用例：判断一个字符序列是否是回文。
用栈和队列来处理
2419142
定义栈对象和队列对象进栈，进队列出队列，退栈（逐个比较出队列元素和出栈元素）
lixuejun@swust.edu.cn
3.6 顺序存储结构的特点线性 结构的特点：线形元素之间的逻辑关系为除第一个元素和最后一个元素之外，
每个数据元素都只有一个前驱元素和一个后继元素。
顺序存储结构的特点：在逻辑上相邻的数据元素在物理上也相邻
lixuejun@swust.edu.cn
3.6 顺序存储结构的特点优点：
（ 1）使用方便
（ 2）可随机存取数据元素缺点：
（ 1）数据元素最大个数预先给定
（ 2）插入和删除时，需要移动较多的元素。
顺序存储结构的表、堆栈和队列
3.1 顺序存储结构
3.2 表和顺序表
3.3 堆栈和顺序堆栈
3.4 队列和顺序队列
3.5 优先级队列和顺序优先级队列
3.6 顺序存储结构的特点计算机学院信息教研室
DS
lixuejun@swust.edu.cn
线性结构线性 结构的特点：线形元素之间的逻辑关系为除第一个元素和最后一个元素之外，每个数据元素都只有一个前驱元素和一个后继元素。
表、堆栈和队列都属于线形结构计算机学院信息教研室
DS
lixuejun@swust.edu.cn
线性结构常见三种线性结构的区别：
表可以在任何位置进行插入和删除堆栈只可以表头位置插入和删除队列是只可在表尾位置插入、在表头位置删除计算机学院信息教研室
DS
lixuejun@swust.edu.cn
存储结构存储结构：数据元素在计算机中的存储方式。
顺序存储结构链式存储结构间接地址仿真指针计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序存储结构用户向系统申请一块地址连续的空间用于存储数据元素集合，这样，任意两个在逻辑上相邻的数据元素在物理上也相邻。
C++中，使用数组向系统申请连续空间。
有动态数组和静态数组两种。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序存储结构使用静态数组申请连续空间使用数组定义语句 []
当程序运行超出该静态数组定义的范围时，系统自动回收该静态数组的地址空间。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序存储结构
#include<stdio.h>
Const int MaxSize =
100;
Void main(void)
{
int I;
int temp[MaxSize];
For(I=o;I<6;I++)
{
Temp[I] = I+1;
Printf(“temp[%d]=
%d\n”,I,temp[i]);
}
}
计算机学院信息教研室
DS
程序退出主函数时,系统自动回收分配给 temp的地址空间静态数组
lixuejun@swust.edu.cn
顺序存储结构动态数组 申请 连续空间使用 动态存储分配运算符 (new).
动态数组存储空间的 回收 方法,当不在需要该动态数组时,使用 动态存储释放运算符 (delete).
计算机学院信息教研室
DS 动态数组
lixuejun@swust.edu.cn
顺序存储结构
#include<iostream.h>
#include<stdlib.h>
Void main(void)
{
int I,*temp;
const int MaxSize=100;
temp=new int[MaxSize];
For(I=0;I<6;I++)
{
Temp[I] = I+1;
cout<<“I=”<<I<<
“temp[i]=“<<temp[i]<<
endl”;
}
delete[ ]temp;
}
计算机学院信息教研室
DS 动态数组申请和释放由用户通过调用 new和 delete运算符完成
lixuejun@swust.edu.cn
表和顺序表表 (List)：可以在 任何位置 进行插入和删除 操作的有 n个 相同类型数据元素 组成的线性结构,N是表的长度。 n=0的表称为空表。
表的逻辑关系表的存储结构
顺序表（ Sequent List）,用顺序存储结构存储的表。
链式表计算机学院信息教研室
DS
lixuejun@swust.edu.cn
把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
假设线性表的每个元素需占用 l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第 i+1个数据元素的存储位置 LOC( a i+1)和第 i个数据元素的存储位置 LOC(a i )之间满足下列关系：
LOC(a i+1)=LOC(a i)+l
线性表的第 i个数据元素 ai的存储位置为：
LOC(ai)=LOC(a1)+(i-1)*l
顺序表
lixuejun@swust.edu.cn
顺序表的类定义数据成员包括,1.数组 2.数组的最大元素个数 3.当前数组元素的个数。
操作,初始化构造表 在表的某一位置插入一个元素 在表的某一位置删除一个元素 定位某个数据元素在表中的存储位置 取表的某个存储位置的数据元素 判表是否为空计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
#include <iostream.h>
#include <stdlib.h>
const int MaxListSize
= 100;
class SeqList
{
private:
DataType
data[MaxListSize];
int size;
public,
SeqList(void); // constructor
~SeqList (void)；
int ListSize(void) const;
int ListEmpty(void) const;
int Find (DataType& item) const;
DataType GetData(int pos) const;
void Insert(const DataType&
item,int pos);
DataType Delete(const int pos);
void ClearList(void);
};
计算机学院信息教研室
DS
//SeqList.h
lixuejun@swust.edu.cn
表和顺序表
#include "seqlist.h"
//构造函数。置顺序表的数据元素个素为 0
SeqList::SeqList (void),size(0){}
//析构函数。
SeqList::~SeqList (void){}
//返回顺序表的元素个数 size
int SeqList::ListSize(void) const
{
return size;
}
计算机学院信息教研室
DS
Seqlist.cpp
lixuejun@swust.edu.cn
表和顺序表
//判顺序表空否，为空返回 1，不空返回 0
int SeqList::ListEmpty(void) const
{
if (size == 0) return 1;
else return 0;
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
//定位元素 item的位置，返回值为 item在顺序表中的位置；返回值为 -1表示不存在
int SeqList::Find(DataType& item) const
{
if(size == 0) return -1;
int i = 0;
while (i < size && item != data[i])
i++; //寻找 item
if (i < size)
return i; // return True
else
return -1; // return False
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
//返回顺序表中位置 pos上的元素。参数出错时退出
DataType SeqList::GetData(int pos) const
{
//取的元素序号必须在 0至 size-1之间
if (pos < 0 || pos > size-1)
{
cerr << "参数 pos越界出错 !" << endl;
exit(1);
}
return data[pos];
}
计算机学院信息教研室
DS
线性表的插入和删除
1、线性表的插入操作
（ a1,a2,… ai-1,ai,… an)----->(a1,a2,… ai-1,b,ai,… an)
一般地，在第 i个数据元素之前插入一个元素时，需要将第 n至第 i个元素向后移动一个位置。此时，需移动位置的元素个数为 n-i+1个。
lixuejun@swust.edu.cn
算法思想：
① 进行合法性检查,1<=i<=n+1；
② 判断线性表是否已满；
③ 将第 n个至第 i个元素逐一后移一个单元；
④ 在第 i个位置处插入新元素；
⑤ 将表的长度加 1。
lixuejun@swust.edu.cn
表和顺序表
//在指定位置 pos处插入一个数据元素 item
void SeqList::Insert(const DataType& item,int pos)
{
if (size==MaxListSize)
{
cerr<<"顺序表已满无法插入 !"<<endl;
exit(1);
}
if (pos<0||pos>size)//当 pos等于 size时表示插入在最后
{
cout<<"参数 pos越界出错 !";
exit(1);
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
//从后向前把前一个元素迁移到后一个元素位置直到存储位置 pos为止
for(int i=size;i>pos;i--)
data[i]=data[i-1];
data[pos] = item; //在 pos位置插入 item
size++; //数据元素个数 size加 1
}
计算机学院信息教研室
DS
2、线性表的删除操作
（ a1,a2,… ai-1,ai,ai+1,… an)----->(a1,a2,… ai-1,ai+1,… an)
一般地，删除第 I个元素时需将第 I+1至第 n个元素依次向前移动一个位置，此时，元素移动的个数为 n-I个。
lixuejun@swust.edu.cn
算法思想：
① 进行合法性检查,I是否满足 1<=I<=n；
② 判线性表是否已空,L.length=0；
③ 将第 I+1至第 n个元素逐一向前移一个位置；
④ 将表的长度减 1。
lixuejun@swust.edu.cn
表和顺序表
//删除指定位置 pos上的数据元素并返回
DataType SeqList::Delete(const int pos)
{
if(size==0)
{
cerr<<"顺序表已空无元素可删 !"<<endl;
exit(1);
}
//删除元素序号必须在 0至 size-1之间
if(pos<0||pos>size-1)
{
cerr<<"参数 pos越界出错 !"<<endl;
exit(1);
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
DataType temp=data[pos];
//从 pos至 size-2逐个元素左移,data[size-1]移入
data[size-2]中
for(int i = pos;i<size-1;i++)
data[i] = data[i+1];
size--; // 数据元素个数 size减 1
return temp;
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
//置顺序表为空
void SeqList::ClearList(void)
{
size = 0; //数据元素个数 size置为初始化值
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
typedef int DataType; //具体应用时定义的数据类型 Datatype
#include "seqlist.h" //类 Seqlist的定义和实现头文件
void main(void)
{
SeqList myList; //插入 5个整型元素
for(int i=0;i<5;i++)
myList.Insert(i+10,i);
cout<<"测试 GetData()成员函数结果如下,"<<endl;
for(i=0;i<5;i++)
cout<<"测试 Delete()成员函数结果如下,"<<endl;
for(i=0;i<5;i++)
cout<<myList.Delete(0)<<" ";
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
表和顺序表
typedef char Datatype; //具体应用时定义的数据类型
Datatype
#include "seqlist.h" //类 Seqlist的定义和实现头文件
void main(void)
{
SeqList list;
//插入 5个字符型元素
for(int i=0;i<5;i++)
list.Insert('A'+i,i);
for(i=0;i<5;i++)
cout<<list.Delete(0)<<" ";
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序表上插入、删除算法的效率分析平均次数如果保持原来的数据元素序列时插入、删除算法的时间复杂度均为 O(n).定位一个数据元素的时间复杂度为 O(n),其余的 算法的时间复杂度均为 O(1)
如果不必保持原来的数据元素序列时插入、删除算法为 O(1),定位一个数据元素的时间复杂度为 O(n),其余的 算法的时间复杂度均为 O(1)
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
3.3 堆栈和顺序堆栈
3.3.1 顺序堆栈类定义
3.3.2 顺序堆栈应用计算机学院信息教研室
DS
lixuejun@swust.edu.cn
堆栈概念堆栈（ Stack）
1,特殊的线性表,只可以表头位置插入和删除
2,允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。
计算机学院信息教研室
DS
进栈或入栈出栈或退栈空 栈特点：后进先出
lixuejun@swust.edu.cn
1 顺序栈用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设指针 top指示栈顶元素在顺序栈中的位置,
top
base Abase
top
A
B
C
D
E
base
top
top
base A
B
lixuejun@swust.edu.cn
顺 序 栈 举 例例：如果进站的车厢序列为 1 2 3 4 5 6，
则能否得到下列出站序列，并说明为什么不能得到或者如何得到
4 3 5 6 1 2
1 3 5 4 2 6
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈类定义
#include <iostream.h>
#include <stdlib.h>
const int MaxStackSize = 100;
class SeqStack
{
private:
Datatype
data[MaxStackSize];
int top;
public:
SeqStack(void){top=0;}
~SeqStack(void){};
void Push(const
DataType& item); //元素
item入栈
DataType Pop(void);
//出栈元素并返回
DataType Peek(void) const;
//读栈顶元素并返回
int StackEmpty(void) const
{
return(top==0);
};
int GetSize(void) const
{
return top;
};
void ClearStack(void)
{top=0};
};
计算机学院信息教研室
DS
//SeqStack0.h
lixuejun@swust.edu.cn
顺序堆栈类实现
#include "SeqStack.h"
//把元素 item入栈,堆栈满时出错退出
void SeqStack::Push(const DataType& item)
{
if(top == MaxListSize)//基类的 ListSize()返回基类的 size值
{
cerr<<"堆栈已满 !"<<endl;
exit(1);
}
//top的初始值为 0是有效存储单元,所以先存储 item
data[top] = item;
top++;
}
计算机学院信息教研室
DS
//SeqStack0.cpp
lixuejun@swust.edu.cn
顺序堆栈类实现
//出栈并返回栈顶元素,栈空时出错退出
DataType SeqStack::Pop()
{
if(top == 0)
{
cerr<<"堆栈已空 !"<<endl;
exit(1);
}
top--;
return data[top];
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈类实现
//取栈顶元素
DataType SeqStack::Peek(void) const
{
if(top == 0)
{
cerr<<"堆栈空 !"<<endl;
exit(1);
}
//top指在栈顶的下一个位置,取 top-1上的元素返回
return data[top-1];
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈继承类堆栈可以说是一种操作受限制的线形表顺序堆栈继承类不定义私有数据，而是通过基类 Seqlist提供的方法使用了基类
Seqlist中的私有数据成员。
顺序堆栈继承类中所有成员函数都是通过调用顺序表中的成员函数来实现的。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈继承类类定义
#include "seqlist.h"
class SeqStack:private SeqList
{
public:
SeqStack(void){SeqList();}
~SeqStack(void){};
void Push(const DataType& item); //元素 item入栈
DataType Pop(void); //出栈元素并返回
DataType Peek(void) const; //读栈顶元素并返回
int StackEmpty(void) const;
int GetSize(void) const;
void ClearStack(void);
};
计算机学院信息教研室
DS
//SeqStack.h
lixuejun@swust.edu.cn
顺序堆栈继承类类实现
#include "SeqStack.h"
#include "seqlist.h"
//把元素 item入栈,堆栈满时出错退出
void SeqStack::Push(const DataType& item)
{
if(ListSize()==MaxListSize) //基类的 ListSize()返回基类的 size值
{
cerr<<"堆栈已满 !"<<endl;
exit(1);
}
Insert(item,ListSize());
}
计算机学院信息教研室
DS
//SeqStack.cpp
lixuejun@swust.edu.cn
顺序堆栈继承类类实现
//出栈并返回栈顶元素,栈空时出错退出
DataType SeqStack::Pop(void)
{
if(0==ListSize())
{
cerr<<"堆栈已空 !"<<endl;
exit(1);
}
return Delete(ListSize()-1); //删除最后存入的元素返回
}
计算机学院信息教研室
DS
//SeqStack.cpp
lixuejun@swust.edu.cn
顺序堆栈继承类类实现取栈顶元素并返回
DataType SeqStack::Peek(void) const
{
return GetData(ListSize()-1); //取最后存入的元素返回
}
//判堆栈空否,空返回 1;非空返回 0
int SeqStack::StackEmpty(void) const
{
return ListEmpty();
}
计算机学院信息教研室
DS
//SeqStack.cpp
lixuejun@swust.edu.cn
顺序堆栈继承类类实现
//读栈元素个数 size
int SeqStack::GetSize(void) const
{
return ListSize();
}
//清空堆栈使之为初始化状态
void SeqStack::ClearStack(void)
{
ClearList();
}
计算机学院信息教研室
DS
//SeqStack.cpp
lixuejun@swust.edu.cn
顺序堆栈应用 —转换为 8进制
#include "SeqStack.h"
void main(void)
{
int n;
SeqStack mystack;
cout<<"输入一个数,准备转换为 8进制 "<<endl;
cin>>n;
while(n)
{
mystack.Push(n%8);
n=n/8;
}
while(!mystack.StackEmpty())
{
cout<<mystack.Pop();
}
cout<<endl;
}
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算问题,在编译系统中，要把便于人们理解的的表达式翻译成能正确值的机器指令序列，通常需要先把表达式变换为机器便于理解的形式 ——这就要求变换表达式的序列。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算在计算机内部，任何一个表达式都是由操作数，运算符，分界符（标志了一个表达式的结束）组成。
中缀表达式：运算符总是出现在两个操作数之间（单目运算符除外）
比如,A+(B-C/D)*E
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算编译系统对中缀形式的算术表达式处理的方法
A+(B-C/D)*E ABCD/-*+
计算机学院信息教研室
DS
中缀表达式 后缀表达式转换转换
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算后缀表达式 的特点：
1.后缀表达式 与 中缀表达式的操作数先后次序相同，只是运算符的先后次序改变。
2.后缀表达式中没有括号，后缀表达式的运算符顺序就是其执行顺序。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算所以编译系统在处理后缀表达式表达式时 不用考虑运算符的优先关系,只要 从左到右 依次扫描后缀表达式的各个单词,当读到一个单词为运算符时,就对该运算符前边的两个操作数做给运算符所代表的 运算,然后将结果 存入一个临时变量 中，并作为一个新的操作数接着进行上述过程，直到表达式处理完毕为止。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算综上所述：
编译系统中表达式计算的两个步骤
（ 1）把中缀表达式转换为后缀表达式；
（ 2）根据后缀表达式计算表达式的值本节主要讨论第一个问题计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算前面讨论知道,后缀表达式 与 中缀表达式的操作数先后次序相同，只是运算符的先后次序改变。
编译系统设置一个存放运算符的堆栈，
初始时栈顶置一分界符 #，编译系统从左到右依次扫描中缀表达式。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算读到一个操作数，即作为一个后缀表达式的一部分输出。
读到一个运算符（分界符也看作一个运算符）就将其优先级同栈顶优先级作比较，
以决定是把所读到的运算符进栈还是作为后缀表达式的一部分输出。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算令 x1为当前栈顶运算符的变量,x2为当前扫描读到的运算符的变量。
若 x1的优先级高于 x2的优先级，将 x1退栈并作为后缀表达式的一个单词输出,然后接着比较新的栈顶运算符 X1与 X2的优先级；
若 x1的优先级低于 x2的优先级，将 x2进栈若 x1的优先级等于于 x2的优先级，且 x1为
,（,,x2为,）,,将 x1退栈若 x1的优先级等于 x2的优先级，且且 x1为
,#”,x2为,#”,算法结束。
计算机学院信息教研室
DS
lixuejun@swust.edu.cn
顺序堆栈应用 —表达式计算计算机学院信息教研室
DS 步骤 中缀表达式 STACK 后 缀表达式
9 ） *E# #+（ -/ ABCD
10 ） *E# #+（ - ABCD/
11 ） *E# #+（ ABCD/-
12 *E# #+ ABCD/-
13 E# #+* ABCD/-
14 # #+ * ABCD/-E
15 # #+ ABCD/-E*
16 # # ABCD/-E*+
X2 X1
lixuejun@swust.edu.cn
3.4队列和循环队列
3.4.1 顺序循环队列
3.4.2 顺序循环队列类的定义和实现
3.4.3 顺序循环队列的应用
lixuejun@swust.edu.cn
队列 概念允许一端插入另一端删除的线性表队尾 插入端队头 取出端
← a1 a2 a3 a4 a5 ←
← a2 a3 a4 a5 a6 ←
特点：先进先出队 尾队 头顺序队列：用顺序存储结构存储的队列
lixuejun@swust.edu.cn
顺序循环队列假溢出,并不是由于存储空间得不够引起的。
所以一般的顺序队列很少在实际的软件系统中使用。
解决的方法是,把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。
当 rear和 front达到 MaxQueueSize-1后，再前进一个位置就自动到 0，可以利用求模运算来实现。
lixuejun@swust.edu.cn
顺序循环队列的表示和实现循环队列结构把队列视为一个循环表，即 cq.data[maxsize-1]之后是数组的第一个元素 cq.data[0] 。
可采用 mod运算 （ 取余数 ） 来实行循环队列的运算,
入队时 操作,cq.data[cq.rear]=x;
cq.rear =(cq.rear+1)% maxsize;
出队时 操作,x=cq.data[cq,front];
cq.front =(cq.front+1) % maxsize;
回忆：堆栈的入栈和出栈的操作呢？
lixuejun@swust.edu.cn
此时,队空,有
cq.front=cq.rear
此时,队满,有
cq.front=cq.rear
例,maxsize=6,初始状态和操作过程如下,
顺序循环队列的表示和实现
B
C
D
F
E
cq.front
cq.rear
A
将 F入队连续 4次出队
cq.frontcq.rear
再出队
B
C
D
E
cq.front
cq.rear
A
cq.front
cq.rear
E
lixuejun@swust.edu.cn
队满和队空时，均有 cq.front=cq.rear。
因此，只凭 cq.front=cq.rear还无法区分是满还是空。
如何判定队满还是空？是循环队列要解决的新问题。
顺序循环队列的表示和实现方法一,用一个计数变量来记载队列中的元素个数。
初始化队列时 c=0;
当入队时，计数变量＋ 1（ c=c+1 ）
当出队时，计数变量－ 1 （ c=c-1）
当计数变量＝ maxsize时，队满
当计数变量＝ 0时，队空
lixuejun@swust.edu.cn
方法二,设一个标志位用来区别队列是空还是满。
初始化队列时,cq.front==cq.rear，标志位为
false
入队后，使 cq.front==cq.rear，则置标志位为 true
出队后，将标志位置为 false
当 cq.front==cq.rear,且标志位为 true时,队满 。
当 cq.front==cq.rear,但标志位为 false时,队空 。
其他为非空非满。
顺序循环队列的表示和实现
lixuejun@swust.edu.cn
方法三,牺牲一个元素空间，来区别队空或队满。
入队前，先判 (cq.rear+1)% maxsize是否等于
cq.front，若是则为队满。
而当 cq.front==cq.rear时，为队空。
前例：当 E入队后,就认为队已满,
而当 F再要入队时,就拒绝入队 。
顺序循环队列的表示和实现
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
#include <iostream.h>
#include <stdlib.h>
const int MaxQueueSize = 100;
class SeqQueue
{
private:
Datatype data[MaxQueueSize];
int front;
int rear;
int count;
SeqQueue.h 采用方法一实现，方法三见书，方法二自己实现
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
public:
SeqQueue (void) // 构造函数
{
front = rear = 0;
cout =0
};
~SeqQueue (void){}; //析构函数
void QInsert(const Datatype& item); //入队列
Datatype QDelete(void); //出队列
Datatype QFront(void) const; //读队头元素值
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
int QEmpty(void) const //判队列是否为空
{
return front == rear;
};
void ClearSeqQueue(void) //清空队列
{
front = rear = 0;
cout =0
};
int GetSize(void) const //取队列元素个数
{
return count;
};
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
// 把元素 item入队列
void SeqQueue::QInsert (const Datatype& item)
{
if (count == MaxQueueSize)
{
cout << "SeqQueue overflow!" << endl;
exit(1);
}
data[rear] = item;
rear = (rear+1) % MaxQueueSize;
count++;
}
SeqQueue.cpp
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
// 出队列
Datatype SeqQueue::QDelete(void)
{
Datatype temp;
if (count == 0)
{
cout << "Deleting from an empty SeqQueue!" << endl;
exit(1);
}
temp = data[front]; //保存队头元素值
front = (front+1) % MaxQueueSize;
count--;
return temp;
}
lixuejun@swust.edu.cn
顺序循环队列类的定义和实现
Datatype SeqQueue::QFront(void) const
{
if(count == 0)
{
cout<<"队列空 !"<<endl;
exit(1);
}
return data[front];
}
lixuejun@swust.edu.cn
顺序循环队列 的应用例：判断一个字符序列是否是回文。
用栈和队列来处理
2419142
定义栈对象和队列对象进栈，进队列出队列，退栈（逐个比较出队列元素和出栈元素）
lixuejun@swust.edu.cn
3.6 顺序存储结构的特点线性 结构的特点：线形元素之间的逻辑关系为除第一个元素和最后一个元素之外，
每个数据元素都只有一个前驱元素和一个后继元素。
顺序存储结构的特点：在逻辑上相邻的数据元素在物理上也相邻
lixuejun@swust.edu.cn
3.6 顺序存储结构的特点优点：
（ 1）使用方便
（ 2）可随机存取数据元素缺点：
（ 1）数据元素最大个数预先给定
（ 2）插入和删除时，需要移动较多的元素。
