雙端堆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、堆是存放在二級緩存中，生命周期由虛擬機的垃圾回收演算法來決定（並不是一旦成為孤兒對象就能被回收）。所以調用這些對象的速度要相對來得低一些。
三、堆棧數據結構區別：
堆（數據結構）：堆可以被看成是一棵樹，如：堆排序；
棧（數據結構）：一種先進後出的數據結構。