单链表及其操作（C实现）

当每一个数据结点都和下一个数据结点用指针链接在一起时，就形成了一个链，这个链子的头就位于第一个数据元素，这样的存储方式就是链式存储。

1. 链表的构成

每个结点的结构，以及单链表的构成，如下：

typedef struct Link
{
　　char elem; // 数据域
　　struct Link * next;  // 指针域
} link;

2. 头结点、头指针和首元结点

• 头结点
  在链表的第一个结点之前额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。
• 头指针
  永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。
• 首元结点
  链表中第一个元素所在的结点，它是头结点后边的第一个结点。

若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。
单链表中可以没有头结点，但是不能没有头指针！

3. 单链表的创建

例如，创建一个链表（1，2，3，4）:

link * initLink()
{
　　link * p = (link*)malloc(sizeof(link));  // 创建头结点
　　link * temp = p;  // 声明一个指针指向头结点，用于遍历链表
　　
　　//生成链表
　　for (int i=1; i<5; i++) 
　　{
　　　　link *a = (link*)malloc(sizeof(link));
　　　　a->elem = i;
　　　　a->next = NULL;
　　　　temp->next = a;
　　　　temp = temp->next;
　　}
　　return p;
}

4. 单链表的遍历

查找某结点：

int selectElem(link * p, int elem)
{
　　link *t = p;
　　int i = 1;
　　while (t->next) 
　　{
　　　　t = t->next;
　　　　if (t->elem == elem) 
　　　　{
　　　　　　return i;
　　　　}
　　　　i++;
　　}
　　return -1;
}

修改某结点数据域：

link *amendElem(link * p, int add, int newElem)
{
　　link * temp = p;
　　temp = temp->next;　　//在遍历之前，temp指向首元结点
　　//遍历到被删除结点
　　for (int i=1; i<add; i++) 
　　{
　　　　temp = temp->next;
　　}
　　temp->elem = newElem;
　　return p;
}</pre>

向链表中插入结点：

// 创建临时指针，断链续接
link * insertElem(link * p, int elem, int add)
{
　　link * temp = p;　　//创建临时结点temp
　　//首先找到要插入位置的上一个结点
　　for (int i=1; i<add; i++) 
　　{
　　　　if (temp == NULL)
　　   {
　　　　　　printf("插入位置无效\n");
　　　　　　return p;
　　　　}
　　　　temp = temp->next;
　　}
　　//创建插入结点c
　　link *c = (link*)malloc(sizeof(link));
　　c->elem = elem;
　　//向链表中插入结点
　　c->next = temp->next;
　　temp->next = c;
　　return p;
}</pre>

从链表中删除节点：

// 把结点摘下来，续接，再释放掉
link * delElem(link * p,int add)
{
　　link * temp = p;
　　//temp指向被删除结点的上一个结点
　　for (int i=1; i<add; i++) 
　　{
　　　　temp = temp->next;
　　}
　　link * del = temp->next;//单独设置一个指针指向被删除结点，以防丢失
　　temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
　　free(del);//手动释放该结点，防止内存泄漏
　　return p;
}