数据结构讲义(第二章线性表x)

公司数据结构第二章线性表2主要内容线性表的概念及定义1线性表的顺序存储2线性表的链式存储3线性表的应用43§2.1线性表的概念及定义线性表(LinearList)：是由n(n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记做：L=(a1,a2,…，ai-1，ai，ai+1，…，an)数据元素的逻辑特性：数据元素之间的先后顺序为“一对一”的关系。ai-1领先于ai则ai-1是ai的直接前驱元素ai-1落后于ai则ai是ai-1的直接后继元素除a1外，每个元素有且仅有一个直接前驱元素除an外，每个元素有且仅有一个直接后继元素线性表中数据元素的个数n(n≥0)称为线性表的长度（n=0时，该线性表称为空表）4线性表的前驱与后继a1a2a3a4a5数据元素直接前驱直接后继前驱后继a1无a2无a2,a3,a4,a5a2a1a3a1a3,a4,a5a5a4无a1,a2,a3,a4无a3a2a3a1,a2a4,a5a4a3a5a1,a2,a3a5顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743存储要点用一段地址连续的存储单元依次存储线性表中的数据元素§2.2线性表的顺序存储顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743存储空间的起始位置用什么属性来描述顺序表？顺序表的容量（最大长度）§2.2线性表的顺序存储顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743如何实现顺序表的内存分配？顺序表一维数组§2.2线性表的顺序存储0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：数组的长度Max线性表的长度Length数组的长度大于等于当前线性表的长度§2.2线性表的顺序存储如何求得任意元素的存储地址？0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)§2.2线性表的顺序存储0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲Loc(ai)=Loc(a1)+(i-1)×c顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)§2.2线性表的顺序存储顺序表——随机存取顺序表中数据元素的存储地址是其序号的线性函数，只要确定了存储顺序表的起始地址，计算任意一个元素的存储地址的时间是相等的，具有这一特点的存储结构称为随机存取（randomaccess）结构§2.2线性表的顺序存储12§2.2线性表的顺序存储线性表的顺序存储：是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。a1a2a3a4a5……a1a2a3a4a5逻辑位置：物理位置：顺序表类的声明constintMaxSize=100;templateclassDataType//模板类classSeqList{public:SeqList();//构造函数SeqList(DataTypea[],intn);~SeqList();//析构函数intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti,DataTypex);private:DataTypedata[MaxSize];intlength;};2.2.2顺序表的实现142.2.2顺序表的实现constintMaxSize=100;templateclassDataTypeclassSeqList1{private:DataTypedata[MaxSize];//一维数组intlength;//线性表长度public:………;//成员函数;}；a1a2a3…alength…data[0]data[1]data[2]data[length-1]lengthMaxSize1.在类中使用静态一维数组静态一维数组是指在声明定义数组时，所给出数组的大小是确定的。数组的大小留有余地。152.2.1顺序表存储结构templateclassDataTypeclassSeqList2{private:DataType*data；//用指针表示一维数组intlength;//表的实际长度intmaxlen;//表的最大长度，容量public:………;//成员函数};2．在类中使用动态一维数组动态一维数组是指在声明定义数组时用指针表示，数组的大小没有确定。在数据成员中除了数组data、表长length，还给出表的容量maxlen.操作接口：SeqList()算法描述：templateclassDataTypeSeqListDataType::SeqList(){length=0;}顺序表的实现——无参构造函数data2.2.2顺序表的实现操作接口：SeqList(DataTypea[],intn)顺序表数组a351224334235122433422.2.2顺序表的实现l顺序表的实现——有参构造函数length=5templateclassDataTypeSeqListDataType::SeqList(DataTypea[],intn){if(nMaxSize)cout参数非法endl;else{for(inti=0;in;i++)data[i]=a[i];length=n;}}2.2.2顺序表的实现顺序表的实现——有参构造函数例：线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。(a1，…，ai-1，ai，…，an)…(a1，…，ai-1，x，ai，…，an)length++;顺序表移动元素插入元素1234567810949152830304262514915212830304262514915283030425162length=8length=9顺序表的实现——插入2.2.2顺序表的实现操作接口：voidInsert(inti,DataTypex)插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,x,ai,…,an)ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化2.2.2顺序表的实现顺序表的实现——插入33例：（35，12，24，42），在i=2的位置上插入33。表满：length=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序号）35122442a1a2a3a40123442241233什么时候不能插入？注意边界条件2.2.2顺序表的实现顺序表的实现——插入1.如果表满了，则抛出上溢异常;2.如果元素的插入位置不合理，则抛出位置异常;3.将最后一个元素至第i个元素分别向后移动一个位置；4.将元素x填入位置i处；5.表长加1；算法描述2.2.2顺序表的实现顺序表的实现——插入templateclassDataTypevoidSeqListDataType::Insert(inti,DataTypex){if(length=MaxSize)throw上溢”endl;elseif(i1||ilength+1)throw“插入位置错误”;else{for(intj=length;j=i;j--)data[j]=data[j-1];data[i-1]=x;length++;}}2.2.2顺序表的实现顺序表的实现——插入最好情况（i=n+1）：基本语句执行0次，时间复杂度为O(1)。最坏情况（i=1）：基本语句执行n+1次，时间复杂度为O(n)。平均情况（1≤i≤n+1）：时间复杂度为O(n)。时间性能分析+-+=11)=1(niiinp+-+)=1(11i=1inn2n=O(n)2.2.2顺序表的实现顺序表的实现——插入n+125例：线性表(4,9,15,21,28,30,30,42,51,62)，删除28。(a1，…，ai-1，ai，ai+1，…，an)…(a1，…，ai-1，ai+1，…，an)length--;顺序表移动元素123456781094915212830304262514915213030425162length=9length=828删除顺序表的实现——删除2.2.2顺序表的实现操作接口：DataTypeDelete(inti)删除前：(a1,…,ai-1,ai,ai+1,…,an)删除后：(a1,…,ai-1,ai+1,…,an)ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化2.2.2顺序表的实现顺序表的实现——删除例：（35,33,12,24,42），删除i=2的数据元素。仿照顺序表的插入操作，完成：1.分析边界条件；2.分别给出伪代码和C++描述的算法；3.分析时间复杂度。35a1a2a3a40123442241233a51224422.2.2顺序表的实现顺序表的实现——删除templateclassDataTypeDataTypeSeqListDataType::Delete(inti,DataTypex){if(length==0)throw“下溢”;elseif(i1||ilength)throw“删除位置错误”;else{x=data[i-1];for(intj=i;jlength;j++)data[j-1]=data[j];length--;}}2.2.2顺序表的实现顺序表的实现——删除操作接口：DataTypeGet(inti)0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲算法描述：templateclassDataTypeDataTypeSeqListDataType::Get(inti){if(i=1&&i=length)returni-1;}时间复杂度？2.2.2顺序表的实现顺序表的实现——按位置查找操作接口：intLocate(DataTypex)35a1a2a3a40123442241233a5例：在（35,33,12,24,42）中查找值为12的元素，返回在表中的序号。iii注意序号和下标之间的关系2.2.2顺序表的实现顺序表的实现——按值查找templateclassDataTypeintSeqListDataType::Locate(DataTypex){for(inti=0;ilength;i++)if(data[i]==x)returni+1;return0;}算法描述：时间复杂度？2.2.2顺序表的实现顺序表的实现——按值查找templateclassDataTypevoidSeqListDataType::PrintList(){for(inti=0;ilength;i++)coutdata[i];}算法描述：时间复杂度？2.2.2顺序表的实现顺序表的实现——遍历算法33插入和删除算法的时间复杂度分析在顺序表中插入或删除一个元素时，平均移动表中大约一半的数据元素。插入平均移动n/2个数据元素，删除平均移动(n-1)/2个数据元素，忽略常数项以及常系数。若表长为n，则两个算法的时间复杂度都为：T(n)=O(n)。2.2.2顺序表的实现341.无需为表示结点间的逻辑关系而增加额外的存储空间；2.可方便地随机存取表中的任一元素。优点1.插入或删除运算不方便，需要移动大量的结点，其效率较低；2.需要预先确定顺序表的最大表长，由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配