数据结构算法设计作业c

《数据结构算法设计作业c》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构作业算法阅读填空练习题——根据《数据结构题集》中相应题目设计，题号不变，以方便查阅。阅读下列算法，将应填入其中处的内容，写在题后的解答栏内。1.19算法说明：算法calculate计算i!×2i(i=0,1,…,n-1)的值并分别存入数组a[ARRSIZE]的各个分量中。对于某个k（0£k£n-1）,当k!×2k>MAXINT时，按出错处理。n为期望计算的项数，返回j值为实际计算的项数。Statuscalculate(inta[ARRSIZE],intn,int&j){if(n<1

2、

3、n>ARRSIZE)returnERROR;a[0]

4、=1;f=1;p=1;aborted=FALSE;for((1);i

5、x+an-1)x+an-2)x+…+a1)x+a0floatp(floata[];intn;floatx0){(1);for(i=n;i>=0;i--)f=(2);(3);}//p算法中，作为循环体的赋值语句的频度为（4），则整个算法的时间复杂度为（5）。解答栏：(1)(2)(3)(4)(5)2.19算法说明：已知一带头结点的单链表按值递增有序，L为其头指针。下列算法删除表中所有值大于mink且小于maxk的结点。有关类型定义如下：typedefstructLNode{Elemtypedata;structLNode*next;}*LinkLi

6、st;12voiddel_min_max(LinkListL,ElemTypemink,ElemTypemaxk){p0=L;p=L->next;while(p&&p->datanext;(3);free(s);}else{p0=p;(4);}}//del_min_max算法del_min_max的时间复杂度为（5）。解答栏：(1)(2)(3)(4)(5)2.22算法说明：下列算法采用插入法将一带头结点的单链表就地逆置，已知L为其头指针。voidinvert(LinkListL){(1);L->ne

7、xt=NULL;//建立新的空表while((2)){s=p;p=p->next;(3);(4);}解答栏：(1)(2)(3)(4)}//invert122.32算法说明：已知一个带头结点的单向循环链表，其每个结点含3个域：数据域data，指针域pre和next，表中结点通过next域单向循环链接，而pre域均为空值。下列算法将该单向循环链表改造成为双向循环链表。有关类型定义如下：typedefstructdulnode{datatypedata;structdulnode*pre,*next;}*linklist;解答栏：(1)(2)(3)(

8、4)voidsing_dulist(linklistda)//da为头指针{p0=da;p=da->next;(1);while((2)){(3);p=p->next;(4);}}//sing_dulist3.18算法说明：算法parenthesis用计数法判别表达式中开、闭括号是否正确配对。已知表达式存于顺序表sq中，有关类型定义如下：#defineLISTSIZE100//顺序表存储容量typedefstruct{charelem[LISTSIZE];//顺序表存储空间intlength;//顺序表当前长度}sqlist;Statuspar

9、enthesis(sqlistsq){i=0;count=0;(1);while((2)&&match){if(sq.elem[i]=='(')count++;elseif(sq.elem[i]=')')if(count>0)count--;else(3);(4);};if((5))match=false;returnmatch解答栏：(1)(2)(3)(4)(5)}//parenthesis123.31算法说明：算法matching判别读入的一个以@为结束符的字符序列是否回文。算法中使用一个不带头结点的双链表作为存储结构，其前半部分为队列，后

10、半部分为栈。有关类型及变量定义如下：typedefstructDuLNode{chardata;structDuLNode*prior,*next;}