《数据结构(C语言版)严尉敏编第5章.ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版)严尉敏编第5章.ppt（95页珍藏版）》请在三一办公上搜索。
1、5.1 数组的类型定义,由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：,(a),typedef Elemtype array2mn;等价于：typedef Elemtype array1n;typedef array1 array2m;,一般地：多维数组的定义如下页所示：,ADT Array 数据对象：Daj1,j2,.,ji,jn|ji=0,.,bi-1,i=1,2,.,n 数据关系：RR1,R2,.,Rn Ri|0 jk bk-1,1 k n 且k i,0 ji bi-2,i=2,
2、.,n 基本操作:ADT Array,InitArray(&A,n,bound1,.,boundn)操作结果：若维数 n 和各维长度合法，构造相应的数组A，并返回OK。,DestroyArray(&A)操作结果：销毁数组A。,Value(A,&e,index1,.,indexn)初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。,Assign(&A,e,index1,.,indexn)初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。,二维数组
3、的抽象定义:,数据对象:D=aij|0ib1-1,0 jb2-1数据关系:R=ROW,COL ROW=|0ib1-2,0jb2-1COL=|0ib1-1,0 jb2-2,5.2 数组的顺序表示和实现,类型特点:1）数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。2）数组是多维的结构，而存储空间是一个一维的结构。,有两种顺序映象的方式:1)以行序为主序(低下标优先);/我们所选择的2)以列序为主序(高下标优先);,以“行序为主序”的存储映象,二维数组A中任一元素aij 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)L,
4、称为基地址或基址,每个元素占L个存储单元,已经存储的元素个数,如果有：int a1020;则有：loc(7,13)=loc(0,0)+(20*7+13)*sizeof(int);如果有：int b768;则有：loc(4，5，6)=loc(0,0,0)+(6*8*4+8*5+6)*sizeof(int);,推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系：,其中 cn=L，ci-1=bi ci,1 i n。,称为 n 维数组的映象函数。数组元素的存储位置是其下标的线性函数,容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，ci 是常数。由于计算各个元素存储
5、位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。,下面是数组顺序存储表示和实现,/-数组顺序存储表示-#includestdarg.h/标准头文件,提供一个类型va_list,三个宏va_start/va_arg 和va_end 的定义,其中va_list为字符指针类型#define MAX_ARRAY_DIM 8/假设数组的最大维数typedef struct ElemType*base;/存储数组元素的首地址(基址),由InitArray分配 int dim;/数组的维数 int*bounds;/存放数组维界的基地址,由InitArray分配
6、 int*constants;/存放映象函数常量基址,由InitArray分配 Array;,Status InitArray(Array,/-基本操作的实现算法-,if(A.boundsi=0;i-)A.constantsi=A.boundsi+1*A.constantsi+1;return OK;/InitArray,Status DestroyArray(Array/DestroyArray,Status Locate(Array A,va_list ap,int&off)/若ap所指下标合法,则求出元素在数组中的相对位置off/最终off带回在存储该元素时已经存储的元素个数,off=0
7、;for(i=0;i=A.boundsi)return(OVERFLOW);off+=A.constantsi*ind;return OK;/Locate,Status Assign(Array&A,ElemType e,),Status Value(Array A,ElemType&e,),Status Value(Array A,ElemType&e,)/如果用VC实现,/A是一数组，e为一元素变量，随后是n 个下标值。/A和e换顺序/若各下标不超界，则e赋值为所指定的A 的元素值，并返回OK。va_start(ap,e);/va_start(ap,A)if(result=Locate(A
8、,ap,off)=0)return result;e=*(A.base+off);return OK;/Value,Status Assign(Array&A,ElemType e,),va_start(ap,e);if(result=Locate(A,ap,off)=0)return result;*(A.base+off)=e;return OK;/Assign,5.3 矩阵的压缩存储,特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质：aij=aji 1i,jn则称A为对称矩阵。如下页
9、图便是一个5阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括,对角线）以下的元素，其存储形式如图所示：,1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1.7 0 6 1 3 an1 a n2 an3 a nn,在这个下三角矩阵中，第i行恰有i个元素，元素总数为：n(n+1)/2 因此，我们可以按从上到下、从左到右将这些元素存放在一个向量sa0.n(n+1)/2-1
10、中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak之间找一个对应关系。,若ij，则aij在下三角形中。aij之前的i-1行共有1+2+i-1=i(i-1)/2个元素，在第i行上，aij之前有j-1个元素（即ai1,ai2,ai3,aij-1），因此有：,2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图a所示，它的下三角（不包括主对角线）中的元素均为常数c。下三角矩阵正好相反，它的主对角线上方均为常数c，如图b所示。在大多数情况下，三角矩阵常数为零。,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量s
11、a0.n(n+1)/2中，其中c存放在向量的最后一个分量中。上三角矩阵中，主对角线之上的第i行(0i n)恰有n-i个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的i行一共有i(2n-i+1)/2个元素，在第i行上，aij前恰好有j-i个元素：aii,aii+1,aij-1。因此，sak和aij的对应关系是：,下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是：i(i+1)/2+j ij n(n+1)/2 ij 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了
12、一个三对角矩阵，a00 a01 a10 a11 a12 a21 a22 a23.可用以行序为主序的 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 形式存储 图5.3 对角矩阵,k=,通常认为 0.05 的矩阵为稀疏矩阵。稀疏矩阵的压缩存储方法:三元组表示法/三元组为：（行，列，值）,什么是稀疏矩阵？简单说，设矩阵A中有t个非零元素，若t远远小于矩阵元素的总数（即tmn），则称A为稀疏矩阵。,5.3.2 稀疏矩阵,定义稀疏因子:,例如，下列三元组表(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),
13、(6,1,15),(6,4,-7),转置,加上行数6和列数7便可作为矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。,#define MAXSIZE 12500/非零元素最大个数 typedef struct int i,j;/该非零元的行下标和列下标 ElemType e;/该非零元的值 Triple;/三元组类型,1.三元组顺序表,typedef struct Triple dataMAXSIZE+1;/非零元三元组表中0号单元未用 int mu,nu,tu;/行、列及非零元个数 TSMatrix;/稀疏矩阵类型,方法1：,转置后得T,Status Tr
14、ansposeSMattrix(TSMatrix M,TSMatrix/TransposeSMattrix其时间复杂度为:O(M.nuM.tu)，若 M.tu 与M.muM.nu同数量级 时，有O(M.mu M.nu2),方法二：快速转置 其基本思想是对M.data仅扫描一遍，在扫描到每一个元素时将其放在T.data的合适的位置上。,cpot1=1;cpotcol=cpotcol-1+numcol-1;(2col M.nu),方法2（快速转置）：,转置后得T,T.mu=7T.nu=6T.tu=8,2 1 12,3 1 9,1 3-3,6 3 14,3 4 24,2 5 18,1 6 15,4
15、6-7,12345678,4,6,2,9,7,5,3,8,1）根据M的mu、nu和tu 的值，对T的mu、nu和tu赋 相应的值；2）初始化数组num;3）扫描M.data，计算num的值；4）根据num的值，计算cpot的值；5）扫描M.data一遍，将非零元放在T.data的合适 的位置上。算法描述如下页所示：,Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵的转置矩阵T,T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;,if(T.tu)for(col=1;col=M.nu;col+)numc
16、ol=0;/0号单元不用,for(t=1;col=M.tu;t+)+numM.datat.j;,cpot1=1;/求第col列中第一个非零元在T.data中的序号 for(col=2;col=M.nu;col+)cpotcol=cpotcol-1+numcol-1;,for(t=1;t=M.tu;t+)col=M.datat.j;q=cpotcol;T.dataq.i=M.datat.j;T.dataq.j=M.datat.i;T.dataq.e=M.datat.e;+cpotcol;return OK;/FastTransposeSMatrix 时间复杂度为：,分析算法FastTranspo
17、seSMatrix的时间复杂度：,时间复杂度为:O(M.nu+M.tu),for(col=1;col=M.nu;+col)for(t=1;t=M.tu;+t)for(col=2;col=M.nu;+col)for(p=1;p=M.tu;+p),三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。,2.行逻辑链接的顺序表,typedef struct Triple dataMAXSIZE+1;/非零元三元组表 int rposMAXRC+1;/各行第一个非零元的位置表 int mu,
18、nu,tu;RLSMatrix;/行逻辑链接顺序表类型,在行逻辑链接的顺序表表示稀疏矩阵时，一些操作的实现。,（1）取值运算，给定一组下标，求矩阵的元素值,void value(RLSMatrix M,int r,int c,ElemType/value,for(i=1;i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(k=1;k=n1;+k)Qij+=Mik*Nkj;,其时间复杂度为:O(m1n2n1),(2)矩阵乘法运算:,2.1 精典乘法运算算法：,M、N和Q的三元组表示分别如下：,Qij=,Q初始化;if Q是非零矩阵/逐行求积 for(arow=1;arow=M.m
19、u;+arow)/处理M的每一行 ctemp=0;/累加器清零 计算Q中第arow行的积并存入ctemp 中；将ctemp 中非零元压缩存储到Q.data；/for arow/if,基本思想：,Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix/MultSMatrix,ctemp=0;/当前行各元素累加器清零 Q.rposarow=Q.tu+1;/Q的第arow行在Q.data中的位置 if(arow M.mu)tp=M.rposarow+1;else tp=M.tu+1 for(p=M.rposarow;ptp;+p)/对当前行中每一个非
20、零元给它该乘的元素乘一遍 brow=M.datap.j;if(brow N.mu)t=N.rposbrow+1;else t=N.tu+1/t为本行最后一个非零元的下一位 for(q=N.rposbrow;q t;+q)ccol=N.dataq.j;/乘积元素在Q中列号 ctempccol+=M.datap.e*N.dataq.e;/for q,/求得Q中第crow(=arow)行的非零元for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu=（arow,ccol,ctempccol）;/if,分析上述算法的时间复杂度,累加器ctemp初始化的时间复杂度
21、为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是(M.muN.nu+M.tuN.tu/N.mu)。,若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数 M.tu=Mmn，N中非零元的个数 N.tu=Nnp，相乘算法的时间复杂度就是(mp(1+nMN)，当M0.05 和N0.05及 n 1000时，相乘算法的时间复杂度就相当于(mp)。,思考：如果两个稀疏矩阵M和N是可乘的，且M和N都以行逻辑链接的三元组顺序表进行存储，编写一个类-C算法，求这两个矩阵的相乘积Q，Q以二维数组
22、的形式存储（即Q不进行压缩）。,/-稀疏矩阵的十字链表存储表示-typedef struct OLNode int i,j;Elemtype e;struct OLNode*right,*down;OLNode,*OLink;typedef struct OLink*rhead,*chead;/行和列链表头指针向量基址 int mu,nu,tu;CrossList,3.十字链表,3.1 创建一个稀疏矩阵的十字链表存储结构基本思想:创建一个稀疏矩阵M的十字链表存储结构的过程就是给M的5个域赋确切值的过程。1）输入M的行m、列n和非零元的个数t；2）申请存储行、列链表头指针的存储空间；3）建立m+
23、n个空链表；4）输入一个非零元的(行，列，值）；5）产生一个结点p；并给其i,j,e赋相应值；6）将p插在相应行的适当位置上；7）将p插在相应列的适当位置上；8）重复4）、5）、6）、7）步，直到非零元输入完为止。,Status CreatMatrix_OL(CrossList scanf(&i,&j,&e)/按任意次序输入非零元；,if(!(p=(OLNode*)malloc(sizeof(OLNode)exit(OVERFLOWER);p-i=i;p-j=j;p-e=e;/生成结点if(M.rheadi=NULL|M.rheadi-jj)/插在表头p-right=M.rheadi;M.rh
24、eadi=p;else/将p插在合适的位置上for(q=M.rheadi;q-right else/将p插在合适的位置上,for(q=M.cheadj;q-down/CreatMatrix_OL,3.2 十字链表存储时两矩阵相加运算算法void addMatrix(CrossList,if(k)pa-e=k;pre=pa;pa=pa-right;pb=pb-right;else 在相应的行、列中，删除pa所指结点；pa、pb后 移；break;/switch/while/for/addMatrix,5.4 广义表的定义,ADT Glist 数据对象：Dei|i=1,2,.,n;n0;eiAto
25、mSet 或 eiGList,AtomSet为某个数据对象 数据关系：R1|ei-1,eiD,2in 基本操作:P107 12 种基本操作 ADT Glist,(a,(b,c),(d,(e,f),g),(3,(2,4),(6,(4,6),12),InitGList(,广义表是递归定义的线性结构，可以形式的写为：,LS=(1,2,n)其中：i或为原子或为广义表,例如:A=()B=(e)C=(a,(b,c,d)D=(A,B,C)E=(a,E)相当于一个无限的列表(a,(a,(a,),基本概念：原子、子表、表长、空表、表头、表尾、表的深度,广义表是一个多层次的线性结构,例如：D=(A,B,C),任何
26、一个非空广义表 LS=(1,2,n)均可分解为表头 Head(LS)=1和表尾 Tail(LS)=(2,n)两部分例如：F=(a,b),c,(d)Head(F)=(a,b)Tail(F)=(c,(d)Head(Head(F)=a;Tail(Head(F)=(b),5.5 广义表的存储结构,1)通常采用头、尾指针的链表结构,LS=(a,(b,c),d),Head(LS)=a;Tail(LS)=(b,c),d),/-广义表的头尾链表存储表示-typedef enum ATOM,LIST ElemTag;/元素的标志类型typedef struct GLNode ElemTag tag;/公共部分，
27、用于区分原子结点和表结点 union/atom是原子结点的值域，AtomType 由用户定义 AtomType atom;struct struct GLNode*hp,*tp;ptr;/ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾*Glist;/广义表类型,空表 LS=NULL,A=()B=(e)C=(a,(b,c,d)D=(A,B,C),B,C,D,ls=(a,(),(b,c),d),2）广义表的扩展线性链表存储结构,typedef enum ATOM,LIST ElemTag;/typedef struct GLNode ElemTag tag;/公共部分，用于区
28、分原子结点和表结点 union AtomType atom;/atom是原子结点的值域 struct GLNode*hp;/表结点的表头指针 struct GLNode*tp;/相当于线性链表的next，指向下一个/元素结点*Glist;/广义表类型,A=()B=(e)C=(a,(b,c,d)D=(A,B,C),5.6 m元多项式的表示：P 110-112 自学！,5.7 广义表的递归算法,递归函数 一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件:,1)在每一次调用自己时，必须是(在某种意义上)更接近于解;,2)必须有一个终止处理或计算的准则。,例如:梵塔的递归函
29、数,void hanoi(int n,char x,char y,char z)if(n=1)move(x,1,z);else hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);/hanoi,求阶乘算法：n!=n*(n-1)!,int fact(int n)if(n=0)return 1;else return n*fact(n-1);/fact,求大小为n的整型数组A中的最大值。int MAX(int*A,int n)if(n=1)return A0;else y=MAX(A,n-1);return(An-1y?An-1:y);/MAX,对于一个输入
30、规模为 n 的函数或问题，用某种方法把输入分割成 k(1kn)个子集，从而产生 l 个子问题，分别求解这 l 个问题，得出 l 个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。,分治法的设计思想为:,在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解,例如:焚塔问题:Hanoi(n,x,y,z),将 n 个盘分成两个子集(1至n-1 和 n)，从而产生下列三个子问题:,1)将1至n-1号盘从 x 轴移动至 y 轴;,3)将1至n-1号盘从y轴移动至z轴;,2)将 n号盘从
31、 x 轴移动至 z 轴;,广义表从结构上可以分解成：,广义表=表头+表尾,或者,广义表=子表1+子表2+子表n,因此常利用分治法求解之。算法设计中的关键问题是，如何将 l 个子问题的解组合成原问题的解。,广义表的头、尾链表存储表示：,typedef enum ATOM,LIST ElemTag;/ATOM=0:原子,LIST=1:子表typedef struct GLNode ElemTag tag;/标志域 union AtomType atom;/原子结点的数据域 struct struct GLNode*hp,*tp;ptr;*GList,例一 求广义表的深度,例二 复制广义表,例三 创
32、建广义表的存储结构,例1:求广义表的深度,设广义表LS为：LS=(1,2,n)则LS的深度定义为：0 当LS为原子时DEPTH（LS）=1 当LS为空表时 1+Max DEPTH（i）n1 1in,在按数学式子写递归算法时，一定不要怀疑它的正确性！,int GlistDepth(Glist L)/返回指针L所指的广义表的深度 for(max=0,pp=L;pp;pp=pp-ptr.tp)dep=GlistDepth(pp-ptr.hp);if(dep max)max=dep;return max+1;/GlistDepth,if(!L)return 1;/L为空表if(L-tag=ATOM)r
33、eturn 0;,for(max=0,pp=L;pp;pp=pp-ptr.tp)dep=GlistDepth(pp-ptr.hp);if(dep max)max=dep;,例如:,pp,pp-ptr.hp,pp,pp,pp-ptr.hp,pp-ptr.hp,例2 复制广义表,新的广义表由新的表头和表尾构成。,可以直接求解的两种简单情况为:空表复制求得的新表自然也是空表;原子结点可以直接复制求得。,将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，,若 LS=NULL 则 NEWLS=NULL否则 产生结点 NEWLS 和LS相同，即若LS为元素结点，则直接将LS的值赋给NEW
34、LS，否则为表结点，则完成下列工作：将表头LS-ptr.hp 复制到NEWLS-ptr.hp 将表尾 LS-ptr.tp 复制到NEWLS-ptr.tp,复制求广义表的算法描述如下:,Status CopyGList(GList/CopyGList,分别复制表头和表尾,CopyGList(T-ptr.hp,L-ptr.hp);/复制求得表头T-ptr.hp的一个副本L-ptr.hpCopyGList(T-ptr.tp,L-ptr.tp);/复制求得表尾T-ptr.tp 的一个副本L-ptr.tp,例3 创建广义表的存储结构P115-117,对应广义表的不同存储结构，相应地有不同的创建存储结构的
35、算法。,自学！,假设以字符串 S=(1,2,n)的形式定义广义表 L，建立相应的存储结构。,由于S中的每个子串i定义 L 的一个子表，从而产生 n 个子问题，即分别由这 n个子串(递归)建立 n 个子表，再组合成一个广义表。,可以直接求解的两种简单情况为:由串()建立的广义表是空表;由单字符建立的子表只有一个原子结点。,如何由子表组合成一个广义表？,首先分析广义表和子表在存储结构中的关系。,先看第一个子表和广义表的关系:,指向广义表的头指针,指向第一个子表的头指针,再看相邻两个子表之间的关系:,指向第i+1个子表的头指针,指向第i个子表的头指针,可见，两者之间通过表结点相链接。,若 S=()则
36、 L=NULL,否则 构造第一个表结点*L,并从串 S 中分解出第一个子串 1,对应创建第一个子广义表 L-ptr.hp;,若剩余串非空，则构造第二个表结点 L-ptr.tp,并从串 S 中分解出第二个子串 2,对应建第二个子广义表;,依次类推，直至剩余串为空串止。,Status CreateGList(Glist/CreateGList,由sub中所含n个子串建立n个子表;,do sever(sub,hsub);/从sub中分离出表头串hsub CreateGList(p-ptr.ph,hsub);q=p;/创建由串hsub定义的广义表p-ptr.hp;if(!StrEmpty(sub)if
37、(!(p=GList)malloc(sizeof(GLNode)exit(OVERFLOW);/建下一个子表的表结点*(p-ptr.tp)p-tag=LIST;q-ptr.tp=p;/if while(!StrEmpty(sub);q-ptr.tp=NULL;/表尾为空表/else,本章小结：1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。,4.掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握
38、任意一种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。5.学习利用分治法的算法设计思想编制递归算法的方法。,习题五1.写在书上的作业：5.1 5.2 5.3 5.10 5.11 5.12 5.13 5.15 5.17 2.要交作业 5.18 5.19 5.213.上机作业：利用稀疏矩阵的三元组压缩存储、实现压缩存储时的矩阵相加和相乘运算；,void Right_Move_K(ElemType A,int n,int k)/将大小为n的数组A中的元素循环右移k位 for(i=0,j=n-1；ij;i+,-j)Ai Aj;/逆置 for(i=0,j=k-1；ij;i+,-j)Ai Aj;/前k个逆置 for(i=k,j=n-1；ij;i+,-j)Ai Aj;/后n-k个逆置/Right_Move_K 该算法的时间复杂度为O（n）,也满足题的要求,5.18 试设计一个算法，将数组An中的元素A0至An-1循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)。,
