anyview 数据结构习题集 第10章答案

时间:2024-03-05 11:39:38

10.23② 试以L.r[k+1]作为监视哨改写教材10.2.1节
中给出的直接插入排序算法。其中,L.r[1..k]为待排
序记录且k<maxsize。
实现下列函数:
void InsertSort(SqList &L);
顺序表的类型SqList定义如下:
typedef struct {
KeyType key;

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

//-_-!!题目关于LT这个函数什么也没说  
void InsertSort(SqList &L)  
{      
    int i,j;  
    for(i=2;i<=L.length;++i){  
        if(LT(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[L.length+1],L.r[j]);--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); 交换             */  
//不知道为什么,compare正常,但swap一直为0  
//终于发现原因了,原来这里的Swap是大写的,如果小写的话,可以通过,但是最终swap为 0  
{      
    int len=L.length,last=0;  
    int i;  
    while(len>1){  
        for(i=1;i<len;++i){  
            if(GT(L.r[i],L.r[i+1])){  
                Swap(L.r[i],L.r[i+1]);  
                last=i;                  
            }  
        }  
        if(len!=last){  
            len=last;  
        }  
        else{  
            break;  
        }  
    }  
}

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;

//基本思路:设置low和high来记录两端的位置,按顺序比较i与0和2的关系  
//如果为0则存放在线性表左端,如果为2则存放在线性表右端  
void HFlag(FlagList &f)  
{  
    ColorType t;  
    int i=1,low=1,high=f.length;      
    while(f.r[low]==\'0\'){ //找到第一个不为0的位置  
          ++low;  
          ++i;  
    }  
    while(f.r[high]==\'2\'){ //找到倒数第一个不为2的结点  
            --high;                               
    }            
    while(i<=high){       
        if(f.r[i]==\'0\'&&low!=i){//如果为0,则与low交换,low!=i的判断极为关键  
            t=f.r[i];  
            f.r[i]=f.r[low];  
            f.r[low]=t;  
            ++low;              
        }  
        else if(f.r[i]==\'2\'){//如果为2,则与high交换  
            t=f.r[i];  
            f.r[i]=f.r[high];  
            f.r[high]=t;  
            --high;  
        }  
        else{  
            ++i;  
        }  
        while(f.r[low]==\'0\'){ //找到第一个不为0的位置  
              ++low;  
        }   
        while(f.r[high]==\'2\'){ //找到倒数第一个不为2的结点  
            --high;                               
        }  
    }  
}

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;

/* 
基本思路: 
    题目要求用逐个插入建堆的算法进行建堆,刚看题目莫名奇妙, 
把书上调整大顶堆的算法抄上去,没想到这天杀的题目也提示下这个是小顶堆... 
仔细看清题目之后,发现这道题目很简单。 
假设当前堆已经是小顶堆,当有新的叶子时, 
只需要跟它的双亲结点的key值比较, 
如果比双亲的key小则交换 
一直交换到跟结点。 
*/
  
//堆调整函数  
void HeapAdjust(HeapType &h,int s,int m){  
    int j;  
    KeyType temp;  
    for(j=m;j>s;j/=2){  
        if(h.r[j].key<h.r[j/2].key){//如果比双亲结点小,则交换  
            temp=h.r[j].key;  
            h.r[j].key=h.r[j/2].key;  
            h.r[j/2].key=temp;  
        }         
    }      
}  
void CreateHeap(HeapType &h, char *s)  
{  
    int i;  
    h.length=0;  
    while(s[i]!=\'\0\'){//逐个插入  
        ++h.length;  
        h.r[h.length].key=s[i];  
        HeapAdjust(h,1,h.length);//调整堆  
        ++i;  
    }  
}

10.35③ 假设定义堆为满足如下性质的完全三叉树:
(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 a.key<b.key ?="" true="" :="" false;="" }<br=""> Status GT(RedType a, RedType b)
{ return a.key>b.key ? TRUE : FALSE; }
void Swap(RedType &a, RedType &b)
{ RedType c; c=a; a=b; b=c; }

/* 
解题思路: 
    近视、眼花,以为题目说的跟书上的一样,又是直接抄上去,结果老是不对 
研究后发现,题目说的是完全三叉树.... 
随便列举一棵完全三叉树,仔细观察可以发现, 
若双亲的序号为i,则左、中、右子树为3i-1,3i,3i+1; 
模仿完全二叉树算法即可轻松得出算法  
主要区别在于参数的变化还有三个子树的比较,特别是j<m和j<m-1的判断, 
如果没有判断则会导致compare次数与答案不同(条件判断顺序从左到右) 
*/
  
void HeapAdjust(HeapType &h,int s,int m){  
    int j;  
    RedType rc;  
    rc.key=h.r[s].key;  
    for(j=s*3-1;j<=m;j=3*j-1){  
        if(j<m&<(h.r[j],h.r[j+1])){  
             ++j;  
             if(j<m&<(h.r[j],h.r[j+1])){  
                 ++j;  
             }  
        }  
        else if(j<m-1&<(h.r[j],h.r[j+2])){  
            j+=2;  
        }  
        if(!LT(rc,h.r[j])){  
            break;  
        }  
        h.r[s]=h.r[j];  
        s=j;  
    }  
    h.r[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;  
    if(h.length){  
        for(i=(h.length+1)/3;i>0;--i){  
            HeapAdjust(h,i,h.length);  
        }  
        for(i=h.length;i>1;--i){  
            Swap(h.r[1],h.r[i]);  
            HeapAdjust(h,1,i-1);  
        }  
    }  
}

10.42④ 序列的”中值记录”指的是:如果将此序列排序

后,它是第n/2个记录。试写一个求中值记录的算法。

实现下列函数:

KeyType MidElement(SqList &L);

顺序表的类型SqList定义如下:

typedef struct {

KeyType key;

} RedType;

typedef struct {

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

int length;

} SqList;

//此题神奇之处在于没有告诉你找不到时返回\'#\';  
//效率很低的解法:用另外一个线性表储存本来的元素  
//然后再用效率很低的选择排序  
//最后之间比较  
//估计存在一种边排序边计算的方法,有空再研究~  
KeyType MidElement(SqList &L)  
{  
    int i,j;  
    SqList M;      
    RedType t;  
    if(!L.length){  
        return  \'#\';  
    }  
    for(i=1;i<=L.length;++i){  
        M.r[i]=L.r[i];  
    }  
    for(i=1;i<=L.length;++i){  
        for(j=1;j<=L.length;++j){  
            if(L.r[i].key>L.r[j].key){  
                t=L.r[i];  
                L.r[i]=L.r[j];  
                L.r[j]=t;  
            }  
        }  
    }  
    for(i=1;i<=L.length;++i){  
        if(M.r[i].key==L.r[L.length/2+1].key){  
            return M.r[i].key;  
        }  
    }  
    return  \'#\';  
}

10.43③ 已知记录序列a[1..n] 中的关键字各不相同,

可按如下所述实现计数排序:另设数组c[1..n],对每

个记录a[i], 统计序列中关键字比它小的记录个数存

于c[i], 则c[i]=0的记录必为关键字最小的记录,然

后依c[i]值的大小对a中记录进行重新排列,试编写算

法实现上述排序方法。

实现下列函数:

void CountSort(SqList &L);

/* 采用顺序表存储结构,L.r存储序列a,L.length为n */

/* 在函数内自行定义计数数组c */

顺序表的类型SqList定义如下:

typedef struct {

KeyType key;

} RedType;

typedef struct {

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

int length;

} SqList;

void CountSort(SqList &L)  
/* 采用顺序表存储结构,L.r存储序列a,L.length为n */  
/* 在函数内自行定义计数数组c                     */  
{  
    RedType temp[100];  
    int c[30];  
    int i,j;  
    for(i=1;i<=L.length;++i){//初始化计数数组  
        c[i]=0;  
        temp[i]=L.r[i];  
    }  
    for(i=1;i<=L.length;++i){//统计数据  
        for(j=1;j<=L.length;++j){  
            if(L.r[j].key<L.r[i].key){  
                ++c[i];  
            }  
        }  
    }  
    for(i=0,j=1;i<=L.length-1;++i){  
        for(j=1;j<=L.length;++j){  
            if(c[j]==i){//找到排序后第i+1个元素,位置为j  
                L.r[i+1]=temp[j];  
            }  
        }  
    }  
}