重刷数据结构，小题大做，——难道非要头结点吗？

上面的两点的意思是：1.不管是在第一个位置还是其它位置插入一个新的结点，都是在一个结点之后插入（在第一个位置插入新结点，是在头结点后插入）；如果没有头结点，在第一个位置插入结点是直接给头指针赋值，而在其它位置插入结点是将结点插入到一个结点之后，这两种处理是不同的。删除结点也类似；

2.空表和非空表中都有结点，所以对空表的处理也就一致了。

你可能会疑惑：难道非得要头指针吗？难道没有头结点，插入、删除、空表的处理就不一致了吗？（貌似有一些同学和我有同样的疑问）

不一致问题的来源

教材给出的插入和删除操作的算法如下：

插入结点

删除结点

从上面可以看出，插入和删除结点的核心操作在于改变结点的next指针域指向。而上面都是通过指向结点的指针来改变结点的next域的，比如p->next = q->next。在没有头结点的情况下，如果要插入和删除第一个结点，需要修改头指针。而头指针不属于任何结点，不能通过修改某个结点的next指针域来修改头指针，所以得特殊处理，这就带来了操作的不一致性。头指针、结点的next指针域，它们虽然都是同一种类型的指针，但得分开处理。

所以问题的来源在于：通过指向结点的指针来访问结点的next指针域，这种方法不适合头指针。

书上的解决方法

书上的解决方法就是引入头结点。这样即使是插入或删除第一个结点，而已不需要修改头指针，而只需要通过头指针修改头结点的next指针域。这样操作都一致了。

新的解决方法

前面说了，问题的来源是“通过指向结点的指针来访问结点的next指针域，这种方法不适合头指针” 。这种访问方法把头指针和结点的next指针当做两个不同的东西。那我们为什么不把头指针和结点的next指针域看做同一种东西呢?它们本就是同样的数据类型啊！这样不是可以一致处理了。把它们都看作指向结点的指针，就可以通过指向指针的指针来修改和访问了。新的算法如下：

插入

删除

小弟通过上面的思路写代码证实了，这种方法可以达到同样的效果。不需要添加头结点，而且操作一致。

代码

下面是两份代码，一份是教材上有头结点的版本，一份是本文提出的无头结点的版本。代码都通过测试！

/*
*有头结点版本
*作者：善良超哥哥
*时间：2014-8-16
*/
//LinkList.h
#ifndef _LIMKLIST_H_
#define _LINKLIST_H_typedef struct LNode{char	data;struct LNode *next;
}LNode;typedef struct{LNode	*head;	//指向第一个结点的指针int		len;	//链表长度
}LinkList;//创建链表，尾插法
void CreateList(LinkList *L);
//在第i个位置插入元素e
int ListInsert(LinkList *L,int i,char e);
//删除第i个位置的元素，并用*e返回
int ListDelete(LinkList *L,int i,char *e);
//遍历打印链表中的所有元素
void ListPrint(LinkList *L);#endif

//LinkList.c
/*
有头结点的链表实现
*/#include "LinkList.h"
#include <stdio.h>
#include <stdlib.h>//创建链表，尾插法
void CreateList(LinkList *L)
{L->head = malloc(sizeof(LNode));//创建头结点L->head->next = NULL;L->len = 0;//开始输入字符，创建链表，以#结束char c;LNode *p = L->head;while((c = getchar()) != '#'){LNode *s = malloc(sizeof(LNode));s->data = c;p->next = s;p = s;++(L->len);}p->next = NULL;
}//在第i个位置插入元素e
int ListInsert(LinkList *L,int i,char e)
{if(i < 1 || i > L->len || L == NULL){return 0;//失败}LNode *p = L->head;for(int j = 1; j < i; j++){p = p->next;}LNode *s = malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;++(L->len);return 1;
}//删除第i个位置的元素，并用*返回
int ListDelete(LinkList *L,int i,char *e)
{if(L == NULL || i < 1 || i >= L->len){return 0;//失败了}LNode *p = L->head;for(int j = 1; j < i; j++){p = p->next;}//删除p指针指向的结点的下一个结点LNode *q = p->next;p->next = q->next;free(q);--(L->len);return 1;
}//遍历打印链表中的所有元素
void ListPrint(LinkList *L)
{LNode *p = L->head->next;while(p!=NULL){printf("%c",p->data);p = p->next;}printf("\n");
}

无头结点版本：

/*
*无头结点版本
*作者：善良超哥哥
*时间：2014-8-16
*/
//LinkList.h
#ifndef _LIMKLIST_H_
#define _LINKLIST_H_typedef struct LNode{char	data;struct LNode *next;
}LNode;typedef struct{LNode	*head;	//指向第一个结点的指针int		len;	//链表长度
}LinkList;//创建链表，尾插法
void CreateList(LinkList *L);
//在第i个位置插入元素e
int ListInsert(LinkList *L,int i,char e);
//删除第i个位置的元素，并用*e返回
int ListDelete(LinkList *L,int i,char *e);
//遍历打印链表中的所有元素
void ListPrint(LinkList *L);#endif