数据结构与算法分析 C语言描述（第2版）Larry Nyhoff 列表的实现 课件.ppt

《数据结构与算法分析 C语言描述（第2版）Larry Nyhoff 列表的实现 课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1MainIndexContentsList(列表)概念1.列表中所有的元素都是同一种类型；2.列表具有有限的大小；3.所有元素都是线性排列的：－存在一个首元素和一个末尾元素；－除了末尾元素，每个元素都有一个后继元素；除了首元素，每个元素都有一个前驱。12MainIndexContentsList(列表)ADT数据元素集合：数据元素的一个有限序列，所有元素都是同一类型的。基本操作：－构造函数：创建空列表；－判空：检查列表是否为空；－插入：在列表中增加一项；－删除：在列表中删除一项；－遍历：按顺序访问列表，处理元素。在STL中也称为迭代操作。2AbstractModelofaListOb

2、ject迭代器通过++和--运算符，既可以向后遍历，也可以向前遍历34MainIndexContentsList--Basedonarray基于静态数组的列表List—Basedonvector基于向量的列表List—Basedonlinkedlist基于链表的列表45MainIndexContentsconstintCapacity=1024;templateclassarrayList{public:arrayList();boolempty()const;intsize()const;voidinsert(Titem,intpos);voiderase(i

3、ntpos);friendostream&operator<<(ostream&out,constarrayList&aList);private:intmySize;TmyArray[Capacity];};基于静态数组的列表（P231）56MainIndexContents基于静态数组的列表arrayList::arrayList():mySize(0){}boolarrayList::empty()const{returnmySize==0;}intarrayList::size()const{returnmySize;}67MainIndexContents基于静态数组的列表o

4、stream&operator<<(ostream&out,constList&aList){for(inti=0;i

5、rnout;}78MainIndexContents基于静态数组的列表voidList::insert(Titem,intpos){if(mySize==Capacity){cerr<<"***Nospaceforlistelement--terminating""execution***";exit(1);}if(pos<0

6、

7、pos>mySize){cerr<<"***Illegallocationtoinsert--"<pos;i--)myArray[i]=myArr

8、ay[i-1];myArray[pos]=item;mySize++;}89MainIndexContents基于静态数组的列表voidarrayList::erase(intpos){if(mySize==0){cerr<<"***Listisempty***";return;}if(pos<0

9、

10、pos>=mySize){cerr<<"Illegallocationtodelete--"<

11、}9classminiVector{public:miniVector(intsize=0);miniVector(constminiVector&obj);~miniVector();miniVector&operator=(constminiVector&rhs);int&back();constint&back()const;int&operator[](inti);constint&operator[](inti)const;基于动态数