数据结构算法设计作业C

数据结构作业算法阅读填空练习题——根据《数据结构题集》中相应题目设计，题号不变，以方便查阅。

阅读下列算法，将应填入其中处的内容，写在题后的解答栏内。

1.19算法说明：算法calculate计算i!⋅2i(i=0,1,…,n-1)的值并分别存入数组a[ARRSIZE]的各个分量中。

对于某个k（0 ≤ k ≤ n-1）,当k!⋅2k>MAXINT时，按出错处理。

n为期望计算的项数，返回j值为实际计算的项数。

Status calculate( int a[ARRSIZE], int n, int &j ){ if( n<1 || n>ARRSIZE ) return ERROR;a[0]=1; f=1; p=1;aborted=FALSE;for( (1) ; i<n && !aborted; i++ ){ f*=i; (2) ;if( (3) ) a[i]=f*p;else (4) ;}if( aborted ) { (5) ; return ERROR;}j=n;return OK;}//calculate解答栏：(1)(2)(3)(4)(5)1.20算法说明：下列算法计算一元多项式P n (x 0)的值，进入算法前，多项式系数a i (i=0,1,…,n)已存放在a[0..n]中。

提示：P n (x)=a n x n+a n-1x n-1+a n-2x n-2+…+a 1x 1+a 0=(…((a n x+a n-1)x+a n-2)x+…+a 1)x+a 0float p( float a[]; int n; float x0 ) { (1) ;for( i=n; i>=0; i-- ) f= (2) ; (3) ; }//p算法中，作为循环体的赋值语句的频度为 （4） ，则整个算法的时间复杂度为 （5） 。

2.19算法说明：已知一带头结点的单链表按值递增有序，L 为其头指针。

下列算法删除表中所有值大于mink 且小于maxk 的结点。

有关类型定义如下：typedef struct LNode { Elemtype data; struct LNode *next; }*LinkList;解答栏：(1) (2)(3) (4) (5)void del_min_max( LinkList L, ElemType mink, ElemType maxk ) { p0=L; p=L->next;while( p && p->data<maxk ) if( (1) ){ (2) ; p=p->next; (3) ; free(s);} else { p0=p; (4) ;} }//del_min_max算法del_min_max 的时间复杂度为 （5） 。

2.22算法说明：下列算法采用插入法将一带头结点的单链表就地逆置，已知L 为其头指针。

