资源描述
.第3章 栈和队列习题1选择题1若让元素1,2,3,4,5依次进栈,则出栈次序不可能出现在 种情况。A5,4,3,2,1 B2,1,5,4,3 C4,3,1,2,5 D2,3,5,4,12若已知一个栈的入栈序列是1,2,3,n,其输出序列为p1,p2,p3,pn,若p1=n,则pi为 。 Ai Bn-i Cn-i+1 D不确定3数组用来表示一个循环队列,为当前队列头元素的前一位置,为队尾元素的位置,假定队列中元素的个数小于,计算队列中元素个数的公式为 。Ar-f B%n Cn+r-f Dn+r-f%n4链式栈结点为：,top指向栈顶.若想摘除栈顶结点,并将删除结点的值保存到x中,则应执行操作。Ax=top-data;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；5设有一个递归算法如下 int fact /n大于等于0 ifn return 1; else return n*fact; 则计算fact需要调用该函数的次数为。An+1Bn-1C nD n+26栈在中有所应用。A递归调用B函数调用C表达式求值D前三个选项都有7为解决计算机主机与打印机间速度不匹配问题,通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是。A队列 B栈 C 线性表 D有序表8设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依次进入栈S,一个元素出栈后即进入Q,若6个元素出队的序列是e2、e4、e3、e6、e5和e1,则栈S的容量至少应该是。A2 B3 C4 D 69在一个具有n个单元的顺序栈中,假设以地址高端作为栈底,以top作为栈顶指针,则当作进栈处理时,top的变化为。 Atop不变 Btop=0 Ctop- Dtop+10设计一个判别表达式中左,右括号是否配对出现的算法,采用数据结构最佳。A线性表的顺序存储结构B队列C. 线性表的链式存储结构 D. 栈11用链接方式存储的队列,在进行删除运算时。A. 仅修改头指针 B. 仅修改尾指针C. 头、尾指针都要修改 D. 头、尾指针可能都要修改12循环队列存储在数组A0.m中,则入队时的操作为。A. rear=rear+1 B. rear=% C. rear=%m D. rear=% 13最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是。 A. %n=front B. rear=front Crear+1=front D. %n=front14栈和队列的共同点是。A. 都是先进先出 B. 都是先进后出C. 只允许在端点处插入和删除元素 D. 没有共同点15一个递归算法必须包括。A. 递归部分B. 终止条件和递归部分C. 迭代部分 D. 终止条件和迭代部分2回文是指正读反读均相同的字符序列,如abba和abdba均是回文,但good不是回文。试写一个算法判定给定的字符向量是否为回文。根据提示,算法可设计为：/以下为顺序栈的存储结构定义#define StackSize 100 /假定预分配的栈空间最多为100个元素typedef char DataType;/假定栈元素的数据类型为字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen/判断t字符向量是否为回文,若是,返回1,否则返回0SeqStack s;int i , len;char temp;InitStack;len=strlen; /求向量长度for i=0; i/将一半字符入栈Push;while !EmptyStack/ 每弹出一个字符与相应字符比较temp=Pop ;if return 0 ;/ 不等则返回0else i+;return 1 ; / 比较完毕均相等则返回 13设从键盘输入一整数的序列：a1, a2, a3,an,试编写算法实现：用栈结构存储输入的整数,当ai-1时,将ai进栈；当ai=-1时,输出栈顶整数并出栈。算法应对异常情况入栈满等给出相应的信息。#define maxsize 栈空间容量void InOutS /s是元素为整数的栈,本算法进行入栈和退栈操作。 int top=0; /top为栈顶指针,定义top=0时为栈空。fori=1; i /n个整数序列作处理。 scanf; /从键盘读入整数序列。if / 读入的整数不等于-1时入栈。ifprintf;exit;else s+top=x; /x入栈。else /读入的整数等于-1时退栈。 ifprintf;exit; else printf； /算法结束。4从键盘上输入一个后缀表达式,试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行,以$符作为输入结束,操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。 题目分析逆波兰表达式求值规则如下：设立运算数栈OPND,对表达式从左到右扫描,当表达式中扫描到数时,压入OPND栈。当扫描到运算符时,从OPND退出两个数,进行相应运算,结果再压入OPND栈。这个过程一直进行到读出表达式结束符$,这时OPND栈中只有一个数,就是结果。float expr/从键盘输入逆波兰表达式,以$表示输入结束,本算法求逆波兰式表达式的值。float OPND30; / OPND是操作数栈。init; /两栈初始化。float num=0.0; /数字初始化。 scanf ;/x是字符型变量。while switch case0=x=9:while=0&x|x=. /拼数if /处理整数num=num*10+ord-ord; scanf;else /处理小数部分。 scale=10.0; scanf;while=0&x num=num+ord-ord/scale; scale=scale*10; scanf; /else push; num=0.0;/数压入栈,下个数初始化case x= :break; /遇空格,继续读下一个字符。case x=+:pushOPND,pop+pop;break;case x=-:x1=pop;x2=pop;push;break;case x=*:pushOPND,pop*pop;break;case x=/:x1=pop;x2=pop;push;break;default: /其它符号不作处理。 /结束switch scanf;/读入表达式中下一个字符。 /结束whilex！=$ printf后缀表达式的值为%f,pop;/算法结束。算法讨论假设输入的后缀表达式是正确的,未作错误检查。算法中拼数部分是核心。若遇到大于等于0且小于等于9的字符,认为是数。这种字符的序号减去字符0的序号得出数。对于整数,每读入一个数字字符,前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点,认为数的整数部分已完,要接着处理小数部分。小数部分的数要除以10或10的幂数变成十分位,百分位,千分位数等等,与前面部分数相加。在拼数过程中,若遇非数字字符,表示数已拼完,将数压入栈中,并且将变量num恢复为0,准备下一个数。这时对新读入的字符进入+、-、*、/及空格的判断,因此在结束处理数字字符的case后,不能加入break语句。5假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO通过对的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false假定被判定的操作序列已存入一维数组中。A和D是合法序列,B和C 是非法序列。设被判定的操作序列已存入一维数组A中。int Judge /判断字符数组A中的输入输出序列是否是合法序列。如是,返回true,否则返回false。 i=0; /i为下标。 j=k=0; /j和k分别为I和字母O的的个数。while /当未到字符数组尾就作。 switch caseI: j+; break; /入栈次数增1。caseO: k+; ifjprintf；exit; i+; /不论Ai是I或O,指针i均后移。if printf；return;else printf；return; /算法结束。 算法讨论在入栈出栈序列即由I和O组成的字符串的任一位置,入栈次数I的个数都必须大于等于出栈次数即O的个数,否则视作非法序列,立即给出信息,退出算法。整个序列即读到字符数组中字符串的结束标记0,入栈次数必须等于出栈次数题目中要求栈的初态和终态都为空,否则视为非法序列。6假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点 ,试编写相应的置空队、判队空 、入队和出队等算法。算法如下：/先定义链队结构:typedef struct queuenodeDatatype data;struct queuenode *next;QueueNode; /以上是结点类型的定义typedef structqueuenode *rear;LinkQueue; /只设一个指向队尾元素的指针置空队void InitQueue /置空队：就是使头结点成为队尾元素QueueNode *s;Q-rear = Q-rear-next;/将队尾指针指向头结点while rear!=Q-rear-next/当队列非空,将队中元素逐个出队s=Q-rear-next;Q-rear-next=s-next;free;/回收结点空间判队空int EmptyQueue /判队空/当头结点的next指针指向自己时为空队return Q-rear-next-next=Q-rear-next;入队void EnQueue /入队/也就是在尾结点处插入元素QueueNode *p= malloc sizeof;/申请新结点p-data=x; p-next=Q-rear-next;/初始化新结点并链入Q-rear-next=p;Q-rear=p;/将尾指针移至新结点出队Datatype DeQueue/出队,把头结点之后的元素摘下Datatype t;QueueNode *p;ifEmptyQueueError;p=Q-rear-next-next; /p指向将要摘下的结点x=p-data; /保存结点中数据if rear/当队列中只有一个结点时,p结点出队后,要将队尾指针指向头结点Q-rear = Q-rear-next; Q-rear-next=p-next;elseQ-rear-next-next=p-next;/摘下结点pfree;/释放被删结点return x;7假设以数组Qm存放循环队列中的元素, 同时设置一个标志tag,以tag= 0和tag = 1来区别在队头指针和队尾指针相等时,队列状态为空还是满。试编写与此结构相应的插入和删除算法。解答循环队列类定义#include template classQueue /循环队列的类定义public: Queue ; Queue delete Q;void EnQueue ;Type DeQueue ;TypeGetFront ;void MakeEmpty front = rear = tag = 0;/置空队列intIsEmpty const return front = rear & tag = 0;/判队列空否intIsFull const return front = rear & tag = 1;/判队列满否private:intrear, front, tag;/队尾指针、队头指针和队满标志Type *Q;/存放队列元素的数组intm;/队列最大可容纳元素个数构造函数template Queue: Queue : rear ,front , tag, m /建立一个最大具有m个元素的空队列。Q =new Typem;/创建队列空间assert ;/断言:动态存储分配成功与否插入函数template voidQueue :EnQueue assert ! IsFull ;/判队列是否不满,满则出错处理rear = % m;/队尾位置进1, 队尾指针指示实际队尾位置Qrear = item;/进队列tag = 1;/标志改1,表示队列不空删除函数template Type Queue :DeQueue assert ! IsEmpty ;/判断队列是否不空,空则出错处理front = % m;/队头位置进1, 队头指针指示实际队头的前一位置tag = 0;/标志改0, 表示栈不满return Qfront;/返回原队头元素的值读取队头元素函数template Type Queue :GetFront assert ! IsEmpty ;/判断队列是否不空,空则出错处理return Q % m;/返回队头元素的值8如果允许在循环队列的两端都可以进行插入和删除操作。要求： 写出循环队列的类型定义； 写出从队尾删除和从队头插入的算法。题目分析 用一维数组 v0.M-1实现循环队列,其中M是队列长度。设队头指针 front和队尾指针rear,约定front指向队头元素的前一位置,rear指向队尾元素。定义front=rear时为队空,%m=front 为队满。约定队头端入队向下标小的方向发展,队尾端入队向下标大的方向发展。1#define M 队列可能达到的最大长度typedefstruct elemtp dataM;int front,rear; cycqueue;2elemtp delqueue /Q是如上定义的循环队列,本算法实现从队尾删除,若删除成功,返回被删除元素,否则给出出错信息。 if printf; exit; Q.rear=%M; /修改队尾指针。returnQ.data%M; /返回出队元素。/从队尾删除算法结束void enqueue / Q是顺序存储的循环队列,本算法实现从队头插入元素x。if Q.rear=%M printf队满; exit; Q.dataQ.front=x; /x 入队列Q.front=%M; /修改队头指针。/ 结束从队头插入算法。9已知Ackermann函数定义如下: 写出计算Ack的递归算法,并根据此算法给出出Ack的计算过程。 写出计算Ack的非递归算法。int Ack if return;elseif returnAck;elsereturnAckm-1,Ack; /算法结束1Ack的计算过程 Ack=Ack1,Ack /因m0,n0而得 =Ack1,Ack /因m0,n=0而得 =Ack1,Ack0,Ack / 因m0,n0而得 = Ack1,Ack0,Ack / 因m0,n=0而得 =Ack1,Ack / 因m=0而得 =Ack / 因m=0而得 =Ack0,Ack /因m0,n0而得 = Ack0,Ack0,Ack /因m0,n0而得 = Ack0,Ack0,Ack0,Ack /因m0,n0而得 = Ack0,Ack0,Ack0,Ack /因m0,n=0而得 = Ack0,Ack0,Ack /因m=0而得 = Ack0,Ack /因m=0而得 = Ack /因n=0而得 =5 /因n=0而得2int Ackerman int akmMN;int i,j;forj=0;j akm0j;=j+1;fori=1;i akmi0=akmi-11;forj=1;j akmij=akmi-1akmij-1; return; /算法结束10已知f为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算的递归算法：求链表中的最大整数；求链表的结点个数； 求所有整数的平均值。#include /定义在头文件RecurveList.h中class List;classListNode /链表结点类friend classList;private:intdata;/结点数据ListNode *link;/结点指针ListNode : data, link /构造函数;class List /链表类private:ListNode *first, current;intMax;int Num;floatAvg ;public:List :first, current /构造函数List /析构函数ListNode* NewNode ;/创建链表结点, 其值为itemvoidNewList ;/建立链表, 以输入retvalue结束voidPrintList ;/输出链表所有结点数据intGetMax return Max ; /求链表所有数据的最大值int GetNum returnNum ; /求链表中数据个数float GetAvg return Avg ; /求链表所有数据的平均值;ListNode* List:NewNode /创建新链表结点ListNode *newnode = new ListNode ;returnnewnode;voidList:NewList/建立链表, 以输入retvalue结束first=NULL;intvalue;ListNode *q;cout value;/输入while/输入有效q=NewNode;/建立包含value的新结点if first = current = q;/空表时, 新结点成为链表第一个结点else current-link= q;current = q; /非空表时, 新结点链入链尾cin value;/再输入current-link = NULL;/链尾封闭voidList:PrintList/输出链表coutnThe List is:n;ListNode *p = first;whilecoutdatalink;cout n; intList:Max/递归算法 : 求链表中的最大值iflink=NULLreturnf-data;/递归结束条件inttemp=Maxlink;/在当前结点的后继链表中求最大值ifdatatempreturnf-data;/如果当前结点的值还要大, 返回当前检点值else returntemp;/否则返回后继链表中的最大值intList :Num /递归算法:求链表中结点个数if return 0;/空表, 返回0return 1+ Num link ;/否则, 返回后继链表结点个数加1floatList :Avg /递归算法 : 求链表中所有元素的平均值if link = NULL /链表中只有一个结点, 递归结束条件n = 1; return data ; else float Sum =Avg link, n * n;n+;return data+Sum / n; #include RecurveList.h/定义在主文件中intmain List test; intfinished;cout finished;/输入建表结束标志数据test.NewList;/建立链表test.PrintList ;/打印链表cout nThe Max is : test.GetMax ;cout nThe Num is : test.GetNum ;cout nThe Ave is : test.GetAve n;printf ;return 0;第4章 串、数组和广义表习题1选择题1串是一种特殊的线性表,其特殊性体现在 。A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符若 2串下面关于串的的叙述中, 是不正确的？A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储,也可以采用链式存储3串ababaaababaa的next数组为 。4串ababaabab的nextval为 。A010104101 B010102101C010100011 D010101011 5串的长度是指 。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数6假设以行序为主序存储二维数组A=array1.100,1.100,设每个数据元素占2个存储单元,基地址为10,则LOC5,5= 。A808 B818 C1010 D10207设有数组Ai,j,数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A5,8的存储首地址为 。ABA+141 BBA+180 CBA+222 DBA+2258设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为 。A13 B33 C18 D409若对n阶对称矩阵A以行序为主序方式将其下三角形的元素依次存放于一维数组B1.n/2中,则在B中确定aijij的位置k的关系为 。Ai*/2+j Bj*/2+i Ci*/2+j Dj*/2+i10AN,N是对称矩阵,将下面三角包括对角线以行序存储到一维数组TN/2中,则对任一上三角元素aij对应Tk的下标k是 。Ai/2+j Bj/2+iCi/2+1 Dj/2+111设二维数组A1. m,1. n即m行n列按行存储在数组B1. m*n中,则二维数组元素Ai,j在一维数组B中的下标为 。A*n+j B*n+j-1 Ci* Dj*m+i-112数组A0.4,-1.-3,5.7中含有元素的个数 。A55 B45 C36 D1613广义表A=a,b,e,则HeadTailHeadTailTail的值为 。A B Cc Dd14广义表的表头是,表尾是 。Aa B C D15设广义表L=,则L的长度和深度分别为 。A1和1 B1和3 C1和2 D2和31已知模式串t=abcaabbabcab写出用KMP法求得的每个字符对应的next和nextval函数值。模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 52设目标为t=abcaabbabcabaacbacba,模式为p=abcabaa计算模式p的naxtval函数值；不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。p的nextval函数值为0110132。p的next函数值为0111232。利用KMP算法,每趟匹配过程如下：第一趟匹配： abcaabbabcabaacbacba abcab第二趟匹配： abcaabbabcabaacbacba abc第三趟匹配： abcaabbabcabaacbacba a第四趟匹配： abcaabbabcabaac bacba abcabaa3数组A中,每个元素Ai,j的长度均为32个二进位,行下标从-1到9,列下标从1到11,从首地址S开始连续存放主存储器中,主存储器字长为16位。求：存放该数组所需多少单元？存放数组第4列所有元素至少需多少单元？数组按行存放时,元素A7,4的起始地址是多少？数组按列存放时,元素A4,7的起始地址是多少？每个元素32个二进制位,主存字长16位,故每个元素占2个字长,行下标可平移至1到11。1242 222 3s+182 4s+142请将香蕉banana用工具 HHead,TTail从L中取出。L=apple,orange,strawberry,peach,pearHHTHTHTL5写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件字符串中的合法字符为A-Z这26个字母和0-9这10个数字。void Count/统计输入字符串中数字字符和字母字符的个数。int i,num36；char ch；fori0；i36；i+numi；/ 初始化whilechgetchar!=# /#表示输入字符串结束。if0=ch=9i=ch48;numi+； / 数字字符elseifA=ch=Zi=ch-65+10;numi+；/ 字母字符fori=0；i10；i+ / 输出数字字符的个数printf数字d的个数dn,i,numi；fori10；i36；i+/ 求出字母字符的个数printf字母字符c的个数dn,i55,numi；/ 算法结束。6写一个递归算法来实现字符串逆序存储,要求不另设串存储空间。题目分析实现字符串的逆置并不难,但本题要求不另设串存储空间来实现字符串逆序存储,即第一个输入的字符最后存储,最后输入的字符先存储,使用递归可容易做到。void InvertStore/字符串逆序存储的递归算法。 char ch;static int i = 0;/需要使用静态变量scanf ;if /规定.是字符串输入结束标志InvertStore; Ai+ = ch;/字符串逆序存储Ai = 0; /字符串结尾标记/结束算法InvertStore。7编写算法,实现下面函数的功能。函数void insert将字符串t插入到字符串s中,插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。说明：不得使用任何库函数题目分析本题是字符串的插入问题,要求在字符串s的pos位置,插入字符串t。首先应查找字符串s的pos位置,将第pos个字符到字符串s尾的子串向后移动字符串t的长度,然后将字符串t复制到字符串s的第pos位置后。对插入位置pos要验证其合法性,小于1或大于串s的长度均为非法,因题目假设给字符串s的空间足够大,故对插入不必判溢出。void insert/将字符串t插入字符串s的第pos个位置。int i=1,x=0; char *p=s,*q=t; /p,q分别为字符串s和t的工作指针ifpos printf;exit;while*p!=0&i p+;i+; /查pos位置 /若pos小于串s长度,则查到pos位置时,i=pos。if printf;exit;else /查找字符串的尾while p+; i+; /查到尾时,i为字符0的下标,p也指向0。while q+; x+; /查找字符串t的长度x,循环结束时q指向0。for=pos ;j-*=*p; p-;/串s的pos后的子串右移,空出串t的位置。 q-; /指针q回退到串t的最后一个字符forj=1;j *p-=*q-; /将t串插入到s的pos位置上 算法讨论 串s的结束标记也后移了,而串t的结尾标记不应插入到s中。8已知字符串S1中存放一段英文,写出算法format,将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。题目分析本题要求字符串s1拆分成字符串s2和字符串s3,要求字符串s2按给定长度n格式化成两端对齐的字符串,即长度为n且首尾字符不得为空格字符。算法从左到右扫描字符串s1,找到第一个非空格字符,计数到n,第n个拷入字符串s2的字符不得为空格,然后将余下字符复制到字符串s3中。void format /将字符串s1拆分成字符串s2和字符串s3,要求字符串s2是长n且两端对齐char *p=s1, *q=s2;int i=0;while p+;/滤掉s1左端空格if printf;exit;while *p!=0 & i*q=*p; q+; p+; i+;/字符串s1向字符串s2中复制if printf; exit;if*= /若最后一个字符为空格,则需向后找到第一个非空格字符 p- ; /p指针也后退while p+;/往后查找一个非空格字符作串s2的尾字符if printf; exit; *q=*p; /字符串s2最后一个非空字符 *=0; /置s2字符串结束标记 *q=s3;p+; /将s1串其余部分送字符串s3。while *q=*p; q+; p+;*q=0; /置串s3结束标记设二维数组a1.m, 1.n 含有m*n 个整数。写一个算法判断a中所有元素是否互不相同?输出相关信息；试分析算法的时间复杂度。题目分析判断二维数组中元素是否互不相同,只有逐个比较,找到一对相等的元素,就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行,每个元素要同本行后面的元素比较一次下面第一个循环控制变量p的for循环,然后同第i+1行及以后各行元素比较一次,这就是循环控制变量k和p的二层for循环。int JudgEqual /判断二维数组中所有元素是否互不相同,如是,返回1；否则,返回0。fori=0;iforj=0;j forp=j+1;p /和同行其它元素比较if printf; return; /只要有一个相同的,就结论不是互不相同fork=i+1;k /和第i+1行及以后元素比较forp=0;pif printf; return; / forj=0;jprintf; return; /元素互不相同/算法JudgEqual结束2二维数组中的每一个元素同其它元素都比较一次,数组中共m*n个元素,第1个元素同其它m*n-1个元素比较,第2个元素同其它m*n-2 个元素比较,第m*n-1个元素同最后一个元素比较一次,所以在元素互不相等时总的比较次数为 +2+1=m*n/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在个位置上均可能相同,这时的平均比较次数约为m*n/4,总的时间复杂度是O。设任意n个整数存放于数组A中,试编写算法,将所有正数排在所有负数前面要求算法复杂性为0。题目分析本题属于排序问题,只是排出正负,不排出大小。可在数组首尾设两个指针i和j,i自小至大搜索到负数停止,j自大至小搜索到正数停止。然后i和j所指数据交换,继续以上过程,直到 i=j为止。void Arrange /n个整数存于数组A中,本算法将数组中所有正数排在所有负数的前面 int i=0,j=n-1,x; /用类C编写,数组下标从0开始whileiwhilei0 i+;whileij & Aj j-;ifi x=Ai; Ai+=Aj; Aj-=x; /交换Ai 与Aj /算法Arrange结束.算法讨论对数组中元素各比较一次,比较次数为n。最佳情况不发生交换,最差情况发生n/2次交换。用类c编写,数组界偶是0.n-1。空间复杂度为O.
展开阅读全文