数据结构课程设计报告40887.docx
《数据结构课程设计报告40887.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告40887.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告40887
安徽工业大学
数据结构课程设计
指导老师：
陈学进
姓名：
陆俊贤
学号：
139074382
计算机学院
课题一：
进制转换
1·数据结构：
栈和队列；
2·算法：
将需要转换的数据分为两部分，整数部分和小数部分，将整数部分利用辗转相除法取得的余数存入栈中，将小数部分乘以进制取整后存入队列中，然后顺序出栈和出队列，输出转换后的数值，
3·程序源代码：
#include
usingnamespacestd;
typedefintdatatype;
classSeqstack
{
private:
datatype*base;
datatype*top;
intsize;
public:
Seqstack（intstacksize=100）
{
base=newdatatype[stacksize];
top=base;
size=stacksize;
};
intEmpty_stack（）;
intPush_stack（datatypee）;
intPop_stack（datatype&e）;
};
classSeqQueue
{
private:
datatype*base;
intfront,rear;
intsize;
public:
SeqQueue（intQueuesize=100）
{
base=newdatatype[Queuesize];
front=rear=0;
size=Queuesize;
};
intEmpty_Queue（）;
intIn_Queue（datatypee）;
intOut_Queue（datatype&e）;
};
intSeqstack:
:
Empty_stack（）
{
returntop<=base;
}
intSeqstack:
:
Push_stack（datatypee）
{
if（top-base{
*top=e;
top++;
return1;
}
else
return0;
}
intSeqstack:
:
Pop_stack（datatype&e）
{
if（top>base）
{
top--;
e=*top;
return1;
}
else
return0;
}
intSeqQueue:
:
Empty_Queue（）
{
returnfront==rear;
}
intSeqQueue:
:
In_Queue（datatypee）
{
if（（rear+1）%size!
=front）
{
rear=（rear+1）%size;
base[rear]=e;
return1;
}
else
return0;
}
intSeqQueue:
:
Out_Queue（datatype&e）
{
if（rear!
=front）
{
front=（front+1）%size;
e=base[front];
return1;
}
else
return0;
}
voidCalculate1（intNum,intr）;
voidCalculate2（doubleNum,intr）;
intmain（）
{
intr;
doubleNum;
cout<<"请输入一个任意十进制数（输入0结束）:
"<while
（1）
{
cin>>Num;
if（Num==0）
return0;
cout<<"请输入转换进制:
"<cin>>r;
cout<<"转换后的数为:
"<if（Num<0）
{
Num=-Num;
cout<<"-";
}
Calculate1（（int）Num,r）;
if（Num-（int）Num）
{
Calculate2（Num-（int）Num,r）;
}
else
cout<cout<<"请输入一个任意十进制数（输入0结束）:
"<}
return0;
}
voidCalculate1（intNum,intr）
{
Seqstacks;
inte;
charch;
while（Num）
{
e=Num%r;
Num=Num/r;
s.Push_stack（e）;
}
while（!
s.Empty_stack（））
{
s.Pop_stack（e）;
if（e>=0&&e<10）
cout<else
{
ch=e+55;
cout<}
}
}
voidCalculate2（doubleNum,intr）
{
if（Num!
=0）
{
cout<<".";
inte;
charch;
SeqQueueq;
while（Num>0.001）
{
Num=Num*r;
e=（int）Num;
Num-=e;
q.In_Queue（e）;
}
while（!
q.Empty_Queue（））
{
q.Out_Queue（e）;
if（e<10&&e>-1）
cout<else
{
ch=e+55;
cout<}
}
cout<}
}
4·测试数据与调试
请输入一个任意十进制数（输入0结束）:
20.3
请输入转换进制:
2
转换后的数为:
1.010*********
请输入一个任意十进制数（输入0结束）:
98.5
请输入转换进制:
16
转换后的数为:
62.8
请输入一个任意十进制数（输入0结束）:
65.3
请输入转换进制:
16
转换后的数为:
41.4CCCCCCCCCCC
课题二·一元多项式的计算
1·数据结构
顺序表
2·算法
将从设备中接收的字符串按照一元多项式的书写规则写入顺序表中，然后将两个顺序表按照用户要求的运算规则（加、减、乘）将运算结果存入顺序表中并输出。
3·程序源代码
#include
#include
usingnamespacestd;
#definemaxsize100
typedefintdatatype;
classa
{
public:
intxishu;
intcishu;
charch;
charsign;
};
classSeqlist
{
public:
aItem[maxsize];
intlen;
Seqlist（）
{len=0;}
voidInitiate（）;
voidOutput（）;
voidSort（）;
friendvoidCalculate1（Seqlist&l1,Seqlist&l2）;
friendvoidCalculate2（Seqlist&l1,Seqlist&l2）;
friendvoidCalculate3（Seqlist&l1,Seqlist&l2,Seqlist&l3）;
};
voidAdd（Seqlist&l3,a&l_flag）;
intmain（）
{
Seqlistl1,l2,l3;
charch;
cout<<"请输入第一个一元多项式:
"<l1.Initiate（）;
cout<"<cin>>ch;
cout<"<l2.Initiate（）;
cout<"<switch（ch）
{
case'+':
Calculate1（l1,l2）;
break;
case'-':
Calculate2（l1,l2）;
break;
case'*':
Calculate3（l1,l2,l3）;
break;
}
cout<return0;
}
voidSeqlist:
:
Initiate（）
{
chara[100];
inti=0,j=0,str_len;
cin>>a;
str_len=strlen（a）;
while（i{
Item[j].xishu=0;
if（i==0）
{
if（a[i]=='-'）
{
Item[j].sign='-';
i++;
}
if（a[i]>='a'&&a[i]<='z'）
{
Item[j].ch=a[i];
Item[j].xishu=1;
i++;
}
if（a[i]>'0'&&a[i]<='9'）
{
while
（1）
{
if（a[i]>'0'&&a[i]<='9'）
{
Item[j].xishu=a[i]-'0'+Item[j].xishu*10;
i++;
}
else
break;
}
Item[j].ch=a[i];
i++;
}
if（a[i]!
='^'）
{
i--;
Item[j].cishu=1;
}
else
{
i++;
Item[j].cishu=a[i]-'0';
i++;
}
j++;
}
else
{
Item[j].xishu=0;
Item[j].sign=a[i];
i++;
if（a[i]>='a'&&a[i]<='z'）
{
Item[j].ch=a[i];
Item[j].xishu=1;
i++;
}
elseif（a[i]>'0'&&a[i]<='9'）
{
while
（1）
{
if（a[i]>'0'&&a[i]<='9'）
{
Item[j].xishu=a[i]-'0'+Item[j].xishu*10;
i++;
}
else
break;
}
Item[j].ch=a[i];
i++;
}
if（a[i]!
='^'）
{
i--;
Item[j].cishu=1;
}
else
{
i++;
Item[j].cishu=a[i]-'0';
i++;
}
j++;
}
}
len=j;
for（i=0;i{
if（Item[i].sign=='-'）
{
Item[i].xishu=-Item[i].xishu;
}
}
}
voidSeqlist:
:
Output（）
{
inti=0;
for（i=0;i{
if（i>0）
{
if（Item[i].xishu<0&&Item[i].xishu!
=-1）
cout<if（Item[i].xishu>1）
cout<<'+'<if（Item[i].xishu==-1）
cout<<'-';
if（Item[i].xishu==1）
cout<<'+';
cout<if（Item[i].cishu!
=1）
cout<<'^'<}
else
{
if（Item[i].xishu==-1）
cout<<'-';
if（Item[i].xishu!
=1&&Item[i].xishu!
=-1）
cout<cout<if（Item[i].cishu>1）
cout<<'^'<}
}
}
voidCalculate1（Seqlist&l1,Seqlist&l2）
{
cout<<'（';
l1.Output（）;
cout<<"）+";
cout<<'（';
l1.Output（）;
cout<<"）";
cout<<"=";
inti,j,flag=0;
for（j=0;j{
flag=0;
for（i=0;i{
if（l2.Item[j].cishu==l1.Item[i].cishu）
{
l1.Item[i].xishu+=l2.Item[j].xishu;
flag=1;
break;
}
}
if（flag==0）
{
l1.Item[l1.len]=l2.Item[j];
l1.len++;
}
}
l1.Sort（）;
l1.Output（）;
}
voidCalculate2（Seqlist&l1,Seqlist&l2）
{
cout<<'（';
l1.Output（）;
cout<<"）-";
cout<<'（';
l1.Output（）;
cout<<"）";
cout<<"=";
inti,j,flag=0;
for（j=0;j{
flag=0;
for（i=0;i{
if（l2.Item[j].cishu==l1.Item[i].cishu）
{
l1.Item[i].xishu-=l2.Item[j].xishu;
flag=1;
break;
}
}
if（flag==0）
{
l1.Item[l1.len]=l2.Item[j];
l1.len++;
}
}
l1.Sort（）;
l1.Output（）;
}
voidSeqlist:
:
Sort（）
{
inti,j;
al_e;
for（i=0;ifor（j=0;jif（Item[j].cishu{
l_e=Item[j];
Item[j]=Item[j+1];
Item[j+1]=l_e;
}
}
voidCalculate3（Seqlist&l1,Seqlist&l2,Seqlist&l3）
{
cout<<'（';
l1.Output（）;
cout<<"）*";
cout<<'（';
l1.Output（）;
cout<<"）";
cout<<"=";
al_flag;
inti,j;
for（i=0;i{
for（j=0;j{
l_flag.xishu=l1.Item[i].xishu*l2.Item[j].xishu;
l_flag.cishu=l1.Item[i].cishu+l2.Item[j].cishu;
l_flag.ch=l1.Item[i].ch;
Add（l3,l_flag）;
}
}
l3.Sort（）;
l3.Output（）;
}
voidAdd（Seqlist&l3,a&l_flag）
{
inti;
intflag=0;
for（i=0;iif（l_flag.cishu==l3.Item[i].cishu）
{
l3.Item[i].xishu+=l_flag.xishu;
flag=1;
}
if（flag==0）
{
l3.Item[l3.len]=l_flag;
l3.len++;
}
}
4·测试数据与调试
输入:
23x^2+6x^3+x^6
+
-21x^2+6x^3-81x^5
输出：
x^6-81x^5+12x^3+2x^2
输入:
3x^2+x^3
*
x^4+6x^5
输出:
6x^8+19x^7+3x^6
课题三·大数相乘
1·数据结构
线性表
2·算法
将从外接设备中接收的字符串存入整形线性表中，并且倒序存入，每个数组元素存一个，然后错位相乘，对应相加。
3·源程序代码
#include
#include
#include
usingnamespacestd;
typedefintdatatype;
#definemaxsize9999
classSeqlist
{
private:
datatypedata[maxsize];
intlen;
public:
Seqlist（）
{
len=0;
for（inti=0;idata[i]=0;
}
voidInitiate（）;
voidOutput（）;
voidReinitiate（）;
friendvoidCalculate（Seqlist&l1,Seqlist&l2,Seqlist&l3）;
};
intmain（）
{
Seqlistl1,l2,l3;
l1.Initiate（）;
l2.Initiate（）;
Calculate（l1,l2,l3）;
l1.Output（）;
cout<<'*';
l2.Output（）;
cout<<'=';
l3.Output（）;
cout<return0;
}
voidSeqlist:
:
Initiate（）
{
chara[maxsize];
intstr_len,i,j;
cin>>a;
str_len=strlen（a）;
for（i=str_len-1,j=0;i>=0;i--,j++）
{
data[j]=a[i]-'0';
len++;
}
}
voidSeqlist:
:
Output（）
{
inti;
for（i=maxsize-1;i>=0;i--）
{
if（data[i]!
=0）
cout<}
}
voidCalculate（Seqlist&l1,Seqlist&l2,Seqlist&l3）
{
inti,j,k;
intflag;
for（i=0;i{
for（j=0;j{
flag=l1.data[i]*l2.data[j];
l3.data[i+j]+=flag;
}
l3.len=i+j;
}
l3.Reinitiate（）;
}
voidSeqlist:
:
Reinitiate（）
{
for（inti=0;i{
if（data[i]>10）
{
data[i+1]+=data[i]/10;
data[i]=data[i]%10;
}
}
}
4·测试数据与调试
输入：
3652
3659
输出：
3652*3659=13362688
升级会员 