《《C++程序设计简明教程》-王晓东-电子教案 第11章 C++应用》由会员分享，可在线阅读，更多相关《《C++程序设计简明教程》-王晓东-电子教案 第11章 C++应用（14页珍藏版）》请在金锄头文库上搜索。
1、第11章 C+应用,11.1 栈类 11.2 矩阵类 11.3 链表类 11.4 二叉树类,11.1 栈类,栈是只允许在表的一端进行插入和删除等操作的线性表，栈允许操作的一端称为栈顶，另一端称为栈底。栈中元素的数量达到上限称为栈满，栈中没有元素称为栈空。,栈的存储方式有顺序存储和链式存储两种。顺序存储用一维数组的形式实现，而链式存储用链表的形式实现。 栈的操作主要有入栈、出栈、测试栈满或者栈空等，所谓入栈，就是在栈顶插入一个元素，新的栈顶是刚插入的这个元素；出栈就是从栈顶删除一个元素，原栈顶元素的后继元素自动成为新的栈顶。 栈的操作有一个十分重要的特点，即后进先出。,template /类模板
2、 class stack public: stack(void); stack(); T pop(void); /出栈 void push(T x); /入栈 int s_empty(void); /测试栈空 int s_full(void); /测试栈满 private: T sMAX; /栈空间 int top; /栈顶 ;,栈类,11.2 矩阵类,一般用二维数组存储和表示矩阵，这种方式必须事先指定矩阵行和列的长度。 矩阵的操作主要有加、减、乘、求逆、转置等。,class matrix public: matrix(int r=2,int c=2); matrix(matrix ,11.3
3、 链表类,线性表的存储结构有顺序和链式两种方式。顺序存储能够较为快捷地访问表中任意元素，然而其空间利用率不高，做插入或删除操作时需要移动大量元素。 链式存储不要求逻辑上相邻的元素在物理位置上也相邻，因此它克服了顺序存储的一些不足，是工程实践中常用的一种数据存储方式。,链表,链表由一些彼此存在逻辑联系的结点组成，这些结点一般是动态生成的。每一个结点包含数据域和next指针，next指针指向链表中的下一个结点。 访问链表结点时由head指针指示，总是从链表的首结点开始，依靠next指针顺序下访。,链表实现,实现链表需要两个步骤，首先定义链表结构，其次在程序中动态地生成结点，并与前一个结点链接。 链
4、表的操作主要有创建、插入以及删除等。,class list protected: peo* head; /链表头指针 public: list(void); list(); void insert(peo*);/插入结点 void del(const char*);/删除结点 void ser(const char*);/查询结点 void display();/显示结点 ;,11.4 二叉树类,理论上可以把二叉树理解为一种特殊的树，它由根和两个不相交的左子树、右子树组成，其中左子树和右子树也是二叉树。 二叉树的特点是，每个结点最多只有两棵子树。,二叉树操作,二叉树的基本操作有建立、添加结点、
5、删除结点、查询结点、遍历、清空整棵树等。 遍历即显示一棵树的所有结点，有前序、中序和后序等3种方式。前序遍历是先访问树的根结点，再访问左子树，最后访问右子树；中序遍历是先访问左子树，再访问树的根结点，最后访问右子树；后序遍历是先访问左子树，再访问右子树，最后访问树的根结点。,node类,class node friend class tree; public: void set(int x); private: int data; node *left;/左子树 node *right;/右子树 ;,二叉树类,class tree private: node *root; public: tree(void); tree(); node* get_r();/得到根结点 void free_t(node *r);/释放二叉树结点的空间 void build_t(int d);/添加结点 void preorder(node *r);/前序遍历 void inorder(node *r); /中序遍历 void postorder(node *r); /后序遍历 ;,
