首页 > 其他分享 >山东大学数据结构实验10 堆及其应用

山东大学数据结构实验10 堆及其应用

时间：2023-04-26 12:56:18浏览次数：40  
标签：Node 10 weight int void heap child 数据结构 山东大学

内容

创建 最小堆类。最小堆的存储结构使用 数组。提供操作:插入、删除、初始化。题目第一个操作是建堆操作，接下来是对堆的插入和删除操作，插入和删除都在建好的堆上操作。

格式

输入

第一行一个数n（n<=5000)，代表堆的大小。第二行n个数，代表堆的各个元素。
第三行一个数m (m<=1000)，代表接下来共m个操作。接下来m行，分别代表各个操作。下面是各个操作的格式：

  • 插入操作：1 num
  • 删除操作：2
  • 排序操作：第一行两个数3和n，3代表是排序操作，n代表待排序的数的数目，接下来一行n个数是待排序数

保证排序操作只出现一次且一定是最后一个操作。

输出

第一行建堆操作输出建好堆后堆顶的元素。
接下来m个操作，若是插入和删除操作，每行输出执行操作后堆顶的元素的值；若是排序操作，输出一行按升序排序好的结果，每个元素间用空格分隔。

样例

输入

10
-225580 113195 -257251 384948 -83524 331745 179545 293165 125998 376875
10
1 -232502
1 -359833
1 95123
2
2
2
1 223971
1 -118735
1 -278843
3 10
-96567 37188 -142422 166589 -169599 245575 -369710 423015 -243107 -108789

输出

-257251
-257251
-359833
-359833
-257251
-232502
-225580
-225580
-225580
-278843
-369710 -243107 -169599 -142422 -108789 -96567 37188 166589 245575 423015

Limitation

1s, 64MB for each test case.

#include <iostream>
using namespace std;
template<class T>
// 增加长度函数
void changeLengthld(T *&a, int oldLength, int newlength){
    T *temp = new T[newlength];
    int number = min(oldLength, newlength);
    copy(a, a + number, temp);
    delete[]a;
    a = temp;
}
template <class T>
class minHeap{
public:
    minHeap(int n = 10);
    // ~minHeap(){};


    void sorted(T a[], int n); //排序
    void pop(); // 排序时删除
    void initialized(T *theHeap, int theSize); // 排序时初始化


    void push(const T& theElement);
    void top(){
        cout << heap[1] << endl;
    }
private:
    T *heap; // 数组
    int arrayLength; // 数组长度
    int heapSize; // 堆中元素个数
};
// 排序插入
template<class T>
void minHeap<T>::push(const T& theElement){// 把元素theELement加入堆
    // 必要时增加数组长度
    if(heapSize == arrayLength - 1){
        changeLengthld(heap, arrayLength, 2*arrayLength);
        arrayLength *= 2;
    }
    // 为元素theElement寻找插入位置
    // currentNode从新叶子向上移动
    int currentNode = ++heapSize;
    while(currentNode != 1 && heap[currentNode / 2] > theElement){
        // 不能把元素theElement插入在heap[currentNode]
        heap[currentNode] = heap[currentNode / 2];  // 把元素向上移
        currentNode /= 2; // 移向根节点
    }
    heap[currentNode] = theElement;
}


// 排序初始化
template<class T>
void minHeap<T>::initialized(T* theHeap, int theSize){
    // 在数组theHeap[1:theSize]中建立小根堆
    delete []heap;
    heap = theHeap;
    heapSize = theSize;
    // 堆化
    for(int root = heapSize / 2; root >= 1; root--){
        T rootElement = heap[root];
        int child = 2 * root;
        while(child <= heapSize){
            if(child < heapSize && heap[child] > heap[child + 1])
                child++;
            if(rootElement <= heap[child])
                break;
            heap[child/2] = heap[child];
            child *= 2;
        }
        heap[child / 2] = rootElement;
    }
}
// 构造函数
template<class T>
minHeap<T>::minHeap(int n){
    arrayLength = 10;
    heapSize = 0;
    heap = new T[n];
}

// 排序

