#c #pointers #linked-list
#c #указатели #связанный список
Вопрос:
Здесь у меня есть рабочий связанный список, который работает для хранения чисел и подсчета добавленных чисел, но проблема, с которой я сталкиваюсь, заключается в понимании того, как изменить это, чтобы числа не добавлялись только в том порядке, в котором они были введены, есть ли способ легко изменить и исправить это или есть способ изменить мою функцию печати, чтобы она выполняла эту функцию за меня?
код
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)
Комментарии:
1. Это похоже на упражнение по кодированию. Мне не сразу понятно, в чем проблема на самом деле и чего вы пытаетесь достичь
2. Чего я пытаюсь добиться, так это того, чтобы при добавлении чисел в связанный список они добавлялись или, по крайней мере, печатались в порядке возрастания. Потому что мне было трудно понять, как это можно сделать
3. обязательно ли это должен быть связанный список? Я имею в виду, вы можете сделать это со связанными списками, но двоичное дерево, вероятно, было бы лучше. В противном случае просто отсортируйте список, как только закончите со вставками.
4. да, это должно быть сделано с помощью связанного списка, надеялся, что можно изменить или отредактировать только функцию печати, чтобы иметь возможность выдавать результаты в порядке возрастания, но просто был смущен тем, как это можно сделать
5. Слишком большой. Сократите свой вопрос.
Ответ №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).
Комментарии:
1. большое вам спасибо! единственная часть, которая меня немного смущает в вашем коде, — это то, как интерпретировать
if prev portion
. если значение prev не равно null или? Обновлю свой код тем, что у меня есть прямо сейчас, чтобы убедиться, что я все делаю правильно2. Обновлено. В C
if (prev)
совпадает сif (prev != NULL)
(наряду с любым другим ложным значением, таким как 0, чтоNULL
и есть).3. ооо, хорошо, спасибо! И является ли этот последний разрыв внутри последнего оператора else или? Обычно мне нравится использовать все эти навороченные
{}
, чтобы отслеживать это в своей голове. указатель рюкзака в этом случае был бы текущим, верно?4. Причина, по которой я спрашиваю, заключается в том, что по какой-то причине с тем, что у меня есть сейчас, некорректно добавлять числа, если они меньше, или сортировать то, что посередине, обновил мой код выше, но не уверен, где я ошибся
5. Обновлено для добавления фигурных скобок. Нет,
current
это ваш временный указатель, который перемещается по списку.knapsack
это ваш головной указатель.