精华内容
下载资源
问答
  • 一部分伪代码 c++代码 #include using namespace std;.../*是一种数据结构,用数组的形式表现出来*/ class stackClass//不需要typedef { private: int data[stack_Size]; int top; public: void i

    一部分伪代码



    c++代码

    #include <iostream>
    
    using namespace std;
    
    #define stack_Size 100
    /*堆是一种数据结构,用数组的形式表现出来*/
    class stackClass//不需要typedef
    {
    private:
        int data[stack_Size];
        int top;
    public:
        void initStack(stackClass &stack);
        void createStack(stackClass &stack,int len);
        void push(stackClass &stack,int x);
        int pop(stackClass stack);
        void destroyStack(stackClass stack);
    };
    /*初始化栈*/
    void stackClass::initStack(stackClass &stack)
    {
        stack.top=-1;//用数组实现栈时一般指向-1
    }
    /*创建栈*/
    void stackClass::createStack(stackClass &stack,int len)
    {
        initStack(stack);//初始化
        cout<<"请依次往栈底输入"<<len<<"个数"<<endl;
        for(int i=0;i<len;++i)//依次往栈底放入len个数
        {
            cin>>stack.data[i];
            stack.top++;
        }
    }
    /*入栈*/
    void stackClass::push(stackClass &stack,int x)
    {
        if(stack.top==stack_Size-1)
            cout<<"栈已满";
        else
            stack.data[++stack.top]=x;
    }
    /*出栈*/
    int stackClass::pop(stackClass stack)
    {
        int x;
        if(stack.top==-1)
            cout<<"栈已空"<<endl;
        else
            x=stack.data[stack.top--];
        return x;
    }
    /*销毁栈*/
    void stackClass::destroyStack(stackClass stack)
    {
        delete []stack.data;
        stack.top=-1;
    }
    
    int main()
    {
        stackClass stack;
        stack.createStack(stack,10);//首先手动往栈中输入10个数
        stack.push(stack,1);//然后依次往栈中送入1,2,3,栈的最顶上元素为3
        stack.push(stack,2);
        stack.push(stack,3);
        cout<<"弹出的数为:"<<stack.pop(stack);//弹出的为最顶上的元素3
        stack.destroyStack(stack);
    
        return 0;
    }
    
    


    运行结果



    展开全文
  • 数据结构

    2021-01-25 15:51:03
    代码实现(小):(1)的定义(2)交换(3)检查容量(4)向下调整(5)向上调整(6)初始化(7)创建(8)销毁(9)的插入(10)的删除(11)获取顶元素(12)判空(13)排序(14)打印 ...

    一、堆

    1. 概念

    如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<=K2i+2 ,则称为小堆(或大堆)。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

    2. 性质

    1. 堆中某个节点的值总是不大于或不小于其父节点的值;
    2. 堆总是一棵完全二叉树。

    3. 结构

    在这里插入图片描述

    二、堆的实现

    1. 算法实现:

    (1)向下调整算法

    堆的向下调整:
    (以小堆为例)

    1. 先设定根节点为当前节点(通过下标获取,标记为cur),比较左右子树的值,找出更小的值,用child来标记。
    2. 比较child和cur的值,如果child比cur小,则不满足小堆的规则,需要进行交换。
    3. 如果child比cur大,满足小堆的规则,不需要交换,调整结束。
    4. 处理完一个节点之后,从当前的child出发,循环之前的过程。

    向下调整(小堆)示例:
    向下调整(小堆)向下调整(大堆)示例:
    向下调整(大堆)

    (2)向上调整算法(堆的创建)

    下面我们给出两个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。

    根节点左右子树不是堆,我们怎么调整呢?

    这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。

    堆的向上调整:
    (以小堆为例)

    1. 先设定倒数的第一个叶子节点为当前节点(通过下标获取,标记为cur),找出他的父亲节点,用parent来标记。
    2. 比较parent和cur的值,如果cur比parent小,则不满足小堆的规则,需要进行交换。
    3. 如果cur比parent大,满足小堆的规则,不需要交换,调整结束。
    4. 处理完一个节点之后,从当前的parent出发,循环之前的过程。
    int a[] =    {9,7,8,10,3,6}
    

    向上调整(小堆)示例:
    在这里插入图片描述

    int a[] =    {1,5,3,8,7,6}
    

    向上调整(大堆)示例:

    在这里插入图片描述

    (3)堆的插入

    将数据插入到数组最后,再进行向上调整。

    int a[]={5,10,15,20}
    int a[]={5,10,15,20,4}
    

    示例:
    在这里插入图片描述

    (4)堆的删除

    删除堆是删除堆顶的数据。

    将堆顶的数据和最后一个数据交换,然后删除数组最后一个数据,再进行向下调整算法。

    示例:
    在这里插入图片描述

    (5)堆的排序

    基本思想:

    1. 将待排序序列构造成一个大顶堆
    2. 此时,整个序列的最大值就是堆顶的根节点。
    3. 将其与末尾元素进行交换,此时末尾就为最大值。
    4. 然后将剩余n-1个元素重新构造成一个堆,这样会得到n-1个元素的次小值。如此反复执行,便能得到一个有序序列了。

    动态演示:
    可视化网站:数据结构和算法动态可视化
    在这里插入图片描述

    2. 代码实现(小堆):

    (以小堆为示例)

    (1)堆的定义

    typedef int HDataType;
    typedef struct heap
    {
    	HDataType* data;
    	int size;
    	int capacity;
    }heap;
    

    (2)交换

    void Swap(int* a, int* b)
    {
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
    

    (3)检查容量

    void checkCapcity(heap* hp)
    {
    	if (hp->capacity == hp->size)
    	{
    		int newC = hp->capacity == 0 ? 1 : 2 * hp->capacity;
    		hp->data = (HDataType*)realloc(hp->data, sizeof(HDataType)*newC);
    		hp->capacity = newC;
    	}
    }
    

    (4)向下调整

    void shiftDown(int* arr, int n, int cur)
    {
    	int child = 2 * cur + 1;
    	while (child < n)
    	{
    		//比较左右子树,找到较小值
    		if (child + 1 < n &&arr[child + 1]<arr[child])
    		{	
    			++child;
    			//child时刻保存较小值的下标
    		}
    		if (arr[child] < arr[cur])
    		{
    			Swap(&arr[child], &arr[cur]);
    			cur = child;
    			child = 2 * cur + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    

    (5)向上调整

    void shiftUp(int* arr, int n, int cur)
    {
    	int parent = (cur - 1) / 2;
    	while (cur > 0)
    	{
    		if (arr[cur] < arr[parent])
    		{
    			Swap(&arr[cur], &arr[parent]);
    			cur = parent;
    			parent = (cur - 1) / 2;
    		}
    		else
    		{
    			break;
    		}
    	}
    
    }
    

    (6)堆的初始化

    void heapInit(heap* hp)
    {
    	assert(hp);
    	hp->data = NULL;
    	hp->capacity = hp->size = 0;
    }
    

    (7)堆的创建

    void heapCreate(heap* hp, int* arr, int n)
    {
    	assert(hp);
    	hp->data = (HDataType*)malloc(sizeof(HDataType)*n);
    	memcpy(hp->data, arr, sizeof(HDataType)*n);
    	hp->capacity = hp->size = n;
    	for (int i = (n - 2) / 2; i >= 0; i--)
    	{
    		shiftDown(hp->data, hp->size, i);
    	}
    }
    
    

    (8)销毁堆

    void heapDestory(heap* hp)
    {
    	assert(hp);
    	free(hp->data);
    	hp->data = NULL;
    	hp->capacity = hp->size = 0;
    }
    

    (9)堆的插入

    void heapPush(heap* hp, HDataType val)
    {
    	assert(hp);
    	checkCapcity(hp);
    	hp->data[hp->size++] = val;
    	shiftUp(hp->data, hp->size, hp->size - 1);
    }
    

    (10)堆的删除

    void heapPop(heap* hp)
    {
    	if (hp->size > 0)
    	{
    		swap(&hp->data[0], &hp->data[hp->size - 1]);
    		hp->size--;
    		shiftDown(hp->data, hp->size, 0);
    	}
    }
    

    (11)获取堆顶元素

    HDataType heapTop(heap* hp)
    {
    	assert(hp);
    	return hp->data[0];
    }
    

    (12)判空

    int heapEmpty(heap* hp)
    {
    	if (hp == NULL || hp->size == 0)
    	{
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    }
    

    (13)堆排序

    void heapSort(heap* hp)
    {
    	assert(hp);
    	for (int i = (hp->size - 2) / 2; i >= 0; i--)
    	{
    		shiftDown(hp->data, hp->size, i);
    	}
    	int end = hp->size - 1;
    	while (end > 0)
    	{
    		Swap(&hp->data[0], &hp->data[end]);
    		shiftDown(hp->data, end, 0); 
    			end--;
    	}
    }
    

    (14)打印堆

    void HeapPrint(heap* hp)
    {
    	assert(hp);
    	for (int i = 0; i < hp->size; i++)
    	{
    		printf("%d ", hp->data[i]);
    	}
    	printf("\n");
    }
    
    展开全文
  • 可以被视为一棵完全二叉树,每个节点的值...2.变量初始化创建构造器 3.插入操作 4.取出最大值操作 5.数据操作 6.将根节点与两边比较和移动的方法 7.层序遍历 8.全部代码 1.编写测试程序 测试插入 ...

    堆可以被视为一棵完全二叉树,每个节点的值都比其子节点大。

    由于是完全二叉树,可以方便的用数组来表示堆,以及实现堆的各种操作(插入,取出最大值,建堆)

    本代码用一维数组实现堆

    目录

    1.编写测试程序

    2.变量初始化,创建构造器

    3.插入操作

    4.取出最大值操作

     5.数据建堆操作

    6.将根节点与两边比较和移动的方法

    7.层序遍历

    8.全部代码


    1.编写测试程序

    测试插入

    import java.util.*;
    public class test {
    	public static void main(String[] args) {		
    		{// 测试插入
    			MaxHeap test1 = new MaxHeap();
    			System.out.println(test1.insert(100));
    			System.out.println(test1.insert(50));
    			System.out.println(test1.insert(51));
    			System.out.println(test1.insert(200));
    			System.out.println(test1.insert(70));
    			System.out.println(test1.insert(150));
    			System.out.println(test1.insert(300));
    			System.out.println("{300,100,200,50,70,51,150}:answer should be ");
    			test1.printMaxHeap();
    			System.out.println();
    			for(int i = 0; i < 9; i++) {
    				if (i != 0) {
    					System.out.print(",");
    				}			
    				test1.deleteMax();
    			}
    			
    			System.out.println();
    			System.out.println();
    		}
    		
    		{// 测试取出最大值
    			MaxHeap test1 = new MaxHeap();
    			test1.printMaxHeap();
    			System.out.println();
    			test1.deleteMax();
    			System.out.print(",");
    			System.out.println();
    			System.out.println();
    
    		}
    		
    		{// 用数组建堆(之前测试的一开始是空堆)
    			int[] testArray = {16,21,75,38,2,50,85,19,61,82};
    			MaxHeap test1 = new MaxHeap(testArray);
    			test1.printMaxHeap();
    			System.out.println();
    			test1.deleteMax();
    		}
    	}
    }

    2.变量初始化,创建构造器

    两种建堆方式,一种是建空堆,一种是用已知数据建堆(先把数据载入堆,再调用建堆方法)

    class MaxHeap {
    	int maxSize = 100;//堆的最大大小
    	int[] array = new int[maxSize+1];
    	int nowSize = 0;//目前堆使用的部分的大小
    	
    	public MaxHeap() {
    		array[0] = Integer.MAX_VALUE;
    	}
    	public MaxHeap(int[] inputArray) {
    		int inputArrayLength = inputArray.length;
    		nowSize =  inputArrayLength;
    		array[0] = Integer.MAX_VALUE;
    		for (int i = 1; i <= inputArrayLength; i++) {
    			array[i] = inputArray[i-1];
    		}
    		buildMaxHeap();
    	}
        //其它方法
    }

    3.插入操作

    先将数字插至数组末尾新增位,然后不断和其父节点比较,如果比父节点大则换位置

            public boolean insert (int data) {
    		
    		if (nowSize == maxSize) {
    			System.out.println("最大堆已满");
    			return false;
    		}
    		nowSize++;
    		int i = nowSize;
    		for (;array[i/2] < data; i = i/2) {// 完全二叉树 n/2是父节点
    			array[i] = array[i/2];// 和插入排序的移动方式类似
    		}
    		array[i] = data;
    		return true;
    	}

    4.取出最大值操作

    1.先把根节点赋给临时变量,然后把数组最后的值移至根节点(赋值),对该值用建树时的排位方法处理,使得整棵树变回大根堆

            public void deleteMax() {
    		if (nowSize == 0) {
    			System.out.print("最大堆已为空");
    			return;
    		}
    		int maxData = array[1];// 取出根节点最大值
    		array[1] = array[nowSize];//将最后值赋给根节点
    		nowSize--;
    		buildFromTreeRoot(1);//对根节点值进行处理
    		System.out.print(maxData);
    		return;//这里可以返回maxData
    	} 

     5.数据建堆操作

    建堆有两种方法,一种是一个个数据插入空堆,则时间复杂度为O(n*logn)。一种是先把数据放入堆,在对每个父子节点进行比较,再处理位置。复杂度为O(n)。

    先把每颗树的子树先处理完再处理根节点,把这个过程迭代下去。最后每个节点所需的调整次数为其高度减一

    public void buildMaxHeap() {
    		for(int i = nowSize / 2; i > 0; i--) {
    			buildFromTreeRoot(i);
    		}	
    	}

    6.将根节点与两边比较和移动的方法

    这里的根节点可以是子树的根节点

    不断的和子节点中最大的比较,若小于则交换

    //将根节点与两边比较和移动的方法
    	public void buildFromTreeRoot(int p) {
    		int temp = array[p];//先用临时变量存下树顶值
    		int Parent;
    		int Child;
    		for (Parent = p ; Parent * 2 <= nowSize ; Parent = Child) {
    			Child = Parent * 2;
    			/* 开始循环说了Parent * 2 <= nowSize,且Child = Parent * 2且Child != nowSize时,那么可以肯定Child+1<=nowSize。
    			 * 那么就可以比较Child和Child++的大小了,反之如果且Child == nowSize,那么Child==nowSize那么自然后面的不用考虑。
    			 */
    			if ((Child != nowSize) && array[Child] < array[Child + 1]) { 
    				Child++;//Child指向左右子节点中的最大者
    			}
    					
    			if ( temp >= array[Child] ) {
    				break;
    			} else { 
    				array[Parent] = array[Child];
    			}
    		}
    		//跳出时没有子结点,或者比子结点大可以跳出了
    		array[Parent] = temp;
    	}

    7.层序遍历

    用于测试

    public void printMaxHeap() {//打印数组相当于层序遍历
    		System.out.print("{");
    		int i;
    		for(i = 1; i <= nowSize; i++) {
    			if (i != 1) {
    				System.out.print(",");
    			}
    			System.out.print(array[i]);
    		}
    		System.out.print("}");
    	}

    8.全部代码

    package maxHeap;
    import java.util.*;
    public class test {
    	public static void main(String[] args) {
    		/*{
    		MaxHeap test1 = new MaxHeap();
    		System.out.println(test1.insert(100));
    		System.out.println(test1.insert(50));
    		System.out.println(test1.insert(51));
    		System.out.println(test1.insert(200));
    		System.out.println(test1.insert(150));
    		System.out.println("{200,150,51,50,100}:answer should be ");
    		test1.printMaxHeap();
    		System.out.println();
    		}
    		
    		{
    			MaxHeap test1 = new MaxHeap();
    			System.out.println(test1.insert(100));
    			System.out.println(test1.insert(50));
    			System.out.println(test1.insert(51));
    			System.out.println(test1.insert(200));
    			System.out.println(test1.insert(70));
    			System.out.println(test1.insert(150));
    			System.out.println("{200,100,150,50,70,51}:answer should be ");
    			test1.printMaxHeap();
    			System.out.println();
    		}*/
    		
    		{// 测试插入
    			MaxHeap test1 = new MaxHeap();
    			System.out.println(test1.insert(100));
    			System.out.println(test1.insert(50));
    			System.out.println(test1.insert(51));
    			System.out.println(test1.insert(200));
    			System.out.println(test1.insert(70));
    			System.out.println(test1.insert(150));
    			System.out.println(test1.insert(300));
    			System.out.println("{300,100,200,50,70,51,150}:answer should be ");
    			test1.printMaxHeap();
    			System.out.println();
    			for(int i = 0; i < 9; i++) {
    				if (i != 0) {
    					System.out.print(",");
    				}			
    				test1.deleteMax();
    			}
    			
    			System.out.println();
    			System.out.println();
    		}
    		
    		{// 测试取出最大值
    			MaxHeap test1 = new MaxHeap();
    			test1.printMaxHeap();
    			System.out.println();
    			test1.deleteMax();
    			System.out.print(",");
    			System.out.println();
    			System.out.println();
    
    		}
    		
    		{// 测试生成大根堆就载入数组
    			int[] testArray = {16,21,75,38,2,50,85,19,61,82};
    			MaxHeap test1 = new MaxHeap(testArray);
    			test1.printMaxHeap();
    			System.out.println();
    			test1.deleteMax();
    		}
    	}
    }
    
    
    class MaxHeap {
    	int maxSize = 100;//堆的最大大小
    	int[] array = new int[maxSize+1];
    	int nowSize = 0;//目前堆使用的部分的大小
    	
    	public MaxHeap() {
    		array[0] = Integer.MAX_VALUE;
    	}
    	public MaxHeap(int[] inputArray) {
    		int inputArrayLength = inputArray.length;
    		nowSize =  inputArrayLength;
    		array[0] = Integer.MAX_VALUE;
    		for (int i = 1; i <= inputArrayLength; i++) {
    			array[i] = inputArray[i-1];
    		}
    		buildMaxHeap();
    	}
    	
    	public boolean insert (int data) {
    		
    		if (nowSize == maxSize) {
    			System.out.println("最大堆已满");
    			return false;
    		}
    		nowSize++;
    		int i = nowSize;
    		for (;array[i/2] < data; i = i/2) {// 完全二叉树 n/2是父节点
    			array[i] = array[i/2];// 和插入排序的移动方式类似
    		}
    		array[i] = data;
    		return true;
    	}
    	
    	public void deleteMax() {
    		if (nowSize == 0) {
    			System.out.print("最大堆已为空");
    			return;
    		}
    		int maxData = array[1];// 取出根节点最大值
    		array[1] = array[nowSize];
    		nowSize--;
    		buildFromTreeRoot(1);
    		System.out.print(maxData);
    		return;//这里可以返回maxData
    	}   
    	
    	
    	public void buildMaxHeap() {
    		//先理子树,子树理完再理根,这样时间复杂度只用O(n)
    		for(int i = nowSize / 2; i > 0; i--) {
    			buildFromTreeRoot(i);
    		}	
    	}
    	
    	//将根节点与两边比较和移动的函数
    	public void buildFromTreeRoot(int p) {
    		int temp = array[p];
    		int Parent;
    		int Child;
    		for (Parent = p ; Parent * 2 <= nowSize ; Parent = Child) {
    			Child = Parent * 2;
    			/* 开始循环说了Parent * 2 <= nowSize,且Child = Parent * 2且Child != nowSize时,那么可以肯定Child+1<=nowSize。
    			 * 那么就可以比较Child和Child++的大小了,反之如果且Child == nowSize,那么Child==nowSize那么自然后面的不用考虑。
    			 */
    			if ((Child != nowSize) && array[Child] < array[Child + 1]) { 
    				Child++;//Child指向左右子节点中的最大者
    			}
    					
    			if ( temp >= array[Child] ) {
    				break;
    			} else { 
    				array[Parent] = array[Child];
    			}
    		}
    		//跳出时没有子结点,或者比子结点大可以跳出了
    		array[Parent] = temp;
    	}
    	
    	/**
    	 * 层序遍历
    	 */
    	public void printMaxHeap() {//打印数组相当于层序遍历
    		System.out.print("{");
    		int i;
    		for(i = 1; i <= nowSize; i++) {
    			if (i != 1) {
    				System.out.print(",");
    			}
    			System.out.print(array[i]);
    		}
    		System.out.print("}");
    	}
    }

     

    展开全文
  • 根据上面输入的数据序列,用初始化方法创建最大(不要用节点依次插入的办法创建最大),然后输出最大的层次序列。 输出用排序后的排序结果。 根据上面输入的数据创建二叉搜索树(关键字不允许重复,如遇...

    实验要求:

    1. 输入一系列不为零的正整数(最多不超过20个),遇到0代表输入结束(不包含0)。
    2. 根据上面输入的数据序列,用初始化方法创建最大堆(不要用节点依次插入的办法创建最大堆),然后输出最大堆的层次序列。
    3. 输出用堆排序后的排序结果。
    4. 根据上面输入的数据,创建二叉搜索树(关键字不允许重复,如遇重复,则不重复插入该关键字),输出二叉搜索树的前序序列、中序序列(分行输出)。

    (输出格式如下图所示
    在这里插入图片描述


    小提示:
    这次试验并不难,而且用到了上一次实验的部分代码,可以进行代码复用(复制),嘿嘿,比如用全局变量commaFlag控制输出格式,还有搜索树的部分函数可以从上一个实验中借鉴(照抄)。


    //my solution
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int commaFlag;
    
    //Max heap part
    template<class T>
    class maxHeap
    {
    public:
    	maxHeap() { heap = NULL; heapSize = 0; }
    
    	void deactivate() { heap = NULL; }//将heap赋空,防止错误释放
    	void initialize(T*, int);
    	T pop();
    	void levelOrder() const;
    protected:
    	T* heap;
    	int heapSize;
    };
    
    template<class T>
    void maxHeap<T>::initialize(T* initHeap, int initSize)
    {
    	//initialize
    	delete[]heap;
    	heap = initHeap;
    	heapSize = initSize;
    	
    	//standardize
    	for (int r = heapSize / 2; r >= 1; r--)
    	{
    		T rElement = heap[r];
    		int rChild = 2 * r;
    		while (rChild <= heapSize)
    		{
    			//rChild is the max one of r'childs
    			if (rChild < heapSize && heap[rChild] < heap[rChild + 1]) rChild++;
    			if (rElement < heap[rChild])
    			{
    				heap[rChild / 2] = heap[rChild];
    				rChild *= 2;
    			}
    			else break;
    		}
    		heap[rChild / 2] = rElement;
    	}
    }
    
    template<class T>
    T maxHeap<T>::pop()
    {
    	T top = heap[1];
    	T lastElement = heap[heapSize--];
    	int current = 1, child = 2;
    	while (child <= heapSize)
    	{
    		if (child < heapSize && heap[child] < heap[child + 1]) child++;
    		if (lastElement < heap[child])
    		{
    			heap[current] = heap[child];
    			current = child;
    			child *= 2;
    		}
    		else break;
    	}
    	heap[current] = lastElement;
    	return top;
    }
    
    template<class T>
    void maxHeap<T>::levelOrder() const
    {
    	for (int i = 1; i < heapSize; i++) cout << heap[i] << ',';
    	cout << heap[heapSize] << endl;
    }
    
    
    //Binary search tree part
    template<class K, class E>
    struct BSTreeNode
    {
    	pair<K, E> thisNode;
    	BSTreeNode<K, E>* leftChild, * rightChild;
    
    	//construct
    	BSTreeNode(const K& key)
    	{
    		thisNode.first = key;
    		thisNode.second = E(0);
    		leftChild = NULL;
    		rightChild = NULL;
    	}
    	BSTreeNode(const pair<const K, E>& thePair)
    	{
    		thisNode.first = thePair.first;
    		thisNode.second = thePair.second;
    		leftChild = NULL;
    		rightChild = NULL;
    	}
    };
    
    template<class K, class E>
    class BSTree
    {
    public:
    	BSTree() { root = NULL; treeSize = 0; }
    	~BSTree() { clear(); }
    
    	int size() const { return treeSize; };
    	void insert(const pair<const K, E>&);
    	void visit(const pair<const K, E>&) const;//访问函数
    	void preOrder() const { preOrder(root); }//前序遍历
    	void inOrder() const { inOrder(root); }//中序遍历
    	void clear() { clear(root); root = NULL; treeSize = 0; }//清空树,所有数据归零
    	void creatTree(K*, E);
    protected:
    	BSTreeNode<K, E>* root;
    	int treeSize;
    
    	void preOrder(BSTreeNode<K, E>*) const ;//前序遍历
    	void inOrder(BSTreeNode<K, E>*) const ;//中序遍历
    	void clear(BSTreeNode<K, E>*);//删除所有节点
    };
    
    template<class K, class E>
    void BSTree<K, E>::insert(const pair<const K, E>& newPair)
    {
    	BSTreeNode<K, E>* parent = NULL, * child = root;
    	while (child != NULL)
    	{
    		parent = child;
    		if (newPair.first > child->thisNode.first) child = child->rightChild;
    		else if (newPair.first < child->thisNode.first) child = child->leftChild;
    		else return;
    	}
    	BSTreeNode<K, E>* newNode = new BSTreeNode<K, E>(newPair.first);
    	if (parent != NULL)
    	{
    		if (newPair.first > parent->thisNode.first) parent->rightChild = newNode;
    		else parent->leftChild = newNode;
    	}
    	else root = newNode;
    	treeSize++;
    }
    
    template<class K, class E>
    void BSTree<K, E>::visit(const pair<const K, E>& theNode) const
    {
    	commaFlag--;
    	if (commaFlag > 0) cout << theNode.first << ",";
    	else cout << theNode.first;
    }
    
    template<class K, class E>
    void BSTree<K, E>::preOrder(BSTreeNode<K, E>* t) const
    {
    	if (t != NULL)
    	{
    		visit(t->thisNode);
    		preOrder(t->leftChild);
    		preOrder(t->rightChild);
    	}
    }
    
    template<class K, class E>
    void BSTree<K, E>::inOrder(BSTreeNode<K, E>* t) const
    {
    	if (t != NULL)
    	{
    		inOrder(t->leftChild);
    		visit(t->thisNode);
    		inOrder(t->rightChild);
    	}
    }
    
    template<class K, class E>
    void BSTree<K, E>::clear(BSTreeNode<K, E>* t)
    {
    	if (t != NULL)
    	{
    		clear(t->leftChild);
    		clear(t->rightChild);
    		delete t;
    	}
    }
    
    template<class K, class E>
    void BSTree<K, E>::creatTree(K* keyArray, E size)
    {
    	pair<K, E> newPair;
    	for (int i = 0; i < size; i++)
    	{
    		newPair.first = keyArray[i];
    		newPair.second = 0;//For convenience, Set all the element values will be set 0.
    		insert(newPair);
    	}
    }
    
    //funtions
    void heapSort(int* arr, int size)
    {
    	maxHeap<int> h;
    	h.initialize(arr, size);
    	for (int i = size; i >= 1; i--) arr[i] = h.pop();//将排序结果导回数组
    	for (int j = 1; j < size; j++) cout << arr[j] << ",";//output
    	cout << arr[size] << endl;
    	h.deactivate();//防止析构时将数组arr错误释放
    }
    
    
    int main()
    {
    	int a[20], b[21], count = 1;
    	cout << "Input" << endl;
    	cin >> a[0];
    	for (; a[count - 1] != 0; count++) cin >> a[count];
    	copy(a, a + count - 1, b + 1);
    
    	cout << "Output" << endl;
    
    	//max heap part
    	maxHeap<int> h;
    	h.initialize(b, count - 1);
    	h.levelOrder();
    	heapSort(b, count - 1);
    
    	//binary search tree part
    	BSTree<int, int> t;
    	t.creatTree(a, count - 1);
    	commaFlag = t.size(); t.preOrder(); cout << endl;
    	commaFlag = t.size(); t.inOrder(); cout << endl;
    	cout << "End";
    	
    	system("pause");
    	return 0;
    }
    

    实验体会:
    发生甚么事了?原来是数据结构做完了啊。
    我啪的一下就把代码敲了上去,很快啊,实验平台一个也没防住,全都通过了。

    展开全文
  • 简单的实现了一下二叉创建初始化,以及取最大,最小元素(大根,小根)。 代码如下: #include #include #include #define father(i) ((i) >> 1) // 父节点 #define lchild(i) ((i) ) // 左结点 #define ...
  • 2、根据上面输入的数据序列,用初始化方法创建最大(不要用节点依次插入的办法创建最大),然后输出最大的层次序列。 3、输出用排序后的排序结果。 4、根据上面输入的数据创建二叉搜索树(关键字不允许...
  • 使用类加载系统把.class文件加载到内存中,将其放在运行时数据区的方法区内,然后在创建一个 java.lang.Class对象,用来封装类在方法区内的数据结构。在这个阶段,会执行类中声明的静态代码块。也就是类中的静态...
  • 类的加载指的是将类的.class文件中二进制数据读入到内存中,将其放在运行时数据区的方法区内,然后在创建一个java.lang.Class对象,用来封装类在方法区内的数据结构。在这个阶段,会执行类中声明的静态代码块。...
  • java.lang.Class对象,用来封装类在方法区内的数据结构。在这个阶段,会执行类中声明的静态代码块。也就是类中的静态块执行时不需要等到类的初始化。 123加载.class文件的方式1、从本地系统中直接加载 2、通过网络...
  • 一定要先初始化链表再建立。以下代码说白了就是一个个的函数出来的,只是要注意函数的参数有时候有引用符&,有时候没有,我总结了一个便于记忆的小技巧:如果你想要对链表做出任何改变,请一定加上&;如.....
  • 构造函数定义初始化赋值的一种写法 无参构造函数定义 调用使用了模板的类创建内存的代码书写格式 注意调用后面加() 调用后执行结果 测试一下用一个结构来分配空间是什么效果 代码修改如下 结构体是12个...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    在计算机科学发展过程中,早期数据结构教材大都采用PASCAL语言为描述工具,后来出现了采用C语言为描述工具的教材版本、至今又出现了采用C++语言为描述工具的多种教材版本。本教实验指导书是为已经学习过C++语言的...
  • avplayer源代码

    热门讨论 2012-05-07 09:45:18
    在player_impl类中, 初始化各模块结构指针由下面几个函数实现, void init_file_source(media_source *ms); void init_audio(audio_render *ao); void init_video(video_render *vo); 你可以根据自己的需求来...
  • 文章目录JVM后台系统线程(仅作了了解)程序计数器虚拟机栈栈帧栈帧的...(1)当一个java线程准备好执行以后,此时操作系统的本地线程也同时创建,一旦调用本地线程初始化成功,操作系统就会调用java线程的run方法。
  • 零起点学通C++多媒体范例教学代码

    热门讨论 2010-11-30 09:35:13
    10.3.2 成员变量的初始化与构造函数 10.3.3 复制构造函数 10.3.4 构造函数和new运算符 10.3.5 再谈默认构造函数 10.4.析构函数和delete运算符 10.4..1 默认析构函数 10.4.2 调用构造函数进行类型转换 10.5 浅层复制...
  • 10.3.2 成员变量的初始化与构造函数 10.3.3 复制构造函数 10.3.4 构造函数和new运算符 10.3.5 再谈默认构造函数 10.4.析构函数和delete运算符 10.4..1 默认析构函数 10.4.2 调用构造函数进行类型转换 10.5 ...
  • 3.5.3 快速文件初始化 100 3.5.4 自动收缩性 100 3.5.5 手动收缩 101 3.6 使用数据库文件组 102 3.6.1 默认文件组 102 3.6.2 FILEGROUP CREATION例子 103 3.6.3 文件流文件组 104 3.7 修改数据库 ...
  • 3.5.3 快速文件初始化 100 3.5.4 自动收缩性 100 3.5.5 手动收缩 101 3.6 使用数据库文件组 102 3.6.1 默认文件组 102 3.6.2 FILEGROUP CREATION例子 103 3.6.3 文件流文件组 104 3.7 修改数据库 ...
  • C++程序设计语言(特别版)--源代码

    热门讨论 2012-04-23 07:33:51
    数据结构--C++与面向对象的途径(修订版) 目录 出版者的话 专家指导委员会 中文版序 译者序 序 第2版序 第1版序 导 论 第1章 致读者 3 1.1 本书的结构 3 1.1.1 例子和参考 4 1.1.2 练习 5 1.1.3 有关...
  • 数据结构--C++与面向对象的途径(修订版) 目录 出版者的话 专家指导委员会 中文版序 译者序 序 第2版序 第1版序 导 论 第1章 致读者 3 1.1 本书的结构 3 1.1.1 例子和参考 4 1.1.2 练习 5 1.1.3 有关...
  • 代码语法错误分析工具pclint8.0

    热门讨论 2010-06-29 07:00:09
    它进行程序的全局分析,能识别没有被适当检验的数组下标,报告未被初始化的变量,警告使用空指针,冗余的代码,等等。软件除错是软件项目开发成本和延误的主要因素。PClint能够帮你在程序动态测试之前发现编码错误。...
  • 书中不仅关注代码本身,同时关注完成这些代码的思路和过程。本书不同于其他的理论型书籍,而是提供给读者一个动手实践的路线图。读者可以根据路线图逐步完成各部分的功能,从而避免了一开始就面对整个操作系统数万行...
  • 书中不仅关注代码本身,同时关注完成这些代码的思路和过程。本书不同于其他的理论型书籍,而是提供给读者一个动手实践的路线图。读者可以根据路线图逐步完成各部分的功能,从而避免了一开始就面对整个操作系统数万行...
  • 一、内存简单介绍 内存结构 ...(2)数据段:已初始化的全局变量和静态变量。 (3)代码段:执行代码的一块区域。 地址由低到高:代码段 -> 数据段 -> BSS段-> -> 栈 内存分...
  • 首先介绍什么是类加载:类加载就是java虚拟机将工程所需的Class文件中的二进制数据到内存中,通过检验,解析,初始化等操作,将静态的字节流转化成方法区中动态的数据结构。类的加载主要分为三个过程:加载、连接...
  • 2020-10-27

    2020-10-27 23:11:53
    栈是一种先进后出的数据结构 内存分配中的和栈 .rodata:常量区 .data:初始化的全局变量和静态变量 .bss:声明但未初始化的全局变量和静态变量 3.JVM虚拟机中的和栈 栈:存放的是方法内部的局部变量 :存放的是...
  • 类加载的全部过程分为5个阶段:加载,验证,准备,解析,初始化。 1.加载  (1)加载二进制文件 根据包名+类名获得二进制文件流,虚拟机没有规定文件从哪里来只要符合规范就行。由类的加载器来决定字节流的来源...
  • jvm-基础知识一

    2020-11-01 20:46:56
    初始化:构造器、静态代码块、静态你变量赋初值。 使用 卸载 2、类加载要完成的功能 通过类的全限定名来获取该类的二进制字节流 把二进制字节流转换为方法区的运行时数据结构。 在创建java.lang.C
  • Java类加载机制由浅入深

    千次阅读 2020-09-14 19:55:06
    类加载具体指将代码编译后生成的.class文件中的二进制数据读入到内存中,将其放在运行时数据区的方法区(具体实现为元空间)内,然后在创建一个java.lang.Class对象,用来封装类在方法区内的数据结构。...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 121
精华内容 48
关键字:

数据结构创建初始化堆代码

数据结构 订阅