数据结构与算法分析_C++语言描述(第2版)Larry_Nyhoff__.ppt

《数据结构与算法分析_C++语言描述(第2版)Larry_Nyhoff__.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析_C++语言描述(第2版)Larry_Nyhoff__.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Main IndexContents1Main IndexContentsCLASS list ConstructorsCLASS list ConstructorsCLASS list OperationsCLASS list OperationsApplication:A List PalindromeApplication:A List Palindrome iteratoriterator Operations Operations Constant Constant IteratorsIterators Declaring and Using Declaring and Using

2、IteratorsIteratorsInserting an element into a listInserting an element into a listRemoving an element from a listRemoving an element from a listThe Function The Function writeListwriteList()()The Function find_last_of()The Function find_last_of()The Sequential Search of a ListThe Sequential Search o

3、f a ListSplicing two listsSplicing two listsOrdered listsOrdered listsRemoving DuplicatesRemoving Duplicates Summary SlidesSummary Slides Chapter 11 The List Container and The List Container and IteratorsIterators1Main IndexContentsShifting blocks of elements to Shifting blocks of elements to insert

4、 or delete a vector iteminsert or delete a vector item2Main IndexContents3Main IndexContentsModel of a list object with links Model of a list object with links to next and previous elementto next and previous element3Main IndexContentsSample listSample list4Main IndexContents5Main IndexContentsThe L

5、ist APIThe List APIlThe list API documents the member function prototype as well as pre-and postconditions.provides three constructors to declare a list object.5Main IndexContents6Main IndexContentsCLASS listConstructorslist();Create an empty list.This is the default constructor.list(int n,const T&v

6、alue=T();Create a list with n elements,each having a specified value.If the value argument is omitted,the elements are filled with the default value for type T.Type T must have a default constructor,and the default value of type T is specified by the notation T().list(T*first,T*last);Initialize the

7、list,using the address range first,last).6Main IndexContents7Main IndexContentsCLASS listOperationsT&back();Return the value of the item at the rear of the list.Precondition:The list must contain at least one element.bool empty()const;Return true if the list is empty,false otherwise.T&front();Return

8、 the value of the item at the front of the list.Precondition:The list must contain at least one element.7Main IndexContents8Main IndexContentsCLASS listOperationsvoid push_back(const T&value);Add a value at the rear of the list.Postcondition:The list has a new element at the rear,and its size increa

9、ses by 1.void pop_back();Remove the item at the rear of the list.Precondition:The list is not empty.Postcondition:The list has a new element at the rear or is empty.8Main IndexContents9Main IndexContentsCLASS listOperationsvoid push_front(const T&value);Add a value at the front of the list.Postcondi

10、tion:The list has a new element at the front,and its size increases by 1.void pop_front();Remove the item at the front of the list.Precondition:The list is not empty.Postcondition:The list has a new element at the front or is empty.int size()const;Return the number of elements in the list.9Main Inde

11、xContentsApplication:A List Palindrome(P247)Application:A List Palindrome(P247)#include#include#include#include/for isalpha()and tolower()using namespace std;/check whether the values in alist read the same forward/and backwards.if so,return true;otherwise return falsetemplate bool isPalindrome(cons

