欢迎来到天天文库
浏览记录
ID:55790702
大小:148.50 KB
页数:25页
时间:2020-06-02
《南邮数据结构ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库。
1、数据结构DataStructuresinC++南京邮电大学计算机学院2006年9月第2章线性表内容提要定义线性表抽象数据类型;讨论线性表的顺序存储表示方法;讨论单链表、循环链表等链接存储表示方法;线性表的应用实例——多项式的算术运算2.1线性表ADT2.1线性表ADT2.2线性表的顺序表示2.2.1顺序存储结构2.2.2顺序表类2.2.3线性表运算实现线性表的定义线性表是n(0)个元素a0,a1,…,an-1的线性序列,记为:(a0,a1,…,an-1)。其中n是线性表中元素的个数,称为线性表的长度;n=0时称为空表。ai是表
2、中下标为i的元素(i=0,1,…,n-1),称ai是ai+1的直接前驱元素,ai+1是ai的直接后继元素。线性表是动态数据结构,它的表长可以改变。线性表ADTADTLinearList{数据:0个或多个元素的线性序列(a0,a1,...,an-1),其最大允许长度为MaxListSize。运算:Create():创建一个空线性表。Destroy():撤消一个线性表。IsEmpty():若线性表空,则返回true;否则返回false。Length():返回表中元素个数。Find(i,x):在x中返回表中下标为i的元素ai。若不存在
3、,则返回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)线性表类template4、lassT>classLinearList{public:……virtualboolFind(inti,T&x)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;……protected:intn;//线性表的长度};2.2线性表的顺序表示2.1线性表ADT2.2线性表的顺序表示2.2.1顺序存储结构2.2.2顺序表类2.2.3线性表运算实现南京邮电大学计算机学院2006年9月2.2.1顺序存储结构顺序存储表示是用一组地址连续的存储单元依次存储线性表中元素5、。顺序表顺序表示的线性表称为顺序表地址计算公式若已知顺序表中每个元素占k个存储单元,第一个元素a0在计算机内存中的首地址是loc(a0),则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k随机存取结构只要给定loc(a0)和k,就可以确定线性表中任意一个元素的存储地址,换句话说,顺序表是一种随机存取结构。2.2.2顺序表类顺序表类templateclassSeqList:publicLinearList{public://公有函数SeqList(intmSize)6、;~SeqList(){delete[]elements;}//教材有误boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);……SingleListLinearListSeqList……private://私有数据intmaxLength;//顺序表的最大长度T*elements;//动态一维数组的指针};动态存储分配构造函数,构建一个空线性表templateSeqList::SeqList(intm7、Size){maxLength=mSize;elements=newT[maxLength];n=0;}析构函数,撤消一个顺序表templateSeqList::~SeqList(){delete[]elements;}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…maxLeng8、th-1templateboolSeqList::Find(inti,T&x)const{//O(1)if(i<09、10、i>n−1){//对i进行越界检查cout<<"OutofBounds"<
4、lassT>classLinearList{public:……virtualboolFind(inti,T&x)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;……protected:intn;//线性表的长度};2.2线性表的顺序表示2.1线性表ADT2.2线性表的顺序表示2.2.1顺序存储结构2.2.2顺序表类2.2.3线性表运算实现南京邮电大学计算机学院2006年9月2.2.1顺序存储结构顺序存储表示是用一组地址连续的存储单元依次存储线性表中元素
5、。顺序表顺序表示的线性表称为顺序表地址计算公式若已知顺序表中每个元素占k个存储单元,第一个元素a0在计算机内存中的首地址是loc(a0),则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k随机存取结构只要给定loc(a0)和k,就可以确定线性表中任意一个元素的存储地址,换句话说,顺序表是一种随机存取结构。2.2.2顺序表类顺序表类templateclassSeqList:publicLinearList{public://公有函数SeqList(intmSize)
6、;~SeqList(){delete[]elements;}//教材有误boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);……SingleListLinearListSeqList……private://私有数据intmaxLength;//顺序表的最大长度T*elements;//动态一维数组的指针};动态存储分配构造函数,构建一个空线性表templateSeqList::SeqList(intm
7、Size){maxLength=mSize;elements=newT[maxLength];n=0;}析构函数,撤消一个顺序表templateSeqList::~SeqList(){delete[]elements;}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…maxLeng
8、th-1templateboolSeqList::Find(inti,T&x)const{//O(1)if(i<0
9、
10、i>n−1){//对i进行越界检查cout<<"OutofBounds"<
此文档下载收益归作者所有