南邮数据结构ppt课件

1、南京邮电大学计算机学院 2006年9月,数据结构,Data Structures in C+,第2章 线性表,内容提要 定义线性表抽象数据类型； 讨论线性表的顺序存储表示方法； 讨论单链表、循环链表等链接存储表示方法； 线性表的应用实例多项式的算术运算,南京邮电大学计算机学院 2006年9月,2.1 线性表ADT,2.1 线性表ADT 2.2 线性表的顺序表示 2.2.1 顺序存储结构 2.2.2 顺序表类 2.2.3 线性表运算实现,南京邮电大学计算机学院 2006年9月,线性表的定义 线性表是n(0)个元素a0,a1,an-1 的线性序列，记为: (a0,a1,an-1)。其中n是线性表中

2、元素的个数，称为线性表的长度；n=0时称为空表。 ai是表中下标为i的元素（i=0,1,n-1），称ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。 线性表是动态数据结构，它的表长可以改变。,南京邮电大学计算机学院 2006年9月,线性表ADT ADT LinearList 数据： 0个或多个元素的线性序列（a0,a1,.,an-1），其最大允许长度为MaxListSize。 运算： Create()： 创建一个空线性表。 Destroy()：撤消一个线性表。 IsEmpty()：若线性表空，则返回true；否则返回false。 Length()： 返回表中元素个数。,南京邮电大学

3、计算机学院 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-

4、1）,南京邮电大学计算机学院 2006年9月,线性表类 template class LinearList public: virtual bool Find(int i,T,南京邮电大学计算机学院 2006年9月,南京邮电大学计算机学院 2006年9月,2.2 线性表的顺序表示,2.1 线性表ADT 2.2 线性表的顺序表示 2.2.1 顺序存储结构 2.2.2 顺序表类 2.2.3 线性表运算实现,2.2.1 顺序存储结构,顺序存储表示 是用一组地址连续的存储单元依次存储线性表中元素。 顺序表 顺序表示的线性表称为顺序表,南京邮电大学计算机学院 2006年9月,地址计算公式 若已知顺序表中

5、每个元素占k个存储单元，第一个元素a0在计算机内存中的首地址是loc(a0)，则表中任意一个元素ai在内存中的存储地址loc(ai)为 loc(ai)=loc(a0)+i*k 随机存取结构 只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。,南京邮电大学计算机学院 2006年9月,2.2.2 顺序表类,顺序表类 template class SeqList:public LinearList public: /公有函数 SeqList(int mSize); SeqList() delete elements; /教材有误 bool Fi

6、nd(int i,T ,南京邮电大学计算机学院 2006年9月, private:/私有数据 int maxLength; /顺序表的最大长度 T *elements; /动态一维数组的指针 ;,南京邮电大学计算机学院 2006年9月,动态存储分配 构造函数，构建一个空线性表 template SeqList:SeqList(int mSize) maxLength=mSize; elements=new TmaxLength; n=0; ,南京邮电大学计算机学院 2006年9月,析构函数，撤消一个顺序表 template SeqList: SeqList() delete elements;

7、 ,南京邮电大学计算机学院 2006年9月,2.2.3 线性表运算实现,搜索运算 Find(i,x): 查找下标为i的元素ai。 在x中返回表中下标为i的元素ai (即表中 第i+1个元素)。如果不存在，则返回 false，否则返回true。,x=elementsi; 渐近时间复杂度：O(1),南京邮电大学计算机学院 2006年9月,template bool SeqList:Find(int i,T ,南京邮电大学计算机学院 2006年9月,插入运算 Insert(i,x)：在表中下标为i的元素ai后插入x。 若i=-1，则将新元素x插在最前面。若插入成功，返回true；,南京邮电大学计算机

8、学院 2006年9月,插入运算的平均时间复杂度 分析：设顺序表长度为n，共有n+1个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即Pi=1/(n+1)，在位置i（i=-1,0,n-1）后插入一个元素要移动 n-i-1个元素。,南京邮电大学计算机学院 2006年9月,template bool SeqList:Insert(int i,T x) /在元素ai之后插入x if (in-1) /越界检查 couti;j-) elementsj+1=elementsj; elementsi+1=x;n+; return true; ,南京邮电大学计算机学院 2006年9月,删除运算 Del

9、ete(i)： 删除元素ai。,南京邮电大学计算机学院 2006年9月,删除运算的平均时间复杂度 分析: 设顺序表长度为n,则删除元素ai（i=0,n-1）,要移动n-i-1元素。若删除表中每个元素的概率是相等的，即Qi=1/n，,南京邮电大学计算机学院 2006年9月,template bool SeqList:Delete(int i) /删除元素ai if (!n) /下溢出检查 coutn-1) coutOut Of Boundsendl; return false; /从前往后逐个前移元素 for (int j=i+1;jn;j+) elementsj-1=elementsj; n-; return true; ,南京邮电大学计算机学院 2006年9月,void main() int x=10; SeqList r(4); r.Insert(-1,x); r.Insert(-1,x); r.Output(cout); /? 请复习C+，理解这一函数 ,南京邮电大学计算机学院 2006