数据结构（C版）-严蔚敏-课后习题答案.pdf

清华大学严蔚敏数据结构习题集（C 版）答案

清华大学严蔚敏数据结构习题集（C 版）答案

第一章 绪论

1.16

void print_descending(int x,int y,int z)//按从大到小顺序输出三个数

{

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

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

{

int tempd;

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

if(m<k-1) f=0;

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

else

{

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

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

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

}

return OK;

}//fib

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

先想到递归方法),则时间复杂度将高达 O(k^m).

1.18

} resulttype;

typedef struct{

int malescore;

int femalescore;

int totalscore;

} scoretype;

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

组中

{

scoretype score;

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

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

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

break;

case 'B':

score.totalscore+=result.score;

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

else score.femalescore+=result.score;

break;

…… …… ……

}

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

}//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];

{

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 次方

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

xp*=x;

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;

2.12

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

A>B;值为负,表示 A<B;值为零,表示 A=B

{

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

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

return 0;

}//ListComp

2.13

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

{

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;

b

{

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

q.data=b;

if(i==1)

{

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

}

else

{