排序单循环链表

Question

我试图在每次编辑后对单循环链表进行排序。但是我的代码不起作用。我基于选择排序算法。我已经这样做了几个小时，但似乎无法获得正确的代码。

void editList(node *head, int value, int newValue)
{
    node *traverser = head;
    do {
        traverser = traverser -> next;
    }while(traverser -> data != value);

    traverser -> data = newValue;

    node *index;
    node *selection;
    node *temp = new node;

    for(index = head; index -> next != head; index = index -> next) {

        for(selection = head; selection -> next != head; selection = selection -> next) {
            if(index -> data > selection -> data) {
                temp -> data = index-> data;
                index -> data = selection -> data;
                selection -> data = temp -> data;

            }
        }//End of outer loop

    }//End of sorting

    return;
}//End of editList()

Answer 1

在分析提供的源代码时，提出的排序算法非常接近预期'selection sort algorithm'.

存在两个嵌套循环，但执行独立的功能。

步骤 1 - 通过将第一个循环中的条件包含到第二个循环中来执行真正的嵌套循环。

To sort all the list, the selection starts from the next node of the index.

for(index = head; index -> next != head; index = index -> next) {
    // start the selection from the index->next
    for(selection = index->next; selection -> next != head; selection = selection -> next) {
        if(index -> data > selection -> data) {
            temp -> data = index-> data;
            index -> data = selection -> data;
            selection -> data = temp -> data;

        }
    }//End of outer loop
}//End of sorting

Bonus 1 - 因为swap只在data层进行，没有使用临时节点，直接使用整数

// use just an integer
int temp;
...
temp = index-> data;
index -> data = selection -> data;
selection -> data = temp;

而不是：

// allocated but never freed
node *temp = new node;
...
temp -> data = index-> data;
index -> data = selection -> data;
selection -> data = temp -> data;

Bonus 2 - 对于第一个搜索部分来定位具有要替换的 int value 的节点，为什么不使用相同的循环结构来防止 never-ending 如果没有节点具有搜索到的值，则循环。

node *traverser;
// a ending loop to search a value into a circular-list
for(traverser = head; traverser->next != head; traverser = traverser -> next) {
    if (traverser -> data == value) {
        traverser -> data = newValue;
        break;
    }
}

而不是

node *traverser = head;
do {
    traverser = traverser -> next;
}while(traverser -> data != value);

traverser -> data = newValue;

排序单循环链表

Sorting singly circular linked list

algorithm

linked-list

circular-list

data-structures