数据结构（牛小飞）2 表单链表ppt课件.ppt

《数据结构（牛小飞）2 表单链表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、链式存储结构的实现表(List)的链式存储结构—单链表单链表部分操作的实现小结和作业复习顺序存储结构的实现顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素a0a1…ai-1ai…an-1线性表的起始地址(基地址)publicclassMyArrayList>{privateAnyType[]theItems;//存储空间基址privateinttheSize;//表的大小privatestaticfinalintDEFAULT_

2、CAPACITY=10;//数组容量……成员方法}线性表顺序存储结构的实现线性表顺序存储结构的实现构造函数MyArrayList()get(intidx)set(intidx,AnyTypenewVal)add(AnyTypex)、add(intidx,AnyTypex)remove(intidx)add原型：publicvoidadd(intidx,AnyTypex)作用：把x插入线性表，作为第idx个数据元素，即在顺序表的第idx个位置之前插入新的数据元素x。逻辑结构的变化→

3、x>,(a0,…,aidx-1,aidx,…,an-1)→(a0,…,aidx-1,x,aidx,…,an-1)add存储结构的变化a0a1xa2a3a4a5a0a1a2a3a4a5add(2,x)6theSize7theSizeadd过程：1、判断i的合法性2、移动3、赋值4、theSize++addadd—合法性A10a0a1a2a3a4a5a6一般的0≤i≤theSize如果theItems.length==theSize?增加存储容量if(idx<0

4、

5、idx>theSize)thrownewLo

6、cateException(idx);if(theItems.length==theSize)ensureCapacity(size()*2+1);//增加存储容量add—移动a0a1xa2a3a4a5a0a1a2a3a4a56theSize7theSizea6a5a5a4a4a3a3a2ak=>ak+1k=(theSize-1)→idxadd—移动for(inti=theSize-1;i>=idx;i--)theItems[i+1]=theItems[i];theItems[idx]=x;add(4,66)th

7、eSize-108756426621183075425687addpublicvoidadd(intidx,AnyTypex)throwsLocateException{//在顺序表的第idx个位置之前插入新的数据元素xif(idx<0

8、

9、idx>theSize-1)thrownewLocateException(idx);if(theItems.length==size())ensureCapacity(size()*2+1);//增加存储容量for(inti=theSize-1;i>=idx;i--)theItems

10、[i+1]=theItems[i];theItems[idx]=x;theSize++;}add1、在什么情况下，移动次数最小，最小移动次数是多少？2、在什么情况下，移动次数最多，最多移动次数是多少？3、在插入0~theSize-1每个位置的概率相同的情况下，移动次数的期望值是多少？原型：publicAnyTyperemove(intidx)作用：删除表中的第idx个位置上的数据元素removeremove逻辑结构的变化→(a1,…,ai-1,ai,ai+1…,a

11、n)→(a1,…,ai-1,ai+1,…,an)存储结构的变化a0a1a3a4a5a0a1a2a3a4a5remove(2)6theSize5theSizeremove过程：1、判断i的合法性2、取值3、移动4、theSize--removea2a3a3a4a4a5ak-1<=akk=i+1→theSize-1a0a1a3a4a5a0a1a2a3a4a56theSize5theSizeremove—移动removepublicAnyTyperemove(intidx)throwLocateException{//删

12、除表中的第idx个位置上的数据元素if(idx<0

13、

14、idx>theSize)thrownewLocateException(idx);AnyTyperemovedItem=theItems[idx];for(inti=idx+1;i