中山大学数据结构与算法实验报告4
|
140
|
2
|
学习笔记,实验报告,数据结构与算法

2337 字
|
9 分钟

第一题 明明的随机数

1.实验题目

image-20241019222236094

2. 实验目的

本实验的主要目的是实现将明明所生成的 N 个 1 到 1000 之间的随机整数进行去重和排序，并输出不重复的随机数个数及从小到大排序后的结果。通过本实验，学生能够：

  1. 掌握如何使用集合（Set）进行数据去重。
  2. 学习如何对数据进行排序，并使用合适的数据结构来高效实现。
  3. 提高对 C++ 语言中标准库容器（如 set、vector 等）和算法（如 sort）的理解和应用能力。

3. 算法设计

本实验通过以下步骤实现去重和排序：

  1. 输入数据处理：
    • 采用循环读取输入数据的方式，首先读取随机数个数 N，再读取 N 个随机数。
    • 使用 unordered_set 数据结构来存储这些随机数，以实现自动去重的效果。
  2. 排序处理：
    • 将去重后的随机数存入 vector 中，以便对其进行排序。
    • 使用 C++ 标准库中的 sort 函数对 vector 进行从小到大的排序。
  3. 输出结果：
    • 输出去重后的随机数个数 M。
    • 输出排序后的随机数。
  4. 时间复杂度：
    • 由于使用了 unordered_set 进行去重，时间复杂度为 O(N)。
    • 排序的时间复杂度为 O(M log M)，其中 M 是去重后的元素个数。
    • 总的时间复杂度为 O(N + M log M)。
  5. 代码实现：
 #include <algorithm>
 #include <unordered_set>
 #include <vector>
 #include <iostream>
 using namespace std;
 ​
 int main() {
     int m;
     while (cin >> m) {
         unordered_set<int> s;
         for (int i = 0; i < m; ++i) {
             int num;
             cin >> num;
             s.insert(num);
         }
 ​
         vector<int> v(s.begin(), s.end());
         sort(v.begin(), v.end());
 ​
         cout << v.size() << endl;
         for (int& num : v) {
             cout << num << " ";
         }
         cout << endl;
     }
     return 0;
 }

4. 程序运行与测试

测试用例

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

  • 输入样例 1：
    • 10
    • 20 40 32 67 40 20 89 300 400 15
  • 输出：
    • 8
    • 15 20 32 40 67 89 300 400
  • 输入样例 2：
    • 3
    • 3 2 1
  • 输出：
    • 3
    • 1 2 3

程序使用标准输入输出，可处理多个测试用例，每次输入包含一个随机数个数和对应的随机数，程序能够正确去重并进行排序。

程序运行

  • 程序能够成功读取输入，利用 unordered_set 实现自动去重，并使用 vector 和 sort 函数进行排序。
  • 在不同规模的输入情况下（如 N 取最大值 100），程序均能在合理的时间内输出正确的结果。

5. 实验总结与心得

通过本次实验，我学会了如何使用 unordered_set 进行去重操作，并通过 vector 结合 sort 函数实现排序。本实验中的挑战主要在于如何高效去重并进行排序，而 C++ 标准库提供了很好的工具来实现这些操作。

通过实验，我更加理解了 C++ 中不同数据结构的应用场景，例如 unordered_set 在处理重复元素时的高效性，以及 vector 在需要排序时的灵活性。此外，本次实验让我体会到，在面对不同问题时，选择合适的数据结构和算法是解决问题的关键。

第二题 Inversion Number

1.实验题目

屏幕截图 2024-10-20 210423

2. 实验目的

本实验的主要目的是实现一个高效计算数列逆序对数量的算法，并通过该算法量化序列的有序程度。通过本实验，学生能够：

  1. 掌握逆序对的概念，并理解其在排序和数组分析中的应用。
  2. 学习并实现基于归并排序的逆序对计算方法，以达到 O(nlogn) 的时间复杂度。
  3. 提高对于分治算法的理解，特别是在大型数据集上进行复杂计算的能力。

