Microsoft PowerPoint - Lecture3.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - Lecture3.ppt"

住卓
6 years ago
Views:

1 Chap 4. Links, Stacks and Queue 1

2 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

3 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

4 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

5 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

6 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

7 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

8 Array-Based List Insert 8

9 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

10 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

11 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

12 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

13 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

14 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

15 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

16 Linked List Position (1) 16

17 Linked List Position (2) 17

18 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

19 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

20 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

21 Insertion 21

22 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

23 Removal 23

24 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

25 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

26 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

27 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

28 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

29 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

30 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

31 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

32 Doubly Linked Lists 32

33 Doubly Linked Insert 33

34 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

35 Doubly Linked Remove 35

36 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

37 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

38 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

39 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

40 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

41 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

42 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

43 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

44 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

45 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

46 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

47 examples of stack 47

48 栈的应用举例 1: 数制转换十进制数 N 和其他 d 进制数的转换是计算机实现计算的基本问题, 其解决方法很多, 其中一个简单算法基于下列原理 : 迭代 N = (N div d) d + N mod d ( 其中 :div 为整除运算,mod 为求余运算 ) 例如 :(1348)10 = (2504)8, 其运算过程如下 : N N div 8 N mod

49 49

50 伪代码表示 : void conversion () { InitStack( ); // 构造空栈 cin >> N; // 输入一个十进制数 while(n) { Push(N % 8); // " 余数 " 入栈 N = N / 8; // 非零 " 商 " 继续运算 } // while while (!StackEmpty) { // 和 " 求余 " 所得相逆的顺序输出八进制的各位数 Pop(e); cout << e; } // while } // conversion 50

51 栈的应用举例 2: 括号匹配的检验处理的括号包括 :{ } [ ] ( ) 正确的格式 : { [ ] ( ) } 或 [ ( { } [ ] ) ] 不正确的格式 : [ ( ] ) 或 { [ ( ] } ) 或 ( ( ) ] ) 则检验括号是否匹配的方法可用期待的急迫程度这个概念来描述 51

52 例如 : 考虑下列括号序列 : [ ( [ ] { } ) ] 分析可能出现的不匹配的情况 : 到来的右括号并非是所期待的 ; 到来的是不速之客 ; 直到结束, 也没有到来所期待的右括号 52

53 算法的设计思想 : 1) 凡出现左括号, 则进栈 ; 2) 凡出现右括号, 首先检查栈是否空若栈空, 则表明该右括号多余, 否则和栈顶元素比较, 若相匹配, 则左括号出栈, 否则表明不匹配 3) 表达式检验结束时, 若栈空, 则表明表达式中匹配正确, 否则表明左括号有余 53

54 代码演示 s3_2/alg.h VC 调试方法 54

55 栈的应用举例 3: 迷宫求解算法迷宫求解问题 : 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题由于计算机解迷宫时, 通常用的是穷举求解的方法, 即从入口出发, 顺某一方向向前探索, 若能走通, 则继续往前走 ; 否则沿原路退回, 换一个方向再继续探索, 直至所有可能的通路都探索到为止为了保证在任何位置上都能沿原路退回, 显然需要用一个后进先出的结构来保存从入口到当前位置的路径因此, 在求迷宫通路的算法中应用栈也就是自然而然 55 的事了

56 迷宫的表示 56

57 解迷宫 57

58 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

59 Queue Implementation (1) 59

60 Queue Implementation (2) 60

61 循环队列 (Circular Queue) 存放队列的数组被当作首尾相接的表队头队尾指针加 1 时从 maxsize -1 直接进到 0,, 可用取模 ( 余数 ) 运算实现队头指针加 1: front=(front+1) % maxsize 队尾指针加 1: rear = (rear+1) % maxsize 队列初始化 :front: = rear = 0 61

62 front rear 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 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

63 front rear 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 rear C 3 B 2 A 退队 A 1 front 5 4 rear 6 7 C 3 B 2 B 退队 0 1 front E F G H D I C J rear front D,E,F,G,H,I,J 进队 63

64 解决 : 设置计数器 count,, 记录队列中的元素个数设置标志表明当前队列的空满情况在数组中始终留空一个单元不用即 front 所指的单元始终不用队列初始化 :front: = rear = 0 队空条件 :front: = = rear 队满条件 :(rear+1)%maxsize: = = front( ( 当队尾再加 1 追上队头时, 队列满 ) 64

65 front rear 3 2 空队列 E F G H D I C rear front D,E,F,G,H,I 进队 6 7 C B rear 3 2 front rear B 退队 front 6 7 队空 C 3 2 C 退队队空条件 :rear = = front 队满队满条件 : 1 (rear+1)%maxsize= =front

数据结构 Data Structure

数据结构 Data Structure 数据结构 : 线性表 Data Structure 2016 年 3 月 15 日星期二 1 线性表栈和队列线性表字典 ADT 栈队列 2016 年 3 月 15 日星期二 2 线性表定义 : 线性表 L 是 n 个数据元素 a 0,a 1, a n-1 的有限序列, 记作 L=(a 0,a 1, a n-1 ) 其中元素个数 n(n 0) 定义为表 L 的长度当 n=0 时,L 为空表,