中山大学数据结构与算法实验报告6
|
72
|
0
|
学习笔记,实验报告,数据结构与算法

3308 字
|
18 分钟

第一题 Query

1.实验题目

2. 实验目的

本实验的目的是实现一个高效的查询算法，通过检查一组查询字符串是否存在于给定的字符串集合中，并输出符合条件的查询字符串。通过本实验，学生能够：

  1. 理解如何利用哈希集合优化查询操作，提高查询效率。
  2. 掌握基于哈希的查找算法在大规模数据中的应用。
  3. 提高对集合操作与数据结构的理解，尤其是处理海量数据时的优化策略。

3. 算法设计

本实验主要采用了 unordered_set 数据结构来解决字符串查询问题，具体设计思路如下：

  1. 哈希集合的构建：
    • 我们使用 unordered_set 来存储集合 A 中的所有字符串。由于 unordered_set 的查找复杂度为 O(1) 平均时间，因此能够快速判断某个字符串是否在集合 A 中。
  2. 查询过程：
    • 对于每个查询字符串 B[i]，我们检查它是否存在于集合 A 中。如果存在，则输出该字符串。
    • 由于要保持输出的顺序，因此查询和输出的顺序与 B 中的顺序保持一致。
  3. 时间复杂度：
    • 构建集合 A 的时间复杂度为 O(n)，其中 n 为集合 A 中字符串的数量。
    • 对于每个查询字符串 B[i]，在哈希集合中查找的时间复杂度为 O(1)（平均情况）。因此，查询所有字符串的时间复杂度为 O(m)，其中 m 为集合 B 中查询字符串的数量。
    • 综合来看，算法的总时间复杂度为 O(n + m)，能够有效处理大规模数据。
  4. 空间复杂度：
    • 空间复杂度主要由集合 A 占用，具体为 O(n)，其中 n 为集合 A 中字符串的数量。
  5. 代码实现：
#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

