-数据结构-线性表.PPT

线性表应用——多项式的表示及运算 (7) 按元素值查找LocateElem(L,e) 思路：在单链表L中从头开始找第1个值域与e相等的 结点，若存在则返回逻辑序号，否则返回0。 int LocateElem(LinkList *L,ElemType e){ LinkList *p=L-next; int i=1; while (p!=NULL p-data!=e){ p=p-next; i++; } if (p==NULL) return 0; else return i; } (8) 插入数据元素ListInsert(L,i,e) 思路：先在单链表L中寻找到第i-1个结点*p，若存在，将值为e的结点*s插入到其后。 bool ListInsert(LinkList *L,int i,ElemType e){ int j=0; LinkList *p=L,*s; while (ji-1 p!=NULL){ //查找第i-1个结点 j++; p=p-next; } if (p==NULL) return false; //未找到 else{ s=(LinkList *)malloc(sizeof(LinkList)); s-data=e; s-next=p-next; //将*s插入到*p之后 p-next=s; return true; } } (9) 删除数据元素ListDelete(L,i,e) 思路：先在单链表L中寻找到第i-1个结点*p，若结点存在，且也存在后继结点*q，则删除该后继结点。 bool ListDelete(LinkList *L,int i,ElemType e){ int j=0; LinkList *p=L,*q; while (ji-1 p!=NULL){ //查找第i-1个结点 j++; p=p-next; } if (p==NULL) return false; //未找到 else{ q=p-next; //q指向要删除的结点 if (q==NULL) false; //不存在后继结点 e=q-data; p-next=q-next; //从单链表中删除*q结点 free(q); //释放*q结点 return true; } } 【例2.5】假设有一个带头结点的单链表 L={ a1 , b1 , a2 , b2 , … , an , bn } 设计一个算法将其拆分成两个带头结点的单链表L1和L2，其中L1={ a1 , a2 , … , an }，L2={ bn , bn-1 , … , b1 }。要求L1使用L的头结点。 L1 ∧ p … L2 头插法建表 尾插法建表 void split(LinkList *L,LinkList *L1,LinkList *L2) 【例2.6】设计一个算法，删除一个单链表L中元素值最大的节点。 L ∧ … … maxp maxpre L 5 3 8 ∧ 6 void delmaxnode(LinkList *L){ LinkList *p=L-next,*pre=L,*maxp=p,*maxpre=pre; while (p!=NULL) { //pre始终指向p的前驱节点 if (maxp-datap-data){ //找到一个更大的节点 maxp=p; //更改maxp maxpre=pre; //更改maxpre } pre=p; //p、pre同步后移一个节点 p=p-next; } maxpre-next=maxp-next; //删除*maxp节点 free(ma