《数据结构与算法分析》课程教学资源（PPT讲稿）Lists, Stacks and Queues

Lists. Stacks and Queues

Lists, Stacks and Queues

More com plete listADT List(i / const List(const List& list)i copy constructor List( destructor ist& operator=(const List& list)i // assignment operator // plus other overloaded operators void add (double x)i double head(consti // get the head element bool search(double x search for a given x void insert(double x) / insert x in a sorted list void delete(double x / delete x in a sorted list void addEnd (double x)i add to the end d deleteD(; delete the end and get the end element double end( / get the element at the end void display ()consti //output it length()consti / count the number of elements

2 struct Node{ double data; Node* next; }; class List { public: List(); // constructor List(const List& list); // copy constructor ~List(); // destructor List& operator=(const List& list); // assignment operator // plus other overloaded operators bool empty() const; // boolean function void add(double x); // add to the head void delete(); // delete the head and get the head element double head() const; // get the head element bool search(double x); // search for a given x void insert(double x); // insert x in a sorted list void delete(double x); // delete x in a sorted list void addEnd(double x); // add to the end void deleteEnd(); // delete the end and get the end element double end(); // get the element at the end void display() const; // output int length() const; // count the number of elements private: Node* head; }; More complete list ADT

list ADT (a general list) class list ublic t() List(const List& list) copy constructor LIston // destructor bool empty() consti double head( const // get the head element void add(double x)i // add to the head void delete(i // delete the head element void display() consti // output private: Or to define one function Double delete 0; Which deletes and returns the head element

3 class List { public: List(); // constructor List(const List& list); // copy constructor ~List(); // destructor bool empty() const; // boolean function double head() const; // get the head element void add(double x); // add to the head void delete(); // delete the head element void display() const; // output private: … }; list ADT (a general list) Or to define one function: Double delete(); Which deletes and returns the head element

list ADT (a sorted list lass list public Liston // constructor List(const List& list)i // copy constructor sto // destructor bool empty ()consti // boolean function double headon consti // get the first element void insert(double x) // insert x in a sorted list void delete (double x sorted list void display()col //output bool search(double x) // search for a given x

4 class List { public: List(); // constructor List(const List& list); // copy constructor ~List(); // destructor bool empty() const; // boolean function double head(); const; // get the first element void insert(double x); // insert x in a sorted list void delete(double x); // delete x in a sorted list void display() const; // output bool search(double x); // search for a given x private: … }; list ADT (a sorted list)

Implementation and efficiency Implementation Static array DynamIc array Linked lists e with and without dummy head tricks Efficiency Insertion> construction, composition Deletion> destruction, decomposition Search application, usage

5 Implementation Static array Dynamic array Linked lists  with and without ‘dummy head’ tricks Efficiency Insertion → construction, composition Deletion → destruction, decomposition Search → application, usage Implementation and Efficiency

Efficiency: Algorithm Analysis Roughly 'counting the number of operations, assuming all basis operations are of the same unit one

6 Roughly ‘counting’ the number of operations, assuming all basis operations are of the same, unit one. Efficiency: Algorithm Analysis

A Few Simple rules Loops at most the running time of the statements inside the for-loop (including tests ) times the number of iterations O(N) Nested loops for(i=0; i<n; i ++ for (=0; j<n;j ++) k++; the running time of the statement multiplied by the product of the sizes of all the for-loops O(N2)

7 A Few Simple Rules Loops at most the running time of the statements inside the for-loop (including tests) times the number of iterations. O(N) Nested loops the running time of the statement multiplied by the product of the sizes of all the for-loops. O(N2 )

Consecutive statements for(=0;i<n;+) These just add a[i=0; O(N)+O(N2)=O(N2) for (i=0:; k<n:; ++ for (=0; j<n j ++ a+=a]++ Conditional: If s1 else s2 never more than the running time of the test plus the larger of the running times of S1 and S2 O(1)

8 Consecutive statements These just add O(N) + O(N2 ) = O(N2 ) Conditional: If S1 else S2 never more than the running time of the test plus the larger of the running times of S1 and S2. O(1)

Our first example: search of an ordered array Linear search and binary search Upper bound, lower bound and tight bound

9 Our first example: search of an ordered array Linear search and binary search Upper bound, lower bound and tight bound

10 Linear search: // Given an array of 'size, in increasing order, find int linearsearch(int* a[l, int size int x)i int low=0, high=size-li for (int i=0; i<size; i++) O(N) if (a[i]==x return i t

10 O(N) // Given an array of ‘size’ in increasing order, find ‘x’ int linearsearch(int* a[], int size,int x) { int low=0, high=size-1; for (int i=0; i<size;i++) if (a[i]==x) return i; return -1; } Linear search: