数据结构，线性表，顺序表常见算法

算法和问题来自于试卷，辅导书，以及网络。

//顺序表的一般数据结构 typedef struct{ int data[Maxsize]; int length; }SqList;

算法2.1.1

从顺序表中删除具有最小值的元素，并由函数返回被删元素值。空出位置由最后一个补齐

分析：算法很简单，基本思想可参照简单选择排序思想

int deleteMin(Sqlist &L, int &e) { int i,j; if(L.length==0) return 0; min=L.data[0]; for(i=1;i<L.length;i++) { if(L[i]<min) { j=i; e=L[i]; } } L.data[j]=L[L.length-1]; --L.length; return e; }

算法2.1.2

将顺序表L所有元素逆置

分析：算法很简单，用两个指针，一个用于替换的变量即可，从两头到中间进行替换。

void revert(Sqlist &L) { int i=0,j=L.length-1; int temp; while(i<j) { temp=L[i]; L[i]=L[j]; L[j]=temp; i++;j--; } }

算法2.1.3

对长度为n的顺序表，删除其中所有值等于x的元素，要求其时间复杂度为O（n）,空间复杂度为O（1）

分析：若不要求空间复杂度，则算法很容易利用一个长度为n的数组实现，现在要求空间复杂度为O（1），则放弃采用这种思想。而且时间复杂度为0（n），则要避免删除后的数组移动，可以用两个指针，第一个遍历完整个数组，第二个当不等于x时才向前移动，这样便将不等于x的数保存在了数组中。

void deleteX(Sqlist &L, int n,int x) { int i=0,j=0,count; //count统计不等于x的数的个数 for(i=0;i<n;i++) { if(L.data[i]!=x) { L.data[j++]=L.data[i]; ++count; } } L.length=count; }

算法2.1.4

从顺序表中删除值在给定的s与t之间（s<t），若不合法则退出运行。

分析：类似与2.1.3 ，只不过删除的条件变了

bool deleteA(Sqlist & L,int s, int t) { int i=0,j=0; if(s>=t||L.length==0) return 0; for(i=0;i<n;i++) { if(L.data[i]<=s&&L.data[i]>=t) //若值不在s，t之间则保存 L.data[j++]=L.data[i]; } L.length=j; return 1; }

算法2.1.5

从有序顺序表中删除值重复的元素，使其中的元素均不相同。

分析：若顺序表无序，则删除相同的较为麻烦，需对每个元素遍历一次顺序表，时间复杂度达到了o(n²)m若表中元素均有序，则这样考虑，相等的元素必定是连续的 比如 12234566689 ，同算法2.1.3， 可以采用两个指针，对于相邻的元素如果相同则跳过这个元素存储即可。

void deleteSame(Sqlist &L) { int i,j=0; for(i=1;i<L.length;i++) //i用于遍历表，j用于存储不相等值 { if(L.data[j]!=L.data[i]) { L.data[++j]=L.data[i]; } //相邻不相等，则存储 } L.length=j+1; //循环结束后j+1才是表长 }

算法2.1.6

在一维数组A[m+n]中有两个线性表（a1，a2，…,am）和（b1,b2,…,bn）。编写算法将两个顺序表位置互换，将（b1,b2,…,bn），放在（a1，a2，…,am）前。

分析：该算法稍微复杂些，一般分为两步：①先将整个线性表逆置，其中元素会变为（（bn,…,b2,b1），（am…,a2，a1））。②观察发现，b表中的元素已在a表前，但a表，b表中的元素均为逆置状态，故再分别对a，b表进行逆置，就能达到要求的效果。这里可以对算法2.1.2做出小小的修改。

void revert(Sqlist &L, int first, int rear) { int temp; while(first<rear) { temp=L.data[first]; L.data[first]=L.data[rear]; L.data[rear]=temp; first++;rear--; } } void transferList(Sqlist &L,int m,int n) { int i=0,j=m+n-1; revert(L,i,j); revert(L,0,n-1); revert(L,n,m+n-1); }//注，表空，越界等错误判别略。