数据结构之线性表(五)——单链表(3取值，按值查找，插入结点，删除结点)

知识准备 带头结点的单链表示意图如下，

类型定义： typedef struct Lnode { ElemType data; //数据域 struct Lnode* next; //指针域 }Lnode, *LinkList; 变量定义： LinkList L; LNode *p,*s; 关键性操作： p = L; //p指向头结点 s = L->next; //s指向首元结点 p = p->next; //p指向下一个结点

1.取值

取值：取单链表中第i个元素的内容 回顾顺序表中元素取值的方法——随机存取，即顺序表中取第i个元素为L->elem[i-1]。 而在链表中，元素是顺序存取的，所以其算法思路如下，

算法思路： 从首元结点开始，依次向下寻找，用变量j来计数，直到找到第i个元素为止，即，$j=i$。 依次往下，直到$j=i$，表示已经找到第i个元素的值了，返回p->data

算法步骤：

1.从第1个结点(L->next)顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next。2.j做计数器，累计当前扫描过的结点数，j的初值为1。3.当p指向扫描到的下一结点时，计数器加1。4.当$j==i$，p所指的结点就是要找的第i个结点。

算法描述：

Status GetElem_L(LinkList L, int i, ElemType& e)//获取线性表L中的耨个数据元素的内容，通过变量e返回 { p = L->next; //初始化，p指向首元结点， j = 1; //初始化，j为计数器 while (p&&j < i) //向后扫描，直到p指向的第i个元素或p为空 { p = p->next; //p指向下一个结点 ++j; } if (!p || j > i) //第i个元素不存在，抛出异常 return ERROR; e = p->data; //取第i个元素 return OK; }

2.按值查找(两种)

根据返回值不同，按值查找分为两种： 1.返回指定元素的地址(返回的是地址) 2.返回指定元素的位置序号(返回的是位置序号)

算法思路： 从首元结点开始，依次向下寻找，用变量i来计数，当指针p指向的数据域等于指定值e时，返回结点地址(就是指针p)，或者当前结点的位序i。

算法步骤：

1.从第1个结点(L->next)顺链扫描，依次让结点的数据域的值与e相比较。2.如果找到一个值与e相等的数据元素，则返回其在链表中的位置或地址。3.如果查遍整个链表都没有找到其值与e相等的元素，则返回0或NULL。

算法描述： 1.返回地址的算法

Lnode* LocateElem_L(LinkList L, ElemType e) { p = L->next; //指向首元结点的指针p while (p&&p->data != e) { p = p->next; //指向下一个结点 } return p; //返回当前结点的地址 }

        2.返回位置的算法

int LocateElem_L(LinkList L, ElemType e) { p = L->next; //指向首元结点的指针p j = 1; while (p&&p->data != e) { p = p->next; //指向下一个结点 j++; } if (p) return j; //返回元素的位置序号 else return 0; }

3.插入结点

插入结点： 在第i个结点前插入值为e的新结点。 如上图，将第$i-1$个元素$a_{i-1}$的指针域指向要插入的元素e，并且要给新结点的指针域赋下一结点(原表中第i个元素$a_i$)的地址。

算法步骤： 1.找到$a_{i-1}$的存储位置p。 2.生成一个数据域为e的新结点s。3.插入新结点，分为两步： 将新结点的指针域指向结点$a_i$。那么就是将结点$a_i$的地址赋值给新结点s的next域，即s->next=p->next。结点$a_{i-1}$的指针域指向新结点。那么就是将p指针的next域赋新结点的地址，即p->next=s。

那么可不可以把上面插入步骤的第一步和第二步互换？         思路上可以，但不能直接互换，因为直接互换会使$a_i$的地址丢失

算法描述： Status ListInsert_L(LinkList& L, int i, ElemType e) { p = L; j = 0; while (p&&j < i - 1) //寻找第i-1个结点，p指向第i-1个结点 { p = p->next; ++j; } if (!p || j > i - 1) //i大于表长+1或者小于1，插入位置非法 return ERROR; s = new LNode; //生成新的结点s s->data = e; //将新结点s的数据域置为e s->next = p->next; //将第i个结点的地址赋到新结点e的指针域中 p->next = s; //将新结点e的地址赋到第i-1个结点的指针域中 return OK; }

4.删除结点

删除结点： 删除第i个结点。 如上图，将第$i-1$个元素$a_{i-1}$的指针域指向第i+1个元素$a_{i+1}$，并把要删除的第i个元素的值保存下来。

算法步骤：

1.找到$a_{i-1}$的存储位置p，保留要删除的$a_i$的值。 2.令p->next指向$a_{i+1}$。这里的$a_{i+1}$元素的地址为p->next->next。3.释放结点$a_i$的空间，这里需要一个额外的指针变量q，其指向的是结点$a_i$，即q=p->next。

算法描述：

Status ListDelete_L(LinkList& L, int i, ElemType& e) { p = L; j = 0; while (p->next&&j < i - 1) //寻找第i-1个结点，p指向第i-1个结点 { p = p->next; ++j; } if (!(p->next) || j > i - 1) //i大于表长+1或者小于1，插入位置非法 return ERROR; q = p->next; //q指向第i个结点 (删除结点) p->next = q->next; //改变删除结点的前驱结点的指针域 e = q->data; //保存删除结点的指针域 delete q; //释放删除结点的空间 return OK; }

单链表查找、插入、删除算法的复杂度分析

1.查找： 因为单链表只能顺序存取，即在查找时要从头指针开始找起，查找的时间复杂度为$O(n)$。2.插入和删除： 因单链表不需要移动元素，只要修改指针，一般情况下时间复杂度为$O(1)$。但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为$O(n)$。