数据结构试验实习题答案

本文格式为Word版，下载可任意编辑——数据结构试验实习题答案试验一线性表

1.设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表依旧有序。

分析：其实这个题在学C语言时就已经写过了，这里采用顺序表来存储数据。主要就是考虑插入的位置是不是在最终一个，假使不在最终一个，那么就要移动数据了，算法很简单就不再说了，这里的数据都看成是整型的。源程序：

//1.1.c

#include

#include

voidInsert(int*p,intlength,intn){//插入函数

inti,j;

intflag=0;

if(n>=p[length-1]){//n比最大数还要大时

p[length]=n;

flag=1;

}

else{

for(i=length-2;i>=0;i--){if(n>=p[i]){//插入n

for(j=length;j>=i+2;j--){

p[j]=p[j-1];

}

p[i+1]=n;

flag=1;

break;}

}

}

if(flag==0){//n为最小数时

for(j=length;j>=1;j--){p[j]=p[j-1];

}

p[0]=n;

}

}

intmain(){

intL[10]={1,3,6,8,9,10,15};//初始化一个非递减速有顺表

intlength=7;//初始化表长

inti,x;

printf(\插入前的顺序表为：\\n\

for(i=0;i

staticintn;

staticintm;

staticintmax;

structPolynomial{//多项式系数结构体

floatdata;

structPolynomial*next;};

structPolynomial*Creat_H(intk){//创立多项式系数的链表

structPolynomial*L;

structPolynomial*p;

p=(structPolynomial*)malloc(sizeof(structPolynomial));

L=p;

floattemp;

inti;

printf(\请依次输入系数(中间用空格隔开)：\\n\

for(i=0;idata=temp;

if(i==k){p->next=NULL;break;

}

p->next=(structPolynomial*)malloc(sizeof(structPolynomial));

p=p->next;

}

returnL;}

structPolynomial*Calculate(structPolynomial*Pa,structPolynomial*Pb){

//计算两个多项式相加

structPolynomial*Pc;

structPolynomial*L;

inti;

max=n>=m?n:m;

Pc=(structPolynomial*)malloc(sizeof(structPolynomial));

L=Pc;

for(i=0;inext=NULL;break;

}

Pc->next=(structPolynomial*)malloc(sizeof(structPolynomial));

Pc=Pc->next;

}

Pc=L;

while(Pa!=NULL

Pc=Pc->next;

Pa=Pa->next;

Pb=Pb->next;

}

if(Pa==NULL){//Pa的长度小于Pb

while(Pb!=NULL){Pc->data=Pb->data;Pc=Pc->next;Pb=Pb->next;

}

}

elseif(Pb==NULL){//Pb的长度小于Pa

while(Pa!=NULL){Pc->data=Pa->data;Pc=Pc->next;Pa=Pa->next;

}

}

returnL;}

intmain(){

inti;

structPolynomial*Ha,*Hb,*Hc;

printf(\请输入多项式a的最高次系n:\\n\

scanf(\

Ha=Creat_H(n);

printf(\请输入多项式b的最高次系m:\\n\

scanf(\

Hb=Creat_H(m);

Hc=Calculate(Ha,Hb);

printf(\系数:次数:\\n\

for(i=0;inext;

}

system(\

return0;}

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

分析：这题用单循环链表来做，数到m的结点就删除它，再用一个数组依次保存这些被删除的结点里的数据，一直到循环链表为空就行了。源程序：

//1.3.c

#include

#include

structJosephus{

intdata;

structJosephus*next;};

intmain(){

structJosephus*J;

structJosephus*L;

structJosephus*temp;

J=L;

inti,j;

intk=0;

intn,m,s;

int*p;

printf(\请输入n,m,s(中间用空格隔开：)\\n\

scanf(\

p=(int*)malloc(n*sizeof(int));

for(i=1;idata=i;

if(i==n){L->next=J;break;

}

L->next=(structJosephus*)malloc(sizeof(structJosephus));

L=L->next;

}//创立一个Josephus环

if(s==1){

for(i=1;inext;

}

}

else{

while(J->data!=s-1){J=J->next;

}

}

while(k!=n){//依次找出数到m的人

for(i=1;inext;

}

p[k++]=J->next->data;

temp=J->next;

J->next=temp->next;

free(temp);

}