初学者学数据结构（三）
线性表的链式存储结构
在顺序表中想要插入或删除一个元素，需要移动大量的元素，这样会严重影响算法的效率。为了解决这个问题，我们引入了线性表的链式存储结构，即链表。
链表有单向链表，双向链表，循环链表三种，由于双向链表和循环链表经过细微的改变而成的，这里我们就主要来讲解单链表。
单链表链式存储结构是用一组不一定是连续的内存存储空间来存储表内的元素，这组内存空间可以是连续的，也可以是非连续的。因为他的内存空间并非连续，所以我们不能用索引的方式来访问表内的元素。这时我们的元素内就不能只写元素的内容，还应该写入下一个元素的地址。
在链式存储结构中，我们把每个元素称为节点，存放元素的内容的地方叫做数据域 data ，存放下个节点地址的地方叫做指针域next，由于在链表中每个节点的地址放在了上一个节点的指针域，为了找到第一个节点，我们引入了头节点，头结点中数据域为空，指针域内存放第一个元素的地址。
单链表示意图：
看了这个图片后大家应该对单向链表有了个大体的概念。
下面我来讲解一下单链表的创建方法。
单链表的创建想要创建一个链表，必须先构造出一个节点来（下面我都以链表中存放的整形为例，但链表放什么都是可以的，数据域是结构体类型也是可以的）：
typedef structNode
{
char name[20] ;
struct Node *next;
}ListNode ,*LinkList;
这样就是一个节点类型，数据域为name数组，指针域为指向节点类型的指针。想要创建一个链表，必须先创建一个头结点：
LinkListCreatHead()
{
LinkList head;
head =(LinkList)malloc(sizeof(ListNode));
head ->next;
return head;
}
用这个函数就可以来创建一个头节点，也就是一个空的链表，链表如何添加节点呢？
节点的添加操作添加分为两种，一种是在两头添加，一种是在中间添加。要添加一个元素时，我们需要将要添加位置的上一个节点的next指向这个节点，而这个节点的next指向原来上个节点所指向的节点。具体方法如下：
voidAddNode(LinkList head , int data , int i)
{
LinkList p , s;
int j = 0 ;
p = head ;
while(p != NULL&& j<i-1)
{
p= p->next;
j++;
}
if(j != i-1 || p == NULL)
{
printf("输入的数据有误！");
}
else
{
s= (LinkList)malloc(sizeof(ListNode));
s->data= data;
s->next = p ->next;
p->next= s;
}
}
这个函数既可以添加两头，也可以添加中间的节点。
我们在来讲一下删除。
节点的删除操作节点的删除是将上一个节点的next存放下一个节点，这样就可以把两个节点中间的那个节点从链表中删除。具体算法如下：
voidDelNode(LinkList head,int i)
{
LinkList p , s;
int j = 0;
p = head;
while(p->next != NULL &&j<i-1)
{
p= p->next;
j++;
}
if(j != i-1||p->next == NULL)
{
printf("输入的数据有误！");
}
else
{
s= p->next;
p->next= s->next;
free(s)；
}
}
这些算法的实现思路并不难，只要掌握好链表的图示结构，这些算法还是很容易写出的。
下面我在说一下节点的查找。
节点的查找节点的查找一共有两种方式，一种是根据序号来查找，一种是根据值来查找。
根据序号来查找的算法如下：
LinkListSelNodeOne(LinkList head , int i)
{
LinkList p , s;
int j = 0;
p =head;
while(p->next != NULL &&j<i-1)
{
p= p->next;
j++;
}
if(j != i-1||p->next == NULL)
{
returnNULL;
}
else
{
returnp->next;
}
}
还有一种是根据值的方式来查找的，具体算法如下：
LinkListSelNodeTwo(LinkList head,int i)
{
LinkList p = head->next;
while(p->next != NULL &&p->data!=i)
{
p= p->next;
}
if(p->data == i)
{
returnp;
}
else
{
returnNULL;
}
}
以上就是关于单链表的具体实现，关于循环链表就是让最后一个节点的指针域存放头结点的地址，双向链表就是在单链表的基础上再添加一个指针域，用来指向上一个节点。具体实现只是在单链表的基础上进行了一些改动，在这里我就不写了。
