-
尾指針
鎖定
尾指針是相對於頭指針而言的，形式與頭指針相同，內容指向鏈表的最後一個節點。
- 中文名
- 尾指針
- 應 用
- 數據結構
尾指針介紹
通常，鏈表的插入與刪除操作都是在鏈表頭或者鏈表尾進行。如果只保存一個頭指針的話，要在鏈表尾操作時必須先遍歷整個表，增加了時間複雜度，如果能再保存一個尾指針
[1]
，則可以立即找到鏈表尾，時間複雜度降為O(1)。
在單向循環鏈表中，時常只保存一個尾指針，因為尾指針的下一個節點即是頭結點。這樣便可以方便地在首尾進行操作。
尾指針代碼
提供一個帶頭結點和尾指針的單鏈表插入實現參考代碼。
#include <stdio.h>
#include <stdlib.h>
#define ElementType int
struct 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$ make gcc -Wall -g -o test test.c -std=c99 jimmy@MyPet:~/code/learnc$ ./test 14 13 10 11 12 15 16
- 參考資料
-
- 1. 循環隊列中的頭尾指針設計 ．萬方[引用日期2018-08-06]
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：6次歷史版本
- 最近更新： 小贤Kn