此处记录常见的顺序表题目。
1.顺序表--对长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
下面给出了C++与C的解法。
算法思想：1.定义i,j变量，i变量用来指示顺序表的下标，用于指示所有元素，j元素用来保存目的顺序表长度，并用来指示下一个可以存储合法数据的位置。
2.遍历顺序表所有元素，当数据不是x时，则把合法数据加入线性表，j变量加1。
3.当遍历到的数据为x时，则不去理会，继续执行下次操作。
总结：简单说，就是合法数据加入顺序表，顺序表长度加一。
例子：
/*对长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素*/ #define MAXSIZE 50 typedef int ElemType; typedef struct{ ElemType data[MAXSIZE]; int length; }SqList; //1.C语言 bool Del_x_1(SqList *L,ElemType x){//这里给进结构体的指针，因为要改变原结构体内顺序表的值，给进指针会更方便一些，速度上也会快一些。 int i,j; if(L->length==0) return false; for(i=0,j=0;i<L->length;i++) if(L->data[i]!=x) L->data[j++]=L->data[i];//注意这里i不要++，因为i是由循环体控制的 L->length=j;//length是计算的个数，从1开始算起，所以j++后，作为长度是正好的 return true; } //2.C++语言 bool Del_x_1(SqList &L,ElemType x){//这里给进结构体的指针，因为要改变原结构体内顺序表的值，给进指针会更方便一些，速度上也会快一些。 int i,j; if(L.length==0) return false; for(i=0,j=0;i<L.length;i++) if(L.data[i]!=x) L.data[j++]=L.data[i];//注意这里i不要++，因为i是由循环体控制的 L.length=k;//length是计算的个数，从1开始算起，所以j++后，作为长度是正好的 return true; }
2.从顺序表L中删除元素x到y之间的所有元素(x<=y)
算法思想：1.定义i,j变量，i变量用来指示顺序表的下标，用于指示所有元素，用于遍历；j元素用来记录不合法的元素个数。i-j元素用来保存目的顺序表长度，并用i-j来指示下一个可以存储合法数据的位置。
2.遍历顺序表所有元素，当数据是合法数据时，则把合法数据加入线性表。
3.当遍历到的数据为非法数据时，则j自增1，继续执行下次操作。
4.i-j总能够表示下一个合法数据可以存储的位置。
总结：简单说，就是合法数据加入顺序表，顺序表长度加一。
下面是王道数据结构给出的习题思路：
//C语言解决 void delallxy(Sqlist *l,int x,int y) { int i=0; int j=0; while(i<l->length) { if(l->data[i]>=x && l->data[i]<=y) j++; else l->data[i-j]=l->data[i]; i++; } l->length-=j; } //C++解决 void delallxy(Sqlist &l,int x,int y) { int i=0; int j=0; while(i<l.length) { if(l.data[i]>=x && l.data[i]<=y) j++; else l.data[i-j]=l.data[i]; i++; } l.length-=j; }
我觉得上面的思路虽然正确，但是看着很别扭，因为说白了，算法思路还是和第一题的思路一样，合法数据加入线性表，不合法则不予理会，所以我稍微修改了一下。
//C语言解决 void delallxy(Sqlist *l,int x,int y) { int i=0; int j=0; while(i<l->length) { i++;//i总是自增1，用于遍历数据 //如果是合法数据，则加入顺序表，j+1 if(l->data[i]<x && l->data[i]>y) { data[j]=data[i] j++; } } l->length=j; } //C++解决 void delallxy(Sqlist &l,int x,int y) { int i=0; int j=0; while(i<l.length) { i++;//i总是自增1，用于遍历数据 //如果是合法数据，则加入顺序表，j+1 if(l.data[i]<x && l.data[i]>y) { data[j]=data[i] j++; } } l.length=j; }
个人总结：
（1）诸如此类删除某个匹配的数字，或者某个数字范围的顺序表，都是按照合法数据加入，非法数据不予理会这个通用思路就好。
（2）虽然对于有些特殊点的题目，比如顺序表是有序的，那可能只要记录第一个大于X，和第一个大于Y，删除X到Y前连续的一块数字段就好。但是最后写出来的代码，都和我说的通用思路写的时间复杂度，空间复杂度差不多，那就记住最通用的就好了。
3.删除有序顺序表的重复值，使其中每个元素都不相同。
算法思路：因为是顺序有序表，所以需要删除重复的连续位置即可，每个元素每一次都与整段数字最后一个比较，若相同不予理会，若不同加入顺序表。
//C语言解决 void delete_some(Sqlist *l) { int i,j;//i用于指示可以存放的下一个合法数据的位置，j遍历数据 for(i=0,j=1;j<L.length;j++) if(L->data[i]!=L->data[j]) L->data[++i]=L->data[j] l->length=i+1; } //C++解决 void delall_some(Sqlist &l) { int i,j; for(i=0,j=1;j<L.length;j++) if(L.data[i]!=L.data[j]) L.data[++i]=L.data[j] l.length=i+1; }
4.合并两个顺序表，使其仍然为顺序表
算法思路：分别把两个顺序表当前最小的值拿出来比较，如果谁小，谁就插入新数组，所以需要三个数组，时间复杂度T=max{f(m),f(n)},m,n为两个数组的长度
//C语言 bool Merge(SqList A, SqList B, SqList *C) { //将有序顺序表AB合并为有序的顺序表C int i, j, k = 0; while (i < A.length&&j < B.length) { if (A.data[i] <= B.length) C->data[k++] = A.data[i++]; else C->data[k++] = B.data[j++]; } //若A没完，则把剩下的A,都加入C while (i < A.length) C->data[k++] = A.data[i++]; //若B没完，则把剩下的B,都加入C while (i < B.length) C->data[k++] = B.data[j++]; C->length = k; return true; } //C++ bool Merge(SqList A, SqList B, SqList &C) { //将有序顺序表AB合并为有序的顺序表C int i, j, k = 0; while (i < A.length&&j < B.length) { if (A.data[i] <= B.length) C.data[k++] = A.data[i++]; else C.data[k++] = B.data[j++]; } //若A没完，则把剩下的A,都加入C while (i < A.length) C.data[k++] = A.data[i++]; //若B没完，则把剩下的B,都加入C while (i < B.length) C.data[k++] = B.data[j++]; C.length = k; return true; }
5.线性表元素（a1,a2,a3……an）为有序顺序表，要求设计一算法，完成最短时间在表中找到该元素，若找到，将其与后继元素互换，若找不到，则插入表中使其仍保持有序
算法思想：
（1）使用到了折半查找，即二分法，每次都拿中间的数字与所求的数字进行比较，若大于中间的数字，则舍去左边，进行比较右边，反之亦然。
（2）需要注意的是，二分法无需考虑奇偶个，因为(low+hight)/2始终向下取整，举例子：（1+5）/2=3,(1+6)/2=3。
（3）二分法终止条件为，low>hight;下面图为终止条件：
void SearchExchangeInsert(ElemType A[],ElemType x){ int low=0,high=n-1,mid;//low和high指向顺序表下界和上界的下标 while(low<=high){ mid=(low+high)/2; //找中间位置 if(A[mid]==x) break; //找到x,退出while循环 else if (A[mid]<x) low=mid+1; //到mid中点的右半部去查 else high=mid-1; //到中点mid的左半部去查 }//下面两个if语句只会执行一个
if (A[mid]==x&&mid!=n-1){//查找成功且x不是最后一个元素，若是最后一个元素则不予操作 ElemType t; t=A[mid]; A[mid]=A[mid+1]; A[mid+1]=t; } if (low>high){ //查找失败，X不在这个顺序表内，此时的high是最后一个小于x的数（在high后面插入）或者是high=-1（也是在high后面插入） for (i=n-1;i>high;i--) A[i+1]=A[i]; //后移元素 A[i+1]=x;//插入x } }
6.顺序表逆置问题。
奇数情况
偶数情况
处理代码一样：
