Lnked列表：如何在具体案例中最小化时间和空间复杂性 [英] Lnked lists: how to minimize time and space complexity in a concrete case
问题描述
我将尝试简要描述我正在进行的项目然后我会提出我的问题。
项目：
假设您正在经营一家连接买家和卖家的在线商店。所以有一个ITEMS列表和一个买家列表。当买家对产品感到满意时，他将其放入购物篮中并将物品从向其他用户显示的可用物品中移除。
会发生什么：买家可以在不通过结账的情况下退出，因此他选择的项目（如果有的话）应该可以再次供其他用户使用，或者卖家可以从卖家处取消，因此即使在某人的篮子里，该项目也不会再有。此外，我可能会被要求在某个时间打印一份关于当前情况的报告，描述每个买家的篮子。
问题：我有一份采取的行动清单像BUYER1登录，ITEM11待售或BUYER13将ITEM1放入购物篮这样的地方（我们忽略了结账）我想知道哪种数据结构更适合处理这种特殊情况，特别是哪种解决方案在时间和空间复杂性方面是最好的。我应该在C中实现我的项目。
我尝试了什么：
我想出了两个可能的解决方案：我可以将项目数据存储在名为可用项目的结构链接列表（包括ID，价格等字段）中，并将买方数据存储在包含字段的结构的链接列表中命名为篮子，它是项目的链接列表，当买家将产品放入购物篮时，该商品将从可用商品中删除并附加到购物篮。问题可能是当销售被取消时，我不知道是谁将物品放入篮子中，所以我应该通过购买者列表并通过他们的篮子来删除产品。或者我可以在名为let的商品结构中添加一个字段，例如buyerID，我可以将值从0（项目可用）更改为将商品放入购物篮的买家的ID但是当我必须打印时每个买家的报告我必须通过项目清单知道他在买什么。
不知道我提出的解决方案是否有效从时间和空间的复杂性。你能建议我一个更好的解决方案吗？非常感谢大家！感谢任何帮助。
I'll try to describe briefly the project I'm working on and then I'll pose my question.
Project:
Suppose you are running an online shop that connects buyers to sellers. So there is a list of ITEMS and a list of BUYERS. When the buyer is satisfied with a product he puts it in the basket and the item is removed from the available items shown to other users.
What can happen: the buyer can quit without going through the checkout so the items he selected (if any) should be available again for other users or the sell can be called off from the seller so the item is not available no more even if it was in someone's basket. Plus I could be asked to print a report of the current situation at a certain time describing for each buyer its basket.
Question: I have a list of actions that take place like "BUYER1 logs-in", "ITEM11 is for sale" or "BUYER13 puts ITEM1 in the basket" (we neglect the checkout) and I was wondering which data structure is more appropriate to handle this specific case, in particular which solution is the best in terms of time and space complexity. I should realize my project in C.
What I have tried:
I came up with two possible solutions: I could store items data in a linked list of structures (with fields like Id, price etc.) named "available items" and store buyers data in a linked list of structures that contains a field named let's say "basket" which is a linked list of items and when a buyers puts a product in the basket the item is removed from the "available items" and appended to the "basket". The issue could be that when a sell is called off I don't know who put the item in the basket so I should go through the list of buyers and for each of them through their basket to delete the product. Or I could add a field to the items struct named let's say "buyerID" where I could change the value from 0 (the item is available) to the ID of the buyer that put the item in the basket but when I have to print a report for each buyer I have to go through the list of items to know what he is buying.
Don't know if the solutions I came up with are efficient both from the time and space complexity. Could you suggest me a better solution? Thanks a lot in advance to everybody! Any help is appreciated.
推荐答案
我认为我不会使用列表;而是使用两个数组（C允许轻松扩展数组）和指针。
一个数组包含Item记录（int index; int available; int inventory; ...）。 Index是数组中项的索引。它也可以是类似SQL的记录的记录ID。可用包含现有物品的数量并可供出售。库存是现有物品的数量。可用总是小于或等于库存。 （注意，...表示记录中的其他成员。）
第二个数组包含买方记录（int index;字符串名称; Cart * cart ;. ..）。索引与Item索引相同。名称是买方的名称。 Cart是指向Cart记录的指针。
Cart记录包含三个字段（int index; int count; Cart * next; ...）。索引是要购买的项目的项目记录索引。 Count是要购买的商品数量。接下来是指向购物车中下一个项目的指针，如果购物车中没有其他记录，则为null。
使用数组的优点是访问速度和减少空间需求。唯一的主要成本是向Items数组添加一个新项目。但这只发生一次，可以通过将新Item附加到数组的末尾来完成。请注意，一次只需要存在一个买方。
我真的很想绘制这个解决方案，但我不知道如何在解决方案部分。
I don't think I would use a list; but rather use two arrays (C allows extending an array easily) and a pointer.
One array contains Item records (int index; int available; int inventory; ...). Index is the index of the item within the array. It could also be the record id of an SQL-like record. Available contains the number of items that are on-hand and are available for sale. Inventory is the number of items that are on-hand. Available is always less than or equal to Inventory. (Note that "..." means other members in the record.)
The second array contains Buyer records (int index; string name; Cart *cart; ...). Index is the same as the Item index. Name is the buyer's name. Cart is a pointer to a Cart record.
The Cart record contains three fields (int index; int count; Cart *next; ...). Index is the Item record index of an item to be purchased. Count is the number of items to be purchased. Next is a pointer to the next item in the cart or null if there are no further records in the cart.
The advantage of using arrays is the speed of access and reduced space requirement. The only major cost is adding a new item to the Items array. But this occurs only once and can be accomplished by appending the new Item to the end of the array. Note that only one Buyer needs to exist at one time.
I'd really like to have drawn this solution but I do not know how to provide a drawing in the Solutions section.
在现实世界的场景中，每个人都会在基于事务的数据库中运行它。但问题保持不变：如果你在每次更改时更改大数据存储空间。
最好是不操纵数据存储，但在数据结构或数据库中设置一些字段和标志。就像是在一个篮子里（身份证，也许超时）。此外，您还应该有一些关于货物的缓存或额外存储空间，以便更快地完成销售或移除。
In a real world scenario everybody would run this in a transaction based database. But the problems stays the same: if you change your big data storage on every change you loose.
Best is to NOT manipulate the data storage, but set some fields and flags in a data structure or database. Like is in a basket (id and maybe timeout). And you should also have some cache or additional storage about goods in basket for faster completion of sale or removal.
Lnked列表：如何在具体案例中最小化时间和空间复杂性
Lnked lists: how to minimize time and space complexity in a concrete case
正如您已经被告知的那样，链表是这个项目的错误工具。 />
您需要了解数据库和数据库设计。
为什么链表错误？
链接列表是在内存中，它暗示如果程序或服务器停止，一切都会丢失。为了避免这个问题，对于每个操作，你必须在内存中加载列表并将其保存到文件之后，但没有什么可以防止多用户并发。
在列表中搜索1项的复杂性
As you have already been told, linked list is the wrong tool for this project.
You need to learn about databases, and databases design.
Why linked list is wrong?
Linked list is in memory, it imply that if the program or server stops, everything is lost. To avoid this problem, for each operation, you have to load the list in memory and save it to file after, but there is nothing to protect from multiuser concurrency.
complexity to search 1 item in list
Number items 1000 1000000
Linked list
load/save list 1000 1000000
find an item mean 500 500000
find an item max 1000 1000000
indexed database
load/save list no need
find an item mean 10 20
find an item max 10 20
这篇关于Lnked列表：如何在具体案例中最小化时间和空间复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
