12.15 单链表（2）
取值、查找、插入、删除......
取值——取单链表中第i个元素的内容
链表不是随机存取结构
Status GetElem_L(LinkList L, int i, ElemType &e) {
// 通变量e带回
p = L->next;
j = 1;
while(p && j < i) {
p = p->next;
++j;
}
if(!p || j > i)
return ERROR;
e = p->data;
return OK;
} 查找——按值查找，根据指定数据获取该数据所在的位置（地址）
p指到首元结点：p = L->next;
计数器加1
指针从上一个移动到下一个：p = p->next;
找到后（p->data == e），返回计数器的值
找到底也没找到，为空了。查找就可以结束了
步骤：
（1）比较；（2）若；（3）若
Lnode *LocateElem_L (LinkList L, Elemtype e) {
p = L->next;
while(p && p->data != e)
p = p->next;
return p;
} 返回序号int LocateElem_L(LinkList L, Elemtype e) {
p = L->next;
j = 1;
while(p && p->data != e){
p = p->next;
j++;
}
if(p)
return j;
else
return 0;
} 插入——在第i个结点前插入值为e的新结点
如：i = 3
第二个结点的后继结点不再是原来位置的第三个结点了
关键：找 i - 1 这个结点，插入结点
算法步骤：（1）首先找到ai-1的存储位置p；（2）生成一个数据域为e的新结点s；（3）插入新结点：1）新结点的指针域指向结点ai；2）结点ai-1的指针域指向新结点
（s->next = p->next）(p->next = s)
Status ListInsert_L(LinkList &L, int i, ElemType e) {
p = L;
j = 0;
while(p && j < i - 1) {
p = p->next;
++j;
}
if (!p || j > i - 1)
return ERROR;
s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
删除——删除第i个结点
算法步骤：（1）找第 i - 1 结点；（2）令 p->next 指向ai+1；（p->next = p->next->next）（3）释放掉结点ai的空间；
Status ListDelete_L(LinkList &L, int i, ElemType &e) {
p = L;
j = 0;
// 还有个q(算法写的比较省略)
while(p->next && j < i - 1) {
p = p->next;
++j;
} // 寻找第i个结点，并令p指向其前驱
if (!(p->next) || j > i - 1)
return ERROR;
q = p->next;
p->next = q->next;
e = q->data;
delete q;
return OK;
} 时间效率
查找：
插入和删除：
投递鹏芯微等公司10个岗位 >
