#include <iostream> using namespace std; #define MAXSIZE 1000 typedef int KeyType; //关键字项类型定义 typedef int InfoType; //其他数据项类型定义 //typedef string ElemType; typedef struct { KeyType key; InfoType otherinfo; }RedType; //记录类型 typedef struct BSTNode { RedType r[MAXSIZE+1]; int length; }SqList; //直接插入排序 void InsertSort(SqList &L) { int i,j; for( i=2; i <= L.length; i++) { if(L.r[i].key < L.r[i-1].key) { L.r[0] = L.r[i]; //将待插入的记录存在哨兵位置 L.r[i] = L.r[i-1]; //r[i-1]后移 for( j=i-2; L.r[0].key < L.r[j].key; j--)//从后往前寻找插入位置 L.r[j+1] = L.r[j]; //记录逐个后移，直到找到插入位置 L.r[j+1] = L.r[0]; //将r[0]就是r[i]插入到正确位置 }//if }//for } int main() { SqList L; int n,i; cin >> n; L.length=n; for(i=1;i<=n;i++) { cin >> L.r[i].key; } InsertSort(L); for(i=1;i<=n;i++) { cout << L.r[i].key <<" "; } //cout << "Hello world!" << endl; return 0; }

这是一段 C++ 代码，实现了直接插入排序算法。其中定义了关键字项类型为整数型，其他数据项类型为整数型的记录类型 RedType。通过结构体 SqList 定义了一个长度为 MAXSIZE+1 的记录数组 r，以及数组的长度 length。主函数中读入了需要排序的元素个数 n 和每个元素的值，然后调用 InsertSort 函数进行排序。排序完成后，输出排序后的数组。

相关问题

这段代码有什么错误，怎么改正：#include<iostream> using namespace std; #define maxsize 100 #define OK 1 #define ERROR 0 typedef int Status; typedef int ElemType; #define MAXSIZE 100 //最大长度 typedef int KeyType;//关键字类型 typedef struct {//“记录类型 ”的意思 KeyType key; //InfoType otherinfo; }RedType; typedef struct {//“记录类型 ”的意思 RedType r[maxsize + 1];//数组//r[0]不用，是哨兵圣盾 int length;//长度 }SqList; ///////////////////////////////////////////////插入排序////////////////////////////////////////////////////////////// void InsertSort(SqList &L){ int i, j; for(i = 2; i <= L.length;i ++) if(L.r[i].key < L.r[i - 1].key){ L.r[0] = L.r[i]; L.r[i] = L.r[i - 1]; for(j = i - 2; L.r[0].key < L.r[j].key;--j){ L.r[j + 1] = L.r[j]; } L.r[j + 1] = L.r[0]; } } int main(){ SqList SA; cin >> SA.length; InsertSort(SA); /* for(int i = 2; i <= 6;i ++){ for(int j = i; j <= 6 - i; j ++) cout << SA.r[j].key << " "; } */ cout << SA.r[2].key; return 0; }

这段代码有两个错误：

1. 在调用 InsertSort 函数之前，未初始化 SqList 结构体中的元素，即未给 length 赋值。

2. 在 InsertSort 函数中的第 11 行，循环条件应为 L.r[0].key < L.r[j].key，而不是 L.r[0].key < L.r[j]。

修改后的代码如下：

#include<iostream>
using namespace std;

#define maxsize 100
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;
#define MAXSIZE 100     //最大长度
typedef int KeyType;//关键字类型

typedef struct {
    KeyType key;
}RedType;

typedef struct {
    RedType r[maxsize + 1];
    int length;
}SqList;

///////////////////////////////////////////////插入排序//////////////////////////////////////////////////////////////
void InsertSort(SqList &L){
    int i, j;
    for(i = 2; i <= L.length; i++){
        if(L.r[i].key < L.r[i - 1].key){
            L.r[0] = L.r[i];
            L.r[i] = L.r[i - 1];
            for(j = i - 2; L.r[0].key < L.r[j].key; --j){
                L.r[j + 1] = L.r[j];
            }
            L.r[j + 1] = L.r[0];
        }
    }
}

int main(){
    SqList SA;
    cin >> SA.length;
    for(int i = 1; i <= SA.length; i++){
        cin >> SA.r[i].key;
    }
    InsertSort(SA);
    cout << SA.r[2].key;
    return 0;
}

修改后的代码在输入数组元素之后，调用了 InsertSort 函数，对数组进行排序，并输出第三个元素的值。

#include <iostream> using namespace std; #define MAXSIZE 1000 #define T 3 typedef int KeyType; //关键字项类型定义 typedef int InfoType; //其他数据项类型定义 //typedef string ElemType; typedef struct { KeyType key; InfoType otherinfo; }RedType; //记录类型 typedef struct BSTNode { RedType r[MAXSIZE+1]; int length; }SqList; //希尔插入排序 void ShellInsert(SqList &L,int dk) { int i,j; for( i=dk+1; i <= L.length; i++) { if(L.r[i].key < L.r[i-dk].key) { L.r[0] = L.r[i]; //将L.r[i]插入有序增量子表 L.r[i] = L.r[i-1]; //暂存在L.r[0] for( j=i-dk; j>0 && L.r[0].key < L.r[j].key; j-=dk) L.r[j+dk] = L.r[j]; //记录逐个后移，直到找到插入位置 L.r[j+dk] = L.r[0]; //将r[0]就是r[i]插入到正确位置 }//if }//for } //按增量序列dt[0..t-1]对顺序表L进行t趟希尔排序 void ShellSort(SqList &L,int dt[],int t) { for( int k=0;k<t; k++) { ShellInsert(L,dt[k]); }//for } int main() { SqList L; int n,i,dt[T]={5,3,1}; cin >> n; L.length=n; for(i=1;i<=n;i++) { cin >> L.r[i].key; } ShellSort(L,dt,T); for(i=1;i<=n;i++) { cout << L.r[i].key <<" "; } //cout << "Hello world!" << endl; return 0; }

这是一段 C++ 代码，实现了希尔排序算法。其中定义了关键字项类型为整数型，其他数据项类型为整数型的记录类型 RedType。通过结构体 SqList 定义了一个长度为 MAXSIZE+1 的记录数组 r，以及数组的长度 length。主函数中读入了需要排序的元素个数 n 和每个元素的值，以及增量序列 dt。然后调用 ShellSort 函数进行排序。排序过程中，先按照增量序列进行希尔插入排序，然后逐渐缩小增量，直到增量为 1，完成最后一趟直接插入排序。排序完成后，输出排序后的数组。