500强网站建设,微网站与微信公众号,定制app开发 杭州app开发公司,上海专业做网站公司地址文章目录 主要内容一.基础练习题1.从顺序表中删除具有最小值的元素#xff08;假设唯一#xff09;并由函数返回被删元素的值。空出位置由最后元素填补#xff0c;若顺序表为空#xff0c;则显示出错信息并退出运行。代码如下#xff08;示例#xff09;: 2.设计一个高效… 文章目录 主要内容一.基础练习题1.从顺序表中删除具有最小值的元素假设唯一并由函数返回被删元素的值。空出位置由最后元素填补若顺序表为空则显示出错信息并退出运行。代码如下示例: 2.设计一个高效算法将顺序表L的所有元素逆置要求算法的空间复杂度为O1。代码如下示例: 3.将两个有序顺序表合并为一个新的有序顺序表并由函数返回结果顺序表。代码如下示例: 4.已知在一维数组A[mn]中依次存放两个线性表a1,a2,....,am和b1,b2,...bn.编写一个函数将数组中两个顺序表的位置互换即将b1,b2,...bn放在a1,a2,...am的前面。代码如下示例: 5.设将n(n1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(Opn)个位置即将R中的数据由(X0,X1,..,Xn-1)变换为(Xp,Xp1,..Xn-1,X0,X1,...Xp-1)。代码如下示例: 总结 主要内容
顺序表基础练习题
一.基础练习题 1.从顺序表中删除具有最小值的元素假设唯一并由函数返回被删元素的值。空出位置由最后元素填补若顺序表为空则显示出错信息并退出运行。
代码如下示例:
算法思想搜索整个顺序表查找最小元素并记住其位置搜索结束后用最后一个元素填补空出的原最小值元素的位置。bool Del_Min(sqList L,ElemType value){
//删除顺序表L中最小元素结点并通过引用型参数value返回其值
//若删除成功则返回true否则返回falseif(L.length0)return false; //表空中止操作返回valueL.data[0];int pos0; //假定0号元素的值最小for(int i1;iL.length;i) //循环寻找具有最小值的元素if(L.data[i]value){ //让value记忆当前具有最小值的元素valueL.data[i];posei;}L.data[pos]L.data[L.length-1]; //空出的位置由最后一个元素提填补L.length--;return true; //此时value即为最小值
}2.设计一个高效算法将顺序表L的所有元素逆置要求算法的空间复杂度为O1。
代码如下示例:
算法思想扫描顺序表L的前半部分元素对于元素L.data[i](0iL.length/2),
将其与后半部分的对应元素L.data[L.length-i-1]进行交换。void Reverse(Sqlist L){Elemtype temp; //辅助变量for(i0;iL.length/2;i){tempL.data[i]; //交换L.data[i]与L.data[L.length-i-1]L.data[i]L.data[L.length-i-1];L.data[L.length-i-1]temp;}
}3.将两个有序顺序表合并为一个新的有序顺序表并由函数返回结果顺序表。
代码如下示例:
算法思想首先按顺序不断取下两个顺序表表头较小的节点存入新的顺序表中。
然后看哪个表还有剩余将剩下的部分加到新的顺序表后面。bool Merge(SeqList A,SeqList B,SeqList C){
//将有序顺序表A和B合并为一个新的有序顺序表Cif(A.lengthB.lengthC.maxSize) //大于顺序表的最大长度return false;int i0,j0,k0;while(iA.lengthj.B.length){if(A.data[i]B.data[j])C.data[k]A.data[i];elseC.data[k]B.data[j];}while(iA.length) //还剩一个没有比较完的顺序表C.data[k]A.data[i];while(jB.length)C.data[k]B.data[j];C.lengthk;return true;
}4.已知在一维数组A[mn]中依次存放两个线性表a1,a2,…,am和b1,b2,…bn.编写一个函数将数组中两个顺序表的位置互换即将b1,b2,…bn放在a1,a2,…am的前面。
代码如下示例:
算法思想先将数组A[mn]中的全部元素a1,a2,...am,b1,b2,...bn原地逆置为bn,bn-1,...b1,am,am-1,..a1,
再对前n个元素和后m个元素分别使用逆置算法即可得到b1,b2,..bn,a1,a2,...am,从而实现顺序表的位置互换。typedef int DataType;void Reverse(DataType A[],int left,int right,int arraySize){if(leftright || rightarraySize)return;int mid(leftright)/2;for(i0;imid-left;i){DataType tempA[lefti];A[lefti]A[right-i];A[right-i]temp;}
}
void Exchange(DataType A[],int m,int n,int araySize){Reverse(A,0,mn-1,arraySize);Reverse(A,0,n-1,arraySize);Reverse(A,n,mn-1,arraySize);
}5.设将n(n1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(Opn)个位置即将R中的数据由(X0,X1,…,Xn-1)变换为(Xp,Xp1,…Xn-1,X0,X1,…Xp-1)。
要求:1) 给出算法的基本设计思想。 2)根据设计思想采用 C或 C或 Java 语言描述算法关键之处给出注释 3) 说明你所设计算法的时间复杂度和空间复杂度
代码如下示例:
算法思想可将这个问题视为把数组 ab 转换成数组 ba(a代表数组的前p 个元素b代表数组中余下的n-p个元素)
先将a逆置得到a^(-1)b再将b逆置得到a^(-1)b^(-1最后将整个a逆置得到(a^(-1)b^(-1)^-1 ba。
设 Reverse 函数执行将数组元素逆置的操作对abcdefgh 向左循环移动3(p3)个位置的过程如下:
Reverse(0p-1)得到 cbadefgh:
Reverse(pn-1)得到 cbahgfed;
Reverse(0,n-1)得到defghabc;
注:Reverse 中两个参数分别表示数组中待转换元素的始末位置。void Reverse(int R[],int from,int to){int i,temp;for(i0;i(to-from1)/2;i){tempR[fromi];R[fromi]R[to-i];R[to-i]temp;}
} //Reverse
void Converse(int R[],int n,int p){Reverse(R,0,p-1Reverse(R,p,n-1Reverse(R,0,n-1
}上述算法中三个Reverse函数的时间复杂度分别为 O(p/2)、O((n-p)/2)和 0(n/2)
故所设计的算法的时间复杂度为 O(n)空间复杂度为 O(1)。
另解借助辅助数组来实现。
算法思想:创建大小为p的辅助数组 S将R中前p 个整数依次暂存在 S中同时将 R中后 n-p 个整数左移
然后将 S中暂存的p个数依次放回到R中的后续单元。时间复杂度为 O(n)空间复杂度为 O(p)。总结
以上是今天要讲的内容练习了一些线性表–顺序表的习题。
