发布时间 : 2024/4/29 21:17:44 星期一 文章常用排序算法课程设计报告更新完毕开始阅读9489155577232f60ddcca1e0

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; ielem[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; nLength; 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

初始化大顶堆

输出堆顶元素,不断调整堆 此句极其重要 利用关键字 调整