|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
在单链表中，又如何实现“插入”和“删除”操作呢？
! o3 N2 S8 T% U2 J' O. E( c' f假设我们要在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。; T' O! q d" j
为插入数据元素x，首先要生成一个数据域为x的结点，然后插入在单链表中，根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。插入后的单链表所示。假设s为指向结点x的指针，则上述指针修改用语句描述即为
2 |( @* b* X/ [7 P5 g7 hs->next=p->next；p->next=s；
, `! h+ f7 w. D8 b0 w( r反之，在线性表中删除元素b时，为在单链表中实现元素a、b和c之间逻辑关系的变化，仅修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为) V* w" r1 t) g& T( M
p->next= p->next->next
) h, j) \, I: T7 g3 }7 r1 a e- O3 D可见，在一直链表中元素插入或删除的确切位置的情况下，在单链表中插入或删除一个结点时，仅需修改指针而不需要移动元素。
3 N: |1 Z; N) P- JStatus ListInsert_L(LinkList &L,inti,ElemType e){' I2 |. b5 W/ H! c
//在带头结点的单链线性表L中第i个位置之前插入元素e
: ]# E# H( Y9 g8 Gp=L；j=0；
6 e: k3 D0 d6 D9 [' f6 V5 Xwhile(p&&j<i-1){p=p->next;++j}//寻找第i-1个结点
. ?5 c, j- I2 w( j; A8 jif(!p||j>i-1)return ERROR; //i小于1或者大于表长+1
5 {8 Z1 p, t3 |s=(LinkList)malloc(sizeof(LNode));//生成新结点8 Z6 s3 t" l. e9 g
s->data=e;s->next=p->next; //插入L中. r! _3 k- x0 V3 t
p->next=s;
8 B* g$ S! z$ xreturn OK;
' K9 h0 c# W# e" P# j}//ListInsert_L2 I: {+ z& j4 c& P4 n* g/ E
void ListDelete_L(LinkList &L,inti,ElemType &e){
2 l% u# }9 ?4 k& R. H//在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
) f! S1 e7 v7 up=L;j=0;
1 X0 d% k$ ^2 n, T% I9 \, K& Lwhile (p->next&&j<i-1){//寻找第i个结点，并令p指向其前驱, C# N/ q1 i( a; b
p=p->next;++j;* P: [* E' g3 d+ N$ m* e8 l
}
# g2 o! p* L0 n* R+ g9 G5 zif(!(p->next||j>i-1)return ERROR;//删除位置不合理' W5 n' t- p( ~1 Z6 l" i# ~- J
q=p->next;p->next=q->next; //删除并释放结点
! I+ c& G: ]* |, |e=q->data;free(q);0 s4 M7 W* o. N8 w1 v
return OK;( x+ l. P) W3 n9 s% J" J# v; y* F9 M* a# W
}//ListDelete_L |
|
/1 
发表于 2016-7-13 15:05
收藏
淘帖
支持！
反对！