数据结构上机作业题.pdf

数据结构上机实验题：

1.分裂线性表，将线性表L1中奇数存到线性表L2中,偶数存到线性

表L3中

2.编写递归函数，计算二叉树中叶子结点的数目。

3．编写直接插入排序测试程序

4．编程实现顺序检索算法

参考答案：

1.分裂线性表，将L1中奇数存到L2中,偶数存到L3中

#includestdio.h

#defineN100/*预定义最大的数据域空间*/

typedefintdatatype;/*假设数据类型为整型*/

typedefstruct{

datatypedata[N];/*此处假设数据元素只包含一个整型的关键字域*/

intlength;/*线性表长度*/

}seqlist;/*预定义的顺序表类型*/

voidinitseqlist(seqlist*L)//初始化表

{

L-length=0;

}

voidinput(seqlist*L)//输入多个数据创建表

{

datatypex;

initseqlist(L);

while(x)

{

L-data[L-length++]=x;

}

}

voidprint(seqlist*L)

{

inti;

for(i=0;iL-length;i++)

{

}

}

/*分裂线性表，将L1中奇数存到L2中,偶数存到L3中*/

voidsprit(seqlist*L1,seqlist*L2,seqlist*L3)

{

inti,j,k,len;

j=0,k=0;

len=L1-length-1;

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

{if(L1-data[i]%2==0)

L3-data[j++]=L1-data[i];

elseL2-data[k++]=L1-data[i];

}

L2-length=k;L3-length=j;

}

intmain()

{

seqlistL1,L2,L3;

initseqlist(L2);

initseqlist(L3);

input(L1);

sprit(L1,L2,L3);

print(L1);

print(L2);

print(L3);

}

2.编写递归函数算法，计算二叉树中叶子结点的数目。

解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为

叶子，将其打印出来。

法一：核心部分为：

DLR(liuyu*root)/*中序遍历递归函数*/

{if(root!=NULL)

DLR(root-lchild);

DLR(root-rchild);}

return(0);

}

法二：

intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目

{

if(!T)return0;//空树没有叶子

elseif(!T-lchild!T-rchild)return1;//叶子结点

elsereturnLeaf_Count(T-lchild)+Leaf_Count(T-rchild);//左子树的叶子数加

上右子树的叶子数

}//LeafCount_BiTree

3．直接插入排序测试程序

/*定义table*/

#defineMAXSIZE100/*文件中记录个数的最大值*/

typedefintkeytype;/*定义排序码类型为整数类型*/

typedefstruct{

keytypekey;

intother;/*此处还可以定义记录中除排序码外的其它域*/

}recordtype;/*记录类型的定义*/

typedefstruct{

recordtyper[MAXSIZE+1];

intlength;/*