《数据结构》陈慧南_第02章线性表

《《数据结构》陈慧南_第02章线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构DataStructuresinC++南京邮电大学计算机学院陈慧南2006年9月第2章线性表南京邮电大学计算机学院陈慧南2006年9月2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算南京邮电大学计算机学院陈慧南2006年9月2.1线性表ADT南京邮电大学计算机学院陈慧南2006年9月线性表的定义线性表是n(0)个元素a0,a1,…,an-1的线性序列，记为:(a0,a1,…,an-1)。其中n是线性表中元素的个数，称为线性表的长度；n=0时称为空表。ai是表中下标为i的元素（i=0,1,…,n-1），称ai是

2、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。若

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）南京邮电大学计算机学院陈慧南2006年9月线性表

4、类templateclassLinearList{public:……virtualboolFind(inti,T&x)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;……protected:intn;//线性表的长度};南京邮电大学计算机学院陈慧南2006年9月2.2线性表的顺序表示南京邮电大学计算机学院陈慧南2006年9月2.2.1顺序存储结构顺序存储表示是用一组地址连续的存储单元依次存储线性表中元素。顺序表顺序表示的线性表称为顺序表a0a1…ai…an-1…

5、01…i…n-1…maxLength-1南京邮电大学计算机学院陈慧南2006年9月地址计算公式若已知顺序表中每个元素占k个存储单元，第一个元素a0在计算机内存中的首地址是loc(a0)，则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k随机存取结构只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。南京邮电大学计算机学院陈慧南2006年9月2.2.2顺序表类顺序表类templateclassSeqList:publicLinearList

6、>{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月动态存储

7、分配构造函数，构建一个空线性表templateSeqList::SeqList(intmSize){maxLength=mSize;elements=newT[maxLength];n=0;}南京邮电大学计算机学院陈慧南2006年9月析构函数，撤消一个顺序表templateSeqList::~SeqList(){delete[]elements;}南京邮电大学计算机学院陈慧南2006年9月2.2.3线性表运算实现搜索运算Find(i,x):查找下标为i的元素ai。在x中返回表中下标为i的元素ai(即表中第i+1

8、个元素)。如果不存在，则返回false，否则返回true。x=elements[