【数据结构】2-3-2 单链表的插入删除
数据结构知识点合集
- 知识点
|
|
- 按位序插入带头节点链表
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e；找到第 i-1 个结点，将新结点插入其后 。
|
|
/*在带头节点的单链表L的第i个位置插入元素e*/
bool ListInsert(LinkList &L,int i,ElemType e)
{if(i<1)return false;/*节点p用于指向当前的节点*/LNode *p;int j=0;/*p指向L的头节点*/p=L;/*循环找到链表的第i-1个位置*/while(p!=NULL && j<i-1){p = p->next;j++;}/*i的值不合法*/if(p==NULL)return false;/*为新插入的节点申请空间*/LNode *s = (LNode *)malloc(sizeof(LNode));/*将元素的值赋给新插入的节点*/s->data = e;/*新插入节点的下一个节点指向p节点的下一个节点*/s->next = p->next;/*p节点的下一个节点指向新插入的节点*/p-next = s;return true;
}
- 按位序插入不带头节点链表
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e；找到第 i-1 个结点，将新结点插入其后 。
|
|
/*在不带头节点的单链表L的第i个位置插入元素e*/
bool ListInsert(LinkList &L,int i,ElemType e)
{if(i<1)return false;if(i=1){LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;/*插入节点的下一个节点指向L的第一个节点*/s->next = L;/*L的头节点指向新插入节点*/L = s;return true; }LNode *p;p = L;int j=1;while(p!=NULL && j<i-1){p = p->next;j++;}if(p==NULL)reutn flase;LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true;
}- 指定节点的前插后插
/*在指定节点p的后面插入元素e*/
bool InsertNextNode(LNode *p,ElemType e)
{if(p==NULL)return false;/*为新插入的节点分配存储空间*/LNode *s = (LNode *)malloc(sizeof(LNode));if(s==NULL)return false;/*将节点插入*/s->data = e;s->next = p->next;p->next = s;return true;
}
/*在指定节点p的前面插入元素e*/
bool InsertPriorNode(LNode *p,ElemType e)
{if(p==NULL)return false;LNode *s = (LNode *)malloc(sizeof(LNode));if(s==NULL)return false;/*将节点插入到p节点之后*/s->next = p->next;p->next = s;/*将p节点的数据和插入节点的数据互换*/s->data = p->data;p->data = e;return true;
}
- 按位序删除节点
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值 。
|
|
/*删除链表中第i个位置的节点并返回其元素值*/
bool ListDelete(LinkList &L, int i, ElemType &e)
{if(i<1)return false;/*p指向当前节点*/LNode *p;p=L;int j=0;/*循环找到第i-1个节点*/while(p=!NULL && j<i-1){p=p->next;j++;}/*第i-1个或着第i个节点为空删除失败*/if(p == NULL)return false;if(p->next == NULL)return false;/*删除第i个节点*/LNode *q = p->next;p->next = q->next;e = q->data;free(q);return true;
}
- 指定节点的删除
当前节点的next指针指向下下个节点，将当前节点的数据域与下一个节点的数据域互换，然后删除下一个节点。
/*删除指定节点p*/
bool DeletNode(LNode *p)
{if(p==NULL)return false;/*p的下一个节点赋给q*/LNode *q = p->next;/*将p的数据换成下一个节点的数据*/p->data = p->next->data;/*p的下一个节点指向下下个节点*/p->next = q->next;/*删除p的下个节点*/free(q);return true;
}