数据结构与STL_第2章_线性表

第二章线性表北京邮电大学信息与通信工程学院《数据结构与STL》《数据结构与STL》2第二章线性表学习内容：2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4顺序表与链表的比较2.5应用举例2.6STL中的相关模板类-3-逻辑结构——4种集合线性树图本章的内容《数据结构与STL》42.1线性表的逻辑结构线性表——最典型的线性结构是零个或多个具有相同类型的数据元素构成的有限序列L=（a1，a2，…，an）线性表中数据元素的个数，称为线性表的长度。长度等于零的线性表称为空表。记为:L=()ai（1≤i≤n）称为数据元素；i表示该元素在线性表中的位置或序号。《数据结构与STL》5a1称为第一个元素或开始结点，an称为最后一个元素或终端结点对于中间任意一个元素ai（1in）：称ai-1为ai的直接前驱称ai+1为ai的直接后继a1a2a3anL=（a1，a2，…，an）性质：对于非空线性表：1.有且仅有一个开始结点a1，a1没有直接前趋2.有且仅有一个终端结点an，an没有直接后继3.其余的任意内部结点ai（1in）有且仅有一个直接前趋结点ai-1，有且仅有一个直接后继结点ai+1。《数据结构与STL》6线性表举例英文字母表：（A，B，C，D，…，X，Y，Z）一周中的7天：（星期日，星期一，星期二，星期三，星期四，星期五，星期六）学生成绩单姓名英语数据结构高数学号丁一9678870101李二8790780102张三6786860103孙红6981960104王冬8774660105《数据结构与STL》7线性表的运算1.求长度GetLength(L)求线性表L的表长。2.置空表SetNull(L)将线性表L置成空表。3.按位查找Get(L,i)查找线性表L中的第i个元素，i应满足1≤i≤GetLength(L)。4.修改Set(L,i,x)修改线性表L中的第i个元素的值为x。5.删除Delete(L,i)删除线性表L中的第i个元素。6.插入Insert(L,i,x)在线性表L中第i个位置上插入一个值为x的新元素。7.按值查找Locate(L,x)查找线性表L中值为x的元素。8.排序sort(L)按某种要求重新排列线性表L中各元素的顺序。《数据结构与STL》8第二章线性表学习内容：2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4顺序表与链表的比较2.5应用举例2.6STL中的相关模板类《数据结构与STL》92.2线性表的顺序存储结构用顺序存储方法存储的线性表称为顺序表（sequentiallist）a1a2ai-1an......表区空闲区LOC(a1)...aiai+1LOC(ai)c设顺序表第一个元素的存储地址为LOC(ai)，每个元素占用c个存储单元，则ai(1≤i≤n)的地址LOC(ai)=?：顺序表是一种随机存取结构LOC(ai)=LOC(a1)+(i-1)×c《数据结构与STL》10顺序表C++模板类定义constintMAXSIZE=1000;//定义顺序表的最大长度templateclassT//定义模板类SeqListclassSeqList{public:SeqList(){length=0;}//无参构造函数SeqList(constTa[],intn);//有参构造函数，使用含有n个元素的数组a初始化intGetLength(){returnlength;}//获取顺序表的长度voidPrintList();//按次序遍历顺序表中的各个数据元素voidInsert(inti,Tx);//在顺序表的第i个位置上插入值为x的新元素TDelete(inti);//删除顺序表第i个元素，并将该元素返回TGet(inti);//获取顺序表第i个位置上的元素intLocate(Tx);//查找顺序表中值为x的元素，找到后返回其位置private:Tdata[MAXSIZE];//存储顺序表数据元素的数组intlength;//顺序表的长度};《数据结构与STL》11顺序表存储形式类数据成员1：data数组类数据成员2:lengthL＝（a1，a2，…,ai-1，ai,…，an)MAXSIZE-1a1…ai-1ai…an空闲下标元素data[0]…data[i-1]…data[n-1]…data[?]《数据结构与STL》12顺序表的基本运算1——初始化构造函数无参构造函数用于建立空顺序表有参构造函数创建一个长度为n的顺序表——使用含有n个元素的数组a初始化[1]若n太大，则抛出异常[2]将数组a中的各个元素赋值到data数组中[3]修改顺序表长度伪代码《数据结构与STL》13C++代码实现：//有参构造函数，使用含有n个元素的数组a初始化templateclassTSeqListT::SeqList(constTa[],intn){if(nMAXSIZE)throw数组长度超过顺序表的最大长度;for(inti=0;in;i++)data[i]=a[i];length=n;}《数据结构与STL》14基本运算2——遍历顺序表按序号依次访问顺序表中的各个数据元素templateclassTvoidSeqListT::PrintList(){cout按序号依次遍历线性表中的各个数据元素:endl;for(inti=0;ilength;i++)coutdata[i];coutendl;}数据元素为什么数据类型才允许cout？假定数据元素为构造类型，该如何设计相应的显示函数？a1…ai-1ai…an空闲《数据结构与STL》15基本运算3——插入操作a1a2...ai-1xai+1...ana1a2...ai-1aiai+1...anai长度为n长度为n+1[1]若表满，则抛出上溢异常[2]若插入位置错误，则抛出位置异常[3]从最后一个元素到第i个元素，顺序后移[4]将x存放到第i个元素位置[5]修改顺序表长度加1伪代码xx《数据结构与STL》16C++代码实现：//在顺序表的第i个位置上插入值为x的新元素templateclassTvoidSeqListT::Insert(inti,Tx){if(length=MAXSIZE)throw上溢异常;if(i1||i=length+1)throw位置异常;//从最后一个元素开始顺序后移，直到第i个为止for(intj=length;j=i;j--)data[j]=data[j-1];data[i-1]=x;//将x插入到顺序表第i个位置length++;}《数据结构与STL》17插入操作时间复杂度分析最好情况：a1a2…aia1a2…xa1a2…ai+1…aiai+1…xaiai+1…an…anx…最坏情况：a1a2…aiai+1…an…a1a2…aiai+1…an…一般情况：a1a2…aiai+1…an…an…O(1)O(n)O(?)《数据结构与STL》18对顺序表进行插入操作，在等概率情况下，平均要移动表中一半的元素，算法的平均复杂度为O(n)a1a2…xaiai+1…a1a2…aiai+1…an…an…T(n)=11(1)niipni11ipn2nT(n)==O(n)《数据结构与STL》19基本操作4——删除操作将第i个元素删除a1a2…aiai+1…an…a1a2…ai+1…an…什么情况下，不能进行删除操作？[1]如果表空，则抛出下溢异常；[2]如果删除元素位置不合理，则抛出位置异常；[3]取出将被删除的元素；[4]依次从第i+1个元素开始到第n个元素分别前移一个位置；[5]表长减1，并返回被删元素的值。伪代码《数据结构与STL》20C++代码实现：//在线性表的第i个位置上插入值为x的新元素templateclassTTSeqListT::Delete(inti){if(0==length)throw下溢异常;if(i1||ilength)throw位置异常;Tx=data[i-1];//将待删除元素暂存//从第i+1个元素开始顺序前移，直到最后一个元素for(intj=i;jlength;j++)data[j-1]=data[j];length--;returnx;}-21-顺序表删除操作的时间复杂度假设表中任意位置删除元素的机会是均等的，则表长为n的顺序表中删除一个元素，平均需要移动多少个元素？删除位置：i∈(1~n)每个位置需要移动的元素数:n-iniinnnT1)(1)(21n《数据结构与STL》22下标：i-1基本操作5——查找操作按位查找：查找顺序表中指定位置的数据元素//获取线性表第i个位置上的元素templateclassTTSeqListT::Get(inti){if(i1||ilength)throw查找位置非法;returndata[i-1];}a1a2…aiai+1…an…时间复杂度？《数据结构与STL》23基本操作5——查找操作按值查找:查找顺序表中指定数值的数据元素。找到——查找成功：返回序号找不到——查找失败：返回错误标志,如0a1a2…xaiai+1…an…//查找线性表中值为x的元素，找到后返回其位置templateclassTintSeqListT::Locate(constTx){for(inti=0;ilength;i++)if(x==data[i])returni+1;return0;//查找失败}xxxx循环一次，判断几次？《数据结构与STL》24x思考如果data数组从data[1]开始存储顺序表数据元素,data[0]不存储,能否设计更高效的算法？//查找线性表中值为x的元素，找到后返回其位置//设data[0]默认不存储顺序表数据元素templateclassTintSeqListT::Locate(constTx){data[0]=x;inti=length;while(x!=data[i])i--;returni;}a1a2…aiai+1…an…012…ii+1…n《数据结构与STL》25试分析顺序表按值查找操作的时间复杂度最好情况：O(1)最坏情况：O(n)一般情况：T(n)==O(n)12n《数据结构与STL》26顺序表应用举例顺序表类设计好以后该如何应用？#includeSeqList.hvoidmain(){inta[7]={1,2,3,4,5,6,7};SeqListintlist(a,7);list.PrintList();list.Insert(1,0);list.PrintList();intx=list.Delete(8);cout删除元素：xendl;list.PrintList();intp=list.Locate(4);cout元素4的位置：pendl;}按序号依次遍历线性表中的各个数据元素:1234567按序号依次遍历线性表中的各个数据元素:01234567删除元素：7按序号依次遍历线性表中的各个数据元素:0123456元素4的位置：5-27-顺序表的优缺点顺序表SeqList的实质是一个容器，用来存储同类型的多个数据，并且封装了一些算法，以简化上层的应用。缺陷1存储空间静态分配2插入删除需要移动大量元素，效率低优点1结构简单2可直接定位表中元素，随机查找速度快《数据结构与STL》28第二章线性表学习内容：2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4顺序表与链表的比较2.5应用举例2.6STL中的相关模板类《数据结构与STL》29链表（linkedlist）采用链式存储方式存储的线性表链表：动态存储顺序表：静态存储动态链表静态链表按实现方式分类单向链表双向链表循环链表按链接方式分类链表分类链式存储是一种应用非常广泛的存储方式《数据结构与STL》30单链表数据元素的逻辑次序和物理次序不一定相同