希尔排序问题（代码运行不成功）？

Question

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define error 0
#define ok 1
#define MAXSIZE 24
#define OVERFLOW -2
typedef struct sq
{
    int arr[MAXSIZE+1];
    int length;
}sqlist;

int initlist(sqlist *p)
{
    p=new sqlist;
    if(!p->arr) exit(OVERFLOW);
    p->length=0;
    printf("初始化成功\n");
}
int listinsert(sqlist *L,int i,int e)
{
    if((i<1)||(i>L->length+1))
    return error;
    if(L->length==MAXSIZE)
    return error;
    for(int j=L->length-1;j>=i-1;i--)
    {
        L->arr[j+1]=L->arr[j];    
    }
    L->arr[i-1]=e;
    ++L->length;
}

void print(sqlist L)
{
    for(int i=0;i<L.length;i++)
    {
        printf("%d\t",L.arr[i]);
    }
}
//一趟希尔排序 
void shellinsert(sqlist *L,int dk)
{
    int j;
    for(int i=dk+1;i<L->length;i++)
     if(L->arr[i]<L->arr[i-dk])
     {
         L->arr[0]=L->arr[i];//暂存arr【0】中
         for(j=i-dk;j>0&&L->arr[0]<L->arr[j];j-=dk)
         L->arr[j+dk]=L->arr[j];//记录后移直到找到插入位置
        L->arr[j+dk]=L->arr[0];
     }
}
//按增量序列进行希尔排序 
void shellsort(sqlist *L,int gap[],int t)
{
    for(int k=0;k<t;++k)
        shellinsert(L,gap[k]);
 } 
int main() 
{
    sqlist L;
    initlist(&L);
    listinsert(&L,1,49);//插入数据 
    listinsert(&L,2,38);
    listinsert(&L,3,65);
    listinsert(&L,4,97);
    listinsert(&L,5,76);
    listinsert(&L,6,13);
    listinsert(&L,7,27);
    listinsert(&L,10,49);
    print(L);
    int gap[3]={4,2,1};//增量列表 
    shellsort(&L,gap[3],3);// 
    return 0;
}

75 20 d:\Users\HP\Desktop\计算机课程\希尔排序.cpp [Error] invalid conversion from 'int' to 'int*' [-fpermissive]
56 6 d:\Users\HP\Desktop\计算机课程\希尔排序.cpp [Note] initializing argument 2 of 'void shellsort(sqlist, int, int)'

Answer 1

你贴那个语法错误自己看看就应该明白是啥错。

希尔排序不熟，只记得好像是分组再加插入排序实现的。我不说算法，我只说这个代码里有些地方语法不对，或者需要优化的地方。

---

gap[3] 是一个 int 类型，但是参数需要的是一个 int[]，也就是 const int* 类型，所以报错这里需要给 &gap[3]（没去检查逻辑，只从语法上来说）

---

用到了 new，那说明是 C++，既然是 C++，头文件应该使用 c 字头的。

#include <cstdio>
#include <cstdlib>

而且使用 new 不需要 malloc.h

---

命名，常量（#define 定义的）通常会使用 CONSTANT_CASE 命名规则，在这里就是定义成全大写字母。

#define ERROR 0
#define OK 1
#define MAXSIZE 24
#define OVERFLOW -2

结构体，或者类一般使用 Pascal 命令规则，比如 Sq 或 SqList 等。

局部变量、参数在 C 中习惯用 snake_case，但在 CPP 中可以跟 Java 一样使用 camelCase。

全局函数也是 camelCase，如 listInsert。

另外，既然都用 C++ 了， Sq 完全可以定义成类，把部分函数改为其方法。这个需要熟悉 CPP 语法和 OOP 方法，所以不展开说了。

---

C/C++ 数组都是 0 开始索引，但从 listinsert 的使用来看，是给的正整数索引，所以 listinsert 的 int i（index，索引） 其实应该是 pos（position，位置），通过 pos - 1 来得到索引。不管参数本身是什么，计算的时候都使用索引会更方便。

int listInsert(SqList* list, int pos, int value) {
    int idx = pos - 1;
    if ((idx < 0) || (idx > list->length) || list->length == MAXSIZE) {
        return ERROR;
    }

......

另外这里参数是定义的 SqList*，也就是指针。因为里面没做指针运算，定义成 引用可能用起来会更方便一些（使用 . 而不是 ->），

---

在 listinsert 中有一处逻辑错误。

    for (int j = L->length - 1; j >= i - 1; i--)
//          ^^^ 循环变量是 j
//                                         ^^^ 但变化的是 i

这个错误主要是因为我们习惯用 i 作为循环变量，当用其他名称作为循环变量的时候，就容易写错。根据上面的代码，把变量名语义化之后，其实就不容易出错了

    for (int j = list->length - 1; j >= idx; j--) {
        arr[j + 1] = arr[j];
    }

---

定义结构体的时候可以初始化，比如

typedef struct Sq {
    int arr[MAXSIZE + 1];
    int length = 0;
} SqList;

因为 arr[] 的内容不需要初始化，所以在定义时就初始化了 length 之后，就不再需要 initlist() 了，何况这里还用错了。

---

看 main 里这段代码

    SqList L;
    initlist(&L);

这里 L 已经是定义的实例，所以在 initlist 是不需要再分配空间的，但是代码里却让它指向了一个新的 sqlist，所以两个实例空间至少有一个不再被引用，可能会存在内存泄漏。

---

看看 print 的定义 void print(SqList L)，这里参数是实例类型，传入的时候按 C/C++ 的规则会拷贝一份 arr 数组会不会拷贝我不太记得了，可以试试。但是这里实际应该使用的是引用或者指针。因为 print 不会去修改数据，可以使用 const 修饰

void print(const SqList& L)

Answer 2

楼上的大佬回答的很好了，补充下

for(j=i-dk;j>0&&L->arr[0]<L->arr[j];j-=dk)
L->arr[j+dk]=L->arr[j];//记录后移直到找到插入位置
L->arr[j+dk]=L->arr[0];

这里我不确定你是否下面两句都是在for循环里面，如果是需要用括号括起来，不是的话，格式化写好点
另外楼上说的 void print(SqList L) 这种是会拷贝的，用引用好些
最终，如果你用 new 申请了内存，结束时需要 delete 释放变量