3. 算法设计

为实现对数列逆序对数量的高效计算，使用了基于归并排序的分治算法。具体算法步骤如下：

  1. 分治策略：
    • 利用归并排序的思想，将数列递归地分为左右两个部分，分别对左右部分计算逆序对数量。
    • 在合并过程中统计跨越左右部分的逆序对数量，从而得到整个数组的逆序对总数。
  2. 合并过程中的逆序对统计：
    • 当左半部分的元素大于右半部分的元素时，可以确定这些元素和右半部分当前元素形成逆序对。
    • 每次在合并过程中，统计左半部分未合并的元素个数，从而计算出这些逆序对的数量。
  3. 时间复杂度：
    • 由于归并排序的时间复杂度为 O(nlogn)，每次合并操作的时间复杂度为 O(n)，因此整体逆序对计算的时间复杂度为 O(nlogn)。
  4. 代码实现：
 #include <iostream>
 #include <vector>
 ​
 using namespace std;
 ​
 // 递归求逆序对并进行归并排序
 long long inverse_number(vector<long long>& A, long long x, long long y, vector<long long>& T) {
     long long inverse_num = 0;  // 用于记录逆序对数量
 ​
     if (y - x > 1) {
         long long m = x + (y - x) / 2;  // 分割数组为两半
         long long p = x, q = m, i = x;
 ​
         // 递归处理左半部分
         inverse_num += inverse_number(A, x, m, T);
         // 递归处理右半部分
         inverse_num += inverse_number(A, m, y, T);
 ​
         // 合并两个有序的子数组，并统计逆序对
         while (p < m || q < y) {
             if (q >= y || (p < m && A[p] <= A[q])) {
                 T[i++] = A[p++];
             } else {
                 T[i++] = A[q++];
                 inverse_num += m - p;  // 统计左边比右边大的元素个数
             }
         }
 ​
         // 将合并的结果复制回原数组
         for (i = x; i < y; i++) {
             A[i] = T[i];
         }
     }
 ​
     return inverse_num;
 }
 ​
 int main() {
     long long n;
     while (cin >> n) {
         vector<long long> A(n);
         for (long long i = 0; i < n; i++) {
             cin >> A[i];
         }
         vector<long long> T(n);  // 临时数组用于合并
 ​
         // 计算逆序对数量
         long long result = inverse_number(A, 0, n, T);
 ​
         // 输出逆序对数量
         cout << result << endl;
     }
     return 0;
 }

4. 程序运行与测试

测试用例

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

  • 输入样例 1：
    • 5
    • 3 1 4 5 2
  • 输出：
    • 4
  • 输入样例 2：
    • 6
    • 6 5 4 3 2 1
  • 输出：
    • 15

程序运行

  • 程序通过标准输入读取数据，可以处理多个测试用例，每次输入包含一个数列长度和对应的数列。
  • 程序能够成功输出逆序对数量，并在大规模数据（如 n 接近 100,000）时表现出良好的效率。

5. 实验总结与心得

通过本次实验，我学习了如何通过归并排序来高效计算逆序对数量。实验中的挑战主要在于如何在分治过程中正确统计跨越左右部分的逆序对数量。

归并排序的分治思想结合逆序对统计，使得在 O(nlogn) 的时间复杂度内完成逆序对计算，体现了分治算法在解决复杂问题上的高效性。通过本实验，我深刻理解了归并排序的细节以及如何在排序过程中进行额外的统计操作。对于类似需要在排序过程中进行额外计算的问题，这种思路具有很高的参考价值。

第三题 Mergesort for List

1. 实验题目

image-20241020221205728

2. 实验目的

本实验的主要目的是实现基于归并排序的链表排序算法，以使链表按从小到大的顺序进行排序。通过本实验，学生能够：

  1. 掌握链表的基本操作，例如拆分、合并链表等。
  2. 理解归并排序的分治思想，并在链表数据结构中加以应用。
  3. 提高对链表操作的熟练度，特别是在复杂数据结构上实现高效算法的能力。