void invert( LinkList L ) { (1) ;L->next=NULL; // 建立新的空表 while( (2) ) { s=p; p=p->next; (3) ; (4) ; } }//invert 解答栏：(1) (2) (3) (4) (5)解答栏：(1) (2) (3) (4)算法说明：已知一个带头结点的单向循环链表，其每个结点含3个域：数据域data，指针域pre和next，表中结点通过next域单向循环链接，而pre域均为空值。

下列算法将该单向循环链表改造成为双向循环链表。

有关类型定义如下：typedef struct dulnode {datatype data;struct dulnode *pre,*next;}*linklist;void sing_dulist( linklist da ) // da为头指针{ p0=da; p=da->next; (1) ;while ( (2) ){ (3) ; p=p->next; (4) ;}}//sing_dulist3.18算法说明：算法parenthesis用计数法判别表达式中开、闭括号是否正确配对。

已知表达式存于顺序表sq中，有关类型定义如下：#define LISTSIZE 100 //顺序表存储容量typedef struct{char elem[LISTSIZE]; //顺序表存储空间int length; //顺序表当前长度}sqlist;Status parenthesis( sqlist sq ){ i=0; count=0; (1) ;while ( (2) && match ){ if ( sq.elem[i]=='(' ) count++; else if ( sq.elem[i]=')' )if ( count>0 ) count--; else (3) ;(4) ;};if ( (5) ) match=false; return match 解答栏：(1)(2)(3)(4)解答栏：(1)(2)(3)(4)算法说明：算法matching判别读入的一个以@为结束符的字符序列是否回文。

算法中使用一个不带头结点的双链表作为存储结构，其前半部分为队列，后半部分为栈。

有关类型及变量定义如下：typedef struct DuLNode {char data;struct DuLNode *prior,*next;}DuLNode,*LinkList;LinkList p,q,s;Status matching( void ){ q=s=NULL; // 双链表头、尾指针初始化match=TRUE;ch=getchar();while ( ch!='@' ){ (1) ;p->data=ch; p->prior=s;if (!q) q=p;else (2) ;s=p;ch=getchar();}while ( (3) ){ if ( q->data!=s->data ) match=FALSE;p=q; (4) ; free(p);if (q!=s) { p=s; (5) ; free(p);}}if ( (6) ) free(q);return match; }//matching 解答栏：(1)(2)(3)(4)(5)算法说明：已知串s的存储结构为块大小为1的块链结构，即数据域为字符的不带头结点的单链表。

下列算法判别串s是否具有对称性。

解此类问题最常用的方法是利用栈，而本算法所用的方法称作逆转链法。

有关类型定义如下：typedef struct chunk{char ch;struct chunk *next;}chunk;typedef struct{chunk *head; //串的头指针int length; //串的当前长度}LString;Status symestring( LString s ){ sym=TRUE;pre=p=NULL; suc=s.head;m=s.length/2;for ( i=1; i<=m; i++ ) //扫描链表前半部分，逆转之{ p=suc; suc=p->next; p->next=pre; (1) };if ( s.length % 2==0 ) q=suc;else (2) ;for ( i=m; i>=1; i-- ) //恢复链表前半部分，同时判断串的对称性{ if ( p->ch!=q->ch ) (3) ;(4) ; p->next=suc; suc=p; p=pre;(5) ;}return sym}//symestring 解答栏：(1)(2)(3)(4)(5)5.17算法说明：已知顺序表L中含有n个整数，下列递归函数分别求表中的最大整数和n个整数的平均值。

有关类型定义如下：#define LISTSIZE 100 //顺序表存储容量typedef struct{int elem[LISTSIZE]; //顺序表存储空间int n; //顺序表当前长度}sqlist;int max( sqlist L; int n )// 求顺序表L中前n个整数的最大值（1<=n<=L.n）, n的初始调用值为L.n{ if ( n==1 ) return L.elem[0];else{ (1) ;if ( L.elem[n-1]>temp ) (2) ;else (3) ;}}//maxfloat ave( sqlist L; int n )// 求顺序表L中前n个整数的平均值（1<=n<=L.n）, n的初始调用值为L.n{ if ( n==1 ) return L.elem[0];else return （4） ;}//ave解答栏：(1)(2)(3)(4)算法说明：本算法后序遍历以bt为根指针的二叉链表，算法中使用了一个工作栈s，其元素具有下列类型：typedef enum { L,R } tagtype; // L和R作为进入左子树或右子树的标志typedef struct{bitree ptr; // 指针域tagtype tag; // 标志域}stackelement;void postorder ( bitree bt ){ initstack(s);if (!bt) finished=TRUE;else { finished=FALSE; (1) ; }while ( (2) ){ while ( p ) { x.ptr=p; x.tag=L; push(s,x); (3) ; }pop(s,x); p=x.ptr;while ( !finished && x.tag=R ){ visit( p->data );if (!stackempty(s)) { pop(s,x); p=x.ptr; }else (4) ;}if ( !finished ) { (5) ; push(s,x); (6) ;}}}//postorder解答栏：(1)(2)(3)(4)(5)(6)算法说明：本算法层次次序遍历以bt 为根指针的二叉链表，算法中使用指针数组a[maxnode]作为队列，其中maxnode 不小于二叉链表中的结点总数。

void levelorder( bitree bt ) { front=0; rear=0;if ( bt ) { a[rear]=bt; (1) ;} while ( (2) ){ visit( a[front]->data );if ( (3) ) { a[rear]=a[front]->lchild; rear++; } if ( (4) ) { a[rear]=a[front]->rchild; rear++; } (5) ; } }//levelorder 9.33算法说明：递归算法orderout 从大到小依次输出二叉排序树中所有关键字不小于x 的数据元素。