# ds-project **Repository Path**: drooly/ds-project ## Basic Information - **Project Name**: ds-project - **Description**: 数据结构课程设计 - **Primary Language**: C++ - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 4 - **Created**: 2025-11-08 - **Last Updated**: 2025-12-21 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 颜色直方图 李孟琳，齐雪晴，许元凤 **摘要**：本项目主要解决数字图像处理里的颜色频率统计问题，完整实现了从读取文本格式图像数据、统计颜色出现频次，到生成文本版直方图的全流程。程序能读取每行代表一个像素 RGB 值（范围 0-255）的文本文件，精准算出每种颜色的出现次数。 RGB 颜色空间里能组合出超 1670 万种离散颜色，要是直接用三维数组存储，虽然查询速度快，但内存消耗特别大，还会有很多闲置空间。所以我们选了哈希表作为核心数据结构，设计了优化后的哈希函数，再搭配分离链式法处理冲突，让颜色的插入、查找和更新操作都能达到接近常数级的时间复杂度（O (1)），既保证了运算效率，又大大降低了内存占用。 另外，项目还拓展了颜色量化功能 —— 通过降低颜色精度来减少独特颜色的总数，给超大型图像处理或者对精度要求不高的场景，提供了更高效的解决方案。 总的来说，本项目不仅精准完成了颜色频率统计的核心需求，还成功平衡了时间效率和空间消耗，比传统方法的资源利用效率更高，有着不错的实用性和应用价值 任务分工及完成情况。 工作量占比。 # 1. 系统分析 ## 1.1 问题描述 问题描述： 颜色直方图会统计数字图像中每种颜色的出现频率，本次仅针对离散 RGB 颜色空间（每个像素的红、绿、蓝分量为 0-255 的整数）。图像以文本文件存储，每行对应一个像素的三个 RGB 分量，需要编写程序统计每种颜色的像素个数。 具体要求： 1.读取存储图像像素的文本文件，文件每行是三个 0-255 的整数（对应 RGB 分量）。 2.统计文件中每种不同 RGB 颜色（即不同分量组合）对应的像素点数量。 3.程序核心仅需完成上述颜色出现次数的统计功能。 ## 1.2 可行性分析 解决问题的关键，就是设计一个既能快速处理 RGB 颜色空间里超 1670 万种离散颜色数据，又不会太费内存的数据结构。核心数据结构要支持高频的查找、插入和更新操作，因为统计颜色频率时，要逐个遍历图像像素，得实时更新计数，效率不能低 核心算法则要搞定两件事：一是把 RGB 颜色高效映射到存储位置，二是妥善处理哈希冲突，不然会拖慢整体运算速度。 我们的总体思路是用哈希表（链地址法） 当核心数据结构：先设计一个优化后的哈希函数，通过对 RGB 三个分量做加权异或运算，把三维的 RGB 颜色空间转换成一维的哈希表索引，再用分离链式法处理冲突 —— 也就是让相同索引的颜色以链表形式存在。 这种方案能很好平衡时间效率和空间利用率：比起直接用 256×256×256 的三维数组（得占约 16MB 内存，还会有大量闲置空间），哈希表只存实际出现的颜色，能大幅减少内存浪费；而且优化后的哈希函数能降低冲突概率，查找、插入、更新操作的平均时间复杂度差不多能到 O (1)，完全能满足海量像素数据的高效处理需求，和代码里的核心逻辑也能对上。 ## 1.3 需求分析 ### （1）输入和输出 - 输入：两种输入方式，一是存储图像像素数据的文本文件（每行 3 个 0-255 的整数，对应 R、G、B 分量），二是系统自动生成的测试图像数据（支持自定义图像尺寸）；无需额外参数，仅需指定输入文件路径（文件输入模式）。 - 输出：文本格式的颜色直方图统计结果，包括总像素数、独特颜色数、最频繁颜色及计数（占比）、前 10 种颜色的频率分布；同时输出算法处理时间，支持直观展示颜色与对应频率的映射关系。 ### （2）数据字典 - 像素数据 = 红色分量（0-255 整数）+ 绿色分量（0-255 整数）+ 蓝色分量（0-255 整数） - 哈希表节点 = RGB 颜色（r/g/b 分量）+ 频率计数（非负整数）+ 下一个节点指针 - 颜色直方图 = 哈希表（存储颜色 - 频率映射）+ 统计信息（总像素数、独特颜色数、最频繁颜色等） - 测试图像 = 固定尺寸（宽 × 高）的像素数组（由系统按预设规则生成） ### （3）数据文件 系统需要读取存储图像像素数据的文本文件，可以是需要被统计的数字图像，也可以是系统自动生成的测试图像。格式为文本文档（txt）。 # 2. 系统设计 ## 2.1 概要设计 |模块名称|核心功能|输入|输出| |------|------|------|------| |数据生成模块|生成符合格式的测试图像数据（RGB 分量文本），支持自定义图像尺寸|预设颜色模式（如红、绿、蓝、黄循环）、图像宽高|二维数组存储的像素数据（每行含 R、G、B 值）| |文件读写模块|读取外部 RGB 文本文件数据，过滤无效行（注释、空行、非法值）；支持生成测试文件|外部文本文件路径 / 测试参数|标准化像素数组、有效像素计数| |哈希表统计模块|基于哈希表实现颜色频率统计，处理哈希冲突，计算关键指标|标准化像素数组、像素总数|颜色 - 频率映射表、总像素数、独特颜色数、最频繁颜色| |结果输出模块|格式化展示统计结果，包括核心指标（处理时间、频率占比）、前 10 种颜色分布|哈希表统计结果、处理时间|文本化直方图（含 RGB 值、计数、占比）| |内存管理模块|安全分配 / 释放像素数组、哈希表节点内存，避免内存泄漏|数组大小、节点数量|无（确保内存安全回收）| ## 2.2 数据结构设计 |数据结构|优势|不足|时间复杂度（查找/插入）|空间利用率| |------|------|------|------|------| |三维数组|直接映射，访问速度最快（O (1)），无需处理冲突|固定占用 16MB 内存（256×256×256×2 字节），大量闲置空间（多数颜色未出现）|O(1)/O(1)|低（仅存储实际颜色时利用率极低）| |二叉排序树|有序存储，支持范围查询，空间仅存实际颜色|查找 / 插入效率受树高影响（最坏 O (n)），需维护树结构平衡| O (logn)/O (logn)（平衡树）|中（需存储指针 / 索引）| |哈希表（分离链式）|平均时间复杂度接近 O (1)，空间仅存实际颜色，冲突处理简单| 依赖哈希函数设计（冲突过多会退化），需额外存储链表指针 |O (1)（平均）/O (1)（平均） |高（仅存储实际颜色 + 少量链表指针）| ### 最终选择：哈希表（分离链式） - 哈希表数组：定义大小为 10007（质数，减少冲突）的指针数组HashNode** hash_table，每个元素指向一个链表的头节点； - 链表节点结构：存储单种颜色的 RGB 值、出现次数及下一个节点指针，代码定义如下： ```cgg unsigned int hash_function(int r, int g, int b) { // 选用大质数作为权重（减少哈希碰撞），异或运算增强随机性 unsigned int hash = (r * 73856093 ^ g * 19349663 ^ b * 83492791); return hash % HASH_TABLE_SIZE; // 取模确保索引在哈希表范围内 } ``` ## 2.3 算法设计 在颜色直方图统计任务中，核心算法主要围绕 颜色频率统计​ 和 哈希表操作​ 展开。我们对比了以下几种可行的算法设计方案： |方案|优势|不足| |------|------|------| |直接遍历+顺序查找|实现简单，无需复杂数据结构|查找效率低（O(n)），不适合海量数据| |先排序后统计|排序后相同颜色相邻，便于统计|排序时间复杂度高（O(n log n)），且需额外空间| |哈希表统计（分离链式）|平均 O(1) 的查找和插入效率，空间利用率高|哈希函数设计影响性能，需处理冲突| #### 最终选择：哈希表统计（分离链式） 综合考虑时间效率、空间利用率以及实际图像数据量（可能包含数百万像素），我们选择 哈希表（分离链式）​ 作为核心算法方案。该方案在保持接近 O(1) 时间复杂度的同时，仅存储实际出现的颜色，显著节省内存。 ### （1）颜色频率统计算法 遍历图像每个像素的 RGB 值，通过哈希函数映射到哈希表中的位置。若该位置已有该颜色节点，则增加其计数；否则插入新节点。 ``` 算法：ColorFrequencyStatistic 输入：像素数组 pixels[]，像素总数 n 输出：哈希表 colorHistogram 1. 初始化哈希表 hashTable（大小为 HASH_TABLE_SIZE） 2. FOR i = 0 TO n-1 DO 3. r, g, b = pixels[i] 的 RGB 分量 4. index = HashFunction(r, g, b) 5. 在 hashTable[index] 链表中查找颜色 (r, g, b) 6. IF 找到 THEN 7. 该颜色计数 +1 8. ELSE 9. 创建新节点，插入链表头部，计数设为1 10. END IF 11. END FOR 12. 返回 hashTable ``` #### 流程图： 开始 → 读取像素 → 计算哈希值 → 查找链表 → 若存在 → 计数+1 → 继续下一像素 → 若不存在 → 插入新节点 → 继续下一像素 → 所有像素处理完毕 → 输出统计结果 → 结束 ### （2）哈希函数设计算法 将三维 RGB 颜色空间映射到一维哈希表索引。通过加权和异或运算，减少冲突概率。 ``` 算法：HashFunction 输入：r, g, b（0-255 整数） 输出：哈希索引 index（0 到 HASH_TABLE_SIZE-1） 1. 选择大质数权重：w1 = 73856093, w2 = 19349663, w3 = 83492791 2. hash = (r * w1) XOR (g * w2) XOR (b * w3) 3. index = hash % HASH_TABLE_SIZE 4. 返回 index ``` ### （3）颜色量化算法（扩展功能） 通过降低颜色精度（如将每分量从 8bit 降至 4bit），减少颜色总数，提升处理效率。 ``` 算法：ColorQuantization 输入：原始颜色 (r, g, b)，量化位数 k（如 k=4） 输出：量化后颜色 (r', g', b') 1. r' = (r >> (8 - k)) << (8 - k) // 保留高 k 位 2. g' = (g >> (8 - k)) << (8 - k) 3. b' = (b >> (8 - k)) << (8 - k) 4. 返回 (r', g', b') ``` # 3. 系统实现 本项目使用C++语言实现，项目内包括main.cpp和test.cpp两个程序和一个文本文档image_data.txt。main.cpp是主程序源代码，test.cpp是测试程序源代码，image_data.txt 是图像测试数据。 ## 3.1 核心数据结构的实现 1. 哈希表数据结构设计 ``` // 哈希表节点结构 typedef struct HashNode { int r, g, b; // 颜色值（RGB分量） int count; // 该颜色出现的次数 struct HashNode *next; // 解决哈希冲突的链表指针 } HashNode; ``` 设计特点： 链地址法：使用链表解决哈希冲突，这是实现中最关键的设计选择 节点存储完整信息：每个节点存储RGB值和计数，便于直接访问 内存开销：每个节点需要4个int（3个RGB + 1个count）和一个指针，共20字节（32位系统）或36字节（64位系统） 2. 像素存储数据结构 ``` // 使用二维数组存储像素 int** pixels = (int**)safe_malloc(count * sizeof(int*)); pixels[i] = (int*)safe_malloc(3 * sizeof(int)); pixels[i][0] = r; // 红色分量 pixels[i][1] = g; // 绿色分量 pixels[i][2] = b; // 蓝色分量 ``` 设计特点： 动态二维数组：第一维指向行，每行独立分配内存 内存不连续：可能导致缓存不友好，但灵活性高 访问模式：pixels[i][j]形式访问，语义清晰 ## 3.2 核心算法的实现 1. 哈希函数算法 ``` unsigned int hash_function(int r, int g, int b) { unsigned int hash = (r * 73856093) ^ (g * 19349663) ^ (b * 83492791); return hash % HASH_TABLE_SIZE; } ``` 算法原理： 质数乘法：使用三个大质数（73856093, 19349663, 83492791）质数乘法有助于分散输入，减少模式导致的冲突。这些质数经过精心选择，具有良好的分布特性。 异或操作：^操作混合三个颜色分量，异或具有可逆性和良好的分布特性，确保每个颜色分量都对哈希值有贡献。 取模运算：% HASH_TABLE_SIZE将结果映射到哈希表大小范围内。HASH_TABLE_SIZE=10007是质数，有助于均匀分布 2. 颜色统计核心算法 ``` void histogram_hash(int** pixels, int pixel_count) { // 创建哈希表 HashNode** hash_table = (HashNode**)safe_calloc(HASH_TABLE_SIZE, sizeof(HashNode*)); int unique_colors = 0; int max_count = 0; int max_r = 0, max_g = 0, max_b = 0; // 遍历所有像素（O(n)复杂度） for (int i = 0; i < pixel_count; i++) { int r = pixels[i][0]; int g = pixels[i][1]; int b = pixels[i][2]; // 计算哈希值 unsigned int index = hash_function(r, g, b); HashNode* current = hash_table[index]; HashNode* prev = NULL; int found = 0; // 在链表中查找颜色（O(k)复杂度，k为链表长度） while (current != NULL) { if (current->r == r && current->g == g && current->b == b) { // 找到颜色，计数加1 current->count++; if (current->count > max_count) { // 更新最大计数 max_count = current->count; max_r = r; max_g = g; max_b = b; } found = 1; break; } prev = current; current = current->next; } // 未找到，创建新节点 if (!found) { HashNode* new_node = (HashNode*)safe_malloc(sizeof(HashNode)); new_node->r = r; new_node->g = g; new_node->b = b; new_node->count = 1; new_node->next = NULL; // 插入链表头部或尾部 if (prev == NULL) { hash_table[index] = new_node; // 链表为空，直接作为头节点 } else { prev->next = new_node; // 插入链表尾部 } unique_colors++; // 更新最大计数（新颜色至少计数为1） if (1 > max_count) { max_count = 1; max_r = r; max_g = g; max_b = b; } } } // 输出结果和释放内存... } ``` 算法复杂度分析： |操作|时间复杂度|空间复杂度| |---|---|---| |遍历像素|O(n)|O(1)| |哈希计算|O(1)|O(1)| |链表查找|O(k)|O(1)| |节点插入|O(1)|O(m)| |总体|平均O(n),最坏O(n²)|O(n + HASH_TABLE_SIZE)| n: 像素总数 m: 唯一颜色数 k: 链表平均长度 = m / HASH_TABLE_SIZE 3. 内存管理算法 三层内存分配策略： ``` // 第一层：像素数组指针 int** pixels = (int**)safe_malloc(count * sizeof(int*)); // 第二层：每个像素的RGB数组 for (int i = 0; i < count; i++) { pixels[i] = (int*)safe_malloc(3 * sizeof(int)); } // 第三层：哈希表节点（按需分配） HashNode* new_node = (HashNode*)safe_malloc(sizeof(HashNode)); ``` 内存释放算法： ``` // 正确的释放顺序（后分配先释放） void free_pixels(int** pixels, int count) { if (pixels == NULL) return; // 先释放每个像素行 for (int i = 0; i < count; i++) { if (pixels[i] != NULL) { free(pixels[i]); } } // 再释放像素数组 free(pixels); } // 哈希表释放算法 for (int i = 0; i < HASH_TABLE_SIZE; i++) { HashNode* current = hash_table[i]; while (current != NULL) { HashNode* temp = current; current = current->next; free(temp); // 释放链表节点 } } free(hash_table); // 释放哈希表数组 ``` # 4. 系统测试 为了测试，我们创建了image_data.txt，随机生成了几组符合要求的数据，只需要把数据放到这个文本文档里，就可以读取分析。为了模拟各种情况，分别进行了单色测试、双色棋盘测试、三原色渐变测试、空文件测试、超大值测试、随机生成100和1000像素测试。其中随机生成100和1000像素的测试数据使用Python脚本生成的。在所有测试中，程序的输出均符合预期。 # 5. 总结 ## 5.1 项目概况和完成情况 本项目成功实现了一个高效的颜色直方图统计系统，全面完成了从问题分析、系统设计到实现测试的全流程开发。主要完成情况如下： ### 核心功能完成情况： 文件读取模块：能够正确读取文本格式的RGB图像数据，自动过滤无效行和注释 哈希表统计模块：实现了基于分离链式法的哈希表，正确统计颜色频率 内存管理模块：实现了安全的内存分配和释放，避免内存泄漏 结果输出模块：格式化输出统计结果，包括总像素数、唯一颜色数、最频繁颜色等 测试验证模块：通过多种测试用例验证了程序的正确性和健壮性 ### 性能指标达成情况： 时间复杂度：平均O(n)，最坏O(n²)（符合哈希表理论性能） 空间复杂度：O(n + HASH_TABLE_SIZE)，内存使用效率高 处理能力：支持最多10,000像素（可调整MAX_PIXELS参数扩展） 正确性：在各种测试用例下均输出正确结果 ### 额外功能实现： 错误处理机制：对无效输入、文件不存在等情况有良好的容错处理 测试数据生成：提供了Python脚本生成多种测试数据 性能分析工具：包含了哈希函数分析工具，便于优化改进 ## 5.2 遇到的问题和解决方法 ### 问题1：哈希冲突导致性能下降 问题描述：在测试大量随机颜色时，虽然理论上冲突概率低，但仍可能出现局部性能下降。 解决方案： 精心选择哈希函数参数，使用大质数权重减少规律性冲突 设定合理的哈希表大小（10007为质数，有利于均匀分布） 实现链表插入优化，采用头插法提高插入效率 ### 问题2：内存管理复杂容易泄漏 问题描述：多层动态内存分配（像素数组、哈希节点）容易导致内存泄漏。 解决方案： 实现safe_malloc和safe_calloc包装函数，统一错误处理 严格遵循"后分配先释放"原则，编写专门的free_pixels函数 在哈希表统计完成后，完整释放所有哈希节点 ### 问题3：文件格式兼容性 问题描述：输入文件可能包含注释、空行、格式错误等多种情况。 解决方案： 实现健壮的文件解析逻辑，跳过注释行（以#开头） 验证RGB值范围（0-255），自动过滤无效数据 支持多种空白字符分隔（空格、制表符） ### 问题4：测试数据覆盖不足 问题描述：手动编写测试数据难以覆盖所有边界情况。 解决方案： 开发Python测试数据生成脚本，支持多种分布模式 设计专门的哈希冲突测试数据 包含边界值测试、空文件测试等特殊情况 ## 5.3 个人小结 成员1：李孟琳 作为项目组长，我主要负责系统整体架构设计、核心算法实现和部分项目文档撰写。在项目中，我深入研究了哈希表在颜色统计中的应用，设计了高效的哈希函数和内存管理策略。最大的收获是学会了如何在实际工程问题中平衡时间复杂度和空间复杂度，以及如何设计健壮的错误处理机制。通过与团队成员的紧密合作，我深刻体会到团队协作在软件开发中的重要性。 成员2：齐雪晴 本次项目中，我负责问题描述梳理以及最终的报告与代码讲解。我明确了“大规模颜色高效统计”的核心需求，收尾时整合各模块成果提炼技术亮点，讲解环节清晰呈现程序设计逻辑与代码实现细节。这次实践提升了我的需求分析与成果展示能力，也加深了对团队协作中模块衔接逻辑的理解。 成员3：许元凤 本次RGB颜色直方图统计项目中，我负责核心内容撰写。完成哈希表方案选型、哈希函数设计、颜色统计逻辑等关键文档撰写，参与数据结构及内存管理模块内容梳理，协助整理测试资料。项目实践深化了我的专业认知，提升了技术文档撰写能力与团队协作效率。 # 参考文献 列出参考的文献资料，根据情况自行添加。 [1] 严蔚敏, 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社, 2007.