南邮数据结构课件2

南京邮电大学计算机学院2006年9月数据结构DataStructuresinC++南京邮电大学计算机学院2006年9月第2章线性表内容提要定义线性表抽象数据类型；讨论线性表的顺序存储表示方法；讨论单链表、循环链表等链接存储表示方法；线性表的应用实例——多项式的算术运算南京邮电大学计算机学院2006年9月2.1线性表ADT2.1线性表ADT2.2线性表的顺序表示2.2.1顺序存储结构2.2.2顺序表类2.2.3线性表运算实现南京邮电大学计算机学院2006年9月线性表的定义线性表是n(0)个元素a0,a1,…,an-1的线性序列，记为:(a0,a1,…,an-1)。其中n是线性表中元素的个数，称为线性表的长度；n=0时称为空表。ai是表中下标为i的元素（i=0,1,…,n-1），称ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。线性表是动态数据结构，它的表长可以改变。南京邮电大学计算机学院2006年9月线性表ADTADTLinearList{数据：0个或多个元素的线性序列（a0,a1,...,an-1），其最大允许长度为MaxListSize。运算：Create()：创建一个空线性表。Destroy()：撤消一个线性表。IsEmpty()：若线性表空，则返回true；否则返回false。Length()：返回表中元素个数。南京邮电大学计算机学院2006年9月Find(i,x)：在x中返回表中下标为i的元素ai。若不存在，则返回false，否则返回true。Search(x)：若x不在表中，则返回-1，否则返回x在表中的下标。Insert(i,x)：在元素ai之后插入x。若i=-1，则x插在第一个元素a0前。若插入成功，则返回true，否则返回false。Delete(i)：删除元素ai。若删除成功，则返回true，否则返回false。Update(i,x)：将元素ai的值修改为x。若修改成功，则返回true，否则返回false。Output(out)：把表送至输出流}//插入x到表：（a0,a1,...,an-1）南京邮电大学计算机学院2006年9月线性表类templateclassTclassLinearList{public:……virtualboolFind(inti,T&x)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;……protected:intn;//线性表的长度};南京邮电大学计算机学院2006年9月2.2线性表的顺序表示2.1线性表ADT2.2线性表的顺序表示2.2.1顺序存储结构2.2.2顺序表类2.2.3线性表运算实现南京邮电大学计算机学院2006年9月2.2.1顺序存储结构顺序存储表示是用一组地址连续的存储单元依次存储线性表中元素。顺序表顺序表示的线性表称为顺序表南京邮电大学计算机学院2006年9月地址计算公式若已知顺序表中每个元素占k个存储单元，第一个元素a0在计算机内存中的首地址是loc(a0)，则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k随机存取结构只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。南京邮电大学计算机学院2006年9月2.2.2顺序表类顺序表类templateclassTclassSeqList:publicLinearListT{public://公有函数SeqList(intmSize);~SeqList(){delete[]elements;}//教材有误boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);……SingleListLinearListSeqList南京邮电大学计算机学院2006年9月……private://私有数据intmaxLength;//顺序表的最大长度T*elements;//动态一维数组的指针};南京邮电大学计算机学院2006年9月动态存储分配构造函数，构建一个空线性表templateclassTSeqListT::SeqList(intmSize){maxLength=mSize;elements=newT[maxLength];n=0;}南京邮电大学计算机学院2006年9月析构函数，撤消一个顺序表templateclassTSeqListT::~SeqList(){delete[]elements;}南京邮电大学计算机学院2006年9月2.2.3线性表运算实现搜索运算Find(i,x):查找下标为i的元素ai。在x中返回表中下标为i的元素ai(即表中第i+1个元素)。如果不存在，则返回false，否则返回true。x=elements[i];渐近时间复杂度：O(1)a0a1…ai…an-1…01…i…n-1…maxLength-1南京邮电大学计算机学院2006年9月templateclassTboolSeqListT::Find(inti,T&x)const{//O(1)if(i0||in−1){//对i进行越界检查coutOutofBoundsendl;returnfalse;}x=elements[i];//通过引用参数x返回下标为i的元素returntrue;}南京邮电大学计算机学院2006年9月插入运算Insert(i,x)：在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功，返回true；南京邮电大学计算机学院2006年9月2)1n(n1...)1n(n0,1ni,...,n,1i次移动次移动插入运算的平均时间复杂度分析：设顺序表长度为n，共有n+1个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即Pi=1/(n+1)，在位置i（i=-1,0,…,n-1）后插入一个元素要移动n-i-1个元素。)n(O2n1)-i(n1n1E1-n-1ii移动元素次数：南京邮电大学计算机学院2006年9月templateclassTboolSeqListT::Insert(inti,Tx){//在元素ai之后插入xif(i-1||in-1){//越界检查coutOutOfBoundsendl;returnfalse;}if(n==maxLength){//上溢出检查coutOverFlowendl;returnfalse;}//从后往前逐个后移元素for(intj=n-1;ji;j--)elements[j+1]=elements[j];elements[i+1]=x;n++;returntrue;}南京邮电大学计算机学院2006年9月删除运算Delete(i)：删除元素ai。南京邮电大学计算机学院2006年9月删除运算的平均时间复杂度分析:设顺序表长度为n,则删除元素ai（i=0,…,n-1）,要移动n-i-1元素。若删除表中每个元素的概率是相等的，即Qi=1/n，1n0id21n)1in(n1E平均移动元素次数：21)-n(n1...1)-(n1)-(n01-ni...,1n,0i次，移动次，移动南京邮电大学计算机学院2006年9月templateclassTboolSeqListT::Delete(inti){//删除元素aiif(!n){//下溢出检查coutUnderFlowendl;returnfalse;}if(i0||in-1){coutOutOfBoundsendl;returnfalse;}//从前往后逐个前移元素for(intj=i+1;jn;j++)elements[j-1]=elements[j];n--;returntrue;}南京邮电大学计算机学院2006年9月voidmain(){intx=10;SeqListintr(4);r.Insert(-1,x);r.Insert(-1,x);r.Output(cout);//??请复习C++，理解这一函数}南京邮电大学计算机学院2006年9月线性表的顺序存储表示的优缺点优点：随机存取；存储空间利用率高。缺点：插入、删除效率低；必须按事先估计的最大元素个数分配连续的存储空间，难以临时扩大。南京邮电大学计算机学院2006年9月P22页，线性表的应用例子（例2.1）留作自学