Создайте связанный список, в котором элементы хранятся в порядке возрастания или распечатываются в этом порядке.

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