? ? ? ? 在学习数据结构的过程中，首先接触到的就是线性表，线性表中的单链表，博主在一开始的时候真的是一头雾水，首先是对于指针的了解甚浅，其次是觉得这玩意太抽象了。但是后来重新看了之后发现，这玩意儿，也就这样吧！
? ? ? ? 下面，以单链表为例，展开单链表的一些基础操作。
一、首先写出单链表的抽象数据类型：
ADT 单链表ADT
ADT List{
数据：
零个或多个数据元素构成的线性序列（,
, …，
）。数据元素之间的关系是一对一关系。
运算：
Init(L)：初始化运算。构造一个空的线性表L，若初始化成功，则返回OK；否则返回ERROR。
Destroy(L)：撤销运算。判断线性表L是否存在，若已存在，则撤销线性表L；否则返回ERROR。
Find(L, i)：查找运算。若线性表L已存在且，则查找并返回单链表L中元素
?的值；否则返回ERROR。
Insert(L, i, x)：插入运算。若线性表L已存在且，则在元素
之后插入新元素x；当i=-1时，新元素插在头部位置。插入成功后返回OK，否则返回ERROR。
Delete(L, i)：删除运算。若线性表L非空且，则删除元素
，删除成功后返回OK，否则返回ERROR。
Output(L)：输出运算。若单链表L已存在，则输出线性表L中所有数据元素，否则返回ERROR。
}
?可能这样看来，也有这么一丝抽象。
二、我们一条函数一条函数的看看吧：
1.Init(L)：初始化运算。构造一个空的线性表L，若初始化成功，则返回OK；否则返回ERROR。
int Init(singleList* L) //单链表的初始化：建立一个空的单链表
{
L->first = NULL; //头指针不指向任何值
L->n = 0; //此时单链表的长度为0
return OK;
}2. Destroy(L)：撤销运算。判断线性表L是否存在，若已存在，则撤销线性表L；否则返回ERROR。
void Destroy(singleList* L) //单链表的撤销
{
Node* p; //定义一个指向单链表中任意结点的指针变量
while (L->first)
{
p = L->first->link; //保存头指针后继结点地址，防止“断链”
free(L->first); //释放first所指结点的存储空间
L->first = p; //把p所指向结点赋为头指针
}
}3. Find(L, i)：查找运算。若线性表L已存在且，则查找并返回单链表L中元素
?的值；否则返回ERROR。
int Find(singleList* L, int i, ElemType* x) //单链表的查找，i表示下标，*x表示返回的数值
{
Node* p; //定义一个指向单链表中任意一个结点的指针变量
int j;
if (i<0 || i>L->n - 1) //判断是否越界：如果下标i小于0或者超过单链表的长度，返回ERROR
return ERROR;
p = L->first; //指针p指向头指针
for (j = 0; j < i; j++)
p = p->link; //从头结点开始查找下标为i的结点a(i)
*x = p->element; //通过*x返回下标为i的结点a(i)的数值
return OK;
}4.?Insert(L, i, x)：插入运算。若线性表L已存在且，则在元素
之后插入新元素x；当i=-1时，新元素插在头部位置。插入成功后返回OK，否则返回ERROR。
//单链表的插入，i表示插入结点a(i)之后，x表示待插入结点的数值
int Insert(singleList* L, int i, ElemType x)
{
Node* p, * q; //分别定义两个指向单链表中任意结点的指针变量
int j;
if (i<-1 || i>L->n - 1) //判断是否越界，这里i可以=-1的是新结点将插入单链表的头结点之前
return ERROR;
p = L->first; //将p指针指向头指针
for (j = 0; j < i; j++)
p = p->link; //从头结点开始查找a(i)
q = (Node*)malloc(sizeof(Node)); //动态生成新结点q
q->element = x; //q结点的数据域赋值为x
if (i > -1) //新结点插入p所指结点之后
{
q->link = p->link;
p->link = q;
}
else //新结点插入头结点之前，成为新的头结点
{
q->link = L->first;
L->first = q;
}
L->n++; //链表长度加1
return OK;
}5. Delete(L, i)：删除运算。若线性表L非空且，则删除元素
，删除成功后返回OK，否则返回ERROR。
int Delete(singleList* L,int i) //单链表的删除，i表示待删除结点的下标
{
int j;
Node* p, * q; //分别定义两个指向单链表中任意结点的指针变量
if (!L->n) //判断链表是否为空
return ERROR;
if (i<0 || i>L->n - 1) //判断是否越界
return ERROR;
q = L->first; //p指针指向头指针
p = L->first; //q指针指向头指针
for (j = 0; j < i-1; j++)
q = q->link; //q指针从头指针开始一直访问到待删除结点a[i]的前驱结点a[i-1]
if (i == 0) //删除头结点
L->first = L->first->link;
else //删除下标为i的结点
{
p = q->link; //p指向a[i]结点
q->link = p->link; //从单链表中删除a[i]结点
}
free(p); //释放p所指向结点的存储空间
L->n--; //单链表长度减1
return OK;
}6. Output(L)：输出运算。若单链表L已存在，则输出线性表L中所有数据元素，否则返回ERROR。
int Output(singleList* L) //单链表的输出
{
Node* p; //定义指向单链表中任意结点的指针变量
if (!L->n) //判断链表是否为空
return ERROR;
p = L->first; //p指针指向头指针
while (p)
{
printf("%4d", p->element); //输出数值
p = p->link; //p指针指向下一个结点
}
return OK;
}三、整合后完整的代码如下：
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct node {
ElemType element;
struct node* link;
}Node;
typedef struct singleList {
Node* first;
int n;
}singleList;
int Init(singleList* L)
{
L->first = NULL;
L->n = 0;
return OK;
}
int Insert(singleList* L, int i, ElemType x)
{
Node* p, * q;
int j;
if (i<-1 || i>L->n - 1)
return ERROR;
p = L->first;
for (j = 0; j < i; j++)
p = p->link;
q = (Node*)malloc(sizeof(Node));
q->element = x;
if (i > -1)
{
q->link = p->link;
p->link = q;
}
else
{
q->link = L->first;
L->first = q;
}
L->n++;
return OK;
}
int Output(singleList* L)
{
Node* p;
if (!L->n)
return ERROR;
p = L->first;
while (p)
{
printf("%4d", p->element);
p = p->link;
}
return OK;
}
int Delete(singleList* L,int i)
{
int j;
Node* p, * q;
if (!L->n)
return ERROR;
if (i<0 || i>L->n - 1)
return ERROR;
q = L->first;
p = L->first;
for (j = 0; j < i-1; j++)
q = q->link;
if (i == 0)
L->first = L->first->link;
else
{
p = q->link;
q->link = p->link;
}
free(p);
L->n--;
return OK;
}
int Find(singleList* L, int i, ElemType* x)
{
Node* p;
int j;
if (i<0 || i>L->n - 1)
return ERROR;
p = L->first;
for (j = 0; j < i; j++)
p = p->link;
*x = p->element;
return OK;
}
void Destroy(singleList* L)
{
Node* p;
while (L->first)
{
p = L->first->link;
free(L->first);
L->first = p;
}
}
void main()
{
int i, x;
singleList list;
Init(&list);
for (i = 0; i < 9; i++)
Insert(&list, i - 1, i);
printf("the list is:");
Output(&list);
Delete(&list, 0);
printf("\n删除0后的链表为：");
Output(&list);
Find(&list, 2, &x);
printf("\n下标为2的数值为：%d", x);
Destroy(&list);
}
结果如下：
?以上就是单链表的基础操作。