【免费】严蔚敏《数据结构(c语言版)习题集》答案资源-CSDN文库

共13个文件

doc：11个

pdf：1个

url：1个

严蔚敏《数据结构(c语言版)习题集》答案

需积分: 0 87 浏览量 2008-11-08 21:45:14 上传评论收藏 524KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

(c语言版)习题集》答案.rar （13个子文件）

严蔚敏《数据结构(c语言版)习题集》答案

第二章线性表.doc 50KB

第八章动态存储管理.doc 26KB

第五章数组和广义表.doc 54KB

第四章串.doc 53KB

第一章绪论.doc 25KB

第三章栈与队列.doc 41KB

www.khdaw.com.url 132B

数据结构习题答案.doc 484KB

第六章树和二叉树.doc 77KB

数据结构答案（完整版）.pdf 370KB

第九章查找.doc 51KB

第七章图.doc 79KB

第十章内部排序.doc 53KB

说明:

1. 本文是对严蔚敏《数据结构(c 语言

版)习题集》一书中所有算法设计题目

的解决方案,主要作者为 kaoyan.com计

算机版版主一具.以下网友:siice,龙抬

头,iamkent,zames,birdthinking 等为答

案的修订和完善工作提出了宝贵意见,

在此表示感谢;

2. 本解答中的所有算法均采用类 c 语

言描述,设计原则为面向交流、面向阅

读,作者不保证程序能够上机正常运行

(这种保证实际上也没有任何意义);

3. 本解答原则上只给出源代码以及必

要的注释,对于一些难度较高或思路特

殊的题目将给出简要的分析说明,对于

作者无法解决的题目将给出必要的讨

论.目前尚未解决的题目有: 5.20, 10.40;

4. 请读者在自己已经解决了某个题目

或进行了充分的思考之后,再参考本解

答,以保证复习效果;

5. 由于作者水平所限,本解答中一定

存在不少这样或者那样的错误和不足,

希望读者们在阅读中多动脑、勤思考,

争取发现和纠正这些错误,写出更好的

算法来.请将你发现的错误或其它值得

改进之处向作者报告: yi-ju@263.net

第一章绪论

1.16

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

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

{

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

if(x<y) x<->y; //<->为表示交换的双

目运算符,以下同

if(y<z) y<->z;

if(x<y) x<->y; //冒泡排序

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<k-1) f=0;

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<i;j++) sum+=temp[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].scor

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;cou

nt++) //注意循环结束的条件

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<B;值

为零,表示 A=B

{

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->n

ext);

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(LNod

e));

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->data<maxk) q=q->next; //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

}//Delete_Equal

2.21

void reverse(SqList &A)//顺序表的就

地逆置

{

for(i=1,j=A.length;i<j;i++,j--)

A.elem[i]<->A.elem[j];

}//reverse

2.22

void LinkList_reverse(Linklist &L)//链

表的就地逆置;为简化算法,假设表长

大于 2

{

p=L->next;q=p->next;s=q->next;p->ne

xt=NULL;

while(s->next)

{

q->next=p;p=q;

q=s;s=s->next; //把 L 的元素逐个插

入新表表头

}

q->next=p;s->next=q;L->next=s;

}//LinkList_reverse

分析:本算法的思想是,逐个地把 L的当

前元素 q 插入新的链表头部,p 为新表

表头.

2.23

void merge1(LinkList &A,LinkList

&B,LinkList &C)//把链表 A 和 B 合并

为 C,A 和 B 的元素间隔排列,且使用原

存储空间

{

p=A->next;q=B->next;C=A;

while(p&&q)

{

s=p->next;p->next=q; //将 B 的元素

插入

if(s)

{

t=q->next;q->next=s; //如 A 非空,将

A 的元素插入

}

p=s;q=t;

}//while

}//merge1

2.24

void reverse_merge(LinkList

&A,LinkList &B,LinkList &C)//把元素

递增排列的链表 A 和 B 合并为 C,且 C

中元素递减排列,使用原空间

{

pa=A->next;pb=B->next;pre=NULL;

//pa 和 pb 分别指向 A,B 的当前元素

while(pa||pb)

{

if(pa->data<pb->data||!pb)

{

pc=pa;q=pa->next;pa->next=pre;pa=

q; //将 A 的元素插入新表

}

else

{

pc=pb;q=pb->next;pb->next=pre;pb

=q; //将 B 的元素插入新表

}

pre=pc;

}

C=A;A->next=pc; //构造新表头

}//reverse_merge

分析:本算法的思想是,按从小到大的

顺序依次把 A 和 B 的元素插入新表的

头部 pc 处,最后处理 A 或 B 的剩余元

素.

2.25

void SqList_Intersect(SqList A,SqList

B,SqList &C)//求元素递增排列的线性

表 A 和 B 的元素的交集并存入 C 中

{

i=1;j=1;k=0;

while(A.elem[i]&&B.elem[j])

{

if(A.elem[i]<B.elem[j]) i++;

if(A.elem[i]>B.elem[j]) j++;

if(A.elem[i]==B.elem[j])

{

C.elem[++k]=A.elem[i]; //当发现了

一个在 A,B 中都存在的元素,

i++;j++; //就添加到 C 中

}

}//while

}//SqList_Intersect

2.26

void LinkList_Intersect(LinkList

A,LinkList B,LinkList &C)//在链表结

构上重做上题

{

p=A->next;q=B->next;

pc=(LNode*)malloc(sizeof(LNode));

while(p&&q)

评论收藏

内容反馈

zwqhlzd

粉丝: 2
资源: 15

严蔚敏《数据结构(c语言版)习题集》答案

严蔚敏数据结构c语言版习题集答案

严蔚敏数据结构c语言版习题集答案串.pdf

严蔚敏数据结构C语言版 习题集答案WORD版

严蔚敏数据结构C语言版习题集答案

严蔚敏《数据结构(c语言版)习题集》全答案

严蔚敏《数据结构（c语言版）习题集》答案

严蔚敏《数据结构(c 语言版)习题集》答案

严蔚敏《数据结构(c语言版)习题集》全答案.pdf

严蔚敏数据结构c语言版习题集全答案.doc

严蔚敏数据结构题集 C语言版 答案

严蔚敏数据结构c语言版+严蔚敏数据结构习题集+严蔚敏数据结构习题集答案

严蔚敏《数据结构(c语言版)习题集》(带完整答案)

严蔚敏数据结构(c语言版)习题集答案

严蔚敏《数据结构(c语言版)习题集

严蔚敏《数据结构(c语言版)习题集》

数据结构习题集答案（严蔚敏c语言版）

严蔚敏：数据结构习题集（c语言版）

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

严蔚敏《数据结构C语言版习题集》答案

严蔚敏《数据结构C语言版习题集》答案 chm

严蔚敏《数据结构(c语言版)习题集》答案第六章树和二叉树文库.pdf

严蔚敏 数据结构 （C语言版） 习题集答案

最新资源

严蔚敏数据结构C语言版习题集答案WORD版

严蔚敏数据结构题集 C语言版答案

严蔚敏数据结构（C语言版）习题集答案