Chap 4. Links, Stacks and Queue 1
Lists A list is a finite, ordered sequence of data items. Important concept: List elements have a position. Notation: <a 0, a 1,, a n-1 > What operations should we implement? 2
List Implementation Concepts Our list implementation will support the concept of a current position. We will do this by defining the list in terms of left and right partitions. Either or both partitions may be empty. Partitions are separated by the fence. <20, 23 12, 15> 3
List ADT template <class Elem> class List { public: virtual void clear() = 0; virtual bool insert(const Elem&) = 0; virtual bool append(const Elem&) = 0; virtual bool remove(elem&) = 0; virtual void setstart() = 0; virtual void setend() = 0; virtual void prev() = 0; virtual void next() = 0; 4
List ADT (cont) virtual int leftlength() const = 0; virtual int rightlength() const = 0; virtual bool setpos(int pos) = 0; virtual bool getvalue(elem&) const = 0; virtual void print() const = 0; }; 5
List ADT Examples List: <12 32, 15> MyList.insert(99); Result: <12 99, 32, 15> Iterate through the whole list: for (MyList.setStart(); MyList.getValue(it); MyList.next()) DoSomething(it); 6
List Find Function // Return true iff K is in list bool find(list<int>& L, int K) { int it; for (L.setStart(); L.getValue(it); L.next()) if (K == it) return true; // Found it return false; // Not found } 7
Array-Based List Insert 8
Array-Based List Class (1) template <class Elem> // Array-based list class AList : public List<Elem> { private: int maxsize; // Maximum size of list int listsize; // Actual elem count int fence; // Position of fence Elem* listarray; // Array holding list public: AList(int size=defaultlistsize) { maxsize = size; listsize = fence = 0; listarray = new Elem[maxSize]; } 9
Array-Based List Class (2) ~AList() { delete [] listarray; } void clear() { delete [] listarray; listsize = fence = 0; listarray = new Elem[maxSize]; } void setstart() { fence = 0; } void setend() { fence = listsize; } void prev() { if (fence!= 0) fence--; } void next() { if (fence <= listsize) fence++; } int leftlength() const { return fence; } int rightlength() const { return listsize - fence; } 10
Array-Based List Class (3) bool setpos(int pos) { if ((pos >= 0) && (pos <= listsize)) fence = pos; return (pos >= 0) && (pos <= listsize); } bool getvalue(elem& it) const { if (rightlength() == 0) return false; else { it = listarray[fence]; return true; } } 11
Insert // Insert at front of right partition template <class Elem> bool AList<Elem>::insert(const Elem& item) { if (listsize == maxsize) return false; for(int i=listsize; i>fence; i--) // Shift Elems up to make room listarray[i] = listarray[i-1]; listarray[fence] = item; listsize++; // Increment list size return true; } 12
Append // Append Elem to end of the list template <class Elem> bool AList<Elem>::append(const Elem& item) { if (listsize == maxsize) return false; listarray[listsize++] = item; return true; } 13
Remove // Remove and return first Elem in right // partition template <class Elem> bool AList<Elem>::remove(Elem& it) { if (rightlength() == 0) return false; it = listarray[fence]; // Copy Elem for(int i=fence; i<listsize-1; i++) // Shift them down listarray[i] = listarray[i+1]; listsize--; // Decrement size return true; } 14
Link Class Dynamic allocation of new list elements. // Singly-linked list node template <class Elem> class Link { public: Elem element; // Value for this node Link *next; // Pointer to next node Link(const Elem& elemval, Link* nextval =NULL) { element = elemval; next = nextval; } Link(Link* nextval =NULL) { next = nextval; } }; 15
Linked List Position (1) 16
Linked List Position (2) 17
Linked List Class (1) / Linked list implementation template <class Elem> class LList: public List<Elem> { private: Link<Elem>* head; // Point to list header Link<Elem>* tail; // Pointer to last Elem Link<Elem>* fence;// Last element on left int leftcnt; // Size of left int rightcnt; // Size of right void init() { // Intialization routine fence = tail = head = new Link<Elem>; leftcnt = rightcnt = 0; } 18
Linked List Class (2) void removeall() { // Return link nodes to free store while(head!= NULL) { fence = head; head = head->next; delete fence; } } public: LList(int size=defaultlistsize) { init(); } ~LList() { removeall(); } // Destructor void clear() { removeall(); init(); } 19
Linked List Class (3) void setstart() { fence = head; rightcnt += leftcnt; leftcnt = 0; } void setend() { fence = tail; leftcnt += rightcnt; rightcnt = 0; } void next() { // Don't move fence if right empty if (fence!= tail) { fence = fence->next; rightcnt--; leftcnt++; } } int leftlength() const { return leftcnt; } int rightlength() const { return rightcnt; } bool getvalue(elem& it) const { if(rightlength() == 0) return false; it = fence->next->element; return true; } 20
Insertion 21
Insert/Append // Insert at front of right partition template <class Elem> bool LList<Elem>::insert(const Elem& item) { fence->next = new Link<Elem>(item, fence->next); if (tail == fence) tail = fence->next; rightcnt++; return true;} // Append Elem to end of the list template <class Elem> bool LList<Elem>::append(const Elem& item) { tail = tail->next = new Link<Elem>(item, NULL); rightcnt++; return true;} 22
Removal 23
Remove // Remove and return first Elem in right // partition template <class Elem> bool LList<Elem>::remove(Elem& it) { if (fence->next == NULL) return false; it = fence->next->element; // Remember val // Remember link node Link<Elem>* ltemp = fence->next; fence->next = ltemp->next; // Remove if (tail == ltemp) // Reset tail tail = fence; delete ltemp; // Reclaim space rightcnt--; return true; } 24
Prev // Move fence one step left; // no change if left is empty template <class Elem> void LList<Elem>::prev() { Link<Elem>* temp = head; if (fence == head) return; // No prev Elem while (temp->next!=fence) temp=temp->next; fence = temp; leftcnt--; rightcnt++; } 25
Setpos // Set the size of left partition to pos template <class Elem> bool LList<Elem>::setPos(int pos) { if ((pos < 0) (pos > rightcnt+leftcnt)) return false; fence = head; for(int i=0; i<pos; i++) fence = fence->next; return true; } 26
Comparison of Implementations Array-Based Lists: Insertion and deletion are (n). Prev and direct access are (1). Array must be allocated in advance. No overhead if all array positions are full. Linked Lists: Insertion and deletion are (1). Prev and direct access are (n). Space grows with number of elements. Every element requires overhead. 27
Space Comparison Break-even point: DE = n(p + E); n = DE P + E E: Space for data value. P: Space for pointer. D: Number of elements in array. 28
Freelists System new and delete are slow. // Singly-linked list node with freelist template <class Elem> class Link { private: static Link<Elem>* freelist; // Head public: Elem element; // Value for this node Link* next; // Point to next node Link(const Elem& elemval, Link* nextval =NULL) { element = elemval; next = nextval; } Link(Link* nextval =NULL) {next=nextval;} void* operator new(size_t); // Overload void operator delete(void*); // Overload }; 29
Freelists (2) template <class Elem> Link<Elem>* Link<Elem>::freelist = NULL; template <class Elem> // Overload for new void* Link<Elem>::operator new(size_t) { if (freelist == NULL) return ::new Link; Link<Elem>* temp = freelist; // Reuse freelist = freelist->next; return temp; // Return the link } template <class Elem> // Overload delete void Link<Elem>::operator delete(void* ptr){ ((Link<Elem>*)ptr)->next = freelist; freelist = (Link<Elem>*)ptr; } 30
Doubly Linked Lists Simplify insertion and deletion: Add a prev pointer. // Doubly-linked list link node template <class Elem> class Link { public: Elem element; // Value for this node Link *next; // Pointer to next node Link *prev; // Pointer to previous node Link(const Elem& e, Link* prevp =NULL, Link* nextp =NULL) { element=e; prev=prevp; next=nextp; } Link(Link* prevp =NULL, Link* nextp =NULL) { prev = prevp; next = nextp; } }; 31
Doubly Linked Lists 32
Doubly Linked Insert 33
Doubly Linked Insert // Insert at front of right partition template <class Elem> bool LList<Elem>::insert(const Elem& item) { fence->next = new Link<Elem>(item, fence, fence->next); if (fence->next->next!= NULL) fence->next->next->prev = fence->next; if (tail == fence) // Appending new Elem tail = fence->next; // so set tail rightcnt++; // Added to right return true; } 34
Doubly Linked Remove 35
Doubly Linked Remove // Remove, return first Elem in right part template <class Elem> bool LList<Elem>::remove(Elem& it) { if (fence->next == NULL) return false; it = fence->next->element; Link<Elem>* ltemp = fence->next; if (ltemp->next!= NULL) ltemp->next->prev = fence; else tail = fence; // Reset tail fence->next = ltemp->next; // Remove delete ltemp; // Reclaim space rightcnt--; // Removed from right return true; } 36
Dictionary Often want to insert records, delete records, search for records. Required concepts: Search key: Describe what we are looking for Key comparison Equality: sequential search Relative order: sorting Record comparison 37
Comparator Class How do we generalize comparison? Use ==, <=, >=: Disastrous Overload ==, <=, >=: Disastrous Define a function with a standard name Implied obligation Breaks down with multiple key fields/indices for same object Pass in a function Explicit obligation Function parameter Template parameter 38
Comparator Example class intintcompare { public: static bool lt(int x, int y) { return x < y; } static bool eq(int x, int y) { return x == y; } static bool gt(int x, int y) { return x > y; } }; 39
Comparator Example (2) class PayRoll { public: int ID; char* name; }; class IDCompare { public: static bool lt(payroll& x, Payroll& y) { return x.id < y.id; } }; class NameCompare { public: static bool lt(payroll& x, Payroll& y) { return strcmp(x.name, y.name) < 0; } }; 40
Dictionary ADT // The Dictionary abstract class. template <class Key, class Elem, class KEComp, class EEComp> class Dictionary { public: virtual void clear() = 0; virtual bool insert(const Elem&) = 0; virtual bool remove(const Key&, Elem&) = 0; virtual bool removeany(elem&) = 0; virtual bool find(const Key&, Elem&) const = 0; virtual int size() = 0; }; 41
Unsorted List Dictionary template <class Key, class Elem, class KEComp, class EEComp> class UALdict : public Dictionary<Key,Elem,KEComp,EEComp> { private: AList<Elem>* list; public: bool remove(const Key& K, Elem& e) { for(list->setstart(); list->getvalue(e); list->next()) if (KEComp::eq(K, e)) { list->remove(e); return true; } return false; } }; 42
Stacks LIFO: Last In, First Out. Restricted form of list: Insert and remove only at front of list. Notation: Insert: PUSH Remove: POP The accessible element is called TOP. 43
Stack ADT // Stack abtract class template <class Elem> class Stack { public: // Reinitialize the stack virtual void clear() = 0; // Push an element onto the top of the stack. virtual bool push(const Elem&) = 0; // Remove the element at the top of the stack. virtual bool pop(elem&) = 0; // Get a copy of the top element in the stack virtual bool topvalue(elem&) const = 0; // Return the number of elements in the stack. virtual int length() const = 0; }; 44
Array-Based Stack // Array-based stack implementation private: int size; // Maximum size of stack int top; // Index for top element Elem *listarray; // Array holding elements Issues: Which end is the top? Where does top point to? What is the cost of the operations? 45
Linked Stack // Linked stack implementation private: Link<Elem>* top; // Pointer to first elem int size; // Count number of elems What is the cost of the operations? How do space requirements compare to the array-based stack implementation? 46
examples of stack 47
栈的应用举例 1: 数制转换十进制数 N 和其他 d 进制数的转换是计算 机实现计算的基本问题, 其解决方法很多, 其中一个简单算法基于下列原理 : 迭代 N = (N div d) d + N mod d ( 其中 :div 为整除运算,mod 为求余运算 ) 例如 :(1348)10 = (2504)8, 其运算过程如下 : N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 48
49
伪代码表示 : void conversion () { InitStack( ); // 构造空栈 cin >> N; // 输入一个十进制数 while(n) { Push(N % 8); // " 余数 " 入栈 N = N / 8; // 非零 " 商 " 继续运算 } // while while (!StackEmpty) { // 和 " 求余 " 所得相逆的顺序输出八进制的各位数 Pop(e); cout << e; } // while } // conversion 50
栈的应用举例 2: 括号匹配的检验 处理的括号包括 :{ } [ ] ( ) 正确的格式 : { [ ] ( ) } 或 [ ( { } [ ] ) ] 不正确的格式 : [ ( ] ) 或 { [ ( ] } ) 或 ( ( ) ] ) 则检验括号是否匹配的方法可用 期待的急迫程度 这个概念来描述 51
例如 : 考虑下列括号序列 : [ ( [ ] { } ) ] 1 2 3 4 5 6 7 8 分析可能出现的不匹配的情况 : 到来的右括号并非是所 期待 的 ; 到来的是 不速之客 ; 直到结束, 也没有到来所 期待 的右括号 52
算法的设计思想 : 1) 凡出现左括号, 则进栈 ; 2) 凡出现右括号, 首先检查栈是否空若栈空, 则表明该 右括号 多余, 否则和栈顶元素比较, 若相匹配, 则 左括号出栈, 否则表明不匹配 3) 表达式检验结束时, 若栈空, 则表明表达式中匹配正确, 否则表明 左括号 有余 53
代码演示 s3_2/alg.h VC 调试方法 54
栈的应用举例 3: 迷宫求解算法 迷宫求解问题 : 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题 由于计算机解迷宫时, 通常用的是 穷举求解 的方法, 即从入口出发, 顺某一方向向前探索, 若能走通, 则继续往前走 ; 否则沿原路退回, 换一个方向再继续探索, 直至所有可能的通路都探索到为止 为了保证在任何位置上都能沿原路退回, 显然需要用一个后进先出的结构来保存从入口到当前位置的路径 因此, 在求迷宫通路的算法中应用 栈 也就是自然而然 55 的事了
迷宫的表示 56
解迷宫 57
Queues FIFO: First in, First Out Restricted form of list: Insert at one end, remove from the other. Notation: Insert: Enqueue Delete: Dequeue First element: Front Last element: Rear 58
Queue Implementation (1) 59
Queue Implementation (2) 60
循环队列 (Circular Queue) 存放队列的数组被当作首尾相接的表 队头 队尾指针加 1 时从 maxsize -1 直接进 到 0,, 可用取模 ( 余数 ) 运算实现 队头指针加 1: front=(front+1) % maxsize 队尾指针加 1: rear = (rear+1) % maxsize 队列初始化 :front: = rear = 0 61
5 4 6 7 front rear 3 2 空队列 0 1 5 4 6 7 3 2 A 进队 A front 0 1 rear 5 4 rear 6 7 队空条件 :rear = = front C 3 B 2 A 0 1 B, C 进队 front 6 7 6 7 6 7 5 0 5 0 5 0 4 rear C 3 B 2 A 退队 A 1 front 4 rear C 3 B 2 B 退队 1 front 4 rear front C 3 2 C 退队 1 62
5 4 6 7 front rear 3 2 空队列 0 1 5 4 6 7 3 2 A 进队 A front 0 1 rear 5 4 rear 6 7 队满条件 :rear = = front C 3 B 2 A 0 1 B, C 进队 front 6 7 5 0 4 rear C 3 B 2 A 退队 A 1 front 5 4 rear 6 7 C 3 B 2 B 退队 0 1 front 5 4 6 7 E F G H D I C J 3 2 0 1 rear front D,E,F,G,H,I,J 进队 63
解决 : 设置计数器 count,, 记录队列中的元素个数 设置标志表明当前队列的空满情况 在数组中始终留空一个单元不用 即 front 所指的单元始终不用 队列初始化 :front: = rear = 0 队空条件 :front: = = rear 队满条件 :(rear+1)%maxsize: = = front( ( 当队尾再加 1 追上队头时, 队列满 ) 64
5 4 5 4 6 7 front rear 3 2 空队列 6 7 0 1 E F G H D I C 3 2 0 5 4 rear front D,E,F,G,H,I 进队 6 7 C B rear 3 2 front rear B 退队 0 1 5 4 front 6 7 队空 C 3 2 C 退队 队空条件 :rear = = front 队满队满条件 : 1 (rear+1)%maxsize= =front 65 0 1