带头结点头指针与带头结点尾指针的学习

单循环链表

对于单链表而言，如果每次在遍历到单链表中间处时需要遍历整个链表，此时只能往后遍历，前方的指针便会丢失。如图1所示，此时若链表遍历到a2处依旧可以通过尾结点循环到a1处，这是单链表所不能解决的。

图1

带头结点头指针的单循环链表

关于单链表的存取，有时候我们在单链表的第一个结点（有效元素）之前附设一个结点，称之为头结点；指向头结点的指针，称之为头指针如图2；

图2

对于单链表来说，不同在于判空，以及尾结点的next为头结点。

/* 初始化链式线性表 */
Status InitList(LinkList* L)
{
    *L = (LinkList)malloc(sizeof(Node)); /* 产生头结点,并使头指针L指向此头结点 */
    if (!(*L)) /* 存储分配失败 */
        return ERROR;
    (*L)->next = *L; /* 单循环链表 */

    return OK;
}

/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList* L)
{
    LinkList p, q;
    p = (*L)->next;           /*  p指向第一个结点 */
    while (p != (*L))                /*  没到表尾 */
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = *L;        /* 头结点指针域为空 */
    return OK;
}

插入和删除可由图三、图四看出差距不大，可参照单链表的编写改基本操作。

图3

图4

带头结点尾指针的单循环链表

对于带头结点尾指针的单循环链表而言，其不仅判空和初始化不同，就连插入操作和删除操作也不同。如图5.

图5

对于插入和删除而言，由于只知道尾指针，于是对于查找头结点和尾结点都可以O（1）进行。

L->rear->next->next  //首节点。
L->rear    //尾指针指向的尾结点。

学习心得

1.在头结点、头指针、尾结点和尾指针的设置时一定要弄清楚。malloc(sizeof(Node))创建的是一个结点，而（LinkList)malloc(sizeof(Node))是创建的是一个结构体指针。两者的返回值都是指向内存首地址的指针，但（LinkList）进行了强制的类型转换。因为malloc()函数的返回值类型是 void *，void 并不是说没有返回值或者返回空指针，而是返回的指针类型未知。所以在使用 malloc() 时通常需要进行强制类型转换，将 void 指针转换成我们希望的类型。
2.初始化工作在头结点头指针和头结点尾指针是不同的。
头结点头指针的定义：

typedef struct Node
{
    ElemType data;
    struct Node* next;/*定义下一个Node的指针，结点内依旧包含data和next指针*/
}Node;
typedef struct Node* LinkList; /* 定义LinkList */

头结点尾指针的定义：

typedef struct Node
{
    ElemType data;
    struct Node* next;/*定义下一个Node的指针，结点内依旧包含data和next指针*/
}Node;
typedef struct {
    Node* rear;
}*LinkListLast;/* 定义LinkList */

我们可以看到两者在定义时是不同，头结点头指针可以在定义结点的时候直接定义结点首地址的指针，而头结点尾指针多了对于尾指针指向的尾结点的定义如图6。

图6

所以在头结点尾指针的初始化时候需要分配两次内存。

/* 初始化链式线性表 */
/* LinkListLast*表示一个结点，使用*L来接受它的返回的首地址
   LinkListLast表示链表
*/
Status InitList(LinkListLast* L)
{
    (*L) = (LinkListLast)malloc(sizeof(Node)); /*定义链表*/
    (*L)->rear = (Node *)malloc(sizeof(Node)); /* 产生头结点,并使尾指针指向此头结点 */
    
    if (!(*L)->rear) /* 存储分配失败 */
        return ERROR;
    (*L)->rear->next= (*L)->rear; /* 单循环链表 */
    return OK;
}

3.在特定位置之前插入和删除某个特定的结点不同，由于前驱结点的指针无法知道所以容易free(p)后找不到前驱结点。此时我们可以创建一个q结点，q为p前驱，qp一起移动。

Status ListInsert(LinkListLast* L, int i, ElemType e,int k)
{
    int j=1;
    Node *p,*s;
    p = (*L)->rear->next->next;
    if (i == 1) {
        ListInsertHead(*L, e);
        return OK;
    }
    if (i == k) {
        ListInsertTail(*L, e);
        return OK;
    }
    while (p!=(*L)->rear && j < i-1)     /* 寻找第i个结点 */
    {
        
        p = p->next;
        ++j;
    }
    if (!p||j > i) {
        return ERROR;
    }
    s = malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
    s->data = e;
    s->next = p->next;
    p->next = s;

    return OK;
}

