C++程序设计简明教程教学课件王晓东第11章 C++应用.ppt

《C++程序设计简明教程教学课件王晓东第11章 C++应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11章C++应用11.1栈类11.2矩阵类11.3链表类11.4二叉树类11.1栈类栈是只允许在表的一端进行插入和删除等操作的线性表，栈允许操作的一端称为栈顶，另一端称为栈底。栈中元素的数量达到上限称为栈满，栈中没有元素称为栈空。栈的存储方式有顺序存储和链式存储两种。顺序存储用一维数组的形式实现，而链式存储用链表的形式实现。栈的操作主要有入栈、出栈、测试栈满或者栈空等，所谓入栈，就是在栈顶插入一个元素，新的栈顶是刚插入的这个元素；出栈就是从栈顶删除一个元素，原栈顶元素的后继元素自动成为新的栈顶。栈的操作有一个十分重要的特点，

2、即后进先出。template//类模板classstack{public:stack(void);~stack();Tpop(void);//出栈voidpush(Tx);//入栈ints_empty(void);//测试栈空ints_full(void);//测试栈满private:Ts[MAX];//栈空间inttop;//栈顶};栈类11.2矩阵类一般用二维数组存储和表示矩阵，这种方式必须事先指定矩阵行和列的长度。矩阵的操作主要有加、减、乘、求逆、转置等。classmatrix{public:matrix

3、(intr=2,intc=2);matrix(matrix&m);~matrix();voidset(void);matrixoperator=(matrix&m);matrixoperator+(matrix&m);//矩阵加法matrixoperator-(matrix&m);//矩阵减法matrixoperator*(matrix&m);//矩阵乘法doubleoperator()(intx,inty);friendostream&operator<<(ostream&out,matrix&m);private:intr

4、ow;//矩阵行数intcol;//矩阵列数double**p;//指向指针的指针};11.3链表类线性表的存储结构有顺序和链式两种方式。顺序存储能够较为快捷地访问表中任意元素，然而其空间利用率不高，做插入或删除操作时需要移动大量元素。链式存储不要求逻辑上相邻的元素在物理位置上也相邻，因此它克服了顺序存储的一些不足，是工程实践中常用的一种数据存储方式。链表链表由一些彼此存在逻辑联系的结点组成，这些结点一般是动态生成的。每一个结点包含数据域和next指针，next指针指向链表中的下一个结点。访问链表结点时由head指针指示，总是

5、从链表的首结点开始，依靠next指针顺序下访。链表实现实现链表需要两个步骤，首先定义链表结构，其次在程序中动态地生成结点，并与前一个结点链接。链表的操作主要有创建、插入以及删除等。classlist{protected:peo*head;//链表头指针public:list(void);~list();voidinsert(peo*);//插入结点voiddel(constchar*);//删除结点voidser(constchar*);//查询结点voiddisplay();//显示结点};11.4二叉树类理论上可以把二叉树

6、理解为一种特殊的树，它由根和两个不相交的左子树、右子树组成，其中左子树和右子树也是二叉树。二叉树的特点是，每个结点最多只有两棵子树。二叉树操作二叉树的基本操作有建立、添加结点、删除结点、查询结点、遍历、清空整棵树等。遍历即显示一棵树的所有结点，有前序、中序和后序等3种方式。前序遍历是先访问树的根结点，再访问左子树，最后访问右子树；中序遍历是先访问左子树，再访问树的根结点，最后访问右子树；后序遍历是先访问左子树，再访问右子树，最后访问树的根结点。node类classnode{friendclasstree;public:void

7、set(intx);private:intdata;node*left;//左子树node*right;//右子树};二叉树类classtree{private:node*root;public:tree(void);~tree();node*get_r();//得到根结点voidfree_t(node*r);//释放二叉树结点的空间voidbuild_t(intd);//添加结点voidpreorder(node*r);//前序遍历voidinorder(node*r);//中序遍历voidpostorder(node*r)

8、;//后序遍历};