精华内容
下载资源
问答
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    常用的数据结构有:数组,栈,链表,队列,树,图,,散列表等,如图所示: 每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。 1、数组 数组是可以再内存连续存储多个元素的...

    本文目录:

    数据结构分类

    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
    常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示:
    这里写图片描述
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。

    1、数组

    数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

    int[] data = new int[100];data[0]  = 1;
    

    优点:
    1、按照索引查询元素速度快
    2、按照索引遍历数组方便

    缺点:
    1、数组的大小固定后就无法扩容了
    2、数组只能存储一种类型的数据
    3、添加,删除的操作慢,因为要移动其他的元素。

    适用场景:
    频繁查询,对存储空间要求不大,很少增加和删除的情况。

    2、栈

    栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
    这里写图片描述
    栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。

    3、队列

    队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队,示例图如下:
    这里写图片描述
    使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

    4、链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
    这里写图片描述
    链表的优点:
    链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
    添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

    缺点:
    因为含有大量的指针域,占用空间较大;
    查找元素需要遍历链表来查找,非常耗时。

    适用场景:
    数据量较小,需要频繁增加,删除操作的场景

    5、树

    是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

    • 每个节点有零个或多个子节点;
    • 没有父节点的节点称为根节点;
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树;

    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树
    这里写图片描述
    二叉树是树的特殊一种,具有如下特点:

    1、每个结点最多有两颗子树,结点的度最大为2。
    2、左子树和右子树是有顺序的,次序不能颠倒。
    3、即使某结点只有一个子树,也要区分左右子树。

    二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

    扩展:
    二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树等,这些数据结构二叉树的基础上衍生了很多的功能,在实际应用中广泛用到,例如mysql的数据库索引结构用的就是B+树,还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大,但算法上比较复杂,想学习的话还是需要花时间去深入的。

    6、散列表

    散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

    记录的存储位置=f(key)

    这里的对应关系 f 成为散列函数,又称为哈希 (hash函数),而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。

    哈希表在应用中也是比较常见的,就如Java中有些集合类就是借鉴了哈希原理构造的,例如HashMap,HashTable等,利用hash表的优势,对于集合的查找元素时非常方便的,然而,因为哈希表是基于数组衍生的数据结构,在添加删除元素方面是比较慢的,所以很多时候需要用到一种数组链表来做,也就是拉链法。拉链法是数组结合链表的一种结构,较早前的hashMap底层的存储就是采用这种结构,直到jdk1.8之后才换成了数组加红黑树的结构,其示例图如下:
    这里写图片描述
    从图中可以看出,左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。

    7、堆

    堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

    • 堆中某个节点的值总是不大于或不小于其父节点的值;

    • 堆总是一棵完全二叉树。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

    堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),满足前者的表达式的成为小顶堆,满足后者表达式的为大顶堆,这两者的结构图可以用完全二叉树排列出来,示例图如下:
    这里写图片描述
    因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

    8、图

    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

    按照顶点指向的方向可分为无向图和有向图:
    这里写图片描述
    这里写图片描述
    图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构,这里不做展开,读者有兴趣可以自己学习深入。

    展开全文
  • 数据结构

    千次阅读 多人点赞 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");
    }
    
    展开全文
  • 数据结构-顺序表基本操作的实现(含全部代码

    万次阅读 多人点赞 2018-09-13 22:14:57
    今天起开始编写数据结构中的各种数据结构及其算法的实现。 主要依据严蔚敏版数据结构教材以及王道数据结构考研辅导书。 今天是线性表的顺序表的实现,主要实现函数如下,读者有需要可以评论,我可以适当加几个。...

    今天起开始编写数据结构中的各种数据结构及其算法的实现。

    主要依据严蔚敏版数据结构教材以及王道数据结构考研辅导书。

    今天是线性表中的顺序表的实现,主要实现函数如下,读者有需要可以评论,我可以适当加几个。

    • CreateList(SqList &L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n)
    • InitList(SqList &L) 参数:顺序表L 功能:初始化 时间复杂度:O(1)
    • InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能:位置i处插入元素e 时间复杂度:O(n)
    • ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能:删除位置i处元素 时间复杂度:O(n)
    • LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能:返回第一个等于e的元素的位置 时间复杂度:O(n)
    • Reverse(SqList &L) 参数:顺序表L 倒置函数 将原顺序表直接倒置
    • PrintList(SqList L) 参数:顺序表L 功能:遍历L,并输出
    • SplitSort(SqList &L) 参数:顺序表L 功能:分开奇偶,并分开排序
    • ClearList(SqList &L) 参数:顺序表L 功能:清空顺序表

    代码如下:

    /*
    Project: sequence_list(数据结构-顺序表)
    Date:    2018/09/12  20191012修改 添加Reverse  20200819修改 添加ClearList
    Author:  Frank Yu
    CreateList(SqList &L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n)
    InitList(SqList &L) 参数:顺序表L 功能:初始化 时间复杂度:O(1)
    InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能:位置i处插入元素e 时间复杂度:O(n)
    ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能:删除位置i处元素 时间复杂度:O(n)
    LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能:返回第一个等于e的元素的位置 时间复杂度:O(n)
    Reverse(SqList &L) 参数:顺序表L 倒置函数 将原顺序表直接倒置
    PrintList(SqList L) 参数:顺序表L 功能:遍历L,并输出
    SplitSort(SqList &L) 参数:顺序表L 功能:分开奇偶,并分开排序
    ClearList(SqList &L) 参数:顺序表L 功能:清空顺序表
    */
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #define MaxSize 100
    #define ElemType int
    #define Status int
    using namespace std;
    //顺序表数据结构
    typedef struct
    {
    	ElemType data[MaxSize];//顺序表元素
    	int length;            //顺序表当前长度
    }SqList;
    //***************************基本操作函数*******************************//
    //初始化顺序表函数,构造一个空的顺序表 
    Status InitList(SqList &L)
    {
    	memset(L.data, 0, sizeof(L));//初始化数据为0
    	L.length = 0;                //初始化长度为0
    	return 0;
    }
    //创建顺序表函数 初始化前n个数据
    bool CreateList(SqList &L, int n)
    {
    	if (n<0 || n>MaxSize)false;//n非法
    	for (int i = 0; i<n; i++)
    	{
    		scanf("%d", &L.data[i]);
    		L.length++;
    	}
    	return true;
    }
    //插入函数 位置i插入数据 i及之后元素后移  1=<i<=length+1 
    bool InsertList(SqList &L, int i, ElemType e)
    {
    	if (i<1 || i>L.length + 1) //判断位置是否有效
    	{
    		printf("位置无效!!!\n");
    		return false;
    	}
    	if (L.length >= MaxSize)//判断存储空间是否已满
    	{
    		printf("当前存储空间已满!!!\n");
    		return false;
    	}
    	for (int j = L.length; j >= i; j--)//位置i及之后元素后移
    	{
    		L.data[j] = L.data[j - 1];
    	}
    	L.data[i - 1] = e;
    	L.length++;
    	return true;
    }
    //删除函数 删除位置i的元素 i之后的元素依次前移
    bool  ListDelete(SqList &L, int i)
    {
    	if (i<1 || i>L.length)
    	{
    		printf("位置无效!!!\n");
    		return false;
    	}
    	for (int j = i; j <= L.length - 1; j++)//位置i之后元素依次前移覆盖
    	{
    		L.data[j - 1] = L.data[j];
    	}
    	L.length--;
    	return true;
    }
    //查找函数 按位置从小到大查找第一个值等于e的元素 并返回位置
    int LocateElem(SqList L, ElemType e)
    {
    	for (int i = 0; i<L.length; i++)//从低位置查找
    	{
    		if (L.data[i] == e)
    			return i + 1;
    	}
    	return 0;
    }
    //倒置函数 将原顺序表直接倒置
    void Reverse(SqList &L)
    {
    	if (L.length)
    		for (int i = 0; i<L.length - 1 - i; i++)
    		{
    			int t = L.data[i];
    			L.data[i] = L.data[L.length - 1 - i];
    			L.data[L.length - 1 - i] = t;
    		}
    }
    //奇偶分开并排序
    void SplitSort(SqList &L)
    {
    	int Even = 0;
    	int Odd = L.length - 1;
    	int i = 0;
    	int j = L.length - 1;
    	bool flag = false;
    	if (L.length)
    		for (; i < j; i++, j--)
    		{
    			while (L.data[i] % 2 != 0)i++;
    			while (L.data[j] % 2 == 0)j--;
    			if (L.data[i] % 2 == 0 && L.data[j] % 2 != 0&&i<j)
    			{
    				int temp = L.data[i];
    				L.data[i] = L.data[j];
    				L.data[j] = temp;
    				flag = true;
    			}
    			if(!flag) //没有交换
    			{
    				Even = L.length - 1;//全奇数
    				Odd = 0; //全偶数
    			}
    		}
    	if (flag)
    	{
    		for(int i=0;i<L.length;i++)
    			if (L.data[i] % 2 == 0) 
    			{
    				Odd = i;
    				Even = i - 1;
    				break;
    			}
    	}
    	sort(L.data, L.data + Even + 1);
    	sort(L.data + Odd, L.data + L.length);
    }
    //清空顺序表
    void ClearList(SqList &L) {
    	L.length = 0;
    }
    //********************************功能函数*****************************************//
    //输出功能函数 按位置从小到大输出顺序表所有元素
    void PrintList(SqList L)
    {
    	printf("当前顺序表所有元素:");
    	for (int i = 0; i<L.length; i++)
    	{
    		printf("%d ", L.data[i]);
    	}
    	printf("\n");
    }
    //创建顺序表函数
    void Create(SqList &L)
    {
    	int n; bool flag;
    	L.length = 0;
    	printf("请输入要创建的顺序表长度(>1):");
    	scanf("%d", &n);
    	printf("请输入%d个数(空格隔开):", n);
    	flag = CreateList(L, n);
    	if (flag) {
    		printf("创建成功!\n");
    		PrintList(L);
    	}
    	else printf("输入长度非法!\n");
    
    }
    //插入功能函数 调用InsertList完成顺序表元素插入 调用PrintList函数显示插入成功后的结果
    void Insert(SqList &L)
    {
    	int place; ElemType e; bool flag;
    	printf("请输入要插入的位置(从1开始)及元素:\n");
    	scanf("%d%d", &place, &e);
    	flag = InsertList(L, place, e);
    	if (flag)
    	{
    		printf("插入成功!!!\n");
    		PrintList(L);
    	}
    }
    //删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果
    void Delete(SqList &L)
    {
    	int place; bool flag;
    	printf("请输入要删除的位置(从1开始):\n");
    	scanf("%d", &place);
    	flag = ListDelete(L, place);
    	if (flag)
    	{
    		printf("删除成功!!!\n");
    		PrintList(L);
    	}
    }
    //查找功能函数 调用LocateElem查找元素
    void Search(SqList L)
    {
    	ElemType e; int flag;
    	printf("请输入要查找的值:\n");
    	scanf("%d", &e);
    	flag = LocateElem(L, e);
    	if (flag)
    	{
    		printf("该元素位置为:%d\n", flag);
    	}
    	else
    		printf("未找到该元素!\n");
    }
    //菜单
    void menu()
    {
    	printf("********1.创建                        2.插入*********\n");
    	printf("********3.删除                        4.查找*********\n");
    	printf("********5.倒置                        6.分奇偶排序***\n");
    	printf("********7.输出                        8.清空*********\n");
    	printf("********9.退出                              *********\n");
    }
    int main()
    {
    	SqList L; int choice;
    	InitList(L);
    	while (1)
    	{
    		menu();
    		printf("请输入菜单序号:\n");
    		scanf("%d", &choice);
    		if (9 == choice) break;
    		switch (choice)
    		{
    		case 1:Create(L); break;
    		case 2:Insert(L); break;
    		case 3:Delete(L); break;
    		case 4:Search(L); break;
    		case 5:Reverse(L); break;
    		case 6:SplitSort(L); break;
    		case 7:PrintList(L); break;
    		case 8:ClearList(L); break;
    		default:printf("输入错误!!!\n");
    		}
    	}
    	return 0;
    }

    结果截图:

    插入结果截图
    删除结果截图
    查找结果截图
    输出结果截图

    ---------------------------------------------2018-09-18更新 添加创建函数 菜单有改动-----------------------------------------

                                                                     

     

    ---------------------------------------------20191012更新 添加Reverse函数--------------------------------------------

    根据下方评论,添加了倒置函数,参考stl的Reverse写法

    template <class _RandomAccessIter>
    _STLP_INLINE_LOOP void
    __reverse(_RandomAccessIter __first, _RandomAccessIter __last, const random_access_iterator_tag &) {
      for (; __first < __last; ++__first)
        _STLP_STD::iter_swap(__first, --__last);
    }
    倒置展示

    2019年10月23日更新,应评论区小伙伴的要求,添加了奇偶分开,并排序的函数

    //奇偶分开并排序
    void SplitSort(SqList &L)
    {
    	int Even = 0;
    	int Odd = L.length - 1;
    	int i = 0;
    	int j = L.length - 1;
    	bool flag = false;
    	if (L.length)
    		for (; i < j; i++, j--)
    		{
    			while (L.data[i] % 2 != 0)i++;
    			while (L.data[j] % 2 == 0)j--;
    			if (L.data[i] % 2 == 0 && L.data[j] % 2 != 0&&i<j)
    			{
    				int temp = L.data[i];
    				L.data[i] = L.data[j];
    				L.data[j] = temp;
    				flag = true;
    			}
    			if(!flag) //没有交换
    			{
    				Even = L.length - 1;//全奇数
    				Odd = 0; //全偶数
    			}
    		}
    	if (flag)
    	{
    		for(int i=0;i<L.length;i++)
    			if (L.data[i] % 2 == 0) 
    			{
    				Odd = i;
    				Even = i - 1;
    				break;
    			}
    	}
    	sort(L.data, L.data + Even + 1);
    	sort(L.data + Odd, L.data + L.length);
    }
    测试全奇偶

     

    有奇偶

    代码已更新至上方全部代码!!!

    -------------------------20200819修改 添加ClearList-------------------------------------

    代码由评论区用户__BlackHole提供,已更新至上方全部代码。

    至于销毁,我是使用的静态分配,如果是new(delete释放)或malloc(free释放)的话,需要释放空间,其实就是堆和栈的区别。

    堆和栈的区别就是申请方式不同:栈是系统自动分配空间,而堆则是程序员根据需要申请空间。由于栈上的空间是自动分配自动回收的,所以,栈内数据的生存周期只是在函数的运行过程中,运行后就释放掉。而堆上的数据只要程序员不释放空间,就一直可以访问到,缺点是一旦忘记释放会造成内存泄露。

    综上,我写的顺序表不需要进行销毁,当然,顺序表最大长度也固定了,各有利弊,如果是动态分配的话记得释放空间呀!

    更多数据结构与算法的实现:数据结构(严蔚敏版)与算法的实现(含全部代码)

    本人b站账号:lady_killer9

    有问题请下方评论,转载请注明出处,并附有原文链接,谢谢!如有侵权,请及时联系。如果您感觉有所收获,自愿打赏,可选择支付宝18833895206(小于),您的支持是我不断更新的动力。

    展开全文
  • 堆的特性: 必须是完全二叉树 用数组实现 任一结点的值是其子树所有结点的最大值或最小值 ...数据结构中堆与内存堆区的区别 一、数据结构中的堆和栈 堆和栈在数据结构中是两种不同的数据结构。 两者都是数据...

    堆的特性:

    必须是完全二叉树
    用数组实现
    任一结点的值是其子树所有结点的最大值或最小值
    最大值时,称为“最大堆”,也称大根堆;

    在完全二叉树中,任何一个子树的最大值都在这个子树的根结点。
    

    最小值时,称为“最小堆”,也称小根堆。

    在完全二叉树中,任何一个子树的最小值都在这个子树的根结点。
    

    大根堆
    在这里插入图片描述
    小根堆
    在这里插入图片描述
    可以看到,对于**堆(Heap)**这种数据结构,从根节点到任意结点路径上所有的结点都是有序的。

    整理:
    二叉堆

    逻辑上:完全二叉树
    存储上:数组(顺序存储)
    作用:找最值		(优先级队列)
    

    操作:

    1向下调整	*	(建队,删除)
    2建堆
    3向上调整  (插入)
    

    数据结构中堆与内存堆区的区别

    一、数据结构中的堆和栈

       堆和栈在数据结构中是两种不同的数据结构。 两者都是数据项按序排列的数据结构。
    
       栈:像是装数据的桶或者箱子
    
        栈是大家比较熟悉的一种数据结构,它是一种具有后进先出的数据结构,也就是说后存放的先取,
        先存放的后取,这就类似于我们要在取放在箱子底部的东西(放进去比较早的物体),
        我们首先要移开压在它上面的物体(放入比较晚的物体)。
    
       堆:像是一颗倒立的大树
    
       堆是一种经过排序的树形数据结构,每个节点都有一个值。通常我们所说的堆的数据结构是指二叉树。
       堆的特点是根节点的值最小(或最大),且根节点的两个树也是一个堆。
       由于堆的这个特性,常用来实现优先队列,堆的存取是随意的,这就如同我们在图书馆的书架上取书,虽然书的摆放是有顺序的,
       但是我们想取任意一本时不必像栈一样,先取出前面所有的书,书架这种机制不同于箱子,我们可以直接取出我们想要的书。
    

    二、内存分配中的堆和栈

       我们现在经常用的并不是数据结构中的堆和栈,之所以说了数据结构中的堆和栈是为了和后面将要说的堆区和栈区区别开来,请大家一定要注意。
       内存中的栈区处于相对较高的地址,以地址的增长方向为上的话,栈地址是向下增长的。
    
       栈中分配局部变量空间,堆区是向上增长的用于分配程序员申请的内存空间。
       另外还有静态区是分配静态变量,全局变量空间的。
       只读区是分配常量和程序代码空间的;以及其他一些分区。
    

    来看一个很经典的例子:

    main.cpp
    
       int a = 0;  全局初始化区
    
       char *p1;  全局未初始化区
    
       main ()
    
       {
    
       int b; 栈
    
       char  s[] = “abc”;栈
    
       char *p2; 栈
    
       char *p3 = “123456”; 123456\0 在常量区,p3 在栈区
    
       static  int c = 0; 全局(静态)初始化区
    
       p1 = (char *)malloc(10);堆
    
       p2 = (char *)malloc (20);堆
    
       }
    

    三 、 内存分配中栈区和堆区的区别

    0、申请方式和回收方式不同

      不知道你是否有点明白了,堆和栈的第一个区别就是申请方式的不同:栈(英文名字;stack)是系统自动分配空间的
    

    ,例如我们定义了一个 char a ;系统会自动的在栈上为其开辟空间。而堆(英文名字:heap)则是程序员根据需要自己申请的空间,例如malloc(10); 开辟是个字节的空间。由于栈上的空间是自动分配自动回收的,所以栈上的数据的生存周期只是在函数的运行过程中,运行后就释放掉,不可以再访问。而堆上的数据只要程序员不释放空间,就一直可以访问到,不过缺点是一旦忘记释放会造成内存泄露。

    1、 申请后系统的响应

        栈 : 只要栈的剩余空间大于所申请的空间,系统将为程序提供内存,否则将报异常提示栈溢出。
    
    
     堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统受到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆。
    
     结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,
     另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。
     另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。
     也就是说堆会在申请后还要做一些后续的工作这就会引出申请效率的问题
    

    2、申请效率的比较

    栈:  由系统自动分配,速度较快。但程序员是无法控制的。
    
    堆:  是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便。
    

    3、 申请大小的限制

    栈: 在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。
    这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,
    在Windows下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),
    如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。
    
      堆:堆是向高地址扩展的数据结构,是不连续的内存区域。
      这是由于系统是用链表来存储空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。
      堆的大小受限于计算机系统中有效的虚拟内存。
      由此可见,堆获得的空间比较灵活,也比较大。
    

    4、堆和栈中的内存内容

     由于栈的大小限制,所以用子函数还是有物理意义的,而不仅仅是逻辑意义。
    
    栈:在函数调用时,第一个进栈的是主函数中函数调用后的下一条指令(函数调用语句的吓一跳可执行语句)的地址,
    然后是函数的各个参数,在大多数的C编译器中,参数是有右往左入栈的,然后是函数中的局部变量。
    注意静态变量是不入栈的。
    当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,
    也就是主函数中的下一条指令,程序由该点继续运行。
    

    堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。

    5、 关于堆和栈一个比较形象的比喻

    栈:使用栈就像我们去饭馆里吃饭,只管点菜(发出申请)、付钱、吃(使用),吃饱了就走,
    不必理会切菜,洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处就是快捷,但是自由度小。
    
       堆:使用堆就像是自己动手做喜欢的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大
    

    此处参考了博客:http://blog.csdn.net/wolenski/article/details/7951961#comments

    堆的基本操作

    堆就是完全二叉树
    而完全二叉树其实就是数组,你可以把它想象成一个完全二叉树。在数组中定义一个规则,
    在这里插入图片描述
    规则
    左 2i+1
    右 2
    i+2
    父 (i-1)/2

    大根堆的向下调整

    1,每回数组中进来一个树,把它与父结点进行比较,如果比他大,就交换
    2,找父结点,进来的数在数组中的下标(i-1)/2,就是父结点的位置
    

    堆的操作

    堆的向下调整

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    建堆

    小堆的建立

    在这里插入图片描述
    从最后一个非叶子节点开始,不断的向下调整。
    在这里插入图片描述

    向上调整

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 数据结构中循环队列的代码。。。。。。。。。。。。。。。
  • 系统堆栈的故事+数据结构中和栈
  • 图结构 非常得类似我们之前讲到过的树结构,但前者没有很多的...在数学的概念,后者是前者的一种,不过在数据结构中我们还是认为两者有所区别,尽管如此,我们在学习图结构的时候仍可以稍微借鉴一下树结构的思想。
  • 数据结构排序

    千次阅读 2013-12-17 16:39:01
    数据结构中,排序是非常重要的一个知识点,尤其像在期末考试、考研等计算机考试经常会考察排序,并要求画出示意图.下面主要通过一道考研题目讲述排序的知识,希望对大家有所帮助.例使用排序对序列{38,49,13,...
  • 数据结构

    万次阅读 多人点赞 2012-10-16 11:27:35
    在任何时候,任意优先元素都是可以插入到队列去的,是计算机科学一类特殊的数据结构的统称一、的定义最大(最小)是一棵每一个节点的键值都不小于(大于)其孩子(如果存在)的键值的树。大顶堆是一棵完全...
  • 图解数据结构

    千次阅读 2019-12-12 21:59:32
    本篇主要讲解数据结构中堆的实现,效率,使用等。 定义 堆(英语:Heap)是计算机科学中的一种特别的树状数据结构。若是满足以下特性,即可称为堆:“给定堆中任意节点P和C,若P是C的母节点,那么P的值会小于等于...
  • 学习,学习,数据结构 ,课程设计。用反编译软件就能编译出源代码
  • 数据结构串基本操作C语言实现

    千次阅读 多人点赞 2019-03-12 19:40:42
    数据结构】串 串的基本操作 以一组地址连续的存储单元存放串值字符序列,存储空间在程序执行过程动态分配得到,操作灵活。 代码: 1.结构体定义 typedef struct { char * ch; //若是非空串,则按串长分配存储...
  • 、堆栈与数据结构中

    千次阅读 2011-05-05 13:56:00
    (heap): 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收,分配方式倒是类似于链表 数据结构):可以被看成是一棵树,如:排序   有人说的很详细 一、...
  • 数据结构-(heap)与的Python实现

    万次阅读 2018-09-17 20:46:49
    数据结构-树介绍了什么是树,以及二叉树的实现。还记得树的三种特殊结构吗?完美二叉树,满二叉树和完全二叉树。这里介绍的结构就是一种完全二叉树。可分为最大和最小,区别就是父节点是否大于所有子节点。...
  • 数据结构中是一种特殊的二叉树,不同于Java内存模型必须符合以下两个条件: 是一棵完全二叉树。 任意一个节点的值都大于(或小于)左右子节点的值。 ...
  • 比较全面的总结了诸多版本,知识无国界,感谢各位的...首先在数据结构上要知道堆栈,尽管我们这么称呼它,但实际上堆栈是两种数据结构和栈。  和栈都是一种数据项按序排列的数据结构。 栈就像装数据的桶或
  • 数据结构中的栈和,计算机系统内存的栈和的理解
  • 数据结构-线性表-顺序存储结构完整可执行代码

    千次阅读 多人点赞 2013-10-05 13:06:17
    数据结构-线性表-顺序存储结构完整可执行代码(c语言描述)   #include "stdio.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存储空间初始分配量 */ typedef int ...
  • 数据结构练习代码

    2019-04-11 14:58:56
    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术...
  • 数据结构C语言版_串的分配存储表示与实现的教程与代码
  • 数据结构-存储结构

    千次阅读 2017-12-17 10:29:39
    数据结构-存储结构
  • 数据结构)和Java语言提到的没有一点关系。 逻辑上:完全二叉树 物理上:数组 是一种顺序存储结构(采用数组方式存储),仅仅是利用完全二叉树的顺序结构的特点进行分析。 2.结点下标计算公式(根节点...
  • 在C/C++语言,借助数组类型来实现顺序表,也就是说,用数组存放线性表的元素及其逻辑关系,数组的基本类型就是线性表元素的的类型,数组大小(即数组上界-下界+1)要大于等于线性表的长度,否则该数组不能存放...
  • 数据结构链式存储

    2012-12-01 14:19:55
    数据结构链式存储.面向C++的数据结构,链式存储的基本代码
  • 数据结构顺序储存

    2015-10-15 15:53:21
    数据结构中顺序储存表的基本使用,有几种类型的函数操作;方便数据结构初学者对算法的认识,提高代码操作
  • 数据结构-的Java实现

    万次阅读 多人点赞 2018-11-13 19:24:32
    (英语:heap)是计算机科学一类特殊的数据结构的统称。 通常是一个可以被看做一棵树的数组对象。总是满足下列性质: 1.堆中某个节点的值总是不大于或不小于其父节点的值; 2.总是一棵完全二叉树。 将...
  • 课程要求代码数据结构的顺序存储结构用C语言实现。
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机,且能...
  • 最常用的是二叉,但既然是专门介绍数据结构,就不妨说全一些,我们取4个典型的进行比较,见下表(此表及表下备注,来自于广东省中山市第一中学黄源河前辈的《左偏树的特点及其应用》,并做过言辞修改及内容补充...
  • 数据结构和内存中堆和栈的区别

    万次阅读 多人点赞 2015-11-10 11:21:56
     和栈在 我的眼里一直是很模糊的概念,只是简单的理解为:堆栈是一种数据结构,是用来存储数据的。由于最近研究的一些东西,涉及到的和栈比较多,一直都是处于模糊的状态,所以经过仔细研究后有了清晰且有条理...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,172,760
精华内容 469,104
关键字:

数据结构中的堆存储结构代码

数据结构 订阅