双端堆c语言

① c语言中怎么实现双端队列这个数据结构

双端队列数据类型
typedef
struct
qnode
{
DataType
data;
struct
qnode
*next;
}LQNode;
typedef
struct
{
LQNode
*front;
LQNode
*rear;
}LQueue;
尾出队：首先判断队列是否为空，如为空则提示队列为空，如不为空则将队尾结点
赋给临时结点。将队尾结点的前驱指针赋给队列的队尾指针，再将队尾结
点的后继指针置空。最后返回临时结点或所需要的数据。

② C语言数据结构 堆的建立和维护

主要函数功能：1、通过输入的数组，建立堆结构
2、将堆结构按小顶堆排列
3、输入POP命令提取一个顶元素，存放在数组中。
（删除顶节点，重新初始化堆结构，重新按小顶堆排列）
4、输入PUSH命令将一个数值插入到堆末尾。
（新数值插入数组末尾，用新数组重建堆，重新按小顶堆排列）
5、打印所有POP提取的顶元素

#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedefstructnode
{
int*data;
structnode*left;
structnode*right;
structnode*brother;
structnode*father;
}NODE;
typedefstructheapTree
{
intsize;
int*nums;//节点数值对应的数组
NODE**nodes;//所有的节点指针，用于释放堆
structnode*rootNode;//根节点
structnode*lastNode;//从上往下，从左往右数最后一个节点
}HEAP;
HEAP*initHeap(int*nums,intsize);//初始化堆
voidrecom(NODE*lastNode,intb);//重组堆，按小顶堆排列。先和子女比较，再兄弟和子女比较，再父亲和子女比较。
//参数：lastNode最后一个节点;b避免兄弟间无限循环，b=2跳出兄弟，进行父亲与子女比较,首次调用b传值1
voidprintfHeap(NODE*rootNode);//测试调试使用：遍历并打印堆数值
voidfreeHeap(HEAP*heap);//释放堆内存
intgetRootNode(HEAP*heap);//取出顶元素
voidaddRootNode(HEAP*heap,intnum);//插入节点元素
intmain()
{
inti,m,n,*nums=NULL,*rootNums=NULL,rNumSize=0,xwNum;//xwNum询问数值
charxwStr[5];//询问字符串POP或PUSH
HEAP*heap=NULL;
printf("输入n,m的值： ");
scanf("%d%d",&n,&m);
nums=(int*)malloc(sizeof(int)*n);
printf("输入%d个数字： ",n);
for(i=0;i<n;i++)
scanf("%d",&nums[i]);
heap=initHeap(nums,n);
recom(heap->lastNode,1);
//printfHeap(heap->rootNode);//测试：顺序打印节点

printf("等待%d次询问，请输入POP或PUSH命令: ",m);
while(1)
{
scanf("%s",xwStr);
if(strcmp(xwStr,"POP")==0)
{
rNumSize++;
if(rootNums==NULL)
rootNums=(int*)malloc(sizeof(int)*rNumSize);
else
rootNums=(int*)realloc(rootNums,sizeof(int)*rNumSize);//扩展原取值的存储内存
rootNums[rNumSize-1]=getRootNode(heap);//取出顶元素
//printfHeap(heap->rootNode);//测试：顺序打印节点
}
elseif(strcmp(xwStr,"PUSH")==0)
{
scanf("%d",&xwNum);
addRootNode(heap,xwNum);//插入新元素
//printfHeap(heap->rootNode);//测试：顺序打印节点//插入后重新排序有问题
}

m--;
if(m==0)
break;
}
printf("所有取出的顶端数值为： ");
for(i=0;i<rNumSize;i++)
printf("%d",rootNums[i]);
printf(" ");

return0;
}
voidaddRootNode(HEAP*heap,intnum)//插入节点元素
{
inti,*numsSave=NULL,*nums=heap->nums,size=heap->size;
numsSave=(int*)malloc(sizeof(int)*(size+1));
for(i=0;i<size;i++)
numsSave[i]=nums[i];
nums=NULL;
numsSave[i]=num;//将新元素添加在数组末尾
freeHeap(heap);//释放堆内存
heap=initHeap(numsSave,size+1);//重新初始新的堆
recom(heap->lastNode,1);//重新小顶堆排列
}
intgetRootNode(HEAP*heap)//取出顶元素
{
inti,*numsSave=NULL,*nums=heap->nums,size=heap->size,rootNum;
rootNum=*heap->rootNode->data;
*heap->rootNode->data=nums[size-1];//根节点对应值换成数组最后一位地址值
numsSave=(int*)malloc(sizeof(int)*(size-1));
for(i=0;i<size-1;i++)
numsSave[i]=nums[i];
nums=NULL;//原数组空间将在freeHeap函数中一并释放
freeHeap(heap);//释放堆内存
heap=initHeap(numsSave,size-1);//重新初始新的堆
recom(heap->lastNode,1);//重新小顶堆排列
returnrootNum;
}
voidfreeHeap(HEAP*heap)//释放堆内存
{
inti;
for(i=0;i<heap->size;i++)//释放所有节点空间
{
heap->nodes[i]->data=NULL;
heap->nodes[i]->brother=NULL;
heap->nodes[i]->father=NULL;
heap->nodes[i]->left=NULL;
heap->nodes[i]->right=NULL;
free(heap->nodes[i]);
}
free(heap->nums);
heap->nums=NULL;
heap->nodes=NULL;
heap->lastNode=NULL;
heap->rootNode=NULL;
heap->size=0;
free(heap);
}
voidprintfHeap(NODE*rootNode)//遍历并打印堆数值
{
printf("%d",*rootNode->data);
if(rootNode->father==NULL&&rootNode->left!=NULL)//根节点
printfHeap(rootNode->left);
elseif(rootNode->father->left==rootNode&&rootNode->father->right!=NULL)//如果第左，那么找右
printfHeap(rootNode->father->right);
elseif(rootNode->father->right==rootNode&&rootNode->brother->left!=NULL)//如果第右，那么找左的左儿子
printfHeap(rootNode->brother->left);
else
printf(" ");
}
HEAP*initHeap(int*nums,intsize)
{
inti;
NODE*newNode=NULL;
HEAP*heap=(HEAP*)malloc(sizeof(HEAP));
heap->rootNode=NULL;
heap->lastNode=NULL;
heap->nodes=(NODE**)malloc(sizeof(NODE*)*size);
heap->nums=nums;
for(i=0;i<size;i++)
{
newNode=(NODE*)malloc(sizeof(NODE));
heap->nodes[i]=newNode;
newNode->data=&nums[i];
newNode->left=NULL;
newNode->right=NULL;
newNode->brother=NULL;
newNode->father=NULL;
if(heap->rootNode==NULL)
heap->rootNode=newNode;
elseif(heap->lastNode->father==NULL)//上一个节点为根节点没有兄弟，新节点放在左位置
{
heap->lastNode->left=newNode;
newNode->father=heap->lastNode;
}
elseif(heap->lastNode->father->left==heap->lastNode)//上一个非根左节点，新节点放兄弟位置
{
heap->lastNode->brother=newNode;
newNode->brother=heap->lastNode;
newNode->father=heap->lastNode->father;
newNode->father->right=newNode;
}
elseif(heap->lastNode->father->right==heap->lastNode)//上一个非根右节点，新节点放兄弟左儿子位置
{
heap->lastNode->brother->left=newNode;
newNode->father=heap->lastNode->brother;
}
heap->lastNode=newNode;
}
heap->size=size;
returnheap;
}
voidrecom(NODE*lastNode,intb)//重组堆，按小顶堆排列。先和子女比较，再兄弟和子女比较，再父亲和子女比较。
//参数：lastNode最后一个节点;b避免兄弟间无限循环，b=2跳出兄弟，进行父亲与子女比较
{
intnumSave;
NODE*minNode=NULL,*fNode=lastNode->father,*bNode=lastNode->brother,*lNode=lastNode->left,*rNode=lastNode->right;
if(lNode!=NULL)
{
minNode=lastNode;
if(*minNode->data>*lNode->data)
{
numSave=*minNode->data;
*minNode->data=*lNode->data;
*lNode->data=numSave;
}
}
if(rNode!=NULL)
{
if(*minNode->data>*rNode->data)
{
numSave=*minNode->data;
*minNode->data=*rNode->data;
*rNode->data=numSave;
}
}
if(b==2)
recom(fNode,1);
elseif(bNode!=NULL)
recom(bNode,2);
}

