数据结构

为什么叫补码(Two’s complement) 计算机的加减法运算天生是一个模2^N的同余类上的运算，满2^N会抛弃进位，那表示有符号数时使用同余类代表很正常吧，比如-1 = 2^N -1 (mod 2^N)，-2 = 2^N-2 (mod 2^N)，这实际上就是补码了。

关于位图存储与数组下标存储的探讨 最近在看《编程珠玑》，书中的第一章提到了位图。位图存储使用二进制位的位数信息，来表示数字。例如，存储1、3、4、6、8，这五个数字， 可以使用<1, 0, 1, 1, 0, 1, 0, 1>这样的向量来表示，这样可以大大减少存储空间， 只用了一个字节（8bit），就可以存储原来需要的8个数字才能表示的信息。 当我跟朋友谈到这个方法时，他却产生了质疑，他觉得这样不如直接按照数组下标存储来的快。他认为数组下标直接存储，直接一步完成，二位图则需要每次位运算寻址，会非常费时间。于是我们就决定写一个程序，实际跑一下看看。 这是位图的代码 typedef struct { uint32_t *bits; size_t size; } Bitmap; Bitmap *create_bitmap(size_t max_num) { size_t num_words = (max_num + 31) / 32; // 计算需要多少个32位字 Bitmap *bm = malloc(sizeof(Bitmap)); if (!bm) { perror("Bitmap allocation failed"); exit(EXIT_FAILURE); } bm->bits = calloc(num_words, sizeof(uint32_t)); // 分配约 1亿位 ≈ 12.5MB bm->size = max_num; if (!bm->bits) { perror("Bitmap bits allocation failed"); exit(EXIT_FAILURE); } return bm; } void bitmap_set(Bitmap *bm, int num) { size_t word_idx = num / 32; size_t bit_idx = num % 32; bm->bits[word_idx] |= (1U << bit_idx); } int bitmap_get(const Bitmap *bm, int num) { size_t word_idx = num / 32; size_t bit_idx = num % 32; return (bm->bits[word_idx] >> bit_idx) & 1U; } 位运算把每个字节大小的内存当作为一组，使用除法判断组数， 再用对8取余，得出每组的位次 ...

基础算法归纳 #cs #c #算法 输出最大值 #include <stdio.h> int main(void) { int i[3], max; scanf("%d %d %d", &i[0], &i[1], &i[2]);//通过数组来代替不同变量 max = i[0]; for (int j = 1; j < n; j++) { if (max < i[j]) { max = i[j]; } } printf("%d", max); } 冒泡排序 void BubbleSort(int arr[], int n)//arr[] 在c中要用第一个数组值 { int flag, tmp; for (int i = 0; i < n - 1; i++) { flag = 0; for (int j = 0; j < n - i -1; j++) { if (arr[j] > arr[j + 1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = 1; } } if (!flag) return; } } 筛选素数 暴力搜索 ...

集合 集合一般被定义为：由一个或多个确定的元素所构成的整体。 集合有什么特性呢？ 首先，集合里的元素类型不一定相同。 你可以将商品看作一个集合，也可以将整个商店看作一个集合，这个商店中有人或者其他物品也没有关系。 其次，集合里的元素没有顺序。 我们不会这样讲：我想要集合中的第三个元素，因为集合是没有顺序的。 事实上，这样的集合并不直接存在于编程语言中。然而，实际编程语言中的很多数据结构，就是在集合的基础上添加了一些规则形成的。 列表 列表（又称线性列表）的定义为：是一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。 列表的概念是在集合的特征上形成的，它具有顺序，且长度是可变的。你可以把它看作一张购物清单： 购物清单中的条目代表的类型可能不同，但是按照一定顺序进行了排列； 购物清单的长度是可变的，你可以向购物清单中增加、删除条目。 在编程语言中，列表最常见的表现形式有数组和链表，而我们熟悉的栈和队列则是两种特殊类型的列表。除此之外，向列表中添加、删除元素的具体实现方式会根据编程语言的不同而有所区分。 数组 数组是列表的实现方式之一，也是面试中经常涉及到的数据结构。 正如前面提到的，数组是列表的实现方式，它具有列表的特征，同时也具有自己的一些特征。然而，在具体的编程语言中，数组这个数据结构的实现方式具有一定差别。比如 C++ 和 Java 中，数组中的元素类型必须保持一致，而 Python 中则可以不同。Python 中的数组叫做 list，具有更多的高级功能。 那么如何从宏观上区分列表和数组呢？这里有一个重要的概念：索引。 首先，数组会用一些名为 索引 的数字来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从 0 算起的。我们可以根据数组中的索引，快速访问数组中的元素。 而列表中没有索引，这是数组与列表最大的不同点。 其次，数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存。 相反，列表中的元素在内存中可能彼此相邻，也可能不相邻。比如列表的另一种实现方式——链表，它的元素在内存中则不一定是连续的。