四、希尔排序
已知待排序序列data[n]；希尔排序的增量序列为d[m]，其中d[]序列降序排列，且d[m-1]=1。其方法是对序列进行m趟排序，在第i趟排序中，按增量d[i]把整个序列分成d[i]个子序列，并按直接插入排序的方法对每个子序列进行排序。
希尔排序的程序为：
void shellsort(int *data,int *d,int n,int m)
{ int i,j;
for (i=0;i<m;i++)
for (j=0; （1） ;j++)
shell( （2） );
}
void shell(int *data,int d,int num,int n)
{ int i,j,k,temp;
for (i=1; （3） ;i++)
{ j=0;
temp=data[j+i*d];
while ((j<i)&&( （4） ))
j++;
for (k=j;k<i;k++)
data[k+1]=data[k];
（5） ;
（6） }
}
五、求树的宽度
所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。本算法是按层次遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
int Width(BinTree *T)
{ int front=-1,rear=-1; /* 队列初始化*／
int flag=0,count=0,p;/*p用于指向树中层的最右边的结点，flag记录层中结点数的最大值。*／
if(T!=Null)
{ rear++; （1） ; flag=1; p=rear;
}
while( （2） )
{ front++;
T=q[front];
if(T->lchild!=Null)
{ rear++; （3） ; count++; } //
if(T->rchild!=Null)
{ rear++; q[rear]=T->rchild; （4） ; }
if(front==p) /* 当前层已遍历完毕*/
{ if( （5） ) flag=count; count=0; //
p=rear; /* p指向下一层最右边的结点*/
}
}
return(flag);
}
六、区间覆盖
设在实数轴上有n个点（x0，x1，……，xn-2，xn-1），现在要求用长度为1的单位闭区间去覆盖这n个点，则需要多少个单位闭区间。
int cover(float x[ ], int num)
{ float start[num],end[num];
int i ,j ,flag, count=0;
for (i=0;i<num;i++)
{ flag=1;
for (j=0;j< （1） ;j++)
{ if ((start[j]>x[i])&&(end[j]-x[i]<=1)) （2） ;
else if ( （3） ) end[j]=x[i];
else if ((x[i]>start[j])&&(x[i]<end[j])) flag=0;
if (flag) break;
}
if ( （4） )
{ end[count]=x[i]; （5）; count++; }
}
return count-1;
}
start[count]=x[i]
上一页 [1] [2] [3] [4] 下一页
上一篇文章： 考试辅导：程序员数据结构笔记（五）下一篇文章： 没有了 【
发表评论】【
加入收藏】【
告诉好友】【
打印此文】【
关闭窗口】
