2.线性表习题答案.doc

1、基于单链表写出向线性表的末尾添加一个元素的算法。Status Insert(LinkList L,ElemType e) LinkList p,q; q=L; p=(LinkList)malloc(sizeof(LNode);/为元素开辟空间 if(p=null) return error; p-data=e； while(q-next) q=q-next;/使p指向最后一个节点 p-next=q-next;/插入p节点 q-next=p; return ok；2、若L为有序表，基于单链表写出算法，使得向L中插入一个元素e后依然有序。Status InsertInOrder_L(LinkList &L,ElemType e) LinkList p,q,s; q=L; p=L-next s=(LinkList)malloc(sizeof(LNode);/为元素开辟空间if(s=null) return error; s-data=e；while( p != NULL ) if( s-value = p-value ) / 找到了s该插入的位置,并且此时p,q已记录下要插入的位置 break else q = p; p = p-next;/ 将s节点插入到q,p节点之间s-next = p;q-next = s;return ok；3、基于单链表写出删除线性表尾元素的算法。Status DeleteRear_L(LinkList &L,ElemType &e) LinkList p,q, P=L; Q=L-next; While(q-next!=null) p=q;Q=q-next;p-next=null;free(q);return ok；4. 基于单链表写出算法，删除等于给定值的第一个元素。Status Delete_L(LinkList &L,ElemType e) linklist p,q; If(L=null) return error Else P=L; Q=L-next; While (q!=null) If(q-data=e) break;/找到节点，提前停止循环 Else p=q; Q=q-next; If(q=null) returnP-next=null;Free(q);return ok； 5. 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表Status converse_sq(sqlist &L) for(i=0;inext; L-next=NULL; while(p!=NULL) q=p; p=p-next; q-next=head-next; L-next=q; Return ok;7. 假设p指向循环链表L中某一结点（简称p结点），试写出删除p结点的直接前驱（假设存在）的算法。Status Delete_L(LinkList &L) linklist s, q;s=p;while(s-next-next!=p)s=s-next;q=s-next;s-next=p;free(q);return ok;8. 建立带表头节点的链表L ，满足用户从键盘正序位输入数据元素Status creatlist_L(LinkList & L) elemtype k; Linklist p,q;L=(linklist)malloc(sizeof(LNode);If (!L)return error;L-next=Null;Q=l; scanf(k)While(k!=-1)P=(linklist)malloc(sizeof(LNode);If