一.??靜態鏈表

在某些語言中指針是不被支持的,只能使用數組來模擬線性鏈表的結構.在數組中每個元素不但保存了當前元素的值,還保存了一個”偽指針域”,一般是int類型,用于指向下一個元素的內存地址.

#define?MAXSIZE?100;????

typedef?struct{? ??

??ElemType?data;? ??

??int?cur;? ??

}component,SLinkList[MAXSIZE]; ??

[cpp]?view plain?copy

#define?MAXSIZE?100;???

typedef?struct{???

??ElemType?data;???

??int?cur;???

}component,SLinkList[MAXSIZE];??

這種鏈表在初始時必須分配足夠的空間, 也就是空間大小是靜態的, 在進行插入和刪除時則不需要移動元素, 修改指針域即可,所以仍然具有鏈表的主要優點(快速插入和刪除).

二.動態鏈表
??
如果程序支持指針,則可按照我們的一般形式實現鏈表, 需要時分配,不需要時回收即可.

typedef?struct??node{ ??

?EleType?data; ??

?struct?node?*?pNext; ??

}Node; ??

??

----------------------------------------------------------------------------------------------------------------------------------------------

有些高級語言中沒有“指針”數據類型，只能用數組來模擬線性鏈表的結構，
數組元素中的指針“域”存放的不是元素在內存中的真實地址，而是在數組中的位置。這樣的鏈表
稱為靜態鏈表。

靜態鏈表：把線性表的元素存放在數組的單元中（不一定按邏輯順序連續存放），每個單元不僅存放元素本身 ，而且還要存放其后繼元素所在的數組單元的下標（游標）。

線性表的靜態單鏈表存儲結構?:

#define MAXSIZE 100;

typedef struct{

??ElemType data;

??int cur;

}component,SLinkList[MAXSIZE];

分析?:

這種描述方法便于在不設?”?指針?”?類型的高級程序設計語言中?,?使用的鏈表結構?.?數組的零分量可看成頭節點?.?這種結構仍然需要預先分配一個較大的空間?.?但在插入和刪除的時候?,?不需要移動元素?.?僅需要修改指針?.?所以仍然具有鏈式存儲結構的主要優點?.

鏈表結構可以是動態地分配存儲的，即在需要時才開辟結點的存儲空間，實現動態鏈接。怎樣開辟存貯空間呢？C語言的庫函數提供了以下幾個函數。

1.malloc 函數

該函數如果成功調用，可以在內存中開辟size指定大小的連續空間。返回值類型為void，請注意這不是表示沒有返回值，而是表示返回值可以指向任何類型。該函數是一個返回指針值的函數，如果成功調用，返回所開辟空間的首地址，如果失敗返回NULL。該函數的參數可以用unsigned int size定義空間大小，也可以用變量類型名作參數來定義空間大小。

如：malloc(sizeof(int));開辟2個字節的存儲空間，molloc(sizeof(struct student));開辟10個(4+4+2)字節。該函數返回值是void類型，因此調用時需要強制轉換成需要的類型。

如：（int *）malloc(sizeof(int));

(struct people *)malloc(sizeof(struct student));

2. free 函數

其作用是釋放由p指向的內存區，即將這部分內存還給系統。我們要注意動態開辟的內存在不用之后應及時還給系統，以免造成內存“遺漏”。free函數無返回值。

這里要說明的是，這種能動態開辟存貯空間的區域是內存的堆棧區。

實際上只有建立動態鏈表才是有意義的。

總結

以上是生活随笔為你收集整理的动态链表与静态链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。