3. 算法设计

为实现对链表的排序，使用了基于归并排序的分治算法，具体步骤如下：

  1. 分治策略：
    • 首先通过遍历链表找到中间节点，将链表分为两部分。
    • 递归地对两部分链表进行排序，直到每部分只包含一个节点。
  2. 合并过程：
    • 使用两个指针分别指向两部分链表的头节点，并通过比较节点值，按从小到大的顺序将它们合并。
    • 合并后的链表作为当前递归的返回值，以实现逐步合并并返回最终结果。
  3. 时间复杂度：
    • 归并排序的时间复杂度为 O(nlogn)，适用于链表排序，因为它在链表上的操作较为高效，不需要随机访问。
  4. 代码实现：
 #include "mergeSort.h"
 #include <iostream>
 ​
 using namespace std;
 ​
 struct linkedlist {
     int data;
     linkedlist *next;
 };
 ​
 // 归并排序函数
 void mergesort(linkedlist *&head, int len) {
     if (len <= 1) return;
 ​
     // 找到链表的中间节点
     linkedlist *mid = head;
     for (int i = 0; i < len / 2 - 1; i++) {
         mid = mid->next;
     }
 ​
     linkedlist *midNext = mid->next;
     mid->next = nullptr;
 ​
     // 递归排序两部分链表
     mergesort(head, len / 2);
     mergesort(midNext, len - len / 2);
 ​
     // 合并两个有序链表
     linkedlist *temp = new linkedlist();
     linkedlist *temp2 = temp;
     linkedlist *left = head;
     linkedlist *right = midNext;
 ​
     while (left != nullptr && right != nullptr) {
         if (left->data < right->data) {
             temp->next = left;
             left = left->next;
         } else {
             temp->next = right;
             right = right->next;
         }
         temp = temp->next;
     }
 ​
     if (left != nullptr) {
         temp->next = left;
     } else {
         temp->next = right;
     }
 ​
     head = temp2->next;
     delete temp2;
 }

4. 程序运行与测试

测试用例

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

  • 输入样例 1：
    • 链表：1 -> 3 -> 2 -> 4 -> NULL
  • 输出：
    • 排序后的链表：1 -> 2 -> 3 -> 4 -> NULL
  • 输入样例 2：
    • 链表：4 -> 2 -> 1 -> 3 -> NULL
  • 输出：
    • 排序后的链表：1 -> 2 -> 3 -> 4 -> NULL

程序运行

  • 程序通过对链表进行分割、递归排序、合并操作，成功实现了对链表的归并排序。
  • 在不同规模的链表上进行测试，程序能够在 O(nlogn) 的时间复杂度内完成排序，并能保持链表的完整性和正确性。

5. 实验总结与心得

通过本次实验，我学会了如何对链表进行归并排序操作，并理解了链表结构与数组在排序算法中的不同之处。链表的归并排序操作中，主要的挑战在于链表的拆分和合并，这需要对链表指针的操作非常熟练。

归并排序在链表上的实现，相比于数组更加自然，因为它避免了随机访问，而只需要顺序遍历节点。通过本实验，我更加理解了归并排序的分治思想，以及在链表等复杂数据结构上应用归并排序的优势和实现细节。

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
排序算法

评论

  1. pidanxia
    2 月前
    2024-11-04 15:56:41

    哇大佬原来是中大的呀！

    • Avatar photo
      Michael Yeung
      博主
      pidanxia
      1 月前
      2024-11-15 19:58:38

      🤝

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

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

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
栈与队列

							
							

							
树与二叉树

							
							

							
顺序表与链表

							
							

							
回溯算法初步(Ⅰ)

							
							

							
递归函数设计技巧

							
							

							
回溯算法初步(Ⅱ)

							
							

							
数据的表示

							
							

							
CPU设计与结构

							
							

					
				

			

		

		
					
			
						
					
		
	




 


 






 
  
、