③ 数据结构 选择排序找最大值和最小值

您好，您可以用双端堆。
只有十万个数据而已，数据量并不大。
不管是双端堆、红黑树、还是采用两个堆（一个最大堆一个最小堆），效率相差没多少。
建树或建堆的复杂度都是O(nlogn)，等于排序的复杂度，并且删除都是O(logn)。
如果不用插入数据的话，可以用下面简单的方法
先对数组排序。
然后设置两个位置，int min = 0, max = n - 1;其中n为元素个数，分别表示最小值和最大值的位置。
获取最大值是ary[max]，获取最小值是a[min]。
删除最大值是max--，删除最小值是min++。
初始化复杂度O(nlogn)，查找和删除都是O(1)

④ 双向堆栈怎么实现

http://hi..com/xavnlkofyhbgtyd/item/e7fef0441c80d215896d10dd

⑤ C语言中怎么实现双端队列这个数据结构

双端队列数据类型

typedef struct qnode
{
DataType

data;

struct

qnode

*next;
}LQNode;

typedef struct

{

LQNode

*front;

LQNode

*rear;
}LQueue;
尾出队：首先判断队列是否为空，如为空则提示队列为空，如不为空则将队尾结点
赋给临时结点。将队尾结点的前驱指针赋给队列的队尾指针，再将队尾结
点的后继指针置空。最后返回临时结点或所需要的数据。