12、t list&alist);10Main IndexContentsint main()string str;list charList;/empty list of charactersint i;char ch;/prompt the user to enter a string that may include blankscout Enter the string:;getline(cin,str,n);/copy all of the non-blank letters as lowercase characters/to the list charListfor(i=0;i str

13、.length();i+)ch=stri;if(isalpha(ch)charList.push_back(tolower(ch);11Main IndexContents/call isPalindrome()and use the return value to designate/whether the string is or is not a palindromeif(isPalindrome(charList)cout str is a palindrome endl;elsecout str is not a palindrome endl;return 0;12Main Ind

14、exContentsFunction Function isPalindromeisPalindrometemplate bool isPalindrome(const list&alist)list copyList;copyList=alist;while(copyList.size()1)if(copyList.front()!=copyList.back()return false;copyList.pop_front();copyList.pop_back();return true;13Main IndexContents/*Run 1:Enter the string:A man

15、,a plan,a canal,PanamaA man,a plan,a canal,Panama is a palindromeRun 2:Enter the string:Go hang a salami,Im a lasagna hogGo hang a salami,Im a lasagna hog is a palindromeRun 3:Enter the string:palindromepalindrome is not a palindrome*/14Main IndexContents15Main IndexContentsCLASS list:iteratorOperat

16、ions*:(反引用运算符）Accesses the value of the item currently pointed to by the iterator.*iteriter;+:Moves the iterator to the next item in the list.iteriter+;+;-:Moves the iterator to the previous item in the list.iteriter-;-;=:Takes two iterators as operands and returns truewhen they both point at the sa

17、me item in the list.iter1=iter2iter1=iter2!=:Returns true when the two iterators do not point at the same item in the list.iter1!=iter2iter1!=iter215Main IndexContentsDeclaring and Using Declaring and Using IteratorsIterators The list class includes iterator as a nested class within its declaration.

18、The declaration of an iterator object must include the class name“iterator”along with the scope operator expression“list:”list:iterator iter;16Main IndexContents17Main IndexContentsCLASS listOperationsiterator begin();Returns an iterator that references the first position(front)of the list.If the li

19、st is empty,the iterator value end()is returned.const_iterator begin();Returns a const_iterator that points to the first position(front)of a constant list.If the list is empty,the const_iterator value end()is returned.17Main IndexContents18Main IndexContentsCLASS listOperationsiterator end();Returns

20、 an iterator that signifies a location immediately out of the range of actual elements.A program must not dereference the value of end()with the*operator.const_iterator end();Returns a const_iterator that signifies a location immediately out of the range of actual elements in a constant list.A progr

21、am must not dereference the value of end()with the*operator.18Main IndexContents list:iterator listIter;list intList;listIter=intList.begin();listIter=intList.end();begin()end()ExampleExampleList iterators move through the list in a ciircular fashion.19Main IndexContentsvoid main()int arr=1,3,3,4,5;

22、int arrSize=sizeof(arr)/sizeof(int);list intList(arr,arr+arrSize);list:iterator iter;iter=find_last_of(intList,3);if(iter!=intList.end()cout *iter “;iter+;cout *iter endl;Searching For The last occurrence of 3 and 7 20Main IndexContents iter=find_last_of(intList,7);if(iter!=intList.end()cout “7 is i

23、n the list”endl;else cout “7 is not in the list”endl;Output:3 47 is not in the list Searching For The last occurrence of 3 and 7 21Main IndexContents#include#include using namespace std;template list:iterator find_last_of (list&alist,const T&value)list:iterator iter=alist.end();do iter-;while(iter!=

24、alist.end()&!(*iter=value);return iter;The Function find_last_of()22Main IndexContentsConstant Constant IteratorsIterators C+uses the const attribute to specify that an object cannot be modified.list:const_iterator iter;Constant iterator is much like a nonconstant iterator,except it cannot be applie

25、d the deference operator,*,on the left side of an assignment statement:*iter=5;/false statement 23Main IndexContentstemplate void writeList(const list&alist,const string&separator)list:const_iterator iter;for(iter=alist.begin();iter!=alist.end();iter+)cout *iter separator;cout endl;The Function writ

26、eList()24Main IndexContents The Sequential Search of a ListThe Sequential Search of a ListVector version:template int seqSearch(const vector&v,int first,int last,const T&target)int i;for(i=first;i last;i+)if(vi=target)return i;return last;25Main IndexContentsList version:template list:iterator seqSe

27、arch(list:iterator first,list:iterator last,const T&target)list:iterator iter=first;while(iter!=last&!(*iter=target)iter+;return iter;The Sequential Search of a List26Main IndexContents Word Frequencies Word Frequencies（P255P255）class wordFreqpublic:wordFreq(const string&str):word(str),freq(1)void i

28、ncrement()freq+;friend bool operator=(const wordFreq&lhs,const wordFreq&rhs)return lhs.word=rhs.word;friend bool operator(const wordFreq&lhs,const wordFreq&rhs)return lhs.word rhs.word;friend ostream&operator(ostream&ostr,const wordFreq&w)ostr w.word (w.freq );return ostr;private:string word;int fre

29、q;27Main IndexContents28Main IndexContentsInserting an element into a list28Main IndexContents29Main IndexContentsCLASS listOperationsiterator insert(iterator pos,const T&value);Insert value before pos,and return an iterator pointing to the position of the new value in the list.The operation does no

30、t affect any existing iterators.Postcondition:The list has a new element.29Main IndexContents30Main IndexContentsCLASS listOperationsvoid erase(iterator pos);Erase the element pointed to by pos.Precondition:The list is not empty.Postcondition:The list has one fewer element.void erase(iterator first,

31、iterator last);Erase all list elements within the range first,last）.Precondition:The list is not empty.Postcondition:The size of the list decreases by the number of elements in the range.30Main IndexContentsRemoving an element from a listerase(iter+);iter=inList.begin();iter+;intList.erase(iter);31M

32、ain IndexContents32Main IndexContentsOrdered listsOrdered listsPosition the iterator curr at the front of the list.Insert 50 in the list:32Main IndexContentsThe function The function insertOrderinsertOrder()()template void insertOrder(list&orderedList,const T&item)/curr starts at first list element,

33、stop marks end list:iterator curr=orderedList.begin(),stop=orderedList.end();/find the insertion point,which may be at end of list while(curr!=stop)&(*curr item)curr+;/do the insertion using insert()orderedList.insert(curr,item);33Main IndexContentsThe Function The Function RemovingDuplicatesRemovin

34、gDuplicatestemplate void removeDuplicates(list&aList)list:iterator curr,p;curr=aList.begin();while(curr!=aList.end()currValue=*curr;p=curr;p+;while(p!=aList.end()if(*p=currValue)alist.erase(p+);else p+;curr+;34Main IndexContentsOrdered list without duplicatesOrdered list without duplicates#include#i

35、nclude#include d_listl.h/for insertOrder()and removeDuplicates()#include d_util.h/for writeList()using namespace std;int main()/declare an unordered array with duplicate valuesint arr=7,2,2,9,3,5,3,9,7,2,i;int arrSize=sizeof(arr)/sizeof(int);list intList;35Main IndexContentsOrdered list without dupl

36、icatesOrdered list without duplicates/build the ordered list using elements from the array for(i=0;i arrSize;i+)insertOrder(intList,arri);/output the ordered list with duplicatescout Ordered list with duplicates:;writeList(intList);/remove duplicate valuesremoveDuplicates(intList);/output the ordere

37、d list that has no duplicatescout Ordered list without duplicates:;writeList(intList);return 0;36Main IndexContents/*Run:Ordered list with duplicates:2 2 2 3 3 5 7 7 9 9Ordered list without duplicates:2 3 5 7 9*/37Main IndexContents38Main IndexContentsSplicing two listsSplicing two lists38Main Index

38、ContentsThe function splice()The function splice()template void splice(list&dest,list:iterator pos,const list&source)list:const_iterator sourceIter;sourceIter=source.begin();/insert each element of source before the/position poswhile(sourceIter!=source.end()dest.insert(pos,*sourceIter);sourceIter+;3

39、9Main IndexContents40Main IndexContentsSummary Slide 1Summary Slide 1-list-A Sequence of elements stored by position.-Index access is not available-to access the value of an element,must pass through its preceding elements.-list iterator-A generalized pointer that moves through a list element by ele

40、ment forward or backward-At any point,the*operator accesses the value of a list item.40Main IndexContents41Main IndexContentsSummary Slide 2Summary Slide 2-The list class has two iterator types:1)1)iteratoriterator:A generalized list traversal pointer.2)2)constconst _ _ iteratoriterator:must be used

41、 with a constant list object.Each type is a nested class of list and must be accessed by using the scope operator:41Main IndexContents42Main IndexContentsSummary Slide 3Summary Slide 3-the list member function begin()-Gives an iterator an initial value that points to the first element.-the list memb

42、er function end()-Returns an iterator pointing just past the last element of the list.42Main IndexContents43Main IndexContentsSummary Slide 4Summary Slide 4-The sequential search of a list object-implemented by using an iterator range firstfirst,lastlast).-It returns an iterator that points at the t

43、arget value or has value lastlast if the target is not in the list.43Main IndexContents44Main IndexContentsSummary Slide 5Summary Slide 5-list class member insert()and erase()-Both use an iterator argument to modify a list.1)insert()insert():places value in the list before the data referenced by the

44、 iterator pospos.2)erase()erase():removes the data item referenced by pospos from the list.44Main IndexContents表容器上机表容器上机时间时间 本周四本周四地点地点 健健A303-305室室题目题目 P567(4)45Main IndexContents一元多项式类一元多项式类template class Polynomialpublic:void read(istream&in);void display(ostream&out)const;Polynomial opertor+(Polynomial addend2);Polynomial istream&opertor (istream&in,Polynomial&number);Polynomial ostream&opertor (ostream&out,const Polynomial&number);private:class Termpublic:T coef;int expo;list myList;46