簡介
尾結點是鍊表中的最後一個節點,一般尾結點的指針的指向為空。當單鍊表的插入方式為尾插法時,尾結點的指針指向不為空,即尾結點變為中第一個節點,鍊表中有個尾指針指向尾結點。
線性表
線性表是數據結構中的重要組成部分。也是程式設計中套用最廣泛的一種數據結構,它的主要特點是線上性序列中的每一個結點只有1個前驅,也只有1個後繼。線性表的存儲方式有順序存儲方式和鏈式存儲方式。用順序存儲方式實現線性表的存儲,使得邏輯上連續的元素在物理存儲上也是連續的,同時對線性表中的數據可以實現隨機存取,而鏈式存儲主要是對線性表中的相鄰元素以相鄰或不相鄰的存儲單元來保存。所以在鏈式存儲結構中,每個結點除了保存元素信息以外,都至少還需1個指針來保存後繼結點的地址。也就是說,1個結點由1個數據域和1個指針域組成。鏈式存儲結構表示線性表中的數據元素時,要先通過1個算法來創建1個鍊表,稱為線性鍊表。1個結點中只含有1個指針域的線性鍊表稱為單鍊表或單向鍊表。而含有2個指針域的鍊表稱為雙向鍊表或雙鍊表,雙鍊表的每個結點中1個指針指向前驅結點,另一個指針指向後繼結點 。
由後往前的逆序創建法
在這種鍊表的創建方式中,首先也要掌握單向鍊表的特點,然後,根據單向鍊表的特點,從尾結點開始,逐個結點地向首結點方向連結,即每次生成的新結點,都將連結在已經存在的鍊表的首部,變成新的首結點。而尾結點是第一個創建的結點。因此,首先就要考慮第一個結點的指針要指向空(即尾結點的指針指向空)。整個鍊表的創建步驟如下:
創建第1個結點A1。第1個被創建的結點為整個鍊表的尾結點。根據單向鍊表的特點,它的指針應指向空。同時,鍊表中只有1個結點,因此這個結點也是已經生成鍊表的首結點。並用一個專門的指針指(在此用h)向這個臨時的首結點。
創建第2個結點A2,並用這個新創建的結點指向已經生成鍊表的臨時首結點。這個新創建的結點A2就成為了已經生成鍊表的新的臨時首結點。所以首結點指針h要指向這個新臨時首結點。
重複第二步的工作,直到所有的結點都生成。
1.創建第1個結點A1。第1個被創建的結點為整個鍊表的尾結點。根據單向鍊表的特點,它的指針應指向空。同時,鍊表中只有1個結點,因此這個結點也是已經生成鍊表的首結點。並用一個專門的指針指(在此用h)向這個臨時的首結點。
2.創建第2個結點A2,並用這個新創建的結點指向已經生成鍊表的臨時首結點。這個新創建的結點A2就成為了已經生成鍊表的新的臨時首結點。所以首結點指針h要指向這個新臨時首結點。
3.重複第二步的工作,直到所有的結點都生成。
雙向鍊表
雙向鍊表也叫雙鍊表,是鍊表的一種,它的每個數據結點中都有兩個指針,分別指向直接後繼和直接前驅。所以,從雙向鍊表中的任意一個結點開始,都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鍊表。