C++和数据结构.ppt

《C++和数据结构.ppt》由会员分享，可在线阅读，更多相关《C++和数据结构.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（三）,常宝宝北京大学计算机科学与技术系,内容提要,栈队列 栈和队列是两种特殊的线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表。 栈和队列广泛地应用在各种软件系统中，是程序设计中必须掌握的两种基本数据结构。,什么是栈？,若限定仅在线性表的一端进行插入和删除操作，这样的线性表称为栈。能够进行插入和删除操作的一端称为栈顶。另一端则相应称为栈底。位于栈顶的元素称为栈顶元素，位于栈底的元素称为栈底元素。不含任何元素的栈称为空栈。栈的特点是后进先出。(Last In First Out: LIFO)上溢和下溢,和栈有关的操作,和栈有关的操作：构造一个不含任何元素

2、的空栈判断栈是否为空栈判断栈是否满返回栈中的元素个数清空栈向栈顶压入(添加)一个元素从栈顶弹出(删除)一个元素读取栈顶元素,栈作为抽象数据类型,template class Stack public: enum error_code success, overflow, underflow;protected: .public: /操作 Stack(); Stack(const Stack,栈操作,Stack:Stack();/ PRECONDITION:/ POSTCONDITION: 建立了一个空栈,error_code Stack:push(const stack_entry/ PREC

3、ONDITION: 栈未满/ POSTCONDITION: 元素item被加入到栈的顶部/ REMARKS: 若栈未满,元素item被加入到栈的顶部,若栈已满,返回overflow,error_code Stack:pop();/ PRECONDITION: 栈非空/ POSTCONDITION: 栈顶部的元素被删除/ REMARKS: 若栈非空,栈顶元素被删除,若栈是空栈,返回错误代码underflow, 在实际实现时，error_code 应写作 Stack:error_code,栈操作,bool Stack:empty() const;/ PRECONDITION: / POSTCOND

4、ITION: 栈的状态未发生变化/ REMARKS: 若栈是空栈,返回true,若栈不是空栈,返回false,error_code Stack:top(stack_entry/ PRECONDITION: 栈非空/ POSTCONDITION: 栈的状态未发生变化/ REMARKS: 若栈非空,栈顶元素被读入item中,若栈是空栈,返回错误/ 代码underflow,栈结构的使用,int main() Stack intStack;/创建一个元素类型是整数的空栈 int n,item; cout n; for (int i=0; i item; intStack.push(item); /将整

5、数item压入栈中 cout endl; while ( !intStack.empty() ) /判断栈是否空栈 intStack.top(item); /读取位于栈顶的整数 cout item “ “; intStack.pop();/将栈顶的整数弹出 cout next; delete oldtop; return success;,template Stack:error_code Stack:push(const stack_entry,栈的实现 链式存储,x,template bool Stack:empty() const if ( top_node = NULL ) retur

6、n true; return false;,template Stack:error_code Stack:top(stack_entry,什么是队列？,若限定线性表仅能在一端进行插入，另一端进行删除，这样的线性表称为队列。能够进行插入的一端称为队尾。能够进行删除的一端称为队头。,位于队尾的元素称为队尾元素，位于队头的元素称为队头元素。不含任何元素的队列称为空队列。队列的特点是先进先出。(First In First Out: FIFO),和队列有关的操作,和队列有关的操作：构造一个不含任何元素的空队列判断队列是否空队列判断队列是否满返回队列中的元素个数清空队列在队尾加入一个元素删除位于队头的

7、元素读取队头元素,队列作为抽象数据类型,template class Queue public: enum error_code success, overflow, underflow;protected: .public: /操作 Queue(); Queue(const Queue,队列的使用,int main() Queue intQueue;/创建一个整型空队列 int x; for (int i = 0; i10; i+ ) intQueue.append(i);/在队列尾部插入整数 while (!intQueue.empty() /判断队列是否空队列 intQueue.retrieve(x);/读取队列头部的元素 cout x “ ”; intQueue.serve();/删除队列头部的元素 cout next; if ( front=NULL ) rear = NULL; delete oldfront; return success;,上机作业,在机器上用C+分别实现顺序存储和链式存储的栈结构。在机器上用C+分别实现顺序存储和链式存储的队列结构。在实现链式存储的栈结构和队列结构时，必须提供析构函数、拷贝构造函数和赋值运算符重载函数，为什么？,