尾指針是相對於頭指針而言的，形式與頭指針相同，內容指向鍊表的最後一個節點。
基本介紹
- 中文名：尾指針
- 套用：數據結構
介紹,代碼,
介紹
通常，鍊表的插入與刪除操作都是在鍊表頭或者鍊表尾進行。如果只保存一個頭指針的話，要在鍊表尾操作時必須先遍歷整個表，增加了時間複雜度，如果能再保存一個尾指針，則可以立即找到鍊表尾，時間複雜度降為O(1)。
在單向循環鍊表中，時常只保存一個尾指針，因為尾指針的下一個節點即是頭結點。這樣便可以方便地在首尾進行操作。
代碼
提供一個帶頭結點和尾指針的單鍊表插入實現參考代碼。
#include <stdio.h>#include <stdlib.h>#define ElementType intstruct ListNode{ ElementType Element; struct ListNode *Next;};typedef struct{ struct ListNode *Head; struct ListNode *Tail;} List, *pList;int InsertTail( ElementType X, pList L ) //尾部插入元素{ struct ListNode *newP; if ( (newP = malloc(sizeof(struct ListNode))) == NULL ) { perror("OUT OF SPACE!"); return -1; } newP->Element = X; newP->Next = NULL; L->Tail->Next = newP; L->Tail = newP; if ( L->Head->Next == NULL) { L->Head->Next = L->Tail; } return 0;}int InsertHead( ElementType X, pList L ) //頭部插入元素{ struct ListNode *newP; if ( (newP = malloc(sizeof(struct ListNode))) == NULL ) { perror("OUT OF SPACE!"); return -1; } newP->Element = X; newP->Next = L->Head->Next; L->Head->Next = newP; return 0;} int main(){ pList L; if ( (L = malloc(sizeof(List))) == NULL ) { perror("OUT OF SPACE!"); return -1; } if ( (L->Head = malloc(sizeof(struct ListNode))) == NULL ) { perror("OUT OF SPACE!"); return -1; } L->Head->Next = NULL; //初始化 L->Tail = L->Head; InsertTail( 10, L ); InsertTail( 11, L ); InsertTail( 12, L ); //三次尾部插入 InsertHead( 13, L ); InsertHead( 14, L ); //兩次頭部插入 InsertTail( 15, L ); InsertTail( 16, L ); //兩次尾部插入 while( L->Head->Next != NULL ) //遍歷輸出 { printf("%d ", L->Head->Next->Element); L->Head = L->Head->Next; } puts(""); return 0;}運行結果
jimmy@MyPet:~/code/learnc$ makegcc -Wall -g -o test test.c -std=c99jimmy@MyPet:~/code/learnc$ ./test 14 13 10 11 12 15 16
