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

3885 字
|
30 分钟

第一题 检查一个序列是否构成堆

1.实验题目

2. 实验目的

本实验的主要目的是判断给定的整数序列是否构成堆结构，包括极小堆、极大堆、两者兼具或既不是堆。通过本实验，学生能够：

  1. 理解堆的基本概念及其在计算机科学中的应用。
  2. 掌握如何通过数组表示堆，并利用数组下标关系高效判断堆性质。
  3. 学习实现极小堆和极大堆的判断算法，提升算法设计与编程能力。
  4. 熟悉使用C++标准库中的vector容器进行数据处理。

3. 算法设计

为实现判断一个整数序列是否为堆（极小堆、极大堆或两者兼具），采用了遍历比较的方法。具体的算法步骤如下：

  1. 输入数据处理：
    • 读取整数n，表示序列长度。
    • 读取n个整数存入vector容器。
  2. 堆性质判断：
    • 极大堆判断：
      • 遍历所有非叶子节点（下标0到(n-2)/2）。
      • 对于每个父节点，检查其是否大于或等于其所有子节点。
      • 如果有任一父节点小于其子节点，则序列不是极大堆。
    • 极小堆判断：
      • 同样遍历所有非叶子节点。
      • 检查每个父节点是否小于或等于其所有子节点。
      • 如果有任一父节点大于其子节点，则序列不是极小堆。
  3. 综合判断：
    • 如果序列同时满足极大堆和极小堆的条件，则输出"both"。
    • 如果仅满足极大堆的条件，则输出"max heap"。
    • 如果仅满足极小堆的条件，则输出"min heap"。
    • 如果不满足上述任何条件，则输出"no"。
  4. 时间复杂度：
    • 遍历所有非叶子节点的时间复杂度为O(n)。
    • 综合判断的时间复杂度依然为O(n)，整体算法效率高。
  5. 代码实现：
#include <iostream>
#include <vector>
using namespace std;

// 判断是否为极大堆
bool isMaxHeap(const vector<int> &arr) {
    int n = arr.size();
    for(int i = 0; i <= (n - 2) / 2; ++i){
        int left = 2 * i + 1, right = 2 * i + 2;
        if(left < n && arr[i] < arr[left]) return false;
        if(right < n && arr[i] < arr[right]) return false;
    }
    return true;
}

// 判断是否为极小堆
bool isMinHeap(const vector<int> &arr) {
    int n = arr.size();
    for(int i = 0; i <= (n - 2) / 2; ++i){
        int left = 2 * i + 1, right = 2 * i + 2;
        if(left < n && arr[i] > arr[left]) return false;
        if(right < n && arr[i] > arr[right]) return false;
    }
    return true;
}

int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    for(auto &num : v) cin >> num;
    bool maxHeap = isMaxHeap(v);
    bool minHeap = isMinHeap(v);
    if(maxHeap && minHeap) cout << "both\n";
    else if(maxHeap) cout << "max heap\n";
    else if(minHeap) cout << "min heap\n";
    else cout << "no\n";
    return 0;
}

4. 程序运行与测试

4.1 测试用例

为验证程序的正确性和鲁棒性，设计了多个测试用例，涵盖不同的堆类型和边界情况。

测试用例1：非堆序列
  • 输入 
    5
3 4 2 1 1
  • 输出 
    no
  • 说明：不满足极大堆和极小堆的条件。
测试用例2：极大堆
  • 输入 
    7
10 9 8 7 6 5 4
  • 输出 
    max heap
  • 说明：每个父节点均大于其子节点，符合极大堆的定义。
测试用例3：极小堆
  • 输入 
    7
1 2 3 4 5 6 7
  • 输出 
    min heap
  • 说明：每个父节点均小于其子节点，符合极小堆的定义。
测试用例4：既是极大堆又是极小堆（所有元素相同）
  • 输入 
    5
2 2 2 2 2
  • 输出 
    both
  • 说明：所有元素相同，满足两种堆的条件。
测试用例5：单个元素
  • 输入 
    1
5
  • 输出 
    both
  • 说明：单个元素的序列既是极大堆也是极小堆。
测试用例6：空序列
  • 输入 
    0
  • 输出 
    both
  • 说明：空序列视为同时满足两种堆。

4.2 程序运行结果

所有测试用例均按预期输出，具体如下：

测试用例编号 输入 输出 预期结果
1 5 3 4 2 1 1 no 正确
2 7 10 9 8 7 6 5 4 max heap 正确
3 7 1 2 3 4 5 6 7 min heap 正确
4 5 2 2 2 2 2 both 正确
5 1 5 both 正确
6 0 both 正确

