PROSAGA码农传奇-C/C++-创建一个链接列表，按升序存储项目或按该顺序打印

<div class =“post-text”itemprop =“text”>
  
    你走在正确的轨道上。现在，您的代码可以正常增加现有项目的计数并添加新项目。这是伪代码的样子（我强烈建议你重命名
     <code>
 previous
 </code>
     至
     <code>
 current
 </code>
     和
     <code>
 temp
 </code>
     至
     <code>
 previous
 </code>
    ，然后在这个假设下继续我的代码 - 这将使得更容易推理插入和遍历）：
  
   <pre>
 <code>
 function KnapsackAdd(knapsack, item) {
 if knapsack is empty {
 make a new knapsack with one item in it
 }
 else { // there are already items in the knapsack
 current = knapsack head
 prev = null

while current != null {
            if current->item == item {
                current->count++
                break
            }

previous = current
            current = current->next
        }

// we're at the end of the list and didn't find the item
        if current == null {
            add new item to end of list
        }
    }
}

</code>
 </pre>
  
    如何修改这些项目以保存排序顺序？通过在遍历期间添加另一个比较，我们可以检查当前节点是否大于我们要插入的数字。如果是，我们知道我们已经到达了正确的插入点：
  
   <pre>
 <code>
 function KnapsackAdd(knapsack, item) {
 if knapsack is empty {
 make a new knapsack with one item in it
 }
 else { // there are already items in the knapsack
 current = knapsack head
 prev = null

while current != null {
            if current->item == item {
                current->count++
                break
            }
            else if current->item > item { // we're at the sorted insertion point!
                make new_node(item: item, count: 1, next: current)

if prev != null { // we're inserting in the middle of the list
                    prev->next = new_node
                }
                else { // we're inserting at the beginning of the list
                       // so we need to update the head reference
                    set knapsack pointer to new_node
                }

break                 
            }

previous = current
            current = current->next
        }

// we're at the end of the list and didn't find the item
        if current == null {
            add new item to end of list
        }
    }
}

</code>
 </pre>
  
    让我们来看一个例子：
  
   <pre>
 <code>
 knapsack.add(5) // knapsack is [5]

knapsack.add(3)  // when iterating, we see that 5 > 3 and engage the new code
                 // block. We must update the head. knapsack is now [3 -> 5]

knapsack.add(7)  // knapsack is [3 -> 5 -> 7]. The new code block is not executed.

knapsack.add(6)  // when iterating, we see that 7 > 6 and engage the 
                 // new code block. No need to update the head; we use the
                 // previous element to link in the new 6 node.
                 // knapsack is [3 -> 5 -> 6 -> 7].

</code>
 </pre>
  
    希望这足以说服您，如果我们从一个空列表开始并始终使用此排序方案插入，我们可以保证列表排序。
  
  
    时间复杂度与之前相同：O（n）。
  
</DIV>