数据结构实习报告

数据结构实习报告本文简介：数据结构实习报告姓名：学号：班级：一、一元多项式计算1、题目要求：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减和相乘，并将结果输出。2、程序代码：#include#includetypedefstructPolynomial{floatcoef;intexpn;structP

数据结构实习报告本文内容：

数据结构实习报告

姓

名：

学

号：

班

级：

一、一元多项式计算

1、题目要求：

能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减和相乘，并将结果输出。

2、程序代码：

#include

#include

typedef

struct

Polynomial{

float

coef;

int

expn;

struct

Polynomialnext;

}*Polyn,Polynomial;

//Polyn为结点指针类型

void

Insert(Polyn

p,Polyn

h){

if(p->coef==0)

free(p);

//系数为0的话释放结点

else{

Polyn

q1,q2;

q1=h;q2=h->next;

while(q2

q2=q2->next;

}

if(q2

free(p);

if(!q2->coef){

//系数为0的话释放结点

q1->next=q2->next;

free(q2);

}

}

else{

//指数为新时将结点插入

p->next=q2;

q1->next=p;

}

}

}

//Insert

Polyn

CreatePolyn(Polyn

head,int

m){

//建立一个头指针为head、项数为m的一元多项式

int

i;

Polyn

p;

p=head=(Polyn)malloc(sizeof(struct

Polynomial));

head->next=NULL;

for(i=0;icoef,Insert(p,head);

//调用Insert函数插入结点

}

return

head;

}//CreatePolyn

void

DestroyPolyn(Polyn

p){//销毁多项式p

Polyn

q1,q2;

q1=p->next;

q2=q1->next;

while(q1->next){

free(q1);

q1=q2;

//指针后移

q2=q2->next;

}

}

void

