《数据结构-用C语言描述》课后习题答案_第1页
《数据结构-用C语言描述》课后习题答案_第2页
《数据结构-用C语言描述》课后习题答案_第3页
《数据结构-用C语言描述》课后习题答案_第4页
《数据结构-用C语言描述》课后习题答案_第5页
已阅读5页,还剩19页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

本文格式为Word版,下载可任意编辑——《数据结构—用C语言描述》课后习题答案=i;j--)A[j+1]=A[j];向后移动元素A[i]=x;插入元素}算法终止2·4

voidrightrotate(ElemTypeA[],intn,k)

以向量作存储结构,本算法将向量中的n个元素循环右移k位,且只用一个辅助空间。{intnum=0;计数,最终应等于nintstart=0;记录开始位置(下标)while(numnext,*pre=L,*s;

p为工作指针,指向当前元素,pre为前驱指针,指向当前元素的前驱s=(linklist*)malloc(sizeof(linklist));申请空间,不判断溢出s->data=x;

while(pp=p->next;}查找插入位置pre->next=s;s->next=p;插入元素}算法终止2·6

voidinvert(linklist*L)

本算法将带头结点的单链表L逆置。算法思想是先将头结点从表上摘下,然后从第一个元素结点开始,依次前插入以L为头结点的链表中。

{linklist*p=L->next,*s;

p为工作指针,指向当前元素,s为p的后继指针

L->next=null;头结点摘下,指针域置空。算法中头指针L始终不变while(p)

{s=p->next;保存后继结点的指针p->next=L->next;逆置L->next=p;

p=s;将p指向下个待逆置结点}

}算法终止2·7

(1)intlength1(linklist*L)

本算法计算带头结点的单链表L的长度{linklist*p=L->next;inti=0;

p为工作指针,指向当前元素,i表示链表的长度while(p)

{i++;p=p->next;}return(i);}算法终止

(2)intlength1(nodesa[MAXSIZE])本算法计算静态链表s中元素的个数。{intp=sa[0].next,i=0;

p为工作指针,指向当前元素,i表示元素的个数,静态链指针等于-1时链表终止while(p!=-1)

{i++;p=sa[p].next;}return(i);}算法终止

2·8

voidunion_invert(linklist*A,*B,*C)

A和B是两个带头结点的递增有序的单链表,本算法将两表合并成一个带头结点的递减有序单链表C,利用原表空间。{linklist*pa=A->next,*pb=B->next,*C=A,*r;

pa,pb为工作指针,分别指向A表和B表的当前元素,r为当前逆

3置

元素的后继指针,使逆置元素的表避免断开。算法思想是边合并边逆置,使递增有序的单链表合并为递减有序的单链表。

C->next=null;头结点摘下,指针域置空。算法中头指针C始终不变

while(pa保存后继结点的指针pa->next=C->next;逆置

C->next=pa;

pa=r;恢复待逆置结点的指针}

else将B表中元素合并且逆置{r=pb->next;保存后继结点的指针pb->next=C->next;逆置

C->next=pb;

pb=r;恢复待逆置结点的指针}

以下while(pa)和while(pb)语句,只执行一个while(pa)将A表中剩余元素逆置{r=pa->next;保存后继结点的指针pa->next=C->next;逆置

C->next=pa;

pa=r;恢复待逆置结点的指针}

while(pb)将B表中剩余元素逆置{r=pb->next;保存后继结点的指针pb->next=C->next;逆置

C->next=pb;

pb=r;恢复待逆置结点的指针}

free(B);释放B表头结点}算法终止2·9

voiddeleteprior(linklist*L)

长度大于1的单循环链表,既无头结点,也无头指针,本算法删除*s的前驱结点

4{linklist*p=s->next,*pre=s;p为工作指针,指向当前元素,pre为前驱指针,指向当前元素*p的前驱

while(p->next!=s){pre=p;p=p->next;}查找*s的前驱pre->next=s;

free(p);删除元素}算法终止

2·10

voidone_to_three(linklist*A,*B,*C)

A是带头结点的的单链表,其数据元素是字符字母、字符、数字字符、其他字符。本算法将A表分成

三个带头结点的循环单链表A、B和C,分别含有字母、数字和其它符号的同一类字符,利用原表空间。

{linklist*p=A->next,r;

p为工作指针,指向A表的当前元素,r为当前元素的后继指针,使表避免断开。算法思想是取出当前元素,根据是字母、数字或其它符号,分别插入相应表中。B=(linklist*)malloc(sizeof(linklist));申请空间,不判断溢出B->next=null;准备循环链表的头结点

C=(linklist*)malloc(sizeof(linklist));申请空间,不判断溢出C->next=null;准备循环链表的头结点while(p)

{r=p->next;用以记住后继结点

if(p->data>=’a’A->next=p;}将字母字符插入A表

elseif(p->data>=’0’B->next=p;}将数字字符插入B表else{p->next=C->next;C->next=p;}将其它符号插入C表

p=r;恢复后继结点的指针}while

}算法终止2·11

voidlocate(dlinklist*L)

L是带头结点的按访问频度递减的双向链表,本算法先查找数据x,

查找成功时结点的访问频度域增1,最终将该结点按频度递减插入链表中适当位置。{linklist*p=L->next,*q;

p为工作指针,指向L表的当前元素,q为p的前驱,用于查找插入位置。while(p查找值为x的结点。if(!p)return(“不存在值为x的结点〞);

else{p->freq++;令元素值为x的结点的freq域加1。p->next->prir=p->prior;将p结点从链表上摘下。p->prior->next=p->next;

q=p->prior;以下查找p结点的插入位置

while(q!=L

p->next=q->next;q->next->prior=p;将p结点插入p->prior=q;q->next=p;}}算法终止

第三章栈和队列(参考答案)

从数据结构角度看,栈和队列是操作受限的线性结构,其顺序存储结构和链式存储结构的定义与线性表一致,请参考教材,这里不再重复。

5

3.11234213432144321

1243214332411324231434211342234114322431

设入栈序列元素数为n,则可能的出栈序列数为C2nn=(1n+1)*(2n!(n!)2)3.2证明:由jdata);p=p->next;}

if(n%2!==0)p=p->next;奇数个结点时跳过中心结点while(pif(p==null)printf(“链表中心对称〞);elseprintf(“链表不是中心对称〞);}算法终止

3.4

intmatch()

从键盘读入算术表达式,本算法判断圆括号是否正确配对(inits;初始化栈sscanf(“%c〞,

while(ch!=’#’)’#’是表达式输入终止符号

switch(ch)

{case’(’:push(s,ch);break;

case’)’:if(empty(s)){printf(“括号不配对〞);exit(0);}pop(s);}

if(!empty(s))printf(“括号不配对〞);elseprintf(“括号配对〞);}算法终止3.5

typedefstruct两栈共享一向量空间{ElemTypev[m];栈可用空间0—m-1inttop[2]栈顶指针}twostack;

intpush(twostack*s,inti,ElemTypex)

两栈共享向量空间,i是0或1,表示两个栈,x是进栈元素,本算法是入栈操作

{if(abs(s->top[0]-s->top[1])==1)return(0);栈满else{switch(i)

{case0:s->v[++(s->top)]=x;break;case1:s->v[--(s->top)]=x;break;

default:printf(“栈编号输入错误〞);return(0);}

return(1);入栈成功}}算法终止

ElemTypepop(twostack*s,inti)

6两栈共享向量空间,i是0或1,表示两个栈,本算法是退栈操作{ElemTypex;

if(i!=0栈编号错误else{switch(i)

{case0:if(s->top[0]==-1)return(0);栈空

elsex=s->v[s->top--];break;

case1:if(s->top[1]==m)return(0);栈空

elsex=s->v[s->top++];break;

default:printf(“栈编号输入错误〞);return(0);}

return(x);退栈成功}}算法终止

ElemTypetop(twostack*s,inti)

两栈共享向量空间,i是0或1,表示两个栈,本算法是取栈顶元素操作{ElemTypex;switch(i)

{case0:if(s->top[0]==-1)return(0);栈空

elsex=s->v[s->top];break;

case1:if(s->top[1]==m)return(0);栈空

elsex=s->v[s->top];break;

default:printf(“栈编号输入错误〞);return(0);}

return(x);取栈顶元素成功}算法终止3.6

voidAckerman(intm,intn)Ackerman函数的递归算法{if(m==0)return(n+1);

elseif(m!=0elsereturn(Ackerman(m-1,Ackerman(m,n-1))}算法终止3.7

(1)linklist*init(linklist*q)

q是以带头结点的循环链表表示的队列的尾指针,本算法将队列置空

{q=(linklist*)malloc(sizeof(linklist));申请空间,不判断空间溢出q->next=q;return(q);}算法终止

(2)linklist*enqueue(linklist*q,ElemTypex)

q是以带头结点的循环链表表示的队列的尾指针,本算法将元素x入队{s=(linklist*)malloc(sizeof(linklist));申请空间,不判断空间溢出s->next=q->next;将元素结点s入队列q->next=s;

q=s;修改队尾指针return(q);}算法终止

(3)linklist*delqueue(linklist*q)

q是以带头结点的循环链表表示的队列的尾指针,这是出队算法{if(q==q->next)return(null);判断队列是否为空else{linklist*s=q->next->next;s指向出队元素

7if(s==q)q=q->next;若队列中只一个元素,置空队列elseq->next->next=s->next;修改队头元素指针free(s);释放出队结点}

return(q);

}算法终止。算法并未返回出队元素3.8

typedefstruct

{ElemTypedata[m];循环队列占m个存储单元

intfront,rear;front和rear为队头元素和队尾元素的指针

约定front指向队头元素的前一位置,rear指向队尾元素

}sequeue;

intqueuelength(sequeue*cq)

cq为循环队列,本算法计算其长度

{return(cq->rear-cq->front+m)%m;}算法终止3.9

typedefstruct

{ElemTypesequ[m];循环队列占m个存储单元

intrear,quelen;rear指向队尾元素,quelen为元素个数}sequeue;

(1)intempty(sequeue*cq)

cq为循环队列,本算法判断队列是否为空{return(cq->quelen==0?1:0);}算法终止

(2)sequeue*enqueue(sequeue*cq,ElemTypex)cq是如上定义的循环队列,本算法将元素x入队{if(cq->quelen==m)return(0);队满

else{cq->rear=(cq->rear+1)%m;计算插入元素位置

cq->sequ[cq->rear]=x;将元素x入队列

cq->quelen++;修改队列长度}

return(cq);}算法终止

ElemTypedelqueue(sequeue*cq)

cq是以如上定义的循环队列,本算法是出队算法,且返回出队元素{if(cq->quelen==0)return(0);队空

else{intfront=(cq->rear-cq->quelen+1+m)%m;出队元素位置cq->quelen--;修改队列长度return(cq->sequ[front]);返回队头元素}

}算法终止

第四章串(参考答案)

在以下习题解答中,假定使用如下类型定义:#defineMAXSIZE1024typedefstruct

{chardata[MAXSIZE];

intcurlen;curlen表示终端结点在向量中的位置}seqstring;

typedefstructnode

8{chardata;

structnode*next;}linkstring;

4.2intindex(strings,t)

s,t是字符串,本算法求子串t在主串s中的第一次出现,若s串中包含t串,返回其第一个字符在s中的位置,否则返回0{m=length(s);n=length(t);i=1;

while(inext;q=Y->next;pre=p;while(p取X中的字符while(q和Y中字符比较

if(!q)return(ch);找到Y中没有的字符

else{pre=p->next;上一字符在Y中存在,p=pre;取X中下一字符。

q=Y->next;再从Y的第一个字符开始比较}}

return(null);X中字符在Y中均存在}算法终止4.6

intstrcmp(seqstring*S,seqstring*T)

S和T是指向两个顺序串的指针,本算法比较两个串的大小,若S串大于T串,返回1;若S串等于T串,返回0;否则返回-1{inti=0;

while(s->ch[i]!=’\\0’

9elseif(s->ch[i]ch[i])return(-1);elsei++;比较下一字符

if(s->ch[i]!=’\\0’

elseif(s->ch[i]==’\\0’elsereturn(0);}算法终止4.7

linkstring*invert(linkstring*S,linkstring*T)

S和T是用带头结点的结点大小为1的单链表表示的串,S是主串,T是模式串。本算法是先模式匹配,查找T在S中的第一次出现。如模式匹配成功,则将S中的子串(T串)逆置。{linkstring*pre,*sp,*tp;

pre=S;pre是前驱指针,指向S中与T匹配时,T中的前驱sp=S->next;tp=T->next;sp和tp分别是S和T串上的工作指针while(sptp=tp->next;}

else失配时主串回溯到下一个字符,子串再以第一个字符开始{pre=pre->next;sp=pre->next;tp=T->next;}

if(tp!=null)return(null);匹配失败,没有逆置else以下是T串逆置

{tp=pre->next;tp是逆置的工作指针,现在指向待逆置的第一个字符

pre->next=sp;将S中与T串匹配时的前驱指向匹配后的后继while(tp!=sp){r=tp->next;

tp->next=pre->next;pre->next=tp;tp=r}}

}算法终止

第五章多维数组和广义表(参考答案)

5.1A[2][3][2][3]

A0000,A0001,A0002A0010,A0011,A0012A0100,A0101,A0102A0110,A0111,A0112A0200,A0201,A0202A0210,A0211,A0212

将第一维的0变为1后,可列出另外18个元素。以行序为主(即行优先)时,先改变右边的下标,从右到左进行。

5.2设各维上下号为c1…d1,c2…d2,c3…d3,每个元素占l个单元。

LOC(aijk)=LOC(ac1c2c3)+[(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)]*l推广到n维数组!!(下界和上界)为(ci,di),其中1

i=1

n

其中αi∏(dk-ck+1)(1=m)printf(“马鞍点i=%d,j=%d,a[i][j]=%d〞,i,j,a[i][j]);}ENDOFforjj}ENDOFfori

最坏时间繁杂度为O(m*(n+n*m)).(最坏时所有元素一致,都是马鞍点)解法2:若矩阵中元素值互不一致,则用一维数组row记录下来各行最小值,再用一维数组col记录下来各列最大值,相等者为马鞍点。

for(i=0;icol[j])col[j]=a[i][j];重新确定最大值

}

for(i=0;iA[max[j]][j])max[j]=i;重新确定第j列最大值的行号if(A[i][j]}

for(i=0;inext;cb=B->next;while(ca!=Apb=cb->right;}

if(pa==ca)ca=ca->next;A表在该行无非0元素;else

if(pb==cb)cb=cb->nextB表在该行无非0元素;elseif(pb->colcol)B的非0元素插入A中;{j=pb->col;pt=chb[j];pre=pt取到表头指针;while(pt->down_colcol){pre=pt;pt=pt->down;}

pre->down=pt->down;该结点从B表相应列摘下i=pb->right;pt=chb[i];pre=pt;取B表行表头指针while(pt->right->rowrow{pre=pt;pt=pt->right;}

pre->right=pt->riht;该结点从B表相应行链表中摘下。Pbt=pb;pb=pb->right;B表移至下一结点以下是将pbt插入A表的相应列链表中j=pbt->col;pt=cha[j];pre=pt;

while(pt->down!=cha[j]pt=pt->down}

pre->down=pbt;pbt->down=pt;

以下是将pbt插入A表相应行链表中i=pbt->right;pt=cha[i];pre=pt;

while(pt->right!=cha[i]pt=pt->right;}pre->right=ptb;ptb->right=pt;

}endof“if(pb->colcol)

elseif(pa->col=pb->col)处理两表中行列一致的非0元素{v=pa->data+pb->data;if(v!=0){pa->data+=pb->data;pa=pa->right;将pb从行链表中删除;pb=pb->right;}else{将pa,pb从链表中删除;然后pa=pa->right;pb=pb->right;}5.7(1),则

n=n0+n1+n2+……+nm+(1)

13设树的分支数为B,有n=B+1

n=1n1+2n2+……+mnm+1(2)由(1)和(2)有:

n0=n2+2n3+……+(m-1)nm+1

6.4

i-1

(1)k(i为层数)(2)(n-2)k+1(3)(n-1)*k+i+1

(4)(n-1)%k!=0;其右兄弟的编号n+16.5(1)顺序存储结构

1234567891011121314ABCD#EF#G####H

注:#为空结点

A

B^C^D^E^F^^G^^H^6.6

(1)前序ABDGCEFH(2)中序DGBAECHF(3)后序GDBEHFCA6.7

(1)空二叉树或任何结点均无左子树的非空二叉树(2)空二叉树或任何结点均无右子树的非空二叉树(3)空二叉树或只有根结点的二叉树6.8

int(0);

else{bl=(bl>br?bl+1:br+1);左右子树高度的大者加1(根)}}算法终止6.9

voidpreorder(cbt[],intn,inti);

cbt是以完全二叉树形式存储的n个结点的二叉树,i是数组下标,初始调用时为1。本算法以非递归形式前序遍历该二叉树

14{inti=1,s[],top=0;s是栈,栈中元素是二叉树结点在cbt中的序号top是栈顶指针,栈空时top=0if(n0){while(i0)i=s[top--];退栈,先序访问右子树}ENDOFwhile(i0)}算法终止

以下是非完全二叉树顺序存储时的递归遍历算法,“虚结点〞用‘*’表示voidpreorder(bt[],intn,inti);

bt是以完全二叉树形式存储的一维数组,n是数组元素个数。i是数组下标,初始调用时为1。

{if(idata!=T2->data)return(0);根结点值不等elsereturn(equal(T1->lchild,T2->lchild)s是指针数组,数组中元素为二叉树节点的指针top=0;

while(t!=null||top!=0)

{while(t!=null){visit(*t);s[++top]=t;t=t->lchild}if(top!=0){t=s[top--];t=t->rchild;}}

}算法终止

voidinorder(bitree*t);(中序非递归遍历){bitree*s[n+1];

15

top=0;

while((t!=null||top!=0)

{while(t!=null){s[++top]=t;t=t->lchild}

if(top!=0){t=s[top--];visit(*t);t=t->rchild;}}算法终止

voidpostorder(bitree*t);(后序非递归遍历){typedefstructnode{bitree*t;tag:0..1}stack;stacks[n+1];top=0;

while(t||top)

{while(t){s[++top].t=t;s[top].tag=0;t=t->lchild;}while(top}if(top){s[top].tag=1;t=s[top].t->rchild;}}

}算法终止6.13

bitree*dissect(bitree**t,ElemTypex)

二叉树t至多有一个结点的数据域为x,本算法拆去以x为根的子树拆开后的第一棵树用t表示,成功拆开后返回其次棵二叉树{bitree*p,*find;if(*t!=null)

{if((*t)->data==x)根结点数据域为x{p=*t;*t=null;return(p);}

else{find=(dissect(在左子树中查找并拆开若在左子树中未找到,就到右子树中查找并拆开if(!find)find=(dissect(return(find);}}

elsereturn(null);空二叉树}算法终止6.14

intsearch(bitreet,ElemTypex)

设二叉树t中,值为x的结点至多一个,本算法打印x的所有祖先算法思想是,借助后序非递归遍历,用栈装遍历过程的结点,当查到值为x的结点时,栈中元素都是x的祖先{typedefstruct{bitreep;inttag;}snode;

16snodes[];inttop=0;

while(ts[top].tag=0;t=t->lchild;}if(t->data==x)

{for(i=1;idata);输出,设元素为字符

return(1);}else

while(top>0退出右子树已访问的结点

if(top>0)置访问标志1,访问右子树{s[top].tag=1;t=s[top].p;t=t->rchild;}

}

return(0);没有值为x的结点}算法终止

6.15中序序列BDCEAFHG后序序列DECBHGFAA

BF

CG

D

EH

前序序列ABCDEFGH6.16后序线索树:A

BCDEFEnull

17H

只有空指针处才能加线索。线索链表:0A0

0C00B11001E10F1^1G11H16.17

bitree*search(bitree*p)

查找前序线索二叉树上给定结点p的前序后继

{if(p->ltag==1)return(p->rchild);左标记为1时,若p的右子树非空,p的右子树的根p->rchild为p的后继;若右子树为空,p->rchild指向后继

elsereturn(p->lchild);左标记为0时,p的左子女p->lchild为p的后继.}算法终止

6.18bitree*search(b:tree*p)

在后序线索二叉树中查找给定结点的后序前驱的算法

{if(p->rtag==0)retur

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论