|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
在单链表中，又如何实现“插入”和“删除”操作呢？
# N j- m; ]+ I: G$ `假设我们要在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。* O5 i$ f- Q! I
为插入数据元素x，首先要生成一个数据域为x的结点，然后插入在单链表中，根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。插入后的单链表所示。假设s为指向结点x的指针，则上述指针修改用语句描述即为
1 L" u4 J# H; W7 \9 m* \% }5 `% Us->next=p->next；p->next=s；- K/ F( }0 g/ A: q
反之，在线性表中删除元素b时，为在单链表中实现元素a、b和c之间逻辑关系的变化，仅修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为
8 x8 r9 v! |5 A2 `1 R1 a Zp->next= p->next->next; s* A; R+ t( r! z$ Y# N
可见，在一直链表中元素插入或删除的确切位置的情况下，在单链表中插入或删除一个结点时，仅需修改指针而不需要移动元素。) k0 W2 j# x U& |+ z
Status ListInsert_L(LinkList &L,inti,ElemType e){
7 N! p% Y* S/ Z2 K; P5 F6 O* C& L8 F//在带头结点的单链线性表L中第i个位置之前插入元素e) V- Y; E/ w9 `% V9 N) \* ^
p=L；j=0；
# [2 b" h; Y1 M, M9 {while(p&&j<i-1){p=p->next;++j}//寻找第i-1个结点
+ V3 d0 g6 Q; j K" Rif(!p||j>i-1)return ERROR; //i小于1或者大于表长+1
5 n9 m- U$ v: B2 P$ m. a cs=(LinkList)malloc(sizeof(LNode));//生成新结点3 o$ @ e9 c3 P
s->data=e;s->next=p->next; //插入L中9 D" p* f+ D. [! H
p->next=s;
; e1 u+ D6 g8 Xreturn OK;' M3 N; g4 K' ^3 A
}//ListInsert_L
[0 \8 d3 s u, m7 ivoid ListDelete_L(LinkList &L,inti,ElemType &e){
. Z2 ]) p# I5 k//在带头结点的单链线性表L中，删除第i个元素，并用e返回其值& n( r8 t& z; U
p=L;j=0;: p8 o, o; r4 C& v" S5 w6 b ?
while (p->next&&j<i-1){//寻找第i个结点，并令p指向其前驱+ B1 `% o3 O$ S) r N
p=p->next;++j;! `& a! `) O$ p
}0 N2 a8 a5 w7 w6 i9 r5 F
if(!(p->next||j>i-1)return ERROR;//删除位置不合理
6 m) A+ w1 m( T2 dq=p->next;p->next=q->next; //删除并释放结点4 @: X) K8 s4 F# H& m F. n
e=q->data;free(q);' d- }, v% u0 c1 H2 d
return OK;% q, A0 g) g2 u. G5 v
}//ListDelete_L |
|
/1 
发表于 2016-7-13 15:05
收藏
淘帖
支持！
反对！