华师网络学院作业答案-数据结构写作题.docx

设计一个递归算法，求二叉树t中度为1的结点数。设二叉链表类型定义如下。

typedefintdatatype; //结点的数据类型，假设为int

typedefstructNODE*pointer;//结点指针类型

structNODE{datatypedata;pointerlchild,rchild;};

typedefpointerbitree;//根指针类型

答案:

intsum1(bitreet){intL,R;

if(t==NULL)return0;

L=sum1(t-lchild);

R=sum1(t-rchild);

if((t-lchild==NULLt-rchild!=NULL),,(t-lchild!=NULLt-rchild==NULL))returnL+R+1;

elsereturnL+R;}

设计递归算法，判断二叉树t中是否所有结点都为正数。

二叉链表的类型定义如下：

typedefintdatatype; //结点的数据类型，假设为int

typedefstructNODE*pointer;//结点指针类型

structNODE{datatypedata;pointerlchild,rchild;};

typedefpointerbitree; //根指针类型

答案:

intdetect(bitreet){intL,R;

if(t==NULL)return1;

if(t-data=0)return0;

returndetect(t-lchild)detect(t-rchild);}

设计算法将顺序表L中所有的小写字符都移动到表的前端，要求元素的移动次数尽量少。顺序表类型定义如下：

typedefchardatatype;//结点的数据类型，假设为char

constintmaxsize=100;//最大表长，假设为100

}

}

}

}

typedefstruct{

datatypedata[maxsize];//线性表的存储向量，第一个结点是data[0]

intn; //线性表的当前长度

}sqlist; //顺序表类型

答案:

voidmoves(sqlist*L){inti,j;datatypex;i=1;j=L-n;while(ij){

while((L-data[i]=aL-data[i]=z)ij)i++;while((L-data[j]a,,L-data[i]z)ij)j--;if(ij){

x=L-data[i];L-data[i]=L-data[j];L-data[j]=x;i++;j--;

}}}

设计算法，将顺序表L中所有的负数都移动到表的后端，要求移动次数尽量少。顺序表类型定义如下：

typedefintdatatype;//结点的数据类型，假设为int

constintmaxsize=100;//最大表长，假设为100

typedefstruct{

datatypedata[maxsize];//线性表的存储向量，第一个结点是data[0]

intn; //线性表的当前长度

}sqlist; //顺序表类型

答案:

voidmoves(sqlist*L){inti,j;datatypex;i=1;j=L-n;while(ij){

while(L-data[i]=0ij)i++;

while(L-data[j]0ij)j--;if(ij){

x=L-data[i];L-data[i]=L-data[j];L-data[j]=x;i++;j--;

设计算法将顺序表L中所有的正数都删除，要求元素的移动次数尽量少。顺序表类型定义如下：

typedefintdatatype;//结点的数据类型，假设为int

constintmaxsize=100;//最大表长，假设为100typedefstruct{

datatypedata[maxsize];//线性表的存储向量，第一个结点是data[0]

intn; //线性表的当前长度

}sqlist; //顺序表类型

答案:

voiddels(sqlist*L){ints,i;

s=0;

for(i=0;in;i++)

if(L-data[i]0)s++;

elseif(s0)L-data[i-s]=l-data[i];

L-n=L-n-s;}

设计算法将顺序表L中所有的数字字符都移动到表的后端