数据结构课件C++版第四章链式存储结构的表堆栈和队列幻灯片.ppt

链式堆栈类的定义和实现 templateclass T LinStackT::Pop(void) { if(size == 0) { cout堆栈已空，无元素可删！endl; exit(1); } StackNodeT *p = top-next; T data = top-data; delete top; size--; top = p; retrun data; } 计 算 机 学 院 信 息 教 研 室 DS StackNode.cpp an-1 an-2 an-3 a0 p 链式堆栈类的定义和实现 templateclass T LinStackT::ClearStack(void) { StackNodeT *p,*p1; p = top; while(p! = NULL) { p1 = p; p = p-next; delete p1; } size = 0; } 计 算 机 学 院 信 息 教 研 室 DS StackNode.cpp an-1 an-2 an-3 a0 p p1 templateclass T int LinListT::EndOfList(void) const //currPtr是否指在链表尾 { if(currPtr == NULL) return 1; else return 0; } 计 算 机 学 院 信 息 教 研 室 DS a0 a1 an ^ … head 4.2.2 单链表类的定义和实现 定位，前插入、删除和取元素成员函数的时间复杂度均为O(n). 与顺序表相比，链表类增加了一组循环遍历成员函数。可以有效降低对循环遍历操作的时间复杂度。(为什么？) 计 算 机 学 院 信 息 教 研 室 DS a0 a1 an ^ … head #include LinList.h void main(void) { LinListint myList; for(int i=0;i5;i++) myList.Insert(i+10,i); cout测试GetData()成员函数结果如下:endl; for(i=0;i5;i++) coutmyList.GetData(i) ; cout测试遍历成员函数结果如下：endl; ListNodeint *p = myList.Reset(); //p指在第一个结点 while(!myList.EndOfList()) //是否到达表尾 { coutmyList.Next ; p = myList.Next(); //p指在第一个结点 } } 计 算 机 学 院 信 息 教 研 室 DS 单链表类的应用 表和顺序表 typedef int DataType; //具体应用时定义的数据类型Datatype #include seqlist.h //类Seqlist的定义和实现头文件 void main(void) { SeqList myList; //插入5个整型元素 for(int i=0;i5;i++) myList.Insert(i+10,i); cout测试GetData()成员函数结果如下:endl; for(i=0;i5;i++) coutmyList.GetData(i)“ ” ; cout测试Delete()成员函数结果如下:endl; for(i=0;i5;i++) coutmyList.Delete(0) ; } 计 算 机 学 院 信 息 教 研 室 DS 顺序表类的应用 单循环链表 (Circular Linked List) 循环链表是单链表的变形。 相同点：两者结点结构相同。 不同点：循环链表最后一个结点的next指针不为 0 (NULL)，而是指向了表的前端。 特点：只要知道表中某一结点的地址，就可搜寻到所有其他结点。 计 算 机 学 院 信 息 教 研 室 xdc DS head #includeiostream.h #includestdio.h templateclass Tclass CirList; //前视定义，否则，无法定义友元 templateclass Tclass ListNode { friend class CirListT; //定义友元 … } 计 算 机 学 院 信 息 教 研 室 DS ListNode.h 单循环链表类的定义 templateclass Tclass CirList { private: ListNodeT *h