EDA365电子论坛网
标题:
单链表的插入和删除
[打印本页]
作者:
hasky
时间:
2016-8-11 14:13
标题:
单链表的插入和删除
在单链表中，又如何实现“插入”和“删除”操作呢？
% P) i& v4 T C+ g$ H- Y
假设我们要在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。
0 H1 p; }" Y% }& e% S2 ?3 [
为插入数据元素x，首先要生成一个数据域为x的结点，然后插入在单链表中，根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。插入后的单链表所示。假设s为指向结点x的指针，则上述指针修改用语句描述即为
% j' T# @7 X$ B4 g& O
s->next=p->next；p->next=s；
. ~% V* T; q5 s9 O9 j
反之，在线性表中删除元素b时，为在单链表中实现元素a、b和c之间逻辑关系的变化，仅修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为
: `# c+ d/ l# g$ ^8 J) E
p->next= p->next->next
" V2 b2 E/ \/ W" q2 `
可见，在一直链表中元素插入或删除的确切位置的情况下，在单链表中插入或删除一个结点时，仅需修改指针而不需要移动元素。
& ?: C6 o4 K& K1 B
Status ListInsert_L(LinkList &L,inti,ElemType e){
* O7 _% L8 u1 U! R! d
//在带头结点的单链线性表L中第i个位置之前插入元素e
3 ?3 S3 w$ V- w
p=L；j=0；
$ m; r# _0 p, P7 Y- f$ j4 g
while(p&&j<i-1){p=p->next;++j}//寻找第i-1个结点
" s T8 ?. z; l, l
if(!p||j>i-1)return ERROR; //i小于1或者大于表长+1
& j: N- f# r7 e# } Y
s=(LinkList)malloc(sizeof(LNode));//生成新结点
. R, n0 r2 K" {0 R
s->data=e;s->next=p->next; //插入L中
5 l7 O) `5 b, }% f2 O: h
p->next=s;
3 [9 v4 K6 d: E
return OK;
0 T. I; j6 {( I
}//ListInsert_L
8 \4 m/ E, {* J
void ListDelete_L(LinkList &L,inti,ElemType &e){
) H+ z- S h& B+ k* f( }2 x+ M
//在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
! T: h: P7 h& l3 Y3 J
p=L;j=0;
3 n) i. }* `- J; U5 ], ]" q2 M
while (p->next&&j<i-1){//寻找第i个结点，并令p指向其前驱
4 T5 R* C' l3 c
p=p->next;++j;
6 D) S/ t% K; [: ]
}
9 X9 ~4 Z( I) r3 \+ h' j. `
if(!(p->next||j>i-1)return ERROR;//删除位置不合理
9 y" B1 Q/ y- ?8 f
q=p->next;p->next=q->next; //删除并释放结点
# T% `0 E& j3 q
e=q->data;free(q);
9 _1 s$ w( a/ n* B
return OK;
% }. F1 V% v. p
}//ListDelete_L
作者:
Pang8343569
时间:
2016-8-11 14:38
谢谢O(∩_∩)O哈哈~谢谢O(∩_∩)O哈哈
' c+ b9 i0 J: Z7 M
作者:
duzy
时间:
2016-8-11 14:54
支持楼主！谢谢分享！
) g- u; c0 B6 i" t4 D# L$ _
作者:
Pang8343569
时间:
2016-8-12 11:42
支持楼主！谢谢分享！
- l% f, G( D' l$ K/ F
作者:
yhg-lee
时间:
2016-8-13 10:45
支持楼主！谢谢分享！
- f/ @2 W( J) ]; \1 b
作者:
wu68aq
时间:
2016-8-15 15:57
支持一下，很不错哦！
5 e3 I2 d0 @4 E$ [4 P3 j
作者:
Dedy01
时间:
2016-8-16 13:53
学习了!3Q
$ X* o6 P3 Q' ?- ~6 i
作者:
Gegu
时间:
2016-8-17 14:03
谢谢分享,必须赞一个～
d; P/ U% t2 I% d) Z5 B2 U
作者:
Titianyeer
时间:
2016-8-19 14:28
' P5 @3 y; r1 I! G
学习了!3Q
欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/)
Powered by Discuz! X3.2