#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; }
时间: 2024-03-31 08:34:31 浏览: 82
这是一段 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 20 typedef int KeyType; typedef struct { KeyType key; //InfoType otherinfo; }Redtype; typedef struct { Redtype r[MAXSIZE + 1]; int length; }SqList; int Partition(SqList& L, int low, int high) { int pivotkey; L.r[0] = L.r[low]; pivotkey = L.r[low].key; while (low < high) { while (low < high && L.r[high].key >= pivotkey)--high; L.r[low] = L.r[high]; while (low < high && L.r[low].key <= pivotkey)++low; L.r[high] = L.r[low]; } L.r[low] = L.r[0]; return low; } void Qsort(SqList& L, int low, int high) { if (low < high) { char pivotloc; pivotloc = Partition(L, low, high); Qsort(L, low, pivotloc - 1); Qsort(L, pivotloc +1,high); } } void Quicksort(SqList& L) { Qsort(L, 1, L.length); } int main() { SqList L; int dt[10]; int i; cout << "输入待排序列长度和输入数据"; cin >> L.length; Quicksort(L,1,dt); return 1; }
你的代码中有一些问题。首先,在 main 函数中调用 Quicksort 函数时,传入的参数个数不正确,Quicksort 函数只需要传入一个参数 SqList& L 即可,不需要传入两个参数和一个未定义的数组 dt。其次,在 Qsort 函数中,递归调用 Qsort 函数时,第二个子序列的起始下标应该是 pivotloc + 1,而不是 pivotloc +1。最后,你没有输出排序后的结果。以下是修正后的代码:
```c++
//快速排序
#include<iostream>
using namespace std;
#define MAXSIZE 20
typedef int KeyType;
typedef struct {
KeyType key;
//InfoType otherinfo;
}Redtype;
typedef struct {
Redtype r[MAXSIZE + 1];
int length;
}SqList;
int Partition(SqList& L, int low, int high) {
int pivotkey;
L.r[0] = L.r[low];
pivotkey = L.r[low].key;
while (low < high)
{
while (low < high && L.r[high].key >= pivotkey) --high;
L.r[low] = L.r[high];
while (low < high && L.r[low].key <= pivotkey) ++low;
L.r[high] = L.r[low];
}
L.r[low] = L.r[0];
return low;
}
void Qsort(SqList& L, int low, int high) {
if (low < high)
{
int pivotloc;
pivotloc = Partition(L, low, high);
Qsort(L, low, pivotloc - 1);
Qsort(L, pivotloc + 1, high);
}
}
void Quicksort(SqList& L) {
Qsort(L, 1, L.length);
}
int main() {
SqList L;
int i;
cout << "输入待排序列长度和输入数据: ";
cin >> L.length;
for (i = 1; i <= L.length; i++) {
cin >> L.r[i].key;
}
Quicksort(L);
cout << "排序后的结果:";
for (i = 1; i <= L.length; i++) {
cout << L.r[i].key << " ";
}
cout << endl;
return 0;
}
```
阅读全文