Tag: 数据结构

如何仅使用Push，Pop，Top，IsEmpty，IsFull对堆栈进行排序？

给定堆栈S，需要仅使用Push ， Pop ， Top ， IsEmpty ， IsFull对堆栈进行排序。 寻找最简单的解决方案。 编辑：删除到位条件。 无法使用其他堆栈或队列。

如何在c或c ++中创建异构链接列表

一个可以保存浮点数，整数，字符等数据和算法的链接列表应该很好而且不是很复杂 我想到了创建一个带有void指针的结构，它将指向后续节点。 但问题是我不能使用带结构的模板。 下到c，我必须测试用户输入的每个字符，以测试它是否是整数，浮点数或字符。然后我们可以进一步 请建议一个有效的算法/代码

Linux内核：为什么’子类’结构将基类信息放在最后？

我正在阅读Linux内核上的Beautiful Code中的章节，作者讨论了Linux内核如何在C语言中实现inheritance（以及其他主题）。 简而言之，定义了一个“基础”结构，为了从中inheritance，“子类”结构将基类的副本放在子类结构定义的末尾 。 然后，作者花了几页来解释一个聪明而复杂的宏，以确定要从对象的基本部分转换为对象的子类部分要返回多少字节。 我的问题：在子类struct中，为什么不将struct struct声明为struct中的第一个东西，而不是最后一个 ？ 首先放置基础结构的主要优点是从基类转换到子类时根本不需要移动指针 – 本质上，执行转换只是告诉编译器让代码使用’额外’子类struct在基类定义的东西之后放置的字段。 只是为了澄清我的问题，让我抛出一些代码： struct device { // this is the ‘base class’ struct int a; int b; //etc } struct usb_device { // this is the ‘subclass’ struct int usb_a; int usb_b; struct device dev; // This is what confuses me – // why put this […]

删除单链接列表中的节点

如何删除单链接列表中的节点，只有一个指针指向要删除的节点？ [开始和结束指针未知，可用信息是指向应删除的节点的指针]

C库用于压缩顺序正整数

我有一个非常普遍的问题，就是为磁盘内的字符串数组创建一个索引。 简而言之，我需要将每个字符串的位置存储在磁盘表示中。 例如，一个非常天真的解决方案是索引数组，如下所示： uint64 idx [] = {0,20,500,1024，…，103434}; 其中第一个字符串位于第0位，第二个字符串位于第20位，第三个位于第500位，第n个位于第103434位。 这些位置总是按顺序排列为非负64位整数。 虽然数字可能会有任何差异，但实际上我认为典型的差异在2 ^ 8到2 ^ 20的范围内。 我希望这个索引在内存中是mmap，并且将随机访问这些位置（假设均匀分布）。 我正在考虑编写自己的代码来进行某种块增量编码或其他更复杂的编码，但是在编码/解码速度和空间之间有很多不同的权衡，我宁愿把工作库作为一个起点。甚至可能在没有任何自定义的情况下解决问题。 任何提示？ 一个c库是理想的，但是c ++也可以让我运行一些初步的基准测试。 如果您还在关注，还有一些细节。 这将用于在库cmph（ http://cmph.sf.net ）上构建类似于cdb（ http://cr.yp.to/cdb/cdbmake.html ）的库。 简而言之，它适用于基于大型磁盘的只读关联映射，内存中的索引很小。 由于它是一个库，我无法控制输入，但我想要优化的典型用例有数百万个值，平均值大小在几千字节范围内，最大值在2 ^ 31。 为了记录，如果我没有找到准备使用的库，我打算在64个整数的块中实现delta编码，其中初始字节指定到目前为止的块偏移量。 块本身将用树索引，给我O（log（n / 64））访问时间。 有太多其他选择，我宁愿不讨论它们。 我真的很期待使用代码而不是如何实现编码的想法。 我将很高兴与大家分享我工作后所做的一切。 感谢您的帮助，如果您有任何疑问，请告诉我。

如何在动态图中避免“堆指针意大利面”？

一般问题 假设您正在编写一个由图形组成的系统，以及可以根据相邻节点的配置激活的图形重写规则。 也就是说，您有一个在运行时期间无法预测地增长/缩小的动态图形。 如果你天真地使用malloc ，新的节点将被分配在内存中的随机位置; 经过足够的时间，你的堆将成为指针意大利面，给你可怕的缓存效率。 是否有任何轻量级的增量技术可以使连接在一起的节点在内存中保持紧密联系 ？ 我尝试了什么 我唯一能想到的是将节点嵌入笛卡尔空间，并使用一些物理弹性模拟来排斥/吸引节点。 那将有线节点保持在一起，但看起来很傻，我想模拟的开销会比缓存效率加速更大。 坚实的例子 这是我正在尝试实施的系统。 这是我试图在C中优化的代码的简短片段。 这个 repo是JS中的原型，工作实现，具有可怕的缓存效率（以及语言本身）。 该video以图形方式显示系统的运行情况。

用C / C ++生成BST超级节点

如何在C / C ++中生成带超级节点的二叉搜索树？

如何使用结构创建数据库表

我正在尝试使用c接口创建和存储数据库。 我有一个包含一些变量和数据类型的结构表。 我如何将它们转换为数据库表。 详情如下。 在，database.c文件中，我初始化了createTable函数和包含约束和数据类型的Folder_table结构，我有一个函数连接到firebird中的数据库。 一旦我读到这个结构，我想知道如何将这个结构转换成表并将其存储在数据库中。 （我可以用sprintf做些什么吗？） **database.c:** #include “/Library/Frameworks/Firebird.framework/Versions/A/Headers/ibase.h” #include #include void* CreateTable(char *tableName, uint rows) { int error = 0; void *table; //// Allocate table table = Allocate(GetTableSize(tableName)*rows); //// List table pointers for(uint rowNumber=0; rowNumber < rows; rowNumber++) { //// Add code to Connect linked list row pointers } return error; } typedef […]

在进入C ++之前我应该​​先学习什么？

我正在学习C，但在那之后或同时，在进入C ++之前我应该​​先学习什么？ 编译器，数据结构，UML或设计模式？（也是在开始学习Win32 API的时候？）我根本不急，所以我可以从最深的开始掌握这些要求。 我只是不想因为粗略和疏忽而迷失方向。 除此之外，哪些数学科目对编码影响最大？ 线性代数，离散数学，微积分？ 如果有人引导我完成这段旅程，我将感激不尽。 我想知道答案有很多问题。 谢谢。

如何生成最大不平衡的AVL树

我编写了一个AVL树的C语言库作为通用分类容器 。 出于测试目的，我希望有一种方法来填充树，使其最大程度地不平衡，即，使其具有包含的节点数的最大高度。 AVL树具有很好的属性，如果从空树开始，按升序（或降序）顺序插入节点，则树始终是完全平衡的（即，对于给定数量的节点，它具有其最小高度）。 从空树T 0开始，为每个节点数n生成精确平衡的AVL树T n的一个整数键序列就是简单的 k 1 = 0 k n + 1 = k n +1，即k n = n-1 我正在寻找一个（希望很简单的）整数键序列，当插入最初空的树T 0时 ，生成最大不平衡的AVL树T 0 ，…，T n 。 我也感兴趣的是一种解决方案，其中只有最后一棵树T n最大程度地不平衡（节点数n将是算法的参数）。 满足约束的解决方案 max（k 1 ，…，k n ） – min（k 1 ，…，k n ）+1≤2n 是可取的，但不是严格要求的。 4 n而不是2 n的关键范围可能是合理的目标。 我无法在互联网上找到关于通过插入生成最大高度的AVL树的任何内容。 当然，我正在寻找的生成树的序列将包括所有所谓的Fibonacci树，它们是具有最小节点数的给定深度的AVL树。 有趣的是，英语维基百科甚至没有在AVL树的文章中提到斐波那契树（也不是斐波那契数字！），而德语维基百科有一篇非常好的文章完全致力于它们。 但对于我的问题，我仍然处于黑暗中。 C语言有点刺耳的黑客是受欢迎的。