[理学]第3章 数据结构课件.ppt

第3章 顺序存储结构的表、堆栈 和队列 数据结构（C+） 1 目录 3.1 顺序存储结构 3.2 表和顺序表 3.3 堆栈和顺序堆栈 3.4 队列和顺序队列 3.5 优先级队列和顺序优先级队列 2 线性表的逻辑结构： 1 线性表的定义 线性表（linear list）是n（n0）个数据元素a1，a2，an 组成的有限序列。其中n 称为数据元素的个数或线性 表的长度，当n=0时称为空表，n0时称为非空表。通 常将非空的线性表记为（a1，a2，,an），其中的数据 元素ai（1in）是一个抽象的符号，其具体含义在不 同情况下是不同的，即它的数据类型可以根据具体情 况而定，本书中，我们将它的类型设定为elemtype， 表示某一种具体的已知数据类型。 3 2 线性表的特征 从线性表的定义可以看出线性表的特征： （1 ）有且仅有一个开始结点(表头结点)a1，它没有直接 前驱，只有一个直接后继; （2）有且仅有一个终端结点(表尾结点)an，它没有直接 后继，只有一个直接前驱; （3） 其它结点都有一个直接前驱和直接后继； （ 4）元素之间为一对一的线性关系。 4 线性表是一种典型的线性结构，用二元组表示为： linear_list=(A,R) 其中 A=ai 1in,n0,aielemtype R=r r= 1in-1 对应的逻辑结构图如图所示。 5 3.1 顺序存储结构 计算机所处理的所有的数据都要存储在内存 中。计算机高级语言系统对数据的存储结构有四 种：顺序存储结构、链式存储结构、间接地址和 仿真指针。其中，顺序存储结构和链式存储结构 是两种最基本和最常用的存储结构。本节讨论顺 序存储结构，其余三种存储结构依次在4.1节、5.2 节和7.1节中讨论。 6 顺序存储结构是计算机中的一种最基本和 最主要的数据存储结构。在顺序存储结构中， 用户向系统申请一块地址连续的有限空间用于 存储数据元素集合，这样，任意两个在逻辑上 相邻的数据元素在物理上也必然相邻。在C+中 ，向系统申请一块地址连续的有限空间的方法 是使用数组。数组有静态数组和动态数组两种 。不论是静态数组还是动态数组，其功能都是 向系统申请一块地址连续的有限空间，只是使 用的方法不同。 7 C+中静态数组向系统申请一块地址连续的有限 空间的方法是使用数组定义语句“。当程序运行超出 该静态数组定义的范围时，系统自动回收该静态数组 的地址空间。一个静态数组定义的例子如下： include const int MaxSize=100; void main(void) int i; int tempMaxSize; /静态申请MaxSize个整型元素的存储空间 8 for(i=0;i include void main(void) int i,*temp; const int MaxSize=100; temp=new intMaxSize; /动态申请MaxSize个整型元素的存储空间 12 for(i=0;iL.size-1) /取的元素序号必须在0至size-1之间 cerrL.size)/当pos等于size时表示插入在 最后 cerrpos;i-) L.datai=L.datai-1; L.datapos=item;/在pos位置插入item L.size+;/数据元素个数size加1 26 27 /删除指定位置pos上的数据元素并返回 elemtype Delete(SequentList struct SequentQueue elemtype queueMaxQueueSize; /将队列中元素定为数组型，元素类型为elemtype int front; /队头 int rear; /队尾 ; 86 2.顺序队列的基本函数： 1)初始化队列 IniQueue( 89 2.入队列 EnQueue( /定义具体应用的数据类型elemtype include“SequentQueue.h“ include“sequentStack.h“ void main(void) sequentStack myStack; sequentQueue myQueue; char str80; cout include const int MaxpQueueSize=100; struct SeqPQueue elemtype dataMaxpQueueSize; /抽象类型elemtype定义的数组 int size; /数据元素个数 106 2.函数的定义： 1).void IniPQueue(SeqPQueue /把元素item插入队尾 3) elemtype PQDelete(SeqPQueue /把队头元素删除并由函数返回 4) elemtype PQFront(SeqPQueue q); /读队头元素值并由函数返回 int PQueueEmpty(SeqPQueue q); /判队列是否为空 6) void ClearPQueue(SeqPQueue 108 2) void PQInsert(SeqPQueue /把元素item插入队尾 if(q.size=MaxPQueueSize) cout struct elemtype int taskNo; int priority; ; /定义具体问题的数据类型elemtype 116 int operatortask.taskNo; /文件方式读入taskNo项 fintask.priority; /文件方式读入priority项 PQInsert(myPQueue,task); /插入 int i=1; cout“序号“任务号“优先级“endl; while(PQueueEmpty(myPQueue) couti“; 119 task=PQDelete(myPQueue); /依次把优先级最高的元素出队列 couttask.taskNo“; /输出显示 couttask.priorityendl; /输出显示 i+; 120 设数据文件task.dat中存放的数据如下所示： 1 30 2 10 3 40 4 20 5 0 121 程序的输出为： 序号任务号优先级 1 5 0 2 2 10 3 4 20 4 1 30 5 3 40 122 当考虑优先级相同元素的先进先出问题时,例 33程序中的宏包含语句改为 include “SeqPQueue2.h“ 程序中的文件打开语句改为 fin.open(“task2.dat“,ios:in|ios:nocreate); 设数据文件task2.dat中存放的数据如下所示： 1 30 2 20 3 40 4 20 5 0 123 注意：进程任务号2和进程任务号4的优先级 相同，均为20。此时程序的输出为： 序号 任务号 优先级 1 5 0 2 2 20 3 4 20 4 1 30 5 3 40 124 3.6 顺序存储结构的特点 顺序存储结构是数据结构中最基本、最常用、最 重要的一种存储结构。顺序存储结构的最主要特征是 逻辑上相邻的数据元素在物理上也相邻。向系统申请 一片物理上相邻的存储空间的方法主要有两种：一种 是静态数组方法，另一种是动态数组方法。静态数组 方法是在程序编译时即分配数组元素空间的方法。本 章讲述的顺序存储结构方法都是静态数组方法。动态 数组方法是在程序运行时分配数组元素空间的方法， 动态数组方法将在第5章讨论。 125 顺序存储结构的特点主要有： （1）使用简便。根据具体问题确定出所需最 大数据元素个数后，只需定义一次，就可任意多 次使用。 （2）可随机存取数据元素。如对顺序表中所 有位置上的数据元素只要给出位置下标即可方便 地存取该