数据结构ppt：第2章 线性结构.ppt

2.4 线性表不同存储表示方法的对比 线性表是线性数据结构的典型代表，它的逻辑特性可简述为“一对一”，很多问题经过抽象都可以具有线性表的逻辑特性，但具体用哪一种存储方式来表示线性表对解决问题的效率是有影响的，表2-3中列出了基本顺序表、游标顺序表、单链表基本操作的算法性能对比，供解决实际问题时参考。 * 数据结构与算法 2.4 线性表不同存储表示方法的对比 * 数据结构与算法 2.5 集合运算的模拟 2.5.1 问题描述与算法分析 1. 有关集合运算的定义 在高等数学或线性代数这类课程中我们已经对集合运算有一定的了解，这里只涉及集合的并、交、差三种运算，如图2-16所示。 * 数据结构与算法 2.5 集合运算的模拟 * 数据结构与算法 2.5 集合运算的模拟 2. 算法分析 在算法分析的部分，将使用算法流程描述中的“盒图”工具，它比语言描述更简洁和紧凑，盒图的图例含义简要说明如图2-17，其中图2-17（a）为顺序结构的表示、图2-17（b）为选择结构的表示、图2-17（c）为循环结构的表示。 * 数据结构与算法 2.5 集合运算的模拟 * 数据结构与算法 2.5 集合运算的模拟 （1）“并”运算 * 数据结构与算法 2.5 集合运算的模拟 （2）“交”运算 * 数据结构与算法 2.5 集合运算的模拟 （3）“差”运算 * 数据结构与算法 2.5 集合运算的模拟 2.5.2 算法实现 1. 在顺序表上实现集合并、交、差运算 顺序表的类型定义采用2.2.1节中SqList的定义，则3个运算的算法实现如下： 【算法2-17】 void OR(SqList X,SqList Y) {/* 顺序表实现集合并运算 */ ElemType e; for(int j=0;jY.GetLength();j++) { Y.GetValue(j+1,e); if(!X.GetLocation(e)) X.Insert(X.GetLength()+1,e); } } * 数据结构与算法 2.5 集合运算的模拟 【算法2-18】 void AND(SqList X,SqList Y) {/* 顺序表实现集合交运算 */ ElemType e; for(int j=0;jX.GetLength();j++) { X.GetValue(j+1,e); if(!Y.GetLocation(e)) X.Delete(j+1); } } * 数据结构与算法 2.5 集合运算的模拟 【算法2-19】 void XOR(SqList X,SqList Y) {/* 顺序表实现集合差运算 */ ElemType e; for(int j=0;jY.GetLength();j++) { X.GetValue(j+1,e); if(Y.GetLocation(e)) X.Delete(j+1); } } 2. 在单链表上实现集合并、交、差运算 * 数据结构与算法 2.6 小结 本章学习了线性数据结构中的典型代表——线性表，线性表包含n个具有“前-后”关系的元素，它与现实生活中“表”的概念基本上致，且表中元素都具有相同的结构。现实问题经抽象具有线性表的特性后，还要选择适合的存储方法来表示线性表，线性表既可以用顺序存储表示、也可以用链式存储表示，对基本顺序表、游标顺序表和单链表做了细致的分析并实现了主要的操作，并对算法效率进行对比。算法性能的优劣、某一种表示方法的改进都是一种相对的概念，要与具体问题相联系。 * 数据结构与算法 2.2 线性表的顺序存储表示 【算法2-9】 bool BuoyList::Delete(int i) { if(i1||ilength) return false; int temp=base[i-1].buoy; int k=i; while(klength) { base[k-1].buoy=base[k].buoy; /* 3 */ k++; } base[k-1].buoy=temp; length--; recycle++; return true; } * 数据结构与算法 2.2 线性表的顺序存储表示 5. 游标顺序表的输出操作 （1）输出单个元素 在指定输出第i个元素的情况下，我们可以借助前面实现的按位查找算法2-6-1。 【算法2-10-1】 bool BuoyList::Output(int i) { ElemType e; if(GetValue(i,e)) { couteendl; return true; } return false; } * 数据结构与算法 2.2 线性表的顺序存储表示