数据结构实验报告Word文件下载.docx
- 文档编号:7401426
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:36
- 大小:327.66KB
数据结构实验报告Word文件下载.docx
《数据结构实验报告Word文件下载.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告Word文件下载.docx(36页珍藏版)》请在冰点文库上搜索。
操作结果:
构造一个空栈s。
Push(&
S,e)
初始条件:
栈s已存在。
操作结果:
插入元素e为新的栈顶元素。
Pop(SqStack&
初始操作:
栈s已存在且非空。
删除s的栈顶元素,并用e返回其值。
StackEmpty(SqStackS)
初始条件:
若栈为空则返回1,否则返回0。
}ADTStack
2、主程序的流程以及各程序模块之间的层次调用关系
见(三、详细设计3、流程图)↓
三、详细设计
1、数据类型
//=====ADTStack的表示与实现=====//
//-----数制转换-----//
#defineSTACK_INIT_SIZE100//存储空间初始分配量
#defineSTACKINCREMENT10//存储空间分配增量
typedefstruct{
int*base;
int*top;
intstacksize;
}SqStack;
//-----基本操作的函数原型说明-----//
voidInitStack(SqStack&
//构造一个空栈s
voidPush(SqStack&
S,inte)
//插入e为新的栈顶元素
intPop(SqStack&
//删除s的栈顶元素,并用e返回其值
intStackEmpty(SqStackS)
//若栈为空则返回1,否则返回0
voidconversion(intn,intf)
//对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数
2、伪码算法
//-----基本操作的算法描述-----//
S){
//构造一个空栈s
S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
if(!
S.base)exit(-2);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}//InitStack
S,inte){
//插入元素e为新的栈顶元素
if(S.top-S.base>
=S.stacksize){
S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
}//Push
//删除s的栈顶元素,并用e返回其值
inte;
if(S.top==S.base)return0;
e=*--S.top;
returne;
}//Pop
intStackEmpty(SqStackS){
//若栈为空则返回1,否则返回0
if(S.top==S.base)return1;
elsereturn0;
}//StackEmpty
//对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数
voidconversion(intn,intf){
InitStack(S);
while(n){
Push(S,n%f);
n=n/f;
while(!
StackEmpty(S)){
Pop(S,e)
printf("
%d"
e);
}//conversion
3、流程图
Y
N
Y
N
Y
YN
N
4、调试分析
(1)调试过程中遇到的问题和解决方法
在调试过程中主要遇到一些符号打错或输出、输出和函数之类的名称打错或漏打,根据第一行提示的错误然后进行修改,修改之后再运行调试,如此循环,直到彻底正常运行,后面就是优化见面的问题了。
(2)算法的时空分析和改进设想
算法时间复杂度:
f(n)
改进设想:
可在输出时将>
10的数字用A-Z输出。
(3)经验和体会等
从这是实验当中,我体会最深的是编程要特别仔细,因为稍不注意就可能打错字母,这些错误有时在调试当中特别难找,就是一个小小的字母可能也要让你花上好长时间来修改,还有就是要形成自己的编程风格,这样的代码看起来不至于那么乱,给有人条理的感觉,也便于代码的维护。
5、用户使用说明
运行输入n和f(n和f均大于0)n和f正确输入,然后打印输出n转换成f进制后的数值输入q(输入q=(y||Y)则继续转换,否则结束)结束。
6、测试结果
7、附录
(1)带注释的源程序
#include<
stdio.h>
stdlib.h>
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
int*base;
int*top;
intstacksize;
//构造一个空栈
S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
if(!
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
//插入e为新的栈顶元素
if(S.top-S.base>
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
*S.top++=e;
//删除s的栈顶元素,并用e返回其值
inte;
if(S.top==S.base)return0;
e=*--S.top;
returne;
//若栈为空则返回1,否则返回0
if(S.top==S.base)return1;
elsereturn0;
SqStackS;
InitStack(S);
while(n){
Push(S,n%f);
n=n/f;
while(!
switch(e=Pop(S)){
case10:
printf("
A"
);
break;
case11:
B"
case12:
C"
case13:
D"
case14:
E"
case15:
F"
default:
\n\n"
//操作,输入要转换的十进制数与要转换成的进制位
voidOperate(){
intn,f;
charq='
y'
;
while(q=='
||q=='
Y'
){
请输入要转换的十进制数值:
"
scanf("
&
n);
\n请输入要转换成的进制位:
f);
\n%d转换成%d进制数:
n,f);
if(n>
0){
if(f>
conversion(n,f);
}else
请输入正确的进制位!
}else{
要换转的十进制数错误。
是否继续?
(y/n):
%s"
q);
\n"
//标题
voidtitle(){
\t\t\t***************************\n"
\t\t\t*\t数制转换\t*\n"
intmain(){
title();
Operate();
(2)程序文件名的清单
数制转换.cpp
第二章一元多项式
choose、m(非零项个数)和expn(指数)的输入形式均为int型,coef(系数)的输入形式为float型,choose的输入值为1、2和0,m和expn的输入范围均为1~32767,coef的输入范围为±
3.4E38。
例:
3.00X^8+8.00X^7-5.00X^5+1.00X^2-2.35X^1
任务:
能够按照指数降序排列建立并输出多项式。
能够完成两个多项式的相加、相减,并将结果输入。
4、测试数据
一元多项式
运算
结果
-x2+x3
+
2x2+3x3+4x5
4x5+4x3+1x2
x3-2x4+5.2x
x2–5x4+3.2x
-7x4+1x3+1x2+8.4x1
-2x2+3x3+4x4
-
x–x2+4x3+x4
3x4-1x3-1x2-x1
ADTPolynomial{
CreatPolyn(&
P,m)
输入m项的系数和指数,建立一个一元多项式p
DestroyPolyn(&
P)
一元多项式P已存在。
销毁一元多项式P。
PrintPolyn(P)
打印输出一元多项式P。
AddPolyn(&
Pa,&
Pb)
一元多项式Pa和Pb已存在。
多项式加法:
Pa=Pa+Pb,并销毁一元多项式Pb
SubtractPolyn(&
多项式减法:
Pa=Pa-Pb,并销毁一元多项式Pb
}ADTPolynomial
//=====ADTPolynomial的表示与实现=====//
//-----一元多项式-----//
typedefstruct{//项的表示,多项式的项作为LinkList的数据元素
floatcoef;
//系数
intexpn;
//指数
}term,ElemType;
//term用于本ADT,ElemType用于LinkList的数据对象名
typedefLinkListpolynomial;
//用带表头结点的有序链表表示多项式
//-----基本操作的函数原型说明-----//
voidCreatPolyn(polynomial&
P,intm)
//输入m项的系数和指数,建立表示一元多项式的有序链表p
intDestroyPolyn(polynomialp)
//销毁一元多项式p
voidPrintPolyn(polynomialP)
//打印输出一元多项式p
voidAddPolyn(polynomial*Pa,polynomial*Pb)
//多项式加法:
voidSubtractPolyn(polynomial*Pa,polynomial*Pb)
//多项式减法:
Pa=Pa-Pb,并销毁一元多项式Pb
2、伪码算法
//-----基本操作的算法描述(部分重要操作)-----//
intcmp(terma,termb){
/依a的指数值<
(或=)(或>
)b的指数值,分别返回-1,0,和+1
}//cmp
P,intm){
InitList(P);
h=GetHead(P);
e.coef=0.0;
e.expn=-1;
SetCurElem(h,e);
//设置头结点的数据元素
printf("
系数指数\n"
for(i=1;
i<
=m;
++i){//一次输入m个非零项
scanf(e.coef,e.expn);
if(!
LocateElemP(P,e,&
q,cmp)){//当前链表中不存在该指数项
if(MakeNode(&
s,e))
InsFirst(&
P,q,s);
//生成结点并插入链表
}//if
}//for
}//CreatPolyn
voidAddPolyn(polynomial*Pa,polynomial*Pb){
//多项式加法:
ha=GetHead(*Pa);
hb=GetHead(*Pb);
//ha和hb分别指向Pa和Pb地头结点
qa=NextPos(ha);
qb=NextPos(hb);
//qa和qb分别指向Pa和Pb中当前结点(现为第一个结点)
ListEmpty(*Pa)&
&
!
ListEmpty(*Pb)&
qa){
//Pa和Pb均非空且ha没指向尾结点(qa!
=0)
a=GetCurElem(qa);
b=GetCurElem(qb);
//a和b为两表中当前比较元素
switch(cmp(a,b)){
case-1:
//多项式Pa中当前结点地指数值小
ha=qa;
qa=NextPos(ha);
//ha和qa均向后移一个结点
break;
case0:
//两者地指数值相等
sum=a.coef+b.coef;
//修改Pa当前结点地系数值
if(sum!
=0.0){
SetCurElem(qa,sum);
ha=qa;
}else{//删除多项式Pa中当前结点
DelFirst(Pa,ha,&
qa);
FreeNode(&
}
DelFirst(Pb,hb,&
qb);
qb=NextPos(hb);
qa=NextPos(ha);
case1:
//多项式Pb中当前结点地指数值小
InsFirst(Pa,ha,qb);
ha=NextPos(ha);
}//switch
}//while
ListEmpty(*Pb)){
Append(Pa,qb);
//链接Pb中剩余结点
FreeNode(&
hb);
//释放Pb头结点
}//if
DestroyPolyn(Pb);
//销毁Pb
}//AddPolyn
voidOpposite(polynomialPa){
//一元多项式系数取反
p=Pa.head;
while(p->
next){
//为一元多项式减法做准备,将系数全部取反,然后执行一元多项式的加法。
p=p->
next;
p->
data.coef*=-1;
}//Opposite
voidSubtractPolyn(polynomial*Pa,polynomial*Pb){
Opposite(*Pb);
//先为一元多项式Pb系数全部取反
AddPolyn(Pa,Pb);
//执行一元多项式的加法,取反后相当于减法。
}//SubtractPolyn
voidSort(polynomialP){
//将链表升序排序转换成降序排序
tailNode=P.tail;
//tailNode标记P链表的尾结点
while(P.head->
next!
=tailNode){
//当P的头结点下一个结点(第一个元素从是头结点的下一个元素)不等//于尾结点时执行
curNode=P.head->
while(curNode!
=tailNode){//
if(curNode->
data.expn<
curNode->
next->
data.expn){
//当当前元素的指数小于下一个元素的指数时执行交换
e=curNode->
data;
curNode->
data=curNode->
data=e;
}//if
newNode=curNode;
//while循环到最后时newNode指向tailNode的前一个结点
curNode=curNode->
//将eNode结点下移
}//while
tailNode=newNode;
//将tailNode结点前移(此时最大的指数已经移到尾结点)
}//Sort
0
1、2
(输入第二个一元多项式)2
N1
(第1次N执行输入m)
Y
N-1
-2
YY
(2)改进设想
增加两个一元多项式的乘法和除法操作,简化代码,减少时间和空间复杂度。
从这是实验当中,我体会最深的是编程要特别仔细,因为稍不注意就可能打错字母,这些错误有时在调试当中特别难找,就是一个小小的字母可能也要让你花上好长时间来修改,还有就是要形成自己的编程风格,这样的代码看起来不至于那么乱,给有人条理的感觉,也便于代码的维护,还有就是函数调用的问题,函数调用多了容易出现错误,函数写多了也容易忘记,这就要求程序员有良好的注释习惯。
运行选择操作(1,2,0)输入第一个一元多项式非零项的个数m输入第一个一元多项式的系数和项数(系数项数)输入第一个二元多项式非零项的个数m输入第二个一元多项式的系数和项数(系数项数)打印输出运算后的一元多项式输入f若f==’y’||f==’Y’则继续选择操作否则结束程序。
#defineDestroyPolynDestroyList
#definePolynLengthListLength
floatcoef;
typedefstructLNode{//结点类型
ElemTypedata;
structLNode*next;
}*Link,*Position;
typedefstruct_LinkList{//链表类型
Linkhead,tail;
//head指向头结点,tail指向最后一个结点
intlen;
//指向线性链表中数据元素的个数
}LinkList;
//依a的指数值<
if(a.expn==b.expn)
return
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告