2.3.2 单链表上的基本运算

单链表上的基本运算包括链表的建立、单链表的插入、单链表的删除、单链表的长度等。带头结点的单链表的运算具体实现如下（以下算法实现文件保存在“LinkList.h”中）。

（1）单链表的初始化操作。

（2）判断单链表是否为空。

（3）按序号查找操作。链表是一种随机存取结构，只能从头指针开始存取元素。因此，要查找单链表中的第i个元素，需要从单链表的头指针h出发，利用结点的next域依次访问链表的结点，并进行比较操作。利用计数器从0开始计数，当计数器为i时，就找到了第i个结点。

（4）按内容查找操作。

（5）定位操作。定位操作是指按内容查找并返回结点的序号的操作。从单链表的头指针出发，依次访问每个结点，并将结点的值与e比较，如果相等，返回该序号表示成功；如果没有值与e相等的元素，返回0表示失败。

（6）插入操作。插入操作就是将元素e插入到链表中指定的位置i，插入成功返回1，否则返回0。

在单链表的第i个位置插入一个新元素e可分为3步进行：

①在链表中找到其直接前驱结点，即第i-1个结点，并由指针pre指向该结点，如图2.13所示。

②动态申请一个新的结点，并由p指向该结点，将值e赋值给p指向结点的数据域，如图2.14所示。

③修改pre和p指向结点的指针域，如图2.15所示。这样就完成了在第i个位置插入结点的操作。

在单链表中插入新结点分为两个步骤：①将新结点的指针域指向第i个结点，即p->next=pre->next；②将直接前驱结点的指针域指向新结点，即pre->next=p。

注意：插入结点的操作步骤不能反过来，即先执行pre->next=p操作，后执行p->next=pre->next操作是错误的。

（7）删除操作。删除操作就是将单链表中的第i个结点删除，其他结点仍然构成一个单链表。删除成功返回1，否则返回0。

删除单链表中的第i个结点分为以下3个步骤：

①找到第i个结点的直接前驱结点，即第i-1个结点，并将指针pre指向该结点，指针p指向第i个结点，如图2.16所示。

②修改pre和p指向结点的指针域，使p指向的结点与原链表断开，即pre->next=p->next。

③动态释放指针p指向的结点。如图2.17所示。

注意：在寻找第i-1个结点（被删除结点的前驱结点）时，要保证被删除结点存在，即pre->next->next!=NULL。如果没有该判断条件，且要删除的结点在链表中不存在，就会执行循环后出现p指向NULL指针域，从而造成错误。

（8）求表长。

（9）销毁链表。