资源描述：
《《数据结构A》第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
2、,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月
3、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到
4、表：（a0,a1,...,an-1）南京邮电大学计算机学院陈慧南2006年9月线性表类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顺序存储结构顺序存
5、储表示是用一组地址连续的存储单元依次存储线性表中元素。顺序表顺序表示的线性表称为顺序表a0a1…ai…an-1…01…i…n-1…maxLength-1南京邮电大学计算机学院陈慧南2006年9月地址计算公式若已知顺序表中每个元素占k个存储单元，第一个元素a0在计算机内存中的首地址是loc(a0)，则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k随机存取结构只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。南京邮电大学计算机学院
6、陈慧南2006年9月2.2.2顺序表类顺序表类templateclassSeqList:publicLinearList{public://公有函数SeqList(intmSize);~SeqList(){delete[]elements;}boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);……SingleListLinearListSeqList南京邮电大学计算机学院陈慧南2006年9月……pr
7、ivate://私有数据intmaxLength;//顺序表的最大长度T*elements;//动态一维数组的指针};南京邮电大学计算机学院陈慧南2006年9月动态存储分配构造函数，构建一个空线性表templateSeqList::SeqList(intmSize){maxLength=mSize;elements=newT[maxLength];n=0;}南京邮电大学计算机学院陈慧南2006年9月析构函数，撤消一个顺序表templateSeqList::~SeqList(){del
8、ete[]elements;}南京邮电大学计算机学院陈慧南2006年9月2.2.3线性表运算实现搜索运算Find(i,x):查找下标为i的元素ai。在x中返回表中下标为i的元素ai(即表中第i+1个元素)。如果不存在，则返回false，否则返回true。x=elements[
