我正在努力提高我在算法和数据结构方面的知识，所以在过去的5-6天里，我一直在尝试在不同的数据结构上实现不同的算法。我有关于单链表、双链表和循环链表的基本知识，并且我可以用数组实现插入排序算法。
然而，使用单链表实现插入排序算法的问题比我最初预期的要大得多。我不喜欢看别人的代码并复制它们来理解一个概念。我真的很喜欢先试着自己做。所以，我写了几行：
#include <stdio.h>
#include <stdlib.h>
typedef struct Node node;
struct Node{
int num;
node *next;
};
void printLinkedList(node *ptr);
void insertionSortLinkedList(node *p,node *head,int sizeOfList);
/* Driver program applying Insertion Sort to a Singly Linked List */
int main(int argc,char *argv[]){
int i, sizeOfList=argc-1;
node *head,*ptr;
ptr=(node*)malloc(sizeOfList*sizeof(node));
for(i=0;i<sizeOfList;i++){
(ptr+i)->num=atoi(argv[i+1]);
(ptr+i)->next=(ptr+i+1);
}
(ptr + sizeOfList-1)->next=NULL;
head=ptr;
printLinkedList(head);
insertionSortLinkedList(ptr,head,sizeOfList);
return 0;
}
void printLinkedList(node *ptr) {
while (ptr != NULL) {
printf("%d ", ptr->num);
ptr=ptr->next;
}
printf("nn");
}
void insertionSortLinkedList(node *p,node *head,int sizeOfList){
int i=0;
int N=1;
int flag;
node *temp;
while(N<sizeOfList){
flag=0;
/* node N > node i */
if((p+N)->num>(p+i)->num){
i++;
}
/* node i >= node N */
else{
/* node i = node N */
if((p+N)->num==(p+i)->num){ // FIRST ERROR HERE. DOES NOT ENTER HERE FOR 2 1 3 1 5 4 3 WHEN 1(i) 2 3 1(N) 5 4 3
/* i = N */
if(i==N){
flag=1;
}
/* i != N */
else{
temp=(p+N);
(p+N-1)->next=(p+N)->next;
temp->next=(p+i)->next;
(p+i)->next=temp;
flag=1;
}
}
/* node i > node N */
else{
/* i = 0 and Head needs to change */
if(i==0){
temp=(p+N);
(p+N-1)->next=(p+N)->next;
temp->next=(p+i);
head=temp;
flag=1;
}
/* i != 0 and Head needs to change */
else{
temp=(p+N);
(p+N-1)->next=(p+N)->next;
temp->next=(p+i);
(p+i-1)->next=temp;
flag=1;
}
}
}
/* Increase N and set i equal zero */
if(flag==1){
i=0;
N++;
}
}
printf("Our ordered values in the LinkedList: ");
printLinkedList(head);
}
我的代码在某个特定点上似乎运行良好。例如，如果我进入终端：
./a.out 2 1 3 1 5 4 3
第一个"；枢轴；工作良好并且算法交换"；2〃；以及"；1〃；。因此我们得到：
1 2 3 1 5 4 3
然后下一个枢轴也工作得很好，并且算法首先比较"；1〃；以及"；3〃；，那么"；2〃；以及"；3〃；并且它决定什么也不做；枢轴"；。所以我们得到：
1 2 3 1 5 4 3
在这一点上，我的算法变得疯狂；1〃；以及"；1〃；决定"；1(第一节点的("；大于"；1(枢轴("；。算法的其余部分不起作用。作为最终结果；排序"；打印出来的阵列是：
1 4
我在其他网站上看到过与链表插入排序相关的问题，但它们遵循的方法与我的代码尝试的方法不同。如果可能的话，我只想解决这个算法背后的错误。如果没有，那么我可能会放弃并像其他代码一样实现代码。如果有人能指导我以正确的心态解决这个问题，或者告诉我为什么这个代码可能不起作用，我将不胜感激。此外，如果这是根本错误的，请告诉我…
您的算法的主要问题是，您将链表结构视为一个数组，并尝试执行p+N等操作…实际上，链表不是数组，因此指向节点的指针不是按顺序放置在内存中，而是分散在地址空间中，操作p+N并不总是指向下一个节点。因此，要迭代列表，必须只使用p->下一句话。
感谢@Mykola的指导，我能够正确地在链表中实现插入排序。我已经意识到，我最大的问题之一是没有仔细处理节点的指针。相反，传递他们的推荐信是一个很大的帮助。我也意识到我没有正确地遍历链表。由于这些更正，我不得不稍微更改一下代码。此外，我还尝试使代码更加清晰，并添加了一个push((函数。
我将在下面包含我的代码，这样，如果有人发现自己处于与我类似的情况，他们可以将其作为参考进行检查：
#include <stdio.h>
#include <stdlib.h>
typedef struct Node node;
struct Node{
int data;
node* next;
};
void printList(node* head);
void push(node** head_ref,int data);
void insertionSort(node** head_ref);
void insertIntoSorted(node** sorted_ref,node* new_node);
/* Driver program that applies insertion sort to singly linked lists */
int main(int argc, char* argv[]){
int i, sizeOfList;
sizeOfList=argc-1;
node *head;
head=NULL;
for(i=sizeOfList;i>0;i--){
push(&head,atoi(argv[i]));
}
/* Print the linked list before the insertion sort */
printf("Your list before the insertion sort is: ");
printList(head);
/* insertion sort function */
insertionSort(&head);
/* Print the linked list after the insertion sort */
printf("Your list after the sort is: ");
printList(head);
return EXIT_SUCCESS;
}
/* Utility function that inserts a new node at the beginning of a linked list */
void push(node** head_ref,int data){
//allocate node and fill
node* new_node;
new_node=(node*)malloc(sizeof(node));
new_node->data=data;
//link
new_node->next=*head_ref;
*head_ref=new_node;
}
/* Utility function to print a linked list */
void printList(node* head){
node* temp;
temp=head;
while(temp!=NULL){
printf("%d ",temp->data);
temp=temp->next;
}
printf("n");
}
/* Function to sort a singly linked list using insertion sort */
void insertionSort(node** head_ref){
/* Initialize the sorted linked list */
node* sorted;
sorted=NULL;
/* Traverse the given linked list and insert every node to "sorted" */
node* current;
current=*head_ref;
while(current!=NULL){
/* Store "next" for next iteration */
node* next;
next=current->next;
/*Insert "current" into the "sorted" linked list */
insertIntoSorted(&sorted, current);
/* Update "current" to the next node */
current=next;
}
*head_ref=sorted;
}
/* Function to insert a given node in the "sorted" linked list. Where
* the insertion sort actually occurs.
*/
void insertIntoSorted(node** sorted_ref,node* new_node){
node* current;
/* Special case for the head end of the "sorted" */
if ((*sorted_ref == NULL) || ((*sorted_ref)->data >= new_node->data))
{
new_node->next = *sorted_ref;
*sorted_ref = new_node;
}
/* Locate the node before the point of insertion */
else
{
current = *sorted_ref;
while ((current->next!=NULL) && (current->next->data < new_node->data)){
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}