[科普中国]-尾结点

数据结构中，尾结点是指链表中最后一个节点，即存储最后一个元素的节点，与之对应的是头结点，在链表的第一个结点之前附设一个结点。在单链表中，尾结点的指针一般为空，即没有保存其他节点的存储位置信息。但在双向链表中，尾结点一般指向链表中第一个节点。

简介尾结点是链表中的最后一个节点，一般尾结点的指针的指向为空。当单链表的插入方式为尾插法时，尾结点的指针指向不为空，即尾结点变为中第一个节点，链表中有个尾指针指向尾结点。

线性表线性表是数据结构中的重要组成部分。也是程序设计中应用最广泛的一种数据结构，它的主要特点是在线性序列中的每一个结点只有1个前驱，也只有1个后继。线性表的存储方式有顺序存储方式和链式存储方式。用顺序存储方式实现线性表的存储，使得逻辑上连续的元素在物理存储上也是连续的，同时对线性表中的数据可以实现随机存取，而链式存储主要是对线性表中的相邻元素以相邻或不相邻的存储单元来保存。所以在链式存储结构中，每个结点除了保存元素信息以外，都至少还需1个指针来保存后继结点的地址。也就是说，1个结点由1个数据域和1个指针域组成。链式存储结构表示线性表中的数据元素时，要先通过1个算法来创建1个链表，称为线性链表。1个结点中只含有1个指针域的线性链表称为单链表或单向链表。而含有2个指针域的链表称为双向链表或双链表，双链表的每个结点中1个指针指向前驱结点，另一个指针指向后继结点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; idata = 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 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 ListLength(L)) // i值不合法 return NULL; for (j = 1; j 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 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 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");}本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所