【免费】数据结构答案答案啊啊资源-CSDN文库

共12个文件

doc：11个

pdf：1个

数据结构答案

需积分: 0 103 浏览量 2008-10-07 21:25:54 上传评论收藏 459KB RAR 举报

资源详情

资源评论

资源推荐

收起资源包目录

数据结构答案.rar.rar （12个子文件）

数据结构答案

第二章线性表.doc 50KB

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

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

第四章串.doc 53KB

第一章绪论.doc 25KB

第三章栈与队列.doc 41KB

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

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

第九章查找.doc 51KB

第七章图.doc 79KB

第十章内部排序.doc 53KB

数据结构答案.doc 306KB

说明:

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)

评论收藏

内容反馈

houzhoulao

粉丝: 0
资源: 5

数据结构答案答案啊啊

评论0

最新资源

数据结构答案 答案啊啊

评论0

广工数据结构答案

数据结构数据结构题集答案答案

数据结构习题答案，数据结构习题答案

数据结构课程答案数据结构课程答案

数据结构课后答案+代码版数据结构课后答案+代码版

PTA数据结构答案

数据结构 上机答案 数据结构 上机答案 数据结构 上机答案

数据结构答案（完整版）

数据结构习题及其答案

王红梅数据结构答案

数据结构1800题（含答案）数据结构1800题（含答案）

王红梅数据结构答案.pdf

广工anyview数据结构答案

数据结构试卷答案数据结构试卷答案数据结构试卷答案数据结构试卷答案数据结构试卷答案

数据结构课后题答案

殷人昆数据结构答案

数据结构答案全集.zip

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

XCP协议的规范文档

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

CANoe通过CAPL脚本实现自动测试

蓝牙BLE协议中文版.pdf

最新资源

数据结构答案答案啊啊

数据结构上机答案数据结构上机答案数据结构上机答案

Qt 5实现串口调试助手（源工程文件、0积分下载）