2019数据结构C++第3章第6讲.pptx

1;2;应用举例;顺序表需要掌握的内容： 算法2.7 算法2.8 算法2.10 顺序表的性能分析 链表的内容 算法2.15 算法2.16 算法2.18 ，2.20,2.21 难点：指针操作 ;;;双向链表 (Doubly Linked List);结点指向p == p-lLink-rLink == p-rLink-lLink;双向循环链表类的定义;template class T class DblList { //链表类定义 public: DblList ( T uniqueVal ) { //构造函数 first = new DblNodeT (uniqueVal); first-rLink = first-lLink = first; }; DblNodeT *getFirst () const { return first; } void setFirst ( DblNodeT, E *ptr ) { first = ptr; } DblNodeT *Search ( T x, int d); //在链表中按d指示方向寻找等于给定值x的结点, //d=0按前驱方向,d≠0按后继方向;DblNodeT *Locate ( int i, int d ); //在链表中定位序号为i(≥0)的结点, d=0按前驱方 //向,d≠0按后继方向 bool Insert ( int i, T x, int d ); //在第i个结点后插入一个包含有值x的新结点,d=0 //按前驱方向,d≠0按后继方向 bool Remove ( int i,T x, int d ); //删除第i个结点 bool IsEmpty() { return first-rlink == first; } //判双链表空否 private: DblNodeT *first; //表头指针 };;12;双向循环链表的搜索算法;14;15;16;静态链表;静态链表的结构;第三章 栈与队列;第三章 栈与队列;栈 ( Stack );3.1栈的类型定义;栈的抽象数据类型;栈的数组存储表示 — 顺序栈;25;26;27;28;出栈操作图示;顺序栈的操作;template class E void SeqStackE::Push(E x) { //若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理 if (IsFull() == true) overflowProcess; //栈满 elements[++top] = x; //栈顶指针先加1, 再进栈 }; template class E bool SeqStackE::Pop(E x) { //函数退出栈顶元素并返回栈顶元素的值 if (IsEmpty() == true) return false; x = elements[top--]; //栈顶指针退1 return true; //退栈成功 }; ;template class E bool SeqstackE::getTop(E x) { //若栈不空则函数返回该栈栈顶元素的地址 if (IsEmpty() == true) return false; x = elements[top]; return true; }; ;33;栈的链接存储表示 — 链式栈;链式栈 (LinkedStack)类的定义;template class E class LinkedStack : public StackE { //链式栈类定义 private: StackNodeE *top; //栈顶指针 void output(ostream os, StackNode E *ptr, int i); //递归输出栈的所有元素 public: LinkedStack() : top(NULL) {} //构造函数 ～LinkedStack() { makeEmpty(); } //析构函数 void Push(E x); //进栈 bool Pop(E x); //退栈; bool getTop(E x) const; //取栈顶 bool IsEmpty() const { return top == NULL; } voi