C++程序设计简明教程 -王晓东 第11章 C++应用.pptVIP

第11章 C++应用 11.1 栈类 11.2 矩阵类 11.3 链表类 11.4 二叉树类 11.1 栈类 栈是只允许在表的一端进行插入和删除等操作的线性表，栈允许操作的一端称为栈顶，另一端称为栈底。栈中元素的数量达到上限称为栈满，栈中没有元素称为栈空。 栈的存储方式有顺序存储和链式存储两种。顺序存储用一维数组的形式实现，而链式存储用链表的形式实现。 栈的操作主要有入栈、出栈、测试栈满或者栈空等，所谓入栈，就是在栈顶插入一个元素，新的栈顶是刚插入的这个元素；出栈就是从栈顶删除一个元素，原栈顶元素的后继元素自动成为新的栈顶。 栈的操作有一个十分重要的特点，即后进先出。 栈类 template class T //类模板 class stack { public: stack(void); ~stack(); T pop(void); //出栈 void push(T x); //入栈 int s_empty(void); //测试栈空 int s_full(void); //测试栈满 private: T s[MAX]; //栈空间 int top; //栈顶 }; 11.2 矩阵类 一般用二维数组存储和表示矩阵，这种方式必须事先指定矩阵行和列的长度。 矩阵的操作主要有加、减、乘、求逆、转置等。 class matrix { public: matrix(int r=2,int c=2); matrix(matrix m); ~matrix(); void set(void); matrix operator =(matrix m); matrix operator +(matrix m);//矩阵加法 matrix operator -(matrix m);//矩阵减法 matrix operator *(matrix m);//矩阵乘法 double operator ()(int x,int y); friend ostream operator (ostream out,matrix m); private: int row;//矩阵行数 int col;//矩阵列数 double **p;//指向指针的指针 }; 11.3 链表类 线性表的存储结构有顺序和链式两种方式。顺序存储能够较为快捷地访问表中任意元素，然而其空间利用率不高，做插入或删除操作时需要移动大量元素。 链式存储不要求逻辑上相邻的元素在物理位置上也相邻，因此它克服了顺序存储的一些不足，是工程实践中常用的一种数据存储方式。 链表 链表由一些彼此存在逻辑联系的结点组成，这些结点一般是动态生成的。每一个结点包含数据域和next指针，next指针指向链表中的下一个结点。 访问链表结点时由head指针指示，总是从链表的首结点开始，依靠next指针顺序下访。 链表实现 实现链表需要两个步骤，首先定义链表结构，其次在程序中动态地生成结点，并与前一个结点链接。 链表的操作主要有创建、插入以及删除等。 class list { protected: peo* head; //链表头指针 public: list(void); ~list(); void insert(peo*);//插入结点 void del(const char*);//删除结点 void ser(const char*);//查询结点 void display();//显示结点 }; 11.4 二叉树类 理论上可以把二叉树理解为一种特殊的树，它由根和两个不相交的左子树、右子树组成，其中左子树和右子树也是二叉树。 二叉树的特点是，每个结点最多只有两棵子树。 二叉树操作 二叉树的基本操作有建立、添加结点、删除结点、查询结点、遍历、清空整棵树等。 遍历即显示一棵树的所有结点，有前序、中序和后序等3种方式。前序遍历是先访问树的根结点，再访问左子树，最后访问右子树；中序遍历是先访问左子树，再访问树的根结点，最后访问右子树；后序遍历是先访问左子树，再访问右子树，最后访问树的根结点。 node类