顺序表的构造算法设计 数据结构 2.6 顺序表中元素互换示例算法（一）

数据结构 2.6 顺序表中元素互换示例算法（一）  

　　希赛教育计算机专业考研专业课辅导招生

　　希赛教育计算机专业考研专业课辅导视频

　　希赛教育计算机考研专业课在线测试系统

　　试设计一个算法 用尽可能少的辅助空间将顺序表中前m个元素和后n个元素进行互换 即将线性表(a a … am b b … bn) 改变成(b b … bn a a … am)

　　此题的难点在于要求用尽可能少的辅助空间 如果没有这个限制 可以另设一个和已知顺序表空间大小相同的顺序表 然后进行元素复制即可

　　此题的一种比较简单的算法是 从表中第m+ 个元素起依次插入到元素a 之前 则首先需将该元素bk(k= … n)暂存在一个辅助变量中 然后将它之前的m个元素(a a … am)依次后移一个位置 显然 由于对每一个bk都需要移动m个元素 因此算法的时间复杂度为O(m×n)