![]() |
#2
pangding2010-10-10 02:01
|
我学习数据结构用的书是《数据结构教程(C++版)》
这是一个线性表的归并算法。
第4章讲线性表,第一个程序是这样的。

/*例如:有两个线性表LA=(1,5,7,15)
LB=(3,6,8,9,13,15,17)
则: LC=(1,3,6,8,9,13,15,15,17)
上述问题要求可知,LC中的数据元素或是LA中的数据元素,或是LB中的数据元素,则首先设LC为空表,然后将LA或LBs中的元素逐个插入到LC当中。
为使LC中元素按值非递减排列,可设两个指针i,j分别向LA和LB中的某个元素,若设i当所指的元素为a,j所指的元素为b则当前应插LC元素c为
|-> b a>b
c=|-> a a=b
|-> a a<b
显然,设指针i的j的初使值为1,在所指元素插入LC之后,指针在表LA或LB中将顺序后移。
*/
template<class T>
class merge<T>::
void MergetList(T La,T Lb, T Lc)
{
/*已知线性表La和Lb中的数据元素按值非递减排列*/
/*归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列*/
InitList(Lc);
i=j=1;k=0;
La_len=ListLength(La);
Lb_len=ListLength(Lb);
while((i<La_len)&&(j<=Lb_len))
{
GetElem(La,i,ai);
GetElem(Lb,j,bj);
if(ai<bj)
{
ListInsert(Lc,++k,ai);
++i;
}
else if (ai==bj)
{
ListInsert(Lc,++k,ai);++i;++j;
}
else
{
ListInsert(Lc,++k,bj);++i;++j;
}
}
while(i<=La_len)
{
/*如果La没有取完,则将La中的所剩元素插入到表Lc中*/
GetElem(La,i++,ai);
ListInsert(Lc,++k,ai);
}
while(j<=Lb_len)
{
/*如果La没有取完,则将La中的所剩元素插入到表Lc中*/
GetElem(La,j++,bj);
ListInsert(Lc,++k,bj);
}
}/***********************************************************************-*/
/* MergeList */
/************************************************************************/
我有几个问题要问大家:LB=(3,6,8,9,13,15,17)
则: LC=(1,3,6,8,9,13,15,15,17)
上述问题要求可知,LC中的数据元素或是LA中的数据元素,或是LB中的数据元素,则首先设LC为空表,然后将LA或LBs中的元素逐个插入到LC当中。
为使LC中元素按值非递减排列,可设两个指针i,j分别向LA和LB中的某个元素,若设i当所指的元素为a,j所指的元素为b则当前应插LC元素c为
|-> b a>b
c=|-> a a=b
|-> a a<b
显然,设指针i的j的初使值为1,在所指元素插入LC之后,指针在表LA或LB中将顺序后移。
*/
template<class T>
class merge<T>::
void MergetList(T La,T Lb, T Lc)
{
/*已知线性表La和Lb中的数据元素按值非递减排列*/
/*归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列*/
InitList(Lc);
i=j=1;k=0;
La_len=ListLength(La);
Lb_len=ListLength(Lb);
while((i<La_len)&&(j<=Lb_len))
{
GetElem(La,i,ai);
GetElem(Lb,j,bj);
if(ai<bj)
{
ListInsert(Lc,++k,ai);
++i;
}
else if (ai==bj)
{
ListInsert(Lc,++k,ai);++i;++j;
}
else
{
ListInsert(Lc,++k,bj);++i;++j;
}
}
while(i<=La_len)
{
/*如果La没有取完,则将La中的所剩元素插入到表Lc中*/
GetElem(La,i++,ai);
ListInsert(Lc,++k,ai);
}
while(j<=Lb_len)
{
/*如果La没有取完,则将La中的所剩元素插入到表Lc中*/
GetElem(La,j++,bj);
ListInsert(Lc,++k,bj);
}
}/***********************************************************************-*/
/* MergeList */
/************************************************************************/
1.为什么没有 main()函数,难道这个只讲算法?
2.函数InitList() GetElem()等好多函数没有声明怎么就用啊。
[ 本帖最后由 xtayaitak 于 2010-10-10 00:54 编辑 ]