数据结构习题集答案(c版)(清华大学严蔚敏)

1.16

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

scanf(\

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

if(xy; //冒泡排序 printf(\}//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=0; temp[k-1]=1; //初始化

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

sum=0;

for(j=i-k;j

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.sport!=NULL) {

switch(result.schoolname) {

case 'A':

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;

……?……?…… } i++； }

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

printf(\

printf(\printf(\printf(\}

}//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(\scanf(\

printf(\for(i=0;i<=n;i++) scanf(\printf(\scanf(\

p=a;xp=1;sum=0; //xp用于存放x的i次方 for(i=0;i<=n;i++) {

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

printf(\}//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>x&&i>=0;i--) va.elem[i+1]=va.elem; 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||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(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->data) {

free(q); q=q->next; }

p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素 }//else }//while