数据结构课程设计教学内容文档格式.docx
- 文档编号:5300465
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:23
- 大小:105.15KB
数据结构课程设计教学内容文档格式.docx
《数据结构课程设计教学内容文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计教学内容文档格式.docx(23页珍藏版)》请在冰点文库上搜索。
//Tball(){r=0;
x=0;
y=0;
z=0;
Tball(doublea,doubleb,doublec,doubled):
TPoint(a,b,c){r=d;
}//带参数的构造函数
Tball(TPoint&
pn):
TPoint(pn){r=1;
}
doubleA(){return4*PI*r*r;
}//计算球的面积
doubleV(){return4.0/3.0*PI*r*r*r;
}//计算球的体积
intPosition(TPoint&
pt);
//判断点pt相对于球的位置
voidJudge(TPoint&
voidShow();
//输出球的各属性值
intTball:
:
Position(TPoint&
pt)//求点pt相对于球的位置
{
doublet,s;
t=(pt.Getx()-x)*(pt.Getx()-x)+(pt.Gety()-y)*(pt.Gety()-y)+(pt.Getz()-z)*(pt.Getz()-z);
s=r*r;
if(t>
s)return1;
//点在球外
elseif(t<
s)return-1;
//点在球内
elsereturn0;
//点在球上
}
voidTball:
Judge(TPoint&
pt)
switch(Position(pt))
{
case-1:
cout<
<
"
此点在球内"
endl;
break;
case0:
此点在球面上"
case1:
点此在球外"
}
Show()//输出球的各属性值
{
cout<
x="
x<
'
\t'
y="
y<
z="
z<
;
球的半径="
r<
球的表面积="
A()<
球的体积="
V()<
voidmain()
intx,y,z,R,x0,y0,z0;
输入球心坐标(x,y,z),以及球的半径R"
cin>
>
x>
y>
z;
输入半径R:
R;
TballA(x,y,z,R);
//定义一个球类对象
A.Show();
//输出球的属性值
输入空间一点的坐标(x0,y0,z0)"
cin>
x0>
y0>
z0;
TPointp(x0,y0,z0);
//定义一个Point类对象
cout<
点和球的位置关系为:
"
A.Judge(p);
【实验过程】
【实验体会】本题要求学会用算法语言C++描述抽象数据类型,属于一道比较简单的题目,对继承又有了进一步的了解。
通过本题的训练,使C++面向对象的编程的基础知识得到了巩固和复习,对面向对象编程的思想有了更加深刻的认识,为以后更复杂的问题的解决奠定了必要的基础。
上机练习4将中缀表达式转换为后缀表达式
【问题描述】表达式转换。
输入的中缀表达式为字符串,转换得到的后缀表达式存入字符数组中并输出。
例如:
a*(x+y)/(b-x)转换后得:
axy+*bx-/
【数据结构】
●定义一个暂时存放运算符的转换工作栈opst。
●中缀表达式字符串char*infix;
●后缀表达式字符串char*postfix;
【算法提示】转换规则:
把运算符移到它的两个操作数后面,删除掉所有的括号。
从头到尾扫描中缀表达式,对不同类型的字符按不同情况处理:
●数字或小数点,直接写入字符串postfix,并在每个数值后面写入一个空格;
●左括号,进栈,直到遇见相配的右括号,才出栈;
●右括号,表明已扫描过括号内的中缀表达式,把从栈顶直到对应左括号之间的运算符依次退栈,并把结果推入栈内;
●对于运算符,分两种情况处理:
◆该运算符的优先级大于栈顶符号的优先级,则入栈;
◆若该运算符的优先级小于栈顶优先级,则先弹出栈顶运算符、写入postfix串;
继续将该运算符与栈顶运算符比较,直到能把它推入栈内为止(即优先级大于栈顶运算符)。
说明:
自行设计运算符优先级的表示。
assert.h>
iostream>
usingnamespacestd;
constintstackIncreament=20;
//栈溢出时扩展空间的增量
template<
classT>
classSeqStack//顺序栈的类定义
SeqStack(intsz=50);
//构造函数,建立一个空栈
~SeqStack(){delete[]elements;
}//析构函数
voidPush(constT&
x);
//如果IsFull(),则溢出处理;
否则把x插入到栈顶
boolPop(T&
//如果IsEmpty(),则不执行退栈,返回false;
否则退掉位于栈顶的元素,返回true
boolgetTop(T&
boolIsEmpty()const{return(top==-1)?
true:
false;
boolIsFull()const{return(top==maxSize-1)?
intgetSize()const{returntop+1;
}//函数返回栈中元素个数
voidMakeEmpty(){top=-1;
}//清空栈中的内容
friendostream&
operator<
(ostream&
os,SeqStack<
T>
&
s);
//输出栈中元素的重载操作<
private:
T*elements;
inttop;
intmaxSize;
voidoverflowProcess();
//栈的溢出处理
};
SeqStack<
SeqStack(intsz):
top(-1),maxSize(sz)//建立一个最大尺寸为sz的空栈,若分配不成功则错误处理
{
elements=newT[maxSize];
//创建栈的数组空间
assert(elements!
=NULL);
//断言:
动态存储分配是否成功
voidSeqStack<
overflowProcess()
T*newArray=newT[maxSize+stackIncreament];
if(newArray=NULL){cerr<
储存分配失败"
exit
(1);
for(inti=0;
i<
=top;
i++)newArray[i]=elements[i];
maxSize=maxSize+stackIncreament;
delete[]elements;
elements=newArray;
Push(constT&
x)//公共函数:
若栈不满,则将元素x插入到该栈的栈顶,否则溢出处理
if(top==maxSize-1)overflowProcess();
//栈满则溢出处理
elements[++top]=x;
//栈顶指针先加1再进栈
boolSeqStack<
Pop(T&
x)
if(top==-1)returnfalse;
x=elements[top--];
returntrue;
:
getTop(T&
x=elements[top];
ostream&
os,SeqStack<
s){
os<
top="
s.top<
//输出栈顶位置
for(inti=0;
=s.top;
i++)//逐个输出栈中元素的值
os<
s.elements[i]<
returnos;
intisdigit(charch)
switch(ch)
case'
+'
case'
-'
*'
/'
('
)'
return0;
break;
default:
return1;
intisp(charch)//栈中优先数
{case'
#'
return0;
return5;
%'
return3;
return6;
inticp(charch)//栈外优先数
return4;
return2;
voidpostfix(SeqStack<
char>
s){//定义栈的对象为s,其元素为字符
charch='
ch1,op;
s.Push(ch);
cin.get(ch);
//栈底放入一个#,读入一个字符
后缀表达式为:
while(s.IsEmpty()==false&
ch!
='
)//连续处理
if(isdigit(ch)){cout<
ch;
}//是操作数,输出之
else{
s.getTop(ch1);
//取栈顶操作符ch1
if(isp(ch1)<
icp(ch))//新输入操作符优先级高
{s.Push(ch);
}//进栈读入下一字符
elseif(isp(ch1)>
icp(ch))//新输入操作符优先级低
{s.Pop(op);
op;
}//退栈并输出
else{
s.Pop(op);
//输入操作符优先级等于栈顶优先级
if(op=='
)cin.get(ch);
}
}
s.Pop(op);
voidmain(){
infix;
//定义顺序栈的对象中缀表达式
输入中缀表达式,以#结束"
postfix(infix);
【实验体会】本题训练的是对栈这种数据结构的应用。
主要掌握的是栈这种数据结构的基本运算和对中缀转后缀的思想的理解。
即栈是先进后出的,然后就是栈外字符的优先级和栈顶字符的优先级的比较,这是该算法的主要思想。
其他就是面向对象编程的基本知识的应用。
上机练习5后缀表达式的计算
【实验目的】
通过上机实践使得学生进一步了解运算受限的线性表——栈的应用特点与使用方式。
掌握栈的类定义,实现栈的主要操作。
并能够应用该数据结构解决简单的应用问题。
模拟一个简单的计算器+、-、*、/等运算,求解输入的后缀表达式的值。
从左向右地扫描后缀表达式,并使用一个栈暂存扫描到的操作数和操作结果。
【实验要求】
1.定义SeqStack类或LinkedStack类,实现其主要成员函数;
定义Calculator类,
实现其成员函数。
2.输入一组后缀表达式,以“#”结束,计算其并验证其值。
例如输入后缀
表达式“56*205+-#”,输出结果:
5。
3.计算器要能够接收浮点数。
4.程序正确运行。
5.认真思考,独立上机实践。
【代码】
#include<
math.h>
stdlib.h>
constintstackIncreament=20;
template<
classSeqStack{//定义SeqStack类
public:
SeqStack(intsz=50);
~SeqStack(){delete[]elements;
voidPush(constT&
boolgetTop(T&
boolIsEmpty()const{return(top==-1)?
true:
boolIsFull()const{return(top==maxSize-1)?
voidmakeEmpty(){top=-1;
friendostream&
s);
private:
T*elements;
inttop;
intmaxSize;
voidoverflowProcess();
SeqStack(intsz){
top=-1;
maxSize=sz;
elements=newT[maxSize];
assert(elements!
overflowProcess(){
T*newArray=newT[maxSize+stackIncreament];
if(newArray=NULL){cerr<
maxSize=maxSize+stackIncreament;
delete[]elements;
elements=newArray;
Template<
x){
if(IsFull()==true)overflowProcess();
if(IsEmpty()==true)returnfalse;
top="
i++)
edl;
classCalculator{//定义Calculator类
Calculator(intsz):
s(sz){}
voidRun();
voidClear();
SeqStack<
double>
s;
voidAddOperand(doublevalue);
boolGet2Operands(double&
left,double&
rignt);
voidDoOperator(charop);
voidCalculator:
DoOperator(charop){
doubleleft,right,value;
boolresult;
result=Get2Operands(left,right);
if(result==true)
switch(op){
value=left+right;
s.Push(value);
case'
value=left-right;
value=left*right;
if(right==0.0){
cerr<
Divideby0!
Clear();
else{value=left/right;
break;
boolCalculator:
Get2Operands(double&
right){
if(s.IsEmpty()==true)
{cerr<
缺少右操作数!
returnfalse;
s.Pop(right);
缺少左操作数!
s.Pop(left);
AddOperand(doublevalue){
s.Push(value);
Run()
charch;
doublenewOperand;
while(cin>
ch,ch!
){
switch(ch){
DoOperator(ch);
break;
default:
cin.putback(ch);
cin>
newOperand;
AddOperand(newOperand);
}
doubleresult;
s.Pop(result);
运算结果为:
result;
Clear(){
s.makeEmpty();
请输入算式并以#结束"
Calculatora(100);
a.Run();
}
【输入、输出界面效果】
【上机总结】本题的解决用到了栈这种数据结构,基本思想是对于一个后缀表达式,应用栈先进后出的特点,先把一个后缀表达式压入栈中,对栈顶元素进行相应的运算,最后得到后缀表达式的结果。
本题还是属于比较简单的题目,对栈的认识会有很大的帮助。
7二叉树的操作
【实验简介】二叉树是树形结构的一种重要类型。
通过本次实验,熟悉二叉树结点的结构,掌握二叉树的基本操作以及具体实现,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
编写程序,实现对二叉树的以下操作:
1.建立二叉树。
2.按任一种遍历次序输出二叉树中的所有结点。
3.求二叉树的深度。
4.求二叉树中的所有节点数。
5.求二叉树中的所有叶子节点数。
6.清除二叉树,使之变成一只空树。
structBinTreeNode//二叉树结点类定义
{Tdata;
//数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 教学内容