创建一个链接列表，以升序存储项目或按该顺序打印

Question

我这里有一个工作链接列表，用于存储数字和添加的数字的计数，但我遇到的问题是了解如何更改它，以便它不会按照输入的顺序添加数字有没有办法轻松更改和修复此问题，或者有没有办法更改我的打印功能来为我执行此功能？

代码

void KnapsackPrint(const listitemptr *knapsack){
   if(*knapsack==NULL)
       printf("knapsack: \n");
   else{
       listitemptr temp=*knapsack;
       while(temp!=NULL){
           printf("knapsack: %d (%d), ",temp->item,temp->count);
           temp=temp->next;
       }
       printf("\n");
   }
}

        listitemptr KnapsackAdd(listitemptr *knapsack, int item){
   if(*knapsack==NULL){//empty list
       listitemptr newest= malloc(sizeof(struct listitem));
       newest->item=item;
       newest->count=1;
       newest->next=NULL;
       *knapsack = newest;
       return newest;
   }else{
       listitemptr current=*knapsack;
       listitemptr prev=NULL;
       while(current!=NULL){
           if(current->item == item){
               current->count=current->count+1;
               break;
           }else if(current -> item > item){
               listitemptr new_node = malloc(sizeof(struct listitem));
               new_node-> item = item;
               new_node-> count= 1;
               new_node-> next = current;
               if(prev != NULL ){
                   prev ->next = new_node;
               }else {
                   current = new_node;
                   break;
               }

           }
           prev=current;
           current=current->next;
       }
       if(current==NULL){
           listitemptr newest= malloc(sizeof(struct listitem));
           newest->item=item;
           newest->count=1;
           newest->next=NULL;
           prev->next=newest;
           return newest;
       }
       return current;
   }
}

Knapsack.h 和定义

/* knapsack.h
 * implements simple knapsack data structure as a linked list 
 * NOTE: a function may update the value of input argument *knapsack if it changes the first node of the knapsack to another node. Such a change include the case when an item is added to an empty knapsack
 */

/* pointer to linked list node data structure */
typedef struct listitem* listitemptr;
/* data structure to use as linked list nodes */
struct listitem {
  int item;           // actual int item
  unsigned int count; // number of the same item in the knapsack; should be >= 1
  listitemptr next;   // pointer to next item 
};

/*
 * adds an item to a knapsack. Nodes should be in ascending order. You must simply increase the "count" if the item already exist in the knapsack; "count" must be set to 1 for previously-nonexisting items
 * @param knapsack: pointer to a listitemptr, itself pointing to the first item in a knapsack; NULL if knapsack has not been created yet 
 * @param item: integer item to add
 * @return pointer to the listitem added/updated; NULL if unsuccessful 
 */
listitemptr KnapsackAdd(listitemptr *knapsack, int item);

/*
 * removes a value from a knapsack; must update the "count" and delete the associated listitem when count becomes 0 
 * @param knapsack: [see KnapsackAdd() params]; updated to NULL if knapsack becomes empty
 * @param item: integer item to remove
 * @return 0 if successful, -1 otherwise (when item not found or knapsack is empty)
 */
int KnapsackRemove(listitemptr *knapsack, int item);

/*
 * prints integer items (in ascending order) and their counts in a knapsack
 * @param knapsack: [see KnapsackAdd() params]
 * @stdout: for example, "" (nothing) when knapsack==NULL, or "-125 (4), 10 (1), 26 (2)" when items include four of -125, one of 10, and two of 26
 * @return void
 */
void KnapsackPrint(const listitemptr *knapsack);

/*
 * returns count of a specific item in a knapsack
 * @param knapsack: [see KnapsackAdd() params]
 * @param item: integer item to search for
 * @return item count, or 0 if it does not exist
 */
unsigned int KnapsackItemCount(const listitemptr *knapsack, int item);

/*
 * total count of items in the knapsack
 * @param knapsack: [see KnapsackAdd() params]
 * @return total item count. For example, 7 in case the items are "-125 (4), 10 (1), 26 (2)" (see SnapsackPrint() description)
 */
unsigned int KnapsackSize(const listitemptr *knapsack);

**给定当前输出 2 1 **

knapsack: 2(1) 1(1)

**给定 2 1 时所需的输出 **

knapsack: 1(1) 2(1)

Answer 1

你走在正确的道路上。现在，您的代码可以很好地增加现有项目的计数并添加新项目。这是伪代码的样子(我强烈建议将 previous 重命名为 current，将 temp 重命名为 previous，然后在这个假设下继续我的代码——这将使推理插入和遍历变得更加容易):

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
        }
    }
}

如何修改它以添加项目以便我们保留排序顺序？通过在遍历过程中添加另一个比较，我们可以检查当前节点是否大于我们要插入的数字。如果是，我们就知道已经到达了正确的插入点:

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
        }
    }
}

让我们看一个例子:

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].

希望这足以让您相信，如果我们从一个空列表开始并始终使用此排序方案插入，我们可以保证列表排序。

时间复杂度与之前相同:O(n)。