2.3.2单链表基本操作(不带头节点)
程序员文章站
2024-03-21 14:49:34
...
注意:以下是不带头节点操作
// 插入(按位序插入)(在前驱节点后插入)
bool ListInsert(LinkList &L, int i, ElemType e) {
LNode *s, *p;
int j = 1;
if (i < 1)
return false;
if (L == NULL)
return false;
if (i == 1) { // 因为首节点无前驱(即头节点),所以需要特殊处理
s = (LNode *) malloc(sizeof(LNode));
s->next = L->next;
L = s;
return true;
}
p = L; // p指针指向首节点
while (p != NULL && j < i - 1) { // 寻找待插入节点的前驱
p = p->next;
j++;
}
if (p == NULL)
return false;
s = (LNode *) malloc(sizeof(LNode));
if (s == NULL)
return false; // 申请空间失败
s->next = p->next;
s->data = e;
p->next = s;
return true;
}
// 删除(按位序删除)
bool ListDel(LinkList &L, int i, ElemType &e) {
LNode *p, *q;
int j = 1;
if (i < 1)
return false; // 删除位置不合法
if (L == NULL) // 表为空表
return false;
if (i == 1) { // 因为首节点无前驱(即头节点),所以需要特殊处理
e = L->data;
q = L->next;
L = q;
return true;
}
p = L; // p指针指向首节点
while (p != NULL && j < i - 1) { // 寻找待删除节点的前驱
p = p->next;
j++;
}
// p == NULL || p->next == NULL 顺序不能颠倒
// 删除位置分别考虑>=length+1,=length
if (p == NULL || p->next == NULL)
return false;
q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}
上一篇: 生成子集(Java)