关闭

关闭

关闭

封号提示

内容

首页 数据结构算法设计作业C.doc

数据结构算法设计作业C.doc

数据结构算法设计作业C.doc

上传者: snophino 2012-03-01 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《数据结构算法设计作业Cdoc》,可适用于考试题库领域,主题内容包含数据结构作业算法阅读填空练习题根据《数据结构题集》中相应题目设计题号不变以方便查阅。阅读下列算法将应填入其中处的内容写在题后的解答栏内。算法说明:算符等。

数据结构作业算法阅读填空练习题根据《数据结构题集》中相应题目设计题号不变以方便查阅。阅读下列算法将应填入其中处的内容写在题后的解答栏内。算法说明:算法calculate计算i((i(i=,,…,n)的值并分别存入数组aARRSIZE的各个分量中。对于某个k((k(n),当k((k>MAXINT时按出错处理。n为期望计算的项数返回j值为实际计算的项数。Statuscalculate(intaARRSIZE,intn,intj){if(n<||n>ARRSIZE)returnERRORa=f=p=aborted=FALSEfor(()i<n!abortedi){f*=i()if(())ai=f*pelse()}if(aborted){()returnERROR}j=nreturnOK}calculate算法说明:下列算法计算一元多项式Pn(x)的值进入算法前多项式系数ai(i=,,…,n)已存放在an中。提示:Pn(x)=anxnanxnanxn…axa=(…((anxan)xan)x…a)xafloatp(floataintnfloatx){()for(i=ni>=i)f=()()}p算法中作为循环体的赋值语句的频度为()则整个算法的时间复杂度为()。算法说明:已知一带头结点的单链表按值递增有序L为其头指针。下列算法删除表中所有值大于mink且小于maxk的结点。有关类型定义如下:typedefstructLNode{ElemtypedatastructLNode*next}*LinkListvoiddelminmax(LinkListL,ElemTypemink,ElemTypemaxk){p=Lp=L>nextwhile(pp>data<maxk)if(()){()p=p>next()free(s)}else{p=p()}}delminmax算法delminmax的时间复杂度为()。算法说明:下列算法采用插入法将一带头结点的单链表就地逆置已知L为其头指针。voidinvert(LinkListL){()L>next=建立新的空表while(()){s=pp=p>next()()}}invert算法说明:已知一个带头结点的单向循环链表其每个结点含个域:数据域data指针域pre和next表中结点通过next域单向循环链接而pre域均为空值。下列算法将该单向循环链表改造成为双向循环链表。有关类型定义如下:typedefstructdulnode{datatypedatastructdulnode*pre,*next}*linklistvoidsingdulist(linklistda)da为头指针{p=dap=da>next()while(()){()p=p>next()}}singdulist算法说明:算法parenthesis用计数法判别表达式中开、闭括号是否正确配对。已知表达式存于顺序表sq中有关类型定义如下:#defineLISTSIZE顺序表存储容量typedefstruct{charelemLISTSIZE顺序表存储空间intlength顺序表当前长度}sqlistStatusparenthesis(sqlistsq){i=count=()while(()match){if(sqelemi=='(')countelseif(sqelemi=')')if(count>)countelse()()}if(())match=falsereturnmatch}parenthesis算法说明:算法matching判别读入的一个以为结束符的字符序列是否回文。算法中使用一个不带头结点的双链表作为存储结构其前半部分为队列后半部分为栈。有关类型及变量定义如下:typedefstructDuLNode{chardatastructDuLNode*prior,*next}DuLNode,*LinkListLinkListp,q,sStatusmatching(void){q=s=双链表头、尾指针初始化match=TRUEch=getchar()while(ch!=''){()p>data=chp>prior=sif(!q)q=pelse()s=pch=getchar()}while(()){if(q>data!=s>data)match=FALSEp=q()free(p)if(q!=s){p=s()free(p)}}if(())free(q)returnmatch}matching算法说明:已知串s的存储结构为块大小为的块链结构即数据域为字符的不带头结点的单链表。下列算法判别串s是否具有对称性。解此类问题最常用的方法是利用栈而本算法所用的方法称作逆转链法。有关类型定义如下:typedefstructchunk{charchstructchunk*next}chunktypedefstruct{chunk*head串的头指针intlength串的当前长度}LStringStatussymestring(LStrings){sym=TRUEpre=p=suc=sheadm=slengthfor(i=i<=mi)扫描链表前半部分逆转之{p=sucsuc=p>nextp>next=pre()}if(slength==)q=sucelse()for(i=mi>=i)恢复链表前半部分同时判断串的对称性{if(p>ch!=q>ch)()()p>next=sucsuc=pp=pre()}returnsym}symestring算法说明:已知顺序表L中含有n个整数下列递归函数分别求表中的最大整数和n个整数的平均值。有关类型定义如下:#defineLISTSIZE顺序表存储容量typedefstruct{intelemLISTSIZE顺序表存储空间intn顺序表当前长度}sqlistintmax(sqlistLintn)求顺序表L中前n个整数的最大值(<=n<=Ln),n的初始调用值为Ln{if(n==)returnLelemelse{()if(Lelemn>temp)()else()}}maxfloatave(sqlistLintn)求顺序表L中前n个整数的平均值(<=n<=Ln),n的初始调用值为Ln{if(n==)returnLelemelsereturn()}ave算法说明:本算法后序遍历以bt为根指针的二叉链表算法中使用了一个工作栈s其元素具有下列类型:typedefenum{L,R}tagtypeL和R作为进入左子树或右子树的标志typedefstruct{bitreeptr指针域tagtypetag标志域}stackelementvoidpostorder(bitreebt){initstack(s)if(!bt)finished=TRUEelse{finished=FALSE()}while(()){while(p){xptr=pxtag=Lpush(s,x)()}pop(s,x)p=xptrwhile(!finishedxtag=R){visit(p>data)if(!stackempty(s)){pop(s,x)p=xptr}else()}if(!finished){()push(s,x)()}}}postorder算法说明:本算法层次次序遍历以bt为根指针的二叉链表算法中使用指针数组amaxnode作为队列其中maxnode不小于二叉链表中的结点总数。voidlevelorder(bitreebt){front=rear=if(bt){arear=bt()}while(()){visit(afront>data)if(()){arear=afront>lchildrear}if(()){arear=afront>rchildrear}()}}levelorder算法说明:递归算法orderout从大到小依次输出二叉排序树中所有关键字不小于x的数据元素。有关类型定义如下:typedefstruct{keytypekey关键字域infotypeotherinfo其他数据域}elemtypetypedefstructbinode{elemtypedatastructbinode*lchild,*rchild}*bitreevoidorderout(bitreet,keytypex){if(t){()if(())printf(t>data)if(())orderout(t>lchild,x)}}orderout算法说明:已知哈希表的装载因子小于哈希函数hash(key)为关键字key(标识符)的第一个字母在字母表中的序号处理冲突的方法为线性探测法。算法Printkey按关键字中第一个字母的顺序输出哈希表中所有关键字。设关键字中的字母均为大写且表中关键字均以''为结束符。有关类型定义如下:typedefstruct{charkeyMAXSIZE关键字数组anytypeotheritem其他数据项}hashelemtypedefhashelemhashtableM用线性探测法处理冲突的哈希表类型voidprintkey(hashtableht){for(i=i<=i){()while(htjkey!=''){k=()if(k==i)printf(htjkey)()}}}printkey算法说明:算法shakersort对rn中记录序列进行双向起泡排序即相邻两趟以相反的方向进行扫描:第一趟从前向后扫描最终将关键字最大的记录放到最末尾第二趟从后向前扫描最终将关键字最小的记录放到最前面第三趟从前向后……第四趟从后向前……以此类推直至全部记录排好序为止。有关类型定义如下:typedefstruct{keytypekey关键字域infotypeotherinfo其他数据域}rcdtypevoidshakersort(rcdtyper,intn)rn存放记录{i=m=ndo{()for(j=i()j)if(rjkey>rjkey){t=rjrj=rjrj=tswap=TRUE}if(()){swap=FALSEfor(j=ni()j)if(rjkey<rjkey){t=rjrj=rjrj=tswap=TRUE}}i}while(())}shakersort算法说明:算法arrange对数组r中n个关键字取整数值的记录进行整理使所有关键字为负值的记录排在关键字为非负值的记录之前。有关类型定义如下:typedefstruct{intkey关键字项infotypeotherinfo其他数据项}rcdtypevoidarrange(rcdtyper,intn)rn存放数据{i=j=ntemp=riwhile(i<j){while(())jif(i<j){ri=rji}while(())iif(i<j){rj=rij}}()}arrange算法arrange在最坏情况下需进行()次记录的移动。解答栏:()()()()解答栏:()()()()()解答栏:()()()()()解答栏:()()()()解答栏:()()()()()解答栏:()()()()()()解答栏:()()()()()解答栏:()()()()()()解答栏:()()()()()解答栏:()()()解答栏:()()()()()解答栏:()()()()解答栏:()()()()()解答栏:()()()()解答栏:()()()PAGE

职业精品

用户评论

0/200
    暂无评论

精彩专题

上传我的资料

热门资料

资料评价:

/12
0下载券 下载 加入VIP, 送下载券

意见
反馈

返回
顶部

Q