《数据结构教学课件：Chapter4 Lists, Stacks, and Queues》由会员分享，可在线阅读，更多相关《数据结构教学课件：Chapter4 Lists, Stacks, and Queues（63页珍藏版）》请在金锄头文库上搜索。
1、1Data Data Structures and Structures and AlgorithmsAlgorithmsChapter4 ListsChapter4 Lists, Stacks, and Queues, Stacks, and Queues4.1 Lists4.2 The Dictionary ADT4.3 Stacks4.4 Queues2A list is a finite, ordered sequence of data items called elements.Each list element has a data type.The empty list con
2、tains no elements.The length of the list is the number of elements currently stored.The beginning of the list is called the head, the end of the list is called the tail.3ListsListsSorted lists have their elements positioned in ascending order of value, while unsorted lists have no necessary relation
3、ship between element values and positions.Notation: ( a0, a1, ,an-1 )What operations should we implement?4ListsListsAdd/delete element anywhere, find, next, previous, test for emptytemplate class List public: virtual void clear() = 0; virtual bool insert(const Elem&) = 0; virtual bool append(const E
4、lem&) = 0; virtual bool remove(Elem&) = 0; virtual void setStart() = 0; virtual void setEnd() = 0; virtual void prev() = 0; virtual void next() = 0;5List ADTList ADT virtual int leftLength() const = 0; virtual int rightLength() const = 0; virtual bool setPos(int pos) = 0; virtual bool getValue(Elem&
5、) const = 0; virtual void print() const = 0;6List ADTList ADTList: MyList.insert(99);Result: Iterate(反复) through the whole list:for (MyList.setStart(); MyList.getValue(it); MyList.next() DoSomething(it);7List ADT ExamplesList ADT Examples/ Return true iff K is in listbool find(List& L, int K) int it
6、; for (L.setStart(); L.getValue(it); L.next() if (K = it) return true; / Found it return false; / Not found8List Find FunctionList Find Function9Array-Based List InsertArray-Based List Inserttemplate / Array-based listclass AList : public List private: int maxSize; / Maximum size of list int listSiz
7、e; / Actual elem count int fence; / Position of fence Elem* listArray; / Array holding listpublic: AList(int size=DefaultListSize) maxSize = size; listSize = fence = 0; listArray = new ElemmaxSize; 10Array-Based List Class (1)Array-Based List Class (1)AList() delete listArray; void clear() delete li
8、stArray; listSize = fence = 0; listArray = new ElemmaxSize;void setStart() fence = 0; void setEnd() fence = listSize; void prev() if (fence != 0) fence-; void next() if (fence = 0) & (pos = 0) & (pos = listSize);bool getValue(Elem& it) const if (rightLength() = 0) return false; else it = listArrayfe
9、nce; return true; 12Array-Based List Class (3)Array-Based List Class (3)/ Insert at front of right partitiontemplate bool AList:insert(const Elem& item) if (listSize = maxSize) return false; for(int i=listSize; ifence; i-) / Shift Elems up to make room listArrayi = listArrayi-1; listArrayfence = ite
10、m; listSize+; / Increment list size return true;13InsertInsert/ Append Elem to end of the listtemplate bool AList:append(const Elem& item) if (listSize = maxSize) return false; listArraylistSize+ = item; return true;14AppendAppend/ Remove and return first Elem in right/ partitiontemplate bool AList:
11、remove(Elem& it) if (rightLength() = 0) return false; it = listArrayfence; / Copy Elem for(int i=fence; ilistSize-1; i+) / Shift them down listArrayi = listArrayi+1; listSize-; / Decrement size return true;15RemoveRemoveDynamic allocation of new list elements./ Singly-linked list nodetemplate class
12、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;16Link ClassLink Class17Linked List Position (1)Linked List Position (1)18Linked List Position
13、 (2)Linked List Position (2)/ Linked list implementationtemplate class LList:public List private: Link* head; /Point to list header Link* tail; /Pointer to last Elem Link* fence;/Last element on left int leftcnt; /Size of left int rightcnt; /Size of right void init() /Initialization routine fence =
14、tail = head = new Link; leftcnt = rightcnt = 0; 19Linked List Class (1)Linked List Class (1)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
15、() removeall(); init(); 20Linked List Class (2)Linked List Class (2)void setStart() fence = head; rightcnt += leftcnt; leftcnt = 0; void setEnd() fence = tail; leftcnt += rightcnt; rightcnt = 0; void next() / Dont move fence if right empty if (fence != tail) fence = fence-next; rightcnt-; leftcnt+;
16、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; 21Linked List Class (3)Linked List Class (3)22Linked List InsertionLinked List Insertion/ Insert at front of right p
17、artitiontemplate bool LList:insert(const Elem& item) fence-next = new Link(item, fence-next); if (tail = fence) tail = fence-next; rightcnt+; return true;/ Append Elem to end of the listtemplate bool LList:append(const Elem& item) tail = tail-next = new Link(item, NULL); rightcnt+; return true;23Ins
18、ert/AppendInsert/Append24RemovalRemoval/ Remove and return first Elem in right/ partitiontemplate bool LList:remove(Elem& it) if (fence-next = NULL) return false; it = fence-next-element; / Remember val Link* ltemp=fence-next;/ Remember link node fence-next = ltemp-next; / Remove if (tail = ltemp) /
19、 Reset tail tail = fence; delete ltemp; / Reclaim space rightcnt-; return true;25RemoveRemoveSystem new and delete are slow./ Singly-linked list node with freelisttemplate class Link private: static Link* freelist; / Headpublic: Elem element; / Value for this node Link* next; / Point to next node Li
20、nk(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;26FreelistsFreeliststemplate Link* Link:freelist = NULL;template / Overload for newvoid* Link:operato
21、r new(size_t) if (freelist = NULL) return :new Link; Link* temp = freelist; / Reuse freelist = freelist-next; return temp; / Return the linktemplate / Overload deletevoid Link:operator delete(void* ptr) (Link*)ptr)-next = freelist; freelist = (Link*)ptr;27Freelists (2)Freelists (2)Array-Based Lists:
22、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.28Comparison of
23、ImplementationsComparison of ImplementationsDE vs. n(P + E)=nDE/(P+E);E: Space for data value.P: Space for pointer.D: Number of elements in array.29Space ComparisonSpace ComparisonSimplify insertion and deletion: Add a prev pointer./ Doubly-linked list link nodetemplate class Link public: Elem eleme
24、nt; / 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; ;30Doubly Linked ListsDoubly Linked
25、Lists31Doubly Linked ListsDoubly Linked Lists32Doubly Linked InsertDoubly Linked Insert/ Insert at front of right partitiontemplate bool LList:insert(const Elem& item) fence-next = new Link(item, fence, fence-next); if (fence-next-next != NULL) fence-next-next-prev = fence-next; if (tail = fence) /
26、Appending new Elem tail = fence-next; / so set tail rightcnt+; / Added to right return true;33Doubly Linked InsertDoubly Linked Insert34Doubly Linked RemoveDoubly Linked Remove/ Remove, return first Elem in right parttemplate bool LList:remove(Elem& it) if (fence-next = NULL) return false; it = fenc
27、e-next-element; Link* 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;35Doubly Linked RemoveDoubly Linked RemoveOften want to insert record
28、s, delete records, search for records.Required concepts:Search key: Describe what we are looking forKey comparisonEquality: sequential search Relative order: sortingRecord comparison36DictionaryDictionaryHow do we generalize comparison?Use =, =: DisastrousOverload =, =: DisastrousDefine a function w
29、ith a standard nameImplied obligationBreaks down with multiple key fields/indices for same objectPass in a functionExplicit obligationFunction parameterTemplate parameter37Comparator ClassComparator Classclass intintCompare public: static bool lt(int x, int y) return x y; ;38Comparator ExampleCompar
30、ator Exampleclass 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; ;39Comparator Example (2)Comparator Example (2)/ The Dictionary abs
31、tract class.template 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;40Dictionary ADTDictionary ADTtemplate c
32、lass UALdict : public Dictionary private: AList* 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; ;41Unsorted List DictionaryUnsorted List DictionaryLIFO: Last In, First Out.Restricted for
33、m of list: Insert and remove only at front of list.Notation:Insert: PUSHRemove: POPThe accessible element is called TOP.42StacksStacks/ Stack abtract classtemplate class Stack public: / Reinitialize the stack virtual void clear() = 0; / Push an element onto the top of the stack. virtual bool push(co
34、nst 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;43Stack ADTStack ADT/ Array-based stack impleme
35、ntationprivate: int size; / Maximum size of stack int top; / Index for top element Elem *listArray; / Array holding elementsIssues:Which end is the top?What is the cost of the operations?44Array-Based StackArray-Based Stack45PUSHPUSHFor example: For example: （A A，B B，C C，D D） （LIFOLIFO）AACBABAtoptop
36、toptoptopHigh Address BCDLow Address 46例例1：一个栈的输入序列是一个栈的输入序列是12345，若在入栈的过，若在入栈的过程中允许出栈程中允许出栈，则栈的输出序列则栈的输出序列43512可能实现可能实现吗？吗？12345的输出呢？的输出呢？ 43512不不可可能能实实现现，主主要要是是其其中中的的12顺顺序序不不能能实现；实现； 12345的输出可以实现，只需压入一个立即弹的输出可以实现，只需压入一个立即弹出一个即可。出一个即可。 435612中到了中到了12顺序不能实现；顺序不能实现； 135426可以实现。可以实现。例例2：如果一个栈的输入序列为如果一
37、个栈的输入序列为123456，能否得，能否得到到435612和和135426的出栈序列？的出栈序列？答：答：答：答：47例例3：设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c，a，b，d，则则可得到出栈的元素序列是：可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，bA）、）、D）可以）可以， B）、）、C）不行。）不行。有无通用的判别原则？有无通用的判别原则？有！若输入序列是有！若输入序列是 ,P,Pj jP Pk kP Pi i (P(Pj jPPk kPPi i) ) ，一定不存在这样的输出序列一定不存在这样的输出序列 ,P,Pi
38、iP Pj jP Pk k 答：答：即对于输入序列即对于输入序列1，2，3，不存在输出序列，不存在输出序列3，1，2/ Linked stack implementationprivate: Link* top; / Pointer to first elem int size; / Count number of elemsWhat is the cost of the operations?How do space requirements compare to the array-based stack implementation?48Linked StackLinked StackF
39、IFO: First in, First OutRestricted form of list: Insert at one end, remove from the other.Notation:Insert: EnqueueDelete: DequeueFirst element: FrontLast element: Rear49QueuesQueues50Queue Implementation (1)Queue Implementation (1)51Queue Implementation (2)Queue Implementation (2)52数据结构课程的内容数据结构课程的内
40、容逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构53第四章内容第四章内容541. 线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示（a1, a2, ai-1，ai, ai1 ，, an）n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点551.1.1 顺序表的实现（或操作）顺序表的实现（或操作）1.1 线性表的实现方式之一
41、线性表的实现方式之一-顺序表顺序表. .用一组用一组地址连续地址连续的存储单元依次存储线性表的元素，可通过的存储单元依次存储线性表的元素，可通过数组数组Vn来实现来实现1) 1) 修改修改 通过数组的下标便可访问某个特定元素并修改之。通过数组的下标便可访问某个特定元素并修改之。核心语句核心语句: : Vi=x; 顺序表修改操作的时间效率是顺序表修改操作的时间效率是T(n)=O(1)2)2)插入插入 在线性表的第在线性表的第i i个位置前插入一个元素个位置前插入一个元素实现步骤：实现步骤：将第将第n至第至第i 位的元素向后移动一个位置；位的元素向后移动一个位置；将要插入的元素写到第将要插入的元素
42、写到第i个位置；个位置；表长加表长加1。注意：事先应判断注意：事先应判断: 插入位置插入位置i 是否合法是否合法?表是否已满表是否已满? 应当有应当有1in+1 或或 i=1,n+1for (j=n;j=i;j-)for (j=n;j=i;j-)aj+1=aj; aj+1=aj; ai=x; ai=x; n+;n+;核心语句：核心语句：/ / 元素后移一个位置元素后移一个位置/ / 插入插入x x / / 表长加表长加1 1 56实现步骤：实现步骤：将第将第i 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意：事先需要判断，注意：事先需要判断，删除位置删除位
43、置i 是否合法是否合法?应当有应当有1in 或或 i=1, n3)3)删除删除 删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for (j=i+1;j=n;j+)for (j=i+1;jdata=new_value 即可。即可。1.2.3 单链表的插入单链表的插入xsbapabp核心语句核心语句Step 1Step 1：s-next=p-next;Step 2Step 2：p-next=s ；p-nexts-next591.2.4 单链表的删除单链表的删除cabp核心语句核心语句q = p-next; /保存保存b的指针，靠它才能指向的指针，靠它才能指向cp-next=q-ne
44、xt; /a、c两结点相连两结点相连free(q) ； /删除删除b结点，彻底释放结点，彻底释放p-next(p-next) - next链表中每个结点都要增加一个指针空间，相当于总共增加了链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变个整型变量，空间复杂度为量，空间复杂度为 O(n)。空间效率分析60 顺序存储的优点是存储密度大顺序存储的优点是存储密度大( (1)1)，存储空间利用率高。缺点是，存储空间利用率高。缺点是插入或删除元素时不方便。插入或删除元素时不方便。 链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存链式存储的优点是插入或删除元素时很方便，使用灵活。
45、缺点是存储密度小（储密度小（11），存储空间利用率低。），存储空间利用率低。顺序存储和链式存储各有哪些优缺点？顺序存储和链式存储各有哪些优缺点？事实上，链表插入、删除运算的快捷是以空间代价来换取时间。事实上，链表插入、删除运算的快捷是以空间代价来换取时间。在什么情况下用顺序表比链表好？在什么情况下用顺序表比链表好？顺序表适宜于做顺序表适宜于做查找查找这样的静态操作；链表宜于做这样的静态操作；链表宜于做插入、删除插入、删除这样的动态操作。这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其
46、主要操作是插入、删除操作，则采用链表。若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。611. 定义定义2. 栈栈与同线性表相同，仍为一对一关系。与同线性表相同，仍为一对一关系。用用顺序栈顺序栈或或链栈链栈存储均可，但以顺序栈更常见存储均可，但以顺序栈更常见只能在只能在栈顶栈顶运算，且访问结点时依照运算，且访问结点时依照后进先出后进先出（LIFO）或先进后出或先进后出（FILO）的原则。的原则。关键是编写关键是编写入栈入栈和和出栈出栈函数，具体实现依顺序栈或函数，具体实现依顺序栈或链栈的不同而不同。链栈的不同而不同。基本操作有入栈、出栈、读栈顶元素值、建栈、或基本操作有入栈、
47、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。判断栈满、栈空等。3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式 2. 逻辑结构逻辑结构限定只能在限定只能在表的一端表的一端进行插入和删除运算的进行插入和删除运算的线性表线性表（只能在（只能在栈顶栈顶操作）操作） 链栈不必设头结点，因为栈顶（表头）操作频繁；链栈不必设头结点，因为栈顶（表头）操作频繁； 采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。且存在多个栈的情况下，链栈是栈的首选存储方式。621. 定定
48、 义义3. 队列队列与同线性表相同，仍为一对一关系。与同线性表相同，仍为一对一关系。顺序队顺序队或或链队链队，以循环顺序队更常见。，以循环顺序队更常见。只能在队首和队尾运算，且访问结点时依照只能在队首和队尾运算，且访问结点时依照先进先出先进先出（FIFO）的原则。的原则。关键是掌握关键是掌握入队入队和和出队出队操作，具体实现依顺序队或操作，具体实现依顺序队或链队的不同而不同。链队的不同而不同。基本操作有入队或出队，建空队列，判队空或队满基本操作有入队或出队，建空队列，判队空或队满等操作。等操作。3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式 2. 逻辑结构逻辑结构只能在表的
49、一端进行插入运算，在表的另一端进行删只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表除运算的线性表 （头删尾插头删尾插）63线性表、栈与队列的异同点线性表、栈与队列的异同点相相同同点点：逻逻辑辑结结构构相相同同，都都是是线线性性的的；都都可可以以用用顺顺序序存存储储或或链链表表存存储储；栈栈和和队队列列是是两两种种特特殊殊的的线线性性表表，即即受受限限的的线线性性表表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。不同点：不同点： 运运算算规规则则不不同同，线线性性表表为为随随机机存存取取，而而栈栈是是只只允允许许在在一一端端进进行行插插入入和和删删除除运运算算，因因而而是是后后进进先先出出表表LIFOLIFO；队队列列是是只只允允许许在在一一端端进进行行插插入入、另另一一端端进进行行删删除除运运算算，因因而而是是先先进进先先出出表表FIFOFIFO。 用途不同，线性表比较通用；堆栈用于函数调用、递归和简用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。计等。
