前言
??书接上文
??完整程序参考：郝斌数据结构-线性表之顺序表程序
题目
第四题
??从有序顺序表中删除其值在给定值s 与t之间（要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
我的版本：
/*有序表的元素是按照升序或降序排列好的*/
/*只需要找到需要删除的s和t所在位置*/
bool Del_s_t(struct arr *pArr,int s,int t){
int i,j;
int k;
if(s>=t||is_empty(pArr)){
return false;
} //不合理的情况退出运行
for(i=0;i<pArr->cnt;i++){
if(pArr->pBase[i]<s){
k++; //记录满足条件的元素个数
}else{
break;
}
}
for(j=pArr->cnt-1;j>0;j--){//cnt-1是最有一个元素的数组下标
if(pArr->pBase[j]>t){
k++; //记录满足条件的元素个数
}else{
break;
}
}
for(;j<pArr->cnt;i++,j++){
pArr->pBase[i] = pArr->pBase[j+1];//j+1的目的是将等于t的元素删掉
}
pArr->cnt = k; //将多余元素删除
return true;
}
参考答案：
bool Del_s_t_two(struct arr *pArr,int s,int t){
int i,j;
if(s>=t||pArr->cnt==0){
return false;
}
for(i=0;i<pArr->cnt&&pArr->pBase[i]<s;i++);//i直接停在小于s的第一个元素下标上
if(i>=pArr->cnt){
return false;//检错，例如出现数组最大元素5，删除区间在5-7的情况；
}
for(j=i;j<pArr->cnt&&pArr->pBase[j]<=t;j++);//j直接停在大于t的第一个元素下标上
for(;j<pArr->cnt;i++,j++){
pArr->pBase[i] = pArr->pBase[j];
}
pArr->cnt=i;//脑抽了！！！i就是数组长度，无需再用k计数了。
return true;
}
第五题
??从顺序表中删除其值在给定值s与t之间(包含s和t，要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
基本思路：
??不再是有序表了，首先遍历数组的全部元素，找到满足小于s和大于t的元素。用k计数，将满足条件的元素存入k的连续下标数组内。k的值就是新数组的长度。
bool Del_s_t_upgrade(struct arr *pArr,int s,int t){
int i,k=0;
if(is_empty(pArr)||s>=t){
return false;
}
for(i=0;i<pArr->cnt;i++){
if(pArr->pBase[i]<s||pArr->pBase[i]>t){
pArr->pBase[k] = pArr->pBase[i];
k++;
}
}
pArr->cnt = k;
return true;
}
参考答案：
bool Del_s_t_upgrade(struct arr *pArr,int s,int t){
int i,k=0;
if(is_empty(pArr)||s>=t){
return false;
}
for(i=0;i<pArr->cnt;i++){
if(pArr->pBase[i]>=s||pArr->pBase[i]<=t){
k++;//记录在s和t之间的元素
}else{
pArr->pBase[i-k]=pArr->pBase[i];//将在s和t之外的元素按顺序排列
}
}
pArr->cnt -= k; //这样判断反而有点麻烦了
return true;
}
第六题
??从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
/*有序表中，值相同的元素一定在连续的位置*/
/*我的思路，将相邻的两个元素对比，不同则存入第一个元素*/
bool Del_same(struct arr *pArr){
int i;
int k=0;
if(is_empty(pArr)){
return false;
}
for(i=0;i<pArr->cnt-1;i++){
if(pArr->pBase[i]!=pArr->pBase[i+1]){
pArr->pBase[k]=pArr->pBase[i];
k++;
}
}
pArr->cnt=k;
return true;
}
BUG:
参考答案：
bool Del_same(struct arr *pArr){
int i,j;
if(is_empty(pArr)){
return false;
}
//将第一个元素作为被比较的对象
for(i=0,j=1;j<pArr->cnt;j++){
if(pArr->pBase[i]!=pArr->pBase[j]){//查找下一个和上一个元素值不同的元素
pArr->pBase[++i]=pArr->pBase[j];//找到后将j元素覆盖i元素的后一个元素。
}
}
pArr->cnt = i+1;//更新当前数组的有效计数。
return true;
}
第七题
??将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
我的思路：错得比较离谱。
参考答案：
bool Sum_A_B(struct arr *pArr1,struct arr *pArr2,struct arr *pArr3){
int i=0,j=0;
if(pArr1->cnt+pArr2->cnt>pArr3->len){
return false;
}
while(i<pArr1->cnt&&j<pArr2->cnt){
if(pArr1->pBase[i]<=pArr2->pBase[j]){
append_arr(pArr3,pArr1->pBase[i++]);
}
else{
append_arr(pArr3,pArr2->pBase[j++]);
}
show_arr(pArr3);
}
while(i<pArr1->cnt){
append_arr(pArr3,pArr1->pBase[i++]);
show_arr(pArr3);
}
while(j<pArr2->cnt){
append_arr(pArr3,pArr2->pBase[j++]);
show_arr(pArr3);
}
return true;
}
第八题
??已知在一维数组A[m+n]中依次存放两个线性表(a1,a2, a3,…, am)和(b1, b2, b3,…, bn,)。编写一个函数，将数组中两个顺序表的位置互换，即将(b1, b2, b3…, bn,)放在(a1, a2,a3,…,am)的前面。
第九题
??线性表(a1, a2, a3,.…,an,)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。
第十题
??【2010统考真题】设将n (n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p ( 0<p<n)个位置，即将R中的数据由(X0,X1,…,Xn-1)变换为(Xp,Xp+t,…,Xn-1，X0,X1,…,Xp-1)。要求:
1)给出算法的基本设计思想。
2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度和空间复杂度。
