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)
解决方案
你在正确的轨道上。现在，您的代码可以很好地用于增加现有项目的计数和添加新项目。这是伪代码中的样子（我强烈建议将您的previoustocurrent和tempto重命名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)。
推荐阅读
- python - 每月汇总值后创建新数据框
- java - Linux：驱动程序在目标文件夹中不可执行
- gcc - 两个编译器（clang vs gcc）有不同的信号api？
- scikit-learn - 从 cross_val_score 得到的分数是 RMSE 还是 MSE？
- reactjs - 在 React 的 onClick 事件处理程序中使用 Currying Function 模式的优点和理解
- mongodb - mongodb向数组字段添加值
- sparse-matrix - LASSO 和稀疏解决方案
- xpath - 使用 Xpath，如何从样式标签中获取价值
- mysql - MYSQL 计算从多个键中选择的结果，如果不存在则插入
- javascript - 使用 New York Times API 时定义结果数