C語言入門教程-鏈表棧

鏈表棧

創(chuàng)建一個指針，使它指向另一個指針，這是可能的，而且常常也是必要的。這一技術有時被稱為句柄。在某些情況下，操作系統(tǒng)需要有自主移動堆上的內(nèi)存塊的能力，這時就要用到此技術。下面是一個指針的例子，它指向了另一個指針：

?

 
int **p; 
int *q; 
 
p = (int **)malloc(sizeof(int *)); 
*p = (int *)malloc(sizeof(int)); 
**p = 12; 
q = *p; 
printf("%dn", *q); 
free(q); 
free(p); 

?

?

Windows和Mac OS使用這種結構支持堆上的內(nèi)存壓縮。應用程序使用指針p，而操作系統(tǒng)負責管理指針*p。因為控制了*p，所以操作系統(tǒng)可以移動*p指向的內(nèi)存塊(**p)，并將*p指向新地址，而這一切不會影響使用p的應用程序。在C中，這種指向指針的指針，還常常用于處理函數(shù)的指針參數(shù)。

指向包含指針結構體的指針
創(chuàng)建一個指針，使它指向一個包含指針的結構體，這也是可能的。下例的代碼使用了上一節(jié)的Addr記錄類型：

?

 
typedef struct 
{char name[21];char city[21];char phone[21]; char *comment;} Addr; 
Addr *s; 
char comm[100]; 
 
s=(Addr *)malloc(sizeof(Addr)); 
gets(s->name, 20); 
gets(s->city, 20); 
gets( s->phone, 20); 
gets(comm, 100); 
s->comment=
(char *)malloc(sizeof(char[strlen(comm)+1])); 
strcpy(s->comment, comm); 

?

指針s指向一個結構體，此結構體又包含一個指向字符串的指針：

?

?

本例中，如果不小心很容易將內(nèi)存塊丟失。例如下面的代碼：

?

s=(Addr *)malloc(sizeof(Addr)); 
gets(comm, 100); 
s->comment=
(char *)malloc(sizeof(char[strlen(comm)+1])); 
strcpy(s->comment, comm); 
free(s); 

?

因為包含指向字符串指針的結構體先于字符串被釋放，所以此程序產(chǎn)生了一個內(nèi)存塊泄漏，如下所示：

?

?

鏈接
最后，我們可以創(chuàng)建一種能夠指向同類型結構體的結構體，這樣就可以鏈接起一整串同類型的記錄，構成一種稱為鏈表的數(shù)據(jù)結構。

?

 
typedef struct 
{ char name[21]; char city[21]; char state[21]; Addr *next;} Addr; 
Addr *first; 

?

這是可以通過編譯的。利用上面的代碼，再加上一點編程經(jīng)驗，您就可以創(chuàng)建如下的數(shù)據(jù)結構：

?

?

動手一試
請為棧函數(shù)庫添加dup、count和add函數(shù)，分別用于復制棧頂元素、返回棧包含元素的數(shù)目和將棧頂端的兩個元素相加。
請為棧函數(shù)庫編寫一個測試程序和一個makefile。將棧函數(shù)庫和測試程序一起編譯，確定程序可以正確地工作。?
?

C常見錯誤
提及一個記錄時（如上面的 (*p).i）時忘記加上括號。
分配了內(nèi)存卻無法釋放。例如，在棧函數(shù)中不要寫top=NULL，因為那樣會導致無法訪問需要被釋放的內(nèi)存。
忘記包含stdio.h。為使用NULL，請在涉及指針操作的源文件中包含stdio.h。?