⑥ C语言中有无堆的概念

栈，堆，静态区，是内存开辟的三个专属区，C语言的内存分配也就只有这三种方式

1.内存在栈上创建（栈结构）
如函数里定义的变量int i; char str[80]，还有保存函数的所有信息的内存都是在栈上创建的
这块内存是连续的，就好比是一个数组，所以你在内存分配的时候，会发现变量地址是连续的

2.内存在堆上创建（链表结构）
这块内存是有很多内存块组成，很像鞭炮一样串在一根绳子上，但这些内存块的大小不一样，存储在链表结构中的结点中，当你用malloc动态申请是，编译器会根据你内存块的大小从表头一次检索，直到链表中的内存块大于等于你所申请的内存大小时，返回该快内存，如果链表上的内存块大于你所申请的内存时，会将多余内存回收到链表结构，这也就是为什么动态申请内存容易造成内存碎片的产生原因。所以分配内存时你会发现他们的地址不连续

3内存在静态区创建
如全局变量，static变量
这块内存也是连续的，也像一个数组，但它跟栈上创建内存唯一的区别是，内存作用时间不一样，静区内存作用时间是整个“程序”运行时间，栈上内存作用时间是整个“函数”的运行时间，注意“程序”和“函数”的区别

而堆内存作用时间范围是0到整个“程序”运行时间，如果你要在小于整个“程序”运行时间内释放这块内存的话，就要使用free，所以是手动申请手动释放，你自己可以控制，但是写代码的好习惯习惯是程序中有几个malloc就有几个free，这样可以防止内存泄露

代码段指的是代码段寄存器，你写的代码存放在这个寄存器里，等待CPU调用，这个属于微机原理所讨论问题，有兴趣可以学学

⑦ C语言中的栈、堆是什么

C语言中的堆和栈都是一种数据项按序排列的数据结构。

栈就像装数据的桶或箱子

我们先从大家比较熟悉的栈说起吧，它是一种具有后进先出性质的数据结构，也就是说后存放的先取，先存放的后取。

这就如同我们要取出放在箱子里面底下的东西（放入的比较早的物体），我们首先要移开压在它上面的物体（放入的比较晚的物体）。

堆像一棵倒过来的树

而堆就不同了，堆是一种经过排序的树形数据结构，每个结点都有一个值。

通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。

由于堆的这个特性，常用来实现优先队列，堆的存取是随意，这就如同我们在图书馆的书架上取书。

虽然书的摆放是有顺序的，但是我们想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，我们可以直接取出我们想要的书。

(7)双端堆c语言扩展阅读：

关于堆和栈区别的比喻

使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。

使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。

参考资料来源：网络-堆栈