Status ListDelete(LinkListLast* L, int i, ElemType* e)
{
    int j;
    Node  *p,*q;
    j = 1;
    p = (*L)->rear->next->next;
    q = malloc(sizeof(Node));
    while (p != (*L)->rear->next && j < i)  /* 遍历寻找第i个元素 */
    {
        q = p;
        p = p->next;
        ++j;
    }
    if (p == (*L)->rear->next || j > i) {
        return ERROR;           /* 链表为空或第i个元素不存在 */
    }
    if (p == (*L)->rear) {
        q->next = p->next;
        *e = p->data;
        (*L)->rear = q;
        free(p);
        return OK;
    }
    q->next = p->next;
    *e = p->data;
    free(p);
    return OK;
}

4.对于头结点尾指针的链表来说，在首结点之前，尾结点之后，查找首尾结点时间复杂度都为O(1)。但需注意若改变在尾结点，那么讨论是否应该改变尾指针。

/* 初始条件：链式线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L表尾插入新的数据元素e，L的长度加1 */
Status ListInsertTail(LinkListLast* L, ElemType e)
{
    Node * s;
    if (!(*L)) {
        return ERROR;
    }
    s = malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
    s->data = e;
    s->next = (*L)->rear->next;      /* 将p的后继结点赋值给s的后继  */
    (*L)->rear->next = s;          /* 将s赋值给p的后继 */
    (*L)->rear = s;
    return OK;
}

完整代码(带头结点尾指针的单循环链表)

#include "stdio.h"    
#include "string.h"

#include "stdlib.h"   

#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */


Status visit(ElemType c)
{
    printf("%d ", c);
    return OK;
}

typedef struct Node
{
    ElemType data;
    struct Node* next;/*定义下一个Node的指针，结点内依旧包含data和next指针*/
}Node;
typedef struct {
    Node* rear;
}*LinkListLast;/* 定义LinkList */

/* 初始化链式线性表 */
/* LinkListLast*表示一个结点，使用*L来接受它的返回的首地址
   LinkListLast表示链表
*/
Status InitList(LinkListLast* L)
{
    (*L) = (LinkListLast)malloc(sizeof(Node));
    (*L)->rear = (Node *)malloc(sizeof(Node)); /* 产生头结点,并使尾指针指向此头结点 */
    
    if (!(*L)->rear) /* 存储分配失败 */
        return ERROR;
    (*L)->rear->next= (*L)->rear; /* 单循环链表 */
    return OK;
}

/* 初始条件：链式线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(LinkListLast L)
{
    if (L->rear->next != L->rear) 
        return FALSE;
    else
        return TRUE;
}

/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkListLast* L)
{
    Node* p, * q;
    LinkListLast Head;
    p = (*L)->rear->next->next;           /*  p指向第一个结点 */
    Head = (*L)->rear->next;
    while (p != Head)                /* p是结构体指针,没到表尾 */
    {
        q = p->next;
        free(p);
        p = q;
    }
     (*L)->rear->next= (*L)->rear;        /*尾指针指向头结点*/
    return OK;
}

/* 初始条件：链式线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(LinkListLast L)
{
    int i = 0;
    Node* p; /* p指向第一个结点 */
    p = L->rear->next->next;
    while (p != L->rear->next)
    {
        i++;
        p = p->next;
    }
    
    return i;
}

/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkListLast L, int i, ElemType* e)
{
    int j;
    Node *p;        /* 声明一结点p */
    p = L->rear->next->next;        /* 让p指向链表L的第一个结点 */
    j = 1;      /*  j为计数器 */
    while (p != L->rear->next && j < i)  /* p不为空或者计数器j还没有等于i时，循环继续 */
    {
        p = p->next;  /* 让p指向下一个结点 */
        ++j;
    }
    if ( !p||j > i)
        return ERROR;  /*  第i个元素不存在 */
    *e = p->data;   /*  取第i个元素的数据 */
    return OK;
}

/* 初始条件：链式线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(LinkListLast L, ElemType e)
{
    int i = 0;
    Node* p = L->rear->next->next;
    while (p!=L->rear->next)
    {
        i++;
        if (p->data == e) /* 找到这样的数据元素 */
            return i;
        p = p->next;
    }

    return 0;
}


/* 初始条件：链式线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkListLast* L, int i, ElemType e,int k)
{
    int j=1;
    Node *p,*s;
    p = (*L)->rear->next->next;
    if (i == 1) {
        ListInsertHead(*L, e);
        return OK;
    }
    if (i == k) {
        ListInsertTail(*L, e);
        return OK;
    }
    while (p!=(*L)->rear && j < i-1)     /* 寻找第i个结点 */
    {
        
        p = p->next;
        ++j;
    }
    if (!p||j > i) {
        return ERROR;
    }
    s = malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
    s->data = e;
    s->next = p->next;
    p->next = s;

    return OK;
}