template<class T>
void minHeap<T>::pop(){
    heap[1].~T(); // 删除最小元素
    T lastElement = heap[heapSize--]; // 删除最后一个元素，然后重新建堆
    // 从跟开始，为最后一个元素找位置
    int currentNode = 1, child = 2;
    while(child <= heapSize){
        if(child < heapSize && heap[child] > heap[child+1]) // 依次进行比较
            child++;
        if(lastElement <= heap[child]) // 如果最后一个元素小于child，直接将lastElement放在根上
            break;
        heap[currentNode] = heap[child]; // 进行继续向孩子比较
        currentNode = child;
        child *=2;
    }
    heap[currentNode] = lastElement; // 为lastElement找到一个位置
}
template<class T>
void minHeap<T>::sorted(T a[],int n){
    initialized(a, n);
    for(int i = n; i>= 1; i--){
        cout << heap[1] << " ";
        pop();
    }
    cout << endl;
}
// 排序删除
int main(){
    int n;
    cin >> n;
    int a[n+1];
    a[0] = 0;
    minHeap<int> B(10);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        B.push(a[i]);
    }
    B.top();
    int m;
    cin >> m;
    for(int j = 0; j < m; j++){
        int d;
        cin >> d;
        switch(d){
            case 1: {int x; cin >> x; B.push(x);B.top();}
                break;
            case 2:{ B.pop();B.top();}
                break;
            case 3: {int num;
                cin >> num; int y[num+1];
                for(int i = 1; i <= num; i++)cin >> y[i];
                y[0]=0;
                B.sorted(y, num);}
                break;
        }
    }

    return 0;
}

格式

输入

一串小写字母组成的字符串（不超过1000000)。

输出

输出这个字符串通过Huffman编码后的长度。

样例

输入

abcdabcaba

输出

19

限制

1s, 1024KiB for each test case.

提示

样例中，'a' 出现了4次，'b' 出现了3次，'c' 出现了2次，'d' 出现了1次
编码为: 'a' : 0 'b' : 10 'c' : 110 'd' : 111

#include <iostream>
using namespace std;
template <class T>
// 定义哈夫曼节点
struct Node {
	T weight;
	Node* leftchild, * rightchild;
Node() {}
	Node(T w) {
		weight = w;
        rightchild = leftchild = NULL;
	}
	Node(T w, Node* r,Node* l) {
		weight = w;
        rightchild = r;
        leftchild = l;
	}

};
template <class T>
class huffmanTree {
public:
	huffmanTree(int* a, int n); // 构造函数
	~huffmanTree(){delete []heap;}; // 析构函数
	void initialize(); // 初始化
	Node<T>* top() { // 返回小根堆的堆顶元素
		return heap[1];
	}
	void push(Node<T>* h); // 插入
	void pop(); // 删除
	void makeTree(); // 建造哈夫曼树
	T cal(Node<T>* t, int n);// 进行计算长度
private:
	Node<T>** heap; // 定义一个指针小根堆
	int heapSize; // 小根堆的长度
};
// 构造函数
template <class T>
huffmanTree<T>::huffmanTree(int* a, int n) {
	heapSize = n; // 定义长度
	heap = new Node<T> * [27];
	for (int i = 1; i <= n; i++) { // 为heap[i]赋值（有值的）
		heap[i] = new Node<T>(a[i - 1]);
	}
}
// 小根堆初始化
template <class T>
void huffmanTree<T>::initialize() {
	for (int root = heapSize / 2; root >= 1; root--) {
		Node<T>* theElement = heap[root];
		int child = root * 2;
		while (child <= heapSize) {
			if (child<heapSize && heap[child]->weight>heap[child + 1]->weight) {
				child++;
			}
			if (theElement->weight <= heap[child]->weight) {
				break;
			}
			heap[child / 2] = heap[child];
			child *= 2;
		}
		heap[child / 2] = theElement;
	}
}
// 小根堆插入
template <class T>
void huffmanTree<T>::push(Node<T>* h) {
	int now = ++heapSize;
	while (now != 1 && heap[now / 2]->weight > h->weight) {
		heap[now] = heap[now / 2];
		now /= 2;
	}
	heap[now] = h;
}
// 小根堆删除
template <class T>
void huffmanTree<T>::pop() {
	Node<T>* theElement = heap[heapSize--];
	int now = 1;
	int child = 2;
	while (child <= heapSize) {
		if (child<heapSize && heap[child]->weight>heap[child + 1]->weight) {
			child++;
		}
		if (theElement->weight <= heap[child]->weight) {
			break;
		}
		heap[now] = heap[child];
		now = child;
		child *= 2;
	}
	heap[now] = theElement;
}
// 建造哈夫曼树
template <class T>
void huffmanTree<T>::makeTree() { // 取小根堆前两个节点进行合并，并将合并之后的结果插入小根堆中
	while (heapSize != 1) {
		Node<T>* x = top();
		pop();
		Node<T>* y = top();
		pop();
		Node<T>* z = new Node<T>(x->weight + y->weight, x, y);
		push(z);
	}
}

