c - 对链表进行壳排序时出现问题

Question

这是一个学校项目。

我和我的 friend 一直在致力于这个特定的项目，并且已经为此陷入了好几天。

我们有这两种结构...

typedef struct node{
  long value;
  struct node *next;
}Node;


typedef struct list{
  Node *Node;
  struct list *next;
  struct list *prev;
}List; 

名为node的结构本身就是链表，我必须使用这个结构作为链表。

第二个结构称为List，可以是指向节点的指针。

使用第一个结构(以及第二个结构，如果我们选择的话)，我们必须对整数的链接列表进行外壳(插入风格)排序。

我们尝试了两种不同的方法，一种是通过遍历间隙元素来强制排序，确定它们是否需要移动到链表已排序部分的某个位置，然后从头开始遍历链表，直到我们找到在已排序部分中找到比它大的元素。这可行，但运行时间太长(这是一门数据结构和算法类(class)，所以我们必须考虑运行时间)。

我们要实现的方法是使用第二个结构体根据希尔排序来指向间隔有间隙的元素，然后根据间隙序列对链表中的这些值进行排序。

我们知道如何生成序列，但是有人能给我们一些关于实现该算法的提示吗？

我们已经形成了标准链表。

我们认为我们需要创建一个列表创建函数和一个列表插入函数，但之后我们不知道如何启动它。

任何和所有的提示和评论表示赞赏!!!!谢谢!

编辑:在此实现中我无法使用任何数组，该项目是关于链表的分析并将其使用和速度与数组进行比较。

Answer 1

我想我会总结一下评论中所说的内容

1) 最初您需要将所有指针放入一个数组中。

结构节点* element_pointers[大小]。

如果您不确定该结构将包含多少个元素，那么您需要 malloc运行时数组

struct node* element_pointer = malloc(sizeof(struct node*)*number_of elements)

2)当尝试将指针放入数组时，您有两个选择

您可以在创建每个结构时将指针放入数组中，也可以遍历链表并将每个下一个指针放入数组中。

如果你遍历该结构，它将是一个简单的 while 循环

int i =0;
element_pointer[i++] = head; //the pointer to the Head struct//
while( Head->next != NULL){
    i++;
    element_pointer[i] = Head->next;
    head = head->next}

3) 对指针进行排序时。在你的 shell-sort 函数中。

像这样进行比较

 if(element_pointer[j]->value > element_ponter[j+gap]->value)

//必要时交换

4)交换函数是这样的

struct node *temp = element_pointer[j]
element_pointer[j] = element_pointer[j+gap]
element_pointer[j+gap] = temp.

正如吉姆·巴尔特提到的，你也可以对双向链表进行排序，我在 SO 上找到了这个 Sorting doubly linked list in c我也需要学习。