顾夕xxxxx《xxxxx》课程设计报告
t[i] = INT_MAX; // 头文件中的2147483647 j1 = crunode1; j = crunode;
// 给非叶子结点赋值
while ( j1 ) {
for ( i=j1; i
t[i] < t[i+1] ? (t[(i+1)/2-1]=t[i]) : (t[(i+1)/2-1] = t[i+1]); // 条件？表达式：表达式 j = j1;
j1 = (j1-1) / 2; }
for ( i=0; i
L->elem[i] = t[0]; // 将当前最小值赋给L->elem[i] j1 = 0;
for ( j=1; j
t[2*j1+1] == t[j1] ? (j1=2*j1+1) : (j1=2*j1+2); //if-else语句
t[j1] = INT_MAX; while ( j1 )
{
j1 = (j1+1) / 2 - 1; // 序号为j1的结点的双亲结点序号 t[2*j1+1]
<=
t[2*j1+2]
?
(t[j1]=t[2*j1+1])
:
14
xxxxx《xxxxx》课程设计报告
(t[j1]=t[2*j1+2]);
}
}
if ( (fp = fopen ( \顺序表树形选择排序.txt\ exit ( ERROR );
for ( n=0; n
m_wr = L->elem[n]; fprintf ( fp, \
fclose ( fp ); free ( t ); }
4.7 堆排序
如下：为堆排序算法
void InsertClass::InitHeap ( SqList *L, int n ) {
// 初始化大顶堆 int key = 0;
int i, j, k;
for( i=(n-1)/2; i>=0; i-- ) // 从编号最大的终端节点开始
{
j = 2 * i + 1; // 编号为j的节点是i的左孩子
k = i;
if( L->elem[j] < L->elem[j+1] && j+1
j++; // 找出左右孩子
15
xxxxx《xxxxx》课程设计报告
中较小的节点
while( L->elem[j] > L->elem[k] && 2*k+1 < n) // 编号为i的左孩子与i比较 换
L->elem[k] = L->elem[j];
L->elem[j] = key; k = j;
{
key = L->elem[k]; // 如果大于，则交
j = 2 * k + 1;
if( L->elem[j+1] > L->elem[j] && j+1 < n) // 交换以后可能
造成堆的破坏,需要从交换的节点往后调整 }
// 大顶堆调整
void InsertClass::AdjustHeap(SqList *L,int n) {
int key = 0; }
}
j++;
int i = 0;
int j = 0;
while ( 2*i+1 < n ) // 从树顶往后找
{
j = 2 * i + 1;
if ( L->elem[j] < L->elem[j+1] && j+1<=n ) // 找出左右孩子中较小的节点
j++ ; // 如果左孩子小于
右孩子，则选择右孩子与父结点比较
16
xxxxx《xxxxx》课程设计报告
if ( L->elem[j] > L->elem[i] ) // 交换
{
key = L->elem[i]; // 利用关键字做中间保介质
L->elem[i] = L->elem[j]; L->elem[j] = key;
}
i = j; }
}
// 对顺序表L进行堆排序
void InsertClass::HeapSort(SqList *L) { int key = 0;
int m_wr = 0; int i = 0; unsigned long n; FILE *fp;
if ( !L->elem )
exit ( ERROR );
InitHeap ( L, L->Length ); // for ( i=L->Length-1; i>0; i-- ) // { if ( L->elem[1] > L->elem[0] ) //
break;
key = L->elem[i]; // L->elem[i] = L->elem[0]; L->elem[0] = key;
AdjustHeap ( L, i-1 ); // 17
初始化大顶堆
输出堆顶元素,不断调整堆 此句极其重要 利用关键字 调整