厂工数据结构Anyview（C语言版）第三、四章答案

痛定思痛。 2023-01-09 03:42 198阅读 0赞

### 第三、四章 ###

*  第三章
 *   *  一、改写直接插入排序算法
     *  二、改进的冒泡排序
     *  三、计数排序
 *  第四章
 *   *  一、哈希表中关键字的有序输出
     *  二、链地址哈希表的构造

# 第三章 #

## 一、改写直接插入排序算法 ##

【题目】试以顺序表L的L.rcd\[L.length+1\]作为监视哨，改写教材3.2节中给出的升序直接插入排序算法。

顺序表的类型RcdSqList定义如下：  
typedef struct \{  
KeyType key;  
…  
\} RcdType;

typedef struct \{  
RcdType rcd\[MAXSIZE+1\]; // rcd\[0\]闲置  
int length;  
\} RcdSqList;

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

#include "allinclude.h"  //DO NOT edit this line
    void InsertSort(RcdSqList &L){
         
      
      int i,j,l;
      
      l = L.length;
      
      for(i = 1;i < L.length;++i){
        
        
        if(L.rcd[i+1].key < L.rcd[i].key){
        
          
          L.rcd[l+1] = L.rcd[i+1];
          j = i+1;
          
          do{
        
            
            j--;
            L.rcd[j+1] = L.rcd[j];
          }while(L.rcd[l+1].key < L.rcd[j-1].key);
          
          L.rcd[j] = L.rcd[l+1];
        }
      }
    }

## 二、改进的冒泡排序 ##

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

顺序表的类型RcdSqList定义如下：  
typedef struct \{  
KeyType key;  
…  
\} RcdType;

typedef struct \{  
RcdType rcd\[MAXSIZE+1\]; // rcd\[0\]闲置  
int length;  
\} RcdSqList;

实现下列函数：  
void BubbleSort(RcdSqList &L);  
/\* 元素比较和交换必须调用以下比较函数和交换函数：*/  
/* Status LT(RedType a, RedType b); 比较："<" */  
/* Status GT(RedType a, RedType b); 比较：">" */  
/* void Swap(RedType &a, RedType &b); 交换 \*/

比较函数和交换函数:  
Status LT(RedType a, RedType b); // 比较函数："<"  
Status GT(RedType a, RedType b); // 比较函数：">"  
void Swap(RedType &a, RedType &b); // 交换函数

#include "allinclude.h"  //DO NOT edit this line
    void BubbleSort(RcdSqList &L) {
         
    /* 元素比较和交换必须调用以下比较函数和交换函数：*/
    /* Status LT(RedType a, RedType b);   比较："<"  */
    /* Status GT(RedType a, RedType b);   比较：">"  */
    /* void Swap(RedType &a, RedType &b); 交换       */
        // Add your code here
        
        int i,j,change,n;
        
        change = 0;
        n = L.length;
        
        for(i = n;i >= 1;i--){
        
          
          //如果进行了交换，就将上一次交换的位置作为下一趟排序循环的终止控制值
            if (change){
        
               
                i = change;
                change = 0;
            }   
            
          for(j = 1;j < i;j++){
        
            
            if(GT(L.rcd[j],L.rcd[j+1])){
        
              
              Swap(L.rcd[j],L.rcd[j+1]);
              change = j;
            }
          }
          
          //如果某趟没进行交换，则已排好，不用再循环
          if(!change) break;
        }
    }

## 三、计数排序 ##

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

顺序表的类型RcdSqList定义如下：  
typedef struct \{  
KeyType key;  
…  
\} RcdType;

typedef struct \{  
RcdType rcd\[MAXSIZE+1\]; // rcd\[0\]闲置  
int length;  
\} RcdSqList;

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

#include "allinclude.h"  //DO NOT edit this line
    void CountSort(RcdSqList &L){
        
    /* 采用顺序表存储结构，在函数内自行定义计数数组c */
      // Add your code here;
      
      int i,j,n;
      RcdType L0[n+1];
      
      n = L.length;
      
      int c[n+1] = {
        0};
      
      for(i = 1;i <= n;i++){
        
        
        for(j = 1;j <= n;j++){
        
          
          if(L.rcd[i].key > L.rcd[j].key) c[i]++;
        }
      }
      
      //把记录序列存到另一个序列中
      for(i = 1;i <= n;i++) L0[i] = L.rcd[i];
      
      //利用数组c各元素的值将记录重新排序
      for(i = 1;i <= n;i++) L.rcd[c[i]+1] = L0[i];
    }

