鍊錶是一種採用「鍊式」儲存結構儲存的線性表。鍊錶的資料元素所佔的儲存單元位址可以是連續的,也可以是不連續的,可依需求暫時、動態地申請分配對應的儲存空間,資料元素之間的邏輯關係可以用「鏈」來表達。
本教學操作環境:windows7系統、Dell G3電腦。
為了克服順序表儲存結構的缺點,充分利用儲存空間和提高運作效率,線性表可以採用另一種儲存結構-鍊式儲存結構。線性表的鍊式儲存結構簡稱「鍊錶(link list)」
鍊錶的資料元素所佔的儲存單元位址可以是連續的,也可以是不連續的,可根據需要暫時、動態地申請分配相應的儲存空間,資料元素之間的邏輯關係可以用「鏈」來表達。
鍊錶的插入和刪除不需要移動資料元素,只需要修改鏈即可實現。
鍊錶分類:
1.以鍊錶記憶體分配實作的方式分類
①動態鍊錶
②靜態鍊錶
#2 .依連結方式分類
①單鍊錶
②循環鍊錶
③雙鍊錶
(它們皆為動態鍊錶)
為了表示每個資料元素ai與其直接後繼資料元素ai 1之間的邏輯關係,對於每個資料元素ai,除了儲存本身的資訊外,還需要儲存一個指示其直接後繼的資訊(後繼的儲存位置-位址)。
儲存資料元素資訊的域稱為資料域,儲存直接後繼位置的域稱為指標域#,指標域中儲存的資訊稱為指標或鏈。
這兩部分資訊組成資料元素ai的儲存映像,稱為結點。
n個結點鏈成一個鍊錶,即線性表(a1,a2,a3,...,an)的鍊式儲存結構,因為鍊錶的每個結點只包含一個指標域,所以稱為單鍊錶。
對於線性表來說,總有個頭有個尾,鍊錶也不例外。鍊錶中指向單鍊錶第一個結點的指標叫做頭指標,整個鍊錶的存取必須從頭指標開始進行,之後的每個結點都是上個結點的後繼指標指向的位置。鍊錶的最後一個結點的指標為「空(通常用NULL表示)」-空指標。
為了方便實現鍊錶的各種運算,在單鍊錶的第一個資料結點之前設一個相同類型的結點,該結點稱為頭結點。
頭結點的資料域可以儲存一個特殊的標誌資訊如鍊錶的長度,也可以不儲存任何資料。
鍊錶的第一個資料結點和最後一個結點又稱為首結點和尾結點。
頭指標:
頭結點:
/*线性表的单链表存储结构*/ /*结点定义*/ typedef struct Node { ElemType data; struct Node *next; }Node; /*单链表定义*/ typedef struct Node *LinkList;
假设存储元素e的结点为s,将s插入到ai结点后面,如何操作?
思考:两句插入代码能否交换?
不能,如果调换过来,会导致ai 1等后面的元素无法找到,因为s的指针域没有指向ai 1的地址。
假设存储元素ai的结点为q,要实现将结点q删除单链表的操作。
存储方式:
时间性能:
①查找
②插入和删除
空间性能:
更多相关知识,请访问常见问题栏目!
以上是鍊錶是一種採用什麼儲存結構儲存的線性表的詳細內容。更多資訊請關注PHP中文網其他相關文章!