void query(string A[], int n, string B[], int m) {
    unordered_set<string> s(A, A + n);  // 将集合 A 中的所有字符串存储到 unordered_set 中
    for (int i = 0; i < m; ++i) {
        if (s.find(B[i]) != s.end()) {  // 查找字符串 B[i] 是否存在于集合 A 中
            cout << B[i] << endl;  // 输出存在于集合 A 中的字符串
        }
    }
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例：

  • 输入样例：
    • A = ["ABC", "CD", "D"]
    • B = ["A", "CD", "BC", "ABC"]
  • 输出：
    • CD
    • ABC
  • 测试结果：
    • 该程序成功输出了集合 B 中存在于集合 A 中的字符串，并且输出顺序与 B 中的顺序一致。

程序运行

  • 程序通过 unordered_set 存储集合 A，并在 O(1) 平均时间复杂度下检查每个查询字符串 B[i] 是否存在于集合 A 中。
  • 程序在处理多个测试用例时表现出较高的效率，可以在合理的时间内完成大规模数据的查询。

5. 实验总结与心得

通过本次实验，我掌握了如何使用 unordered_set 来高效处理大规模的查找问题。实验中的核心挑战在于如何有效地利用哈希集合进行快速查询，而非传统的线性查找方法。利用哈希集合，查询操作可以在常数时间内完成，这使得程序能够在大数据量下快速输出结果。

此外，本实验让我理解了数据结构选择对性能优化的影响，尤其是在处理大规模数据时，选择合适的集合类型能够显著提升程序效率。在类似的查询问题中，哈希集合通常是首选数据结构，因为它能够在 O(1) 时间内完成查找操作。

通过本次实验，我还进一步加深了对算法时间复杂度的理解，特别是如何设计高效的查询算法，并优化程序的性能。在面对复杂的数据查询问题时，哈希集合是一个非常强大的工具，可以极大提高查询速度。

第二题 爸爸去哪儿之一

1.实验题目

2. 实验目的

本实验的目的是实现一种房间分配算法，通过模拟“爸爸去哪儿”节目的房间分配规则，解决根据小朋友英文名计算房间分配的实际问题。通过本实验，学生能够：

  1. 理解哈希表和线性探测法在处理冲突中的应用。
  2. 掌握如何计算并输出哈希表中元素查找的平均查找长度。
  3. 提高对哈希算法和探测法的理解，特别是在大数据量条件下如何优化查询效率。

3. 算法设计

本实验主要通过哈希表与线性探测法来实现房间的分配，具体的设计步骤如下：

  1. 名字转数值：
    • 每个小朋友的英文名通过字母的 ASCII 值转化为对应的数值，字符 'a' 的数值为 1，'b' 为 2，...，'z' 为 26。小朋友的英文名数值是其各个字母数值的和。
  2. 房间分配：
    • 通过对英文名的数值对房间总数 m 取余，得到初步的房间位置。如果该房间已经被占用，则使用线性探测法查找下一个空房间。探测时，若超出房间总数，则回到第 0 间房进行查找。
  3. 平均查找长度：
    • 在分配房间时，记录每个小朋友的查找长度（即需要探查的房间数），最终计算并输出所有小朋友的平均查找长度。
  4. 输出：
    • 输出每间房的分配情况，如果某个房间为空，则输出“NULL”。最后输出平均查找长度，保留三位小数。
  5. 时间复杂度：
    • 计算名字的数值总时间复杂度为 O(n)，其中 n 是小朋友的数量。
    • 房间分配时，哈希查找的平均时间复杂度为 O(1)，但在最坏情况下需要线性探测，因此最坏情况下为 O(m)，其中 m 为房间数量。
    • 综合考虑，总时间复杂度为 O(n + m)，适用于输入规模较大的情况。
  6. 代码实现：
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;

// 计算小朋友名字的数值
int getNameValue(string name) {
    int sum = 0;
    for (char c : name) {
        sum += c - 'a' + 1;
    }
    return sum;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<string> rooms(m, "NULL");  // 初始化所有房间为空
        vector<int> probes(n, 1);  // 初始化每个小朋友的查找长度为1（即查找第一个位置）

        for (int i = 0; i < n; i++) {
            string name;
            cin >> name;
            int pos = getNameValue(name) % m;  // 计算小朋友名字对应的初步房间号
            // 线性探测法查找空房间
            while (rooms[pos] != "NULL") {
                probes[i]++;  // 查找过程中增加查找次数
                pos = (pos + 1) % m;  // 如果房间被占用，检查下一个房间
            }
            rooms[pos] = name;  // 将小朋友名字分配到找到的房间
        }

        // 输出每个房间的分配情况
        for (int i = 0; i < m; i++) {
            cout << i << ":" << rooms[i] << endl;
        }

        // 计算平均查找长度
        double probe = 0;
        for (int i : probes) {
            probe += i;
        }
        probe /= n;
        printf("%.3f\n", probe);  // 输出平均查找长度，保留三位小数
    }
    return 0;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例：

  • 输入样例：
    • 5 6
    • kimi
    • tiantian
    • stone
    • angela
    • cindy
  • 输出：
    • 0:kimi
    • 1:stone
    • 2:cindy
    • 3:NULL
    • 4:tiantian
    • 5:angela
    • 1.400
  • 其他测试用例：
    • 程序能够正确处理多组输入，输出每个房间的分配情况，并计算并输出平均查找长度。

程序运行

  • 程序通过哈希算法和线性探测法完成房间分配，每次查找空房间时，采用了线性探测法保证可以找到空房间。
  • 程序能够根据输入的数据，输出房间分配情况，并正确计算平均查找长度。

5. 实验总结与心得

通过本次实验，我学会了如何使用哈希表和线性探测法来解决实际问题。在处理房间分配时，遇到哈希冲突时采用线性探测法是一种简单有效的解决方案。程序能够在输入规模较大的情况下依然保持较好的效率。

实验中的挑战主要在于如何有效地计算小朋友名字对应的房间号，以及如何在哈希冲突时进行线性探测。通过模拟“爸爸去哪儿”节目的房间分配策略，进一步加深了我对哈希算法的理解，特别是如何优化哈希冲突的处理。

此外，实验让我理解了计算查找长度的概念，并学会了如何计算并输出平均查找长度，这对于优化哈希表操作非常重要。通过这种方式，我们能够更加准确地评估哈希算法的性能，特别是在面对大规模数据时。

第三题 爸爸去哪儿之二

1.实验题目

2. 实验目的

本实验的目的是实现一种基于平方探测法的房间分配算法，通过模拟“爸爸去哪儿”节目的房间分配策略，解决根据小朋友英文名计算房间分配的实际问题。通过本实验，学生能够：

  1. 理解哈希表中平方探测法的应用。
  2. 掌握如何计算并输出哈希表中元素查找的平均查找长度。
  3. 提高对哈希冲突解决方法的理解，特别是在数据量较大时如何优化查找效率。

3. 算法设计

本实验主要采用哈希表与平方探测法来实现房间的分配，具体设计步骤如下：

  1. 名字转数值：
    • 每个小朋友的英文名通过字母的 ASCII 值转化为对应的数值，字符 'a' 的数值为 1，'b' 为 2，...，'z' 为 26。小朋友的英文名数值是其各个字母数值的和。
  2. 房间分配：
    • 通过对英文名的数值对房间总数 m 取余，得到初步的房间位置。如果该房间已经被占用，则使用平方探测法查找空房间。
    • 在平方探测中，从初始位置开始，按照步数平方依次尝试下一个房间，直到找到空房间为止。
  3. 平均查找长度：
    • 在分配房间时，记录每个小朋友的查找长度（即需要探查的房间数），最终计算并输出所有小朋友的平均查找长度。
  4. 输出：
    • 输出每间房的分配情况，如果某个房间为空，则输出“NULL”。最后输出平均查找长度，保留三位小数。
  5. 时间复杂度：
    • 计算名字的数值总时间复杂度为 O(n)，其中 n 是小朋友的数量。
    • 房间分配时，哈希查找的平均时间复杂度接近 O(1)，但在最坏情况下，平方探测可能需要 O(m) 的时间，其中 m 为房间数量。
    • 综合考虑，总时间复杂度为 O(n + m)，适用于输入规模较大的情况。
  6. 代码实现：
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;

// 计算小朋友名字的数值
int getNameValue(string name) {
    int sum = 0;
    for (char c : name) {
        sum += c - 'a' + 1;
    }
    return sum;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<string> rooms(m, "NULL");  // 初始化所有房间为空
        vector<int> probes(n, 1);  // 初始化每个小朋友的查找长度为1（即查找第一个位置）

        for (int i = 0; i < n; i++) {
            string name;
            cin >> name;
            int initialPos = getNameValue(name) % m;  // 计算小朋友名字对应的初步房间号
            int pos = initialPos;
            int j = 1;
            // 使用平方探测法查找空房间
            while (rooms[pos] != "NULL") {
                probes[i]++;  // 查找过程中增加查找次数
                pos = (initialPos + j * j) % m;  // 使用平方探测法计算下一个位置
                j++;
            }
            rooms[pos] = name;  // 将小朋友名字分配到找到的房间
        }

        // 输出每个房间的分配情况
        for (int i = 0; i < m; i++) {
            cout << i << ":" << rooms[i] << endl;
        }

        // 计算平均查找长度
        double probe = 0;
        for (int i : probes) {
            probe += i;
        }
        probe /= n;
        printf("%.3f\n", probe);  // 输出平均查找长度，保留三位小数
    }
    return 0;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例：

  • 输入样例：
    • 5 6
    • kimi
    • tiantian
    • stone
    • angela
    • cindy
  • 输出：
    • 0:kimi
    • 1:stone
    • 2:cindy
    • 3:NULL
    • 4:tiantian
    • 5:angela
    • 1.400
  • 其他测试用例：
    • 程序能够正确处理多组输入，输出每个房间的分配情况，并计算并输出平均查找长度。

程序运行

  • 程序通过哈希算法和平方探测法完成房间分配，每次查找空房间时，使用平方探测法有效解决哈希冲突。
  • 程序能够根据输入的数据，输出房间分配情况，并正确计算平均查找长度。

5. 实验总结与心得

通过本次实验，我学会了如何使用平方探测法在哈希表中解决冲突问题。在处理房间分配时，遇到哈希冲突时采用平方探测法是一种比线性探测法更为有效的解决方案。程序能够在输入规模较大的情况下依然保持较好的效率。

实验中的挑战主要在于如何有效地计算小朋友名字对应的房间号，以及如何在哈希冲突时进行平方探测。通过模拟“爸爸去哪儿”节目的房间分配策略，进一步加深了我对哈希算法的理解，特别是如何优化哈希冲突的处理。

此外，实验让我理解了计算查找长度的概念，并学会了如何计算并输出平均查找长度，这对于优化哈希表操作非常重要。通过这种方式，我们能够更加准确地评估哈希算法的性能，特别是在面对大规模数据时。

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
哈希表数据结构
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
栈与队列

							
							

							
树与二叉树

							
							

							
顺序表与链表

							
							

							
回溯算法初步(Ⅰ)

							
							

							
递归函数设计技巧

							
							

							
回溯算法初步(Ⅱ)

							
							

							
数据的表示

							
							

							
CPU设计与结构

							
							

					
				

			

		

		
					
			
						
					
		
	




 


 






 
  
、