没有合适的资源?快使用搜索试试~ 我知道了~
首页严蔚敏数据结构\严蔚敏数据结构答案.doc
严蔚敏数据结构\严蔚敏数据结构答案.doc
4星 · 超过85%的资源 需积分: 16 15 下载量 27 浏览量
更新于2023-03-03
评论 1
收藏 277KB DOC 举报
严蔚敏的数据结构讲得非常好,自己也出书。但答案不太好找。严蔚敏数据结构\严蔚敏数据结构答案.doc
资源详情
资源评论
资源推荐
说明:
1. 本文是对严蔚敏《数据结构(c 语言版)习题集》一书中所有算法设计题目的解决方案,主
要作者为一具.以下网友:biwier,szm99,siice,龙抬头,iamkent,zames,birdthinking,lovebuaa 等为
答案的修订和完善工作提出了宝贵意见,在此表示感谢;
2. 本解答中的所有算法均采用类 c 语言描述,设计原则为面向交流、面向阅读,作者不保证程
序能够上机正常运行(这种保证实际上也没有任何意义);
3. 本解答原则上只给出源代码以及必要的注释,对于一些难度较高或思路特殊的题目将给出
简要的分析说明,对于作者无法解决的题目将给出必要的讨论.目前尚未解决的题目有: 5.20,
10.40;
4. 请读者在自己已经解决了某个题目或进行了充分的思考之后,再参考本解答,以保证复习效
果;
5. 由于作者水平所限,本解答中一定存在不少这样或者那样的错误和不足,希望读者们在阅读
中多动脑、勤思考,争取发现和纠正这些错误,写出更好的算法来.请将你发现的错误或其它
值得改进之处向作者报告:##[email]yi-ju@263.net[/email]
第一章 绪论
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 || m==k) f=1;
##else
##{
# # for(i=0;i<=k-2;i++) temp[i]=0;
# # temp[k-1]=1;temp[k]=1; //初始化
# # sum=1;
# # j=0;
# # for(i=k+1;i<=m;i++,j++) //求出序列第 k 至第 m 个元素的值
# ## #temp[i]=2*sum-temp[j];
# # f=temp[m];
##}
##return OK;
}//fib
分析: k 阶斐波那契序列的第 m 项的值 f[m]=f[m-1]+f[m-2]+......+f[m-k]
# ## ###=f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]
# ## ###=2*f[m-1]-f[m-k-1]
所以上述算法的时间复杂度仅为 O(m). 如果采用递归设计,将达到 O(k^m). 即使采用暂存中
间结果的方法,也将达到 O(m^2).# #
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[MAXSIZE];
##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[ 0 ].totalscore+=result[i].score;
# ## ###if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;
# ## ###else score[ 0 ].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 temp;
##float *p=a;
##printf("Input number of terms:");
##scanf("%d",&n);
##printf("Input value of x:");
##scanf("%f",&x);
##printf("Input the %d coefficients from a0 to a%d:\n",n+1,n);
##p=a;xp=1;sum=0; //xp 用于存放 x 的 i 次方
##for(i=0;i<=n;i++)
##{
# # scanf("%f",&temp);
# # sum+=xp*(temp);
# # 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,并用返回值表示结果,值为 1,表示 A>B;
值为-1,表示 A<B;值为 0,表示 A=B
{
##for(i=1;i<=A.length&&i<=B.length;i++)
# # if(A.elem[i]!=B.elem[i])
# ## #return A.elem[i]>B.elem[i]?1:-1;
##if(A.length==B.length) return 0;
##return A.length>B.length?1:-1;# # //当两个字符表可以互相比较的部分完全相同时,哪个较长,
哪个就较大
}//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
剩余63页未读,继续阅读
cjy1986823
- 粉丝: 0
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论1