/* 初始条件：链式线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中表头插入新的数据元素e，L的长度加1 */
Status ListInsertHead(LinkListLast* L,  ElemType e)
{
    Node * s;
    if (!(*L)) {
        return ERROR;
    }
    if ((*L)->rear == (*L)->rear->next) {
        s = malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
        s->data = e;
        s->next = (*L)->rear->next;     /* 将p的后继结点赋值给s的后继  */
        (*L)->rear->next = s;           /* 将s赋值给p的后继 */
        (*L)->rear = s;
        return 0;
    }
    s = malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
    s->data = e;
    s->next = (*L)->rear->next->next;     /* 将p的后继结点赋值给s的后继  */
    (*L)->rear->next->next =s ;           /* 将s赋值给p的后继 */
    
    return OK;
}

/* 初始条件：链式线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L表尾插入新的数据元素e，L的长度加1 */
Status ListInsertTail(LinkListLast* L, ElemType e)
{
    Node * s;
    if (!(*L)) {
        return ERROR;
    }
    s = malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
    s->data = e;
    s->next = (*L)->rear->next;      /* 将p的后继结点赋值给s的后继  */
    (*L)->rear->next = s;          /* 将s赋值给p的后继 */
    (*L)->rear = s;
    return OK;
}

/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkListLast* L, int i, ElemType* e)
{
    int j;
    Node  *p,*q;
    j = 1;
    p = (*L)->rear->next->next;
    q = malloc(sizeof(Node));
    while (p != (*L)->rear->next && j < i)  /* 遍历寻找第i个元素 */
    {
        q = p;
        p = p->next;
        ++j;
    }
    if (p == (*L)->rear->next || j > i) {
        return ERROR;           /* 链表为空或第i个元素不存在 */
    }
    if (p == (*L)->rear) {
        q->next = p->next;
        *e = p->data;
        (*L)->rear = q;
        free(p);
        return OK;
    }
    q->next = p->next;
    *e = p->data;
    free(p);
    return OK;
}

/* 初始条件：链式线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkListLast L)
{
    Node* p = L->rear->next->next;
    while (p!=L->rear->next)
    {
        visit(p->data);
        p = p->next;
        
    }
    printf("\n");
    return OK;
}



int main()
{
   
    LinkListLast L;
    ElemType e;
    Status i;
    int j, k;
    i = InitList(&L);
    printf("初始化L后：ListLength(L)=%d\n", ListLength(L));
    for (j = 1; j <= 10; j++)
        ListInsertTail(&L, j);
    printf("在L的表尾依次插入1～10后：L.data=");
    ListTraverse(L);

    for (j = 12; j <= 17; j++)
        i = ListInsert(&L,3, j,ListLength(L));
    printf("在L的第三个位置依次插入12～17后：L.data=");
    ListTraverse(L);

    printf("ListLength(L)=%d \n", ListLength(L));
    i = ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n", i);

    i = ClearList(&L);
    printf("清空L后：ListLength(L)=%d\n", ListLength(L));
    i = ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n", i);

    for (j = 1; j <= 10; j++)
        ListInsertHead(&L,  j);
    printf("在L的表头依次插入1～10后：L.data=");
    ListTraverse(L);

    printf("ListLength(L)=%d \n", ListLength(L));

    ListInsertHead(&L,  0);
    printf("在L的表头插入0后：L.data=");
    ListTraverse(L);
    printf("ListLength(L)=%d \n", ListLength(L));

    GetElem(L, 5, &e);
    printf("第5个元素的值为：%d\n", e);
    for (j = 3; j <= 4; j++)
    {
        k = LocateElem(L, j);
        if (k)
            printf("第%d个元素的值为%d\n", k, j);
        else
            printf("没有值为%d的元素\n", j);
    }


    k = ListLength(L); /* k为表长 */
    for (j = k + 1; j >= k; j--)
    {
        i = ListDelete(&L, j, &e); /* 删除第j个数据 */
        if (i == ERROR)
            printf("删除第%d个数据失败\n", j);
        else
            printf("删除第%d个的元素值为：%d\n", j, e);
    }
    printf("依次输出L的元素：");
    ListTraverse(L);

    j = 5;
    ListDelete(&L, j, &e); /* 删除第5个数据 */
    printf("删除第%d个的元素值为：%d\n", j, e);

    printf("依次输出L的元素：");
    ListTraverse(L);

  

    i = ClearList(&L);
    printf("\n删除L后：ListLength(L)=%d\n", ListLength(L));
 
    return 0;
}

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,905评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,140评论 2赞 379
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,791评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,483评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,476评论 5赞 364
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,516评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,905评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,560评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,778评论 1赞 296
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,557评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,635评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,338评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,925评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,898评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,142评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,818评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,347评论 2赞 342