數據結構中，尾結點是指鍊表中最後一個節點，即存儲最後一個元素的節點，與之對應的是頭結點，在鍊表的第一個結點之前附設一個結點。在單鍊表中，尾結點的指針一般為空，即沒有保存其他節點的存儲位置信息。但在雙向鍊表中，尾結點一般指向鍊表中第一個節點。
基本介紹
- 中文名：尾結點
- 外文名：Tail node
- 學科：數據結構
- 定義：鍊表中最後一個節點
- 有關術語：鍊表
- 作用：存儲元素及存儲位置
簡介,線性表,由後往前的逆序創建法,雙向鍊表,
簡介
尾結點是鍊表中的最後一個節點，一般尾結點的指針的指向為空。當單鍊表的插入方式為尾插法時，尾結點的指針指向不為空，即尾結點變為中第一個節點，鍊表中有個尾指針指向尾結點。
線性表
線性表是數據結構中的重要組成部分。也是程式設計中套用最廣泛的一種數據結構，它的主要特點是線上性序列中的每一個結點只有1個前驅，也只有1個後繼。線性表的存儲方式有順序存儲方式和鏈式存儲方式。用順序存儲方式實現線性表的存儲，使得邏輯上連續的元素在物理存儲上也是連續的，同時對線性表中的數據可以實現隨機存取，而鏈式存儲主要是對線性表中的相鄰元素以相鄰或不相鄰的存儲單元來保存。所以在鏈式存儲結構中，每個結點除了保存元素信息以外，都至少還需1個指針來保存後繼結點的地址。也就是說，1個結點由1個數據域和1個指針域組成。鏈式存儲結構表示線性表中的數據元素時，要先通過1個算法來創建1個鍊表，稱為線性鍊表。1個結點中只含有1個指針域的線性鍊表稱為單鍊表或單向鍊表。而含有2個指針域的鍊表稱為雙向鍊表或雙鍊表，雙鍊表的每個結點中1個指針指向前驅結點，另一個指針指向後繼結點。
由後往前的逆序創建法
在這種鍊表的創建方式中，首先也要掌握單向鍊表的特點，然後，根據單向鍊表的特點，從尾結點開始，逐個結點地向首結點方向連結，即每次生成的新結點，都將連結在已經存在的鍊表的首部，變成新的首結點。而尾結點是第一個創建的結點。因此，首先就要考慮第一個結點的指針要指向空(即尾結點的指針指向空)。整個鍊表的創建步驟如下：
- 創建第1個結點A1。第1個被創建的結點為整個鍊表的尾結點。根據單向鍊表的特點，它的指針應指向空。同時，鍊表中只有1個結點，因此這個結點也是已經生成鍊表的首結點。並用一個專門的指針指(在此用h)向這個臨時的首結點。
- 創建第2個結點A2，並用這個新創建的結點指向已經生成鍊表的臨時首結點。這個新創建的結點A2就成為了已經生成鍊表的新的臨時首結點。所以首結點指針h要指向這個新臨時首結點。
- 重複第二步的工作，直到所有的結點都生成。
void CreateListR(Snode *&L, ElemType a[], int n){ Snode *s, *r; int i;L = (Snode *) malloc(sizeof(Snode));L->next = NULL;r = L;for (i=0; i<n;i++){ s = (Snode *)malloc(sizeof(Snode));s->data = a[i];r->next = s;r = s;}r-> next = NULL;}雙向鍊表
雙向鍊表也叫雙鍊表，是鍊表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鍊表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鍊表。
// 線性表的雙向鍊表存儲結構typedef struct DuLNode { ElemType data; struct DuLNode *prior, *next;} DuLNode, *DuLinkList;// 帶頭結點的雙向循環鍊表的基本操作(14個)void InitList(DuLinkList *L) { // 產生空的雙向循環鍊表L *L = (DuLinkList)malloc(sizeof(DuLNode)); if (*L) (*L)->next = (*L)->prior = *L; else exit(OVERFLOW);}void DestroyList(DuLinkList *L) { // 操作結果：銷毀雙向循環鍊表L DuLinkList q, p = (*L)->next; // p指向第一個結點 while (p != *L) { // p沒到表頭 q = p->next; free(p); p = q; } free(*L); *L = NULL;}void ClearList(DuLinkList L) { // 不改變L // 初始條件：L已存在。操作結果：將L重置為空表 DuLinkList q, p = L->next; // p指向第一個結點 while (p != L) { // p沒到表頭 q = p->next; free(p); p = q; } L->next = L->prior = L; // 頭結點的兩個指針域均指向自身}Status ListEmpty(DuLinkList L) { // 初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE if (L->next == L && L->prior == L) return TRUE; else return FALSE;}int ListLength(DuLinkList L) { // 初始條件：L已存在。操作結果：返回L中數據元素個數 int i = 0; DuLinkList p = L->next; // p指向第一個結點 while (p != L) { // p沒到表頭 i++; p = p->next; } return i;}Status GetElem(DuLinkList L, int i, ElemType *e) { // 當第i個元素存在時，其值賦給e並返回OK，否則返回ERROR int j = 1; // j為計數器 DuLinkList p = L->next; // p指向第一個結點 while (p != L && j < i) { // 順指針向後查找，直到p指向第i個元素或p指向頭結點 p = p->next; j++; } if (p == L || j > i) // 第i個元素不存在 return ERROR; *e = p->data; // 取第i個元素 return OK;}int LocateElem(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) { // 初始條件：L已存在，compare()是數據元素判定函式 // 操作結果：返回L中第1個與e滿足關係compare()的數據元素的位序。 // 若這樣的數據元素不存在，則返回值為0 int i = 0; DuLinkList p = L->next; // p指向第1個元素 while (p != L) { i++; if (compare(p->data, e)) // 找到這樣的數據元素 return i; p = p->next; } return 0;}Status PriorElem(DuLinkList L, ElemType cur_e, ElemType *pre_e) { // 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅， // 否則操作失敗，pre_e無定義 DuLinkList p = L->next->next; // p指向第2個元素 while (p != L) { // p沒到表頭 if (p->data == cur_e) { *pre_e = p->prior->data; return TRUE; } p = p->next; } return FALSE;}Status NextElem(DuLinkList L, ElemType cur_e, ElemType *next_e) { // 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼， // 否則操作失敗，next_e無定義 DuLinkList p = L->next->next; // p指向第2個元素 while (p != L) { // p沒到表頭 if (p->prior->data == cur_e) { *next_e = p->data; return TRUE; } p = p->next; } return FALSE;}DuLinkList GetElemP(DuLinkList L, int i) { // 另加 // 在雙向鍊表L中返回第i個元素的地址。i為0，返回頭結點的地址。若第i個元素不存在， // 返回NULL int j; DuLinkList p = L; // p指向頭結點 if (i < 0 || i > ListLength(L)) // i值不合法 return NULL; for (j = 1; j <= i; j++) p = p->next; return p;}Status ListInsert(DuLinkList L, int i, ElemType e) { // 在帶頭結點的雙鏈循環線性表L中第i個位置之前插入元素e，i的合法值為1≤i≤表長+1 // 改進算法2.18，否則無法在第表長+1個結點之前插入元素 DuLinkList p, s; if (i < 1 || i > ListLength(L) + 1) // i值不合法 return ERROR; p = GetElemP(L, i - 1); // 在L中確定第i個元素前驅的位置指針p if (!p) // p=NULL,即第i個元素的前驅不存在(設頭結點為第1個元素的前驅) return ERROR; s = (DuLinkList)malloc(sizeof(DuLNode)); if (!s) return OVERFLOW; s->data = e; s->prior = p; // 在第i-1個元素之後插入 s->next = p->next; p->next->prior = s; p->next = s; return OK;}Status ListDelete(DuLinkList L, int i, ElemType *e) { // 刪除帶頭結點的雙鏈循環線性表L的第i個元素，i的合法值為1≤i≤表長 DuLinkList p; if (i < 1) // i值不合法 return ERROR; p = GetElemP(L, i); // 在L中確定第i個元素的位置指針p if (!p) // p = NULL,即第i個元素不存在 return ERROR; *e = p->data; p->prior->next = p->next; // 此處並沒有考慮鍊表頭，鍊表尾 p->next->prior = p->prior; free(p); return OK;}void ListTraverse(DuLinkList L, void(*visit)(ElemType)) { // 由雙鏈循環線性表L的頭結點出發，正序對每個數據元素調用函式visit() DuLinkList p = L->next; // p指向頭結點 while (p != L) { visit(p->data); p = p->next; } printf("\n");}void ListTraverseBack(DuLinkList L, void(*visit)(ElemType)) { // 由雙鏈循環線性表L的頭結點出發，逆序對每個數據元素調用函式visit() DuLinkList p = L->prior; // p指向尾結點 while (p != L) { visit(p->data); p = p->prior; } printf("\n");}