PrintPolyn(Polyn

P){

Polyn

q=P->next;

int

flag=1;

//项数计数器

if(!q)

{

//若多项式为空，输出0

putchar(

0

);

printf(“\n“);

return;

}

while

(q){

if(q->coef>0

//系数大于0且不是第一项

if(q->coef!=1

if(q->expn==1)

putchar(

X

);

else

if(q->expn)

printf(“X^%d“,q->expn);

}

else{

if(q->coef==1){

if(!q->expn)

putchar(

1

);

else

if(q->expn==1)

putchar(

X

);

else

printf(“X^%d“,q->expn);

}

if(q->coef==-1){

if(!q->expn)

printf(“-1“);

else

if(q->expn==1)

printf(“-X“);

else

printf(“-X^%d“,q->expn);

}

}

q=q->next;

flag++;

}//while

printf(“\n“);

}

//PrintPolyn

int

compare(Polyn

a,Polyn

b){

if(a

else

if(!a||a->expnexpn)

return

-1;

else

return

0;

}

else

if(!a

//a多项式已空，但b多项式非空

else

return

1;

//b多项式已空，但a多项式非空

}

//compare

Polyn

AddPolyn(Polyn

pa,Polyn

pb){

//求解并建立多项式a+b，返回其头指针

Polyn

qa=pa->next;

Polyn

qb=pb->next;

Polyn

headc,hc,qc;

hc=(Polyn)malloc(sizeof(struct

Polynomial));//建立头结点

hc->next=NULL;

headc=hc;

while(qa||qb){

qc=(Polyn)malloc(sizeof(struct

Polynomial));

switch(compare(qa,qb)){

case

1:

{

qc->coef=qa->coef;

qc->expn=qa->expn;

qa=qa->next;

break;

}

case

0:

{

qc->coef=qa->coef+qb->coef;

qc->expn=qa->expn;

qa=qa->next;

qb=qb->next;

break;

}

case

-1:

{

qc->coef=qb->coef;

qc->expn=qb->expn;

qb=qb->next;

break;

}

}//switch

if(qc->coef!=0){

qc->next=hc->next;

hc->next=qc;

hc=qc;

}

else

free(qc);

//当相加系数为0时，释放该结点

}

//while

return

headc;

}

//AddPolyn

Polyn

SubtractPolyn(Polyn

pa,Polyn

pb){//求解并建立多项式a+b，返回其头指针

Polyn

h=pb;

Polyn

p=pb->next;

Polyn

pd;

while(p){

//将pb的系数取反

p->coef*=-1;

p=p->next;

}

pd=AddPolyn(pa,h);

for(p=h->next;p;p=p->next)

//恢复pb的系数

p->coef*=-1;

return

pd;

}

//SubtractPolyn

int

main(){

int

m,n,flag=0;

float

x;

Polyn

pa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULL

printf(“请输入a的项数:“);

scanf(“%d“,pa=CreatePolyn(pa,m);//建立多项式a

printf(“请输入b的项数:“);

scanf(“%d“,pb=CreatePolyn(pb,n);//建立多项式a

//输出菜单

printf(“**********************************************\n“);

printf(“操作提示：\n\t1.输出多项式a和b\n\t2.建立多项式a+b\n\t3.建立多项式a-b\n“);

printf(“\t4.退出\n**********************************************\n“);

for(;;flag=0){

printf(“执行操作：“);

scanf(“%d“,if(flag==1){

printf(“多项式a：“);PrintPolyn(pa);

printf(“多项式b：“);PrintPolyn(pb);continue;

}

if(flag==2){

pc=AddPolyn(pa,pb);

printf(“多项式a+b：“);PrintPolyn(pc);

DestroyPolyn(pc);continue;

}

if(flag==3){

pd=SubtractPolyn(pa,pb);

printf(“多项式a-b：“);PrintPolyn(pd);

DestroyPolyn(pd);continue;

}

if(flag==4)

break;

if(flag4)

printf(“Error!!!\n“);continue;

}//for

DestroyPolyn(pa);

DestroyPolyn(pb);

return

0;

}

3、运行结果：

二、设计一个模拟计算器的程序

1、题目要求：

设计一个模拟计算器的程序

要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。

2、

程序代码：

#include

#include

#include

using

namespace

std;

class

calculator

{

public:

void

cal(string

s);

void

express();

int

legal(string

w);

private:

void

push();

void

pop();

bool

can();

int

StringToNumber(string

aStr);

int

number[1000];

char

symbolt[1000];

string

s,t;

int

i,j,p;

};

void

calculator::push()

{

p++;

symbolt[p]=s[i];

}

void

calculator::pop()

{

p--;

switch

(symbolt[p+1])

{

case

+

:{number[p]+=number[p+1];break;}

case

-

:{number[p]=number[p]-number[p+1];break;}

case

:{number[p]=number[p]*number[p+1];break;}

case

/

:{number[p]=number[p]/number[p+1];break;}

}

}

bool

calculator::can()

{

if

(((s[i]==

+

)||(s[i]==

-

))

if

(((s[i]==

)||(s[i]==

/

))

return

false;

}

int

calculator::StringToNumber(string

aStr)

{

int

number

=

0;

for

(int

i=0;i=

0

)

calculator

MyCal;

if(!MyCal.legal(w))

{

MyCal.cal(w);

MyCal.express();

}

char

chose;

cout>chose;

if

(chose==

n

||chose==

N

)

break;

}

return

0;

}

3、

运行结果：

三、Josephus问题

1、

题目要求：

设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。

2、

程序代码：

#include

#include

“malloc.h“#define

False

0

#define

TRUE

1

typedef

int

DataType;

struct

SeqList{

int

MAXNUM;

int

n;

DataTypeelement;

};

typedef

struct

SeqListPSeqList;

PSeqList

createNullList_seq(int

m){

PSeqList

palist=(PSeqList)malloc(sizeof(struct

SeqList));

if(palist!=NULL){

palist->element=(DataType*)malloc(sizeof(DataType)*m);

if(palist->element){

palist->MAXNUM=m;

palist->n=0;

return

palist;

}

else

free(palist);

}

printf(“Out

of

space!!\n“);

return

NULL;

}

int

insertPre_seq(PSeqList

palist,int

p,DataType

x){

/*在palist所指顺序表中下标为P的元素之前插入元素x*/

int

q;

if

(palist->n>=palist->MAXNUM){//溢出

printf(“Overflow!

\n“);

return

0;

}

if

(ppalist->n){

printf(“Not

exist!

\n“);

return

0;

}

for(q=palist->n-1;q>=p;q--)

palist->element[q+1]=palist->element[q];

palist->element[p]=x;

palist->n=palist->n+1;

return

1;

}

int

deleteP_seq(PSeqList

palist,int

p){

//删除下标为p的元素

int

q;

if

(ppalist->n-1){

printf(“Not

exist!

\n“);

return

0;

}

for(q=p;qn-1;q++)

palist->element[q]=palist->element[q+1];

palist->n=palist->n-1;

return

1;

}

void

josephus_seq(PSeqList

palist,int

s,int

m){

int

s1,i,w;

s1=s-1;

for(i=palist->n;i>0;i--){

s1=(s1+m-1)%i;

w=palist->element[s1];

printf(“Out

element

%d

\n“,w);

deleteP_seq(palist,s1);

}

}

main(){

PSeqList

jos_alist;

int

i;

int

n,s,m;

printf(“\nplease

input

the

values(element);

free(jos_alist);

}

}

3、

运行结果：

例如输入n＝8，s＝1，m＝4；结果如下：

14