|
|
|
单链表中的每个节点由两部分组成：数据域和指针域。节点形式如下：
|
|
|
|
|
|
其中，data部分称为数据域，用于存储线性表的一个数据元素（节点）。next部分称为指针域或链域，用于存放一个指针，该指针指向本节点所含数据域元素的直接后继所在的节点。若数据元素的类型用ElemType表示，则单链表的类型定义如下：
|
|
|
|
|
|
单链表分为带头节点（其next域指向第一个节点）和不带头节点两种类型，由于头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致，因而可简化运算的实现过程。
|
|
|
|
|
|
1）初始化函数initlist（Slink *head）
|
|
|
|
初始化函数用于创建一个头节点，由head指向它，该节点的next域为空，data域未设定任何值。由于调用该函数时，指针head在本函数中指向的内容发生改变，为了返回改变的值，因此使用了应用型参数，其时间复杂度为O（1）。初始化函数的语法如下：
|
|
|
|
|
|
2）插入函数insert（Slink *head, int i, ElemType x）
|
|
|
|
插入函数的设计思想是：创建一个data域值为x的新节点*p，然后插入到head所指向的单链表的第i个节点之前。为保证插入正确有效，必须查找到指向第i个节点的前一个节点的指针，主要的时间耗费在查找上，因而在长度为n的线性单链表进行插入操作的时间复杂度为O（n）。插入函数的语法如下：
|
|
|
|
|
|
3）删除函数delete（Slink *head, int i, ElemType x）
|
|
|
|
删除函数的设计思想是：线性链表中元素的删除要修改被删除元素前驱的指针，回收被删除元素所占的空间。主要的时间耗费在查找上，因而在长度为n线性单链表进行删除操作的时间复杂度为O（n）。删除函数的语法如下：
|
|
|
|
|
|
4）查找函数get（Slink *head, int i）
|
|
|
|
查找函数的设计思想是：线性链表中查找元素要找元素前驱的指针。在长度为n的线性单链表进行查找操作的时间复杂度为O（n）。查找函数的语法如下：
|
|
|
|
|
|
5）求单链表长函数Length（Slink *head）
|
|
|
|
求单链表长函数的设计思想是：通过遍历的方法，从头数到尾，即可得到单链表长。求单链表长函数的语法如下：
|
|
|
|
|