通过这些测试用例，验证了程序在不同情况下的正确性和稳定性。

5. 实验总结与心得

通过本次实验，我深入理解了堆的基本概念及其在数组中的表示方法。设计并实现了判断序列是否为极小堆、极大堆或两者兼具的算法，增强了算法设计与编程能力。

在实现过程中，体会到数组下标与堆节点关系的重要性。通过合理的索引计算，能够高效地遍历和判断堆的性质。此外，处理边界情况（如空序列和单元素序列）增强了程序的健壮性。

实验中使用多样化的测试用例，确保程序在不同情况下均能正确运行。这不仅巩固了堆的理论知识，也提升了使用C++标准库进行高效编程的能力。总体而言，本次实验为进一步学习复杂数据结构与算法打下了坚实的基础。

第二题 奖学金

1.实验题目

2. 实验目的

本实验的主要目的是根据学生的语文、数学、英语成绩，计算总分并排序，选出前5名学生发放奖学金。通过本实验，学生能够：

  1. 理解排序算法在实际问题中的应用，特别是多重排序条件的处理。
  2. 掌握结构体的使用及其在数据存储与处理中的作用。
  3. 提高使用C++标准库函数（如sort）进行高效数据处理的能力。
  4. 学习如何处理多组测试数据，并确保输出格式的正确性。

3. 算法设计

为实现根据总分及特定排序规则选出前5名学生，采用了以下步骤：

  1. 数据输入与存储：
    • 读取学生人数n。
    • 对每个学生，读取其语文、数学、英语成绩，并计算总分。
    • 使用结构体Student存储每个学生的学号、各科成绩及总分。
  2. 排序规则：
    • 主排序依据：总分从高到低。
    • 次排序依据：总分相同情况下，语文成绩从高到低。
    • 第三排序依据：总分和语文成绩相同情况下，学号从小到大。

    通过自定义比较函数cmp实现上述排序规则，并使用std::sort对学生列表进行排序。

  3. 选取前5名：
    • 排序完成后，选取排序后的前5名学生，输出其学号和总分。
    • 若学生人数少于5，则根据实际人数输出。
  4. 处理多组测试数据：
    • 程序能够连续处理多组测试数据，每组数据之间输出一个空行以分隔。
  5. 时间复杂度分析：
    • 排序的时间复杂度为O(n log n)，其中n为学生人数。
    • 数据输入和总分计算的时间复杂度为O(n)。
    • 整体时间复杂度主要由排序决定，为O(n log n)。
  6. 代码实现：
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;

struct Student {
    int id;         // 学号
    int chinese;    // 语文成绩
    int math;       // 数学成绩
    int english;    // 英语成绩
    int total;      // 总分

    Student(int id, int chinese, int math, int english)
        : id(id), chinese(chinese), math(math), english(english) {
        total = chinese + math + english;
    }
};

bool cmp(const Student& a, const Student& b) {
    if (a.total != b.total) return a.total > b.total;  // 总分高的在前
    if (a.chinese != b.chinese) return a.chinese > b.chinese;  // 总分相同，语文成绩高的在前
    return a.id < b.id;  // 总分和语文成绩都相同，学号小的在前
}

int main() {
    int n;
    while (cin >> n) {
        vector<Student> students;

        for (int i = 1; i <= n; ++i) {
            int chinese, math, english;
            cin >> chinese >> math >> english;
            students.emplace_back(i, chinese, math, english);
        }
        sort(students.begin(), students.end(), cmp);
        for (int i = 0; i < 5; ++i) {
            cout << students[i].id << " " << students[i].total << endl;
        }
    }

    return 0;
}

4. 程序运行与测试

为验证程序的正确性和鲁棒性，设计了多个测试用例：

  • 测试用例1：标准输入
    • 输入
    6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
    • 输出
    6 265
4 264
3 258
2 244
1 237
  • 测试用例2：多组数据
    • 输入
    6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
    • 输出
    6 265
4 264
3 258
2 244
1 237

8 265
2 264
6 264
1 258
5 258
  • 测试用例3：少于5名学生
    • 输入
    3
100 100 100
90 90 90
80 80 80
    • 输出
    1 300
2 270
3 240
  • 测试用例4：所有学生总分相同
    • 输入
    5
80 80 80
80 80 80
80 80 80
80 80 80
80 80 80
    • 输出
    1 240
