西南科技大学：《数据结构》课程教学资源（PPT课件讲稿）第三章 顺序存储结构的表、堆栈和队列

顺序存储结构的表、堆栈和队列 DS ■3.1顺序存储结构 32表和顺序表 算 机■3.3堆栈和顺序堆栈 3.4队列和顺序队列 息-35优先级队列和顺序优先级队列 教 研 3.6顺序存储结构的特点 室 lixuejun@swust.edu.cn

lixuejun@swust.edu.cn 顺序存储结构的表、堆栈和队列 ◼ 3.1 顺序存储结构 ◼ 3.2 表和顺序表 ◼ 3.3 堆栈和顺序堆栈 ◼ 3.4 队列和顺序队列 ◼ 3.5 优先级队列和顺序优先级队列 ◼ 3.6 顺序存储结构的特点 计 算 机 学 院 信 息 教 研 室 DS

线性结构 DS ◆线性结构的特点:线形元素之间的逻辑 勿关系为除第一个元素和最后一个元素之 算 学外,每个数据元素都只有一个前驱元素 和一个后继元素。 教◆表、堆栈和队列都属于线形结构 研 室 lixuejun@swust.edu.cn

lixuejun@swust.edu.cn 线性结构 线性结构的特点：线形元素之间的逻辑 关系为除第一个元素和最后一个元素之 外，每个数据元素都只有一个前驱元素 和一个后继元素。 表、堆栈和队列都属于线形结构 计 算 机 学 院 信 息 教 研 室 DS

线性结构 DS 常见三种线性结构的区别: 算◆表可以在何位置进行插入和删除 机 院 ◆堆栈只可以表头位置插入和删除 信◆队列是只可在表尾位置插入、在表头位 教置删除 室 lixuejun@swust.edu.cn

lixuejun@swust.edu.cn 线性结构 常见三种线性结构的区别： 表可以在任何位置进行插入和删除 堆栈只可以表头位置插入和删除 队列是只可在表尾位置插入、在表头位 置删除 计 算 机 学 院 信 息 教 研 室 DS

存储结构 DS 存储结构:数据元素在计算机中的存 计算机学 储方式 ◆顺序存储结构 院◆链式存储结构 信◆间接地址 教◆仿真指针 研 室 lixuejun@swust.edu.cn

lixuejun@swust.edu.cn 存储结构 存储结构：数据元素在计算机中的存 储方式。 顺序存储结构 链式存储结构 间接地址 仿真指针 计 算 机 学 院 信 息 教 研 室 DS

顺序存储结构 DS ◆用户向系统申请一块地址连续的空间用 算 于存储数据元素集合,这样,任意两个 机在逻辑上相邻的数据元素在物理上也相 信◆C++中,使用数组向系统申请连续空间。 自 教◆有动态数组和静态数组两种。 研 室 lixuejun@swust.edu.cn

lixuejun@swust.edu.cn 顺序存储结构 用户向系统申请一块地址连续的空间用 于存储数据元素集合，这样，任意两个 在逻辑上相邻的数据元素在物理上也相 邻。 C++中，使用数组向系统申请连续空间。 有动态数组和静态数组两种。 计 算 机 学 院 信 息 教 研 室 DS

顺序存储结构 DS 使用静态数组申请连续空间 算◆使用数组定义语句[ 机 房◆当程序运行超出该静态数组定义的范围时,系 总.统自动回收该静态数组的地址空间 教 研 室 lixuejun@swust.edu.cn

lixuejun@swust.edu.cn 顺序存储结构 使用静态数组申请连续空间 使用数组定义语句[] 当程序运行超出该静态数组定义的范围时，系 统自动回收该静态数组的地址空间。 计 算 机 学 院 信 息 教 研 室 DS

顺序存储结构 DS静态数组 #include For(I=oFI<6:I++) 计 Const int maxsize= 100 Temp[I]= I+1 算机学院信息教研 Printf(“temp%od]= 院 Did main(oid dn” Temp[i]) int I int temp[MaxSize]; 室 程序退出主函数时系统自动回收分配给temp的地址空间 lixuejun(@swust.edu.cn

lixuejun@swust.edu.cn 顺序存储结构 #include 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的地址空间 静态数组

顺序存储结构 DS动态数组 ◆动态数组申请连续空间使用动态 章存储分配运算符(neW) 机 院◆动态数组存储空间的回收方法:当 总不在需要该动态数组时使用动态 教存储释放运算符( delete) 室 lixuejun@swust.edu.cn

lixuejun@swust.edu.cn 顺序存储结构 动态数组申请连续空间使用动态 存储分配运算符(new). 动态数组存储空间的回收方法:当 不在需要该动态数组时,使用动态 存储释放运算符(delete). 计 算 机 学 院 信 息 教 研 室 DS 动态数组

顺序存储结构 DS动态数组 #include For(I=0; I 算 Void main(oid) Temp[I=I+1; 机{ cout <<I="<<I<< int I temp: “temp=<<temp<< M const int MaxSize=100;end 院 } 自 教 temp=new int[MaxSizel; deleteL temp: 研 室申请和释放由用户通过调用new和 delete运算符完成 lixuejun@swust.edu.cn

lixuejun@swust.edu.cn 顺序存储结构 #include #include 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运算符完成

表和顺序表 Ds◆表(is):可以在任何位置进行插入和删 除操作的有n个相同类型数据元素组成的 算线性结构N是表的长度。n=0的表称为 机 空表。 院◆表的逻辑关系 信◆表的存储结构 自 教研 顺序表( Sequent List):用顺序存储结构 存储的表。 室 链式表 lixuejun@swust.edu.cn

lixuejun@swust.edu.cn 表和顺序表 表(List)：可以在任何位置进行插入和删 除操作的有n个相同类型数据元素组成的 线性结构. N是表的长度。 n=0的表称为 空表。 表的逻辑关系 表的存储结构 ◼ 顺序表（Sequent List）：用顺序存储结构 存储的表。 ◼ 链式表 计 算 机 学 院 信 息 教 研 室 DS