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

部分顺序表算法的总结。

Min/Max

顺序表使用下标i记录位置，链表使用指针Min/Max来指向对应结点。

intMin=0;for(inti=1;i<n;i++){if(data[i]<data[Min])Min=i;}//顺序表Node*Min=L;Node*p=L;while(p){if(p->data<Min->data)Min=p;p=p->next;}//链表

逆置(a->a-1)

逆置即指将链表元素实现倒序。

即a1 a2 … an>>an an-1 …a2 a1。

voidreverse(ElemType data[],intlow,intn){for(inti=low;i<low+n/2;i++){swap(data[i],data[2*low+n-i-1]);//如low=0时a0与an-1,a1与an-2}}//扫描一遍线性表即可，因此T(n)=O(n),S(n)=O(n)

使用逆置可实现表内元素平移m位的效果。

即a1 a2 …am am+1 … an >>am+1 am+2 … an a1 a2 …am。
a b c d e平移2位即得c d e a b

思路：即求ab>>ba;ab->a-1b-1->ba
步骤：
1：逆序a1 a2 … am>>am am-1 … a2 a1;
2：逆序am+1 am+2 … an>>an an-1 … am+1;
3：此时线性表变为am am-1 … a2 a1 an an-1 … am+1；再次逆序线性表即可。

a b c d e>>b a e d c>>c d e a b

voidreverse_m(ElemType data,intn,intm){//向左平移m位reverse(data,0,p);reverse(data,p+1,n-p);reverse(data,0,n);}//时空复杂度同reverse函数

删值X

遍历一遍线性表，删去符合要求的结点。

所有值为X的结点

需要记录线性表中值不为X或为X的结点个数，从而确定删除后所在位置。

//记录不为X的个数voiddelete_X(ElemType data[],int&n){intcount=0;for(inti=0;i<n;i++){if(data[i]!=X){count++;data[count]=data[i];}}n=count;}//记录为X的个数voiddelete_X(ElemType data[],int&n){intcount=0;for(inti=0;i<n;i++){if(data[i]==X)count++;elsedata[i-count]=data[i];//值不为X的结点需前移count位}n-=count;}

删区间[s,t]上的值

若非有序表，则逐个遍历进行判断。
若是有序表，则可减少遍历的次数。

booldelete_StoT(ElemType data[],int&n,ElemType s,ElemType t){inti,j;if(s>t||n==0)//输入非法或线性表为空returnfalse;for(i=0;i<n&&data[i]<s;i++);//寻找第一个值大于等于s的结点位置if(i>=n)returnfalse;for(j=i;j<n&&data[j]<=t;j++);//寻找第一个值大于t的结点位置，若无则为n；for(j<n;i++,j++){//j位置后的结点平移至i位置之后data[i]=data[j];}n=i;//i为表长returntrue;}

1 3 4 5 6 7 8 删去[3,6]的值
则i=1,j=5；>>1 7 8

删去重复值(有序表)

将每一结点视为待插入点，与已插入表表尾进行比较，若相同则跳过，若不相同插入至表尾。

voiddelete_same(ElemType data,int&n){for(inti=1,j=0;i<n;i++){//i为待插入结点下标，j为已插入表表尾下标if(data[i]!=data[j])data[++j]=data[i];//插入}n=j+1;}

1 2 2 3 4 5 5 6>> 1 2 3 4 5 6
j：0 1 1 2 3 4 4 5
i：_ 1 2 3 4 5 6 7

Merge()

将两个有序表合并为一个有序表。
步骤：i,j均从表头出发
若data1[i]<data2[j],将data1[i]放入新的表尾，i++ //假设单调递增，递减同理
否则将data2[j]放入新的表尾，j++
其中一表为空时将剩余非空表直接插入值新表中。

intMerge(ElemType data1[],ElemType data2[],intn1,intn2,ElemType&data[]){inti,j,k;for(i=0,j=0,k=0;i<n1&&j<n2;){if(data1[i]<data2[j])data[k++]=data1[i++];elsedata[k++]=data2[j++];}while(i<n1)data[k++]=data1[i++];while(j<n2)data[k++]=data2[j++];return0;}

若要求合并表无重复元素，可先将表1，表2删去重复值，之后合并时若值相等取其一入表，之后均后移一位。

找主元素

主元素即为重复数大于n/2的结点数据。
一种较为高效的算法思想可总结为用Main记录当前元素，相对数count记录Main的重复数，若下一元素相同则count++；反之count–；若count=0则选择下一元素作为新的记录结点。遍历一遍后还需重新扫描一次线性表，得到绝对个数count。此时时间负责度为O(n)，且空间复杂度为O(1)。

ElemTypeMain_data(ElemType data[].intn){intcount=0;ElemType Main=data[0];for(inti=1;i<n;i++){if(count!=0{if(data[i]==Main)count++;elsecount--;}else{count=1;Main=data[i];}}count=0;for(inti=0;i<n;i++){if(Data[i]==Main)count++;}}if(count>n/2)returnMain;elsereturn-1;}

两个有序表的中位数(等长)

如S1=(11,13,15,17,19),S2=(2,4,6,8,20),则中位数为11(向上取整）。
思路：比较两个序列的中位数，若相同则返回；
若不同，较大的序列保留较小部分序列，较小的序列保留较大部分序列，重新比较，直到序列个数均为1，此时较小值即为所求。要求删去长度相等。

15>6 >> 11 13 15 6 8 20
13>8 >> 11 13 8 20
13>10 >> 11 20
11<20 则返回11

ElemTypeMidAandB(ElemType A[],ElemType B[],intn1,intn2){intlow1=low2=0,high1=high2=n-1;while(low1<high1||low<high2){intmid1=(low1+high1)/2,mid2=(low2+high2)/2;if(A[mid1]==B[mid2])returnA[mid1];elseif(A[mid1]>B[mid2]){if(low1+high1)%2==0){high1=mid1;low2=mid2;}else{high1=mid1 low2=mid2+1;}}else{if(low1+high1)%2==0){low1=mid1;high2=mid2;}else{low1=mid1+1;high2=mid2;}}}returnA[low1]>B[low2]?B[low2]:A[low1];}