南京邮电大学数据结构A第2章

数据结构A·第2章南京邮电大学计算机学院计算机科学与技术系戴华[e-mail]2020/2/29第2章线性表内容提要1、定义线性表抽象数据类型；2、讨论线性表的顺序存储表示方法；3、讨论单链表、循环链表等链接存储表示方法；4、线性表的应用实例——多项式的算术运算。2.1线性表抽象数据类型课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算(a)集合结构(b)线性结构(c)树形结构(d)图状结构图1-2四种基本的结构关系2.1线性表抽象数据类型1.线性表举例表1-1学生情况表学号姓名性别B06050401杨慧女B06050402闵洁女B06050403范秋杰女B06050404唐丹瑶女………2.1线性表抽象数据类型线性表是n(0)个元素a0，a1，…，an-1的有序集合，记为（a0，a1，…，an-1）其中，n是线性表中元素的个数，称为线性表的长度，n=0时称为空表。2.线性表的定义设ai是线性表（a0，a1，…，an-1）中下标为i的元素（一般习惯说法，认为ai是表中第i+1个元素），i=0,1,…,n-1，则称ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。线性表是动态数据结构，它的表长可以改变。2.1线性表抽象数据类型ADT2.1线性表ADTADTLinearList{数据:0个或多个元素的线性序列（a0,a1,...,an-1），其最大允许长度为MaxListSize。运算:Create()：创建一个空线性表。Destroy()：撤消一个线性表。IsEmpty()：若线性表空，则返回true；否则返回false。Length()：返回表中元素个数。Find(i,x)：在x中返回表中下标为i的元素ai(即表中第i+1个元素)。如果不存在，则返回false，否则返回true。Search(x)：返回x在表中的下标；若x不在表中，则返回-1。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)：把表送至输出流。}3.线性表抽象数据类型2.1线性表抽象数据类型程序2.1线性表的C++类templateclassTclassLinearList{public:virtualboolIsEmpty()const=0;virtualintLength()const=0;virtualboolFind(inti,T&x)const=0;virtualintSearch(Tx)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;virtualboolUpdate(inti,Tx)=0;virtualvoidOutput(ostream&out)const=0;proteced:intn;};//保存在头文件linearlist.h//若线性表空，则返回true；否则返回false//线性表的长度//返回表中元素个数//如果不存在，则返回false，否则返回true//在x中返回表中下标为i的元素,//返回x在表中的下标//若x不表中，则返回-1//在元素ai之后插入x。若i=-1，//则x插在第一个元素a0前。插入成功返回true，否则返回false//删除元素ai,成功则返回true，否则返回false//将元素ai的值修改为x。//修改成功返回true，否则返回false//把表送至输出流线性表的规范2.2线性表的顺序表示1.线性表的两种存储表示法(1)顺序表示法(2)链接表示法2.线性表的顺序表示法用一组地址连续的存储单元依次存储线性表中元素。课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算逻辑上相邻的元素在物理（存储空间）上也相邻顺序表示的线性表称为顺序表。存储结构是逻辑结构在计算机内的映象，包括：元素和关系。2.2线性表的顺序表示（1）线性表的顺序表示法若已知顺序表示的线性表中每个元素占k个存储单元，第一个元素a0在计算机内存中的地址是loc(a0)，则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*ka0a1…ai…an-1…（2）地址计算公式（3）随机存取结构只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。loc(a0)loc(ai)ki个元素2.2线性表的顺序表示程序2.1线性表的C++类templateclassTclassLinearList{public:virtualboolIsEmpty()const=0;virtualintLength()const=0;virtualboolFind(inti,T&x)const=0;virtualintSearch(Tx)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;virtualboolUpdate(inti,Tx)=0;virtualvoidOutput(ostream&out)const=0;proteced:intn;//线性表的长度};3.顺序表类线性表的规范2.2线性表的顺序表示templateclassTclassSeqList:publicLinearListT{public://公有函数SeqList(intmSize);//创建一个空线性表~SeqList(){delete[]elements;};//撤销一个线性表boolIsEmpty()const;intLength()const;boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);boolUpdate(inti,Tx);voidOutput(ostream&out)const;private://私有数据intmaxLength;//顺序表的最大长度T*elements;//动态一维数组的指针};SeqListintL(5);程序2.2线性表的顺序表实现一组地址连续的存储单元线性表的实现T//定义了一个有5个整型值的顺序表对象+每个成员函数的实现2.2线性表的顺序表示classSeqList:publicLinearListT{public:SeqList(intmSize);……private:intmaxLength;T*elements;//动态一维数组的指针}4.动态一维数组描述顺序表a0a1…ai…an-1…01…i…n-1…maxLength-1顺序表在一维数组中的存储第一个元素最后一个元素elements2.2线性表的顺序表示(1)构造函数//创建一个空顺序表templateclassTSeqListT::SeqList(intmSize){maxLength=mSize;elements=newT[maxLength];//动态存储分配n=0;}(2)析构函数//撤消一个顺序表templateclassTSeqListT::~SeqList(){delete[]elements;}2.2线性表的顺序表示（1）搜索运算Find(i,x)：查找下标为i的元素ai在x中返回表中下标为i的元素ai（即表中第i+1个元素）。如果不存在，则返回false，否则返回true。x=elements[i];5.在顺序存储表示下实现线性表上定义的操作a0a1…ai…an-1…01…i…n-1…maxLength-1elements2.2线性表的顺序表示（1）搜索运算5.在顺序存储表示下实现线性表上定义的操作templateclassTboolSeqListT::Find(inti,T&x)const{if(i0||in-1){//对i进行越界检查coutOutofBoundsendl;returnfalse;}x=elements[i];//通过引用参数x返回下标为i的元素returntrue;}渐近时间复杂度：O(1)算法的健壮性2.2线性表的顺序表示（2）插入操作Insert(i,x)：在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功，返回true；…后移n-i-1个元素01…ii+1i+2…n-1…maxLength-1a0a1…ai…插入操作an-1x…ai+1…elementsfor(intj=n-1;ji;j--)elements[j+1]=elements[j];elements[i+1]=x;2.2线性表的顺序表示（2）插入操作templateclassTboolSeqListT::Insert(inti,Tx){if(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;}算法的健壮性Insert(i,x)：在表中下标为i的元素ai后插入x2.2线性表的顺序表示时间复杂度分析：①设顺序表长度为n，共有n+1个可插入元素的位置，在位置i（i=-1,0,…,n-1）后插入一个元素要移动n-i-1个元素渐近时间复杂度：O(n)-1-11(--1)12niinEnin（2）插入操作2)1n(n1...)1n(n0,1ni,...,n,1i次移动次移动②设在各位置处插入元素的概率是相等的，即Pi=1/(n+1)，则平均情况下在表中插入元素需要移动元素的个数为：2.2线性表的顺序表示（3）删除操作Delete(i)：删除元素ai。aia0…ai-1……前移n-i-1个元素0…i-1ii+1i+2…n-1…maxLength-1删除操作an-1……删除它ai+1for(intj=i+1;jn;j++)elements[j-1]=elements[j];n--;2.2线性表的顺序表示（3）删除操作Delete(i)：删除元素ai。templateclassTboolSeqListT::Delete(inti){if(!n)//下溢出检查{coutUnderFlowendl;returnfalse;}if(i0||in-1){coutOutOfBoundsendl;returnfalse;}for(intj=i+1;jn;j++)elements[j-1]=elements[j];//从前往后逐个前移元素n--;returntrue;}算法的健壮性2.2线性表的顺序表示时间复杂度分析：①设顺序表长度为n，则删除元素ai（i=0,…,n-1）,要移动n-i-1元素。渐近时间复杂度：O(n)（3）删除操作1011(1)2ndinEnin②若删除表中每个元素的概率是相等的，即Pi=1/n，则平均情况下从表中删除一个元素需要移动元素的个数为：0,1...,in-10n(n-1)(n-1)(n-2)...12in移动次，，移动次2.2线性表的顺序表示（4）顺序表的应用voidmain(){intx=10;SeqListintr(4);r.Insert(-1,x);r.Insert(-1,x)