数据�l�构�W�二章算法设计题 [9]_跨考网

8. 已知�U�性表�Q?/span>a1 a2 a3 �?/span>an�Q�按��序存于内存�Q�每个元素都是整敎ͼ�试设计用最���时间把所有��gؓ负数的元素移到全部正数值元素前边的���法�Q�例�Q�（x,-x,-x,x,x,-x �?/span>x�Q�变为（-x,-x,-x�?/span>x,x,x�Q�。�?a target="_blank">东北大学 1998 �?/span> (15�?/span>)�?/span>

　　�c�M��本题的另外叙�q�有�Q?/span>

　　�Q?/span>1�Q�设有一元素为整数的�U�性表L=(a1,a2,a3,�?/span>,an),存放在一�l�数�l?/span>A[N]�?/span>,设计一个算�?/span>,以表�?/span>an作�ؓ参考元�?/span>,���该表分为左、右两部�?/span>,其中左半部分每个元素���于�{�于an,叛_��部分每个元素都大�?/span>an, an位于分界位置�?/span>(要求�l�果仍存攑֜�A[N]�?/span>)。�?a target="_blank">北京理工大学 1999 八（6分）�?/span>

　　�Q?/span>2�Q�顺序存储的�U�性表A,其数据元素�ؓ整型,试编写一���法,��?/span>A拆成B�?/span>C两个�?/span>,�?/span>A中元素值大于等�?/span>0的元素放�?/span>B,���于0的放�?/span>C�?/span>.. 要求:

　1�Q�表B�?/span>C另外讄���存储�I�间�Q?/span>

　　2�Q�表B�?/span>C不另外设�|?/span>,而利�?/span>A的空间。�?a target="_blank">�׃��大学 2001 �?ji��)�?/span>1 (12�?/span>)�?/span>

　　�Q?/span>3�Q�知�U�性表�Q?/span>a1, a2,a3,�?/span>,an�Q�按��序存储�Q�且每个元素都是整数均不相同�Q�设计把所有奇数移到所有偶数前边的���法。（要求旉���最���，辅助�I�间最���）【东北大�?/span> 1997 �?/span> (15�?/span>)�?/span>

　　�Q?/span>4�Q�编写函数将一整数序列中所有负数移到所有正��C��前，要求旉���复杂度�ؓO�Q?/span>n�Q�。�?a target="_blank">南京航空航天大学 2001 八（10分）�?/span>

　　�Q?/span>5�Q�已知一个由n�Q?/span> �?/span>n=1000�Q�个整数�l�成的线性表�Q�试设计该线性表的一�U�存储结构，�q�用标准pascal语言描述���法�Q�实现将n个元素中所有大于等�?/span>19的整数放在所有小�?/span>19的整��C��后。要求算法的旉���复杂度�ؓO(n),�I�间复杂�?/span>O(1)。�?a target="_blank">西安交通大�?/a> 1996 六（11分）�?/span>

　　【参考答案�?/span>

　　[题目分析]题目要求重排n个元素且以顺序存储结构存储的�U�性表�Q���得所有��gؓ负数的元素移到正数元素的前面。这可采用快速排序的思想来实玎ͼ�只是提出暂存的第一个元素（枢��u�Q��ƈ不作��Z��后的比较标准�Q�比较的标准是元素是否�ؓ负数�?/span>

　　int Rearrange�Q?/span>SeqList a; int n)

　　�?/span>a是具�?/span>n个元素的�U�性表�Q�以��序存储�l�构存储�Q�线性表的元素是整数。本���法重排�U�性表a�Q?/span>

　　∥��所有��gؓ负数的元素移到所有��gؓ正数的数的前面�?/span>

　　{i=0; j=n-1; �?/span> i,j为工作指针（下标�Q�，初始指向�U�性表a的第1个和�W?/span>n个元素�?/span>

　　t=a[0]; ∥暂存枢轴元素�?/span>

　　while(i<j)

　　{while(i<j && a[j]>=0) j--; �?/span> 若当前元素�ؓ大于�{�于�Ӟ��则指针前�U�R�?/span>

　　if(i<j){a[i]=a[j];i++;} �?/span> ���负数前�U�R�?/span>

while(i<j &&a[i]<0)i++; �?/span> 当前元素�����数时指针后移�?/span>

　　if(i<j) a[j--]=a[i]; �?/span> 正数后移�?/span>

　　}

　　a[i]=t; ∥将原第一元素攑ֈ�最�l�位�|��?/span>

　　}