算法与数据结构-c语言描述（第2版）张乃孝版_代码

#include <stdio.h>

#include <stdlib.h>

Include “PriorityQueue.c”

typedef int KeyType;

typedef int DataType;

typedef struct

{ KeyType key; /* 排序码字段 */

DataType info; /* 记录的其它字段 */

void insertSort(SortObject * pvector) { /* 按递增序进行直接插入排序

*/

int i, j;

RecordNode temp;

for( i = 1; i < pvector->n; i++ ) { /* 依次插入记录 R

1

, R

2

…R

n-1

*/

temp = pvector->record[i]; j = i-1;

while ((temp.key < pvector->record[j].key)&&(j>=0) ){ /* 由后向前找插入位置 */

pvector->record[j+1] = pvector->record[j]; j--; }/* 将排序码大于 k

i

的记录后移 */

RecordNode temp;

for( i = 1; i < pvector->n; i++ ) {

temp = pvector->record[i]; left = 0; right = i – 1;/* 置已排序区间的下、上界初值 */

while (left <= right) {

mid=(left+right)/2; /* mid 指向已排序区间的中间位置 */

if (temp.key<pvector->record[mid].key)right=mid-1; /* 插入元素应在左子区间 */

else left=mid+1; /* 插入元素应在右子区间 */

}

for(j=i-1; j>=left; j--) pvector->record[j+1] = pvector->record[j];

struct Node

DataType info; /* 记录的其它字段 */

ListNode *next; /* 记录的指针字段 */

};

head=*plist;

pre=head->next;

if(pre==NULL) return;

now=pre->next;

if(now==NULL) return; /* 为空链表或链表中只有一个结点 */

while( now!=NULL){

q=head; p=head->next;

while(p!=now && p->key<=now->key){q=p;p=p->next;} /* 循环结束找到插入

位置 */

if(p==now) {pre=pre->next;now=pre->next; continue;} /* now 应放在原位

/*Shell 排序*/

void shellSort(SortObject * pvector, int d) { /* 按递增序进行 Shell 排序 */

int i, j, increment;

RecordNode temp;

for (increment = d; increment > 0; increment /= 2) {/* increment 为本趟 shell 排序增量 */

for(i=increment; i<pvector->n; i++){

temp=pvector->record[i]; /* 保存待插入记录 Ri*/

j=i-increment;

while(j>=0 && temp.key<pvector->record[j].key) {/* 查找插入位置 */

pvector->record[j+increment]=temp; /* 插入记录 Ri */

}

}

/*直接选择排序*/

void selectSort(SortObject * pvector) { /* 按递增序进行直接选择排序 */

int i, j, k;

}

}

}

/*堆排序*/

void heapSort(SortObject * pvector ){

for ( i = n/ 2 -1; i >= 0; i--) sift(pvector,n,i); /*首先构造第一个堆*/

for (i = n -1; i > 0; i--) { /*把最小元素与最后一个元素进行交换*/

pvector ->record[0]= pvector ->record[i];

sift(pvector,i,0); /*重新调整建堆，看下面的实现。注意 i 在控制调整范围中的作用*/

}

}

void sift(SortObject * pvector, int size , int p) {

RecordNode temp=pvector->record[p];

int child= 2* p +1;

while(child<size) {

if((child<size-1)&&

(pvector->record[child].key>pvector->record[child+1].key))

child++; /*选择比较小的子结点 */