⑧ c语言中 堆怎么理解

c中代码在代码段，数据在数琚段，局部变量在堆栈中，除了这些已经明确安排好的空间，剩余空间称为自由空间，要利用这些空间可以通过内存分配函数，动态分配，这部分空间称为堆空间！堆空间相比栈空间是非常大的，栈空间是非常有限的windows下32位程序，缺省约为1M而每个程序的地址空间为4G，堆空间使用1~2G内存是不成问题的。
至于p那个指针本身是局部变量，p所指内存在堆上出了函数也是可以用的，必须能够传递出去才行，p自己只能在函数内部使用！传递出去的指针必须在适当的时候释放，否则会产生内存泄漏！
1)这么理解似平不是问题，不过太肤浅;
2)由于各种编程语言(包括c，c )不能(也不允许)直接访问内存，和cpu各寄存器，要通过标志符(就是一个名字)来访问它们，这就牵扯到名字的作用域问题了！而内存，寄存器这些东西本来就在和语言无关，只和该语言如何使用有关，通过名字，我们可以更清晰的理解代码的意图，可以更好的安排代码，所以各种语言，通过名字来使用内存和寄存器！这样名字就和内存，寄存器这种实际存在的东西联系到一起了！变量是最经常使用的一种名字了！对c，这种语言自动变量在堆上，只有函数内部甚至内部的一对大括号内可用(即变量名可见，如果变量的相关内容，如变量值，变量地址，传递出去，外部也是可以使用的，当然同一程序的内部变量地址就不要传递了！同样参数和返回值也不要把自动变量地址传递出去，因为已经过期,有可能被别的东西占用了，使用会么错的，而动态分配的内存其实属于全局性质的，传递出去是没问题的，只要能够及时释放就行，那就是无名全局数据，可以通过有名变量(指针)来使用，因为没有名字所以不能直接促使用，因为是全局的所以可以任意传递，因为要管理的，所以用完要释放！因为无名，所以只能间接引用！

⑨ c语言堆和栈，静态区的理解

楼主问这样的问题，需要澄清平台。比如windows下的与linux下的编译器及很多嵌入式C编译器不同。为什么考虑嵌入式C？原因是目前C语言的很大市场在嵌入式领域。windows下，除了某些特殊需要，java，C++，C#已经优势尽显了。

另外，讨论了半天，q在你代码的那里？我怎么没找到？？我眼睛都揉红了也没找见呀
只好表述一下原理
VC下：
1. 函数形参和函数内部非静态局部变量都在栈上分配（所以a,b,p本身都在栈上。但p指向的内容在堆上。q在哪里，我找不到）。
栈的分配的方法是：sp-=字数。
sp是堆栈指针。”字数“是说：你分配一个字节的局部变量，编译器也给你一个字的长度的空间。原因是，堆栈是具有字长度的。16位、32位机器下，字长度为16，64位机器下，字长度为32.
而且，windows下，栈是从高地址向低地址增长的。为什么？栈与堆共享空间，并且，堆从低向高长，栈从高向低长，降低溢出风险。

静态区名字本身就说明了他的特性：静止的，不随程序的运行变化。也就是相对的说，堆和栈都是动态的。静态区是编译器在编译时指定长度、链接时定位地址、windows载入器载入时分配内存。
这里的动与静是编译器和链接器的说法，是语言层面。不适用于系统层面。Windows随时可能将任何用户程序程序的全部资源“请出”内存，也可重新载入，此时，什么静都是浮云。

还有返回值。楼主的main不返回值编译器会警告你的。返回值存在什么地方？
答案是寄存器里AX（EAX，DX，EDX等）。

嵌入式系统里可能这些都不适用。比如，某些嵌入式处理器的形参直接使用寄存器（R0~R15，或A、B等）

⑩ 浅析C语言中堆和栈的区别

一、堆栈空间分配区别：
1、栈（操作系统）：由操作系统自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈；
2、堆（操作系统）： 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收，分配方式倒是类似于链表。
二、堆栈缓存方式区别：
1、栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放；
2、堆是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些。
三、堆栈数据结构区别：
堆（数据结构）：堆可以被看成是一棵树，如：堆排序；
栈（数据结构）：一种先进后出的数据结构。