数据结构题集(C语言版)算法设计题答案

第一章绪论

1.16

void print_descending(int x,int y,int z)//

按从大到小顺序输出三个数

{

scanf("%d,%d,%d",&x,&y,&z);

if(xy; //<->为表示交换的双目运算符,以下同

if(yz;

if(xy; //冒泡排序

printf("%d %d %d",x,y,z);

}//print_descending

1.17

Status fib(int k,int m,int &f)//求k 阶斐波那契序列的第m 项的值f

{

int tempd;

if(k<2||m<0) return ERROR;

if(m

else if (m==k-1) f=1;

else

{

for(i=0;i<=k-2;i++) temp[i]=0;

temp[k-1]=1; //初始化

for(i=k;i<=m;i++) //求出序列第k 至第m 个元素的值

{

sum=0;

for(j=i-k;j

temp[i]=sum;

}

f=temp[m];

}

return OK;

}//fib

分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m).

1.18

typedef struct{

char *sport;

enum{male,female}

gender;

char schoolname; //校名为'A','B','C','D'或'E'

char *result;

int score;

} resulttype;

typedef struct{

int malescore;

int femalescore;

int totalscore;

} scoretype;

void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中

{

scoretype score ;

i=0;

while(result[i].sport!=NULL)

{

switch(result[i].schoolname)

{

case 'A':

score[ 0 ].totalscore+=result[i].score;

if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;

else score[ 0 ].femalescore+=result[i].score;

break;

case 'B': score.totalscore+=result[i].score;

if(result[i].gender==0) score.malescore+=result[i].score;

else score.femalescore+=result[i].score;

break;

…… …… ……

}

i++；

}

for(i=0;i<5;i++)

{

printf("School %d:\n",i);

printf("Total score of male:%d\n",score[i].malescore);

printf("Total score of female:%d\n",score[i].femalescore);

printf("Total score of all:%d\n\n",score[i].totalscore);

}

}//summary

1.19

Status algo119(int a[ARRSIZE])//求i!*2^i 序列的值且不超过maxint

{

last=1;

for(i=1;i<=ARRSIZE;i++)

{

a[i-1]=last*2*i;

if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;

last=a[i-1];

return OK;

}

}//algo119

分析:当某一项的结果超过了maxint 时,它除以前面一项的商会发生异常.

1.20

void polyvalue()

{

float ad;

float *p=a;

printf("Input number of terms:");

scanf("%d",&n);

printf("Input the %d coefficients from a0 to a%d:\n",n,n);

for(i=0;i<=n;i++) scanf("%f",p++);

printf("Input value of x:");

scanf("%f",&x);

p=a;xp=1;sum=0; //xp 用于存放x 的i次方

for(i=0;i<=n;i++)

{

sum+=xp*(*p++);

xp*=x;

}

printf("Value is:%f",sum);

}//polyvalue

第二章线性表

2.10

Status DeleteK(SqList &a,int i,int k)//删

除线性表a 中第i 个元素起的k 个元素

{

if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;

for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件

a.elem[i+count-1]=a.elem[i+count+k-1];

a.length-=k;

return OK;

}//DeleteK

2.11

Status Insert_SqList(SqList &va,int x)//把x 插入递增有序表va 中

{

if(va.length+1>va.listsize) return ERROR;

va.length++;

for(i=va.length-1;va.elem[i]>x&&i>=0;i--)

va.elem[i+1]=va.elem[i];

va.elem[i+1]=x;

return OK;

}//Insert_SqList

2.12

int ListComp(SqList A,SqList B)//比较字符表A 和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A

{

for(i=1;A.elem[i]||B.elem[i];i++)

if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i];

return 0;

}//ListComp

2.13

LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针

{

for(p=l->next;p&&p->data!=x;p=p->next);

return p;

}//Locate

2.14

int Length(LinkList L)//求链表的长度

{

for(k=0,p=L;p->next;p=p->next,k++);

return k;

}//Length

2.15

void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb 接在ha 后面形成链表hc

{

hc=ha;p=ha;

while(p->next) p=p->next;

p->next=hb;

}//ListConcat

2.16

见书后答案.

2.17

Status Insert(LinkList &L,int i,int b)//在无头结点链表L 的第i 个元素之前插入元素b

{

p=L;q=(LinkList*)malloc(sizeof(LNode));

q.data=b;

if(i==1)

{

q.next=p;L=q; //插入在链表头部

}

else

{

while(--i>1) p=p->next;

q->next=p->next;p->next=q; //插入在第i 个元素的位置

}

}//Insert

2.18

Status Delete(LinkList &L,int i)//在无头结点链表L 中删除第i 个元素

{

if(i==1) L=L->next; //删除第一个元素

else

{

p=L;

while(--i>1) p=p->next;

p->next=p->next->next; //删除第i 个元素

}

}//Delete

2.19

Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L 中值大于mink 且小于maxk 的所有元素

{

p=L;

while(p->next->data<=mink) p=p->next; //p 是最后一个不大于mink的元素

if(p->next) //如果还有比mink 更大的元素

{

q=p->next;

while(q->datanext; //q是第一个不小于maxk 的元素

p->next=q;

}

}//Delete_Between

2.20

Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L 中所有值相同的元素

{

p=L->next;q=p->next; //p,q 指向相邻两元素

while(p->next)

{

if(p->data!=q->data)

{

p=p->next;q=p->next; //当相邻两元素不相等时,p,q 都向后推一步

}

else

{

while(q->data==p->d …… 此处隐藏：16295字，全部文档内容请下载后查看。喜欢就下载吧 ……