数据结构作业系统_第十章答案

② 试以[k+1]作为监视哨改写教材节
中给出的直接插入排序算法。其中，[1..k]为待排
序记录且k

实现下列函数：
void InsertSort(SqList &L);

顺序表的类型SqList定义如下：
typedef struct {
KeyType key;
...
} RedType;

typedef struct {
RedType r[MAXSIZE+1]; .
} RedType;

typedef struct {
RedType r[MAXSIZE+1]; .,kp)是堆，则可以写一个时
间复杂度为O(log(n))的算法将(k1,k2,...,kp,kp+1)
调整为堆。试编写"从p=1起，逐个插入建堆"的算法，
并讨论由此方法建堆的时间复杂度。

实现下列函数：
void CreateHeap(HeapType &h, char *s);

堆（顺序表）的类型HeapType定义如下：
typedef char KeyType;

typedef struct {
KeyType key;
... ...
} RedType;

typedef struct {
RedType r[MAXSIZE+1];
int length;
} SqList, HeapType;

void CreateHeap(HeapType &h, char *s)
{
int i,j,locate,k;
KeyType e;
=0;
for(i=0;s[i]!='\0';i++)
{
++;
[].key=s[i];
e=[].key;
locate=;
k=2;
for(j=;k>0;j=j/2,k=j/2)
{
if(e<[k].key)
{
[j].key=[k].key;
locate=k;
}
}
[locate].key=e;
}
}

③ 假设定义堆为满足如下性质的完全三叉树：
(1) 空树为堆；
(2) 根结点的值不小于所有子树根的值，且所有子树
均为堆。
编写利用上述定义的堆进行排序的算法，并分析推导
算法的时间复杂度。

实现下列函数：
void HeapSort(HeapType &h);

堆（顺序表）的类型HeapType定义如下：
typedef char KeyType;

typedef struct {
KeyType key;
... ...
} RedType;

typedef struct {
RedType r[MAXSIZE+1];
int length;
} SqList, HeapType;

比较函数和交换函数:
Status LT(RedType a, RedType b)
{ return < TRUE : FALSE; }
Status GT(RedType a, RedType b)
{ return > TRUE : FALSE; }
void Swap(RedType &a, RedType &b)
{ RedType c; c=a; a=b; b=c; }

void HeapAdjust(HeapType &H,int s,int m)
{
int j,flag;
RedType rc;
rc=[s];
for(j=3*s-1;j<=m;j=3*j-1)
{
flag=0; printf("Do %d\n ",j);
if(jif(flag){if(jelse if(j+1if(!LT(rc,[j]))break;
[s]=[j];
s=j;
}
[s]=rc;
}
void HeapSort(HeapType &h)
/* 元素比较和交换必须调用以下比较函数和交换函数：*/
/* Status LT(RedType a, RedType b); 比较："<" */
/* Status GT(RedType a, RedType b); 比较：">" */
/* void Swap(RedType &a, RedType &b); 交换 */
{
int i;
.
} RedType;

typedef struct {
RedType r[MAXSIZE+1]; ey)
{
temp=[j];
k=j;
}
temp=[i];
[i]=[k];
[k]=temp;
}
if%2==0)n=2;
else n=2+1;
return [n].key;
}

③ 已知记录序列a[1..n] 中的关键字各不相同，
可按如下所述实现计数排序：另设数组c[1..n]，对每
个记录a[i]， 统计序列中关键字比它小的记录个数存
于c[i]， 则c[i]=0的记录必为关键字最小的记录，然
后依c[i]值的大小对a中记录进行重新排列，试编写算
法实现上述排序方法。

实现下列函数：
void CountSort(SqList &L);
/* 采用顺序表存储结构，存储序列a，为n */
/* 在函数内自行定义计数数组c */

顺序表的类型SqList定义如下：
typedef struct {
KeyType key;
...
} RedType;

typedef struct {
RedType r[MAXSIZE+1]; ey>[j].key)
count++;
c[i-1]=count;
}
for(i=1;i<=;i++)
[i]=[i];
=;
for(i=0;i<;i++)
[c[i]+1]=[i+1];
}