尾指针是相对于头指针而言的，形式与头指针相同，内容指向链表的最后一个节点。
介绍
通常，链表的插入与删除操作都是在链表头或者链表尾进行。如果只保存一个头指针的话，要在链表尾操作时必须先遍历整个表，增加了时间复杂度，如果能再保存一个尾指针，则可以立即找到链表尾，时间复杂度降为O(1)。
在单向循环链表中，时常只保存一个尾指针，因为尾指针的下一个节点即是头结点。这样便可以方便地在首尾进行操作。
代码
提供一个带头结点和尾指针的单链表插入实现参考代码。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#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;
}
|
运行结果
|
1
2
3
4
|
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
|
