C++和数据结构.ppt
数据结构（三）,常宝宝北京大学计算机科学与技术系chbbpku.edu.cn,内容提要,栈队列 栈和队列是两种特殊的线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表。 栈和队列广泛地应用在各种软件系统中，是程序设计中必须掌握的两种基本数据结构。,什么是栈？,若限定仅在线性表的一端进行插入和删除操作，这样的线性表称为栈。能够进行插入和删除操作的一端称为栈顶。另一端则相应称为栈底。位于栈顶的元素称为栈顶元素，位于栈底的元素称为栈底元素。不含任何元素的栈称为空栈。栈的特点是后进先出。(Last In First Out: LIFO)上溢和下溢,和栈有关的操作,和栈有关的操作：构造一个不含任何元素的空栈判断栈是否为空栈判断栈是否满返回栈中的元素个数清空栈向栈顶压入(添加)一个元素从栈顶弹出(删除)一个元素读取栈顶元素,栈作为抽象数据类型,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/ PRECONDITION: 栈未满/ POSTCONDITION: 元素item被加入到栈的顶部/ REMARKS: 若栈未满,元素item被加入到栈的顶部,若栈已满,返回overflow,error_code Stack:pop();/ PRECONDITION: 栈非空/ POSTCONDITION: 栈顶部的元素被删除/ REMARKS: 若栈非空,栈顶元素被删除,若栈是空栈,返回错误代码underflow, 在实际实现时，error_code 应写作 Stack:error_code,栈操作,bool Stack:empty() const;/ PRECONDITION: / POSTCONDITION: 栈的状态未发生变化/ 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); /将整数item压入栈中 cout << endl; while ( !intStack.empty() ) /判断栈是否空栈 intStack.top(item); /读取位于栈顶的整数 cout << item << “ “; intStack.pop();/将栈顶的整数弹出 cout << endl;,栈的实现 顺序存储,和线性表类似，栈也有两种存储结构：(1) 顺序存储 (2) 链式存储。顺序存储：用一组连续的存储单元依次存放自栈底到栈顶的数据元素。,栈的实现 顺序存储,template class Stack public: enum error_code success, overflow, underflow;protected: int count; stack_entry entrymax_entry;public: /操作 Stack(); Stack(const Stack,栈的实现 顺序存储,template Stack:Stack() count = 0;,template Stack:error_code Stack:pop() if ( count = 0 ) return underflow; count-; return success;,template Stack:error_code Stack:push(const stack_entry,栈的实现 顺序存储,x,template bool Stack:empty() const if ( count = 0 ) return true; return false;,template Stack:error_code Stack:top(stack_entry,栈的实现 链式存储,在栈的链式实现中，栈被组织成一个链表。栈顶指针在链式存储的栈中：(1) 压入元素(2) 弹出元素,栈的实现 链式存储,template class Stack public: enum error_code success, overflow, underflow;protected: struct node stack_entry entry; node *next; node():next(0) node(const stack_entry ,栈的实现 链式存储,template Stack:Stack() top_node = NULL;,template Stack:error_code Stack:pop() if (top_node = NULL) return underflow; node* oldtop = top_node; top_node = top_node->next; delete oldtop; return success;,template Stack:error_code Stack:push(const stack_entry,栈的实现 链式存储,x,template bool Stack:empty() const if ( top_node = NULL ) return true; return false;,template Stack:error_code Stack:top(stack_entry,什么是队列？,若限定线性表仅能在一端进行插入，另一端进行删除，这样的线性表称为队列。能够进行插入的一端称为队尾。能够进行删除的一端称为队头。,位于队尾的元素称为队尾元素，位于队头的元素称为队头元素。不含任何元素的队列称为空队列。队列的特点是先进先出。(First In First Out: FIFO),和队列有关的操作,和队列有关的操作：构造一个不含任何元素的空队列判断队列是否空队列判断队列是否满返回队列中的元素个数清空队列在队尾加入一个元素删除位于队头的元素读取队头元素,队列作为抽象数据类型,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; i<10; i+ ) intQueue.append(i);/在队列尾部插入整数 while (!intQueue.empty() /判断队列是否空队列 intQueue.retrieve(x);/读取队列头部的元素 cout << x << “ ”; intQueue.serve();/删除队列头部的元素 cout << endl;,队列的实现 顺序存储,在队列的顺序实现中，用一组连续的存储单元存储队列中的元素。(1) 队头固定(2) 队头、队尾均不固定(3) 循环数组防止“假溢出”,队列的实现 顺序存储,template class Stack public: enum error_code success, overflow, underflow;protected: int count; stack_entry entrymax_entry;public: /操作 Stack(); Stack(const Stack,template class Queue public: enum error_code success, overflow, underflow;protected: int count; int front, rear; queue_entry entrymax_entry;public: /操作 Queue(); Queue(const Queue,队列的实现 顺序存储,template Queue:Queue() count=0; rear=max_entry-1; front=0;,template bool Queue:empty() const if ( count=0 ) return true; return false;,template Queue:error_code Queue:append(const queue_entry,队列的实现 顺序存储,template Queue:error_code Queue:retrieve(queue_entry,template Queue:error_code Queue:serve() if ( count = 0 ) return underflow; count-; front = (front+1)%max_entry; return success;,队列的实现 链式存储,在队列的链式实现中，队列被组织成一个链表。队头指针和队尾指针在链式存储的队列中：(1) 插入元素 (2) 删除出元素,队列的实现 链式存储,template class Queue public: enum error_code success, overflow, underflow;protected: struct node queue_entry entry; node *next; node():next(0) node(const queue_entry ,队列的实现 链式存储,template Queue:Queue():front(NULL),rear(NULL) ,template bool Queue:empty() const if ( front=NULL ) return true; return false;,template Queue:error_code Queue:append(const queue_entry,队列的实现 链式存储,template Queue:error_code Queue:retrieve(queue_entry,template Queue:error_code Queue:serve() if ( front = NULL ) return underflow; node* oldfront = front; front = front->next; if ( front=NULL ) rear = NULL; delete oldfront; return success;,上机作业,在机器上用C+分别实现顺序存储和链式存储的栈结构。在机器上用C+分别实现顺序存储和链式存储的队列结构。在实现链式存储的栈结构和队列结构时，必须提供析构函数、拷贝构造函数和赋值运算符重载函数，为什么？,
