数据结构——顺序表（基础代码题）
一、顺序表
1.对顺序表L 进行遍历并输出每个数据元素的数据值。
(改变结构就用引用，简单的就用值传递)
void ListVisit(SqList L){for (int k=0;k<L.length;k++)printf("%d",L.data[k]);
}
2.假设有一个顺序表i，其存储的所有数据元素均为不重复的正数，查找L 中值为e的数据元素，若找到则返回其下标，若找不到则返回-1。
int Search_e(SqList L,int e){for(int k=0;k<L.length;k++)if(L.data[k]==e)return k;return -1;
}
3.假设有一个顺序表L，其存储的所有数据元素均为正数，查找L中第i个数据元素并返回其值。
int Get_i(SqList L,int i){if(i>=1&&i<L.length)return L.data[i-1];return -1; //范围越界
}
4.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。
void Reverse(SqList &L){ //由1234改变成4321结构发生变化，使用引用符int temp;for(int i=0;i<L.length/2;i++) {//length/2=2.5计算机会自动抹去0.5temp=L.data[i];L.data[i]=L.data[L.length-i-1];L.data[L.length-i-1]=temp;}}
5.在顺序表L的第i个位置插入新元素e，若i的输入不合法，则返回false，表示插入失败；否则，将第i个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。
bool Insert_e(SqList &L, int e,int i){//合法性判断if(i<1||i>L.length+1)return false;//顺序表存满判断if(L.length==MaxSize)return false;for(int j=L.length;j>=i;j--)L.data[j]=L.data[i-1];L.data[i-1]=e; //第i个位置的下标要-1L.length++;return true;
}
6.已知一个顺序表L，其中的元素递增有序排列，设计一个算法，插入一个元素X（X为int型）后保持该顺序表仍然递增有序排列，假设插入操作肯定成功，插入成功后返回插入元素所在位置。
//假设插入操作肯定成功，则不需要情况判断
int ListInsert(SqList &L,int x){for(int i) //i因为要返回数值，故不能在for循环里定义，因为for循环完之后会自动消失，所以要把i定义在循环之外int i;for(i=0;i<L.length;i++)if(L.data[i]>x)break;//得到插入元素的位置for(int j=L.length;j>=i+1;j--)L.data[j]=L.data[j-1];L.data[i]=x; //插入元素L.length++;return i;
}bool ListDelete(SqList &L,int i,int &e){if(i<1||i>L.length) //不合法判断return false;e=L.data[i-1]; //被删除的元素赋值给变量efor(int j=i;j<L.length;j++)L.data[j-1]=L.data[j]; //将之后的元素依次往前移动L.length--;return true;}
8.从顺序表中删除具有最小值的元素并由函数返回被删元素的值。（假设顺序表中的数据元素全为正值且最小值唯一）。
int Delete_Min(SqList &L){if(L.length==0)return -1; //空表，出现错误int min=L.data[0],pos=0;for(int i=1;i<L.length;i++)if(L.data[i]<min){min=L.data[i];pos=i;//找到顺序表中的最小值}for(int j=pos;j<L.length-1;j++)L.data[j]=L.data[j+1];//前移表中的数据元素L.length--; //顺序表长度减一return min; //返回最小值
}
9.对长度为n的顺序表L，编写一个时间复杂度O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
//方法一
void Delete_x_1(SqList &L,int x){int k=0; // 定义删除x的个数for(int i=0;i<L.length;i++){if(L.data[i]==x)k++;elseL.data[i-k]=L.data[i];}L.length=L.length-k;
}
//方法二
void Delete_x_1(SqList &L,int x){int j=0;for(int i=0;i<L.length;i++){if(L.data[i]!=x){L.data[j]=L.data[i];j++;}}L.length=j;
}
10.从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则返回false，若执行成功则返回true。
//方法一
bool Del_s_t_1(SqList &L,int s ,int t){if(s>=t||L.length==0)return false;int k=0;for(int i=0;i<L.length;i++){if(L.data[i]>=s&&L.data[i]<=t)k++;elseL.data[i-k]=L.data[i];}L.length=L.length-k;return true;
}
//方法二
bool Del_s_t_2(SqList &L,int s ,int t){if(s>=t||L.length==0)return false;int j=0;for(int i=0;i<L.length;i++){if(L.data[i]<s||L.data[i]>t){ //判断元素是否保留L.data[j]=L.data[i];j++;}}L.length=j;return true;
}
11.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
void Del_Same(SqList &L){int j=1; //定义一个变量作为保留元素的位置，判断元素保留不保留要求从第二个元素进行比较，下标为0的元素肯定保留for(int i=1;i<L.length;i++)if(L.data[i]!=L.data[j-1]){L.data[j]=L.data[i];j++;}L.length=j;
}
12.从【有序】顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则返回false，执行成功则返回true。
难题
//自己写的，不是太正确
bool Delete_s_t(SqList &L,int s,int t){if(s>=t||L.length==0)return false;int k=0;for(int i=0;i<L.length;i++){if(L.data[i]>=s&&L.data[i]<=t)k++; L.data[i-k]=L.data[i];}L.length=L.length-k;return true;
}
//正确答案P20，解题思路：连续的空间，给出一个排队的位置（需要删除的元素的位置），看看哪些元素需要保留，然后在排队位置上进行保留，然后更新排队位置。
bool Delete_s_t(SqList &L,int s,int t){if(s>=t||L.length==0)return false;int i,j;for(j=0;j<L.length&&L.data[j]<s;j++);//找出大于s元素的位置if(j=L.length)return false;for(i=j;i<L.length&&L.data[i]<=t;j++);//找到小于t元素的位置for(;i<L.length;i++,j++) //循环顺序表L.data[j]=L.data[i]; L.length=j;return true;
}
13.将两个有序顺序表A和B合并为一个新的有序顺序表C，若合并成功则返回true，合并失败则返回false。
bool Merge(SqList A,SqList B,SqList &C){if(A.length+B.length>C.Maxsize)return false; //判断顺序表A和B的长度没有超过C的int i=0,j=0,k=0;while(i<A.length&&j<B.length){ //比较两个表内元素的大小if(A.data[i]<=B.data[j]){C.data[k]=A.data[i];k++;i++;}else{C.data[k]=B.data[j];k++;j++;} }//存在一个表有剩余while(i<A.length){C.data[k]=A.data[i];k++;i++;}while(i<A.length){C.data[k]=B.data[j];k++;j++;}C.length=k;return true;}