运行结果：

 4.从有序顺序表中删除其值在给定值s与t之间（包含s和t，要求s

思路：本题与上一题存在区别。因为是有序表，所以删除的元素必然是相连的整体。先寻找值大于等于s的第一个元素(第一个删除的元素)，然后寻找值大于t的第一个元素(最后一个删除的元素的下一个元素)，要将这段元素删除，只需直接将后面的元素前移。

#include
using namespace std;
const int maxn=100;
int len;
typedef struct
{int data[maxn];int length;
}Sqlist;
bool del_s_t(Sqlist &l,int s,int t)
{int i,j;if(len==0||s>=t) return 0;//表为空，或者s、t不合法，则返回falsefor(i=0;i=len) return false;//所有元素都小于s，返回falsefor(j=i;j>len;//输入顺序表的长度for(int i=0;i>lis.data[i];}del_s_t(lis,3,6);for(int i=0;i

运行结果：

 

5.从顺序表中删除其值在给定值s与t之间（包含s和t，要求s

 思路：用k记录下元素值在s至t之间元素的个数，对于当前扫描的元素，若其值不在s到t之间，则前移k个位置；否则执行k++。

#include
using namespace std;
const int maxn=100;
int len;
typedef struct
{int data[maxn];int length;
}Sqlist;
bool del_s_t(Sqlist &l,int s,int t)
{int k;l.length=len;if(len==0||s>=t) return 0;//表为空，或者s、t不合法，则返回falsefor(int i=0;i=s&&l.data[i]<=t) k++;//记录要删除元素的个数elsel.data[i-k]=l.data[i];//当前元素前移k个位置}l.length-=k;len=l.length;return true;
}
int main()
{Sqlist lis;cin>>len;//输入顺序表的长度for(int i=0;i>lis.data[i];}del_s_t(lis,3,6);for(int i=0;i

 运行结果：

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

思路：注意是有序顺序表，值相同的元素一定在连续的位置上，用类似于直接插入排序 的思想，初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同，若相同，则继续向后判断，若不同，则插入前面的非重复有序表的最后，直至判断到表尾为止。

#include
using namespace std;
const int maxn=100;
int len;
typedef struct
{int data[maxn];int length;
}Sqlist;
bool del_same(Sqlist &l)
{l.length=len;if(l.length==0) return false;int i,j;for(i=0,j=1;j>len;//输入顺序表的长度for(int i=0;i>lis.data[i];}del_same(lis);for(int i=0;i

运行结果：

7.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

思路：首先，双指针i、j，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。

#include
using namespace std;
const int maxn=100;
typedef struct
{int data[maxn];int length;
}Sqlist;
bool mergeab(Sqlist &lisa,Sqlist &lisb,Sqlist &lis)
{int i=0,j=0,k=0;if(lisa.length+lisb.length>lis.length) return false;while(i>lisa.length>>lisb.length>>lis.length;//输入顺序表a,b的长度,顺序表lisb的元素for(int i=0;i>lisa.data[i];}for(int i=0;i>lisb.data[i];}mergeab(lisa,lisb,lis);for(int i=0;i

运行结果：

 

8.已知在一维数组A[m+n]中依次存放两个线性表（a1,a2,...,）和（b1, b2, ...,）。编写一个函数，将数组中两个顺序表的位置互换，即将（b1, b2, ...,）放在（a1,a2,...,）的前面。

思路：先将数组中的全部元素原地逆置,再对前n个元素和后m个元素分别使用逆置算法。

#include
using namespace std;
const int maxn=100;
typedef struct
{int data[maxn];int length;
}Sqlist;
void rev(Sqlist &l,int st,int en)
{int tem;for(int i=st,j=en;j-i>=1;i++,j--){tem=l.data[i];l.data[i]=l.data[j];l.data[j]=tem;}
}
int main()
{Sqlist lis;int m,n;cin>>m>>n;lis.length=m+n;for(int i=0;i>lis.data[i];}for(int i=m;i>lis.data[i];}cout<<"原始顺序表："<

运行结果： 

 

9.线性表 （a1,a2,...,）中的元素递增有序且按顺序存储于计算机内。要求设计一个算法， 完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换， 若找不到，则将其插入表中并使表中元素仍递增有序。

思路：顺序存储的线性表递增有序，可以顺序查找，也可以折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找法。

#include
using namespace std;
const int maxn=100;
typedef struct
{int data[maxn];int length;
}Sqlist;
//二分查找元素x
void findx(Sqlist &l,int x)
{int left=0,right=l.length-1,mid;while(left<=right){mid=left+right>>1;if(x==l.data[mid]) break;else if(x>l.data[mid]) left=mid+1;//在右侧else right=mid-1;//在左侧}if(l.data[mid]==x&&left!=l.length-1)//找到啦x，且不在最后一个位置，则可以与后继节点交换{int tem=l.data[mid];l.data[mid]=l.data[mid+1];l.data[mid+1]=tem;}//没有找到//由于经过二分查找之后，能确定x在right在右边，即在right的后插入xif(left>right){int i;for(i=l.length-1;i>right;i--) l.data[i+1]=l.data[i];//元素后移l.data[i+1]=x;//插入xl.length+=1;//更新一下顺序表的长度}
}
int main()
{Sqlist lis;cin>>lis.length;for(int i=0;i>lis.data[i];}int x;cout<<"输入要查找的元素值x："<>x;findx(lis,x);for(int i=0;i

运行结果：