严蔚敏版数据结构习题集答案详解资源-CSDN文库

5星 · 超过95%的资源需积分: 4 23 浏览量 2011-12-26 13:28:13 上传评论收藏 258KB PDF 举报

根据给定的文件信息，我们可以总结出以下几个关键的IT知识点，特别是关于数据结构与算法的知识点： ### 1. 数据结构的重要性与应用数据结构是计算机科学中的一个核心概念，它涉及如何组织和存储数据，以便高效地进行访问和修改。严蔚敏教授的数据结构教材是学习数据结构的经典之一，其覆盖了线性结构（如数组、链表）、树形结构（如二叉树、堆）、图形结构（如图）以及查找和排序算法等内容。数据结构的选择直接影响到算法的效率，因此掌握不同的数据结构及其操作对于软件开发和算法设计至关重要。 ### 2. 算法设计与分析算法是解决问题的一系列步骤，而算法设计涉及到如何有效地解决问题。严蔚敏的数据结构习题集中涵盖了多种算法，如排序算法（如冒泡排序）、动态规划（如斐波那契数列的求解）和统计算法（如成绩统计）。理解并能设计高效的算法对于优化程序性能、解决实际问题有着重要作用。同时，算法分析，尤其是时间复杂度和空间复杂度的分析，是评估算法优劣的关键指标。 ### 3. C语言编程 C语言是一种通用的、过程式的编程语言，广泛应用于系统软件、嵌入式系统和应用软件开发中。严蔚敏的数据结构习题集使用C语言作为描述算法的语言，这是因为C语言提供了低级访问硬件的能力，同时具有高级语言的特性，适合于教学和实现复杂的算法。了解C语言的基本语法、数据类型、控制结构和函数定义对于理解和实现算法是必不可少的。 ### 4. 代码调试与优化在习题集中，作者提到了代码可能存在的错误和不足，这强调了代码调试和优化的重要性。调试是为了找出并修正代码中的错误，而优化则是为了提高代码的执行效率。良好的调试技巧可以帮助开发者快速定位问题，而优化则可以通过改进算法或代码结构来减少资源消耗，提升程序性能。 ### 5. 学术交流与合作习题集的解答过程体现了学术社区的交流与合作精神。多名网友参与了答案的修订和完善工作，这种开放式的合作不仅有助于提高解答的准确性和全面性，也促进了知识的共享与传播。在IT领域，开源项目、技术论坛和学术会议都是重要的交流平台，它们鼓励创新思维和团队协作，推动了技术的发展。严蔚敏的数据结构习题集不仅是学习数据结构和算法的重要资源，也是理解和实践软件工程基本原则的绝佳案例。通过深入研究这些习题及其解答，可以加深对数据结构、算法设计、编程语言和软件开发过程的理解，从而提升个人的技术能力和专业素养。

资源推荐

资源详情

资源评论

说明 : 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].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:",i);

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

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

printf("Total score of all:%d",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);

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<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->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->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->next=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)

{

if(p->data<q->data) p=p->next;

else if(p->data>q->data) q=q->next;

else

{

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

s->data=p->data;

pc->next=s;pc=s;

p=p->next;q=q->next;

}

}//while

C=pc;

}//LinkList_Intersect

2.27

void SqList_Intersect_True(SqList &A,SqList B)// 求元素递增排列

的线性表 A 和 B 的元素的交集并存回 A 中

{

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

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

{

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

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

else if(A.elem[i]!=A.elem[k])

{

A.elem[++k]=A.elem[i]; // 当发现了一个在 A,B 中都存在的元素

i++;j++; // 且 C 中没有 , 就添加到 C 中

}

}//while

while(A.elem[k]) A.elem[k++]=0;

}//SqList_Intersect_True

2.28

void LinkList_Intersect_True(LinkList &A,LinkList B)// 在链表结

构上重做上题

{

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

while(p&&q)

{

if(p->data<q->data) p=p->next;

else if(p->data>q->data) q=q->next;

else if(p->data!=pc->data)

{

pc=pc->next;

pc->data=p->data;

p=p->next;q=q->next;

}

}//while

}//LinkList_Intersect_True

2.29

void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)

{

i=0;j=0;k=0;m=0; //i 指示 A 中元素原来的位置 ,m 为移动后的位置

while(i<A.length&&j<B.length&& k<C.length)

{

if(B.elem[j]<C.elem[k]) j++;

else if(B.elem[j]>C.elem[k]) k++;

else

{

same=B.elem[j]; // 找到了相同元素 same

while(B.elem[j]==same) j++;

剩余35页未读，继续阅读

评论收藏

内容反馈

思念の汤圆

2013-07-19

有很好的参考价值。
li84006800

2012-10-09

很好很准确，很有参考价值，就是解题步骤没有，有点简单了

文修

粉丝: 41
资源: 60

严蔚敏版数据结构习题集答案详解

数据结构习题集及答案（严蔚敏版）

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

数据结构习题集 严蔚敏版（包括答案）

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

严蔚敏数据结构习题集答案详细版本

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

严蔚敏版数据结构 习题集答案.rar

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

数据结构习题集严蔚敏版

严蔚敏版数据结构答案

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

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

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

严蔚敏数据结构习题集答案.rar

严蔚敏 数据结构课本 习题集答案 源码

数据结构 严蔚敏教材 习题集答案.

数据结构习题集（严蔚敏版）

数据结构答案(严蔚敏版)

数据结构 严蔚敏版答案

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

清华大学、严蔚敏、数据结构习题集答案

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

严蔚敏《数据结构（C语言版）》讲义 + 习题集答案

最新资源

数据结构习题集严蔚敏版（包括答案）

严蔚敏版数据结构习题集答案.rar

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

严蔚敏数据结构课本习题集答案源码

数据结构严蔚敏教材习题集答案.

数据结构严蔚敏版答案