数据结构实验实习题答案

实验一 线性表

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

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

//1.1.c

#include

#include

void Insert(int* p,int length,int n){//插入函数

int i,j;

int flag=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;

}

}

int main(){

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

int length=7;//初始化表长

int i,x;

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

for(i=0;i

printf(\

}

printf(\请输入要插入的整数：\\n\

scanf(\

Insert(L,length,x);//插入x

printf(\插入%d后的顺序表为：\\n\

for(i=0;i<=length;i++){

printf(\

}

printf(\

system(\

return 0; }

2. 用单链表ha 存储多项式A（x ）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。试写出程序。

分析：这题主要是两个链表的相加，注意指针不要弄错就行，源程序有很详细的注释。 源程序：

//1.2.c

#include

static int n;

static int m;

static int max;

struct Polynomial{//多项式系数结构体

float data;

struct Polynomial* next; };

struct Polynomial* Creat_H(int k){//创建多项式系数的链表

struct Polynomial* L;

struct Polynomial* p;

p=(struct Polynomial*)malloc(sizeof(struct Polynomial));

L=p;

float temp;

int i;

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

for(i=0;i<=k;i++){

scanf(\

p->data=temp;

if(i==k){

p->next=NULL;

break;

}

p->next=(struct Polynomial*)malloc(sizeof(struct Polynomial));

p=p->next;

}

return L; }

struct Polynomial* Calculate(struct Polynomial* Pa,struct Polynomial* Pb){

//计算两个多项式相加

struct Polynomial* Pc;

struct Polynomial* L;

int i;

max=n>=m? n:m;

Pc=(struct Polynomial*)malloc(sizeof(struct Polynomial));

L=Pc;

for(i=0;i<=max;i++){

if(i==max){

Pc->next=NULL;

break;

}

Pc->next=(struct Polynomial*)malloc(sizeof(struct Polynomial));

Pc=Pc->next;

}

Pc=L;

while(Pa!=NULL&&Pb!=NULL){

Pc->data=Pa->data+Pb->data;

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;

}

}

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

while(Pa!=NULL){

Pc->data=Pa->data;

Pc=Pc->next;

Pa=Pa->next;

}

}

return L; }

int main(){

int i;

struct Polynomial *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;i<=max;i++){//输出相加后的结果

printf(\

if(i==max){

break;

}

Hc=Hc->next;

}

system(\

return 0; }

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

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

//1.3.c

#include

#include

struct Josephus{

int data;

struct Josephus* next; };

int main(){

struct Josephus* J;

struct Josephus* L;

struct Josephus* temp;

J=L;

int i,j;

int k=0;

int n,m,s;

int* p;

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

scanf(\

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

for(i=1;i<=n;i++){

L->data=i;

if(i==n){

L->next=J;

break;

}

L->next=(struct Josephus*)malloc(sizeof(struct Josephus));

L=L->next;

}//创建一个Josephus环

if(s==1){

for(i=1;i

J=J->next;

}

}

else{

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

J=J->next;

}

}

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

for(i=1;i

J=J->next;

}

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

temp=J->next;

J->next=temp->next;

free(temp);

}

for(i=0;i

printf(\

}

printf(\

free(p);

system(\

return 0; }

for(i=1;i

J=J->next;

}

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

temp=J->next;

J->next=temp->next;

free(temp);

}

for(i=0;i

printf(\

}

printf(\

free(p);

system(\

return 0; }

本文来源：https://www.bwwdw.com/article/f90.html