2 240
3 240
4 240
5 240

5. 实验总结与心得

通过本次实验，我深入理解了多重排序条件在实际问题中的应用。设计并实现了根据总分及特定规则选出前5名学生的算法，增强了对结构体和自定义排序函数的掌握。

在编程实现过程中，体会到合理组织数据结构（如使用struct存储学生信息）的重要性，以及如何利用C++标准库中的sort函数结合自定义比较函数高效地完成复杂排序。此外，处理多组测试数据和确保输出格式符合要求也提升了程序的健壮性和适应性。

实验中设计的多样化测试用例，特别是包含边界情况的测试，帮助我全面检验了程序的正确性。这不仅巩固了理论知识，也提升了使用C++进行高效数据处理的能力。总体而言，本次实验为进一步学习复杂数据处理和算法设计打下了坚实的基础。

第三题 heap

1. 实验题目

2. 实验目的

本实验的主要目的是实现一个小根堆（Min Heap）用于优先队列的操作，包括插入（push）和删除堆顶元素（pop）。通过本实验，学生能够：

  1. 理解堆数据结构的基本概念及其在优先队列中的应用。
  2. 掌握堆的插入与删除操作的实现原理及其在数组中的存储方式。
  3. ju提高使用C++进行数据结构实现的编程能力，特别是对类和操作符重载的应用。
  4. 学习如何处理多组测试数据，并确保程序的效率和正确性。

3. 算法设计

为实现一个小根堆，主要需要实现两个核心操作：插入元素（push）和删除堆顶元素（pop）。堆通常通过完全二叉树的结构来表示，而在程序中使用数组来存储堆结构可以简化操作。具体的算法设计如下：

3.1 数据表示

  • 数组表示堆：使用一个从下标1开始的数组来存储堆元素。对于任意一个节点，假设其下标为i：
    • 左子节点的下标为2*i
    • 右子节点的下标为2*i + 1
    • 父节点的下标为i/2
  • 类结构：
    • array类：封装了一个固定大小的数组，并重载了下标操作符以便于访问元素。
    • heap类：包含堆的大小n和一个array对象，用于存储堆元素。提供了clear、top、size、push和pop等成员函数。

3.2 插入操作（push）

插入操作的步骤如下：

  1. 增加堆的大小：将堆的大小n加1。
  2. 插入新元素：将新元素x放入堆的最后一个位置h[n]。
  3. 上浮调整：
    • 从新插入的位置开始，比较该节点与其父节点的值。
    • 如果当前节点的值小于父节点的值，则交换两者的位置。
    • 重复上述过程，直到当前节点不再小于其父节点，或者到达堆顶。

3.3 删除堆顶操作（pop）

删除堆顶操作的步骤如下：

  1. 替换堆顶：将堆顶元素h[1]替换为堆的最后一个元素h[n]，并将堆的大小n减1。
  2. 下沉调整：
    • 从堆顶开始，比较当前节点与其左右子节点的值。
    • 找出当前节点与其子节点中最小的那个节点。
    • 如果当前节点的值大于最小子节点的值，则交换两者的位置。
    • 重复上述过程，直到当前节点不再大于其任何一个子节点，或者到达叶子节点。

3.4 时间复杂度分析

  • 插入操作（push）：
    • 最坏情况下需要上浮至堆顶，时间复杂度为O(log n)。
  • 删除堆顶操作（pop）：
    • 最坏情况下需要下沉至叶子节点，时间复杂度为O(log n)。
  • 整体时间复杂度：
    • 插入和删除操作的时间复杂度均为O(log n)，保证了堆操作的高效性。

3.5 代码实现

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005;

// array类，封装堆的数组部分
class array {
private:
    int elem[MAXN];
public:
    int &operator[](int i) { return elem[i]; }
};

// heap类，实现小根堆
class heap {
private:
    int n;      // 当前堆的大小
    array h;    // 存储堆元素的数组

public:
    // 构造函数，初始化堆
    heap() : n(0) {}

    // 清空堆
    void clear() { n = 0; }

    // 获取堆顶元素
    int top() { 
        if(n >=1)
            return h[1]; 
        else
            return -1; // 或者其他错误处理
    }

    // 获取堆的大小
    int size() { return n; }

    // 插入元素
    void push(int x);

    // 删除堆顶元素
    void pop();
};

