堆和鏈表
我們經常在題目中有要求，輸入一個整數，然後以這個整數作為數組的元素個數，下面的程序代碼是
錯誤的。
int n,array[n];
scanf(%d,&n);
在Turbo C中，
不允許出現動態數組。那麼如果必須需要這樣時，就只能使用鏈表了。
一、堆
堆是一種動態存儲結構，實際上就是數據段中的自由存儲區，它是C語言中使用的一種名稱，常常用於動態數據的存儲分配。堆中存入一數據，總是以2字節的整數倍進行分配，地址向增加方向變動。堆可以不斷進行分配直到沒有堆空間為止，也可以隨時進行釋放、再分配，不存在次序問題。
所謂動態數組是指在程序運行期間確定其大小的，如常用到的動態數組，它們是在程序執行過程中動態進行變化的，即在程序開始部分沒有說明大小，只有在程序運行期間用堆的分配函數為其分配存儲空間，分配的大小可根據需要而定，這些數據使用過後，可釋放它們占用的堆空間，並可進行再分配。
堆和棧在使用時相向生長，棧向上生長，即向小地址方向生長，而堆向下增長，即向大地址方向，其間剩余部分是自由空間。使用過程中要防止增長過度而導致覆蓋。
一般的程序我們都是使用小內存模式，它的內存分配如下：
________________
| 代碼段 |
|————————|
| 數據段 |
|————————|
| BSS段 |
|————————|
| 堆 |
|----------------| 自由空間
|----------------|
| 棧 |
|————————|
| 遠堆 |
|----------------|
|________________| 自由空間
在堆和棧之間、以及遠堆地址的後面都是自由空間，總共是64K。
堆管理函數：
1.得到堆和棧之間的自由空間大小的函數
小數據內存模式：unsigned coreleft(void);
大數據內存模式：unsigned long coreleft(void);
對於遠堆，可以用farcoreleft()函數。
2.分配一個堆空間函數
void malloc (unsigned size);
該函數將分配一個大小為size字節的堆空間，並返回一個指向這個空間的指針。由於這個指針是void型的，因此當將它賦給其他類型的指針時，必須對該指針進行強制類型轉換。例如info是一個結構類型指針，即：
struct addr *info;
將由malloc()函數返回的指針賦給info時，必須進行類型轉換：
info=(struct addr *)malloc (sizeof(record));
malloc()函數所分配的堆空間將不進行初始化。在調用malloc()函數時，若當時沒有可用的內存空間，該函數便返回一個NULL指針。
3.分配一個堆空間，其大小為能容納幾個元素，沒有元素長度為size的函數
void calloc(unsigned n,unsigned size);
該函數將分配一個容量為n*size大小的堆空間，並用0初始化分配的空間。該函數將返回一個指向分配空間的指針，沒有空間可用時，則返回一個NULL指針。
4.重新分配堆空間函數
void *realloc(void *ptr,unsigned newsize);
該函數將對由ptr指向的堆空間重新分配，大小變為newsize。
5.釋放堆空間函數
void free(void *ptr);
下面舉一個關於堆和棧的綜合例子：
void push(int);
int pop();
int *pi,*tos;
main()
{
int v;
pi=(int *)malloc(50*sizeof(int));
if(!pi)
{
printf(allocation failure\n);
exit(0);
}
tos=pi;
do
{
printf(please input value,push it;enter 0 then pop;(enter -1 then stop)\n);
scanf(%d,&v);
if(v!=0) push(v);
else printf(pop this is it %d\n,pop());
}
while(v!=-1);
}
void push(int i)
{
pi++;
if(pi==(tos+50))
{
printf(stack overflow\n);
exit(0);
}
*pi=i;
}
int pop()
{
if(pi==tos)
{
printf(stack underflow\n);
exit(0);
}
pi--;
return *(pi+1);
}
程序分配100字節的堆空間，轉換成int型賦給pi，當pi為NULL時，表示沒有可用的空間了，則顯示allocation failure。輸入一個整數，壓入棧中，當超過50時，則顯示stack overflow.當輸入0時，則把棧中的數據彈出。這個程序也演示了棧的後進先出的特點。
二、鏈表
堆是用來存儲動態數據的。動態數據最典型的例子就是鏈表。
形象的說：將若干個數據項按一定的原則前後鏈接起來，沒有數據項都有一個指向下一個數據的指針，則這些數據項靠指針鏈成一個表，最後的一個數據沒有指針(指針為NULL)，這就是鏈表。可以看出鏈表放在存儲器中，並不一定象數組一樣，連續存放，也可以分開存放。由於鏈的各節點均帶有指向下一個節點的地址，因而要找到某個節點，必須要找到上一個節點，如此類推，則可由第一個節點出發找到目的點。鏈表在數據庫建立和管理中用得比較普遍。
鏈表中的每個節點都具有相同的結構類型，它們是由兩部分組成，即數據部分(它們包含一些有用的信息),另一部分就是鏈的指針。下面就定義一個通信鏈節點的數據結構：
struct address
{
char name[30];
char street[40];
char city[20];
char state[10];
char zip[6];
struct address *next; /*pointer to next entry*/
}list_entry;
該結構中前五個成員是該節點的信息部分，最後一個成員是指向同一個結構類型的指針。即next又指向一個同樣結構類型的節點。
1.建立鏈表
建立鏈表時，首先要將第一個節點的內容存入堆中，為此要將堆中能存入該節點內容的內存區域首地址賦給一個指針。我們可以用malloc()函數來分配內存區域。如info是一個指針：
info=(struct address *)malloc(sizeof(list_entry));
當第一個節點存入有info指出的內存區後，再執行該函數，便得到狹義個節點的存儲地址info，此時將該info賦給上一個節點的next，並將該節點內容存入info指出的內存區，這樣兩個節點就鏈接起來了。此過程反復多次，就可不斷的將節點加入鏈表的尾端。
#include stdlib.h
#include alloc.h
#include stdio.h
#include string.h
struct address
{
char name[30];
char street[40];
char city[20];
char state[10];
char zip[6];
struct address *next;
}list_entry;
void inputs(char *,char *,int);
void dls_store(struct address*);
main()
{
struct address *info;
int i;
for(i=0;i<5;i++)
{
info=(struct address *)malloc(sizeof(list_entry));
inputs(enter name:,info->name,30);
inputs(enter street:,info->street,40);
inputs(enter city:,info->city,20);
inputs(enter state:,info->state,10);
inputs(enter zip:,info->zip,6);
dls_store(info);
}
}
void inputs(char *prompt,char *s,int count)
{
char p[255];
do
{
printf(prompt);
gets(p);
if(strlen(p)>count) printf(\n too long \n);
}
while(strlen(p)>count);
strcpy(s,p);
}
void dls_store(struct address *in)
{
static struct address *last=NULL;
if(!last) last=in;
else last->next=in;
in->next=NULL;
last=in;
}
inputs()函數比較簡單，就不說明了。
dls_store()函數是將輸入的節點地址寫到上一個節點的next指針項。其中定義的結構指針last是一個靜態變量，初始值為NULL，這意味著在編譯時將為該變量分配一個固定的存儲空間以存放其值。因初始值為NULL，這樣在第一次調用該函數時，由於它代表一個空指針，因而把由malloc()分配的第一個節點地址賦給它，使last指向該節點，第二次調用時，靜態變量last已指向第一個節點地址。如此反復調用，便建立起了n次調用產生的n個節點的鏈了(本題n=5)。
2.鏈數據的插入和刪除
對於一個已排序好的鏈表(假設是生序)，現在想插入一個數據進去，可能有三種情況：
(1).比首項數據還小，即插入的數據作為首項出現：
這種情況我們的處理方法是：把該數據作為第一項，指針指向原先的首項即可。設原先首項為top，待插入的數據為in，則：
in->next=top;
即可讓該數據作為鏈表的頭。
(2).比最後一項大，即插入的數據作為最後一項出現：
這也很好辦，設原先最後一項為old，則：
old->next=in;
in->next=NULL;
(3).作為中間某一項出現：前面是old,後面是top,則：
old->next=in;
in->next=top;
如果想刪除一個數據，也可能是出現在開頭，中間和結尾。
例如想刪除in這個數據，它原先的前面是old,後面是top,即原先的鏈表是這樣：
old->next=in;
in->next=top;
現在刪除in，只需把old指向top即可:
old->next=top->next;
/*刪除節點函數*/
void delete(struct address *info,struct address *old)
{
if(info)
{
if(info==start) start=info->next; /*刪除的是第一個節點*/
else
{
old->next=info->next; /*被刪除節點前的指針指向下一個節點*/
last=old; /*若節點是鏈表尾，則該節點前的節點指針指向NULL*/
}
free(info); /*釋放刪除節點占用空間*/
}
}
/*查找鏈表中是否有該數據*/
struct address *search(struct address *top,char *n)
{
while(top)
{
if(!strcmp(n,top->name)) return top; /*找到要刪除的節點指針*/
top=top->next; /*繼續找*/
}
return NULL; /*沒有找到*/
}
/*鏈表的輸出*/
void display(struct address *top)
{
while(top)
{
printf(top->name);
top=top->next;
}
}
鏈表問題比較復雜，但又是很重要的概念。上面說的輸入，查找，刪除，插入等功能一定要理解，可以參考別的一些資料看看。
上面說的單鏈表，但是單鏈表有一個缺點，就是無法反向操作，當某一個鏈因破壞而斷裂，則整個鏈就被破壞而無法恢復。雙鏈表可以彌補這個缺點，所謂雙鏈表是指每個節點有兩個指針項，一個指針指向其前面的節點，而另一個指針指向後面的節點。關於雙鏈表的使用相對要復雜一些，這裡就不介紹了，可以找其他一些資料看看。
