[数据结构]一般顺序表部分总结

部分顺序表算法的总结。Min/Max顺序表使用下标i记录位置链表使用指针Min/Max来指向对应结点。intMin0;for(inti1;in;i){if(data[i]data[Min])Mini;}//顺序表Node*MinL;Node*pL;while(p){if(p-dataMin-data)Minp;pp-next;}//链表逆置(a-a-1)逆置即指将链表元素实现倒序。即a1 a2 … anan an-1 …a2 a1。voidreverse(ElemType data[],intlow,intn){for(intilow;ilown/2;i){swap(data[i],data[2*lown-i-1]);//如low0时a0与an-1,a1与an-2}}//扫描一遍线性表即可因此T(n)O(n),S(n)O(n)使用逆置可实现表内元素平移m位的效果。即a1 a2 …am am1 … an am1 am2 … an a1 a2 …am。a b c d e平移2位即得c d e a b思路即求abba;ab-a-1b-1-ba步骤1逆序a1 a2 … amam am-1 … a2 a1;2逆序am1 am2 … anan an-1 … am1;3此时线性表变为am am-1 … a2 a1 an an-1 … am1再次逆序线性表即可。a b c d eb a e d cc d e a bvoidreverse_m(ElemType data,intn,intm){//向左平移m位reverse(data,0,p);reverse(data,p1,n-p);reverse(data,0,n);}//时空复杂度同reverse函数删值X遍历一遍线性表删去符合要求的结点。所有值为X的结点需要记录线性表中值不为X或为X的结点个数从而确定删除后所在位置。//记录不为X的个数voiddelete_X(ElemType data[],intn){intcount0;for(inti0;in;i){if(data[i]!X){count;data[count]data[i];}}ncount;}//记录为X的个数voiddelete_X(ElemType data[],intn){intcount0;for(inti0;in;i){if(data[i]X)count;elsedata[i-count]data[i];//值不为X的结点需前移count位}n-count;}删区间[s,t]上的值若非有序表则逐个遍历进行判断。若是有序表则可减少遍历的次数。booldelete_StoT(ElemType data[],intn,ElemType s,ElemType t){inti,j;if(st||n0)//输入非法或线性表为空returnfalse;for(i0;indata[i]s;i);//寻找第一个值大于等于s的结点位置if(in)returnfalse;for(ji;jndata[j]t;j);//寻找第一个值大于t的结点位置若无则为nfor(jn;i,j){//j位置后的结点平移至i位置之后data[i]data[j];}ni;//i为表长returntrue;}1 3 4 5 6 7 8 删去[3,6]的值则i1,j51 7 8删去重复值(有序表)将每一结点视为待插入点与已插入表表尾进行比较若相同则跳过若不相同插入至表尾。voiddelete_same(ElemType data,intn){for(inti1,j0;in;i){//i为待插入结点下标j为已插入表表尾下标if(data[i]!data[j])data[j]data[i];//插入}nj1;}1 2 2 3 4 5 5 6 1 2 3 4 5 6j0 1 1 2 3 4 4 5i_ 1 2 3 4 5 6 7Merge()将两个有序表合并为一个有序表。步骤i,j均从表头出发若data1[i]data2[j],将data1[i]放入新的表尾i //假设单调递增递减同理否则将data2[j]放入新的表尾j其中一表为空时将剩余非空表直接插入值新表中。intMerge(ElemType data1[],ElemType data2[],intn1,intn2,ElemTypedata[]){inti,j,k;for(i0,j0,k0;in1jn2;){if(data1[i]data2[j])data[k]data1[i];elsedata[k]data2[j];}while(in1)data[k]data1[i];while(jn2)data[k]data2[j];return0;}若要求合并表无重复元素可先将表1表2删去重复值之后合并时若值相等取其一入表之后均后移一位。找主元素主元素即为重复数大于n/2的结点数据。一种较为高效的算法思想可总结为用Main记录当前元素相对数count记录Main的重复数若下一元素相同则count反之count–若count0则选择下一元素作为新的记录结点。遍历一遍后还需重新扫描一次线性表得到绝对个数count。此时时间负责度为O(n)且空间复杂度为O(1)。ElemTypeMain_data(ElemType data[].intn){intcount0;ElemType Maindata[0];for(inti1;in;i){if(count!0{if(data[i]Main)count;elsecount--;}else{count1;Maindata[i];}}count0;for(inti0;in;i){if(Data[i]Main)count;}}if(countn/2)returnMain;elsereturn-1;}两个有序表的中位数(等长)如S1(11,13,15,17,19),S2(2,4,6,8,20),则中位数为11(向上取整。思路比较两个序列的中位数若相同则返回若不同较大的序列保留较小部分序列较小的序列保留较大部分序列重新比较直到序列个数均为1此时较小值即为所求。要求删去长度相等。156 11 13 15 6 8 20138 11 13 8 201310 11 201120 则返回11ElemTypeMidAandB(ElemType A[],ElemType B[],intn1,intn2){intlow1low20,high1high2n-1;while(low1high1||lowhigh2){intmid1(low1high1)/2,mid2(low2high2)/2;if(A[mid1]B[mid2])returnA[mid1];elseif(A[mid1]B[mid2]){if(low1high1)%20){high1mid1;low2mid2;}else{high1mid1 low2mid21;}}else{if(low1high1)%20){low1mid1;high2mid2;}else{low1mid11;high2mid2;}}}returnA[low1]B[low2]?B[low2]:A[low1];}