// 实现堆的插入操作
void heap::push(int x)
{
    // 增加堆的大小
    n++;
    // 将新元素放在堆的最后
    h[n] = x;
    // 当前插入的位置
    int i = n;
    // 上浮调整
    while (i > 1 && h[i] < h[i / 2])
    {                         
        swap(h[i], h[i / 2]); 
        i /= 2;         
    }
}

// 实现堆的删除堆顶操作
void heap::pop()
{
    if(n < 1)
        return; // 堆为空，无需删除

    // 将堆顶替换为堆的最后一个元素
    h[1] = h[n];
    n--;

    int i = 1;
    while (i <= n)
    {
        int left = 2 * i;     
        int right = 2 * i + 1; 
        int smallest = i;

        // 找出当前节点和其子节点中最小的
        if(left <= n && h[left] < h[smallest]){
            smallest = left;
        }
        if(right <= n && h[right] < h[smallest]){
            smallest = right;
        }

        // 如果当前节点已经是最小的，停止调整
        if (smallest == i)
        {
            break;
        }

        // 交换当前节点与最小子节点
        swap(h[i], h[smallest]);
        // 继续向下调整
        i = smallest;
    }
}

// 测试代码
int main() {
    heap h;
    h.push(3);
    h.push(1);
    h.push(2);
    printf("%d\n", h.top()); // 应输出1
    h.pop();
    printf("%d\n", h.top()); // 应输出2

    // 进一步测试
    h.push(0);
    printf("%d\n", h.top()); // 应输出0
    h.pop();
    printf("%d\n", h.top()); // 应输出2

    return 0;
}

4. 程序运行与测试

为了验证小根堆的正确性和鲁棒性，设计了多个测试用例，涵盖基本操作和边界情况。

测试用例1：基本操作
  • 测试代码 
    heap h;
h.push(3);
h.push(1);
h.push(2);
printf("%d\n", h.top());
h.pop();
printf("%d\n", h.top());
  • 预期输出 
    1
2
  • 说明：插入3、1、2后，堆顶应为1。删除堆顶后，新的堆顶应为2。
测试用例2：多次插入和删除
  • 测试代码 
    heap h;
h.push(5);
h.push(3);
h.push(8);
h.push(1);
h.push(7);
printf("%d\n", h.top()); // 1
h.pop();
printf("%d\n", h.top()); // 3
h.push(0);
printf("%d\n", h.top()); // 0
h.pop();
printf("%d\n", h.top()); // 3
  • 预期输出 
    1
3
0
3
  • 说明：测试了多次插入和删除操作，验证堆顶元素的正确性。
测试用例3：边界情况
  • 测试代码 
    heap h;
h.push(10);
printf("%d\n", h.top()); // 10
h.pop();
// 尝试获取堆顶，应处理空堆情况
// 根据实现，可能需要定义行为
  • 预期输出 
    10
  • 说明：测试了插入一个元素后删除的情况，确保堆能够处理单一元素的操作。
测试用例4：重复元素
  • 测试代码 
    heap h;
h.push(2);
h.push(2);
h.push(2);
printf("%d\n", h.top()); // 2
h.pop();
printf("%d\n", h.top()); // 2
h.pop();
printf("%d\n", h.top()); // 2
  • 预期输出 
    2
2
2
  • 说明：插入多个相同元素，验证堆的稳定性。

5. 实验总结与心得

通过本次实验，我深入理解了堆数据结构，特别是小根堆的实现原理及其在优先队列中的应用。实验过程中，设计并实现了堆的插入和删除操作，增强了对堆在数组中存储方式的理解。

在编程实现过程中，体会到合理组织数据结构（如使用类和结构体）的重要性，以及如何通过操作符重载简化代码的访问方式。通过自定义比较和交换操作，确保了堆的性质在每次插入和删除后得到维护。

此外，处理堆的边界情况（如空堆和单元素堆）也让我认识到编程中细节处理的重要性，确保程序的健壮性和正确性。通过多样化的测试用例，全面检验了程序的功能和性能，提升了编写高效、可靠代码的能力。

总体而言，本次实验不仅巩固了堆数据结构的理论知识，还提升了使用C++进行复杂数据结构实现的编程能力。这为后续学习更复杂的数据结构与算法打下了坚实的基础。

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

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

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

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
栈与队列

							
							

							
树与二叉树

							
							

							
顺序表与链表

							
							

							
回溯算法初步(Ⅰ)

							
							

							
递归函数设计技巧

							
							

							
回溯算法初步(Ⅱ)

							
							

							
数据的表示

							
							

							
CPU设计与结构

							
							

					
				

			

		

		
					
			
						
					
		
	




 


 






 
  
、