线性结构复习.doc

线性结构复习 设计一个算法从顺序表L中删除所有值为x的元素。要求算法的空间复杂度为O（1） void delall(SqList L) { int i=0,j; while(iL.lengthL.elem[i]!=x) i++; //确定表L中第一个值为x的元素的位置 for(j=i+1;jL.length;j++) if(L.elem[j]!=x) { L.elem[i]=L.elem[j]; i++; } L.length=i; } 设计一个算法从一给定的有序顺序表L中删除元素值在x到y（x=y）之间的所有元素，要求以较高的效率来实现。要求算法的空间复杂度为O(1) void delete(SqList L,ElemType x,ElemType y) { int i=0,k=0; while(iL.length) { if(L.elem[i]=x L.elem[i]=y) k++; //记录被删记录的个数 else L.elem[i-k]=L.elem[i]; //前移k个位置 i++; } L.length=L.length-k; } 设有一个顺序表L，含有2n个整数，其中n个为负数，n个为正数，设计一个算法将L中所有元素按正负数相间排列。要求本算法的时间复杂度为O(n)，空间复杂度为O(1) void move(SqList L) { int i=0,j=L.length-1; int temp; while(ij) //使得正数都在前半部分，负数都在后半部分 { while(ijL.elem[i]0)i++; while(ijL.elem[j]0)j--; if(ij) //交换L.elem[i](负数)和L.elem[j](正数) { temp=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=temp; } } i=1; while(iL.length/2) //通过交换使得正负数相间 { j=L.length-2; temp=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=temp; i=i+2; j=j-2; } } 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。 Status ListDelete_L(LinkList L,ElemType mink,ElemType maxk) { LinkList p,q,prev=NULL; if(minkmaxk)return ERROR; pre=L; p=pre-next; //pre是p的前驱，p是pre的后继 while(pp-data=mink){ //寻找第一大于mink的元素，让p指向它，pre指向其前驱 pre=p; p=p-next; }//while while(pp-datamaxk) //删除大于mink小于maxk的结点 { pre-next=p-next; free(p); p=pre-next; } return OK; } 有一个带头结点的单链表L（至少有一个结点），设计算法将L逆置。 Status ListOppose_L(LinkList L) { LinkList p,q; p=L-next; //p指向单链表第一个结点 L-next=NULL; //形成空的单链表 while(p){ //采用头插入法将p结点插入到头结点的后面实现逆置 q=p; p=p-next; q-next=L-next; L-next=q; } return OK; } 6、试写一高效的算法，删除有序单链表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。 解： void ListDelete_LSameNode(LinkList L) { LinkList p,q,pre; pre=L; p=pre-next; //pre是p的前驱，p是pre的后继 while(p){ pre=p; p=p-next; if(pp-data==pre-data){ pre-next=p-next; //删除相同的元素