程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言入門知識 >> C語言入門(二十二)堆和鏈表

C語言入門(二十二)堆和鏈表

編輯:C語言入門知識
堆和鏈表

我們經常在題目中有要求,輸入一個整數,然後以這個整數作為數組的元素個數,下面的程序代碼是錯誤的。
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;
}
}

 

鏈表問題比較復雜,但又是很重要的概念。上面說的輸入,查找,刪除,插入等功能一定要理解,可以參考別的一些資料看看。

上面說的單鏈表,但是單鏈表有一個缺點,就是無法反向操作,當某一個鏈因破壞而斷裂,則整個鏈就被破壞而無法恢復。雙鏈表可以彌補這個缺點,所謂雙鏈表是指每個節點有兩個指針項,一個指針指向其前面的節點,而另一個指針指向後面的節點。關於雙鏈表的使用相對要復雜一些,這裡就不介紹了,可以找其他一些資料看看。
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved