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

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

实现下列函数：

void InsertSort(SqList &L);

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

typedef struct {

RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; } SqList;

void InsertSort(SqList &L) {

int i,j;

for(i=L.length-1;i>0;i--) {

L.r[L.length+1]=L.r[i+1]; if(GT(L.r[i],L.r[i+1])) {

L.r[L.length+1]=L.r[i]; L.r[i]=L.r[i+1]; }

for(j=i+2;LT(L.r[j],L.r[L.length+1]);j++) L.r[j-1]=L.r[j];

L.r[j-1]=L.r[L.length+1]; } }

10.26② 如下所述改写教科书1.4.3节中的起泡排序算法： 将算法中用以起控制作用的布尔变量change改为一个整型变 量，指示每一趟排序中进行交换的最后一个记录的位置，并 以它作为下一趟起泡排序循环终止的控制值。

实现下列函数：

void BubbleSort(SqList &L);

/* 元素比较和交换必须调用以下比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较：\ */

/* Status GT(RedType a, RedType b); 比较：\ */ /* void Swap(RedType &a, RedType &b); 交换 */

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

typedef struct {

RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; } SqList;

比较函数和交换函数:

Status LT(RedType a, RedType b); // 比较函数：\Status GT(RedType a, RedType b); // 比较函数：\void Swap(RedType &a, RedType &b); // 交换函数

void BubbleSort(SqList &L)

/* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较：\ */ /* Status GT(RedType a, RedType b); 比较：\ */ /* void Swap(RedType &a, RedType &b); 交换 */ {

int i,j,change=1;

for(i=L.length;i>1;i=change) {

change=1; for(j=1;j

if(GT(L.r[j],L.r[j+1])) {

Swap(L.r[j],L.r[j+1]); change=j; } } } }

10.32⑤ 荷兰国旗问题：设有一个仅由红、白、兰 这三种颜色的条块组成的条块序列。请编写一个时 间复杂度为O(n)的算法，使得这些条块按红、白、 兰的顺序排好，即排成荷兰国旗图案。

实现下列函数：

void HFlag(FlagList &f)

/* \荷兰国旗\的元素为red，white和blue，*/ /* 分别用字符'0','1'和'2'表示 */

\荷兰国旗\的顺序表的类型FlagList定义如下： #define red '0' #define white '1' #define blue '2'

typedef char ColorType;

typedef struct {

ColorType r[MAX_LENGTH+1]; int length; } FlagList;

void swap(ColorType &a,ColorType &b) {

ColorType temp; temp=a; a=b; b=temp; }

void HFlag(FlagList &f) {

int i,j,k; char c;

for(i=1,j=1,k=f.length;j<=k;) {

c=f.r[j]; if(c==red)

swap(f.r[i++],f.r[j++]); if(c==white) j++; if(c==blue)

swap(f.r[j],f.r[k--]); } }

10.34③ 已知(k1,k2,...,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; h.length=0;

for(i=0;s[i]!='\\0';i++) {

h.length++;

h.r[h.length].key=s[i]; e=h.r[h.length].key; locate=h.length; k=h.length/2;

for(j=h.length;k>0;j=j/2,k=j/2) {

if(e

h.r[j].key=h.r[k].key; locate=k; } }

h.r[locate].key=e; } }

10.35③ 假设定义堆为满足如下性质的完全三叉树：