栈类模板的设计与实现.docx
《栈类模板的设计与实现.docx》由会员分享，可在线阅读，更多相关《栈类模板的设计与实现.docx（24页珍藏版）》请在冰点文库上搜索。
栈类模板的设计与实现
封皮
（按学校要求手工填写）
成绩评定表
学生姓名
蒋倩雯
班级学号
1103060412
专业
通信工程
课程设计题目
栈类模板的设计与实现
评
语
组长签字：
成绩
日期
20年月日
课程设计任务书
学院
信息科学与工程
专业
通信工程
学生姓名
蒋倩雯
班级学号
1103060412
课程设计题目
栈类模板的设计与实现
实践教学要求与任务
进行栈类模板的设计并实现，栈采用链式存储结构，数据元素可以是char,int,float等多种数据类型，包括以下功能：
（1）实现初始化栈操作，建立一个空栈；
（2）实现清空栈操作；
（3）实现判断栈是否为空的操作；
（4）实现求栈长度的操作；
（5）实现返回栈顶元素的操作；
（6）实现入栈操作；
（7）实现出栈操作；
（8）实现栈的遍历操作，输出栈的每个元素。
（9）将上述功能作为类的成员函数实现，编写主函数测试上述功能。
工作计划与进度安排
第17周：
分析题目，查阅课题相关资料，进行类设计、算法设计；
第18周：
程序的设计、调试与实现；
第19周：
程序测试与分析，撰写课程设计报告，进行答辩验收。
指导教师：
201年月日
专业负责人：
201年月日
学院教学副院长：
201年月日
摘要
本文采用C++语言实现了栈类模板的设计与实现，采用VisualC++6.0的控制台工程和MFC工程分别实现了栈类的初始化，清空栈，判断空栈，求栈长度，进栈出栈等操作，通过对两种程序的测试结果表明：
，两种程序均能正确的实现栈类模板的设计与实现。
关键词：
栈类模板；控制台工程；MFC工程
目录
1需求分析1
2算法基本原理1
3类设计3
4基于控制台的应用程序3
4.1类的接口设计4
4.2类的实现5
4.3主函数设计6
4.4基于控制台的应用程序测试7
5基于MFC的应用程序8
5.1基于MFC的应用程序设计8
5.1.1MFC程序界面设计8
5.1.2MFC程序代码设计11
5.2基于MFC的应用程序测试15
结论18
参考文献19
1需求分析
（1）本题目是栈类模板的设计与实现，栈类模板是采用C++语言将栈面向对象化，用C++语言设计了一个栈类模板，类带变了某一批对象的共性与特征，是用来定义对象的一种抽象类型。
（2）设计的内容为：
初始化栈操作，清空栈，判断是否空栈，求栈的长度，返回栈顶元素，入栈出栈，栈的遍历，输出元素。
（3）设计采用链式存储结构。
2算法基本原理
（1）链式存储结构的栈称为链栈（Linked-stack）,对于链栈而言，栈顶元素不断改变，程序只有使用一个top引用来记录当前栈顶元素即可。
Top引用变了永远引用栈顶元素，在使用一个size变量记录当前栈中包含多少元素。
进栈：
对于链栈的进栈操作，需要让top引用指向新添加的元素，新元素的next引用执行原来的栈顶元素，同时记录栈内元素个数的size变量+1
出栈：
对于链栈的出栈操作，需要将栈顶元素弹出栈，程序需要让top引用执行原栈顶元素的下一个元素，并释放原来的栈顶元素，同时记录下栈内元素size变量-1.
（2）基本操作：
InitStack（S）
操作前提：
S为未初始化的栈
操作结果：
将S初始化为空栈
ClearStacck（S）
操作前提：
栈S已经存在
操作结果：
将栈S置成空栈
IsEmpty（S）
操作前提：
栈S已经存在
操作结果：
判断栈空函数，若S为空栈，则函数值为TRUE，否则为FALSE
Stacklength（S）
操作前提：
栈S已经存在
操作结果：
返回栈中元素的个数
Push（S，x）
操作前提：
栈S已经存在
操作结果：
在S的顶部插入元素，若S栈未满，将元素插入栈顶位置。
若已满，返回FALSE，表示操作失败，否则返回TRUE。
（3）首先要定义一个类为stack，其类型名为Th，操作分为九个步骤，具体步骤如下：
第1步，实现栈初始化操作，建立一个空栈stack。
第2步，实现清空栈的操作，执行clear语句，例如本题输入元素为5、7、9，执行clear语句，将其清空。
第3步，实现判断栈是否为空的操作，执行empty判断语句，对其进行判断，未清空前输出true，清空后输出false。
第4步，实现求栈长度的操作，例如本题输入元素5、7、9执行出栈操作后删除栈顶元素9，输出长度为2。
第5步，实现返回栈顶元素操作，本题输入元素5、7、9依次进栈顺序为9、7、5，然后执行返回栈顶语句，返回栈顶元素9。
第6步，实现入栈操作，例如本题输入元素5、7、9后依次入栈，为9、7、5。
第7步，实现出栈操作，本题中当执行返回栈顶元素9后，只剩下元素7、5，然后依次出栈。
第8步，实现栈的遍历操作输出栈的每一个元素，此题输出为9、7。
第9步，将上述功能作为类的成员函数实现，编写主函数测试上述功能。
3类设计
从上面的算法分析可以看到，本设计面临的主要问题是将这些要求作为类的成员函数，可以定义一个类stack,然后将这些要求作为该类的成员函数，该类主要分为公有变量和私有变量两部分，执行过程主要是公有变量里面的八个成员函数，然后分别利用主函数里面的函数分别对他们依次调用，完成对类的操作。
类公有变量及私有变量相互关系如图1所示。
图1stack类和公有变量及私有变量UML图形表示
4基于控制台的应用程序
整个程序首先定义了一个类stack，然后在公有变量中分别定义九个成员函数，首先是建立一个空栈stack，随后实现清空栈操作，即执行voidclear（），后判断栈是否为空，执行boolempty（）函数，然后是求栈长度，执行size（）函数，在返回栈顶元素，执行thetop（）const，后分别是实现入栈及出栈操作，最后实现栈的遍历，输出栈的每一个元素，在私有变量中主要是对栈的检验，main函数为程序的主函数，通过调用成员函数些实现程序的运行。
4.1类的接口设计
//Linequ.h文件，实现类的声明
#include
usingstd:
:
cout;
usingstd:
:
endl;
template
structnode{
_Thvalue;node<_Th>*next;
node（const_Th&data=_Th（）,node<_Th>*link=0）:
value（data）,next（link）{}};
template
classstack{
public:
stack（）{header=newnode<_Th>（_Th（）,0）;}
voidclear（）{while（!
empty（））pop（）;}
boolempty（）const{return!
header->next;}
unsignedintsize（）const{unsignedints=0;
for（node<_Th>*cur=header;cur->next;cur=cur->next）
++s;
returns;}
_Thtop（）const{
check_for_validity（）;
returnheader->value;}
voidpush（const_Th&element）{
node<_Th>*new_node=create_node（element,header）;
header=new_node;
}
voidpop（）{
if（empty（））return;
node<_Th>*peek=header;
header=header->next;
deletepeek;
}
voidprint_all（）const{
for（node<_Th>*cur=header;cur->next;cur=cur->next）
cout<value<<"";cout<}
private:
node<_Th>*header;
template
staticnode<_Th>*create_node（const_Type&value,node<_Th>*n）{
returnnewnode<_Th>（value,n）;
}
voidcheck_for_validity（）const{
if（empty（））throw0;//shouldthrowsomethingmoremeaningful
}
};
在开头的程序中定义一个结构体，然后定义了类stack，公有变量中包含了全部的成员函数，并且基类继承来的成员全部可以访问，而类中的私有变量时不可访问的。
4.2类的实现
//Linequ.cpp文件，类实现
#include"linequ.h"//包含类的声明头文件
//stack类的实现
stack（）{header=newnode<_Th>（_Th（）,0）;}
voidclear（）{while（!
empty（））pop（）;}
boolempty（）const{return!
header->next;}
unsignedintsize（）const{unsignedints=0;
for（node<_Th>*cur=header;cur->next;cur=cur->next）
++s;
returns;}
_Thtop（）const{
check_for_validity（）;
returnheader->value;}
voidpush（const_Th&element）{
node<_Th>*new_node=create_node（element,header）;
header=new_node;
}
voidpop（）{
if（empty（））return;
node<_Th>*peek=header;
header=header->next;
deletepeek;
}
voidprint_all（）const{
for（node<_Th>*cur=header;cur->next;cur=cur->next）
cout<value<<"";cout<在类的成员函数实现过程中，因为无外部接口，所以主要是在基类内部实现，通过主函数调用调用基类中的成员函数依次完成操作。
首先是建立一个空栈，在主函数中输入了3个元素为5、7、9，然后实现清空栈操作，在判断栈是否为空，因为输入了元素，所以输出false，在求栈长度，求栈顶元素后，输出9，所以栈长度为2，在分别实现入栈以及出栈操作，实现栈的遍历，输出元素为7、5。
4.3主函数设计
//main.cpp主函数
#include"linequ.h"
intmain（）{
stacks;
s.push（5）;
s.push（7）;
s.push（9）;
s.print_all（）;
cout<<"top:
"<s.pop（）;
cout<<"top:
"<s.print_all（）;
cout<<"size:
"<cout<<"isempty:
"<<（s.empty（）?
"true":
"false"）<s.clear（）;
cout<<"isempty:
"<<（s.empty（）?
"true":
"false"）<return0;
}
在程序的主函数部分，分别定义了所要输入的元素为5、7、9，随后对这些元素依次进行操作，首先执行函数调用s.print_all（），输出所以元素为975，在执行s.pop（），取栈顶元素，输出9，在出栈输出为75，在求栈长度为2，在判断栈是否为空，因为有元素存在，输出false，在清空栈，清空后栈为空，输出true，完成操作。
4.4基于控制台的应用程序测试
下图为程序运行结果：
程序运行结果如图2所示
图2doc环境下的运行结果
从图中可以看出当输入元素579后，输出结果为975，取栈顶元素9，后出栈，输出栈顶元素7，依次出栈输出75，后判断栈是否为空，因为依然有元素存在，所以输出false，在执行清空栈操作，判断是否为空，所以输出true，程序执行完后，可以看出是正确的。
5基于MFC的应用程序
MFC是microsoft基本类库。
该库的主要优点是效率较高，它减少了大量在建立windows程序时必须编写的代码。
同时它还提供了一般C++编程的优点。
MFC程序与DOS界面程序编写的最大不同是程序员需要将编程精力放在图形界面设计、图形界面输入输出以及界面元素和代码对应转换等问题上，而这些问题在DOS界面程序中是不存在的。
MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面所设计的栈类模板的设计，并通过图形界面的输入输出改造来完成。
5.1基于MFC的应用程序设计
5.1.1MFC程序界面设计
首先在VC中建立MFCAppWizard（exe）工程，名称为stack，并在向导的Step1中选择Dialogbased，即建立基于对话框的应用程序，如下图4~5所示。
图4建立MFCAppWizard（exe）工程
图5建立基于对话框的应用程序
将对话框资源中的默认对话框利用工具箱改造成如下界面，如图6所示。
图6方程组求解程序界面设计
图6所示的界面中包含了3个StaticText控件，5个Button控件，和5个EditBox控件，控件的基本信息列表如下表1所示。
表1控件基本信息
控件类别
控件ID
控件Caption
说明
StaticText
IDC_STATIC
控制
结果
输入
Botton
IDC_BUTTON_e1
清空栈
IDC_BUTTON_e2
判断栈空
IDC_BUTTON_e3
求栈长
IDC_BUTTON_e4
输出
IDC_BUTTON_e5
返回栈顶元素
IDC_BUTTON_e6
退出操作
EditBox
IDC_EDIT_l1
输入元素
IDC_EDIT_l2
输出栈是否为空
IDC_EDIT_l3
输出栈长
IDC_EDIT_l4
出栈
IDC_EDIT_l5
返回栈顶元素
5.1.2MFC程序代码设计
为了能够将对话框界面上的控件能够与代码联系起来，需要为5个EditBox控件建立MemberVariables，按Ctrl+w键进入MFCClassWizard界面，选择MemberVariables选项卡，可显示成员变量设置界面，如图7所示。
图7成员变量设置界面
通过该界面设置与5个EditBox控件对应的成员变量，具体如表2所示。
表2控件基本信息
控件ID
成员变量类型
成员变量名称
IDC_EDIT_l1
Int
m_l1
IDC_EDIT_l2
Cstring
m_l2
IDC_EDIT_l3
Int
m_l3
IDC_EDIT_l4
Int
m_l4
IDC_EDIT_l5
Int
m_l5
下面是编写代码的重要阶段，可以借鉴在设计基于DOS界面的控制台应用程序的代码，并将其作必要的改写，具体改写的步骤与内容如下。
①将类stack仍然叫stack，将其加入MFC工程。
②修改stack文件具体包括：
●将显示入栈voidpush（）const{return!
header->next;}函数和建立一个空栈stack（）{header=newnode<_Th>（_Th（）,0）;}函数注释掉，因为在图形界面的程序上已经不需要连个函数承担输出功能了；
●将输出栈voidpop（）函数加入参数intm_l1变成voidpop（intm_l1），以实现将所求结果显示在对话框中，并最终完成在对话框界面上的显示；
③在对话框类的实现文件123.cpp中加入#include".h"，以实现在该文件中可使用stack类。
④具体编写代码如下：
实现清空栈操作
voidCMy12315Dlg:
:
OnButton1（）
{
UpdateData（true）;
voidclear
clearm_l1;
UpdateData（false）;
⑤判断栈空操作
voidCMy12315Dlg:
:
OnButton2（）
{//TODO:
Addyourcontrolnotificationhandlercodehere
UpdateData（true）;
if（m_l1=NULL||m_l1==0）
m_l2="null";
else
m_l2="notnull";
UpdateData（false）;
}
⑥实现求栈u长度的操作，具体代码如下：
voidCMy12315Dlg:
:
OnButton3（）
{
UpdateData（true）;
m_l1=（char）（m_l1）;
m_l3=strlen（m_l1）;
UpdateData（false）;//TODO:
Addyourcontrolnotificationhandlercodehere
}
⑦输出栈的操作，代码如下：
voidCMy12315Dlg:
:
OnButton4（）
{UpdateData（true）;
voidpop（）;
m_l4=pop（intm_l1）;//TODO:
Addyourcontrolnotificationhandlercodehere
UpdateData（false）;
⑧返回栈顶元素，代码如下
voidCMy12315Dlg:
:
OnButton5（）
{
UpdateData（true）;
Thetop（）const
check_for_validity（）;
m_l5=m_l1->header;
returnheader->value;
UpdateData（false）;
}
⑨退出按钮比较简单，代码如下：
voidCMy12315Dlg:
:
OnButton6（）
{
//TODO:
Addyourcontrolnotificationhandlercodehere
OnOK（）;
}
5.2基于MFC的应用程序测试
运行程序后，首先出现的界面如图8所示。
图8程序初始运行界面
单击读入数据按钮后，可将系数矩阵A和方程组右端项b的数据在界面上显示出来，如图9所示。
图9读入数据后的界面
单击计算求解按钮，实现求解并将解显示出来，如图10所示。
图10输出后的界面
单击退出按钮后，程序能够正常实现退出。
结论
本次课程设计论文主要分为五部分，第一部分主要介绍了类模板的需求。
第二部分介绍了算法的基本原理，第三部分主要是类设计，介绍了类的基本结构，第四部分是基于控制台的应用程序，第五部分是基于MFC的应用程序设计。
整个程序中的栈类模板是通过定义普通类实现的，在程序开始定义一个结构体，然后定义类整个程序的要求是将所有的功能作为类的成员函数，，数据成员可以是、多种数据类型，在类里分别定义了公有变量和私有变量，在公有变量中定义了八个成员函数，分别为实现初始化操作，建立一个空栈，实现清空栈操作，判断栈是否为空操作，实现求栈长度，实现返回栈顶元素操作，实现入栈操作，实现出栈操作，实现栈的遍历操作，输出栈的每一个元素，通过对这些成员函数的定义，使类更加的具体化，特殊化达到了对问题的有效描述和处理，程序的问题访问也是根据问题需要而设计的，私有变量的数据成员维护着数据的正确性，在主函数中，先是分别定义了一组数据，然后在定义了调用函数，通过这些函数的定义，使程序更加的清晰，易懂，从而理解的更加透彻，而公有变量中的所有成员函数都可以被主函数调用，使程序的执行更加的简洁，通过主函数，公有变量和私有变量的相互作用，共同实现所有的功能。
在进行设计MFC程序时，由于MFC程序与DOS界面程序编写的不同，需要知道图形界面设计，图形界面输入输出以及界面元素和代码对应转换等问题，而这些问题在DOS界面程序中是不存在的。
本次设计MFC程序是编写windows程序的初步尝试，能够实现程序的主要功能。
编写的MFC程序虽然能实现所需功能，但是从面向对象程序设计理念和图形界面设计要求来说，还存在不足之处，主要为以下几点：
（1）设计完成MFC程序后需要改动源代码时不容易找到原程序，需要建立文件便于查找。
（2）效率不高，有太多成员变量和成员函数，功能相同可以合并或删除。
参考文献
[1]谭浩强著.C++面向对象程序设计.北京，清华大学出版社，2005
[2]李晓燕，数据结构初步。
北京：
中国财政出版社。
1996
[3]李庆扬,王能超,易大义.数值分析.湖北:
华中理工大学出版社,1986:
55-72
[4]Decoder编著.C/C++程序设计.北京：
中国铁道出版社，2002
[5]蔡子经，施伯乐.数据结构教程.上海：
复旦大学出版社，1994
[6]殷人昆,数据结构（用面向对象方法与C++描述）.北京：
清华大学出版社,1997
[7]唐策善，李龙激，黄刘生，数据结构————用C++语言描述。
北京：
高等教育出版社。
1995
[8]陈志泊,王春玲.面向对象的程序设计语言—C++.北京:
人民邮电出版社,2002:
115-130
升级会员 