# 第四章 #

## 一、哈希表中关键字的有序输出 ##

【题目】已知某哈希表的装载因子小于1，哈希函数H(key)为关键字(标识符)的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。

哈希表的类型HashTable定义如下：  
\#define SUCCESS 1  
\#define UNSUCCESS 0  
\#define DUPLICATE -1  
typedef char StrKeyType\[4\];  
typedef struct \{  
StrKeyType key; // 关键字项  
int tag; // 标记 0:空；1:有效; -1:已删除  
void \*any; // 其他信息  
\} RcdType;

typedef struct \{  
RcdType \*rcd; // 存储空间基址  
int size; // 哈希表容量  
int count; // 表中当前记录个数  
\} HashTable;

实现下列函数：  
void PrintKeys(HashTable ht, void(*print)(StrKeyType));  
/* 依题意用print输出关键字 \*/

#include "allinclude.h"  //DO NOT edit this line
    void PrintKeys(HashTable ht, void(*print)(StrKeyType)){
        
    /* 依题意用print输出关键字 */
    
      int i;
      
      char c;
      
      for(c = 'A';c <= 'Z';c++){
        
        
        for(i = 0;i < ht.size;i++){
        
          
          if(ht.rcd[i].tag == DUPLICATE) continue;
          
          if(ht.rcd[i].key[0] == c) print(ht.rcd[i].key);
         }
      }
    }

## 二、链地址哈希表的构造 ##

【题目】假设哈希表长为m，哈希函数为H(x)，用链地址法处理冲突。试编写输入一组关键字并建造哈希表的算法。

哈希表的类型ChainHashTab定义如下：  
\#define NUM 7  
\#define NULLKEY -1  
\#define SUCCESS 1  
\#define UNSUCCESS 0  
\#define DUPLICATE -1

typedef char HKeyType;

typedef struct HNode \{  
HKeyType data;  
struct HNode\* next;  
\}\*HLink;

typedef struct \{  
HLink \*rcd; // 指针存储基址，动态分配数组  
int count; // 当前表中含有的记录个数  
int size; // 哈希表的当前容量  
\}ChainHashTab; // 链地址哈希表

int Hash(ChainHashTab H, HKeyType k) \{ // 哈希函数  
return k % H.size;  
\}

Status Collision(ChainHashTab H, HLink &p) \{  
// 求得下一个探查地址p  
if (p && p->next) \{  
p = p->next;  
return SUCCESS;  
\} else return UNSUCCESS;  
\}

实现下列函数：  
int BuildHashTab(ChainHashTab &H, int n, HKeyType es\[\]);  
/\* 直接调用下列函数 */  
/* 哈希函数： */  
/* int Hash(ChainHashTab H, HKeyType k); */  
/* 冲突处理函数： */  
/* int Collision(ChainHashTab H, HLink &p); \*/

#include "allinclude.h"  //DO NOT edit this line
    
    int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]){
        //n是关键字数组的长度！
    /* 直接调用下列函数                             */
    /* 哈希函数：                                   */
    /*    int Hash(ChainHashTab H, HKeyType k);     */
    /* 冲突处理函数：                               */
    /*    int Collision(ChainHashTab H, HLink &p);  */
      int i,m,j = 0;
      HLink p,q;
      
      //初始化哈希表，置空
      H.count = 0;
      H.size = NUM;
      H.rcd = (HLink *)malloc(NUM*sizeof(HLink));
      for(i = 0;i < H.size;i++) H.rcd[i] = NULL;
     
      //遍历每个关键字 
      for(i = 0;i < n;i++){
        
        
        p = (HLink)malloc(sizeof(HLink));
        p->next = NULL;
        p->data = es[i];
        
        m = Hash(H,es[i]);
        
        if(H.rcd[m]){
        
          
          q = H.rcd[m];
          
          while(q){
        
            
            if(p->data == q->data) j =1;//用j记住相同的关键字，如果关键字相同就不用插入
            q = q->next;
          }
          
          if(!j){
        
            
            //插入到表头
            p->next = H.rcd[m];
            H.rcd[m] = p;
          } 
          j = 0;
        
         }
      
          else H.rcd[m] = p;//不加else会出问题
          H.count++;
       }
    }