// 计算长度
template <class T>
T huffmanTree<T>::cal(Node<T>* t, int n) {
	int sum = 0;
	if (t != NULL) {
		if (t->rightchild == NULL && t->leftchild == NULL) { // 判断是否为子节点，是子节点则计算长度
			sum += n * t->weight;  // 长度等于weight * 层数（根为0层）
		}
		// 递归使用进行左右孩子中的计算
		sum += cal(t->leftchild, n + 1);
		sum += cal(t->rightchild, n + 1);
	}
	return sum;

}
int main() {
	string str;
	cin >> str;
	int num = 0, flag = 0;

	int* a = new int[26]; // 初始化a
	for (int i = 0; i < 26; i++) {
		a[i] = 0;
	}
	for (int i = 0; i < str.length(); i++) {
		a[(int)str[i] - 'a']++;
		if (a[str[i] - 'a'] == 1) {
			num++; // 字母中次数大于等于1的个数
		}
	}
	int* b = new int[num]; // 出现的字母储存在b中
	for (int i = 0; i < 26; i++) {
		if (a[i] != 0) {
			b[flag] = a[i];
			flag++;
		}
	}
	huffmanTree<int> c(b, flag);
	c.initialize();
	c.makeTree();
	cout << c.cal(c.top(), 0) << endl;

	return 0;
}

标签：Node,10,weight,int,void,heap,child,数据结构,山东大学
From： https://www.cnblogs.com/lyz103/p/17355579.html

相关文章

  • 山东大学数据结构实验9 二叉树操作
    描述创建二叉树类。二叉树的存储结构使用链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。格式输入格式第一行为一个数字n(10<=n<=100000)，表示有这棵树有n个节点，编号为1~n。之后n行每行两个数字，第i行的两个数字a、b表示编号......
  • 山东大学数据结构实验8 散列表
    要求使用线性开型寻址实现描述给定散列函数的除数D和操作数m，输出每次操作后的状态。有以下三种操作：插入x，若散列表已存在x，输出“Existed”，否则插入x到散列表中，输出所在的下标。查询x，若散列表不含有x，输出“-1”，否则输出x对应下标。删除x，若散列表不含有x，输出“NotFound”，否......
  • 第10章 枚举类和注解
    1.枚举类的使用枚举类的实现：在JDK1.5之前需要自定义枚举类在JDK1.5之后新增了enum关键字用于定义枚举类枚举类的属性：枚举类对象的属性不应允许被改动，所以应该使用privatefinal进行修饰。（若枚举只有一个对象，则可以作为一种单例模式的实现方式，即privatefinal类名instance=......
  • Oracle 19c的参数sec_case_sensitive_logon与ORA-01017错误
    Oracle的参数sec_case_sensitive_logon是Oracle11g开始被引入。这个参数主要是为了控制密码的大小写敏感问题。sec_case_sensitive_logon=true表示密码区分大小写。sec_case_sensitive_logon=false表示密码不区分大小写。从Oracle12c开始，参数sec_case_sensitive_logon被弃用......
  • Sitecore XP 10.3(latest) Docker一键部署
    本文演示通过PowerShell+DockerDesktopforWindows一键部署Sitecore10.3（即Sitecore最新版）Docker开发/测试/演示环境。官方参考 SitecoreXP10.3.0DeveloperWorkstationDeploymentWithDocker演示配置为XPSingle（XP0） 环境准备1，windows10+/WindowsServer2019(Windows......
  • C++数据结构(树)
    树是一种递归定义的数据结构，如果树中节点的各子树从左到右是有次序的，不能互换，则称该树为有序树，否则叫无序树。关于树的节点：节点拥有的子树的个数叫做节点的度如果度为0，那么该节点叫做叶节点或终端节点，除了根节点外的分支节点称为内部节点树的度是各节点度的最大值。节点的子......
  • SMU Spring 2023 Trial Contest Round 10
    SMUSpring2023TrialContestRound10 A-RemoveDuplicates#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedefpair<string,int>PSI;constintN=2e2+5,INF=0x3f3f3f3f,Mod=1e6;constdoubleeps=1e-6;typedef......
  • 什么是数据结构？
    数据结构研究计算机数据间关系，包括数据的逻辑结构和存储结构及其操作。我们接触一种数据结构，一定要掌握这三个方面基本概念1.数据（Data）数据即信息的载体，是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。2.数据元素（DataElement）数据......
  • 初识数据结构
    什么是数据结构，数据结构可以理解为我们规定数据元素之间具有某种关系或规则，程序员根据这些规则能够更好的管理和操作这些数据。数据元素的关系包括三种：线性关系——1：1线性关系即为数据是一对一的关系，即除了开头的数据元素和最后的数据元素，其他如何应该数据元素有......
  • 2023年电子科技大学ACM-ICPC暑假前集训-数据结构
    Preface学校针对大一新生的暑假前集训的第一个专题DS，由于要求集体写题解就顺便把写好的发上来了由于下面都写了题意所以直接看也能有很多收获，当然非电专的学生的话就没法交题了代码的话由于专题还没结束怕放上来然后被CV导致被爆破，所以应该在这周六专题结束后会放上来下面都是......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99