西安电子科技大学计算机学院数据结构课件 第2章（2）.pptVIP

单链表的存储映象 头结点 在链表的第一个结点之前附设一个结点，头指针指向头结点。设置头结点的目的是统一空表与非空表的操作，简化链表操作的实现。 首元结点 链表中存储线性表中第一个数据元素的结点。 取表元素Status GetElem_L(LinkList L, int i, ElemType e) { p = L-next; j = 1; while( p j i){ p = p-next; ++j; } if (!p || ji) return ERROR; e = p-data; return OK; } 插入Status ListInsert_L(LinkList L, int i, ElemType e) { p = L; j = 0; while (p j i-1) { p = p-next; ++j } if (!p || ji-1) return ERROR; s = (LinkList) malloc( sizeof (LNode) ); s-data = e; s-next = p-next; ① p-next = s; ② return OK; } 删除单链表的第i个结点的过程 删除Status ListDelete_L(LinkList L, int i, ElemType e) { p = L; j = 0; while (p-next j i-1) { p = p-next; ++j } if (!(p-next) || ji-1) return ERROR; r = p-next; e = r-data; p-next = p-next-next; //(p-next = r-next;) ① free(r); return OK; } 动态建立单链表的过程 头插法建表CreateList_L(LinkList L, int n) { L = (LinkList) malloc( sizeof (LNode) ); L-next = NULL; for( i=n; i0; --i){ s = (LinkList) malloc( sizeof (LNode) ); scanf( s-data); s-next = L-next; ① L-next = s; ② } } 尾插法建表CreateList_L(LinkList L, int n) { tail = L = (LinkList) malloc( sizeof (LNode) ); L-next = NULL; for( i=n; i0; --i){ s = (LinkList) malloc( sizeof (LNode) ); scanf( s-data); s-next = NULL; tail-next = s; ① tail = s; ② } } 归并void MergeList_L(LinkList La, LinkList Lb, LinkList Lc) { pa = La-next; pb = Lb-next; Lc = pc = La; while( pa pb ){ if(pa-data = pb-data){ pc-next = pa; pc = pa; pa = pa-next; } else{ pc-next = pb; pc = pb; pb= pb-next; } } pc-next = pa ? pa : pb; free( Lb ); } 练习：已知L是带头结点的非空单链表，指针p所指的结点既不是第一个结点，也不是最后一个结点 删除*p结点的直接后继结点的语句序列 q = p-next; p-next = q-next; free(q); 删除*p结点的直接前驱结点的语句序列 q = L; while(q-next-next != p) q = q-next; s =