【习题课】第1-3章课件

第13章习题.第13章习题.1作业15 试用试用ADL语言编写一个算法，判断任一整数语言编写一个算法，判断任一整数 n 是否为素数。是否为素数。.作业15 试用ADL语言编写一个算法，判断任一整数 n 2考察知识点考察知识点l判断素数判断素数素数素数大于大于1的自然数中，除了的自然数中，除了1和此整和此整数自身外，不能被其他自然数整除的数。数自身外，不能被其他自然数整除的数。判断：对于指定的判断：对于指定的n，如果，如果2,n-1内的整内的整数都不能整除数都不能整除n，则，则n为素数。为素数。lADL语言写算法语言写算法算法证明很难，可以使用边界条件和特殊算法证明很难，可以使用边界条件和特殊数据，人工模拟算法执行过程。数据，人工模拟算法执行过程。.考察知识点判断素数.3完成情况完成情况n思想思想基本正确，对素数定义的理解：基本正确，对素数定义的理解：1？n算法算法特殊情况处理：特殊情况处理：n 1？算法输出；？算法输出；nADL语言的使用：语言的使用：运算符号：运算符号：MOD(模模)，DIV(除数除数)，/(除除)；，（取整）；（取整）；？sqrt?fabs()?输入输出参数：设置返回值；中间用输入输出参数：设置返回值；中间用“.”分隔；分隔；条件语句：条件语句：if then else ；for i1 to n step 1(i=i+1?)赋值语句：赋值语句：.完成情况思想基本正确，对素数定义的理解：1？.4参考答案算法算法 S(n.flag)/*判断整数判断整数n是否为素数，将结果保存到变量是否为素数，将结果保存到变量flag*/S1n1？IF(n1)THEN(flagfalse.RETURN.)S2初始化初始化 i2.flagtrue.S3求余判断求余判断 WHILE(in-1)DO (IF(n MOD i)=0 THEN (flagfalse.RETURN.)ii+1.).参考答案算法 S(n.flag).5n正确性验证：正确性验证：n假定假定n7，模拟执行过程，对，模拟执行过程，对i2，3，4，5，6时，分别判断时，分别判断(7 mod i)的取值是的取值是否为否为0。n改进：改进：n-1？n/2 、n1/21/2 n=a b,na2,bn/2,a,b,2,bn/2,a,b,n/2 nann1/21/2,bn,bn1/21/2,a,a,n1/21/2 ,b,b.正确性验证：.6参考答案2算法算法 S(n.flag)/*判断整数判断整数n是否为素数，将结果保存到变量是否为素数，将结果保存到变量flag*/S1n1？IF(n1)THEN(flagfalse.RETURN.)S2初始化初始化 i2.flagtrue.S3求余判断求余判断 WHILE(i n/2 )DO (IF(n MOD i)=0 THEN (flagfalse.RETURN.)ii+1.).参考答案2算法 S(n.flag).7作业1-8n若若A(n)=amnm+a1n+a0是关于是关于n的的m次多项式，次多项式，证明证明A(n)=O(nm)。n设设f(n)和和g(n)是正整数集到正实数集的函数，称是正整数集到正实数集的函数，称f(n)是是O(g(n)当且仅当存在正常数当且仅当存在正常数C和和n0，使得对，使得对任意的任意的n n0，有，有f(n)Cg(n)。n完成情况完成情况：令：令n01，C am+a1+a0，amnm+a1n+a0 Cnm 注意：注意：当当ai 0时，时，aini ainm不一定成立不一定成立。.作业1-8若A(n)=amnm+a1n+a0是关于n的m8n证明：对于所有的证明：对于所有的n1，有：，有：A(n)=i=0,maini i=0,m|ai|ni nm i=0,m|ai|ni-m nm i=0,m|ai|令令C i=0,m|ai|，有，有A(n)Cnm 所以，所以，A(n)=O(nm)。参考答案参考答案.证明：对于所有的n1，有：参考答案.9作业111n 证明对正整数证明对正整数n3，算法，算法BS的元素比较的元素比较次数次数T(n)5n/3-2。n已知：已知：0 n=1 T(n)=1 n=2 T(n/2 )+T(n/2 )+2 n2.作业111 证明对正整数n3，算法BS的元素比较次数T(10n考察知识点考察知识点：数学归纳法：数学归纳法基础归纳：基础归纳：n=c(初值初值)时，命题是正确的；时，命题是正确的；归纳步骤：如果归纳步骤：如果nk1时，命题成立，则时，命题成立，则nk时，命题也成立。时，命题也成立。n完成情况完成情况：1.利用结论利用结论T(n)3n/22，需要注意前提条，需要注意前提条件件当当n是是2的幂时的幂时；2.由由n=k反推反推nk-1时的情况。时的情况。.考察知识点：数学归纳法.11 0 n=1 T(n)=1 n=2 T(n/2 )+T(n/2 )+2 n2nn=3 时，时，T(3)=T(1)+T(2)+2=3，5 3/3-2=3，命题成立。，命题成立。n假设假设n (k+1)/2 (k+1)/2 ，即即k (k+1)/2 (k+1)/2 所以：所以：T(k+1)/2 )5(k+1)/2)/3-2,(1)T(k+1)/2 )5(k+1)/2 )/3-2 (2)T(k+1)=T(k+1)/2 )+T(k+1)/2)+2 5(k+1)/2)/3-25(k+1)/2 )/3-2+2 =5(k+1)/2 +(k+1)/2 )/3-2 /k1=(k+1)/2 +(k+1)/2 =5(k+1)/3-2 综上，命题得证。综上，命题得证。.0 12作业112n给出算法给出算法BS的非递归算法，并说明算法最的非递归算法，并说明算法最多需要多大的辅助空间。多需要多大的辅助空间。.作业112给出算法BS的非递归算法，并说明算法最多需要多大13算法算法SM(A,n.max,min)SM1初始化初始化 maxminA1.SM2比较比较 FOR I=2 TO n DO/求最大和最小元素求最大和最小元素 (IF AI max THEN maxAI.IF AI min THEN minAI).算法SM(A,n.max,min).14BS算法算法算法BS（A，i，j.fmax，fmin）/在数组在数组A的第的第i个元素到第个元素到第j个元素之间寻找最大和最个元素之间寻找最大和最/小元素，已知小元素，已知i j。BS1 递归出口递归出口IF i=j THEN（fmaxfminAi.RETURN.）IF i=j 1 THEN（IF Ai Aj THEN（fmaxAj.fminAi）.ELSE（fmaxAi.fminAj）.RETURN）.BS算法算法BS（A，i，j.fmax，fmin）15BS2 取中值取中值 mid (i+j)/2 BS3 递归调用递归调用 BS（A，i，mid.gmax，gmin）BS（A，mid+1，j.hmax，hmin）.BS4 合并合并 fmaxmaxgmax，hmax.fminmingmin，hmin.BS2 取中值.16完成情况完成情况n做的很少做的很少SM方法；（没有体现分治思想）方法；（没有体现分治思想）依次对比邻近的两个元素，找到较大较小者，依次对比邻近的两个元素，找到较大较小者，不断更新全局最大最小值；不断更新全局最大最小值；依次对比，用数组存放每对的最大最小值；依次对比，用数组存放每对的最大最小值；两个栈分别存放当前起始和终止元素下标；两个栈分别存放当前起始和终止元素下标；一个栈存储中间值，另一个存放最大最小值。一个栈存储中间值，另一个存放最大最小值。（没法确定起始和终止元素的下标）（没法确定起始和终止元素的下标）.完成情况做的很少.17n辅助空间辅助空间：因为采用某种特殊结构，而增加：因为采用某种特殊结构，而增加占用的空间；占用的空间；n占用空间占用空间：算法运行所需要的空间；：算法运行所需要的空间；n方法方法3：数组；：数组；n方法方法4：栈：栈.辅助空间：因为采用某种特殊结构，而增加占用的空间；.18方法4n基本思想基本思想：n创建两个栈，一个存放起始元素的下标，一创建两个栈，一个存放起始元素的下标，一个存放终止元素的下标。个存放终止元素的下标。n每次从栈中弹出一对下标，若两者相等或相每次从栈中弹出一对下标，若两者相等或相差为差为1，则找到最大最小值，否则找到中间，则找到最大最小值，否则找到中间下标，形成两对新的下标，压入栈内。下标，形成两对新的下标，压入栈内。.方法4基本思想：.19示例n数组A=3,9,21,15,8,1916初始：压入起始和结束下标初始：压入起始和结束下标 1和和6；循环：循环：弹出元素弹出元素1和和6；两者不相等、；两者不相等、相差不相差不为为1；取中值取中值(1+6)/2=3；形成两；形成两对新的下标，对新的下标，(1,3)和和(4,6);压入栈；压入栈；弹出弹出4和和6，两者不相等、相差不为两者不相等、相差不为1；取中值取中值(4+6)/2=5；形成两对新的；形成两对新的下标，下标，(4,5)和和(6,6);压入栈内；压入栈内；1346134566.示例数组A=3,9,21,15,8,1916初始：压入起20A=3,9,21,15,8,19134566弹出弹出(6,6)，相等，元素值为，相等，元素值为19，则，则fmax maxfmax,19=19，fmin minfmin,19=19；弹出弹出(4,5)，相差为，相差为1，元素值为，元素值为15和和8，则，则fmax max19,15,8=19，fmin min19,15,8=8；13.A=3,9,21,15,8,19134566弹出(6,621参考答案n算法算法f(A,i,j.fmax,fmin)nf1.初始化初始化 fmaxfminAi.Lstack left;Lstack right;/存储起始和终止下标存储起始和终止下标 left.push(i).right.push(j).nf2.求最大、最小值求最大、最小值 While(!left.IsEmpty()DO (l left.pop().r right.pop().参考答案算法f(A,i,j.fmax,fmin).22IF l=r THEN /相等相等 (fmaxmaxfmax,Al.fmin minfmin,Al.)ELSE(IF r-l=1 /相差为相差为1 THEN(fmaxmaxfmax,Al,Ar.fmin minfmin,Al,Ar.)ELSE(mid=(i+j)/2.left.push(l).left.push(mid+1).right.push(mid).Right.push(r).).IF l=r THEN /23n辅助空间：栈辅助空间：栈nn/2n/2n/4n/41log2n.辅助空间：栈nn/2n/2n/4n/41log2n.24作业21编写算法编写算法Reverse(A,n)，将顺序存储的，将顺序存储的线性表线性表A=(a1,a2,an)转换为转换为A=(an,a2,a1)，要求转换过程中使用尽可能少的辅，要求转换过程中使用尽可能少的辅助空间。助空间。关键点关键点：限制辅助空间的使用：限制辅助空间的使用如果没有这个限制，则可以有多种方法：如果没有这个限制，则可以有多种方法：1.辅助数组；辅助数组；2.双下标同时向中间移动双下标同时向中间移动.作业21编写算法Reverse(A,n)，将顺25分析n只需从线性表的第一个数据元素开始，将只需从线性表的第一个数据元素开始，将第第i i个数据元素与第个数据元素与第n-i+1n-i+1个数据元素相交个数据元素相交换即可。换即可。ni i的变化范围是的变化范围是1 1到到 n/2n/2。a a1 1a a2 2a an-1n-1a an na an na an-1n-1a a2 2a a1 11+n1+n2+(n-2+(n-1)1)(n-1)+2(n-1)+2 n+1n+1.分析只需从线性表的第一个数据元素开始，将第i个数据元素与第n26参考答案算法算法ReverseReverse（A A，n.An.A）Reverse1.Reverse1.元素互换元素互换 FOR i=1 TO FOR i=1 TO n/2 DO DO Ai An-i+1.Ai An-i+1.参考答案算法Reverse（A，n.A）.27作业2-8n在单链表类在单链表类SLISTSLIST中添加一个成员函数，将单中添加一个成员函数，将单链表中元素的次序完全颠倒。链表中元素的次序完全颠倒。.作业2-8在单链表类SLIST中添加一个成员函数，将单链表中28利用堆栈；利用堆栈；从表头删除，插入表尾；从表头删除，插入表尾；(不推荐不推荐)换数据域的取值，换数据域的取值，p1和和p2向中间移动，更换向中间移动，更换数据域的取值。数据域的取值。headp1p2.利用堆栈；headp1p2.29方法4n思想：从左向右，依次更换邻近结点的指针方向。思想：从左向右，依次更换邻近结点的指针方向。n初始设置，第一个元素需要被放到表尾，指向空指初始设置，第一个元素需要被放到表尾，指向空指针，针，p1=null，p2=next(head)/第一个元素第一个元素headp22p3345p1nullp11p26P3 next(p2)next(P2)P1./反转P1 P2.P2 P3.方法4思想：从左向右，依次更换邻近结点的指针方向。headp30参考答案n算法 Reverse(head.head)/*将指针 head 所指向的链表倒置*/RV1空链表和1个节点链表 IF(next(head)=NULL)RETURN.RV2指针初始化/P1,P2 分别指向两个连续的节点P1 NULL.P2 next(head).参考答案算法 Reverse(head.head).31RV3反转链表WHILE(P2 NULL)DO(P3 next(p2)next(P2)P1./反转节点指针 P1 P2.P2 P3./移动3个指针）RV4head指向反转链表 next(head)P1.p1p2.RV3反转链表p1p2.32作业211n已知线性表中的元素以已知线性表中的元素以data值递增有序排列，并以值递增有序排列，并以单链表做存储结构。试写一高效的算法，删除表中单链表做存储结构。试写一高效的算法，删除表中所有值大于所有值大于mink且小于且小于maxk的元素，同时释放被的元素，同时释放被删结点空间，并分析算法的时间复杂度。删结点空间，并分析算法的时间复杂度。n链表是有序的：链表是有序的：找到区间找到区间n特殊情况的处理特殊情况的处理：表为空，：表为空，元素都大于元素都大于maxk(第一个元素大于第一个元素大于maxk)；元素都小于元素都小于mink(最后一个元素小于最后一个元素小于mink)。.作业211已知线性表中的元素以data值递增有序排列，并以33n主要思想主要思想：找到大于找到大于mink的第一个元素，删除操作，直至元的第一个元素，删除操作，直至元素大于素大于maxk。n时间复杂度时间复杂度：比较为基本运算比较为基本运算 最好最好：空，元素都大于空，元素都大于maxk（找不到）（找不到）/O(1)最坏：元素都小于最坏：元素都小于mink（找不到），（找不到），元素都小于元素都小于maxk，O(n)；.主要思想：.34算法 LD(L,mink,maxk)nLD1.特殊情况特殊情况 IF mink maxk THEN(RETURN.)nLD2.初始化初始化 phead.prevp.p next(p)nLD3.找找 WHILE(p NULL AND data(p)maxk)DO (IF(data(p)mink)THEN (prev p.p next(p)/向后移动向后移动 ELSE(next(prev)next(p).q p.p next(p).AVAILq.)/删除删除qRETURN.prevheadpPprevp.算法 LD(L,mink,maxk)LD1.特殊情况35作业217n对于顺序堆栈和链式堆栈对于顺序堆栈和链式堆栈s，分别编写函数，分别编写函数SelectItem(Stack&s,int n)，要求在，要求在堆栈中查找元素堆栈中查找元素n在栈中第一次出现的位置，在栈中第一次出现的位置，并将该位置元素移至栈顶，同时其他元素次并将该位置元素移至栈顶，同时其他元素次序不变。（注意：用序不变。（注意：用int匹配堆栈的模板）匹配堆栈的模板）.作业217对于顺序堆栈和链式堆栈s，分别编写函数Selec36n基本思想基本思想：n取栈顶元素，若不匹配，则进行弹栈操作；取栈顶元素，若不匹配，则进行弹栈操作；n找到（或无法找到）后恢复原来的元素次找到（或无法找到）后恢复原来的元素次序。序。n关键点：关键点：记录弹出的顺序，后弹出的元素能记录弹出的顺序，后弹出的元素能够先被压回原来的栈够先被压回原来的栈，因此需要使用一个辅，因此需要使用一个辅助堆栈。助堆栈。.基本思想：.37示例101051511212s shelpStackhelpStack51517 73 3n=5151511212101051517 73 37 751515151121210103 37 77 73 35151.示例105112shelpStack5173n=51511238参考答案int SelectItem(Stack&s,int n)AStack temp(100);/顺序堆栈，辅助栈顺序堆栈，辅助栈 /LStack temp;/链式堆栈链式堆栈 bool flag=false;/是否存在元素是否存在元素n int loc=0;/记录记录n所在的位置所在的位置 while(!s.isEmpty()&s.Peek()!=n)temp.Push(s.Pop();loc+;栈非空且当前元素不等于n.参考答案int SelectItem(Stack 39 if(!s.isEmpty()s.Pop();flag=true;/弹出弹出n while(!temp.isEmpty()/将辅助栈中元素压入原栈将辅助栈中元素压入原栈 s.Push(temp.Pop();if(flag)then s.Push(n)；else loc=-1;return loc;因为找到元素而跳出循环.if(!s.isEmpty()因为找到元素40作业225n编写并实现双端队列类，双端队列是可进行如编写并实现双端队列类，双端队列是可进行如下操作的线性表。下操作的线性表。n(1)push(item)item插入到队列的前端；插入到队列的前端；n(2)pop(item)删除前端元素且赋给删除前端元素且赋给item；n(3)inject(item)item插入尾端；插入尾端；n(4)eject(item)删除尾端元素且赋给删除尾端元素且赋给item.作业225编写并实现双端队列类，双端队列是可进行如下操作的41n结点结构结点结构SLNode：数据域和指针域；：数据域和指针域；n类成员：队首和队尾的类成员：队首和队尾的SLNode类型指针、指示元类型指针、指示元素个数的整型变量；素个数的整型变量；nPush(item插入队列前端插入队列前端)若空，则加入一个以若空，则加入一个以item为数据域的结点，元素个为数据域的结点，元素个数为数为1；否则，；否则，temp记录原队首指针记录原队首指针front；创建以创建以item为数据域的新结点，作为新的队首，赋为数据域的新结点，作为新的队首，赋值给值给front；front的指针域指向的指针域指向temp，元素个数加，元素个数加1。.结点结构SLNode：数据域和指针域；.42nPop(删除前端元素，并赋值删除前端元素，并赋值item)n若空，则错误；否则，若空，则错误；否则，temp记录原队首指针记录原队首指针front；队首后移，即队首后移，即frontnext(front)；返回返回temp的数据域；的数据域；删除删除temp结点，元素个数减结点，元素个数减1；若大小为零，则队尾指针若大小为零，则队尾指针rear赋值为赋值为NULL。.Pop(删除前端元素，并赋值item).43nInject(item插入队尾插入队尾)n若空，则加入一个以若空，则加入一个以item为数据域的结为数据域的结点，元素个数为点，元素个数为1；否则，；否则，创建以创建以item为数据域的新结点为数据域的新结点temp，作为新的队尾，即作为新的队尾，即next(rear)temp；队尾指针后移，即；队尾指针后移，即rear next(rear);元素个数加元素个数加1。.Inject(item插入队尾).44nEject(删除队尾元素并赋值给删除队尾元素并赋值给item)n若空，则出错；否则，若空，则出错；否则，找到队尾指针的前驱指针找到队尾指针的前驱指针 temp front.IF(temp rear)THEN (WHILE(next(temp)rear)DO (temp next(temp)队尾指针更新，即队尾指针更新，即rear temp，要删除结点是要删除结点是next(temp)，返回数据域，删除结点，元，返回数据域，删除结点，元素个数减素个数减1。若大小为零，若大小为零，front和和rear赋值为赋值为NULL。.Eject(删除队尾元素并赋值给item).45作业310n设稀疏矩阵设稀疏矩阵M Mm m n n中有中有t t个非零元素，用三元个非零元素，用三元组表的方式存储组表的方式存储.请设计一个算法，计算请设计一个算法，计算矩阵矩阵M M的转置矩阵的转置矩阵N N，且算法的时间复杂性，且算法的时间复杂性为为O(n+t).O(n+t).注意，书中给出的算法的复杂注意，书中给出的算法的复杂性为性为O(nO(n t)t)。.作业310设稀疏矩阵Mmn中有t个非零元素，用三元组表的46M=50 0 0 010 0 20 0 0 0 0 0-30 0 -60 5N=50 10 0 -300 0 0 00 20 0 -600 0 0 50050a01010a11220a230-30a332-60a4335a50050b00110b103-30b22120b323-60b4335b5算法的关键是求出算法的关键是求出a中元素在中元素在b中的位置中的位置.M=50 0 0 0N=50 10 47BindexBindex0 0；FOR FOR j j=0 TO=0 TO n n1 1 DO DO FOR FOR k k=0 TO=0 TO t t1 1 DO DO IF col(Ak)=j Then IF col(Ak)=j Then(row(BBindex)=j.(row(BBindex)=j.col(BBindex)=row(Ak).col(BBindex)=row(Ak).value(BBindex)=Value(Ak).value(BBindex)=Value(Ak).Bindex+Bindex+）a0a1a2a3a4a500502120011033523-6003-30j=0,k=0,a0,列坐标=0；存储j=0;k=1;a1,列坐标=0；存储j=0;k=2;a2,列坐标=2；j=0;k=3;a3,列坐标=0；存储j=0;k=4;j=0;k=5;j=1;k=0005030-301010.Bindex0；a00050212001103352348a0a1a2a3a4a500502120011033523-6003-30005030-301010j=1,k=0,a0,列坐标=0j；j=1,k=1;列坐标1j=1,k=2;j=1,k=3;j=1,k=4;j=1,k=5;j=2,k=0；j=2,k=1；j=2,k=2，列坐标=2=jFOR FOR j j=0 TO=0 TO n n1 1 DO DO FOR FOR k k=0 TO=0 TO t t1 1 DO DO IF col(Ak)=j Then IF col(Ak)=j Then2201.a000502120011033523-6003-30049005030-30101033532-601220a0a1a2a3a4a500502120011033523-6003-30b2axby?y=列坐标小于列坐标小于col(ax)的元素个数的元素个数+列坐标等于列坐标等于col(ax)且在且在ax之前的之前的 元素个数元素个数.005030-30101033532-601220a0050a0a1a2a3a4a500502120011033523-6003-30基本思想：数组数组数组数组numnum存储存储存储存储a a中每列非零元素个数；中每列非零元素个数；中每列非零元素个数；中每列非零元素个数；数组数组数组数组pospos存储存储存储存储a a中每列第一个非零元素在中每列第一个非零元素在中每列第一个非零元素在中每列第一个非零元素在b b的三元的三元的三元的三元 组表中的位置；组表中的位置；组表中的位置；组表中的位置；302101230123num0335pos.a000502120011033523-6003-30基51算法算法:TRANSPOSE(A.B):TRANSPOSE(A.B)n nTP1TP1初始化初始化 nRows(B)Cols(A).nRows(B)Cols(A).n n/B/B的行数等于的行数等于A A的列数，的列数，B B的列数等于的列数等于A A的行数的行数Cols(B)Rows(A).Cols(B)Rows(A).tCount(B)Count(A).tCount(B)Count(A)./B /B中非中非0 0元素的个数等于元素的个数等于A A中非中非0 0元素的个数元素的个数n nTP2 TP2 定义数组定义数组定义数组定义数组numnum FOR iFOR i 0 TO 0 TO n n-1 DO-1 DO numnum i i0 0.FOR iFOR i 0 TO t-1 DO0 TO t-1 DO（j j col(A col(A i i).).numnum j jnumnum j j+1.+1.）/A/A中每列非零元素个数中每列非零元素个数中每列非零元素个数中每列非零元素个数 pos0pos0 0 0/定义数组定义数组定义数组定义数组pospos FOR i 1 TO n-1 DO FOR i 1 TO n-1 DO (posi (posi posposi-1+numi-1)i-1+numi-1).算法:TRANSPOSE(A.B).52a0a1a2a3a4a500502120011033523-6003-3003102231num00132335pos005030-30101033532-601220b0b1b2b3b4b5.a000502120011033523-6003-30053n nTP3TP3 处理三元组表处理三元组表处理三元组表处理三元组表 FOR i 0 TO t-1 DO FOR i 0 TO t-1 DO (pcol(A i)./(pcol(A i)./列坐标列坐标列坐标列坐标 kposp.kposp./该列坐标的该列坐标的该列坐标的该列坐标的元素元素元素元素在在在在b b中的位置中的位置中的位置中的位置 col(Bk)row(Ai).col(Bk)row(Ai).row(Bk)col(Ai).row(Bk)col(Ai).val(Bk)val(Ai).val(Bk)val(Ai).posp posp+1 posp posp+1).).a0a1a2a3a4a500502120011033523-6003-300335pos0050.TP3处理三元组表a000502120011033554n nTP3处理三元组表处理三元组表 FOR i 0 TO t-1 DO (pcol(A i).kposp.col(Bk)row(Ai).row(Bk)col(Ai).val(Bk)val(Ai).posp posp+1).a0a1a2a3a4a500502120011033523-6003-301335pos00501010.TP3处理三元组表a000502120011033555n nTP3处理三元组表处理三元组表 FOR i 0 TO t-1 DO (pcol(A i).kposp.col(Bk)row(Ai).row(Bk)col(Ai).val(Bk)val(Ai).posp posp+1).a0a1a2a3a4a500502120011033523-6003-302335pos005010101220.TP3处理三元组表a000502120011033556n nTP3处理三元组表处理三元组表 FOR i 0 TO t-1 DO (pcol(A i).kposp.col(Bk)row(Ai).row(Bk)col(Ai).val(Bk)val(Ai).posp posp+1).a0a1a2a3a4a500502120011033523-6003-302345pos005030-3010101220.TP3处理三元组表a000502120011033557n nTP3处理三元组表处理三元组表 FOR i 0 TO t-1 DO (pcol(A i).kposp.col(Bk)row(Ai).row(Bk)col(Ai).val(Bk)val(Ai).posp posp+1).a0a1a2a3a4a500502120011033523-6003-303345pos005030-30101032-601220.TP3处理三元组表a000502120011033558n nTP3处理三元组表处理三元组表 FOR i 0 TO t-1 DO (pcol(A i).kposp.col(Bk)row(Ai).row(Bk)col(Ai).val(Bk)val(Ai).posp posp+1).a0a1a2a3a4a500502120011033523-6003-303355pos005030-30101033532-601220.TP3处理三元组表a000502120011033559n nTP3处理三元组表处理三元组表 FOR i 0 TO t-1 DO (pcol(A i).kposp.col(Bk)row(Ai).row(Bk)col(Ai).val(Bk)val(Ai).posp posp+1).a0a1a2a3a4a500502120011033523-6003-303356pos005030-30101033532-601220.TP3处理三元组表a000502120011033560f(j)a b c a b c a c a b c a-1 -1 -1 0 1 2 3 -1 0 1 2 3 作业2-15.f(j)a b c a b c a 61a b c a a b b a b c a b .a b c a a b b 62